A* path finding made lightning-fast by pre-compiling

Pre-compiled A* path-finding

This resource contains an AI path finder implemented in C++ for Torque.
It is capable of calculating the best path from one node to another by using the A* algorithm.

DOWNLOAD THE SCOURCE AND EXAMPLE CODE HERE

Its interface suggests that it can work in both pre-compiled and "live" mode, but this is not true as it does nothing if the navigation net has not been pre-compiled. It does however have all the stuff needed to run in a "live" mode, you just have to add some code to call the pathmanager in this case ( I never completed that part of the code as we only use pre-compiled paths ).

The plus side

- If the navigation nodes are pre-compiled, the "live" work is reduced to fetching an entry from a table.
- If using "live" pathfinding: it is still a lot faster than in having the pathfinder implemented in script ( A navigation net that took 15 minutes to calculate with the A* implementation in the "CTF Bots" resource took about 10 seconds to compile with this path manager ).

The minus side

- When using the precompiled pathfinding, you will have trouble with a dynamic navigation net ( Like supporting un-locking a door, or blowing up a bridge ).
- The pre-compiled data may get big in huge navigation nets ( But I tried to save a minimal amount of data ).

How it works

1) Place a bunch of navigation nodes in your map.
2) Feed the AIPathNodeGraph all the nodes in your map ( a 3D locaion & a movement modifier ).
3) Tell it what nodes are connected to each other.
4) Tell the AIPathNodeGraph to compile all the nodes to find out where you can go from where.
5) Start using it.

Heads up!

When using the pre compiled pathfinder( the only thing that works ), you do not get a complete path when asking how to get from point A to point B as you would expect then using the A* algorithm... you will only get the next node to go to from point A.
This is because this is the only data that is saved when compiling.
If you really need all of the path you can ask again from the next node or re-write the as you see fit.
When you go to work ( shool, shop, visit your hamster ) do you plan how to get past that signpost on the other side of town before you get out of bed? ;)

Using the system - Nodes

In the file Navigation.cs there is a declaration of the NavNode. This is the nodes that the system uses to create the navigation graph. They should now be found as editor objects under the shapes/NavigationNode category in the mission editor.
These nodes MUST be placed in a group named "MissionGroup/NavigationNet". So create this group and add a bunch of NavNode objects to it.
The default move modifier for a node is 0. So if you don't set the moveMod to something higher than that, the node will be easy to walk to. The maximum value of moveMod is 1. Setting it to 1 or higher will make the node impossible to reach. Setting it to something like 0.9 will make the node lava-filled, that is: sure, you can go there, but you won't unless the barrel of a loaded shotgun tells you so.

Some tips on node placement:

1) Visibility: Nodes are linked together if they "can see" each other ( using a raycast ) and are close enough to each other ( see tip 2 ). So make sure you have a clear line of sight between nodes that you want to become a walkable path. And remember, the collision boxes of objects may not nessesarily be even remotely close to what its visible geometry suggests. And place the nodes a bit above ground to avoid "blinding" them, at eye-level is a good rule of thumb ( eye? ).

2) Distance: Using the variable $NAV_NODE_RADIUS in "Navigation.cs" ( default value = 80 ), you can control the maximum distance that two nodes can have and still be linked. So if you hava a corridor that is 100 units long, it would probably be enough with a node just outside each end and one in the middle. More nodes than that would only increase the compile time. But let me disagree with myself at once here: Say you would expect BOTs to hang around in this corridor, there would be only one node to hang around. And if two (friendly?) BOTs meet in this corridor, they would likely collide and head-butt each other ( See my example map, lots of stubborn BOTs there ).
So in conclusion: Keep your nodes sparse, unless you need more of them for any reason.

3) Separete node nets: After placing some nodes and realising they seem to link up and compile nicely ( all the ugly pink blobs are gone ): You may find that a BOT can't reach all the areas you expect it to. Indeed, the system detects nodes that aren't linked to other nodes, but there is still no guarantee that all nav-nodes have been linked into a single nav-net. Several nav-net may have been created that has no links to each other. This can be both a problem and a feature.
If it is a problem for you: go back to 1 and 2 adn make sure the nodes are close enough and can see each other.
If it is a feature for you: Use it to place BOTs in separate areas of your map and make sure they stay there.

4) The A* algorithm outsmarting you: Say you put your nodes in a fine round arc. You think the BOT will use it? Not bloody likely! Not unless the nodes are just inside the $NAV_NODE_RADIUS from each other. The A* algorithm works by finding the shortest ( if all nodes have the same move-modifiers ) or the most efficient ( if some nodes have the altered move-modifiers ) route to its destination. This may not be the route you would want it to take, and the bot may take corners with questionable grace, as an example. To reduce this: Make sure that the nodes are sparse enough to force the BOT using the nodes you placed, or work with the visibility. Or just accept that your computer is smarter than you.

5) Use the editor: The path drawing code supplied by Stephane Conde makes the paths show up in red when in the editor. Use this to find out what the system is actually doing.

Using the system - Compiling

If everything goes according to plan ( it never does ), you should be able to compile the path nodes by calling the "buildNodeGraph()" method. It will then be saved to the file:

data/missions/paths/<name_of_your_mission_file>.path

Two warnings here:
1) If the directory "data/missions/paths" does not exist ( only "data/missions" usually exist ) you will have to create it manually, else all the hard compiling will be done and still it will not be able to save it for a rainy day.
2) The system will not detect if you move the nodes around, change their values or make any chnges to them at all: so after you edit the navigation nodes, you will have to remove the path file manually. If you don't the system will use the old node data that has been saved to the path file.

Finding out where to go next

If the systen is started up correctly, you should now have an object named NodeGraph that can do magic for you.

Righty: Say you have a BOT that has just spawned and he/she/it wants to haul ass to some place other than where it is right now.

First it needs to know its closest node, so do this ( %somethingInTheWrongPlace would typically be the BOT or anything that can have getPosition() called upon it ):

%iWantToGoFromHere = NodeGraph.getClosestNodeIndex(%somethingInTheWrongPlace.getPosition());

...this call will reply with an index of the closest node ( Not the ID of the node or anything like that, the ID is a number used internally in the NodeGraph ).

Second thing to do is the same with a location that you want the BOT to go to:

%iWantToGoToHere = NodeGraph.getClosestNodeIndex(%someNicerTarget.getPosition());

..or just:

// The location "1.0 2.5 666.0" is the nicest place I know :)
%iWantToGoToHere = NodeGraph.getClosestNodeIndex("1.0 2.5 666.0");

Third you ask the system of the ID of the next node to go to:

%idOfNextPlaceToGoTo = NodeGraph.getNextNodeIndexOnPath(%iWantToGoFromHere, %iWantToGoToHere );

Fourth you ask for the actual location of the node:

if(%idOfNextPlaceToGoTo != -1) {
	%nextCoordinateToGoToReachBliss = NodeGraph.getNode(%idOfNextPlaceToGoTo);
}

Fifth you just tell your BOT to go there. This should be something like this:

%somethingInTheWrongPlace.setMoveDestination(%nextCoordinateToGoToReachBliss, true);

The files and where to put them

OK, enough teasing, you want the code don't you.

The C++ source are new objects, so you should only need to add these two files to your project(included in the Zip file):

engine/game/AIPathManager.h
engine/game/AIPathManager.cc

...also: Remember actually adding the files to your project. :)

Files to edit

If you want the node net to be drawn with red lines when in editor mode ( trust me, you want this, at least while developing ) edit this file:

engine/editor/worldEditor.cc

Add:

#include "game/AIPathManager.h"

...as the last #include statement.

And in WorldEditor::renderScene(), just after glDepthFunc(GL_LEQUAL); (should be the 2nd line in the function...) put this:

// Render the new paths
for(SimSetIterator itr(Sim::getRootGroup());  *itr; ++itr)
{
   AIPathNodeGraph* obj = dynamic_cast<AIPathNodeGraph*>(*itr);
   if (obj)
      obj->renderPaths();
}

...that should be all you need for the C++ code.

OK: now we move over to the scripting part of this beast(included in the Zip file):

server/scripts/Navigation.cs


...remeber to actually execute the file above with something like:

exec("./Navigation.cs");

...someplace like in function onServerCreated() in server/scripts/game.cs.

exec("./Navigation.cs");

Now to perform the actual compiling-saving-loading of the nodes, you would typically call:

buildNodeGraph();

...from inside the "startGame()" method in the file "server/scrits/game.cs".

To get the NavNode selectable in the editor, copy all the files in the "data/shapes/markers" directory of the Zip file to, yep ypu guessed it, "data/shapes/markers" ( There is no absolute need to use these, you can use any entity that has a location. But I'd recommend using these nav markers as it will be easier to pinpoint errors if you have the same files as everyone else ).

Installing the example

In the Zip file for this resource there is also a very simple example map.
It is the classic "Stronghold" with 72 nodes and 100 Torque Orcs added.
They collide and block each other and act really stupid as they blindly follow their paths and dont give a rats ass about their surroundigs.

Install instructions can be found in the Zip file.

The screenshot is from this map in action.

DOWNLOAD THE SCOURCE AND EXAMPLE CODE HERE

That's it, my work here is done

Using this system, you should be able to have 200 BOT:s running around your map and having the poly count be a bigger problem than the pathfinding :D

/Bjarne

Thanx to:

- Mark Holocomb, author of the AI Pathfinding with CTF Demo ( This resource started there and grew to its current state because the specific needs of our project. )

- Stephane Conde, that supplied the code to visualize the node-net in the editor.