Location of Huts

[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.

[rah]

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

Well done.

[Caesar the Great]

we're practically playing god here with the game

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

[Ming]

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

[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.

[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]

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

[-Jrabbit]

Hmm. Ming says "every edge helps." Rah says he's "not sure if...that's appropriate."



This one will be worth watching...

[Cyrion]

Samson, just a question: what do you mean in your formula with "RemainderOf" ?? Do you mean the integer part of the result of the division?? Or what else??

I'm just trying to find an easy way to use your research...

[samson]

Cyrion,

"RemainderOf" means the remainder of an integer divsion. For example the RemaindOf( 23 / 4) is 3. This is also known as a Modulo or Mod operation. Most calculators have a Mod button. The Windows "Calculator" app does, in scientific mode.

[Cyrion]

Ok, it's the other part of the division result! I should have guessed...

Now I just need to find how it's called in Excell and then I might, for the first time, be of use to someone in Poly!


EDIT: OK, found it, and it's called... MOD! I sometimes feel sooo stupid...

[samson]

Cyrion,

If you are adept at Excel programming, you could be of great use in the civlab on the Supply and Demand project. There are 30+ formulas involving much input gathering and calculation to determine Supply and Demand commodities for a city. A spreadsheet that prompted for the input and did all the calculations would be quite valuable, if you're interested.

[Scouse Gits]

A program (originally coded in VB) will be posted in a new thread momentarily ...

SG[1]

[SlowThinker]

Since I don't like a disorder, I am moving the continuation of samson's formulas from theGits' Hut Finder Program thread here:

Originally posted by samson
Using the same modulo-32 SEED as for huts, you can predict all specials locations (although not their type).

For all map coordinates:
1) Calculate Nsum and NDiff the same way as for huts.
2) Calculate Hash without the "+ 8" offset: Hash = (NSum/4) x 11 + (NDiff/4) x 13
3) Use Modulo-16 instead of 32: Hash = RemainderOf( (Hash + Seed) / 16)
4) If Hash = RemainderOf(NSum/4) + RemainderOf(NDiff/4) x 4 then the location is a special.

Determining the type of special (fish/whale) requires a modulo-64 seed and at least three data points.

Originally posted by samson
In order to generate hut locations from specials, you'd need the location and types of three specials from the same group of four. This can determine the modulo-64 seed which could be used to predict not only hut and special locations but the type of special as well.

Originally posted by samson
Distance can be calculated with the algorithm I described in STEP 1 in the thread "Calculating Caravan and Freight Delivery Payments".

[SlowThinker]

Originally posted by samson
Determining the type of special (fish/whale) requires a modulo-64 seed and at least three data points.

What are 'three data points' ?

[Elephant]

I presume from context they are the X,Y coordinates of three specials in a group.

Do you have MapEditor? Try starting with a blank ocean map and change the Resource Seed in increments of 16 (2-18-34-50, 3-19-35-51, etc...). Then do increments of 64.

[SlowThinker]

Originally posted by Elephant in Which utilities/helpers do you use?
Beware, though, that HF calculates a "base" seed, not the exact seed; the specials will be in the right place, but they may be the opposite "type" (Whale or Fish). To get the seed right you need to expose more of the map to see several groups of specials, then experiment with the seed in MapEditor by adding 16 or 32 repetitively until you get the right arrangement.

I see HutFinder shows values up to 32 (or 31?). Since there is 64 different seeds, you have to try 2 seeds if you want to find out the correct seed?
Why hut finder doesn't distinguish between seeds x and x+32? There is not sufficient information from one hut position?

...then experiment with the seed in MapEditor by adding 16 or 32 repetitively...

I suppose adding 32 once would be sufficient...?

[SlowThinker]

I found the rule: the type of special depends directly on the coordinates, but is different for seed patterns 0-15, 16-31, 32-47, 48-63. The layout is tessellated: seed 0-15 has chessboard tiles of size 1x1, seed 16-31 has tiles of size 2x2, seed 32-47 has 4x4, seed 48-63 has 8x8. See the attached .mp files: fish types are marked as wheat, whale as jungle.

NSum = (X + Y)/2 ; NDiff = (X - Y)/2

A note: if you turn the map by 45 degrees anticlockwise then the x coordinate corresponds to NSum and y coordinate corresponds to NDiff.
So you see that the fish/whale type of specials depends on NSum, NDiff coordinates by a simple way.

[SlowThinker]

I forgot to attach the file with patterns...

[SlowThinker]

To be complete: the rule mathematically:

nomenclature: size of a chessboard tile:
ChessboardConstant=CC=2^(Seed div 16)

the rule:
The special is the whale type even as (NSum mod (2*CC)) div CC = (NDiff mod (2*CC)) div CC

[SlowThinker]

A program (originally coded in Delphi) will be posted in a new thread momentarily ... (Civ2 Beakers Counter )

ST

[SlowThinker]

Civ2Beakers/Civ2Admin version 0.4 can do it:
http://apolyton.net/forums/showthrea...89#post2351489