计算两点之间的最短路线

过去几周,我一直在使用nodejswebsockets在多人游戏上进行HTML5游戏。

我一直陷在这个问题上。 想象一下,我有一个数组( 如下所示 )实现这个tileheet映射。

1棕色的瓷砖 – 有一个障碍,玩家不能通过它。

0绿色瓷砖 – 是允许玩家移动的自由path。

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

  array[x][y] 

瓷砖地图 - 计算最短的路线

我想创build最快的algorithm来找出地图两点之间的最短路线(如果有的话)。 你将如何解决这个问题? 我知道这是常见的问题。

例如

在位置(1,7)的玩家用一些AI来发射子弹,这个AI会在位置(6,0)向敌方玩家发射。 子弹必须计算两个玩家之间的最短路线,如果没有,就会爆炸在墙上。

问题

如何有效地find两点之间的最短路线?

这是一个常见的图论问题algorithm

在图论中,最短path问题是在图中的两个顶点(或节点)之间寻找path的问题,使得其组成边的权重之和被最小化。

在路线图上find两个交叉点之间的最短path的问题(图的顶点对应于交叉点并且边对应于路段,每个路段的路段长度加权)可以通过最短path的特殊情况图中的问题。

现在存在很多这种algorithm的实现。 在实现中更简单的是具有最坏情况性能的Dijkstraalgorithm,其中O(|E|+|V|log|V|)其中

  • | V |节点的数量
  • | E |的数量

algorithm工作的例证

在这里输入图像描述

Dijkstra最短pathalgorithm的定义

  • 初始节点 – 我们开始的节点。
  • 节点Y的距离 – 是从初始节点Y的距离。

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

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

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

  3. 对于当前节点,考虑所有未访问的邻居并计算它们的暂定距离。 将新计算的暂定距离与当前分配的值进行比较,并分配较小的一个。

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

  5. 如果目的地节点已被标记访问(当规划两个特定节点之间的路由时)或者未访问集合中的节点之间的最小暂定距离是∞(当规划完全遍历时;当初始节点之间没有连接时和剩余的未访问节点),然后停止。 algorithm已经完成

  6. 否则,select标记有最小临时距离的未访问节点,将其设置为新的“当前节点”,然后返回到步骤3。

Dijkstraalgorithm的更多实现,你可以在github上findmburst / dijkstrasalgorithm 。

例如这里是JavaScript的实现

虽然dijkstraalgorithm明确的工作,在你的情况下,图是一个不加权的图,所以一个简单的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数组也可以用来检查一个点是否被访问。

这里没有计算path代价的条件,因为所有的path代价都是1.所以你可以在这里运行正常的二维BFSalgorithm,复杂度是O(V + E)(顶点和边)。

这里每个节点都有两个属性。 一个是行,另一个是列。 所以你可以创build一个表示单元格的值。 这里是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]单元中find最短path。