Javascript A* pathfinding function for tile-based game optimisation

Question

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: https://stackoverflow.com/questions/11300249/javascript-return-position-index-of-matched-array-within-array

Answer 1

I have made the 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 element

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 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 < 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: 0,
        h: calc_h(start,end)
    };
    start_obj.p = start_obj.i;
    start_obj.f = start_obj.g + start_obj.h;


    var open_tiles = [start_obj];
    var closed_tiles = new Array((pathfind_map.length + 2) * down); // sparse array matching mobility_tiles
    var current_tile, f, open_index, smallest;
    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);

        // Add tile to closed list
        closed_tiles[current_tile.i] = current_tile;

        if(end_i === current_tile.i){
            // Path found, finish.
            return reconstruct_path(end, map, closed_tiles);
        }

        // 4-surrounding tiles:
        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) {
            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]);
            var t_g = (curr.g + (t[1] ? 14 : 10));
            if (index > -1) {
                // Tile already found in open list
                var old = open_tiles[index];
                if (t_g < old.g) {
                    // This new path is better. Update open list entry
                    old.g = t_g;
                    old.f = t_g + old.h;
                    old.p = curr.i;
                }
            } else {
                // Tile wasn't found in open list, so add it now
                var coord = int_to_coord(current_tile.i, map);
                var potential = {
                    i: t[0],
                    g: t_g,
                    h: calc_h(coord, end),
                    p: curr.i
                };
                potential.f = potential.g + potential.h;
                open_tiles.push(potential);
            }
        });
    }
    // No valid path found from start to end
    return false;
}

Another change you could do to make this appear smoother to the UI would be to make it async.

Instead of the while (open_tiles loop (reminder this will require changes elsewhere):

var iterations = 10;
(function iter() {
    while (iterations--) {
        if (!open_tiles.length) {
            failed_callback();
            return;
        }
        ...
        if(end_i === current_tile.i){
            // Path found, finish.
            found_callback(reconstruct_path(end, map, closed_tiles));
            return;
        }
        ...

    }
    iterations = 10;
    window.setTimeout(iter, 1);
}());

Answer 2

Also not necessarily concerning performance:

• First off: Never use for..in on arrays, it doesn't do what you think it does.
• The code isn't really readable. The "magic arrays" aren't nice (see James' suggestion), and the long, long lines don't really help either.
• A working example (eg with jsfiddle) with some explanation how to call your code would be helpfull,
• To speed up the array search, it may be worth trying implementing coordinates as objects with an integer hash value, which should help comparisons.

Answer 3

I know you are asking about performance but I'd like to suggest some readability changes.
Lists are good for lists of things not for keeping properties in.

for example:

    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
    ];

could be an object/list of objects:

     var terrain_tile_types = {
         "INV" : { "description" : "invisible/unselectable", "other_property": 0, "another_property": 0, "mobility_type": {"walking": false, "swimming":false, "flying":false} } // ID = "INV"
         "FLATGRASS" : { "description": "Flat Grass", "other_property": 1, "another_property": 0", mobility_type": {"walking": true, "swimming":false, "flying":true} } // ID = "FLATGRASS"
         "H2O": { "description": "Water", "other_property": 0, "another_property": 1, "mobility_type": {"walking": false, "swimming":true, "flying":true} } // ID = "H2O"}
     };

This way when you read the code it actually makes sense what you are accessing. Less need for magic numbers?

Answer 4

please check out this :

http://jsfiddle.net/konijn_gmail_com/bndxD/

Main features are :

• Named properties instead of indexed properties
• JS naming convention nameStuffLikeThis not name_stuff_like_this
• Not using for..in
• Extract getting a tile into a function which returns nothing when bounds are wrong

It is more memory intensive then your version, but it should be much faster, let me know if it actually is on large maps. It also easily allows for 8 directional searching and monsters that go over multiple terrain types. It does not put this in a nice object, even though this really should contain a map object with a function that does path-finding.

Code :

//which directions can be taken,
//only cardinal in this case, you can be creative with this
var directions = [{ x: -1, y:  0},
                  { x:  1, y:  0},
                  { x:  0, y:  1},
                  { x:  0, y: -1}];

//What can be traversed ? 
var PASS_FLOOR = 0x1; // 0001  
var PASS_WATER = 0x2; // 0010  

// Some terrain types:
// Feel free to embellish with other properties
var terrainTypes = [
    { type: "",      canPass: 0},
    { type: "grass", canPass: PASS_FLOOR},
    { type: "water", canPass: PASS_WATER},];

//map should really be a class..
var testMap = [[2, 2, 2, 2, 2],
               [1, 1, 1, 2, 2],
               [1, 1, 2, 2, 2],
               [1, 2, 2, 1, 1]];

/* Get a tile at a location, ideally this should be a function of the map object.. 
dont trust map at all, trust that location has .x and .y */
function getTile(map, location) {
    if (map && map[location.x] && map[location.x][location.y])
        return terrainTypes[map[location.x][location.y]];
    return false;
}

/* This could be cleaner.. */
function getNeighbours(map, location, directions_optional) {
    var i;
    var neighbours = [];
    //make sure we start with something
    location.trace = location.trace || [];
    //This code still has far too many globals, that should all get fixed
    var vectors = directions_optional || directions;
    for (i = 0; i < vectors.length; i++) {
        var newX = location.x + vectors[i].x;
        var newY = location.y + vectors[i].y;
        if (!map[newX]) map[newX] = [];
        if (!map[newX][newY])
        {
          map[newX][newY] = {
            x: newX,
            y: newY,            
            //distance from origin
            d: (location.d || 0) + 1,
            //how did we get here
            trace: location.trace.slice(0)
          } 
         }
        else
        {
          continue;
        }
        map[newX][newY].trace.push({ x: newX, y: newY });
        neighbours.push(map[newX][newY]);
    }
    return neighbours;
}


function findPath(start, end, mobility_optional, map_optional) {
    // start = start coords array { x, y }, note this could be a monster or an item with these properties!
    // end = end coords array  { x, y }, see above
    // mobility_optional = which type of tiles are "walkable" based on the moving unit's type, see var PASS_*
    // map_optional = optional map array to use instead of the default (terrain_map)
    var map = map_optional || testMap;
    var mobility = mobility_optional || start.mobility || PASS_FLOOR;
    var shadowMap = [];
    var location, neighbours, i;

    // Validate start and end
    if (!getTile(map, start) || !getTile(map, end)) return false;

    // Able to walk on start and end tile? If not return false
    if (!(getTile(map, start).canPass & mobility) || !(getTile(map, end).canPass & mobility)) return false;

    //Start with the start ( we only look there hence the last parameter )
    var todo = getNeighbours(shadowMap, start, [{ x: 0, y: 0}]);

    //While we have places to check
    while (todo.length > 0) {
        location = todo.shift();
        console.log( "Looking at" , location );
        neighbours = getNeighbours(shadowMap, location);
        console.log( "Neighbours" , neighbours );        
        //Find neighbours and iterate over them
        for (i = 0; i < neighbours.length; i++) {
            //check whether we can go there with mobility
            if (!(getTile(map, neighbours[i]).canPass & mobility)) continue;
            //did we find the place ? 
            if (neighbours[i].x == end.x && neighbours[i].y == end.y) return neighbours[i].trace;
            //did we find a new spot further away from start ?
            if (neighbours[i].d > location.d) todo.push(neighbours[i]);
            //did we find an old spot closer to the start ?
            //if (neighbours[i].d < location.d)
            //Save some memory
            //delete neighbours[i].trace
        }
    }
    return false;
}

var start = { x: 0, y: 0 , mobility : PASS_WATER };
var end   = { x: 3, y: 1 };

console.log(findPath(start, end));​