by date
T2d A (star) pathfinding almost a reality.
T2d A (star) pathfinding almost a reality.
| Name: | Rodney Rindels - Torqued |  |
|---|---|---|
| Date Posted: | Jun 03, 2006 | |
| Rating: |  5.0 out of 5 | |
| Public: | YES | |
| Comments: | YES | |
| RSS Feed: |  or Subscribe with  . | |
| Profile Page: | View profile page for Rodney Rindels - Torqued |
Blog post
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
Recent Blog Posts
| List: | 11/27/06 - Tri Poker Plus 09/17/06 - Lion, and Tigers and Lawyers , ohh my! 07/18/06 - TGB Memory Game Demo 06/12/06 - Capicu - Street Rules Dominoes 06/08/06 - TGB - Game in a Day 06/03/06 - T2d A (star) pathfinding almost a reality. 05/31/06 - T2D Pause Screen |
|---|
Submit your own resources!| Matthew Langley (Jun 03, 2006 at 22:44 GMT) |
| Chris Schirlinger (Jun 05, 2006 at 00:32 GMT) Resource Rating: 5 |
| Rodney Rindels - Torqued (Jun 05, 2006 at 05:09 GMT) |
tdn.garagegames.com/wiki/TGB/Source/Pathfinding
I'm a little embarrased by it, but its there as a logic example if nothing else.....
| Chris Schirlinger (Jun 05, 2006 at 05:26 GMT) Resource Rating: 5 |
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.)
| Rodney Rindels - Torqued (Jun 05, 2006 at 05:29 GMT) |
You must be a member and be logged in to either append comments or rate this resource.
