A* Pathfinding through 2d polygons

Shared Code
#21

Wow, nice. Impressive. =)

#22

Thanks! ;D

#23

Very interesting! I tried your latest demo, it seemed very robust. :slight_smile: 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! :smiley: Hard to think of a subject that’s “scientific” enough… :stuck_out_tongue:

Anyway, keep up the good work! :slight_smile:

#24

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…

#25

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.

#26

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! 8)
  • faster path-finding by using a map as opposed to a list which eliminates the expensive openList.contains(x) method (thanks Jono! ;)).

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