July 16, 2005

Pathfinding Algorithms & Search Space Representations Demo

Here's a pathfinding demo I wrote in 2003 that some readers may find useful (and thanks again to Damian for hosting this!).

The demo allows you to freely mix and match any of four different search algorithms (Breadth-First, Best-First, Dijkstra's, and A*) with any of ten different search space representations (4-way grid, 8-way grid, hex grid, quadtree, corner graph, waypoint graph, navigation mesh, and oh so much more).

You can also execute any of the four search algorithms as a bidirectional search.


Click on the image below to download.

EDIT (12/26/07): To anyone looking to get their hands on the source code for this, I regret to inform you that I recently lost it all in a hard drive crash ...

Posted by PaulT at July 16, 2005 10:36 AM
Comments

Thanks for the nice demo!

Have you considered actually adding new nodes for start and end points to a corner/waypoint graph? Obviously the path to the closest node isn't always the best one, or even traversable.

Any thoughts how to handle different size of objects with different representations? Expanding the walls and obstacles works fine, but requires separate search spaces for different size of objects. At least with corner graph it's possible to calculate maximum radius for each node and connection. How about other representations?

Thanks for the AIIDE presentations, I hope to see you guys again next year :) And good luck with this blog, it's looking good already!

Posted by: Jarmo Kauko at July 19, 2005 11:25 PM

> Thanks for the nice demo!

Thanks! :)

> Have you considered actually adding new nodes for
> start and end points to a corner/waypoint graph?
> Obviously the path to the closest node isn't
> always the best one, or even traversable.

Good point. Frankly, that is a bug with the current implementation; it's much too easy right now to get the path to go through an obstacle on the way to the first or last point of the search on the graph.

If I ever get the time to update this to version 2.0, I will definitely fix that.

> Any thoughts how to handle different size of
> objects with different representations?

Great question. Here are just a handful of the possible approaches:

-2D grid/Quadtree: if each unit has circular collision and the graph has sufficiently high resolution relative to the size of each unit, it's possible to measure the unit's radius in terms of a number of cells (rounding up, such that if a tank has a radius of 15 pixels and each grid square is 10x10 pixels, you consider the tank as having a radius of 2 grid squares). You can then test each grid square you want to pathfind through and determine at runtime whether or not it's blocked. If you're only considering static obstacles (i.e. not pathfinding against other units or the player), it's also possible to cache this data in the grid directly as a performance optimization.

It's my understanding the RTS classic Total Annihilation used several 2D grids in parallel -- there were N number of standard unit sizes (where each unit had circular collision), and each of these N possible unit sizes had its own completely independent grid that's valid for that type of unit. So if I'm a small tank, I'm using a different grid from a what huge walking Krogoth mech uses.

-Circle-based waypoint graph: in addition to storing the radius of any given circle in the graph, you can also store the maximum radius for the the link between any pair of nodes in the graph (i.e. the size of the widest creature that could travel between the two nodes in a straight line).

-Navigation meshes: the two general approaches here (AFAIK) are to either store multiple different navigation meshes for the different possible sizes of objects (which takes a lot of memory and requires a small, fixed number of allowable object sizes), or to "shrink" the Navigation Mesh at runtime by pulling in all of the polygon edges of the NavMesh that are up against obstacles that the unit in question wants to avoid.

This is a bit trickier than it seems since you need to precompute a bit of additional data to do this correctly. You can imagine, for example, that we have a character with a radius of 10 units, and he needs to walk through a triangle somewhere in the NavMesh, and we know that there is no NavMesh on the other side of edge #2 of that triangle. If we're building a path that goes through that triangle, edge #2 *MIGHT* be marking a wall -- or it might just represent a hole in the ground the character doesn't want to fall into.

In the former case, we want to pull in the NavMesh by 10 units to make sure the character doesn't bump into the wall, but in the latter case, we probably want to ignore it, since it's probably OK if part of the unit dangles over the edge of the pit as he moves around (we know that his center will be on the NavMesh triangle at all times, so there's no danger of him falling into the pit).

The best I can do in the limited space and time I have available is point you to my article "Building a Near-Optimal Navigation Mesh" from AI Game Programming Wisdom Volume 1, which discusses the implementation for NavMeshes. I'd like to write a more exhaustive article on just this topic at some point.

Posted by: Paul T at July 20, 2005 07:59 AM

Mmm, nice visuals. It's so much easier to get the behavior (and especially the weaknesses) of an algorithm when one can actually *see* what it's doing! :)

Posted by: Rob at July 20, 2005 05:12 PM

Nice little demo! (Although, it crashes quite often, but hey, it's just a demo :)

On the subject :

***Navigation meshes: the two general approaches here (AFAIK) are to either store multiple different navigation meshes for the different possible sizes of objects (which takes a lot of memory and requires a small, fixed number of allowable object sizes), or to "shrink" the Navigation Mesh at runtime***

... Let's say we have two goals for NavMesh : pathfinding and the actual AI-movement over the NavMesh. The size of the object/agent only really matters in pathfinding process (because we can always easily simulate "real" physics repulsion of the NavMesh edges). The good approach is to specify the 2D mesh for the agent and then use Minkowski Sum with the NavMesh and the mesh of the agent, keeping only extended vertices that will be obstructed (no line-of-sight), effectively making a higher pathfinder level, using POV approach with newly created vertices, with the actual NavMesh patfinder on the lower level (if needed at all). It shouldn't take a lot of memory, NavMesh stays the same and it also provides the ability to "cut out" areas not traversable due to size restrictions.

Posted by: Bojan at August 9, 2005 06:55 AM