• 1

• 43
• 4

Below are the bunch of functions which I wrote to determine paths between give coordinates of a square tile-based game. It permits paths between tiles in 4 directions (i.e. not 8 directions/diagonal paths).

It can be pretty resource-intensive when the path is long, especially if the target is unreachable (on large maps (~10,000 tiles) it literally causes Firefox to hang for several seconds in this case).

So far I'm very happy with the results it yields but not so much its performance. One aspect I'd like to try to improve is the repeated sorting of the closed_tile array.

// Some example variables:
var terrain_tile_types = [
 ["",[0,0,0,0]], // Not really a tile (invisible/unselectable)
 ["Flat grass",[1,0,0,1]], // ID: 1
 ["Water",[0,1,1,1]] // ID: 2
];
var unit_types = [
 ["Unit type 1",[10,0.1,null],0,1]
];
var terrain_map = [[2,2,2,2,2],[1,1,1,2,2],[1,1,2,2,2],[1,2,2,1,1]];
function calc_h(start,end){ // start,end: [locI,locJ]
 // Estimates the cost of moving from given tile to end
 return Math.abs(end[0]-start[0])+Math.abs(end[1]-start[1]);
}
function is_in_array(needleCoords,haystack){
 // Where haystack is an array of randomly-arranged coordinate arrays, (e.g. [[1,1,28.72,...],[0,2,43.2,...]])
 // And needleCoords is an array with coords to find (e.g. [0,1]).
 // Returns index if found
 
 for(n in haystack){
 if(haystack[n][0]==needleCoords[0] && haystack[n][1]==needleCoords[1]) return n;
 }
 return false;
}
function reconstruct_path(end,closed_tiles){
 var path=[];
 var current_tile=closed_tiles[is_in_array(end,closed_tiles)];
 
 while(current_tile[5][0]!=current_tile[0] || current_tile[5][1]!=current_tile[1]){
 path=path.concat([ [current_tile[0],current_tile[1]] ]);
 current_tile=closed_tiles[is_in_array(current_tile[5],closed_tiles)];
 }
 path.reverse();
 return path;
}
function pathfind(start,end,mobility_type,substitute_map){
 // start = start coords array, end = end coords array
 // mobility_type = determines which type of tiles are "walkable" based on the moving unit's type - will be an integer index o
 // substitute_map = optional map array to use instead of the default (terrain_map)
 
 pathfind_map = typeof substitute_map !== 'undefined' ? substitute_map : terrain_map;
 mobility_type = typeof mobility_type !== 'undefined' ? mobility_type : 0;
 // Able to walk on end tile? If not return false
 if(terrain_tile_types[terrain_map[end[0]][end[1]]][1][mobility_type]!=1) return false;
 // Validate start and end arrays
 if(start.length!=2 || end.length!=2
 || start[0]!==+start[0] || start[0]!==(start[0]|0)
 || start[1]!==+start[1] || start[1]!==(start[1]|0)
 || end[0]!==+end[0] || end[0]!==(end[0]|0)
 || end[1]!==+end[1] || end[1]!==(end[1]|0)) return false;
 
// Add g, h and f values (and parent = start)
start=start.concat([0,calc_h(start,end)]);
start=start.concat([(start[2]+start[3])]);
start=start.concat([start]);
 
var open_tiles=[start]; // Structure: [[locI,locJ,g,h,f,[parent]]]
var closed_tiles=[]; // Structure: [[locI,locJ,g,h,f,[parent]]]
while(open_tiles.length>0){
 // Order open_tiles by f value (smallest)
 open_tiles.sort(function(a,b){return a[4]-b[4];});
 
 // Add tile to closed list
 closed_tiles[closed_tiles.length]=open_tiles[0];
 if(end[0]==open_tiles[0][0] && end[1]==open_tiles[0][1]){
 // Path found, finish.
 return reconstruct_path(end,closed_tiles);
 }
 
 // 4-surrounding tiles:
 var surrounding_tiles=[[open_tiles[0][0]-1,open_tiles[0][1],false],[open_tiles[0][0],open_tiles[0][1]-1,false],[open_tiles[0][0],open_tiles[0][1]+1,false],[open_tiles[0][0]+1,open_tiles[0][1],false]];
 
 for (q in surrounding_tiles){
 if(pathfind_map[surrounding_tiles[q][0]]!=undefined && pathfind_map[surrounding_tiles[q][0]][surrounding_tiles[q][1]]!=undefined && terrain_tile_types[pathfind_map[surrounding_tiles[q][0]][surrounding_tiles[q][1]]]!=undefined && is_in_array(surrounding_tiles[q],closed_tiles)===false){
 
 // Not able to cross this terrain?
 if(terrain_tile_types[pathfind_map[surrounding_tiles[q][0]][surrounding_tiles[q][1]]][1][mobility_type]!=1) continue;
 
 var status=is_in_array(surrounding_tiles[q],open_tiles);
 if(status!==false){
 // Tile already found in open list
 if((open_tiles[0][2]+(surrounding_tiles[2]?14:10))<open_tiles[status][2]){
 // This new path is better. Update open list entry
 open_tiles[status][2]=(open_tiles[0][2]+(surrounding_tiles[2]?14:10));
 open_tiles[status][4]=open_tiles[status][2]+open_tiles[status][3];
 open_tiles[status][5]=[open_tiles[0][0],open_tiles[0][1]];
 }
 }else{
 // Tile wasn't found in open list, so add it now
 var tile_info_to_add=[surrounding_tiles[q][0],surrounding_tiles[q][1],(open_tiles[0][2]+(surrounding_tiles[2]?14:10)),calc_h(surrounding_tiles[q],end)];
 tile_info_to_add=tile_info_to_add.concat([tile_info_to_add[2]+tile_info_to_add[3],[open_tiles[0][0],open_tiles[0][1]]]);
 open_tiles=open_tiles.concat([tile_info_to_add]);
 }
 }
 }
 // Remove tile from list (shift removes first element from array)
 open_tiles.shift();
 
 }
 // No valid path found from start to end
 return false;
}

Here's a question I asked earlier about optimising the is_in_array() function: http://stackoverflow.com/questions/11300249/javascript-return-position-index-of-matched-array-within-array