I've recently watched a few D2 speedruns and noticed the reset strategy to get the "right" A1 town exit; I've since found the thread explaining it here: https://www.speedrun.com/d2lod/thread/wi5mn
I've put some thought into why this works and how this can be exploited further....
- How does a pseudo-random number generator (PRNG) work?
A PRNG has some internal state and when you ask it for a random number this state changes in a deterministic way. An example for a simple PRNG would be calling this function on some state x and returning the state as random result for each number generated.
f(x) = x * 7 mod 13
Let's say x starts with 1 (called the seed) and we want some random numbers, here's what we get:
1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2, 1
That's clearly a pretty bad PRNG because it is very predictable. Seeing just one result allows us to calculate the next one (because we give out the complete state as result, easy to fix). But imagine using very large prime numbers instead of 7 and 13. And a more complex operation than a multiplication.
And imagine not being able to observe the full result but just a coin flip, e.g., mapping 1-6 to head and 7-12 to tail in this function for the output. Then it's much harder to predict.
Now there are two properties of a RNG that we are interested in:
i) how predictable is it, i.e., can we get the internal state by observing the output? ii) how big is the state, i.e., in our case x can only take 12 different values
The thing we are interested here is only the size of the state. You might think that i) is the more interesting thing, but it turns out the size is the limiting factor for Diablo II map generation.
Our example function above only has 12 different states (values 1 to 12). That means two things:
i) it repeats itself after at most 12 different outputs, see example above, it gets back to 1 in the 13th output, since that's the only state it has it'll just start over ii) there are only 12 different seeds that can be used, i.e., 12 different combinations for the first 12 outputs
We care about ii) here. Assume that this function would be used to generate a map and our map just consists of 4 random numbers between 1 and 12
How many maps that consist of 4 numbers between 1 and 12 are there? 12 * 12 * 12 * 12 = 20736 How many different maps can that PRNG generate? Only 12. Each seed (initial value) will generate a unique map.
So for example we'll never get the map 1, 10, 2, 3 because there is no such seed that generates this sequence. Or we never get a map where the same number occurs twice because it only repeats after 12 outputs, but we only look at 4.
So even tough it looks like there are only very few maps our PRNG is already insufficient.
- So you build a bad PRNG, a real game would surely use a better one with more than 12 possible seeds?
Diablo 2 seems to use a RNG with a seed of 64 bits: https://github.com/OpenDiablo2/OpenDiablo2/blob/8a547ebf0e23daedbaf0c5717b9f81b72a74ecb0/d2core/d2gamestate/d2gamestate.go#L22
That means there are a total of 2^64 (that's 18,446,744,073,709,551,616) different possible maps. That ought to be enough for a true randomization of maps, right? Nope.
Diablo 2 maps have lots of coin flip (or 3-way or 4-way) "decisions" that are being made during generation. Examples are:
- Town exits in A1 and A2
- Exit directions on maps and caves
- Is there a river in map X
- Which direction is the barracks in?
- Is the <whatever> dungeon on the left or right part of the map?
- Are there portals/weird escher-style paths/nothing in direction X in the Arcane Sanctuary?
- Which tomb is the right one?
- Is the path between the different Kurast areas to the left or the right?
- Are there 2 chests or 3 chests in X?
- ....
You can probably find tons of these examples. We are looking for ones that should not be correlated. For example, there is some correlation between area exits as some configurations are impossible (they'd run into each other).
Let's look at each of these decisions as a coin flip decision. For most it's clearly more than a single coin flip (4 town exits in A1, 3 exits for many areas), let's ignore that and say there's one coin flip on average in each decision.
How many of these coin flips in maps can you find? 100? Probably! And these are just the decisions that you can easily spot in the game. There's way way more than that internally.
How many different maps are there theoretically if they only consist if 100 coin flips? 2^100 maps. How many different maps can possibly exist with a 64 bit seed? Only 2^64.
2^100 is way more than 2^64. It's a factor of 2^36 more, that's around a factor of 68 billion more. In this example only 0.00000000145519% out of the maps could exist are actually being generated if maps consist of only 100 coin flips. But maps are way more complex than that so it's even worse (or better, for us)!
Diablo 2 can only make 64 coin flips for map generation without becoming predictable. There are more than 64 coin flips in maps, so we can gain some information by observing maps.
A lot of things that could be possible are simply never generated due to this limitation and there are unexpected correlations that can be exploited.
- Some assumptions about map generation in Diablo 2
There's one big assumption to make this useful that seems to be true: The whole map is generated at once for all acts. It is clearly generated at least the starting act at the same time (otherwise map hacks that just read local data wouldn't work on battle.net). It looks like it generates everything for all acts in the beginning as https://www.speedrun.com/d2lod/thread/wi5mn indicates that are correlations between A1 town layout and A3 and A4.
This is important: the whole problem could be avoided if D2 generated maps as you first enter the area. Because the PRNG state would then be influenced by whatever you did before you entered the area (such as kills, spell damage calculations, whatever else the seed is being used for).
This can be tested: start the game with --seed X and check in new games whether all acts look the same in different play-throughs. I guess they do?
- Finding correlations (in an automated way)
There are probably way more correlations than have been found. There's probably stuff like "real tomb was circle, therefore exit in area X faces direction Y". These could be figured out:
i) make a list with easily identifiable "markers" like the examples I gave in 2) ii) create a new map on a character that has all acts revealed iii) find all markers/results of these coin flips or X-way decisions iv) repeat several times
Once you got enough data you can write a simple tool to find correlations. Note that these can be more complex than just one finding implies one other. It could be that three different decisions are tails imply that another two can never be heads.
Gathering that data can be automated. Inject some code in the game, make it generate maps (in the simplest case by just starting a game). Look at what it generated in memory. Example code from a map hack looks easy enough: https://github.com/planqi/slashdiablo-maphack/blob/master/BH/Modules/Maphack/Maphack.cpp#L802
Stuff it finds has a position and an ID. Something like finding "tower in A1 is on the left part of the map" or "exit in arcane sanctuary is top right" is easy to figure out based on this.
No, I didn't do any of this. I didn't even play the game in 15 years... I'm just procrastinating here...
- Fun fact: more serious PRNG problems
This "limitation" isn't really a problem for a game like D2 when played normally. But there has been at least one case of an online poker site using a seed of only 64 bits, i.e., they had only 2^64 different possibilities the deck could be shuffled. However, there are 52! ways a deck could be shuffled. 52! is way way way bigger than 2^64 (it's bigger by factor of 4 followed by 48 zeroes). Clever people did exploit that to earn serious money. (Can't find the story right now, was ~10 years ago)
Problems with the PRNG in slot machines are also not unheard of, there's a fun story of people feeding the output of slot machines to a phone app which then told them when to bet a lot of money because the next move is gonna be a winner: https://www.wired.com/2017/02/russians-engineer-brilliant-slot-machine-cheat-casinos-no-fix/
Edit 1: removing accidental smileys Edit 2: typos