Javascript: Pathfinding In A (50000*50000 Grid) 2d Array?

The problem So, say one imagines a 2-d array of integer values which represents a gridded-map, like this: +-----+------+-----+-----+-----+ | 10 | 2 | 2 | 4 | 656 | +-----+

Solution 1:

Don't construct an explicit graph (pointers are expensive) -- use pairs of coordinates to represent nodes in the queue and modify your Dijkstra implementation to operate on your 2d array representation directly.

Use an array similar to the costs array to store the (initially tentative) distances calculated by the algorithm.

Dijkstra will calculate the costs to all nodes in a single run, so if your starting point is fixed, running it once should be sufficient -- there is no need to run it millions of times.

P.S.: Created a Jsfiddle running Dijkstra on images: https://goo.gl/5GWwMF

Computes the distances to all points from a mouse click, where darker pixels are interpreted as more expensive...

It becomes slower with larger images but didn't manage to crash it so far, but I think for your data it will run out of memory in the browser.

The Dijkstra implementation uses the following interface to access the graph -- I think this should be straight forward to provide on top of your data structure without explicitly generating a "traditional" graph data structure with explicit nodes and edges in memory:

/**
 * The interface the Dijkstra implementation below uses
 * to access the graph and to store the calculated final
 * and intermediate distance data.
 *
 * @Interface
 */
Graph = function() {};

/**
 * Returns the current distance for the given node.
 * @param {Object} node
 * @return {number}
 */
Graph.currentDistance = function(node) {};

/**
 * Stores the current distance for the given node.
 * @param {Object} node
 * @param {number} distance
 */
Graph.setCurrentDistance = function(node, distance) {};

/**
 * Returns an array of connected nodes for the given node, 
 * including the distances.
 *
 * @param {Object}
 * @return {Array<{cost:number, node:Object}>}
 */
Graph.connections = function(node) {};

P.P.S.: Added code to display the shortes path on all clicks after the first click. Also fixed a bug permitting diagonal movement: https://goo.gl/wXGwiv

So in conclusion, while this probably doesn't scale to 50k x 50x in the browser, I think this shows that Dijkstra operating on the arrays directly is worth trying on the server side, and that an array identical in size to the data array is all that is needed to store all shortest paths from a single point.