Civ1 Advanced hacking: special resource and hut patterns

[darkpanda]

I was in a bit of a rush when I posted a simple patch to make all/none map squares special. At that time, I was looking at the "Check Special Resource" for completely different reasons (reviewing the map drawing code).

But right after posting it, I started to wonder: in what more sophisticated/interesting ways could this routine be altered?

To investigate possibilities, I started to explore 3 different approaches:

1. Adjust the original formula to change the "shape" of the well known resource/hut pattern
2. Completely rewrite the routine to produce more random, unpredictable patterns
3. Completely rewrite the routine to make special resources and/or huts "customizable" by having them stored in/loaded from the MAP rather than computed in real time with a formula

Hereunder, I provide more details about each approach (only 1. completed thus far).

1. Adjust existing patterns

The 2 formulae to determine whether or not a map square contains a special resource or a hut are re-stated hereunder:

[b]SPECIAL RESOURCE[/b]
  Y > 1   [I]AND[/I]
  Y < 48  [I]AND[/I]
  (X MOD 4)*4 + (Y MOD 4) == ((X/4)*13 + (y/4)*11 + TMW) MOD 16

[b]HUT[/b]
  Y > 1   [I]AND[/I]
  Y < 48  [I]AND[/I]
  square at (X,Y) is not a city [I]AND[/I]
  square at (X,Y) is not visible by barbarians [I]AND[/I]
  (X MOD 4)*4 + (Y MOD 4) == ((X/4)*13 + (y/4)*11 + TMW + 8) MOD 32

The first few elements of those boolean formulae are simply checking for other external conditions (square not in poles, hut not already visited, etc).

The last operand of both formulae are the ones that control those very peculiar patterns that CIV players quickly get familiar with:

Special resource pattern

Huts pattern

1.1. In-depth pattern analysis

Before altering those formulae, let's try to make some sense out of them (if you're not interested, you can skip this part and go to 1.2. directly).

First, let's look at the left operand, which is identical for both formulae:

[B](X MOD 4)*4 + (Y MOD 4)[/B]

X and Y are the coordinates of the map square. If we exclude the poles, they range, respectively, from 0 to 79 (included) and from 2 to 47 (included). The square with coordinates (0,0) is the top-left corner of the map, and from this square, the X and Y coordinates increase 1 by 1 horizontally towards the right (X) and vertically towards the bottom (Y). It can be represented as follows:

The meaning of N MOD 4 is the value of integer N modulo 4, or in other words, the remainder of the integer division of N by 4. One of the properties of the modulo operation is that it produces cyclical values when given a linear input range of integers.

Typically:

if the value of [B]N[/B] is  0  1  2  3 [I] 4  5  6  7[/I]  8  9 10 11 [I]12 13 14 15[/I] 16 17 ...
     then [B]N MOD 4[/B] is  0  1  2  3  [I]0  1  2  3 [/I] 0  1  2  3  [I]0  1  2  3[/I]  0  1 ...

With this property in mind, we can get the intuition that if X MOD 4 and Y MOD 4 are both cyclical, then (X MOD 4)*4 + (Y MOD 4) is also going to be cyclical, all the more that (X MOD 4) is multiplied by 4, which happens to be modulo divisor.
When computing (X MOD 4)*4 + (Y MOD 4) for all map squares (X,Y), we immediately see a cyclical pattern appear, as highlighted in blue in the grid below:

The cyclic pattern is a 4x4 area that contains values from 0 to 15, ordered from top to bottom and left to right.

In other words, the left operand divides the map in a set of identical 4x4-square areas, each area containing all values from 0 to 15.

Now, let's look at the right operands:

Special resources: [color=green][b]((X/4)*13 + (Y/4)*11 + TMW)     MOD 16[/b] [/color]
             Huts: [color=red][b]((X/4)*13 + (Y/4)*11 + TMW + 8) MOD 32[/b] [/color]

Here again, there is a strong similarity between both formulae, the only differences being the final MOD divisor (16 vs 32) and the addition of 8 for the Hut formula.

Let's look at the identical part first: (X/4)*13 + (Y/4)*11 + TMW

Here, N/4 yields the quotient of the integer division of N by 4. When applied to a continuous range of values like 0, 1, 2, 3, 4, 5, 6, ..., this operation is guaranteed to return the same result for 4 consecutive values:

if the value of [B]N[/B] is  0  1  2  3 [I] 4  5  6  7[/I]  8  9 10 11 [I]12 13 14 15[/I] 16 17 ...
         then [B]N/4[/B] is  0  0  0  0  [I]1  1  1  1 [/I] 2  2  2  2  [I]3  3  3  3[/I]  4  4 ...

Again, when applied to both X and Y, we can foresee that this formula will work at a the level of 4x4-square areas:

We also see in the picture above that X/4 and Y/4 are symmetrical, and this is always an issue when trying to design a random pattern.

This is why CIV developers multiply X/4 by 13 and Y/4 by 11. The reason for choosing 11 and 13 as multipliers is that they are both prime numbers whose smallest common mulitplicant is, thus, their own product 11 x 13. Another reason is that they result in a rather nice and even pattern...

This beats symmetry because the smallest X and Y necessary for X/4*13 being equal to, and thus symmetrically exchangeable with Y/4*11, are X = 11*4 = 44 and Y = 13*4 = 52, which never happens since Y is always smaller than 52.

So this guarantees that X/4*13 + Y/4*11 always yields different results for all values of X and Y within the map.

In this part of the formula, the addition of the Terrain Master Word (TMW) brings variation in the pattern from game to game.

Looking only at the special resource formula, the final step is the MOD 16 operation, which effectively gets the value of X/4*13 + Y/4*11 + TMW within the range [0..15]:

Since we are only dealing with values between 0 and 15 though, we cannot avoid having a pattern repetition in those right operand values, as highlighted below, where all colored areas are identical:

Now, since the resulting value of both operands are within the range [0..15], there is a guaranteed single match between both operands for every 4x4 area. In other words, there is 1 and only 1 square for each 4x4-square area on the map that will make the special resource formula true:

Matching with the first operand, we can see how the right operand pattern repetition results in the repetition of the special resource pattern as well:

Now let's look a the right operand of the hut pattern formula: ((X/4)*13 + (Y/4)*11 + TMW + 8) MOD 32

Compared to the special resource formula, the addition of 8 plays only a little role, which is to shift the pattern compared to the special resrouce pattern, otherwise, without this "+8", every hut square would also be a special resource square.

The real difference lies in the 32 MOD divisor (0x1F) instead of 16 (0xF) for special resource: the MOD 32 operation will cast the right operand values for the 4x4 areas ( (X/4)*13 + (Y/4)*11 + TMW + 8 ) into the [0..31] range, instead of [0..15] for the special resource pattern.

Since the left operand values' range is only [0..15], this means that 4x4 areas for which the right operand value ranges from 16 to 31 will not contain any square for which the hut formula is true, i.e. those 4x4 areas will not contain any hut square. Those areas have a gray background in the picture below:

On average, this cuts by half the potential number of huts compared to the total number of special resources (disregarding ocean squares that cannot contain huts either).
Same as for special resources, the right operand's value range being [0..31], there is a repeating pattern, which is highlighted below (areas with a red overlay cannot contain huts):

As for special resources, when matching with the first operand, we can see how the right operand pattern repetition also results in the repetition of the huts pattern:

1.2. Adjusting the pattern by hacking the formula

Obviously, adjusting numerical parameters in the formula will lead to different results when calculating the operands, and thus different patterns.

Understanding the formula as explained in 1.1. definitly helps in understanding and deciding how to change the parameters.

On the left side of the formulas, both the MOD 4 operations are actually coded as n & 0x3, where "&" is the binary AND operation. So it can only be changed powers of 2 (2, 4, 8, 16, 32, 64, etc.). Otherwise the '&' operation will no longer correspond to a MOD operation, but rather to something less understandable.
The multiplication by 4, as well, is actually a bitwise left-shift by 2 bits, so simple modification only allows for changing the number of bits shifted, i.e. powers of 2 as well.

On the right side, however, we are more lucky: the divisons by 4 are still done by bitwise right-shift by 2 bits, so still limited to powers of 2.
However, the multplications by 13 and 11 are done directly, so those 2 multipliers are the easiest to change. Also, there is no need to set values greater than 15, because the MOD 16 will cast them back to the [0..15] range anyway, i.e. 18 is the same as 2, for example.

The offsets of those 2 multipliers are given below:

offsets for:  13 (0xD) - 11 (0xB)
   EN 47401:  0x1C885  - 0x1C893

Although the patterns obtained are still repetitive in some way, some of them seem less regular that the standard one, and could be more interesting to play or at least give new experiences in CIV games.

Hereunder I attached a HTML page that simulates the pattern for you when you change the different parameters (ZIPped because of civfanatics forum limitations):

View attachment pattern_sim.zip

Also, hereunder is a large batch of patterns that I found interesting by changing the multipliers:

||||
x multiplier|0|4|5|7
y multiplier|0|13|13|2
pattern|

|

|

|

||||
x multiplier|7|7|8|9
y multiplier|13|14|14|10
pattern|

|

|

|

||||
x multiplier|11|11|12|14
y multiplier|2|3|15|11
pattern|

|

|

|

||||
x multiplier|2|2|5|6
y multiplier|3|5|14|7
pattern|

|

|

|

2. Rewrite formula to be more random

In progress...

3. Rewrite formula to store special squares in MAP

In progress...

 

[hannurabi]

Continued form other thread:

Spoiler :

Quote:
Originally Posted by hannurabi View Post
I don't mean to hijack this thread but this got my interest:



At first it seemed quite hard to get random enough results for algorithm, since the bonus tile is determined by formula and not by variable. (Am I correct?) But I just tried different things with the help of my civclone and came up with something like this:

Spoiler:
Code:
unsigned int seed = 'constant random seed';

for (int x = 0; x < Width; x++)
{
for (int y = 0; y < Height; y++)
{
unsigned int randstate = seed;
int i = 0;
while (i < x * y)
{
randstate = randstate * 1103515245 + 12345;

if (randstate % 3 == 0)
i = i - 1;
else
i = i + 1;
}

if (randstate % 8 == 0)
bonus(x,y) = true;
}
}


It's gives results that seem to be quite random. Also, often bonus resources are plenty and sometimes they are just few. See attached pics. I'm not mathematician so I have no clue why the algorithm gives those results. I think this also needs some further testing and adjustment too.

Next challenge is to overwrite the Civdos formula with assembly version of this formula, don't know how hard or easy or possible that might actually be.

It's worth saying that it's possible that I have made some logic failure and it's not possible to add this into civdos

Your formula looks interesting, but there's a catch: in CivDOS, the special resource pattern is implemented as a function, with the following signature:
boolean isSpecialResource(int x, int y);

This function contains the famous formula, which is recomputed, only for x and y, every time the function is called.

In your example, you described a process of spreading around the special resources... But after this process is done, how can you write it as a function with the same signature as above?

The only alternatives I see are:
Run the full algorithm on every call, and stop when the input x,y is reached -> too long
Store the special resource pattern after initial processing, then lookup stored values on every call -> very different from existing implementation, and so quite heavy in terms of hacking

I have thought, before, of the latter approach, and coming back to it now, it seems more and more achievable (there's room in the MAP to store special resources and huts).

As a matter of fact, I suggest we redirect this discussion to this other thread I started some time ago, for this exact purpose: Civ1 Advanced hacking: special resource and hut patterns

Maybe the loops confused you but the applied to CivDOS the formula is something like this:

boolean isSpecialResource(int x, int y)
{
        unsigned int randstate = seed;
	int i = 0;
	while (i < x * y)
	{
               randstate = randstate * 1103515245 + 12345;

		if (randstate % 3 == 0)
			i = i - 1;
		else
			i = i + 1;
	}

	if (randstate % 8 == 0)
		return true;

       return false;
}

But I can see that the While loop can really take a while. I think you are right after all. Formula requires more adjusting.

 

[darkpanda]

Maybe the loops confused you but the applied to CivDOS the formula is something like this:

boolean isSpecialResource(int x, int y)
{
        unsigned int randstate = seed;
int i = 0;
while (i < x * y)
{
               randstate = randstate * 1103515245 + 12345;

if (randstate % 3 == 0)
i = i - 1;
else
i = i + 1;
}

if (randstate % 8 == 0)
return true;

       return false;
}

But I can see that the While loop can really take a while. I think you are right after all. Formula requires more adjusting.

You're absolutely right, I misread your code! But indeed, the internal loop has no guarantee to terminate, which could make Civ hang forever...

In the meantime, I resumed my work on inserting a new routine in CIV, based on your formula, I'll get back when it's working.

 

[darkpanda]

<Duplicate post terminated>

 

[darkpanda]

Here is a sample view on how I manually created assembly, for the algorithm your proposed, fit-for-purpose of hacking CIV.EXE, relying on a spreadsheet tool with minimal macros for jump offsets:



I then dump the bytes contents into a raw "bin" file (using a small Java routine), and I opened it with IDA to make sure it's doing what I expect...

Here are the bytes in IDA:



And the graph view:




Now all that remains is to put it in CIV and test it

 

[darkpanda]

The routine posted above has a bug which result in "divide error" fatal error... But even when fixed, it always returns false. Some more research is needed.

 

[hannurabi]

The routine posted above has a bug which result in "divide error" fatal error... But even when fixed, it always returns false. Some more research is needed.

I don't know about divide error. You fixed it?

About return value, maybe try different numbers as constants and test it to find best combination? I see that you used number 0x4E69 (20073) instead of the big number 1103515245, which is understandable because the number is so huge. Am I correct? Again, I'm not that fluent in math, that I can't tell if it matters really.

Have you tried different number for "modulo 8" part, for example 4 or even 2, just to see if it gives any results?

Then there's the seed number, which really defines the algorithm output. Maybe some seeds just gives bad results.

 

[darkpanda]

Yes the divide error is fixed: using "idiv cx" may result in a divide error if the result of the division of dx:ax by cx does not fit in ax (if it's bigger than 0xFFFF, basically). Easy to fix with a "mov dx, 0" prior to the idiv.

I did take smaller values to fit in 16-bit, indeed. Actually, both 0x4E69 and 0x3039 are multiples of 3, so (N*0x4E69 + 0x3039)%3 is always 0, whatever the value of N. So I did try with other values, specifically prime numbers 0x4E67 and 0x3037, but then some weird cyclic pattern appears... And as you predicted, some seeds generate a lot if special resources, while others so not generate any...

I didn't try different modulo values.

I am starting to think the original formula is actually well crafted and balanced!

Anyway, let's investigate further...

 

[hannurabi]

Yeah, there's nothing wrong with the original formula, but I always liked to see more random patterns in special resources. Something like possibility to have 3 oasis next to each other.

The idea behind my algorithm was to mimic pseudo random number generator, to some extend at least. The rng 'cycles' has to be determined by values of x and y somehow.

I don't really understand why the algorithm seems to work OK on my civclone, but not in CivDOS, maybe I have made some error implementing it...

 

[darkpanda]

Yeah, there's nothing wrong with the original formula, but I always liked to see more random patterns in special resources. Something like possibility to have 3 oasis next to each other.

The idea behind my algorithm was to mimic pseudo random number generator, to some extend at least. The rng 'cycles' has to be determined by values of x and y somehow.

I don't really understand why the algorithm seems to work OK on my civclone, but not in CivDOS, maybe I have made some error implementing it...

Because i starts with value 0, and (N*0x4E69 + 0x3039) is always 0, then the first operation on i is always i = i - 1, so the first value of i is always -1. The problem is that in assembly, -1 is written 0xFFFF, and cmp says that 0xFFFF is bigger than any other value (including x*y). So the loops always end at first iteration, and the value of randstate is always the same...

Long story short: I change the "(rs%3==0) ? i-- : i++;" into "i = i + 1 + rs%3". And I also changed the constant integer values. to fit in 16-bit, and make them prime.

I tested your algorihtm quickly, using original values, in Java, and indeed it seems to do something acceptable, although different seeds will indeed yield different patterns, in particular some seeds make very scarce resources (jumping every other row).

I'm keeping looking...

 

[darkpanda]

Inspired by your algorithm, hannurabi, I designed a similar algorithm, but I changed some of its logic:

			boolean hasSpecialResource(int x, int y) {
					int i = 0;
					int rs = seed;  
					while(i<x+80*y) {
						rs = rs*[B][COLOR="Red"]0x4E67[/COLOR][/B] + [B][COLOR="Red"]12343[/COLOR][/B];
						int ax = rs&0xFFFF;
						int dx = (rs>>16)&0xFFFF;
						rs = (ax+dx)&0xFFFF;
						i++;
					}

					if([B]rs%((i%[COLOR="Red"]7[/COLOR])+[COLOR="Red"]7[/COLOR][/B])==0)
						return true;
					else
						return false;
			}

I highlighted in red that parameters that can be tweaked. Most notably, the two "7"'s at the end will impact respectively repetition of the pattern, and scarcity of resources: the higher it is, the fewer resources there are.

I proof-tested it with a small Java routine, and it gives the following result, compared with CIV's original formula:

Now all remains is to try and implement it in assembly...

 

[hannurabi]

Like stars in the night sky

It's sure is more random than the original. Can't wait to see that in the CivDOS.

 

[darkpanda]

So, for some reason, it doesn't work as expected in CivDOS, and creates plenty of vertical lines full of special resources, all-the while creating other sparse resources here and there:



This may be very hard to debug, I need to get into the screen drawing routine at the precise moment when a special resource cell is drawn, and check its logic...

By the way, I had the exact same problem with my first, aborted, attempt to re-write he "isSpecialResource()" routine using random() calls. So there may be some hidden mechanism that bypasses this logic altogether.

 

[darkpanda]

So there may be some hidden mechanism that bypasses this logic altogether.

Scratch that, I found the issue, a simple mistake in reading the subroutine arguments: it takes 3 arguments, but only uses 2 of them, so I am using terrain type as Y and Y as X...

Will be fixed ASAP

 

[darkpanda]

So finally, here it is:

This is the resource pattern obtained by using the original version of the algorithm I designed several months ago, using various seeds:

Here is the logic in Java code:

	boolean isSpecialResource(int x, int y) {
		CivRandom cr = new CivRandom( seed0, 0xBABE );
		int r = cr.next( x*0xBABE + y*seed0 );
		return ( r^0xCAFE ) % 5 == 0;
	}

where CivRandom is a bit-perfect Java port of the random routine used in CivDOS (I wrote and debugged it to the extreme when designing the Civ1 exploit: design flaw in randomness).

Here is the same logic written in assembly:

	 : Routine initialization
	                proc far
                     	var_4           = word ptr -4 ; temporary storage for Random seed 1
                     	var_2           = word ptr -2 ; temporary storage for Random seed 2
                     	arg_2           = word ptr  2 ; map square X
                     	arg_4           = word ptr  4 ; map square Y
[b]55 [/b][color=blue]                              push    bp[/color]
[b]8B EC [/b][color=blue]                           mov     bp, sp[/color]
[b]83 EC 04 [/b][color=blue]                        sub     sp, 4[/color]
	
	 : Making backup copies of random seeds
[b]A1 DA 5B [/b][color=blue]                        mov     ax, ds:5BDAh[/color]
[b]89 46 FE [/b][color=blue]                        mov     [bp+var_2], ax[/color]
[b]A1 DC 5B [/b][color=blue]                        mov     ax, ds:5BDCh[/color]
[b]89 46 FC [/b][color=blue]                        mov     [bp+var_4], ax[/color]
	
	 : Manually re-seeding the random generator using the TerrainMasterWord (ds:6E00h) from the SVE as seed1
	 : and the static value 0xBABE as seed2 
[b]A1 00 6E [/b][color=blue]                        mov     ax, ds:6E00h[/color]
[b]A3 DA 5B [/b][color=blue]                        mov     ds:5BDAh, ax[/color]
[b]C7 06 DC 5B BE BA [/b][color=blue]	         mov     word ptr ds:5BDCh, 0BABEh[/color]
	
	 : Computing base value of random call argument: base = X * seed2 + Y * seed1
[b]8B 46 08 [/b][color=blue]                        mov     ax, [bp+arg_2][/color]
[b]F7 2E DC 5B [/b][color=blue]                     imul    word ptr ds:5BDCh[/color]
[b]8B C8 [/b][color=blue]                           mov     cx, ax[/color]
[b]8B 46 0A [/b][color=blue]                        mov     ax, [bp+arg_4][/color]
[b]F7 2E DA 5B [/b][color=blue]                     imul    word ptr ds:5BDAh[/color]
[b]03 C1 [/b][color=blue]                           add     ax, cx[/color]
	
	 : Calling Random routine on 'base'
[b]50 [/b][color=blue]                              push    ax[/color]
[b]9A 5B 00 DE 1D [/b][color=blue]	                 call    far ptr 1DDEh:5Bh[/color]
[b]83 C4 02 [/b][color=blue]                        add     sp, 2[/color]
	
	 : Additional computation on random routine result: ( random(base) XOR 0xCAFE ) / 5
[b]35 FE CA [/b][color=blue]                        xor     ax, 0CAFEh[/color]
[b]BA 00 00 [/b][color=blue]                        mov     dx, 0[/color]
[b]B9 05 00 [/b][color=blue]                        mov     cx, 5[/color]
[b]F7 F9 [/b][color=blue]                           idiv    cx[/color]
	
	 : Rollback seeds to their original values
[b]8B 46 FE [/b][color=blue]                        mov     ax, [bp+var_2][/color]
[b]A3 DA 5B [/b][color=blue]                        mov     ds:5BDAh, ax[/color]
[b]8B 46 FC [/b][color=blue]                        mov     ax, [bp+var_4][/color]
[b]A3 DC 5B [/b][color=blue]                        mov     ds:5BDCh, ax[/color]
	
	 : Return "false" by default
[b]2B C0 [/b][color=blue]                           sub     ax, ax[/color]
	
	 : Checks if DX == 0; if so, it means that ( random(base) XOR 0xCAFE ) MODULO 5 == 0, in which case 
	 : the map square *has* a special resource
[b]0B D2 [/b][color=blue]                           or      dx, dx[/color]
	
	 : If DX is NOT equal to 0, directly jump to routine end
[b]75 03 [/b][color=blue]                           jnz     short loc_56[/color]
	
	 : ELSE return TRUE: the map square DOES contains a special resource
[b]B8 01 00 [/b][color=blue]                        mov     ax, 1[/color]
	
	 : Routine termination
	loc_56:                                 ; CODE XREF: sub_0+51
[b]8B E5 [/b][color=blue]                           mov     sp, bp[/color]
[b]5D [/b][color=blue]                              pop     bp[/color]
[b]CB [/b][color=blue]                              retf[/color]
	sub_0           endp

Changing the modulo operand to values higher than 5 will result in scarcer resources.

I also tried with the algorithm detailed earlier, but for some reason, it produces a very repetitive pattern, that is not present in my original simulations... Not sure I am willing to further debug why it is repetitive, since the proof of concept to completely replace the special resource routine is now achieved

 

[hannurabi]

That's really cool work!

Are those hex bytes all you have to insert/change in the exe to get it to work? I tried to hex edit the exe to apply the function but game crashed after intro. I double checked the bytes but they seemed to be same as above. Am I doing something wrong? Civ version 01.

Or could you provide a patch for this?

 

[darkpanda]

Yes, there's more to change, because the additional "random()" call requires an additional entry in the relocation table... The XML patch is already done, and I am attaching it here: View attachment patch101_sepcial_res.zip

You need to unzip it and put it in your "patches" sub-dir inside JCivED.

It will also be released together with JCivED 0.0.14a, soon.