Pathing Work
by Chris · in Torque Game Builder · 11/26/2005 (10:51 pm) · 2 replies
Hello everyone,
I have just finished a basic c++ a* pathfinding program to learn how it works. I have started to plan out how I want to work with that to make a Pathing utility. What I am currently thinking is to have it be a utility class. You would create an instance of it, then give it some data, like collision masks you want it to consider as non walkable, your target position, and your starting position. It would then find the path and store that. Then using the another function you would take out the next position you should head to. The actual moving of an object would be done via script. Once you reach a set position you would then ask for the next position you need to go to. This would continue working until you reach the end position or if you change the end position and create a new path (incase you want to follow an object).
That was my original idea but after thinking about it, if I have a bunch of collision masks that I want to consider as nonwalkable. How would I go about learning what is at a specific location. So I decided to change my initial idea to adding into t2dSceneObject. This would give everything with a parent of t2dSceneObject the ability to use pathfinding. I like the idea of adding it to the t2dSceneObject class as I think it would be a lot nicer and easier to use. The problem is I still dont know how to go about getting the data as to what is at a specific area.
For the t2dSceneObject I was thinking of creating a matrix based off the objects size. The size of the object would determine the size of a node. Then if I could somehow use pickRect() for the sceneGraph that the object is attached to I could get a list of what objects are there, and then check the masks to see if I can or cant move to that area. From there I would continue with my open/closed list and once I reached the target (or I find that its impossible to reach the target) I would create a list of positions. Then have some onReachNode or something similar type event that can be overloaded in torque script. By default it would make the object move to the next node right away.
Anyway If you can help me basically to sum that up I am looking for a way to determine if, in a certain area on the scenegraph of any t2dSceneObject, there are any objects that the sceneObject could collide with. IE: Tilemaps, other sceneObjects.
Lux
I have just finished a basic c++ a* pathfinding program to learn how it works. I have started to plan out how I want to work with that to make a Pathing utility. What I am currently thinking is to have it be a utility class. You would create an instance of it, then give it some data, like collision masks you want it to consider as non walkable, your target position, and your starting position. It would then find the path and store that. Then using the another function you would take out the next position you should head to. The actual moving of an object would be done via script. Once you reach a set position you would then ask for the next position you need to go to. This would continue working until you reach the end position or if you change the end position and create a new path (incase you want to follow an object).
That was my original idea but after thinking about it, if I have a bunch of collision masks that I want to consider as nonwalkable. How would I go about learning what is at a specific location. So I decided to change my initial idea to adding into t2dSceneObject. This would give everything with a parent of t2dSceneObject the ability to use pathfinding. I like the idea of adding it to the t2dSceneObject class as I think it would be a lot nicer and easier to use. The problem is I still dont know how to go about getting the data as to what is at a specific area.
For the t2dSceneObject I was thinking of creating a matrix based off the objects size. The size of the object would determine the size of a node. Then if I could somehow use pickRect() for the sceneGraph that the object is attached to I could get a list of what objects are there, and then check the masks to see if I can or cant move to that area. From there I would continue with my open/closed list and once I reached the target (or I find that its impossible to reach the target) I would create a list of positions. Then have some onReachNode or something similar type event that can be overloaded in torque script. By default it would make the object move to the next node right away.
Anyway If you can help me basically to sum that up I am looking for a way to determine if, in a certain area on the scenegraph of any t2dSceneObject, there are any objects that the sceneObject could collide with. IE: Tilemaps, other sceneObjects.
Lux
About the author
#2
That actually sounds like a good idea. If I can get the scenegraph a t2dsceneobject is on then from there you could find the map and layers. From there have a list of args something similar to (collidemap?, collidesprite?). It would use the current information on what to collide with to work. If no collision is active passing (true, true) wouldn't do anything but if the object is set to collide with a tile map and you want to take those into consideration then passing (true, false) would work. Again if you where to pass true to either of those two args if something is considered "nonwalkable" then it the object must already be able to collide with it.
Still using the size of the sprite as a way to make a grid of nodes you could then make a path that seems realistic. If you base it off tilelayers and have a larger then normal object how are you going to determine if that larger then normal object can fight through a certain space? Same can be said for something of smaller size.
Your idea of using linkPoints as a way to keep information is really cool. That also got me thinking about moving objects. If I where to do all this it would have to be updated when an object moved (like if the tilemap scrolls). In this case i couldn't really use worldposition as a way to work with things. I guess I still have some things to think about.
Lux
11/27/2005 (11:47 am)
Phil,That actually sounds like a good idea. If I can get the scenegraph a t2dsceneobject is on then from there you could find the map and layers. From there have a list of args something similar to (collidemap?, collidesprite?). It would use the current information on what to collide with to work. If no collision is active passing (true, true) wouldn't do anything but if the object is set to collide with a tile map and you want to take those into consideration then passing (true, false) would work. Again if you where to pass true to either of those two args if something is considered "nonwalkable" then it the object must already be able to collide with it.
Still using the size of the sprite as a way to make a grid of nodes you could then make a path that seems realistic. If you base it off tilelayers and have a larger then normal object how are you going to determine if that larger then normal object can fight through a certain space? Same can be said for something of smaller size.
Your idea of using linkPoints as a way to keep information is really cool. That also got me thinking about moving objects. If I where to do all this it would have to be updated when an object moved (like if the tilemap scrolls). In this case i couldn't really use worldposition as a way to work with things. I guess I still have some things to think about.
Lux
Associate Phil Shenk
I'm also working on a C++ a* pather. My approach is to make the "pather" an object that gets passed a tileLayer, and start and end coords (as tile indexes). The path gets generated like "$path.createPath". THen, like in your first idea, the user gets the path steps like "$path.getPath(%step)", which will return the coord of the path node at %step. The coord is passed back as a local coord on the tileLayer (-1, -1 -> 1, 1)... this is so that I can get the path nodes even if the tileLayer is moving, scaled, scrolling or rotating.
For collision info, I'm using the custom attributes field of tileLayer. Baisically for now, for each tile you set "1" for blocking, and "0" for passable. Eventually, this will be a bit mask so you can have different objects be able to pass where others can't.
I figured basing the thing on a tileLayer made sense since a lot of people are making tile-based games, and that's where the level data will be anyway. It's pretty easy to use... when you set a wall tile, for example, you just set the custom attributes to also be "1". If you remove the wall tile in-game, then you just have to set that tile's custom attibute to "0" and regen the path.
Caveats are:
-the pathing tileLayer can't be repeating, of course.
-it won't work (for now), if there are other custom attibutes. I may eventually parse this to find the pathing info, or I might just add new members to the bit that holds custom attributes (like mPathAttributes or something).
-Currently, the way to get a world position coord from the path step is to make a linkPoint on the tileLayer and get the coord from that. This works pretty well actually, since the linkPoints will update if the tileLayer is moving or rotating. I ussually make two linkPoints, one for the path node the unit is leaving, and one for the one it's going to, then I tween the unit pos between these linkPoint "nodes". The system is flexible enough that you can set your unit's pos in other ways though. I might eventually add some of this tweening info to the C++ side, not sure.
Anyway, that's my approach. I suppose another more generic approach would be to make a custom C++ "grid" object, maybe that populates itself by checking actual collision polys in the game? You'd have to re-set the grid anytime the collision info chaged though, and that might get expensive. Funny that the a* part is the easiest part. Getting all the other things in place is the hard bit :)