A* navigational mesh path finding
- by theguywholikeslinux
So I've been making this top down 2D java game in this framework called Greenfoot [1] 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 [2]. 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 [3].
I got a good answer concerning a visibility graph. I have since purchased the book (Computational Geometry: Algorithms and Applications [4]) and read further into the topic, however I am still in favour of a navigational mesh (See "Managing Complexity" [5] from Amit’s Notes about Path-Finding [6]).
(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 [7]) 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.
http://greenfoot.org
http://www.ai-blog.net/archives/000152.html
http://stackoverflow.com/q/7585515/
http://www.cs.uu.nl/geobook/
http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html
http://theory.stanford.edu/~amitp/GameProgramming/
http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html
