计算两点之间的最短路线

Question

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

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

1或棕色瓷砖 - 路上有障碍物,玩家无法通过它.

0或绿色瓷砖 - 是允许玩家移动的自由路径.

通过以下方式访问地图上的任何图块:

 array[x][y]

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

示例:

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

问题:

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

Answer 1

这是一种常见的图论问题算法

在图论中,最短路径问题是在图中的两个顶点(或节点)之间找到路径使得其组成边缘的权重之和最小化的问题.

在路线图上找到两个交叉点之间的最短路径的问题(图形的顶点对应于交叉点,并且边缘对应于路段,每个路段按其路段的长度加权)可以通过最短路径的特殊情况建模图中的问题.

目前存在很多这种算法的实现.在实现更简单的是Dijkstra算法的最坏情况下的性能, O(|E|+|V|log|V|)其中,

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

算法工作的例证

Dijkstra最短路径算法的定义

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

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

1. 为每个节点分配一个暂定距离值:为我们的初始节点设置为0,为所有其他节点设置为∞.

2. 将初始节点设置为当前节点.标记未访问的所有其他节点.创建一组称为未访问集的未访问节点.

3. 对于当前节点,考虑其所有未访问的邻居并计算其暂定距离.将新计算的暂定距离与当前指定值进行比较,并指定较小的临时距离.

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

5. 如果目标节点已被标记为已访问(当计划两个特定节点之间的路由时)或未访问集中的节点之间的最小暂定距离是∞(当计划完整遍历时;在初始节点之间没有连接时发生)和剩下的未访问的节点),然后停止.算法已经完成.

6. 否则,选择标记有最小暂定距离的未访问节点,将其设置为新的"当前节点",然后返回步骤3.

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

例如,这里是JavaScript实现