Devlog #2: Linear Congruential Generators
There are effects that we want to apply to the whole map in Goblin Camp, such as changing seasons tile by tile or having snow gradually melt. When a season changes the effect has to be applied to every tile on the map, it would look very odd to have one tile of winter remain while the rest of the map has moved on to summer. At the same time we want to apply the changes randomly so that it doesn’t look too “mechanical”. So what we want to do is to choose random tiles on the map one by one and apply the change (be it changing the season or whatever else).
“Choosing a tile on the map” can be thought of as just choosing a number between 0 and N, where N is the number of tiles on the map in total. You can imagine that each tile on the map has it’s own unique number, just start counting from any corner and go row by row. A 10 x 10 map has 100 tiles, so starting from 1 you’d count up to 100. Thus to choose a random tile you just need to throw a 100-sided die and you can convert that number into a tile.
Generating random numbers is very commonplace in games, and most if not all game engines will provide you various ways to get a random number in a given range. One way to change the season in Goblin Camp would be to just use a regular random number generator. The main problem with that approach is that we would get duplicate numbers, and we would not have any guarantee that we’d hit every tile either, so we would have to implement a backup method that would check each tile to make sure it had been changed. We would end up checking most tiles multiple times, wasting a lot of CPU time in doing so.
So how can we avoid duplicates and avoid having to verify that we changed every tile? One way would be to make a list of all of the numbers between 0 and N, and then shuffling that list so the numbers are in random order, and just removing numbers from the list one by one. That way we would encounter each number only once and know that once the list is empty all of the tiles have been changed. This would be fine if the number of tiles were relatively small, but Goblin Camp has large maps so the amount of memory required to list all of the numbers, and the time it would take to generate and shuffle them, make this method less then optimal.
There happens to be a very convenient mathematical method of generating a sequence of numbers in random order while also only generating each number once. An algorithm called a linear congruential generator (LCG). LCG’s have often been used just to generate random numbers, but by selecting the parameters just right it will give us each number in our range once and in random order. Compared to the list method described above, the memory required to keep an LCG’s state is minimal and isn’t related to how many numbers you need, and the code is very simple so generating new numbers is very fast.
The randomness of LCGs is considered to be relatively poor, much better general use random number generators exist and should be used when the quality of the random numbers matters. In this case though exactly how random our numbers are is not important.
The Hull–Dobell Theorem describes the requirements for the parameters of the LCG, but I won’t go deeper into that in this blog post. Suffice to say that as long as you choose the parameters so that they satisfy the theorem, you’ll get each number in your range once and in random order.
Here is our LCG in action (at 10x speed):
