Mysteries of the "small ones" maps revealed!

Firstly, let me explain my terminology, so that we don't get into language problems.

• I call Infantry1Level0Map.raw a "pathmap" or "pathfinding map".
• I call InfantryInfo.raw an "info map".
• I call Infantry.raw a "waypoint map".
• A pathmap is divided up into a number of "segments" each 64 x 64 pixels.

Here's how I think that DICE creates a waypoint map from a level zero pathmap.

For each segment in the pathmap, do the following:

1. Find all the non-connecting "black" regions in the segment.
2. Sort them into descending order of size (number of pixels).
3. Pick a point within each of the four largest regions: the "waypoint" for that region (of course, if there's only one black region, then there's only one waypoint!).
4. Put the coordinates of the waypoints into the structure that will be written to the waypoint map file.

The algorithm that DICE use in step 3 is still a mystery to me, however. Also, why do you sometimes have to "mod 64" their waypoint coordinates?

Once the above steps are done, then the connections between segments have to be determined. Note that I consider the segments to go from the bottom up rather than the top down (because that way they are in the same orientation as the map), so I think of the connections as being to the segment "above" and "to the right", rather than "below" and "to the right".

So, starting at the last segment and working back to the first segment:

1. See if any black pixels along the right-hand edge of the segment line up with black pixels in the segment to the right. If so, then mark the corresponding regions as being connected.
2. See if any black pixels along the top edge of the segment line up with black pixels in the segment above. If so, then mark the corresponding regions as being connected.

The info map is the same size as the level zero pathmap (in number of segments), but the segment structure is different. Each info map segment is 32 x 32 pixels, and each pixel is two bits. The info map is created at the same time as the waypoint map, using the sorted list of regions. Here is how I think that they create the info map:

1. Create a copy of the current 64 x 64 segment.
2. If there are more than three black regions, then white out all regions after number three.
3. Shrink the segment down to 32 x 32.
4. Each pixel in the info segment is two bits, set as follows: largest region = 00, second largest = 01, third largest = 10, everything else = 11.
5. Pack the pixels into bytes, and write the info map.

It's all very well to make these claims, but what evidence do I have to support me? To help me to analyse the path files I wrote a program to display the contents graphically. Here is a screen dump showing part of the Wake Island infantry path maps: Wake.png (24 KB). At the bottom left of the image you can see the current segment and the eight surrounding segments. To the right of that is the data from the waypoint map. To the right of that are the big grids showing the current segment, and the segments above and to the right, with the waypoints colour coded. In the top right you can see the colour-coded info segment.

You can see that the waypoints are in order of decreasing region size, and that the info map segment is a shrunk-down version of the current segment. Note that the "yellow" region doesn't appear in the info map.

You can download and play with my Pathfinding map explorer program (209 KB) if you wish, but be warned that I wrote this program for myself, so it's not production-quality code. Try it with the DICE maps, and compare the results with the output from other tools.

Here is my implementation of the above algorithms: CreateInfoWaypoint (50 KB). It takes a level zero pathmap, and generates the corresponding info and waypoint maps. Note: it doesn't handle boats and landing craft (and there isn't much point adding watercraft support now that FourCentsShy has created genPathmaps!)

Any comments, bug reports, grammar flames, send them to:

BF1942 at home.netspeed.com.au

Note: I'm really quite slack, so please don't be offended if I don't reply to your email immediately. It'll probably take me a couple of days just to get around to checking for new mail :-)

Matthew "Madman" Gill
(AchingLasers in the FPSCentral forums)