Determine tiles in movement range
by Joe Rossi · in Torque Game Builder · 07/29/2008 (11:39 am) · 6 replies
I'm prototyping a "tactics" strategy battle system and I need to be able to show the player what tiles his objects can move to each turn. The code I have almost works, but I have a problem. If there are tiles behind a wall or other immovable tiles, those tiles are technically in movement range. But the object wouldn't be able to make it to those tiles as they become out of their range limit when they have to maneuver around the obstacle(s). This seems to be in a lot of different games, basically every strategy wargame has it... does anyone know an algorithm or technique to do this? Maybe send out a bunch of aStar paths to every outer tile?
Here's what I have so far:
Here's what I have so far:
function calculate_range( %obj, %range )
{
//get player objects starting tile
%pTile = PathLayer.pickTile( %obj.getposition() );
%pTileX = getWord(%pTile, 0);
%pTileY = getWord(%pTile, 1);
%i = 1;
for ( %t = 1; %t < %range +1 ; %t++ )
{
//highlight tiles to the right
%tX = %pTileX + %t;
%tY = %pTileY;
//make sure this tile is "moveable"
if ( PathLayer.getTileCustomData( %tX, %tY ) == 0 ) {
//if so, highlight
// Clone a "highlight" tile and move it over the tile they can move to.
%obj = RangeHighlightTile.clone() ;
%obj.setposition( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
}
//highlight tiles to the left
%tX = %pTileX - %t;
%tY = %pTileY;
//make sure this tile is "moveable"
if ( PathLayer.getTileCustomData( %tX, %tY ) == 0 ) {
//if so, highlight
%obj = RangeHighlightTile.clone() ;
%obj.setposition( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
}
//highlight upward tiles
%tX = %pTileX;
%tY = %pTileY + %t;
if ( PathLayer.getTileCustomData( %tX, %tY ) == 0 ) {
%obj = RangeHighlightTile.clone() ;
%obj.setposition( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
}
//highlight downward tiles
%tX = %pTileX;
%tY = %pTileY - %t;
if ( PathLayer.getTileCustomData( %tX, %tY ) == 0 ) {
%obj = RangeHighlightTile.clone() ;
%obj.setposition( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
}
////------- Now fill in all tiles in between
%tX = %pTileX + %i ;
for ( %c = 1; %c < %range+1 ; %c++ ){
%tY = %pTileY + %c ;
if ( PathLayer.getTileCustomData( %tX, %tY ) == 0 ) {
%obj = RangeHighlightTile.clone() ;
%obj.setposition( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
}
}
for ( %c = 1; %c < %range+1 ; %c++ ){
%tY = %pTileY - %c ;
if ( PathLayer.getTileCustomData( %tX, %tY ) == 0 ) {
%obj = RangeHighlightTile.clone() ;
%obj.setposition( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
}
}
%tX = %pTileX - %i ;
for ( %c = 1; %c < %range+1 ; %c++ ){
%tY = %pTileY + %c ;
if ( PathLayer.getTileCustomData( %tX, %tY ) == 0 ) {
%obj = RangeHighlightTile.clone() ;
%obj.setposition( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
}
}
for ( %c = 1; %c < %range+1 ; %c++ ){
%tY = %pTileY - %c ;
if ( PathLayer.getTileCustomData( %tX, %tY ) == 0 ) {
%obj = RangeHighlightTile.clone() ;
%obj.setposition( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
}
}
%i++;
}
}
#2
07/29/2008 (1:22 pm)
Thanks James, I'll have to try something like this later tonight. I'll try your array class too, it looks pretty useful.
#3
Here's what I have in case anyone wants to mess around with it or give suggestions.
07/29/2008 (10:29 pm)
Well I 'm not sure how efficient this is considering it runs a findDestinationPath and a ton of loops on every tile potentially in range...but it seems to be working and that's all I care about for the moment :PHere's what I have in case anyone wants to mess around with it or give suggestions.
function test_path_and_highlight( %obj, %tX, %tY, %range){
if ( PathLayer.getTileCustomData( %tX, %tY ) == 0 ) {
%obj.findDestinationPath( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
if ( $object_path && %range < $object_path.getSteps() ){
// out of range, don't highlight
} else {
//show a highlight over this tile indicating it is a valid move
%obj = RangeHighlightTile.clone() ;
%obj.setposition( PathLayer.pathgrid.getTileWorldPosition( %tX SPC %tY ) );
}
}
}
function calculate_range( %obj, %range ) {
%pTile = PathLayer.pickTile( %obj.getposition() );
%pTileX = getWord(%pTile, 0);
%pTileY = getWord(%pTile, 1);
%i = 1;
for ( %t = 1; %t < %range + 1 ; %t++ )
{
%tX = %pTileX + %t;
%tY = %pTileY;
test_path_and_highlight( %obj, %tX, %tY, %range );
%tX = %pTileX - %t;
%tY = %pTileY;
test_path_and_highlight( %obj, %tX, %tY, %range );
%tX = %pTileX;
%tY = %pTileY + %t;
test_path_and_highlight( %obj, %tX, %tY, %range );
%tX = %pTileX;
%tY = %pTileY - %t;
test_path_and_highlight( %obj, %tX, %tY, %range );
%tX = %pTileX + %i ;
for ( %c = 1; %c < %range + 1 ; %c++ ){
%tY = %pTileY + %c ;
test_path_and_highlight( %obj, %tX, %tY, %range );
}
for ( %c = 1; %c < %range + 1 ; %c++ ){
%tY = %pTileY - %c ;
test_path_and_highlight( %obj, %tX, %tY, %range );
}
%tX = %pTileX - %i ;
for ( %c = 1; %c < %range + 1 ; %c++ ){
%tY = %pTileY + %c ;
test_path_and_highlight( %obj, %tX, %tY, %range );
}
for ( %c = 1; %c < %range + 1 ; %c++ ){
%tY = %pTileY - %c ;
test_path_and_highlight( %obj, %tX, %tY, %range );
}
%i++;
}
} 
#4
07/29/2008 (11:19 pm)
I've always been interested in making a tactics game in TGB, and in particular the AI for it... keep me posted on your progress! 
#5
08/01/2008 (2:06 am)
You could use Dijkstra's algorithm to calculate shortest path to every tile from given position. It is similar to the "flood fill" type approach described by James. It is also more efficient than testing path separately for every tile possibly in range.
#6
08/01/2008 (2:22 am)
Thanks Jussi, I came across that but decided to try the built in TGB functions first. If I run into performance issues I will probably rewrite the function to use that, but for now the regular TGB functions seem to be doing the trick. I actually came a long way with this over the past few days, it's all working pretty nicely :) 
Associate James Ford
Sickhead Games
You have a seed point (the tile the unit is on), and you want to know all the tiles you can get to given your "movement points". So, test each tile adjacent to the starting tile, if you can get to it without exceeding your available movement points then add each one of them (and the movement points left after moving there) to a "frontier" array. If one of those tiles is already in the frontier, set the movement points left to whichever of the two is less. If the tile is already is in "searched" array then done add it to the frontier. Then put your seed tile in the searched array.
Next iteration you do the same for each tile in the frontier, and then putting them in the searched array. Until you have no tiles in your frontier then all the tiles in the searched array are the ones you can reach!
A proper array class to keep track of tiles as you search is going to be very useful...
TScriptArray Resource