Tweet
I've been fooling around with this for awhile and finally, I think, have got it working.
Most Civ players know that the layout of huts on a map follows a pattern. There is one hut location for every 32 map squares with huts appearing only when the location is on land. There are, therefore, 32 possible hut patterns and one known hut location is sufficient to determine which pattern is being used.
The hut pattern is linked to the special resource pattern since both use the same map seed to generate hut and resource locations. One resource square appears for every 16 map squares and thus there are 16 resource location patterns. But the two types of resources have four different distribution patterns within a resource diamond, giving a total of 64 resource patterns. The hut pattern repeats twice within these 64 patterns. The pattern on a specific map is determined by a seed number randomly generated by Civ2 at startup or set in the map editor.
If the algorithm used to create the patterns is known, and the seed is known, then all possible hut locations can be predicated for any map. After study of the hut pattern and the shifts in the pattern caused by varying the seed with the map editor, I have derived an algorithm which conforms to the distribution of huts seen in the game.
To use this algorithm to predict hut locations, the map seed must be known. This is not available to the player without examination of the map in the editor. However, if one hut location is known, the equation can be transposed to solve for the seed. The seed in turn can then be used to generate all other hut locations.
Warning: If you don't want to know how to predict hut locations (removing some of the mystery of the game) stop reading here.
Hut locations are determined by applying a hashing algorithm to the normalized sum and difference of the X,Y map coordinates. It is a modulo-32 hash using the random seed. Predicting hut locations involves two steps: first, determination of the seed from one known hut location. Next, generation of all possible hut locations using the seed.
Determining the Seed:
1) NSum = (X + Y)/2 ; NDiff = (X - Y)/2
Civ maps use only half the address space of the map dimensions since all coordinates are either pairs of even numbers or pairs of odds. Thus, the sum and difference of the map coordinates needed to be "normalized" by dividing them by two.
2) NDiff = RemainderOf( (NDiff + 4096) / 4096 )
To simulate unsigned arithmetic, add and then divide by a power of 2 after subtractions. Nothing magic about 4096, you could use any sufficiently large power of 2.
3)Hash = (NSum/4) x 11 + (NDiff/4) x 13 + 8
4) Seed = RemainderOf(NSum/4) + RemainderOf(NDiff/4) x 4 - RemainderOf(Hash/32)
5) Seed = RemainderOf( (Seed + 32) / 32)
This derives a modulo-32 seed for hut pattern generation.
Generating Hut Locations:
1) For each coordinate pair on the Civ map, calculate the values of NSum, NDiff, and Hash.
2) Hash = RemainderOf( (Hash + Seed) / 32)
3) If Hash = RemainderOf(NSum/4) + RemainderOf(NDiff/4) x 4
then the location will hold a hut unless, of course, the terrain is water.
Happy hunting.
Most Civ players know that the layout of huts on a map follows a pattern. There is one hut location for every 32 map squares with huts appearing only when the location is on land. There are, therefore, 32 possible hut patterns and one known hut location is sufficient to determine which pattern is being used.
The hut pattern is linked to the special resource pattern since both use the same map seed to generate hut and resource locations. One resource square appears for every 16 map squares and thus there are 16 resource location patterns. But the two types of resources have four different distribution patterns within a resource diamond, giving a total of 64 resource patterns. The hut pattern repeats twice within these 64 patterns. The pattern on a specific map is determined by a seed number randomly generated by Civ2 at startup or set in the map editor.
If the algorithm used to create the patterns is known, and the seed is known, then all possible hut locations can be predicated for any map. After study of the hut pattern and the shifts in the pattern caused by varying the seed with the map editor, I have derived an algorithm which conforms to the distribution of huts seen in the game.
To use this algorithm to predict hut locations, the map seed must be known. This is not available to the player without examination of the map in the editor. However, if one hut location is known, the equation can be transposed to solve for the seed. The seed in turn can then be used to generate all other hut locations.
Warning: If you don't want to know how to predict hut locations (removing some of the mystery of the game) stop reading here.
Hut locations are determined by applying a hashing algorithm to the normalized sum and difference of the X,Y map coordinates. It is a modulo-32 hash using the random seed. Predicting hut locations involves two steps: first, determination of the seed from one known hut location. Next, generation of all possible hut locations using the seed.
Determining the Seed:
1) NSum = (X + Y)/2 ; NDiff = (X - Y)/2
Civ maps use only half the address space of the map dimensions since all coordinates are either pairs of even numbers or pairs of odds. Thus, the sum and difference of the map coordinates needed to be "normalized" by dividing them by two.
2) NDiff = RemainderOf( (NDiff + 4096) / 4096 )
To simulate unsigned arithmetic, add and then divide by a power of 2 after subtractions. Nothing magic about 4096, you could use any sufficiently large power of 2.
3)Hash = (NSum/4) x 11 + (NDiff/4) x 13 + 8
4) Seed = RemainderOf(NSum/4) + RemainderOf(NDiff/4) x 4 - RemainderOf(Hash/32)
5) Seed = RemainderOf( (Seed + 32) / 32)
This derives a modulo-32 seed for hut pattern generation.
Generating Hut Locations:
1) For each coordinate pair on the Civ map, calculate the values of NSum, NDiff, and Hash.
2) Hash = RemainderOf( (Hash + Seed) / 32)
3) If Hash = RemainderOf(NSum/4) + RemainderOf(NDiff/4) x 4
then the location will hold a hut unless, of course, the terrain is water.
Happy hunting.
Comment