T2D A-star pathfinding stuffs
by Phil Shenk · in Torque Game Builder · 02/07/2006 (1:08 am) · 10 replies
I wrote a C++ A-star "extension" for T2D, and a script demo that shows off it's features. I submitted a resource, but it's still waiting on approval. I think I can link to it though:
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=9711
Here's a short overview:
There are two new script objects, a pathGrid2D and a path. One pathGrid can contain many paths, and it's designed so that each unit in your app that needs to find paths can have it's own path object.
The pathGrid contains all pathability data. To set it up, you assign it a tileLayer that's the size and shape of what you want to path on. The most obvious tileLayer to use is your actual game field, although you could just as easily make a special tileLayer that only contained your passablility data.
Path objects will pass back world coordinates based on this tileLayer. It's pretty simple really... you get coords along a path that avoids obsatcles on your tileLayer. All passability data is set in the tileCustomData fields. To set a tile as "blocked", set the tileCustomData to "10", to set it as "open", set it to "0" or nothing. To set an "avoidence weight" for a tile, set it to any value between 0 and 10. Higher values will be more avoided than lower values.
As I mentioned, you can get a world coordinate and/or world angle at any point on a generated path. Just pass in a distance, and you get a coord. You can do anything you like then, like use setPosition(), moveTo(), etc. Just keep getting the next coord on the path until you reach the end!
You can get postion coords or angles on a linear path, or a spline path.
Here's basically how you use it:
Of course you can get trickier, but that's the basics! Simple, huh?
There's lots of other cool stuff, like debugging symbols to show you where the nodes are being searched and the path that is found, path node pruning, and more. Check it out and let me know what you think!
www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=9711
Here's a short overview:
There are two new script objects, a pathGrid2D and a path. One pathGrid can contain many paths, and it's designed so that each unit in your app that needs to find paths can have it's own path object.
The pathGrid contains all pathability data. To set it up, you assign it a tileLayer that's the size and shape of what you want to path on. The most obvious tileLayer to use is your actual game field, although you could just as easily make a special tileLayer that only contained your passablility data.
Path objects will pass back world coordinates based on this tileLayer. It's pretty simple really... you get coords along a path that avoids obsatcles on your tileLayer. All passability data is set in the tileCustomData fields. To set a tile as "blocked", set the tileCustomData to "10", to set it as "open", set it to "0" or nothing. To set an "avoidence weight" for a tile, set it to any value between 0 and 10. Higher values will be more avoided than lower values.
As I mentioned, you can get a world coordinate and/or world angle at any point on a generated path. Just pass in a distance, and you get a coord. You can do anything you like then, like use setPosition(), moveTo(), etc. Just keep getting the next coord on the path until you reach the end!
You can get postion coords or angles on a linear path, or a spline path.
Here's basically how you use it:
// make a pathGrid
$pathGrid = = new pathGrid2d(){ scenegraph = t2DSceneGraph; } ;
//assign a tileLayer
$pathGrid.setTileLayer( $tLayer );
// make a path (pass in start and end coords)
$path1 = $pathGrid.createPath("0 0", "100 -215" );
//get coords and angle at distance 10 along path
%myCoord = $path1.getSplineWorld( 10 );
%myAngle = $path1.getSplineAngle(10);
// do the path thing
$spritey.moveTo( %myCoord );
$spritey.rotateTo( %myAngle );Of course you can get trickier, but that's the basics! Simple, huh?
There's lots of other cool stuff, like debugging symbols to show you where the nodes are being searched and the path that is found, path node pruning, and more. Check it out and let me know what you think!
About the author
#2
02/07/2006 (12:36 pm)
Looks pretty sweet!
#3
that looks really useful! Must have been a lot of work. I'll try it out later this month when I have more time to work with T2D.
02/07/2006 (1:54 pm)
Hey Phil,that looks really useful! Must have been a lot of work. I'll try it out later this month when I have more time to work with T2D.
#4
02/07/2006 (3:33 pm)
Woow. there's so much i'll never have to learn about math since i bought torque 2D...
#5
@ Michael, yeah it took me awhile. I got a little obsessive about it :)
Anyone who downloads it and gets it working, please let me know so I know if I included everything properly...
02/07/2006 (7:27 pm)
@ Jesse, yeah that's my "day job" ... glad you like the trailer! Got some more cinematic goodies for this year's E3 also ;)@ Michael, yeah it took me awhile. I got a little obsessive about it :)
Anyone who downloads it and gets it working, please let me know so I know if I included everything properly...
#6
P.S. Thanks a lot for sharing this Phil
02/07/2006 (11:46 pm)
This A* looks awesome, hopefully I'll get some time to implement it and test it out in an RTS :)P.S. Thanks a lot for sharing this Phil
#7
I'm kind of thinking out loud here, but it should work, and help out on large scale maps.
Let me know how/if it works for you!
02/08/2006 (11:03 am)
Cool Matt! For an RTS, you should be able to make a "coarse" grid and a "fine" grid. THen make one path object on the coarse grid for large scale movment, and another path object on the fine grid from the entry point on one side of the coarse grid square to the exit point on the other side.I'm kind of thinking out loud here, but it should work, and help out on large scale maps.
Let me know how/if it works for you!
#8
02/08/2006 (12:55 pm)
Very nicely done Phil!:) Thanks a whole bunch!:)
#9
I think, I know what you're talking about. Wait until I finalize my encryption library. (for a first glance http://tdn.garagegames.com/wiki/Torque_2D/Asset_Encryption).
-Michael
02/08/2006 (1:18 pm)
Quote:
@ Michael, yeah it took me awhile. I got a little obsessive about it :)
I think, I know what you're talking about. Wait until I finalize my encryption library. (for a first glance http://tdn.garagegames.com/wiki/Torque_2D/Asset_Encryption).
-Michael
#10
The transluscent shapes are the built-in debugging symbols, so you can see how broad a search is, and where pathing attempts were made, as well as the final resulting path. The green circles are open nodes at the time the destination was found, the red rectangles are closed nodes, and the blue triangles are the path nodes themselves, pointing towards their "children".
These nodes are automatically sized to fit inside the tiles the pathGrid is using. Drawing the nodes is by far the slowest thing the routine does, so you will often see a hitch with a path of any real size.
BTW, to toggle the debug symbols, you just do like:
Here's a shot of the pather working on a grid where various weighted tiles are set. The broken up rubble is equal to "1.0" ( a vertical or horzontal step is a distance of "1", so this would add a cost equal to an additional h/v step. The sold rock is equal to "2.0", the lava with the grid over it is "5.0" and the open lava is "9.0" You can see how the path attempts to avoid the more expensive tiles, and steers a nice route through the least expensive or open ones.
02/09/2006 (8:41 pm)
I finally got a site up where I can link to screenies, so I updated the resource with some screenshots of the script demo. Here's one of them:The transluscent shapes are the built-in debugging symbols, so you can see how broad a search is, and where pathing attempts were made, as well as the final resulting path. The green circles are open nodes at the time the destination was found, the red rectangles are closed nodes, and the blue triangles are the path nodes themselves, pointing towards their "children".
These nodes are automatically sized to fit inside the tiles the pathGrid is using. Drawing the nodes is by far the slowest thing the routine does, so you will often see a hitch with a path of any real size.
BTW, to toggle the debug symbols, you just do like:
$pathGrid.setDebugDraw( "true" ); // or "false"
Here's a shot of the pather working on a grid where various weighted tiles are set. The broken up rubble is equal to "1.0" ( a vertical or horzontal step is a distance of "1", so this would add a cost equal to an additional h/v step. The sold rock is equal to "2.0", the lava with the grid over it is "5.0" and the open lava is "9.0" You can see how the path attempts to avoid the more expensive tiles, and steers a nice route through the least expensive or open ones.
Torque Owner Jesse Hall
I'm going to check it out this evening!!!!
Hey are you the Phil from D2/Hellgate? I watched the latest Hellgate trailer this morning and im psyched!
- Jesse