过去几周我一直在开发多人 HTML5 游戏，使用nodejs和websockets.
我已经被这个问题困住了一段时间。想象一下，我用一个数组实现了这个 tilesheet 地图（如下所示）。
1或棕色瓷砖- 路上有障碍物，玩家无法通过。
0或绿色瓷砖- 是允许玩家移动的自由路径。
通过调用访问地图上的任何图块：
array[x][y]
我想创建最快的算法来找出地图两点之间的最短路线（如果有的话）。你会如何解决这个问题？我知道这是常见问题。
示例：
位置 (1,7) 的玩家发射带有一些 AI 的子弹，子弹会射向位置 (6,0) 的敌方玩家。Bullet 必须计算 2 名玩家之间的最短路线，如果没有，它就会撞到墙上。
问题：
如何高效地找到两点之间的最短路径？
这是一个常见的图论问题算法
在图论中，最短路径问题是在图中寻找两个顶点（或节点）之间的路径的问题，使得其组成边的权重之和最小。
寻找道路地图上两个交叉点之间的最短路径的问题（图的顶点对应于交叉点，边对应于路段，每个都由其路段的长度加权）可以通过最短路径的特殊情况进行建模图中的问题。
目前存在该算法的许多实现。在实现更简单的是Dijkstra算法的最坏情况下的性能， O(|E|+|V|log|V|)其中，
算法将分配一些初始距离值并尝试逐步改进它们：
为每个节点分配一个暂定距离值：对于我们的初始节点将其设置为 0，对于所有其他节点将其设置为 ∞。
将初始节点设置为当前节点。标记所有其他节点未访问。创建一个所有未访问节点的集合，称为未访问集。
对于当前节点，考虑其所有未访问的邻居并计算它们的暂定距离。将新计算的暂定距离与当前指定的值进行比较并指定较小的值。
当我们考虑完当前节点的所有邻居后，将当前节点标记为已访问并将其从未访问集合中删除。永远不会再次检查访问过的节点。
如果目标节点已被标记为已访问（在规划两个特定节点之间的路线时）或未访问集中节点之间的最小暂定距离为 ∞（规划完整遍历时；当初始节点之间没有连接时发生和剩余的未访问节点），然后停止。算法完成。
否则，选择标记为最小暂定距离的未访问节点，将其设置为新的“当前节点”，并返回步骤 3。
您可以在 github 存储库mburst/dijkstras-algorithm上找到 Dijkstra 算法的更多实现。
例如这里是JavaScript 实现
虽然 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
在上一个阵列也可以用来检查是否访问了点。
这里没有计算路径成本的条件，因为所有的路径成本都是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] 单元格中找到最短路径。