计算两点之间的最短路线

Question

过去几周我一直在开发多人 HTML5 游戏，使用 nodejs 和 websockets。

我被这个问题困扰了一段时间。想象一下，我用一个数组实现了这个瓦片地图（如下所示）。

1 或 棕色方块 - 路上有障碍物，玩家无法通过。

0 或 绿色方块 - 是允许玩家移动的自由路径。

通过调用访问地图上的任何图块：

 array[x][y]

我想创建最快的算法来找出地图两点之间的最短路线（如果有的话）。你会如何处理这个问题？我知道这是常见问题。

示例：

位置 (1,7) 的玩家用一些 AI 发射一颗子弹，该子弹将射向位置 (6,0) 的敌方玩家。 Bullet 必须计算 2 名玩家之间的最短路线，如果没有，它就会撞到墙上爆炸。

问题：

如何高效地找到两点之间的最短路线？

Answer 1

这是常见的graph theory problem algorithm

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

The problem of finding the shortest path between two intersections on a road map (the graph's vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of its road segment) may be modeled by a special case of the shortest path problem in graphs.

目前存在 lot of implementations of this algorithm. More simpler in implementation is a Dijkstra's algorithm，最差情况下的性能为 O(|E|+|V|log|V|)，其中

|V|是节点数
|E|是边数

算法工作图解

Dijkstra最短路径算法的定义

初始节点 - 我们开始的节点。
节点 Y 的距离 - 是从 初始节点 到 Y 的距离。

算法将分配一些初始距离值，并将尝试逐步改进它们：

为每个节点分配一个暂定距离值：将我们的初始节点设置为0，所有其他节点设置为∞。
将初始节点设置为当前节点。将所有其他节点标记为未访问。创建一个包含所有 unvisited 节点的集合，称为 unvisited 集合.
对于当前节点，考虑其所有未访问 邻居并计算它们的暂定距离。将新计算的暂定距离与当前分配的值进行比较，并分配较小的值。
当我们完成对当前节点的所有邻居的考虑后，将当前节点标记为已访问并将其从未访问集中删除。访问过的节点将永远不会被再次检查。
如果目的节点已经被标记为已访问（在规划两个特定节点之间的路径时）或者未访问集合中的节点之间的最小暂定距离为∞（规划一次完整遍历时；发生在初始节点与剩余未访问节点之间没有连接时），则停止。 算法完成.
否则，select标记暂定距离最小的未访问节点，设置为新的"current node"，然后返回到步骤 3。

您可以在 github 存储库 mburst/dijkstras-algorithm 上找到更多 Dijkstra 算法的实现。

例如这里是JavaScript implementation

Answer 2

虽然 dijkstra 算法确实有效，但在您的情况下，该图是未加权图，因此简单的 BFS 就足够了。

伪代码：

queue = [startingposition]
prev = [-1, -1, -1 ...] (array of n elements, all -1)
while (queue not empty) 
   u <- pop(queue)
   if u = targetposition then DONE! trace the *prev* array for path
   for (v in every unvisited points adjacent to u):
      prev[v] = u
      push v to queue
   end for
end while

prev数组也可以用来判断一个点是否被访问过

Answer 3

这里没有计算路径代价的条件，因为所有的路径代价都是1。所以你可以运行这里使用普通的2D BFS算法，复杂度为O(V+E)(顶点和边) .

这里每个节点都有两个属性。一个是行，另一个是列。所以你可以创建一对来表示一个单元格的值。这是c++代码和解释：

#define pii pair<int,int>
int fx[]={1,-1,0,0}; //Direction array for moving one cell to another cell horizontaly
int fy[]={0,0,1,-1}; //Direction array for moving one cell to another cell verticaly
int cell[100][100]; //cell[x][y] if this cell is -1 then it is block (Here it is your brown cell)
int d[100][100],vis[100][100]; //d means destination from source. 
int row,col;
void bfs(int sx,int sy) //Source node is in [sx][sy] cell.
{
    memset(vis,0,sizeof vis);
    vis[sx][sy]=1;
    queue<pii>q; //A queue containing STL pairs
    q.push(pii(sx,sy));
    while(!q.empty())
    {       
        pii top=q.front(); q.pop();
        for(int k=0;k<4;k++)
        {
            int tx=top.uu+fx[k];
            int ty=top.vv+fy[k]; //Neighbor cell [tx][ty]
            if(tx>=0 and tx<row and ty>=0 and ty<col and cell[tx][ty]!=-1 and vis[tx][ty]==0) //Check if the neighbor is valid and not visited before.
            {               
                vis[tx][ty]=1;
                d[tx][ty]=d[top.uu][top.vv]+1; 
                q.push(pii(tx,ty)); //Pushing a new pair in the queue
            }
        }
    }
}

现在您可以很容易地找到从 d[x][y] 单元格开始的最短路径。

计算两点之间的最短路线

Calculating the shortest route between two points

javascript

algorithm

math

node.js

graph-algorithm

算法工作图解

Dijkstra最短路径算法的定义