[35494:35753] [0x8AA6:0x8BA9] 260 0x104 unknown (#25)
During my journey inside the map generation code, I figured out this code was also setting up the values of the data block
unknown25, which is apparently some kind of
high-level path-finding data, i.e. data meant to help the Civ AI moving units around the map in an optimal way.
The funny thing is that the Civ code setting up this data seems to
wrong - although it may not matter in the end...
Let me try to explain:
1. The first thing that can be remarked, is that
this data is almost always the same, whatever gamesave you take form whichever version of Civ... Actually, I noticed this
after having gone through everything explained below, but anyone can see it for themselves by opening their SVE save in
JCivED or any hex editor.
In my case, this data block is nearly always as below (the rare differences happen on 1 or 2 bytes, usually at the end of the block):
Code:
00 16 13 11 01 10 01 02 00 00 0A 02 00
30 61 00 00 02 10 21 00 12 29 20 8A 00
00 00 00 24 00 0A 18 25 08 02 A4 08 80
14 03 00 46 20 0A 80 C0 20 80 48 08 80
68 00 38 45 20 00 80 02 00 04 00 8E 80
00 90 01 C0 00 00 22 10 01 40 34 5B 85
00 00 00 00 00 22 00 10 01 00 68 00 C6
00 10 01 00 20 04 10 01 00 00 00 B4 43
00 00 00 04 00 40 00 00 00 14 03 64 00
00 00 00 40 00 00 00 10 01 64 00 40 00
00 04 00 10 01 00 00 00 00 40 00 00 04
00 44 00 02 02 00 06 10 11 01 00 00 40
00 40 20 20 00 3C 4F 10 01 10 01 00 00
00 00 00 00 00 76 DB 95 13 11 01 00 00
10 01 00 06 38 65 04 E4 00 00 00 00 04
08 00 30 41 00 C2 44 40 0A 00 00 00 40
00 80 00 00 24 00 40 22 00 94 03 0C 00
00 04 00 02 44 10 21 00 00 62 04 58 85
00 40 24 00 42 12 01 00 28 00 40 08 C0
00 00 44 20 20 00 16 0B 00 8C 00 00 84
Note that I arranged the bytes in a 13x20 table format (=260 bytes) , you will understand by reading further below.
2. Second thing: how Civ generates this data was very interesting to walk through.
Here is basically how it goes:
- Civ divides the map area into 4x4 tiles: 80/4 = 20 and 50/4 ~= 13, which makes a set of 20*13 = 260 tiles; this explains the 20x13 data size, and we can then expect 1 byte of data per 4x4 map tile
- The iteration loop is by columns: first tile to be processed is in the top-left corner, then the next tile is the one below, then below, etc... until the column is fully processed; then the next column (right of the top-left tile) is processed, etc.
- For each tile:
- Civ checks if any of the 4 central squares is a land square:
- If not, the tile is skipped and the next tile is processed
- Else Civ retrieves the corresponding Continent ID
- Next, Civ iterates through the 4 neighbour tiles at the top (North), top-right (North-East), right (East) and bottom-right (South-East) as follows:
- If one of the tile's 4 central squares is also land, and has the same Continent ID as retrieved above, and the walking distance(*) from the processed tile to the neighbour tile is less than 20:
- Update the unknown25's byte corresponding to the processed tile: set the bit 0x1 (for N), 0x2 (for NE), 0x4 (for E) or 0x8 (for SE) to value 1
- Update the unknown25's byte corresponding to the neighbour tile: set the bit 0x10 (for S), 0x20 (for SW), 0x40 (for W) or 0x80 (for NW) to value 1; note: this is a smart trick to cross-link tiles, so only 4 neighbours need be processed for each tile...
- Civ goes on to process the next tile
About the
walking distance mentioned above: I didn't decipher exactly how it's done, but at a glance, Civ seems to instantiate a militia unit (alternatively a trireme for
sailing distance) and lets it
GoTo from the original square to the destination square, counting up steps on the way... I may be wrong, but at the moment it does not really matter.
So the bottom line is that this generated data is
a byte flag for each tile indicating which of the 8 neighbour tiles are within close walking distance. It is like a
high-level roadmap that AI land units (or player's GoTo-units for that matter)
could use as a guideline to find directions when moving around.
3. Third, what does it look like?
Intuition made me think that such a roadmap should follow the shape of continents, somehow like a
skeleton of the continents. To confirm this, I wanted to compare the generated unknown25 data with the actual map data, so I wrote a quick routine that displays the continents in the background, then overlays square-level and tile-level grids (in dark- and light-green), and then draws the unknown25 as a graph linking the tiles (pink for N,NE,E,SE and yellow for S,SW,W,NW).
Hereunder is the result for different 2 gamesaves:
As anyone can see, the path-graphs do not make any sense compared to the actual continents, and furthermore (this is how I discovered it) they are almost identical! That is to say, the
unkown25 data is actually independent form the map geography...
4. But how can that be wrong?
Scratching my head and double-checking whether I was misguided in my interpretation of the code, I followed the execution of Civ step-by-step, looking at the memory in parallel (thanks a lot to
DOSBox in debug mode for that!).
Doing this, I could confirmed that I understood it right, but more importantly, I understood
what Civ was doing wrong, and I believe it is a programmer's mistake, in the way that the map data is accessed in memory.
To put it simply:
- the map data (which is eventually stored in a gamesave's .MAP file) is stored in the "graphics" memory, i.e. a memory region which is managed by the graphics code contained in MGRAPHIC.EXE, EGRPAHIC.EXE or TGRAPHIC.EXE
- this region of memory actually contains multiple images, and the graphics code maintains an array of "image pointers" to convert an image ID (0, 1, 2 ...) into an image pointer (424F:0000, 51F0:0000, ...)
- whenever something needs to be read from or written to the map data, Civ calls specific routines from the graphics code, with image parameters (X, Y, color value, etc...) and more importantly with the image ID from which the data must be read from/written to.
- for most of the map generation code, Civ uses image ID = 1 to store the map data (stored at 424F:0000 in Civ EN 474.01)
- however, in our specific example of the unknown25 data, Civ uses image ID = 2 (stored at 51F0:0000)
I was curious whether Image ID = 2 was containing something useful for the generation of map data, so I made a memory dump and converted it to a picture, which is shown below in false colors:
As you will surely have discovered by yourself, this is actually the first image of the
new game introduction sequence,
BIRTH1.PIC, which happens to be the current screen content at the time when the map generation code is being executed:
5. Can it be fixed? Should it be fixed?
Having discovered that, I tried - unsuccessfully so far - to patch CIV.EXE so that it goes and get the data from the actual map image.
I am actually very interested in discovering what Civ would do if accessing the data properly...
But then I am also wondering: if this bug has always been here, in all versions of Civ (to be confirmed) is this data actually used at all by the Civ's AI code? In oterh words, even if it is corrected, is it going to change anything in the game?
I guess answers to those questions will come in the next episode...
At least I think that's one more down for the deciphering of SVE file format!
Cheers