Pathfinding is the method used to allow NPC (non player characters) to navigate thier environment. There are many possible solutions to this, however it is unlikely that there is ever going to be a single solution that works perfectly for every single possible usage scenario. Games typically make code that works specific to thier own requirements, however for a technology package such as the Torque AI Pack v1.0 we have tried to provide you with a working solution for almost all possibilities.

How does the pathfinding solution in the AI pack work?

At its heart, the pathfinding solution in the AI pack uses a regular grid of "nodes" which are points that the AI has determined an NPC can stand at. These nodes are clear of any obstructions and have something underneath them for the NPC to stand on.

IMAGE: Put here an image of the typical node graph

These nodes are then connected together to form what we call the "navmesh". This essentially forms a connected set of points called a "graph" which is useful, because we can then describe a specific path between Point A and Point B by the set of nodes (and connections which connect them) that the NPC must travel through to get from A to B.

IMAGE: How a typical path gets from A to B

The big issue is how to best generate that list of nodes and connections so that we get a good path?

Well, luckily for us, from a field called graph theory, there are many well known algorithms that can be applied to a graph of nodes and connections. We simply chose the most well known and used of those algorithms, this is known as the A* ("A Star") algorith.

The good part of the A* algorithm, is that if there IS a possible route between two points in the graph, which is not always the case, we will be guaranteed to eventually find that route, otherwise we will simply fail to get a route, in which case we know a route is impossible and we can handle that case.