Location of Huts

[rah]

Yep, Ming and I were discussing that this weekend, after your initial post. Since our four person game almost always play on a 39X49 world, it would be quite easy to come up with a grid that would list the coordinates of all the huts for each of the seed settings. (Find one, know the rest) I'm not sure if we think that's appropriate.

RAH

[samson]

Thanks, Rah.

This may well be an example of analytical ovekill, but it was fun. Practically, I don't think your calculator would be of much use, but a nice utility program that takes one hut coordinate pair as input and spits out a list of other hut sites might be helpful.

[rah]

Huts have always played an important role in the game. Especially in MP games. Knowing where the huts are can turn a game. Now we can find all the huts after one hut instead of the few extras we needed earlier. Even though I doubt I'll be pulling out a calculator during an MP game. The turns move real fast early and by the time you get a chance to breath, you've already uncovered enough huts to know where the rest are.

[Ming]

And what's wrong with trying to understand the game as good as we can. In MP games, every edge helps

[Caesar the Great]

we're practically playing god here with the game

...soon we'll be able to replicate it perfectly

[rah]

Very good. We always needed two huts, one from two different four patterns, to figure it out where the rest were.

Well done.

[samson]

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.