Procedurally generated maps - algorithm?

[Maurice76]

Like many people who ever played X-Com, it's only natural to replay it from time to time. That itch is starting to act up again, so as I am turning back to TFTD (first game I played in the X-Com series, way back when), I can't help but wonder how the game builds up the various maps. It's a question that surfaced while wondering how the game determines which MAP sections to use when generating its maps. Considering there are different amount of files for each map type, it's especially interesting to know how the game finds its way in creating the map. Has the algorithm ever been decoded? How does the game determine which terrain blocks (in the MAPS directory) belong to which map type? Is that based on the name alone or is there a table somewhere (hardcoded perhaps)? What about the appearance ratio for each of those terrain blocks within a map?

 

The non-trivial portion stems from the placement of possible USO's and the possible X-Com craft. Not all missions have X-Com craft and some missions that have X-Com craft may not feature a USO. Furthermore, USO's have different sizes and therefore different placement restrictions. Another complexity in the mix is the Sunken Plane map, which has restrictions on which of its composing blocks can go where. The UFOPedia lists that particular map as always being 50x50x4, regardless of USO size. Now I don't recall from previous playthroughs if that map can also hold the larger USO sizes (Dreadnought, Fleet Supply Cruiser).

 

The most logical approach is that the game would first place the blocks where the USO is placed upon (depending on the USO size), then the block which will house the X-Com craft (since that one is always 1x2), followed by filling out the remaining blocks randomly with available ones. But what about further restrictions? Some of the map blocks are 20x20, does the game limit the amount of those that can appear in any given map? As I recall, there is no restriction for distance between the X-Com craft and the USO.

 

Hopefully someone can shed some light on these questions .

[NKF]

TFTD can have map sizes up to 60x60x4. Ship missions are a 30x70x4 grid. So there's a bit of room.

 

The game compiles its tile set based on the mission, terrain and the types of ships present. The map tilesets are an enumeration of prefixes like coral, seabed, etc. The file names are formed by taking the prefix and adding a number and file extension to the end. A specific number of files are loaded for each map set.

 

Map generation starts off by fitting the X-Com craft and alien ship into the map first if they are present. These areas are effectively reserved.

 

It then has a series of unique routines for each of the different scenarios/terrain types. Most of them are essentially the same. They make about 20 attempts to install random 20x20 block sections in the map. Then the rest of the gaps are filled with random smaller 10x10 blocks.

 

More interesting maps have their own set of instructions to form the map. The port for example first installs its coast and ensures that the large 20x20 rail station is installed along the top edge of the map. After that it goes into the usual process of 20 attempts to fit 20x20 blocks in and then the 10x10 block fillers.

 

The plane on the other hand takes the time to try and fit its two wings (each one a 20x20 block) into the map. It then make several attempts to fit various fuselage sections (tail, mid sections, nose) into the map before filling it in with small 10x10 segments.

 

The cruise ships have fixed maps, so there's not a lot of work here apart from deciding which map to load.

 

I'm guessing here, but the terror site in UFO must have instructions to install the roads before fitting the houses in, since there's always at least one road that goes from one end of the map to the other.

 

- NKF

[Maurice76]

Thanks for the information, NKF. I've been diving into the GeoScope.exe file, as that one seems to be responsible for creating the GeoData.dat file in the battlescape savegame directories. I can find references to the X-Com and Alien crafts in there, each preceded by the dimensions (in map block size) and each followed by the (up to five) MCD files that compose the craft in question. I assume that that particular area is where the .exe also holds the logic on how to build the map.

 

Specifically, I am looking for the areas that hold the following info:

 

- Information on how many map blocks exist for a given map type. Since the GeoScope.exe doesn't contain the name, it has to use enumeration; I did find the names in the Tactical.exe file, but it probably simply maps the relevant value in the GeoData.dat file to a name it can resolve, so it can actually address the specific files it needs to compose the map. Therefore, the GeoScope.exe file has to find out in another way that simply directory listing which enumeration is available to it for any given map type. It cannot, for instance, address map block 00 for the Sunken Galleon, or block 12 and higher for the surface of Artefact sites, because those blocks don't exist.

 

- Information on the specifics of each map block within a type. Since it uses enumeration, it must also hold the information on what map block has which contraints. Like you said, the Island and Port maps have restrictions with respect to the coast line (Island only allows for 04, 05 and 07 along the south side of the map, while Port 02 through 09 are the only blocks allowed along the eastern edge). Other restrictions also apply: for instance, on the first level of Artefact sites, it's mandatory to have exactly 1 instance of 09, while on the second level it's mandatory to have exactly 2 instances of 04 and exactly 1 of 15. Something similar applies to Alien Colony level 2 (2 instances of 00, 1 instance of 15). Or is this all hard-coded in the subroutines that compile a map? And besides mandatory blocks, it also has to have information on the maximum amount of times any given block is allowed to occur (otherwise you'd run the risk of getting a map that's composed of only 1 specific map block repeated to fill the map, aside from the possible craft present).

 

While trying to wrap my head around the algorithm used, I could think of different solutions to tackle this challenge, but I have no idea which approach the developers used. Based on your post, though, I figure that there has been some reverse engineering by people, who have found the more intricate details of their approach?

 

Edit: With respect to the roads in UFO, I think you are right. It's probably similar to the coast line in the Island and Port maps, where the game determines if there's a WE road, a NS road, or both, and then places those tiles first - maybe even before the X-Com craft? They're just not as restricted to a border like in the Island and Port maps.

[Hobbes]

This is the mapScript used by OpenXCom to generate the Urban terrain (it was reverse engineered from the original):

 

- type: URBAN

commands:

- type: addCraft

- type: addLine

label: 1

direction: vertical

executionChances: 50

rects:

- [1, 1, 4, 1]

- type: addLine

label: 2

conditionals: -1

executionChances: 50

direction: horizontal

rects:

- [1, 1, 1, 3]

- type: addLine

conditionals: [-1, -2]

direction: both

rects:

- [1, 1, 3, 3]

- type: addBlock

size: 2

executions: 4

- type: fillArea

# URBAN set is lacking blocks 10-13, so the numbers don't correlate properly here,

# because these are references to the block numbers within the sets, not the file names.

blocks: [3, 4, 10, 11, 12, 13, 14]

freqs: [3, 3, 2, 2, 2, 2, 2]

 

And this is the equivalent for Port terrain in TFTD:

 

 

- type: PORT_TERROR

commands:

- type: addBlock

rects:

- [0,0,4,2]

blocks: 20

- type: addBlock

rects:

- [4,0,1,5]

executions: 5

blocks: [2, 3, 4, 5, 6, 7, 8, 9]

maxUses: [1, 1, 1, 1, 1, 1, 1, 1]

- type: addCraft

- type: addBlock

size: 2

executions: 2

- type: fillArea

 

If you need an explanation of the several commands used above, check this page https://ufopaedia.org/index.php?title=Ruleset_Reference_Nightly_(OpenXcom)#Terrains

[Maurice76]

Hey, Hobbes, thanks for your info. I can say especially this part has been enlightening:

 

# URBAN set is lacking blocks 10-13, so the numbers don't correlate properly here,

# because these are references to the block numbers within the sets, not the file names.

 

Up to now I assumed that the GeoScape.exe held explicit references to the map file numbers, but what you're saying implies that it's implicit. In other words, if I get it right, the actual number of the file after the map type (e.g. URBAN01.MAP) only has relevance for the followup order; internally, it simply uses an enumeration that's mapped onto this followup order. If that's right, then for instance, you could rename URBAN14-URBAN18 to URBAN10-URBAN13 and it would work just like it should, as the followup order of the blocks didn't change in the directory listing. Or am I completely on the wrong track here?

 

Edit Just for the sake of it, I renumbered a few of the files in the TFTD Maps directory (specifically, I turned all LINERB0X.MAP and LINERT0X.MAP files into respectively LINERB1X.MAP and LINERT1X.MAP) so the followup order wasn't changed - but the game still flunked out when I tried to enter a ship Terror mission. So apparently, the Tactical.exe does at least make the explicit relation to filename. If implicit enumeration is used by the GeoScape.exe, the Tactical.exe doesn't. I'm guessing the implicit referral works like that in OpenXCOM?

 

Btw, in the two script examples you mentioned, I assume that "addLine" simply uses the blocks with the road tiles in it, distributing those randomly along the line and the "addBlock" refers to a set of all blocks with size 2? Just wondering, since both the coast side of the Port script and the fillArea of the URBAN script have an explicit reference to block enumerations.

[NKF]

A lot of this info has been reverse engineered through guesswork and executable digs and discussed here and there over the years. Although I must admit that I have recently been able to have a look at some materials used by the TFTD developers that hopefully we'll be able to put under the file section in due course . That is, assuming we get the OK from current series owners. Among other things, it has some fairly detailed info on the area of map generation (called "Geomorphics" by the developers). Fingers crossed!

 

Geoscape.exe essentially only creates the outline of the map and then passes it on to Tactical.exe via Geodata.dat, and doesn't directly handle any of the terrain map sets. Tactical.exe does that and does all the work stitching the relevant map parts (maps, routes) into one big map.

 

Geodata.dat stores the map dimension size in module size (6x6x4 for example) as opposed to actual tiles (60x60x4), the X-Com plane type, UFO type, terrain type and two 2d maps equal to the map width x height (6x6 in this example). One map stores the terrain file numbers to load and the other the craft locations. It also holds how many ships are on the map and who own them.

 

As mentioned earlier, each terrain type has its own map generator routine. These routines populate the Geodata.dat map outline.

 

Coral for example, when deciding which big module to use, does a random roll of 0~2 + 10. The resulting number should match up to the big map blocks in this map set. It also reserves the next module over and the two in the row below it. The small modules are a random roll of 0~7 + 2.

 

A few more examples: The Pipes map does a random number roll of 0~3 + 8 for big modules and 0~6 + 1 for its small modules. Volcano does 0~2 + 9 for big modules and 0~7 + 1 for small modules.

 

Geoscape.exe effectively controls the range of files used in each map set from each of its map generation routines. Tactical.exe is technically able to recognise up to 99 map modules for each terrain set, but is limited to what Geoscape.exe provides it.

 

Special maps with certain constraints like the aeroplane, port and other maps with mandatory structures are dealt with by their respective map generators. They simply install the exact modules or range of modules needed, and then randomly fill the rest of the map with what's left over.

 

Except for the mandatory/one-off map modules, there are no counts or constraints on how many times the random modules can be generated. You could in theory have all random map sections filled with the same module. Considering the number of identical random number rolls needed to achieve this, the chances of this happening are very low.

 

- NKF

[Maurice76]

Thanks for your reply, NKF . I know how the GeoData.dat file is structured (thanks to the UFOPedia) and that the GeoScape.exe is responsible for its creation. This implies, however, that it already knows which blocks from the available ones are 10x10 and which are 20x20. In the Port example given by Hobbes, the algorithm used by the game to build the GeoData.dat file for the Port knows that it has to assign blocks 2 through 9 in one of the slots on the right side of the map and no others. I realise that compiling program code creates instructions in machine language that are unreadable to us lowly humans, but while variable names are lost along the way, variable values are not. As such, for instance the algorithm, that creates the GeoData.dat for a mission on the SEABED type, knows that when it goes on to place the 2x2 map blocks, it can assign blocks 10, 11 and 12 (assuming the 10 1x1 blocks are numbered from 0 through 9 internally) and write the corresponding byte values into the GeoData.dat file at the proper spots, so that the Tactical.exe can then map the numbers to actual files. Those specific map block pointers (10, 11, 12) still have to be detectable in the compiled code of the GeoData.exe somehow (and by what you say, it just uses a range starting from 0, with an offset - another interesting take on the way to address it). Something similar applies for instance to the spot where the X-Com craft can be placed in the Alien Colony Entrance (coordinates are seemingly randomly selected from the set of (0A,00), (28,00), (0A,28) and (28,28) in (X, Y) format, so the GeoScape.exe has to contain those four set values somewhere, too).

 

Maybe I should also explain a bit better as to why I want to find out . More than 15 years ago, before reliable internet connections, I had already written a few tools of my own (in TurboPascal, lol) to edit savegames for various games - Dune2 amongst them as one of the first ones. Changing byte values at specific offsets to alter things. Not because I couldn't win without cheating, but just because I could or to fix glaring errors (the unit limit in some missions of Dune2 was one of those). With TFTD, I ran into that infamous bug of finding that last alien on the second level of Artefact sites once too often , which triggered my desire to develop some tools to handle that. So I went on to explore the various savegame files and discover the meaning of various bytes by pattern recognition and trial and error. I learned how to interpret Large units when connecting the UNITPOS and UNITREF files, the meaning of the various flags in the flagbyte at position offset 0x0A of each unit record in the UNITPOS file as well as the connection between the value of the second flag of that byte and the value of the byte at 0x0D in the UNITREF file for the corresponding unit. Based on that, I wrote a number of tools (again, in Turbo Pascal ) to manipulate that data. Among them tools to make all units visible, to make the map completely visible, to relocate units (so I could move units stuck inside a wall to an open tile), list various stats of each unit present (name, coordinates and status) and even one that directly accessed the video card to draw a rudimentary map, showing the units present. That last tool didn't survive video card upgrades . But over the years and a number of system upgrades, I've lost all tools I made myself, except for the one that lists the various stats. I know there are lots of tools out there these days that can do the same as mine did - and probably a lot better, too - but that doesn't take away my personal desire to dabble with creations of my own .

 

As such, I've recently regained interest in the game, rediscovering most of the details below the hood of the game, with a lot of help from the UFOPedia Wiki I might add. The area that I yet left unexplored all these years, however, is how the game handles map creation (hence my opening questions). I've opened both the GeoScope.exe and Tactical.exe in a HEX editor to scan for data patterns, but all the compiled instructions make it somewhat hard to identify the data elements. Like I said in one of the previous posts, I did find references to the X-COM craft and USO's in both .exe files (not only with references to the MCD files used to draw those craft, but also their dimensions in blocksizes and ownership), which seems like a good place to start exploring to see if I can identify the various data elements - especially since the Tactical.exe proceeds with a block referring all the various map types to the corresponding MCD files (by the way, it was interesting to find that each map type can only ever have 5 MCDs attached to it, besides those for the various crafts and the mandatory BLANKS.MCD file). My questions above stem from the fact that I have no idea how the developers went about to program their subroutines and hence, how they arranged the data needed, further increasing complexibility of my search.

 

What I'm really trying to do is see if I can use the base game, manipulate the .exe's into accepting more map blocks; besides potentially adding the T'Leth level 2 set to possible map blocks for Artefact sites (with proper name, just copy them over) also creating new map blocks of my own with the MapView tool and then using them ingame, maybe build alternate Alien Colony entrance maps that it can choose between, etc ... Yes, I know OpenXCOM exists . Anyway, thanks so far for the insight and information, I really appreciate it! And I do hope that you'll be allowed to publish your information, NKF; it'll be interesting to read for sure!

 

Edit: Just this afternoon I stumbled across Zombie's Excel sheet with regards to offsets in the UFO exe files. Although the offsets for TFTD are different, I've already been able to identify the ship/base loadout section and the UFOPedia section within the GeoScape.exe file. Even if they're not the sections I am looking for, they do provide more insight .

[Maurice76]

And this is the equivalent for Port terrain in TFTD:

 

I can say for sure that it's inaccurate when it comes down to drawing the coastline, with respect to the original game. I just had two Port terror missions in subsequent months, and in both cases one of the coastal blocks occurred twice (different one between the two sites) in the column of the coastline.

 

Also, it seems that the coastline for the Island terror mission is somewhat static. I just had one and decided to save just before touching down. I kept reloading about 20 times to see what the GeoData.dat file would contain. In all cases, the game painted the 2x2 coastal blocks in the southwest and southeast corners. If block 4 was in the southwest, 5 would be in the southeast and vice versa. I never saw the game paint 4 twice, or 5 twice. Block 7 was always between those two 2x2 blocks, so right in the middle of the southern row of blocks.

 

With regards to the randomizer detailed above with the ranges and offsets, Island is an oddball. The range of 2x2 map blocks is disjointed, if you ignore the coastal blocks from the range: blocks 02, 03 and 06 are all 2x2 blocks without a coastline. The only way to use the concept of a range and offset there is to include the coastal numbers anyway and simply discard any output that would paint those inland (but that's 40% of the random rolls then; seems awkward). On the other hand, block 06 also features those statues, which would therefore have to go near the coast, but since block 07 can only occur once, it will never fit directly above it ... it makes me believe the game doesn't use that block at all.

[NKF]

The island coast line is set up by randomly picking 20x20 coast block A or B (4 or 5) at geomap row 3, col 1, and then B or A at row 3, col 3 depending on which came first. With a XOR 1, apparently.

 

Then a standard random filler block 8 ~ 14 at row 3 col 2 and finally 7 at row 4, col 2.

 

The rest is installing hotel 2 or 3, then all the gaps are patched up with random blocks 8 ~ 14.

 

Indeed, there doesn't appear to be an way of getting an instance of block 6.

 

- NKF

[Maurice76]

The island coast line is set up by randomly picking 20x20 coast block A or B (4 or 5) at geomap row 3, col 1...

 

I assume you meant to type "row 3, col 0" there , considering that the rows and columns are enumerated (0, 4) instead of (1, 5) for that 5x5 map . It's interesting to see they first filled up the block at (3, 2) specifically and after that the block at (4, 2) ... I thought they would just put the one down at (4, 2) and after placing the 2x2 inland block(s), fill up the yet unfilled areas of the map - including the one at (3, 2) with randomly picked 1x1 blocks.

 

I also assume that you got that info from the materials you mentioned earlier? Because you explicitely state a (row, column) enumeration format instead of a single enumerated line running from 0 to 24 (for a 5x5 map, that is) - I wondered up to now which one they used .

 

Edit: Coming to think of it, that also means that the top of the location of the X-Com craft is always in row 0 or 1 on Island maps.

[NKF]

Actually I was working with 5 * 3 + 3. Just converted into coordinates to help myself better visualise it. I still catch myself with the old fencepost even though I'm well aware of it.

 

Just throwing a wild guess here, but that first random block might have been where block 6 was meant to go.

 

- NKF

[Maurice76]

Just throwing a wild guess here, but that first random block might have been where block 6 was meant to go.

 

I think you're right, if they initially intended the map to be 6x6 mapblocks in size, instead of 5x5. A late change to make it 5x5 may have simply made them opt to fill it in with a random 1x1 tile, while keeping block 06 among the game files, even though it's no longer used ingame. I guess something similar applies to GRUNGE16, which looks somewhat ... odd at the ground level, probably intended as an alternative to GRUNGE15 but scrapped from ingame use near the end of development.

[Maurice76]

The plane on the other hand takes the time to try and fit its two wings (each one a 20x20 block) into the map. It then make several attempts to fit various fuselage sections (tail, mid sections, nose) into the map before filling it in with small 10x10 segments.

 

Funny, I always thought that a tail section would always be present in column 0, a cockpit in column 4 and one mid section in each column between, with wings on the sides. The word "try" is indeed correct here: I've just had two Crashed Plane missions back to back (two UFO's in the same region) and in the first one I only got 1 middle section, 1 large wing (2x2) and 1 small wing (1x1), besides a cockpit and a tail. In the second one, I got no tail, 2 large wings, 2 middle sections and a cockpit. It was a cruiser mission, which was located in the southwest corner of the map, so the game possibly tried to place the tail there a few times and failed, after which it skipped it altogether.

 

Anyway, I've also started to mess around with IDA 5.0 (free version) to disassemble the .exe as well as using the DOSBox debugger, but it's slow going with hundreds of lines of Assembly code to plough through. Learning curve for reading Assembly is also somewhat steep (and the fact that the DOSBox debugger only logs reliably when you have the "core" option to "normal" didn't help either ) and I haven't found any decent C-decompilers that work with 16-bit DOS executables. At least I know it was written in C now, since it was compiled with a Watcom C compiler. I've also found that the game apparently first creates the GeoData.dat file, before establishing its contents and writing them to file subsequently. Hopefully I can find out exactly where in the code the subroutines start that kick off the map generation, but as an added complexity I've found that the game also updates the mouse position as well as the soundbytes between creating an empty GeoData.dat file, and writing the contents to it.

[Maurice76]

It has been slow-going with reallife getting in the way ... but I achieved a small breakthrough tonight.

 

A short while ago I already realised that IDA 5.0 was only disassembling the DOS4GW portion of the executable, which makes it very hard to find the correct spot in the code. After locating the extended portion of the executable (DOS version 1.0, as far as I can tell) at offset 2998h in the executable by virtue of the "LE" tag there, I also learned that they used the Linear Execution extension to make use of the extension offered by DOS4GW. After cutting away the DOS4GW portion from a copy of the GeoScape.exe file, I managed to finally load it into IDA 5.0 properly, as it managed to disassemble quite a lot of the file.

 

I have also been using the DOSBox Debugger to scan the code as it was executing. Thanks to its logger, I was able to log a lot of information to file, allowing me the time to carefully analyse the code and match the code up with some parts of the assembly code produced in IDA 5.0. However, it wasn't until tonight, but I finally found the code responsible for the generation of at least one map type!

 

Using the logging I made while touching down at an Artefact site, I found that the game calls on a function starting at offset 42470h (53 51 56 57 ...) to generate the map for the mission that is going to follow. In fact, the '05' at offset 4249Dh is used to define both the X- and Y- dimensions of the Alien Artefact site top map. The funny thing is that it fills the map block section first with FF's and the RMP file section with 01's, looping through the array 25 times (the counter can be found at 424F2h, which contains the hex value '19', which is 25 in decimals) to fill out all 25 relevant sections for that particular map type. I guess after that it will go and determine the various map blocks; although I'm eager to analyse the section that follows, I'll postpone that for tomorrow as it's getting kinda late here.

 

But this looks very promising anyway! Hopefully I'll be able to fully write down the flow of each of the map types this way .

[Maurice76]

In my explorations, I'm at least verifying a number of the things stated by NKF ... but at the same time, I realise this is my 4th post in this topic in a row, so interest seems to be low. Is any of my exploring of the .exe with regards to map generation already well-known and documented (and I just fail to find that information, making me a member of the loony corner) or is there still room for pioneering, analysing yet undiscovered aspects of this part of the game?

[Zombie]

In my explorations, I'm at least verifying a number of the things stated by NKF ... but at the same time, I realise this is my 4th post in this topic in a row, so interest seems to be low.

 

True, but I'm watching from the sidelines with anticipation! I'm sure that there would be more involvement in this topic if our esteemed colleague Bomb Bloke was active.

 

Is any of my exploring of the .exe with regards to map generation already well-known and documented (and I just fail to find that information, making me a member of the loony corner) or is there still room for pioneering, analysing yet undiscovered aspects of this part of the game?

 

I suspect there's still a lot of room for discovery in this area. As far as I know, most of the map info we found out so far was through game file analysis and testing the old-fashioned way (ie, manually)! I did a little searching through the executable and found some map stuff which I put in my "Mod Sheet" but I never really went any further than that because I'm not an expert on IDE, decompiliers or assembly language. Seb76 used to be into this a lot and he would have helped but he's gone now. Anyway, go ahead and post any information you can find!

 

- Zombie

[Maurice76]

True, but I'm watching from the sidelines with anticipation! I'm sure that there would be more involvement in this topic if our esteemed colleague Bomb Bloke was active.

 

Well, that's at least good to know . I mean, if I was just going to rediscover things that have already been figured out years ago, I would be kinda late to the party and might just consider this a private project instead .

 

I suspect there's still a lot of room for discovery in this area. As far as I know, most of the map info we found out so far was through game file analysis and testing the old-fashioned way (ie, manually)! I did a little searching through the executable and found some map stuff which I put in my "Mod Sheet" but I never really went any further than that because I'm not an expert on IDE, decompiliers or assembly language. Seb76 used to be into this a lot and he would have helped but he's gone now. Anyway, go ahead and post any information you can find!

 

Actually I have used your mod sheet to identify some areas within TFTD's GeoScape.exe file, that didn't tell me anything before . Offsets are different of course, but the data entries themselves are fairly consistent between the two games. I've been browsing these forums and seen Seb76's name getting mentioned a few times, but also that he is no longer active.

 

In all honesty, reading assembly isn't trivial - but again in all honesty, it's not rocket science either. It's just a lot. To give an indication, the code to generate the top side Alien Artefact map seems to stretch across more than 3000 lines (maybe more, my analysis still isn't complete) of manipulating registers and comparing them to finally yield a 92 byte array . Such a quantity is just overwhelming. But at least the number of instructions used seem to be small (even if I know that the x86 instruction set is described in a 2900 pages book by IBM ) and especially the more common ones become "readable" once you see them often enough. But I am still very green ... Google is my friend .

 

Anyway, I spent a good 2 hours yesterday just to decipher the subroutine that places the X-Com craft on that map. Note: I have taken the source of its RNG seed for granted for now, maybe further analysis will yield more information on it. It could be that it reads a "garbage" byte, or a byte that gets filled with a call to the Real Time Clock, as the code does have a subroutine with an interrupt that reads the RTC.

 

My analysis so far:

- The game first initializes the 92-byte array, filling in the X, Y and Z dimensions at the start - at this point it also explicitely sets the map type to '00' (this is set to the proper value only some 3000 instructions later);

- It loops a number of times through the array equal to X * Y, setting the values for the map blocks all to 'FF' and for the corresponding RMP values to '01';

- Then it performs a series of operations and calculations on the random seed, performing two divisions over its course, the second one at the end. At the divisions, it divides the transformed number by the map dimension (either X or Y, they're the same ... the game refers to the X value, even for the random Y-offset) and the remainder of that division is stored as the X-offset and Y-offset respectively;

- Once it has determined it, it performs a check of the value at that spot in the array, at a position equal to X-offset + Y-offset * 5 ( <- this was the formula NKF hinted at, in one of his posts higher up) against value 'FC' - this specific value is used to determine some flag behaviour, which determines which direction a subsequent condition check goes. The check is made to see if that spot is available for the top section of the X-Com craft;

- If so, it uses the derived values to find the bottom side and performs the same check;

- If the location is valid, it performs the calculations for the X and Y values again, with the same input as before (so it didn't store them!) to find the location in the array where the top section has to go, writing a '00' at that spot for the map block, as well as a '00' for the corresponding RMP section;

- Again it performs the X and Y calculations, with the Y-offset increased by 1 for that iteration, to find the location of the bottom section of the X-Com craft, writing '00' to both the map block part and RMP part;

 

After placing the X-Com craft that way, it proceeds with a similar evaluation for map block 9, which is the exit to the second level. That one is more complicated as it's 2x2 in size, instead of 1x2 for the X-Com craft. I didn't analyse that section in detail yet, I only glanced at it for now.

 

My hypothesis now is that the placement of the X-Com craft is a general-purpose subroutine that also places the USO's on missions against those. Since Artefact top side missions use a randomly placed X-Com craft, it makes sense to use the same subroutine as for those missions The check against the value of 'FC' otherwise makes no sense at all, since the array is still completely empty when the game starts to determine the X-Com crafts' location. When used in USO missions, it has to make sure not to place the USO on a spot where the X-Com craft is already located, so there it does make sense. But maybe it's even more generic and also used for other map blocks, once it has determined a set of X and Y coordinates.

 

I'll post more when I find more .

[Maurice76]

Update:

 

Did some more crunching on the logfile I had with regards to the Artefact top side generation:

- After placing the X-Com craft, the game calls a specific subroutine to build the map for the Alien Artefact site. This was actually accomplished through a switch statement in Assembly ... I really had to look that one up to even begin to understand what it was doing;

- Like NKF already stated, after placing the mandatory location of the X-Com vessel as well as the exit building, the game will switch to placing some 2x2 blocks:

--- It will first randomly try to find a suitable 2x2 slot that's available, with respect to the blocks already present;

--- Once it found such a spot, it will randomize among the possible ones. For the Artefact site, this random is between 1 and 2, with an offset of 0A (10) - which matches up with the available map blocks in the MAPS directory. For this map type: blocks 10 and 11 are the 2x2 blocks;

--- It will break out of its attempts to place such a 2x2 block when it meets either of the following two requirements: it has placed two of those 2x2 blocks (excluding the exit block), and/or it has attempted to place them 20 times.

- After it is done with the 2x2 blocks, it will make a pass along the array of map blocks, and randomly pick one of the 1x1 blocks for each of the 'gaps' still present (gaps are found by checking the position on the array against the value 'FF')

 

After considering the possibly layouts for the exit block and the X-Com craft in a 5x5 grid, I realised that some configurations allow for three 2x2 blocks, while others allow for only two. The random + offset was also already stated by NKF .

 

In my TFTD version, the offset value for the 2x2 blocks is located at 444DAh of the GeoScape.exe, '0A'. The game determines the range a bit weird; there is a '01' located at offset 444CBh, which forms the start. It is then increased by 1 through the instructions at 2F885h (which moves it from one register into another, machine code that does that is '66 89 C3') and 2F888h (the '43' is an instruction to raise the value in that register by 1). As you can see by the offsets, it's a different part in the code, hence a different subroutine. I think it's raised in the subroutine by 1 (meaning there's always at least one 2x2 block present in any random map), so to get the full range, the game needs to set the base value first before calling the subroutine.

 

The number of loops the game makes to attempt placement is located at 44513h (hex value '14'), the maximum number it will place is slightly further ahead, at 44526h (value '02').

 

In theory, if you raise the value at 444CBh and add as many 2x2 blocks to the ALART files (.MAP in the MAPS directory, .RMP in the ROUTES directory), numbering them accordingly (ALART12 and higher), I fully expect the game to render the ALART map ingame with possibility of those other blocks.

 

Oh, and I almost forgot: the code that places the X-Com craft also contains instructions to fill the last 8 bytes as well as byte 7 through 10 of the array - and based on that, I found a conditional check to determine what craft type was placed. Hence, the function also places USO's on the map.

 

Edit: Victory: I did get the extra map block ingame, after raising the value at 444CBh by 1. I had copied ALART09 to ALART12, and made a number of changes to it (removed the exit tiles, made a side entrance, etc) and on my 3rd attempt it was placed in the map .

[Space Voyager]

Kudos to you guys... I understand little and I'm ok with that.

[NKF]

My hypothesis now is that the placement of the X-Com craft is a general-purpose subroutine that also places the USO's on missions against those.

 

It's certainly the case with most of the unique missions like the port, island and artefact sites. The more general everyday missions however has a separate routine just for the troop transport that essentially does the same thing but also attempts to set the troop transport away from the alien sub.

 

- NKF

[Maurice76]

I guess you are right, NKF, as you have been before . I am still in the process of mapping out the subroutines myself. Yesterday evening, just before I stopped for the night, I managed to identify the various branches of the switch-statement I encountered. The switch statement compares a specific value against the decimal value 14, but the code that followed was marked as "data" by IDA 5.0. After converting it to code, I found only 12 cases belonging to the switch statement, so that puzzled me somewhat. But after scanning through the subroutines called within each of those cases, I could identify them and understand why there were only 12 to begin with: it referred to all the random top side maps that the game knows and the final one is the Island Terror site (at value 13, so anything higher would be skipped by the switch statement). But from 0 (Seabed) to 13 (Island Terror), there are two maps that drop out, namely the GRUNGE map (at 10) that follows ALART (at 9) and the Ocean Liner (at 11).

 

I can understand the omission of the Ocean Liner, as it's a static map, but the omission of the GRUNGE map was a bit surprising. Either it is handled outside the switch statement, or it's not even handled by the GeoScape.exe, but rather by the Tactical.exe. I haven't opened that one yet, so I don't know which subroutines are in there. I do plan to open it, though, if for nothing else than to figure out why pretty much all the aliens in the Alien Colony stage 2 are placed in the top row of the map blocks (except for the 3 Lobsterman Commanders, who are always at the Synomium Device). Somehow, I am suspecting a bug in either the randomizer not covering the entire range of possible spawnspots, or an overflow error on the total number of available spawnspots.

 

Anyway, now that I've been able to identify the purpose of various subroutines, I'm really starting to make progress in understanding them and identifying the key values within each.

[Zombie]

I can understand the omission of the Ocean Liner, as it's a static map, but the omission of the GRUNGE map was a bit surprising. Either it is handled outside the switch statement, or it's not even handled by the GeoScape.exe, but rather by the Tactical.exe. I haven't opened that one yet, so I don't know which subroutines are in there. I do plan to open it, though, if for nothing else than to figure out why pretty much all the aliens in the Alien Colony stage 2 are placed in the top row of the map blocks (except for the 3 Lobsterman Commanders, who are always at the Synomium Device). Somehow, I am suspecting a bug in either the randomizer not covering the entire range of possible spawnspots, or an overflow error on the total number of available spawnspots.

 

Not sure I understand you. Do you mean top Level (of the modules) or top Row (of all the modules which make up a stage 2 colony map)? Typically this would be North on the compass rose but it's the upper right in the game. There appears to be plenty of spawn points available for the aliens from what I can see... so I dunno what's wrong there. However, in your first sentence you are talking about the GRUNGE map not showing up, which in the game is the Alien Artifact Site 2nd stage. Which is it: Colony (base) or Artifact?

 

As I said, an alien Colony appears to have plenty of spawn points for the aliens. In the GRUNGE maps, there are few (if any) spawn points in the small 10x10 modules (and their spawn priority is almost always 1 which is rock bottom). However, in the big 20x20 modules there are many. If you are talking about the Artifact site, then perhaps the game is only placing the larger 20x20 map blocks in the top row for some reason. That's the only thing I can come up with at the moment.

 

- Zombie

[Maurice76]

Not sure I understand you.

 

Sorry for the confusion. I was at work when I wrote that and in a bit of a hurry .

 

Anyway, I tried to say two things:

- First of all, I encountered a switch statement, which seems to take care of random maps. I've found subroutines for the USO sites (0 through 8), Artefact top side, Port Terror and Island Terror. If you keep the listing as given on the UfoPedia in mind (bytes 10 and 11 in the GeoData.dat file), you'll notice that Cargo Ship is missing, but so is Grunge. That the Cargo Ship is missing from that list is logical, as it's a set map, but Grunge in random. So whatever subroutine is used to build the Grunge map, it's not passing through the switch statement.

 

In the mean time I've also found the subroutine that builds T'Leth top level, which has the Grunge looks. That one, too, is random. It first places mab block 00 in each of the four corners, then randomizes the location for the exit block (block 03), after which it randomizes the location for both entrance blocks (01 and 02, both appear once). After that, it will make 20 attempts to place 2x2 blocks, breaking from that loop if it managed to place 3 of them. Then it fills the remainder with 1x1 blocks.

 

- The second thing I tried to say is that I usually find the aliens on Colony stage two mission to be in map blocks at the north of the alien base. When you look on the minimap, it's the map blocks in the top left corner. Usually all aliens are spread out across a given map, but in that particular mission, I always find them in the northern row, usually in the first 3 to 4 blocks when counting from the left side of the minimap. The presence of a 2x2 block in that top row usually spreads them a little further. The only exception are the Commanders, which are always near the Synomium Device - probably by virtue of the spawnpoints there being the only ones where they can spawn.

 

I am wondering if that clustering of aliens in the northern row of map blocks (especially towards the left side of that row) is caused by a typo in the randomizer that determines the spawnspots that will hold an actual alien, or if the value it feeds to the randomizer is affected by an overflow. I suspect that if the number of spawnpoints exceeds 255, it will omit those spawnpoints. Let's say a typical Colony stage two mission has 300 spawnpoints if you count them across all the used mapblocks; if it discards 256 due to byte overflow, the effective number the game would use to spawn aliens is the remainder, which is some ~45 spawnpoints. Counting from left to right and top to bottom, it finds those all in the top row, towards the left, unable to even use the other ones - which results in a virtually empty base, except for those few blocks. I haven't done any checking on what's going on there, but I intend to once I feel I am done with the map generation .

 

By the way, I've found the determination for the Seabed, Coral Reef or base type selection. It performs a random generation of a number between 0 and 3, which it then checks. If it's less than 2 (i.e., 0 or 1) it will use the type assigned to it based on the location of the worldmap, if it's equal to 2 it will use the Seabed maptype regardless of what was there before, and if it's 3, it will use Coral Reef instead of what was there before.

 

So, for any given maptype used for USO sites, there is a 50% chance to use the maptype based on geographical location, 25% chance on Seabed and 25% chance on Coral Reef. If the basetype was already Seabed or Coral Reef, odds for them increases to 75% and 25% for the other one.

[Maurice76]

--- It will break out of its attempts to place such a 2x2 block when it meets either of the following two requirements: it has placed two of those 2x2 blocks (excluding the exit block), and/or it has attempted to place them 20 times.

 

Slight alteration to the above:

 

The game will cycle 2 times through attempts to place a 2x2 block on the Artefact site. Each cycle will run until either it succeeded, or until 20 attempts have been made, whichever comes first. At the start of the next cycle, the number of attempts is reset to 0 again, so in theory the game could make 40 attempts across 2 cycles if it keeps failing. After 2 cycles, the game moves on to placing the 1x1 tiles on the yet unoccupied tiles.

 

I've also found Colony Stage 2 in the GeoScape.exe file; it runs a slightly different loop. After placing the block with the Synomium Device and two entrance blocks, it will make 3 cycles of at most 10 attempts each to place a 2x2 block on the map.

[Maurice76]

It's certainly the case with most of the unique missions like the port, island and artefact sites. The more general everyday missions however has a separate routine just for the troop transport that essentially does the same thing but also attempts to set the troop transport away from the alien sub.

 

- NKF

 

I've been going over this, but I am finding something different. In every case, the X-Com craft is placed first. On USO recovery mission, the USO is placed next, but the placement routine loads up the location of the X-Com craft and keeps it in mind when trying to place the USO. The strange thing is that both subroutines end with an IF-statement that selects between the craft being placed to be an X-Com craft or a USO, even though it's pretty clear that the first subroutine only handles the X-Com craft, and the second one handles the USO. Seeing also how the source code of both subroutines share a lot of the same operations (with the second one having a bit more in virtue of loading up the X-Com craft position as well, plus a few deviations from the first subroutine at spots), I suspect they originally designed it all to be handled within one subroutine, but ran into some complexities with regards to the USO placement. Rather than to create a difficult construction, they decided to simply split it into two subroutines, by simply copying the code and altering the second one to accomodate knowledge of the X-Com craft. They left some redundant code, like the IF-statement at the end that selected between the two types.

 

The subroutine to place the X-Com craft is called by four subroutines: one that handles the generation of Port Terror sites, one that handles the Island Terror sites, one that handles the Artefact sites and the fourth one handles USO recovery missions (map type is not considered at that point for those missions). The USO recovery mission then calls on a subroutine to place the USO on the map. Each of those four subroutines then call on a further subroutine that distinguishes between the 12 Stage 1 random map types (9 USO recovery, Port, Island, Artefact) to call the specific subroutine for that map type, to fill out the map with the various map blocks.

 

Edit: I stand corrected! The code was quite hard to read, but now I see what it does. There are two subroutines that place a craft on the map. The first one will place a USO if present, or the X-Com craft otherwise. The second one is only called upon when a USO is present and will then place an X-Com craft as the second craft on the map. I did identify that the second subroutine keeps the location of the craft placed with the first subroutine in mind, I just didn't see the switch-over on craft type when it handles a USO recovery mission. This means the IF-statement I mentioned above makes sense for the first subroutine. Not sure why it's present as well in the second one, other than that it was a leftover from copying the subroutine.