首页 文章

计算两点之间的最短路线

提问于
浏览 次
19

过去几周我一直在使用 nodejs 和 websockets 进行多人HTML5游戏 .

我已经陷入了这个问题一段时间了 . 想象一下，我有一个用数组实现的tileheet map（如下所示） .

1 或 brown tiles - 路上有障碍，玩家无法通过它 .

0 或 green tiles - 允许玩家移动的自由路径 .

通过以下方式访问 Map 上的任何图块：

array[x][y]

tilesheet map - calculate the shortest route

我想创建最快的算法，找出 Map 两点之间的最短路径（如果有的话） . 你会如何解决这个问题？我知道这是常见的问题 .

Example ：

位置（1,7）的玩家用一些人工智能发射子弹，该AI会朝向位置（6,0）的敌方玩家 . 子弹必须计算两个球员之间的最短路线，如果没有，它只会在墙上爆炸 .

Question ：

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

javascript node.js algorithm math graph-algorithm

3 回答

  • 17

    这是常见的graph theory problem algorithm

    在图论中，最短路径问题是在图中的两个顶点（或节点）之间找到路径的问题，使得其组成边缘的权重之和最小化 . 在路线图上找到两个交叉点之间的最短路径的问题（图形的顶点对应于交叉点，并且边缘对应于路段，每个路段按其路段的长度加权）可以通过最短路径的特殊情况建模图中的问题 .

    现在存在lot of implementations这个算法 . 更简单的实现是Dijkstra's algorithm，最坏情况下的性能为 O(|E|+|V|log|V|) 其中

    • |V| 是节点数

    • |E| 是边数

    算法工作图

    enter image description here

    Dijkstra最短路径算法的定义

    • initial node - 我们开始的节点 .

    • distance of node Y - 是从 initial node 到 Y 的距离 .

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

    • 为每个节点分配一个暂定距离值：为 initial node 设置为0，为所有其他节点设置为∞ .

    • 将 initial node 设置为当前 . 标记所有其他节点 unvisited . 创建一组名为 unvisited set 的所有 unvisited 节点 .

    • 对于当前节点，请考虑其所有 unvisited 邻居并计算其暂定距离 . 将新计算的暂定距离与当前指定的值进行比较，并指定较小的临时距离 .

    • 当我们考虑当前节点的所有邻居时，将当前节点标记为已访问并将其从 unvisited set 中删除 . 永远不会再次检查受访节点 .

    • 如果目标节点已标记为已访问（在规划两个特定节点之间的路由时）或 unvisited set 中节点之间的最小暂定距离为∞（计划完整遍历时;在初始节点之间没有连接时发生）和剩下的未访问的节点），然后停止 . The algorithm has finished .

    • 否则，选择标记有最小暂定距离的 unvisited 节点，将其设置为新"current node"，然后返回步骤3 .

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

    例如，这里是JavaScript implementation

    回复于
  • 3

    虽然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数组也可用于检查是否访问了一个点 .

    回复于
  • 1

    这里没有计算路径成本的条件，因为所有路径成本都是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]单元格中找到最短路径 .

    回复于

相关问题