Path finding
by Gavin Beard · in Torque Game Builder · 03/08/2008 (4:00 am) · 4 replies
Hi,
I'm not great with path finding, but am looking to use A* on a tile based map, however there is a specific thing I need to do. When I select a unit within the map I need it to display all possible tiles where the unit could move to such as in this image:
GREEN is the unit. RED is all possible destination tiles
I am presuming A* would be the best possible solution but was hoping maybe someone could point me the the right direction)
Big Thanks
I'm not great with path finding, but am looking to use A* on a tile based map, however there is a specific thing I need to do. When I select a unit within the map I need it to display all possible tiles where the unit could move to such as in this image:
GREEN is the unit. RED is all possible destination tiles
I am presuming A* would be the best possible solution but was hoping maybe someone could point me the the right direction)
Big Thanks
#2
03/09/2008 (2:00 pm)
Looking into this a bit further i am thinking a Breadth first algorithm would be better? any one tried this in TGB 
#3
In any case, to provide a summary of how I did it:
First, create an abstract grid that is the same size as the maximum potential move range of the unit in question. Assume that all tiles cost 1 (or less, if movement can cost less in your situation). So, by example, if a unit has 4 movement points during that turn, create a 5x5 grid.
Next, iterate over each tile location in the grid assuming that each tile, in its turn, is the goal location for the unit. Run a path algorithm using the start and goal tiles to see if a path exists. While you do, count the actual movement cost involved--you no longer assume the lowest potential cost for your path check.
A* works just grand because it tends to locate the optimal path, cutting down the amount of processing you need to engage. Breadth first would be less efficient, I think, even for this.
Additionally, you'll want to start with goal tiles furthest out. Why? In your invisible/abstract grid, you mark any tile that has been found accessible as such--that way you don't have to run your path check if it has previously been uncovered as accessible as part of a path to another tile location. The result is that you'll rarely have to run path checks on tiles nearest your start tile (they are generally known to be accessible, or not, fairly early).
There are a few solid optimizations that could be made, though I never got that far myself as it was just for a prototype. Still, once you are done, you'll have a "movement map" of all potentially accessible tiles for that unit.
I stored the move map on the unit and regenerated a new move map each time they stepped to a new tile--in my case, the movement cost of tiles on the map could change so it was most efficient for me to check each time a unit moved.
You could instead store the map on the tile so that future units could use it as well, assuming they had the same number of move points. It could also be used to "pre-fill" larger, or completely act as a reference for smaller ones (when a unit has less movement available from the tile).
Alternatively, if you know the maximum amount of moves a unit could ever make, when you load your level you could front-load the processing by building move maps for each tile, storing the maps on the tile itself and just calling it up whenever you need to know the possible moves a unit can make from any specific tile.
That would also offer the advantage of having to do no path checking during game play, but would present a lot of pre-processing (and wasted processing on maps that will never be referenced during game play).
Maybe that is worthwhile or useful for smaller maps but should probably be avoided otherwise. It could provide some nifty secondary advantages if you wanted to use those generated maps for some other game play element/mechanic (making them "range" maps rather than necessarily "move" maps).
03/18/2008 (6:56 am)
I did something like this for a prototype a little while back, though I wasn't using TGB tile maps. As a side note, I did it entirely in TS and was able to get good results for a complimentary A* styled algorithm, albeit with a fair bit of tweaking. Having said that, on large tile maps it wouldn't be sensible to use TS, deferring to C++ in its stead.In any case, to provide a summary of how I did it:
First, create an abstract grid that is the same size as the maximum potential move range of the unit in question. Assume that all tiles cost 1 (or less, if movement can cost less in your situation). So, by example, if a unit has 4 movement points during that turn, create a 5x5 grid.
Next, iterate over each tile location in the grid assuming that each tile, in its turn, is the goal location for the unit. Run a path algorithm using the start and goal tiles to see if a path exists. While you do, count the actual movement cost involved--you no longer assume the lowest potential cost for your path check.
A* works just grand because it tends to locate the optimal path, cutting down the amount of processing you need to engage. Breadth first would be less efficient, I think, even for this.
Additionally, you'll want to start with goal tiles furthest out. Why? In your invisible/abstract grid, you mark any tile that has been found accessible as such--that way you don't have to run your path check if it has previously been uncovered as accessible as part of a path to another tile location. The result is that you'll rarely have to run path checks on tiles nearest your start tile (they are generally known to be accessible, or not, fairly early).
There are a few solid optimizations that could be made, though I never got that far myself as it was just for a prototype. Still, once you are done, you'll have a "movement map" of all potentially accessible tiles for that unit.
I stored the move map on the unit and regenerated a new move map each time they stepped to a new tile--in my case, the movement cost of tiles on the map could change so it was most efficient for me to check each time a unit moved.
You could instead store the map on the tile so that future units could use it as well, assuming they had the same number of move points. It could also be used to "pre-fill" larger, or completely act as a reference for smaller ones (when a unit has less movement available from the tile).
Alternatively, if you know the maximum amount of moves a unit could ever make, when you load your level you could front-load the processing by building move maps for each tile, storing the maps on the tile itself and just calling it up whenever you need to know the possible moves a unit can make from any specific tile.
That would also offer the advantage of having to do no path checking during game play, but would present a lot of pre-processing (and wasted processing on maps that will never be referenced during game play).
Maybe that is worthwhile or useful for smaller maps but should probably be avoided otherwise. It could provide some nifty secondary advantages if you wanted to use those generated maps for some other game play element/mechanic (making them "range" maps rather than necessarily "move" maps).
#4
I will look at he info here and see where it leads, i shall report back soon.
03/20/2008 (1:19 pm)
Wow, thanks alot for the info.I will look at he info here and see where it leads, i shall report back soon.
Associate Phillip O'Shea
Violent Tulip
That resource implements A* into TGB provided you have TGB Pro.