iAI - Path finding shenanigans

Well it's been a while since I first mentioned the iAI (immersive ai) project that is underway... so here's an update!

The iAI engine is broken up into four modules - Manager, Seek, Combat & Interact. The Manager being exactly that - managing the various iAI Agents within the game world, providing updates, goal/state changes and ensuring that everything is running smoothly. The Seek module is those functions which allow the agent's to traverse/seek objects in the game world; it's most important component being obviously path finding. Combat focuses on the attack/defend functionality of the agents; with the Interact module focusing on the interactions of the agents with the game world, other agents and of course the player itself.

In order to develop the other modules easier, the core function of the Seek module, pathfinding, needed to be completed.

Seek :: PathMap (Node Graph)

An obvious choice for the path finding is the A* path finding algorithm; which is very easy to implement, once a graph of nodes has been developed... which was quite a task in itself :)

When a mission is loaded, the server generates a complete graph of nodes for the terrain (removing ones inside objects, interiors etc) and assigns the various move modifiers (needed for A*) for each node. Each node in the graph is joined to its 8 neighbours (if it has 8 immediate neighbours). The greatest challenge in this was detecting where interiors/objects were (a castray isn't good enough, as a player needs to be able to reach it), so a combination of both castray and collide box detections are used, depending on the nodes location.

The final result

Just the graph (iAIPathMap) looks like this:


Being a good little algorithm and avoiding interiors/objects:

The bounding boxes for each node, which render differently depending on their move modifier (such as the ones in the water are orange as they have a 70% increase move modifier than normal terrain ones):


And with both the graph and bounding boxes:


An obvious improvement to this is the mapping of interiors as well, and joining that to the terrain pathmap - but that's for later :)

Seek :: Path Creation (A* fun)

Now a nice path map had been developed, it was time to delve into actually creating a path between two nodes. When an agent requests a path from one world point to another, the algorithm grabs the closest node for the start and end points, and calculates the shortest path between the two nodes. It takes into consideration the move modifier, so paths through water are considered harder to traverse etc. If you're interested in the A* algorithm itself, there are heaps of resources on the net about it..

So now that we have a path returned between two points, some optimisations need to be done on it! I thought that the A* returned the shortest path?! It does indeed, but as the world is coated in nodes (and thus the A* will return points from nodes to nodes), we can further optimise it by seeing if nodes can be skipped... smoothing the path.

The concept goes that if a path of A->B->C exists, but a traversable path from A->C exists, then you can skip B. So the smoothing algorithm does exactly that. It checks if the current node (A) and the next next node (C) is in roughly a straight line, and the next node (B), as long as it (B) isn't down a steep hill or something, then it will delete the next node. It completes the check that the next node (B) isn't down a steep hill, to ensure that nodes are skipped from one hill top to another :)

Ok that may have been confusing, but hey, I've got some pictures that might show it a bit better. The path on the RIGHT is the unsmoothed path, with the path on the LEFT being the smoothed path. See how much shorter it becomes? It also reduces the number of nodes in the path, in this case from 36 down to 14.


another picture of the smoothing.. again the smoothed path is on the LEFT with unsmoothed on the RIGHT. Excuse old mate iAIAgent who is traversing the path, hence why the unsmoothed path seems to just end - he's already traversed that section :)



The paths obviously are rendering as splines, but there is an option to switch it to linear rendering (as if you have quite a few paths being rendered as splines, tends to slow down the old frame rate), or off completely of course.


Next Steps

Well the next thing to tackle is the Manager module, and calculating the various goals/states for the agents themselves.

Well that's the end of this update.. till next time, happy Torque'ing