A* navigational mesh path finding

Question

So I've been making this top down 2D java game in this framework called Greenfoot and I've been working on the AI for the guys you are gonna fight. I want them to be able to move around the world realistically so I soon realized, amongst a couple of other things, I would need some kind of pathfinding.

I have made two A* prototypes. One is grid based and then I made one that works with waypoints so now I need to work out a way to get from a 2d "map" of the obstacles/buildings to a graph of nodes that I can make a path from. The actual pathfinding seems fine, just my open and closed lists could use a more efficient data structure, but I'll get to that if and when I need to.

I intend to use a navigational mesh for all the reasons out lined in this post on ai-blog.net. However, the problem I have faced is that what A* thinks is the shortest path from the polygon centres/edges is not necessarily the shortest path if you travel through any part of the node. To get a better idea you can see the question I asked on stackoverflow.

I got a good answer concerning a visibility graph. I have since purchased the book (Computational Geometry: Algorithms and Applications) and read further into the topic, however I am still in favour of a navigational mesh (See "Managing Complexity" from Amit’s Notes about Path-Finding). (As a side note, maybe I could possibly use Theta* to convert multiple waypoints into one straight line if the first and last are not obscured. Or each time I move back check to the waypoint before last to see if I can go straight from that to this)

So basically what I want is a navigational mesh where once I have put it through a funnel algorithm (e.g. this one from Digesting Duck) I will get the true shortest path, rather than get one that is the shortest path following node to node only, but not the actual shortest given that you can go through some polygons and skip nodes/edges.

Oh and I also want to know how you suggest storing the information concerning the polygons. For the waypoint prototype example I made I just had each node as an object and stored a list of all the other nodes you could travel to from that node, I'm guessing that won't work with polygons? and how to I tell if a polygon is open/traversable or if it is a solid object? How do I store which nodes make up the polygon?

Finally, for the record: I do want to programme this by myself from scratch even though there are already other solutions available and I don't intend to be (re) using this code in anything other than this game so it does not matter that it will inevitably be poor quality.

Answer 1

I would advise that even if you are going to write all your own code, that you download Recast and build the sample application as it has visualisations that show the generated navmesh and it allows you to test the path-finding with a simple point and click interface. You can learn a lot just by playing with that.

As you have already realised, there are two steps to producing a good looking path - the A* path-finder and then the subsequent post-processing which includes path straightening (the elimination of any turns not necessary to avoid obstacles) and possibly also the adding of curves at the turning points.

Path finding

You've got the A* part mastered which is great. You have also made the observation that A* will not always find the straightest path. It's crucial to understand that this is because A* is an algorithm to find the shortest path through a graph (being a mathematical concept where nodes are dimensionless) when you apply it to a mesh, you have to map nodes to mesh elements somehow.

The most obvious thing to do is to navigate from polygon centre point to centre point and base the cost on this distance, but this has some problems. One is that it won't always find the geometrically shortest path and the second is that if you try and follow the path you've calculated there you'll notice that a straight line from one centre to the next can cross a polygon that isn't part of the path (and might not be navigable at all). It's not an awful way to cost the graph traversal while perform A* but it's clearly not adequate for any traversal purpose.

The next simplest solution is to perform A* from edge to edge through the mesh. You'll find this simpler to think about if you imagine that instead of one node per polygon, you have one per-edge per-polygon. So your path goes from your start point to just inside the nearest edge, crosses to just inside the edge of the adjacent polygon and then to just inside the next edge in that same polygon and so on. This produces the shortest path more often and also has the benefit of being traversable if you don't want to perform a path straightening step.

Path straightening

The algorithm used in Detour (the navigation library that accompanies Recast) is pretty simple. You should observe that it will only straighten the path within the bounds of the polygons found during the A* search. As such, if that doesn't not find the tightest path around an obstacle, you will not get a tight path after running that algorithm either. In practice the navmeshes produced by recast tend to have a single polygon that you can pass through when navigating a choke point (the closest point between two obstacles) and so A* will always produce a list of nodes that are as close to the obstacle as possible. If you are using tiles as the navmesh, this won't be the case and this very simple algorithm will insert spurious turns.

Detour's path straightening algorithm isn't quite O(n) in complexity because when it determines that it needs to insert a turn, it inserts it at the point where it last tightened the funnel to the left (when turning left and vice versa) and then starts tracing through the nodes from that point again.

If you want to straighten the path outside of the polygons that form part of the A* route, things get a lot more complex. You'll need to implement a ray-cast routine that can test if two points in your navmesh can see each other (you should have this anyway so you can see if you need to use A* at all). You do this by intersecting the line segment formed by origin->target with the connecting edges of the polygon containing the origin, then testing the connecting edges of the polygon that moves you into and so on. If you intersect a non-connecting edge (I call them border edges), then you've hit an obstacle.

You can then perform this ray-cast test whenever the funneling algorithm determines it needs to insert a turn to see if it really does, but I think you'll have to keep performing that test at every node until you do insert a turn (at which point you can revert to the simple funnel algorithm). That's going to get expensive, rendering the path straightening approximately O(n^2).

Representing the navmesh

You can represent your mesh as an array of polygon classes. The polygon class could be as simple as an array of vertices and an array of references to the adjacent polygon for each edge if there is one. Of course you can probably think of ways to store that more compactly. Since a vertex is usually shared by several polygons, it's normal to have one big array of vertices and then have each polygon store indices into that array. Depending on the characteristics of your navmesh you might have an average number of connecting edges that's only 50% or less of the number of edges. In that case you might want to store a link to another polygon and the index of the edge rather than store a link for every edge. Also I recommend you store the index of the polygon in the navmesh's polygon array rather than using a class reference.