计算两点之间的最短路线
过去几周，我一直在使用nodejs和websockets在多人游戏上进行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将分配一些初始距离值，并尝试逐步改进它们：
-
为每个节点分配一个暂定的距离值：对于我们的初始节点将其设置为0，对于所有其他节点将其设置为∞。
-
将初始节点设置为当前。 标记所有其他节点未访问 。 创build一组所有未访问节点，称为未访问集 。
-
对于当前节点，考虑所有未访问的邻居并计算它们的暂定距离。 将新计算的暂定距离与当前分配的值进行比较，并分配较小的一个。
-
当我们考虑当前节点的所有邻居时，将当前节点标记为已访问并将其从未访问集中移除。 被访问的节点将不会再被检查。
-
如果目的地节点已被标记访问（当规划两个特定节点之间的路由时）或者未访问集合中的节点之间的最小暂定距离是∞（当规划完全遍历时;当初始节点之间没有连接时和剩余的未访问节点），然后停止。 algorithm已经完成 。
-
否则，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。
