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:

- Using a BinaryHeap to store the A* algorithm’s open list. It’s a neat way to store objects in an array where you want the first object to be the smallest. Sorting time is now much quicker.
- Using a HashMap for the A* algorithm’s closed list. Now it’s really quick to check if a node is in the closed list since there’s no need to iterate over the whole list as List.contains(obj) does. I just use HashMap.get(obj) and if it returns null, the obj isn’t there.
- Eliminated connections to concave nodes - points in a polygon which stick in are never connected to any other nodes. This cuts down the number of connections between nodes, making the A* algorithm quicker.