A* Pathfinding through 2d polygons

Shared Code
#1

EDIT: see StraightEdge project at http://www.java-gaming.org/index.php/topic,23427.0.html

Hi,

I made some code which uses A* to find the quickest path through arbitrary 2D polygons. Here’s a little test program that you can try, just click/drag around the left and right mouse buttons:

http://keithphw.freehostia.com/PathFinder/AStarPathFinder.jnlp
source (note that clicking this link may not work, you may have to paste the link text into your browser window to actually download the zip file):
http://keithphw.freehostia.com/PathFinder/src.zip
dependency jar (Java Topology Suite):
http://keithphw.freehostia.com/PathFinder/jts-1.8.jar

There’s 2 things that the code does (or tries to :persecutioncomplex:):

  • Links the corners of polygons together if they are straight-line reachable, to make a kind of mesh that the A* code can work on. This code is in NodeConnector .
  • Does A* on the mesh, and tries to find the quickest path. This code is in PathFinder

You guys are the best source of info on this stuff that I have ever known, so if anyone’s got any tips for me on how to make it better, I’d really appreciate it. Also, if anyone would like to work on the code together to use in a 2d RPG style point-and-click game, let me know 8)

I suspect that my implementation of A* is very inefficient, so any help would be greatly appreciated - general tips, code, or even just saying hi! :slight_smile: 8)

Thanks!
Keith

PS: Hmm, after profiling my code, it looks like I call ArrayList.contains too often…

#2

wow, ticking show nodes halves the FPS…

#3

Yeah there’s quite a few lines that get drawn when you tick that.

If you use java6u10 on windows and have a non-intel video card, then lines are accelerated so it doesn’t make much difference.

#4

There’s now a ‘player’ (a pink dot :P) which you can move around by clicking. Try adjusting his speed in the bottom text field. Source and links updated.

There’s a bug where overlapping obstacles can cause the player to get stuck, i’ll fix it up soon.

PS: The frame rate is shown in the top left. Regarding performance - every frame the path is re-calculated and rendered, and then the game loop thread sleeps for 1 ms before starting again.

#5

It’s a bit awkward that the framerate drops the same amount when there is either 1 node in the way, or lots of nodes.

Maybe you check everything-against-everything when 1+ collision occurs?

#6

Yeah that’s right. If there’s no straight-line path from the player to the target, then the NodeConnector finds all straight lines from the player to every possible polygon vertice, and from the target to every possible polygon vertice. These lines are shown in blue when you tick ‘Draw Node Connectors’, the check box at the bottom. I think I need to make these lines because they are used by the A* algorithm. The straight lines between all of the stationary polygon vertices are pre-calculated and cached (these lines are drawn in grey).

Hey I’m finding that I use the ArrayList.contains method too much. In the A* path-finding method I call it every time before I add a node to the closed or open list to make sure that I don’t add it twice. Should I use a HashMap instead, because then the HashMap can just find out straight away if that node is already contained rather than cycle through the whole list to see if it’s already there?
Thanks for taking a look :slight_smile:

#7

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:

http://www.cs.cornell.edu/Info/People/chew/Delaunay.html

#8

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.

#9

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.
#10

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

#11

Bro!!!
i played your game and it is gnarly!!! :o
like seriously gnarly ;D
catcha on the flip side bro

wooooo!!!1
:smiley: :frowning: 8)

#12

[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 :slight_smile:

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.

#13

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 :slight_smile:

PS: Here are some mock-ups of the rpg i’m working on:

#14

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

#15

Nice one Jono! Thanks a lot, I can’t believe I overlooked that and wasn’t even using A* at all! :stuck_out_tongue: 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?!?

#16

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).

#17

Good idea, i’ll add that HashMap in :slight_smile: 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?

#18

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.

#19

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.

#20

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 :stuck_out_tongue:

  • 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 :slight_smile:

Cheers,
Keith