Classes and data-types
Classes used to describe the world
These classes store information about the game world. The examples provided with ASIPathFinder are just that...examples! You could easily reimplement them to better suit your requirements.
ASIWorldMap
A three-dimensional array that stores the actual positions of objects in the game world. ASIWorldMap is actually a subclass of the included ASIObjectMap, which is a generic three-dimensional, fixed size array of pointers.
ASIMapObject
An object in the game world. Subclasses represent objects with different properties.
ASIUnit
An ASIMapObject subclass used to represent an object that can move.
ASITeam
ASIUnits belong to an ASITeam, and all objects in the same team will co-operatively path find with each other.
Classes used for path finding
ASISpatialPathAssessor
Each object that needs to move uses it’s path assessor to calculate a full path to the destination before real path finding begins.
Because path assessment can be fairly CPU intensive, ASISpatialPathAssessor allows you to pause path assessment and resume it at a later time (by tweaking MAX_NODES_TO_ASSESS_PER_STEP).
ASISpaceTimeMap
A 3-dimensional array, where the first two dimensions represent a position in 2d space, and the third represents a point in time. Each ASITeam has its own Space Time map that all objects in that team use for reserving their future position.
The size of the 3rd dimension (time) governs how many steps objects will plan in advance when performing path finding. More time steps will improve reliability, since some collisions may take many moves to resolve. However, more steps will also take more time to calculate. Also, the greater the number of time steps objects plan in advance, the more likely an obstacle (such as an enemy unit or newly-constructed building) will appear in the meantime, which will force replanning.
ASISpaceTimePathFinder
Allows objects to perform path finding. Objects plan x steps in advance, where x is the size of the z-dimension of the space time map. Once a partial path has been calculated, positions are reserved on the space time map so another object cannot travel to that position at that time.
ASISearchNodeList
A search node list is basically an array of positions to be considered during both path assessment and path finding. At each step, path assessors and path finders look at the adjacent positions, find out if it is possible to move to them, and, if so, add them to the search list.
Once all adjacent positions have been looked at, the path assessor or path finder simply grabs the first node on the search list, and uses it’s position to start over again, looking at adjacent positions.
As items are added to the search node list, they are sorted in such a way as the first item on the list is always the best node to consider next. This is done by comparing the node’s distance from the destination, and the cost to get there (more on these below).
In implementation, ASISearchNodeList is basically a binary heap.
ASIPath
An array of positions, generated by the path finder. ASIUnits each have a path that describes the route they will take for the next few moves. As they move, they simply take the first position in the path, move there, and then remove it from the path.
ASIPathSearchDataTypes
Structs, constants and functions used by all the path finding classes, see below.
Primitive data types
Position3D
A struct that stores a position in 3-dimensional space.
Size3D
Similar to a Position3D, but is used for describing a 3-dimensional size.
Node
A struct that defines a particular position used during path assessment and path finding, along with the distance from the destination, the cost to reach that position (see below for more info on these), the direction used to travel to this position, and the parent node (the node. we were travelling from). Path finders can construct a path knowing only the final node simply by walking back through the parents of the node.