patternjavascriptMinor
Javascript A* pathfinding function for tile-based game optimisation
Viewed 0 times
pathfindingjavascriptfunctionoptimisationgameforbasedtile
Problem
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, en
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, en
Solution
I have made the
Reduce comparisons by navigating a 1 dimensional model of the map instead.
When you call
For the terrain_map provided and a mobility index of 0, this would be the following array:
(spacing to demonstrate relationship to terrain_map)
With this array you can start with any coordinate
Once you have that you can move up or down by adding/subtracting
Since this array is a padded version of the map, you never have to worry about wrapping around because you cannot move to these fake coordinates that make up the padding.
This may or may not wind up actually being faster (it depends on how big your maps actually are and how easy the set of paths were to compute in the first place).
code:
In
and changed
Instead of
I have no idea how big of an affect this will have (if any), but I think it would be faster to just splice out the smallest element rather than sort every time (again depends on size of your map). In the meantime there is no benefit to having
The completely raw untested result:
```
// 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 = [ // [x][y] = key to terrain_tyle_types
[2,2,2,2,2],
[1,1,1,2,2],
[1,1,2,2,2],
[1,2,2,1,1]
];
function coord_to_int(coord, map) {
return (coord[0] + 1) * (map[0].length + 2) + (coord[1] + 1);
}
function int_to_coord(i, map) {
return [
Math.floor((i - 1) / (map[0].length + 2) - 1),
(i - 1) % (map[0].length + 2)
];
}
function newArray(size, value) {
var arr = [];
while (size--) {
arr.push(value);
}
return arr;
}
function generate_mobility_tiles(mobility, map) {
var i,
j,
ii = map.length,
jj = map[0].length,
o = newArray((ii + 2) * (jj + 2), false);
for (i = 0; i 0) {
// remove smallest tile, faster than sort+shift?
f = Number.MAX_VALUE;
open_ind
current_tile arrays into objects so that it this is easier to edit. I doubt it makes enough of a difference to be noticeable. That is, I replaced [[i, j], g, h, f, [parent]] with a structure {i, g, h, f, p}. It may be worthwhile to change them back though.Reduce comparisons by navigating a 1 dimensional model of the map instead.
When you call
pathfind you can generate a set of mobility_tiles for a given map.For the terrain_map provided and a mobility index of 0, this would be the following array:
[
0, 0,0,0,0,0 ,0,
0, 0,0,0,0,0 ,0,
0, 1,1,1,0,0 ,0,
0, 1,1,0,0,0 ,0,
0, 1,0,0,1,1 ,0,
0, 0,0,0,0,0 ,0
](spacing to demonstrate relationship to terrain_map)
With this array you can start with any coordinate
[i,j] and convert it into an index in this array via a the coord_to_int function and back with its inverse function.Once you have that you can move up or down by adding/subtracting
map[0].length + 2 and left or right by adding/subtracting 1 from the index.Since this array is a padded version of the map, you never have to worry about wrapping around because you cannot move to these fake coordinates that make up the padding.
This may or may not wind up actually being faster (it depends on how big your maps actually are and how easy the set of paths were to compute in the first place).
code:
function coord_to_int(coord, map) {
return (coord[0] + 1) * (map[0].length + 2) + (coord[1] + 1);
}
function int_to_coord(i, map) {
return [
Math.floor((i - 1) / (map[0].length + 2) - 1),
(i - 1) % (map[0].length + 2)
];
}
function newArray(size, value) {
var arr=[];
while(size--) {
arr.push(value);
}
return arr;
}
function generate_mobility_tiles(mobility, map) {
var i,
j,
ii = map.length,
jj = map[0].length,
o = newArray((ii + 2) * (jj + 2), false);
for (i = 0; i < ii; i += 1) {
for (j = 0; j < jj; j += 1) {
if(terrain_tile_types[map[i][j]][1][mobility]) {
o[coord_to_int([i, j]] = true;
}
}
}
return o;
}In
pathfind://near start
var mobility_tiles = generate_mobility_tiles(mobility_type, pathfind_map),
down = pathfind_map[0].length+2,
right = 1;
closed_tiles = new Array((pathfind_map.length + 2) * down); // sparse array matching mobility_tiles
//later
var surrounding = [
[current_tile.i + down, false],
[current_tile.i - down, false],
[current_tile.i + right, false],
[current_tile.i - right, false]
];
surrounding.forEach(function (t) { //IE < 9 compat is up to you
if (!mobility_tiles[t[0]] || //cannot move here
closed_tiles[t[0]]) { //visited already
return;
}
var index = open_tiles.map(function (x) { return x.i; }).indexOf(t[0]);
...and changed
reconstruct_path accordingly (and remove is_in_array).Instead of
sort and shift, splice out the smallest elementI have no idea how big of an affect this will have (if any), but I think it would be faster to just splice out the smallest element rather than sort every time (again depends on size of your map). In the meantime there is no benefit to having
open_tiles.shift() at the end of the loop rather than right after the sort and caching the lookup into a local variable:while (open_tiles.length > 0) {
// remove smallest tile, faster than sort+shift?
f = Number.MAX_VALUE;
open_index = open_tiles.length;
smallest = 0;
while (open_index--) {
if (f > open_tiles[open_index].f) {
f = open_tiles[open_index].f;
smallest = open_index;
}
}
current_tile = open_tiles.splice(smallest, 1);The completely raw untested result:
```
// 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 = [ // [x][y] = key to terrain_tyle_types
[2,2,2,2,2],
[1,1,1,2,2],
[1,1,2,2,2],
[1,2,2,1,1]
];
function coord_to_int(coord, map) {
return (coord[0] + 1) * (map[0].length + 2) + (coord[1] + 1);
}
function int_to_coord(i, map) {
return [
Math.floor((i - 1) / (map[0].length + 2) - 1),
(i - 1) % (map[0].length + 2)
];
}
function newArray(size, value) {
var arr = [];
while (size--) {
arr.push(value);
}
return arr;
}
function generate_mobility_tiles(mobility, map) {
var i,
j,
ii = map.length,
jj = map[0].length,
o = newArray((ii + 2) * (jj + 2), false);
for (i = 0; i 0) {
// remove smallest tile, faster than sort+shift?
f = Number.MAX_VALUE;
open_ind
Code Snippets
[
0, 0,0,0,0,0 ,0,
0, 0,0,0,0,0 ,0,
0, 1,1,1,0,0 ,0,
0, 1,1,0,0,0 ,0,
0, 1,0,0,1,1 ,0,
0, 0,0,0,0,0 ,0
]function coord_to_int(coord, map) {
return (coord[0] + 1) * (map[0].length + 2) + (coord[1] + 1);
}
function int_to_coord(i, map) {
return [
Math.floor((i - 1) / (map[0].length + 2) - 1),
(i - 1) % (map[0].length + 2)
];
}
function newArray(size, value) {
var arr=[];
while(size--) {
arr.push(value);
}
return arr;
}
function generate_mobility_tiles(mobility, map) {
var i,
j,
ii = map.length,
jj = map[0].length,
o = newArray((ii + 2) * (jj + 2), false);
for (i = 0; i < ii; i += 1) {
for (j = 0; j < jj; j += 1) {
if(terrain_tile_types[map[i][j]][1][mobility]) {
o[coord_to_int([i, j]] = true;
}
}
}
return o;
}//near start
var mobility_tiles = generate_mobility_tiles(mobility_type, pathfind_map),
down = pathfind_map[0].length+2,
right = 1;
closed_tiles = new Array((pathfind_map.length + 2) * down); // sparse array matching mobility_tiles
//later
var surrounding = [
[current_tile.i + down, false],
[current_tile.i - down, false],
[current_tile.i + right, false],
[current_tile.i - right, false]
];
surrounding.forEach(function (t) { //IE < 9 compat is up to you
if (!mobility_tiles[t[0]] || //cannot move here
closed_tiles[t[0]]) { //visited already
return;
}
var index = open_tiles.map(function (x) { return x.i; }).indexOf(t[0]);
...while (open_tiles.length > 0) {
// remove smallest tile, faster than sort+shift?
f = Number.MAX_VALUE;
open_index = open_tiles.length;
smallest = 0;
while (open_index--) {
if (f > open_tiles[open_index].f) {
f = open_tiles[open_index].f;
smallest = open_index;
}
}
current_tile = open_tiles.splice(smallest, 1);// 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 = [ // [x][y] = key to terrain_tyle_types
[2,2,2,2,2],
[1,1,1,2,2],
[1,1,2,2,2],
[1,2,2,1,1]
];
function coord_to_int(coord, map) {
return (coord[0] + 1) * (map[0].length + 2) + (coord[1] + 1);
}
function int_to_coord(i, map) {
return [
Math.floor((i - 1) / (map[0].length + 2) - 1),
(i - 1) % (map[0].length + 2)
];
}
function newArray(size, value) {
var arr = [];
while (size--) {
arr.push(value);
}
return arr;
}
function generate_mobility_tiles(mobility, map) {
var i,
j,
ii = map.length,
jj = map[0].length,
o = newArray((ii + 2) * (jj + 2), false);
for (i = 0; i < ii; i += 1) {
for (j = 0; j < jj; j += 1) {
if (terrain_tile_types[map[i][j]].mobility[mobility]) {
o[coord_to_int([i, j]] = true;
}
}
}
return o;
}
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 reconstruct_path(end, map, closed_tiles){
var path = [],
current_tile = closed_tiles[coord_to_int(end, map)];
while (current_tile.p != current_tile.i) {
path.push(int_to_coord(current_tile.i, map));
current_tile = closed_tiles[current_tile.p];
if (!current_tile) { return false; }
}
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)
var pathfind_map = typeof substitute_map !== 'undefined' ? substitute_map : terrain_map;
mobility_type = typeof mobility_type !== 'undefined' ? mobility_type : 0;
var mobility_tiles = generate_mobility_tiles(mobility_type, pathfind_map),
down = pathfind_map[0].length+2,
right = 1;
// Able to walk on end tile? If not return false
var end_i = coord_to_int(end, pathfind_map);
if (!mobility_tiles[end_i]) return false;
// Validate start and end arrays
if (start.length != 2 || end.length != 2 ||
start[0] !== +start[0] || start[0] !== (start[0]|0) || // note: bit-ors ???
start[1] !== +start[1] || start[1] !== (start[1]|0) || // think that is wrong
end[0] !== +end[0] || end[0] !== (end[0]|0) ||
end[1] !== +end[1] || end[1] !== (end[1]|0)) { return false; }
var start_obj = {
i: coord_to_int(start, pathfind_map),
g:Context
StackExchange Code Review Q#13258, answer score: 8
Revisions (0)
No revisions yet.