After yesterday’s post, PaoloMan reminded me about how he and Piggi changed the CEngine pathfinding system simplifying the level design by at least an order of magnitude. In fact I had the intention of writing about their bread crumb pathfinding algorithm, but the good will got lost in some interruption of my editing. Anyway the matter is interesting and would be a pity to settle this matter with few lines embedded in another topic, so I am happy that my subattentive mind left out this yesterday.
https://youtube.com/watch?v=Kshhr7Ds7_4
In the beginning it was [https://www.maxpagani.org/CV-projectDesc-RS.html|Rainbow Six: Rogue Spear]. This was the first game of the studio on the then new GameBoy Advance platform with the quite ambitious goal of recreating the playing experience of the PC version of the game.
Pathfinding was needed for a number of actions of non-playing characters. Terrorists had to be able to find their way toward noises they heard, or to the last known position of their pals. Counter-terrorists had to manage to stay together following the player controller team leader.
A full A* algorithm would have been likely to be daunting on the poor ARM 7, so I devised a lighter system for all these pathfinding needs (well the idea was mine, but later I discovered it was already employed by other game engines). The idea was to define a routing network of nodes connected by straightly “walkable” rails. When a character needed to go from its actual position P to a remote position Q it queried the pathfinding system for the routing node closest to its position P. Then it asked the node for the next node in the network in order to get close to Q. In overly-simplified pseudo code it would turn out like this:
currentNode = findNodeClosestTo( P );
targetNode = findNodeClosestTo( Q );
walkTo( getNodePosition( currentNode ));
while( currentNode != targetNode )
{
nextNode = getNextNode( currentNode, targetNode );
walkTo( getNodePosition( nextNode ));
currentNode = nextNode;
}
walkTo( Q );
Although the gameboy side of the algorithm was simple (even with extra code for a more realistic behaviour of characters) and fast (provided a way to quickly find the nearest node you can walk to) two non trivial problems had to be solved on the editor side.
First – networks had to be hand drawn on each map and – second – routing tables had to be computed for each node.
The reason for requiring manual work to draw networks was simply because we didn’t have enough programmer time to put the right amount of AI in the editors. One of the constraints of the project was the maximum reuse of GameBoy Color editors and tools we developed for [https://www.maxpagani.org/CV-projectDesc-RM.html|Rayman GBC] and minimally improved over the next two GBC platform games. This meant that editors didn’t understand the 3rd dimension.
So level designers had to hand draw the network taking care of connecting nodes with walkable line, trying to be very careful when more than one terrain level was involved. Also it wasn’t easy to test and debug the network. First you had to flash the game on a GBA and play it. A quick play throughout the level could not show any flaw even with a flawed network.
A properly designed routing network affected how realistic would be the movement of the characters, so networks were subject to several fine tunings.
Routing tables creation was not that hard, but the “easy way” my fellow programmers took first involved several hours of number crunching on the editor PCs. Level designers were quite mad at us for this daunting weight.
Lear produced a new and much more efficient construction algorithm, trimming down the network computation to a bunch of seconds.
But we were talking about Lara and the prophecy. Well it was clear that laying out routing networks was a big problem, luckily the AI needs for this game were quite modest. The pathfinding would have been employed for enemies to chase the playing character only after a walkable contact have been established.
PaoloMan and Piggi came out with a clever mechanism that allowed us to get rid of pathfinding networks and the related burden. The idea was to have the main character to drop virtual (and invisible on screen) breadcrumbs. When the chasing enemy loses direct sight of Lara (maybe she just turned around a corner), he can search the most recently dropped crumb for walkable way. If the most recent is not accessible, then he should go backward in time until he find a suitable one. It is like the main character defines a subset of a routing network just for the area where she is.
Talking about pseudocode, this approach would be something like:
// breadcrumb 0 is the current character position,
// 1 is the most recent and so on
breadcrumb = getBreadCrumb( Lara, 0 );
// find the most recent breadcrumb you can walk to
i=0;
while( !canWalkTo( breadcrumb ) && i < MAX_BREADCRUMB)
{
++i;
breadcrumb = getBreadCrumb( Lara, i );
}
if( i==MAX_BREADCRUMB )
{
// give up
}
// now just follows the trail
while( i >= 0 && ! canWalkTo( Lara ))
{
walkTo( getBreadCrumb( Lara, i ));
--i;
}
if( i > 0 )
{
walkTo( Lara );
}
What I find notable is that, when working with games, standard solution to known problems (e.g. the A* for pathfinding) could be overwhelming or too daunting both to implement, to run and to manage. Having a clear vision of the needs of the game can point you to a proper, more efficient and simpler solution for the problem.