I’m having problems with the construction of the nav-mesh for some shapes. My implementation of line-testing to visible polygon vertices is not working for some shapes due to floating point rounding. But I just did some googling and found this great site which has an excellent triangulation algorithm which I will use. By using triangles instead of line-testing, the code should be less-error-prone.
Here’s the site, it’s got a cool applet which shows how off the code:
Nice work man, steady 60 fps on my machine with Java 6 installed. Just curious, have you tried your A* algorithm on maze type of maps with a lot of corridors?
I think if you are solving path finding for the “islands” type of map, A* is an over kill. I could treat the polygons as simple rectangles.
New and improved version, let me know what you think:
http://www.freewebs.com/commanderkeith/PathFinder/AStarPathFinder.jnlp
Thanks dude 8) try out this new version which has a maze. And thanks for the idea!
Now the code is much more robust since I thought of a better may to make the node connections. Every obstacle has an outerPolygon, which is the one drawn, and an innerPolygon which is a slightly shrunk version. The Java Topology Suite (http://www.vividsolutions.com/jts/jtshome.htm) has an excellent method polygon.buffer(double) which does the shrinking (thanks to OrangyTang for the suggestion of using JTS). Obstacle nodes are located at the vertices of the outerPolygon. To test if two nodes are connected, a straight line between them is intersected with every obstacle’s innerPolygon. If there’s no intersection, then the two nodes are connected. Easy! And the two nodes can even be nodes within the same polygon, or one can be the player’s position or target or both.
This is 1 gazillion times better than the previous way i did it where obstacles only had 1 polygon, and every node-node line was intersected with lines that didn’t share the same nodes. This produced messy code and massive problems when the player or target was right on the edge of an obstacle, since lines would intersect even though the player should have been just outside of the obstacle, so he’d get stuck. Here’s a good sum-up of the problems I was having, from the JTS website:
[quote]Robustness problems are especially serious in geometric computation, since the numerical errors can propagate into the combinatorial computations and result in complete failure of the algorithm.
[/quote]
With the new method, everything’s more robust and the code is simpler and cleaner. There’s also some new performance enhancements:
hey 8)
i looked at your pathfinder and i was wondering what you’re going to apply it to? ???
some kind of arcade game or maybe something else?
Cheers bro ;D
Bro!!!
i played your game and it is gnarly!!! :o
like seriously gnarly ;D
catcha on the flip side bro
wooooo!!!1
8)
[quote]try out this new version which has a maze. And thanks for the idea!
[/quote]
Very well done, it is time to put this on a real game application 
However I have a question, when I click a destination on the maze map, a pink path is drawn almost
instantly from the player to the destination. I assume at this point a shortest path is already being caulculated.
But as the player travel towards the desitnation, i noticed that the frame rate drops a lot. There shouldn’t
be any computation at all here, isnt it? I only tested on my another machine with Java 5 installed.
Yeah the path-finding algorithm is done every frame for the purpose of performance and robustness testing, but you’re right that in a real application the algorithm only needs to be run when the target changes. I’ll try and add a ‘recalc every frame’ check-button that toggles this on and off.
I’m going to try and add the code into the rpg game I’m working on. I’ll make some changes to it though, like instead of making node connections between all obstacles I’ll make the algorithm only connect nodes of obstacles that are within a certain distance (like a screen width). This will speed things up at the cost of not being able to do long-distance path-finds, but that’s ok.
If you can think of a cool game to use this in i’d be interested to know
PS: Here are some mock-ups of the rpg i’m working on:
I just had a look at your A-star and noticed another optimisation that can be made. ;D
Whenever you add a node to the open list you call the calcGCost function that runs back through ever node on the path. This isn’t necessary since you can calculate the value directly (as you do on line 100 when calculating newGCost).
This should make a noticeable difference for longer paths.
Ah, another thing. Your nodes are comparing to one another by G cost, when it ought to be by F cost. That should cut down on the number of nodes expanded when there’s a clear run toward the goal. Edit: Infact, as it is it’s actually a Dijkstra’s search, not A* =S
Nice one Jono! Thanks a lot, I can’t believe I overlooked that and wasn’t even using A* at all! 
It was a quick fix - just a change to the Node class’s compareTo method to sort by F cost rather than G cost.
I think it improved the algorithm’s performance lots, but since the demo program spends most of its time rendering there wasn’t a big improvement on my computer - on the maze map the FPS increased about 5 per cent when the path was long.
About the re-calculation of the G-cost, the Node.calcGCost method isn’t recursive - it just returns parent.getGCost() + the distance from itself to its parent. So that should be ok. Thanks for taking a look into the code and helping me to improve it. Let me know if you can think of any other enhancements 8)
The program and the source code is updated. There’s now a new ‘test’ checkbox button, at the suggestion of phu004. When ticked, the path is re-calculated every frame, which slows the frame rate down but is good for performance testing. When un-ticked, the path is only re-calculated when the target changes due to a mouse is click or drag.
Maybe the next feature that should be added is moving obstacles or the insertion of obstacles on the fly?!?
My pleasure! It’s looking like a pretty neat bit of code, so it’s nice to be able to help.
Oh right, I see what you mean. I misread how that recursion was working. ;D
I did just have one other thought. The binary heap takes linear time for the contains method. One way to get this down to constant time could be to use a binary heap and a hash table together. When you add and pop nodes you do it to both structures, but you just use the heap to find the minimum value node (as in the code right now) and use the hash to check whether the open list contains a node. That should shift it from O(n^2.log(n)) to O(n.log(n)) worst case.
I don’t have first hand experience with this, but one approach is to add another dimension so you search x,y,z where the z value is the time taken so far on the path. This should work so long as you know where each obstacle will be at any given time. The current heuristic will still work too, since it will still always underestimate the distance to the goal (which is required to guarantee the shortest path).
Good idea, i’ll add that HashMap in I’m not near a computer with a compiler now, but i’ll do it asap.
By the way, wouldn’t the HashMap.get operation be O(1) and the array search operation be O(n)? Or were you talking about worst-case scenarios where there are collisions in the HashMap.get operation?
That sounds interesting, I’ll read into it more. But rather than that, I was thinking of just simply adding a way to insert (and remove) obstacles - it would probably mean adding some methods to NodeConnector.
Oh, something interesting: I profiled the program while running the maze map and I found that 3 times more time is spent within the NodeConnector.makeReachableNodesFor method compared with the PathFinder.calcPath method, so maybe that’s where any future optimisations should be made.
PS: How do you know so much about the ins and outs of pathfinding? Just an interest or are you studying it?
I meant the overall big-O for the search. It’s actually just O(n^2) as it stands - not O(n^2.log(n)) like I first thought - where as well as inserting to the heap there is the O(n) contains check. There shouldn’t be too many collisions in the hash map, so I didn’t consider this (or any collisions at all? - I didn’t see how the keys were generated).
[quote]PS: How do you know so much about the ins and outs of pathfinding? Just an interest or are you studying it?
[/quote]
I tutored basic graph algorithms and search for a year or two at uni, and had some “practical” experience entering the Robocup Rescue simulation league.
Great, no wonder you’re pretty sharp at this stuff. I originally was hoping that I could use someone else’s A* pathfinding code for my RPG project and wouldn’t have to delve into the A* algorithm myself, but I forced myself to learn it when I saw there wasn’t much out there in java. But now i actually find it really interesting. I’ve spent heaps of time reading about little optimisations like the BinaryHeap.
Hi,
I’ve optimised this further and it’s more than 10 times faster!
Webstart (unsigned): http://keithphw.freehostia.com/PathFinder/AStarPathFinder.jnlp
Try out the very large maze by clicking the ‘big maze’ button at the bottom. It may take a while to generate the maze (but with the second optimisation it takes seconds instead of minutes 8) )
Two changes:
Obstacle points are checked to see if they’re contained by other obstacles once at the start and the value is cached. Before they were always checked to see if they’re contained every frame. That was pretty dumb
This was the big speed up - when a line from one point to another was tested for intersection with obstacles, the obstacle list was unordered. Now I order the obstacle list by the obstacle’s proximity to the points. The closest obstacles are first because these closer obstacles are more likely to intersect the line. This boosted the algorithm speed by more than a factor of 10! Woo hoo!
The jnlp link and source are updated. Any pointers or comments appreciated
Cheers,
Keith
Wow, nice. Impressive. =)
Thanks! ;D
Very interesting! I tried your latest demo, it seemed very robust. Nice work, thank you for sharing this! I’m actually trying to come up with a subject for my masters thesis, one of the ideas was to do it about path finding in computer games. This (path finding through convex shapes) was something I was interested in, but looks like you’ve beaten me to it! Hard to think of a subject that’s “scientific” enough…
Anyway, keep up the good work!
Thanks a lot. There’s quite a bit of research in this area already - about games, robotics and military applications. You’re really lucky that you get to do a thesis on this topic! I’d be interested to know what you end up looking at, it’s very exciting.
There’s so much more that you could do - like what if the obstacles weren’t seen all at once (line of sight). How could you handle moving obstacles. Also, how can multi-threading make it quicker…
Well I’m still undecided, but so far this subject is the one I’ve thought about the most; it would be interesting to do. I did my BS thesis on garbage collection, but I’ve decided not to take it further – too boring to be honest… 
So perhaps I will indeed choose pathfinding for the masters. Those ideas you presented definately sound interesting. In any case, I still have plenty of time to think about it, as I’m not planning to start until next year.
New updates:
I might try to make a tower-defence style game with this since I think it’d be pretty easy now that I can easilly add and remove obstacles in real time.
The demo and source code are updated. I’m not really happy with the API right now because it feels messy since I added ‘ObstacleManager’ so that might change:
Webstart (unsigned): http://keithphw.freehostia.com/PathFinder/AStarPathFinder.jnlp
Let me know if you have any thoughts!
http://www.fileden.com/files/2008/9/22/2110084/swirlScreenShot8_7_09.png
http://www.fileden.com/files/2008/9/22/2110084/wootScreenShot8_7_09.png