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
Javascript A* pathfinding function for tile-based game optimisation
javascript;pathfinding
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 startvar 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 < 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);}());