The Pathfinding Files
In order to play a single player game in Battlefield 1942 an
important part of the game, the AI engine, must be up and running.
The AI is a mechanism, used by the game, to operate the robot soldiers.
The AI is basically divided into two parts. One part is devoted to
determining a good strategy for the robot soldiers to follow; which
point on the map the soldiers should try to take or hold. The other,
called pathfinding, determines ways for the soldiers to get
from point A to point B.
There are three different types of pathfinding files for each vehicle:
- The search map files
- The info file
- The smallones file
Search maps
The pathfinding search maps are one bit images. The bots are allowed to move the given
vehicle around in the areas of the pathfinding map where the bits are set to zero (DoGo),
shown in black. Every place the bits are set high (NoGo) the bots are not allowed to go
and if, by chance they end up in that area, that's where they stay. The picture to
the right is the infantry pathfinding map from Piti. Since none of it extends into the
water, if a bot ends up there vehicle-less, even feet from shore, it will sit there till
it dies.
The names of these files have the following format:
<vehicle name><map number>Level<level>Map.raw
An example: Tank0Level1Map.raw
The map numbers 0-4 correspond to vehicle types tank, infantry, boat, landingcraft,
car respectively. The map numbers are used in the AIpathfinding.con to assign the proper
pathfinding files to the given vehicle. The entry for infantry in the AIpathfinding.con
looks like:
rem *** Infantry ***
ai.addSearchMap Infantry1 0 1.5 30 1.0 0.4 2.0 1
ai.addSearchType Infantry 1 0
ai.setMapSpawnPoints 1 1180/1020
ai.setSmoothing 1 10
The vehicle name is shown in blue, the vehicle number in purple and the number in red is
the map index number. It doesn't refer to the vehicle number, but to the sequence it was
loaded. In maps where there are no sea vessels, the car has a map number of 2. The number
in orange is the minimum search level
and refers to the lowest level (least compressed) map used by the vehicle. For boats and
landing craft this is set to 2 and for land vehicles this is set to 0. This means that,
even if there are level 0 & 1 pathfinding maps for boats and landing craft in the pathfinding
directory, they never get used.
The level refers to how many times the map has been compressed. Each time the image
gets compressed a level, every four bits (two across, two down) get merged into one, halving
it's dimentions. If any of the original bits are set high (NoGo's), the resulting bit
gets set high (NoGo). The opposite is true for the info maps.
SmallOnes mesh overlaying the info image for Iwo Jima
The way these images are stored is consistent with the way they are used. Notice
the image to the right. Before a search map image is stored, it's broken down into 64x64
pixel tiles, displayed in the image as a numbered grid. Information for each of these
tiles is processed and stored seperately from the other tiles. This information is stored
as a chain of 64x64 pixel images. To save space in the file,
if the tile is all DoGo's or all NoGo's, the image is replace with a 0 or 1 respectively
(4 bytes long). if the information in the tile is a mixture of both DoGo's and NoGo's, a -1
marks the beginning of the record in the search map file, followed by 512 bytes of image
information (64*64 bits equals 512 bytes).
The Info File
The search maps are used to create the smallOnes and info files. After the search maps have
been broken down into tiles, each tile is examined and broken down into up to 4 contiguous
(connected) areas in order of size. if more than 4 seperate areas exist in one tile, only
the 4 larges are chosen and the others are ignored. Before being stored in the info file, the
tile gets compressed 1 level, but unlike the search maps, if any of 4 pixels ( 2 across by 2 down)
are DoGo's, the resulting pixel is a DoGo. This makes the DoGo regions slightly large than
the regions in the search map.
A single info tile with and without grid imposed
The info files are 2 bit images. Each pixel can have a values from 0 (00b) to 3 (11b).
The NoGo areas in the tile have a value of 3, which would be the same as the 4th area (if
there is one). How the game handles that is only a guess, but if the bot is in a valid
pathfinding point in a tile that has 4 areas and the info files has that point set to 3,
it must be the 4th area.
The SmallOnes File
The smallOnes file is not an image. It's a mesh of sorts. It's used to connect all the
pieces back together. A point is chosen for every area that exists in the info file. How the
point is chosen is arbitratry. Some think it's a waypoint and it might be. More importantly,
it's used by the AI to determine if the bot can move from one adjacent tile to the next.
For every smallOne point in a tile there is a 4 flags that mark whether or
not it is connected to any of the 4 possible points in the next tile in the adjacent column
and row. So every smallOne point can be connected to, at most, 8 other smallOnes points, 4
each in the next row and col. Since any previous tiles will have these flags set if connected
to the current tile, there is no need to mark connections to any tiles in previous columns or
rows.
Moving Around
In order for a bot to get from any point on
the map to another point. There must be a contiguous DoGo area connecting them. The game
AI consults all three file types for a vehicle, looking for a combination of connected tiles
that do just that.
In order to get from point A to point B, the bots need to first consult the lowest level
search map for to see is both points are in valid pathfinding areas, then the info file to
find out which smallOne points to use for both. After finding the starting and ending smallOnes,
it needs to find a chain of connected smallones that get from point A to point B. With a chain
of smallOnes chosen, the bot checks the info and search map files again to draw the path it
needs to take.
| 
