T2d A (star) pathfinding almost a reality.
by Rodney Rindels - Torqued · 06/03/2006 (9:56 pm) · 5 comments
Update: Its ugly.. but its on TDN! tdn.garagegames.com/wiki/TGB/Source/Pathfinding - enjoy!
I realized early on that I would have to build better pathfinding if I were to have a truly professional gameplay, my quasi top down * isometric perspective + some 2D scenes. The game i'm working on needed 8 way movement capability while pathfinding in a more natural way instead of the moveTo() angle based function that can't "walk" around items, and didn't look at natural or be able to keep state on direction player is heading in, etc. So .. I started working on a c++ rendition of the typical A* type pathfinding, once I felt that was working quasi-ok, I ported to torqueScript natively to try and see how bad performance would be impacted so I could possibly use as a TDN resource or for the Binary Users that will soon be members of our community. Lets just say, ouch, without Binary Heaps or true arrays (* remember I want Binary users to be able to possibly use this, so no C++ modifications could be used). I implemented a rough but fairly accurate version in native TS.
It basically implements a
this will move an object along an Astar Path %path is created using
what is %path? %path is just a ScriptObject, each node along the path is a ScriptObject, etc.
The performance is "ok".. It could probably be optimized somewhat.
**Fixed: I noticed about a 1 second delay in the pathfinding when moving 300 - 400 world units away.
This delay seems to be in actual object creation. moving a 8x8 sprite object from "0 0" to "300 300" is alot of nodes.. 2K plus in some instances, so .. thats probably the issue.
**Fixed: Its still not ready for primetime, because I have to finish implementing some collission costs at objects found at the intersects. But here are a few screenshots showing the directional finding in action.
**Fixed: You'll notice a bobble at the end of each path, thats because I have a bug in the knowing when the hell to stop portion of the pathfinding. I hope to have this completed soon ,and be able to share it with the T2D community..
Update: Fixed the bobble issue. and have it working pretty sweet now...
Update: Fixed most of the performance bottlenecks. It now works fine in 1000's of world coordinates paths
Update: Object Avoidance works and seems to be pretty stable...
EyeCandy
Initial Tests
After Fixing Bobbling
After Adding Object Avoidance Costing
I realized early on that I would have to build better pathfinding if I were to have a truly professional gameplay, my quasi top down * isometric perspective + some 2D scenes. The game i'm working on needed 8 way movement capability while pathfinding in a more natural way instead of the moveTo() angle based function that can't "walk" around items, and didn't look at natural or be able to keep state on direction player is heading in, etc. So .. I started working on a c++ rendition of the typical A* type pathfinding, once I felt that was working quasi-ok, I ported to torqueScript natively to try and see how bad performance would be impacted so I could possibly use as a TDN resource or for the Binary Users that will soon be members of our community. Lets just say, ouch, without Binary Heaps or true arrays (* remember I want Binary users to be able to possibly use this, so no C++ modifications could be used). I implemented a rough but fairly accurate version in native TS.
It basically implements a
moveToAstar(%obj,%path)
this will move an object along an Astar Path %path is created using
%path = findPath(%obj,%toVector);
what is %path? %path is just a ScriptObject, each node along the path is a ScriptObject, etc.
The performance is "ok".. It could probably be optimized somewhat.
**Fixed: I noticed about a 1 second delay in the pathfinding when moving 300 - 400 world units away.
This delay seems to be in actual object creation. moving a 8x8 sprite object from "0 0" to "300 300" is alot of nodes.. 2K plus in some instances, so .. thats probably the issue.
**Fixed: Its still not ready for primetime, because I have to finish implementing some collission costs at objects found at the intersects. But here are a few screenshots showing the directional finding in action.
**Fixed: You'll notice a bobble at the end of each path, thats because I have a bug in the knowing when the hell to stop portion of the pathfinding. I hope to have this completed soon ,and be able to share it with the T2D community..
Update: Fixed the bobble issue. and have it working pretty sweet now...
Update: Fixed most of the performance bottlenecks. It now works fine in 1000's of world coordinates paths
Update: Object Avoidance works and seems to be pretty stable...
EyeCandy
Initial Tests
After Fixing Bobbling
After Adding Object Avoidance Costing
About the author
#2
06/05/2006 (12:32 am)
Very interesting. Looking forward to when you let us mortals play with it :)
#3
tdn.garagegames.com/wiki/TGB/Source/Pathfinding
I'm a little embarrased by it, but its there as a logic example if nothing else.....
06/05/2006 (5:09 am)
I finally got off my ass, cleaned up a few things, and went ahead and posted it to TDN..tdn.garagegames.com/wiki/TGB/Source/Pathfinding
I'm a little embarrased by it, but its there as a logic example if nothing else.....
#4
I mean, you actually used the words "A(*)" in a sentence that made sense!
Beside, if you haven't written 20,000 lines of financial calculation code, in one large function, using variables called A, AA, AAA, AAAB, AAAC... never actually assigning anything to any variable more than once.. then your code is beautiful :)
(Note: code hinted at in example actually existed.)
06/05/2006 (5:26 am)
Never be embarrassed by your code!I mean, you actually used the words "A(*)" in a sentence that made sense!
Beside, if you haven't written 20,000 lines of financial calculation code, in one large function, using variables called A, AA, AAA, AAAB, AAAC... never actually assigning anything to any variable more than once.. then your code is beautiful :)
(Note: code hinted at in example actually existed.)
#5
06/05/2006 (5:29 am)
Lol yep, was a maintenance coder for a bank for a short stint... I still have nightmares!
Employee Matthew Langley