Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (533)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  A* Pathfinding through 2d polygons  (Read 11873 times)
0 Members and 1 Guest are viewing this topic.
Offline CommanderKeith
« Posted 2008-12-12 08:37:11 »

EDIT: see StraightEdge project at http://www.java-gaming.org/topics/straightedge-2d-path-finding-and-lighting/23427/view.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  Cool

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!  Smiley Cool   

Thanks!
Keith

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




Offline Renoria

Junior Member




...


« Reply #1 - Posted 2008-12-13 01:02:53 »

wow, ticking show nodes halves the FPS...
Offline CommanderKeith
« Reply #2 - Posted 2008-12-13 03:55:31 »

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.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline CommanderKeith
« Reply #3 - Posted 2008-12-16 10:03:58 »

There's now a 'player' (a pink dot   Tongue) 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.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 743
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2008-12-16 14:53:57 »

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?

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline CommanderKeith
« Reply #5 - Posted 2008-12-17 01:56:58 »

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 Smiley

Offline CommanderKeith
« Reply #6 - Posted 2008-12-18 03:17:32 »

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

Offline phu004

JGO Coder


Medals: 4
Projects: 9
Exp: 10 years


NoSuchPersonException


« Reply #7 - Posted 2008-12-18 08:09:49 »

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.
Offline CommanderKeith
« Reply #8 - Posted 2008-12-21 08:31:15 »

New and improved version, let me know what you think:

http://www.freewebs.com/commanderkeith/PathFinder/AStarPathFinder.jnlp

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?

Thanks dude  Cool  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.

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.




Offline Hotgamerz r sik

Junior Newbie





« Reply #9 - Posted 2008-12-21 09:50:49 »

hey  Cool
i looked at your pathfinder and i was wondering what you're going to apply it to?  Huh
some kind of arcade game or maybe something else?

Cheers bro Grin

Our birthdays are but feathers on the broad wings of time...
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Hotgamerz r sik

Junior Newbie





« Reply #10 - Posted 2008-12-21 10:07:30 »

Bro!!!
i played your game and it is gnarly!!!  Shocked
like seriously gnarly Grin
catcha on the flip side bro

wooooo!!!!!!!!!!!!!!!!1
 Cheesy Sad Cool

Our birthdays are but feathers on the broad wings of time...
Offline phu004

JGO Coder


Medals: 4
Projects: 9
Exp: 10 years


NoSuchPersonException


« Reply #11 - Posted 2008-12-21 10:56:59 »

Quote
try out this new version which has a maze. And thanks for the idea!

Very well done, it is time to put this on a real game application Smiley

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.
Offline CommanderKeith
« Reply #12 - Posted 2008-12-22 02:30:51 »

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 Smiley

PS: Here are some mock-ups of the rpg i'm working on:
http://www.java-gaming.org/topics/2d-vector-graphics-style/19237/view.html

Offline Jono
« Reply #13 - Posted 2009-01-08 09:21:21 »

I just had a look at your A-star and noticed another optimisation that can be made. Grin

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


Offline CommanderKeith
« Reply #14 - Posted 2009-01-08 14:17:56 »

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

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?!?

Offline Jono
« Reply #15 - Posted 2009-01-08 20:48:27 »

Nice one Jono! Thanks a lot, I can't believe I overlooked that and wasn't even using A* at all!  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.
My pleasure! It's looking like a pretty neat bit of code, so it's nice to be able to help.

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  Cool
Oh right, I see what you mean. I misread how that recursion was working. Grin

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.

Maybe the next feature that should be added is moving obstacles or the insertion of obstacles on the fly?!?
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).
Offline CommanderKeith
« Reply #16 - Posted 2009-01-10 04:13:01 »

Good idea, i'll add that HashMap in  Smiley 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?

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

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?

Offline Jono
« Reply #17 - Posted 2009-01-10 05:23:09 »

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?
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?
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.
Offline CommanderKeith
« Reply #18 - Posted 2009-01-10 07:21:58 »

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.

Offline CommanderKeith
« Reply #19 - Posted 2009-04-23 06:23:15 »

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

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  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  Smiley

Cheers,
Keith

Offline Markus_Persson

JGO Wizard


Medals: 14
Projects: 19


Mojang Specifications


« Reply #20 - Posted 2009-04-23 09:35:17 »

Wow, nice. Impressive. =)

Play Minecraft!
Offline CommanderKeith
« Reply #21 - Posted 2009-04-23 09:40:16 »

Thanks!  Grin

Offline mh114

Junior Member





« Reply #22 - Posted 2009-04-23 10:14:14 »

Very interesting! I tried your latest demo, it seemed very robust. Smiley 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! Cheesy Hard to think of a subject that's "scientific" enough.. Tongue

Anyway, keep up the good work! Smiley

Offline CommanderKeith
« Reply #23 - Posted 2009-04-23 10:41:41 »

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


Offline mh114

Junior Member





« Reply #24 - Posted 2009-04-23 10:54:17 »

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

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.

Offline CommanderKeith
« Reply #25 - Posted 2009-07-08 04:38:49 »

New updates:
- dynamic obstacle addition and removal (removal is much slower than addition). Drag the right mouse button to add rectangle obstacles, right click to remove.
- improved scalability through storing objects in a grid. Also you can now specify the maximum distance to connect nodes, speeding up mesh creation and pathfinding speed. Maps can now be very big, try the gigantic maze! Cool
- faster path-finding by using a map as opposed to a list which eliminates the expensive openList.contains(x) method (thanks Jono!  Wink).

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!



Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

pw (25 views)
2014-07-24 01:59:36

Riven (25 views)
2014-07-23 21:16:32

Riven (19 views)
2014-07-23 21:07:15

Riven (22 views)
2014-07-23 20:56:16

ctomni231 (51 views)
2014-07-18 06:55:21

Zero Volt (46 views)
2014-07-17 23:47:54

danieldean (37 views)
2014-07-17 23:41:23

MustardPeter (40 views)
2014-07-16 23:30:00

Cero (56 views)
2014-07-16 00:42:17

Riven (55 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!