Javascript：在（50000 * 50000网格）2d阵列中寻路？ [英] Javascript: Pathfinding in a (50000*50000 grid) 2d array?

问题描述

问题

所以，假设有人想象一个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 |
+ ----- + ------ + ----- + ----- + ----- +


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 | +-----+------+-----+-----+-----+

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

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.

现在我们想要找到从网格上的[x，y]到网格上[q，r]的最简单路径（其中步骤的总和是可能性最低，换句话说）

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)

问题域

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

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)

所以使用Dijkstra算法或A *！

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

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.

然而，实际上，我将使用最大 50,000 x 50,000 的阵列！那是2.5亿！

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

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

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...

我认为我可能需要采取另一种方法，但我不确定，我该如何做到这一点？

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

推荐答案

不构造显式图形（指针很昂贵） - 使用坐标对来表示队列中的节点修改您的Dijkstra实现以直接操作您的2D阵列表示。

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.

使用类似于costs数组的数组来存储算法计算的（最初暂定的）距离。

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

Dijkstra将计算单次运行中所有节点的成本，因此如果您的起点是固定的，那么运行一次就足够了 - 不需要运行数百万次。

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.

PS：在图像上创建了一个运行Dijkstra的Jsfiddle：
https://goo.gl/5GWwMF

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.

Dijkstra实现使用以下界面访问图表 - 我认为这应该是直接提供在您的数据结构之上而不显式生成传统图形数据结构，在内存中具有显式节点和边缘：

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。：添加代码以在第一次点击后显示所有点击的短路径。还修正了允许对角线移动的错误： https://goo.gl/wXGwiv

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

总而言之，虽然这可能不会在浏览器中扩展到50k x 50x，但我认为这表明直接在阵列上运行的Dijkstra值得在服务器端尝试，而且数组相同数据数组的大小是从单点存储所有最短路径所需的全部。

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.

这篇关于Javascript：在（50000 * 50000网格）2d阵列中寻路？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！