Wow, nice. Impressive. =)
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.
- 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!