Anyone have a pathfinding algorithm?
by Christian · in Torque 2D Beginner · 09/26/2013 (1:42 am) · 7 replies
Are there any readily available pathfinding algorithms that are out there that can be adapted into T2D script? I remember trying A* a few years ago with T3D, but could never get it to work.
Looking for something simple like a 8 x 10 game board with simple squares that are either 'can move on' or 'can't move on'.
Thanks,
Christian
Looking for something simple like a 8 x 10 game board with simple squares that are either 'can move on' or 'can't move on'.
Thanks,
Christian
#2
I made a custom pathfinding attempt, but it's too much for torque-script to handle.
10/05/2013 (11:16 pm)
Do you mind showing an example of your A* for your tower defense? For whatever reason every A* example I've found doesn't make any sense to me.I made a custom pathfinding attempt, but it's too much for torque-script to handle.
#3
A* won't make much sense until you sit and read a few good articles on it - preferably outside of the context of a specific engine to avoid clutter.
Do you own T2D 1.7.6? If you do there is a functioning A* demo in the <install>/games folder that you can use as a starting point for understanding how it works. Looking at that demo you'll see, however, that it relies on the t2dTileLayer object for its "grid".
Your main take-away from your script-only attempt is that this will require engine-side support for the heavy lifting - and all of that has been removed from T2D MIT. If you own T2D 1.7.6 then you could port over what you need and work from there, but all of the working versions that I have would require at least as much work to port.
Maybe I can find some time to work on getting something like this working, but my plate is pretty full....
10/06/2013 (9:14 am)
Aw man... Most of the underlying support for this was removed from the MIT version - "game-specific fluff" was cut.A* won't make much sense until you sit and read a few good articles on it - preferably outside of the context of a specific engine to avoid clutter.
Do you own T2D 1.7.6? If you do there is a functioning A* demo in the <install>/games folder that you can use as a starting point for understanding how it works. Looking at that demo you'll see, however, that it relies on the t2dTileLayer object for its "grid".
Your main take-away from your script-only attempt is that this will require engine-side support for the heavy lifting - and all of that has been removed from T2D MIT. If you own T2D 1.7.6 then you could port over what you need and work from there, but all of the working versions that I have would require at least as much work to port.
Maybe I can find some time to work on getting something like this working, but my plate is pretty full....
#5
But without the torque engine support it's too much for just script to handle.
So I may have to figure something else out for now.
10/06/2013 (8:36 pm)
I think that's what the problem is. I've read a lot of articles and examples on it, I could get at least a modified version of it working with something like c++.But without the torque engine support it's too much for just script to handle.
So I may have to figure something else out for now.
#6
Mine wasn't very powerful, but it didn't need to be - I was limiting myself to an 8x8 grid or 'battleboard.' That's still 64 nodes to track, mind you. In my case, some of those nodes were unwalkable/blocked due to specific terrain, such as rocks or trees. I actually followed the same tutorial that Danial referenced above, and used the manhattan method for most of my costs/heuristics. My implementation made two passes: One like a flood fill, where it searched out to a character's max movement rate from their current position, and returned which spaces were reachable. The second pass was made when the character selected their destination space.
The beauty of this was, the actual grunt work was already done, since the pathfinding just had to work back up the parenting chain to determine the route to that space from their destination. Then I culled that route to only include destination and turns, so I could reduce a straight 4-5 space route to only one movement node.
01/27/2014 (5:30 pm)
This is a little old of a post now, but I've built some simple A*/flood fill pathfinding even back in TGE. (And actually, I built it first in the original Neverwinter Nights game, which used 'NWScript', another sort of C+ derivative. NWN had all the 'moveTo' functionality built in, so all I had to do was keep track of node positions to build a path on a grid, then queue the actionMoveTo stuff to the actors).Mine wasn't very powerful, but it didn't need to be - I was limiting myself to an 8x8 grid or 'battleboard.' That's still 64 nodes to track, mind you. In my case, some of those nodes were unwalkable/blocked due to specific terrain, such as rocks or trees. I actually followed the same tutorial that Danial referenced above, and used the manhattan method for most of my costs/heuristics. My implementation made two passes: One like a flood fill, where it searched out to a character's max movement rate from their current position, and returned which spaces were reachable. The second pass was made when the character selected their destination space.
The beauty of this was, the actual grunt work was already done, since the pathfinding just had to work back up the parenting chain to determine the route to that space from their destination. Then I culled that route to only include destination and turns, so I could reduce a straight 4-5 space route to only one movement node.
Torque Owner Richard Ranft
Roostertail Games
The main reason that the A* demo solution from TGB won't work in T2D MIT is that there is no longer a t2dTileMap or t2dTileLayer object to build on - have to use a different structure to map your movement costs.