Javascript：在（50000*50000网格）2d阵列中寻路？-Javascript:Pathfindingina(50000*50000grid)2darray?

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 | +-----+------+-----+-----+-----+ | 234 | 165 | 724 | 759 | 230 | +-----+------+-----+-----+-----+ | 843 | 734 | 999 | 143 | 213 | +-----+------+-----+-----+-----+ | 242 | 2135 | 131 | 24 | 374 | +-----+------+-----+-----+-----+ | 159 | 464 | 155 | 124 | 151 | +-----+------+-----+-----+-----+

所以,假设有人想象一个2-d的整数值数组,它代表一个网格化的地图,如下所示:+ ----- + ------ + ----- + ----- + - ---- + | 10 | 2 | 2 | 4 | 656 | + ----- + ------ + ----- + ----- + ----- + | 234 | 165 | 724 | 759 | 230 | + ----- + ------ + ----- + ----- + ----- + | 843 | 734 | 999 | 143 | 213 | + ----- + ------ + ----- + ----- + ----- + | 242 | 2135 | 131 | 24 | 374 | + ----- + ------ + ----- + ----- + ----- + | 159 | 464 | 155 | 124 | 151 | + ----- + ------ + ------ + ------ + ------ +

The 2d indices represent the coordinates of a cell on the map, and the values in the array represent the relative difficulty to traverse the terrain of that cell - so for example 999 might be thick brambles, while 2,3,4 might be a slightly inclining path... or something.

2d索引表示地图上单元格的坐标,数组中的值表示遍历该单元格地形的相对难度 - 例如999可能是粗荆棘,而2,3,4可能是稍微倾斜的路径...或者其他什么。

Now we want to find the easiest path from [x,y] on the grid to [q,r] on the grid (where the sum of the steps is the lowest possible, in other words)

现在我们想要找到从网格上的[x,y]到网格上的[q,r]的最简单路径(其中步长的总和是最低的,换句话说)

The problem domain

问题领域

This needs to run in a modern browser, where a rather spartan map is rendered, and we'll draw a line from [x,y] to [q,r] through all the interceding vertices, after the user has input [q,r]. Conveniently, [X,Y] is always the same (say [0,0] for simplicity)

这需要在现代浏览器中运行,其中渲染相当简洁的地图,并且在用户输入[q之后,我们将通过所有中间顶点绘制从[x,y]到[q,r]的线。 R]。方便的是,[X,Y]总是相同的(简单来说[0,0])

So use Dijkstra's algorithm or A*!

所以使用Dijkstra的算法或A *!

So my first instinct was to model the array as a graph, apply Dijkstra's algorithm and work from there. And in the above case, with a 5x5 grid, that works fine. I traverse each array index, and use the value, and adjacent values, to generate a node with weighted edges to all of it's neighbours. This builds up a graph which I can then apply Dijkstra's algorithm to.

所以我的第一直觉是将数组建模为图形,应用Dijkstra的算法并从那里开始工作。在上面的例子中,使用5x5网格,工作正常。我遍历每个数组索引,并使用值和相邻值生成一个节点,该节点的所有邻居都有加权边。这构建了一个图表,然后我可以应用Dijkstra的算法。

However, In practice, I will be working with arrays up to 50,000 x 50,000 in size! That's 250 million!

但是,实际上,我将使用最大50,000 x 50,000的阵列!那是2.5亿!

So obviously building a graph on-the-fly to run Dijkstra’s algorithm isn't applicable. My next idea was to pre-compute the paths (The data-set is fixed), store them on the server and do a callback when we get the destination [q,r]...but this is 250,000,000 paths... even if I made it run in less than a second (which i don't think it will) it'll take years to compute all the paths...

因此,显然构建运行Dijkstra算法的图形是不适用的。我的下一个想法是预先计算路径(数据集是固定的),将它们存储在服务器上并在我们到达目的地[q,r]时进行回调...但这是250,000,000个路径...甚至如果我让它在不到一秒的时间内运行(我认为不会这样),那么计算所有路径需要数年时间......

I think I might need to take another approach but I'm not sure, how can I make this work?

我想我可能需要采取另一种方法,但我不确定,我怎样才能做到这一点?

1 个解决方案

/**
 * 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) {};