我在过去几周一直在开发一个多人在线HTML5游戏，使用nodejs和websockets。
我有一个问题困扰了我一段时间。假设有一个由数组实现的瓦片地图（如下所示）。
1或棕色瓷砖 - 道路上有障碍物，玩家不能通过它。
0或绿色瓷砖 - 是允许玩家移动的自由路径。
通过调用以下方式访问地图上的任何瓦片:
array[x][y]
我想创建最快的算法，以找出地图上两点之间最短的路径（如果存在）。您会如何解决这个问题？我知道这是一个常见的问题。
例子：
位于位置 (1,7) 的玩家发射一颗子弹，带有某种 AI，直向位于位置 (6,0) 的敌方玩家。子弹必须计算出两个玩家之间的最短路径，如果没有，则会撞到墙上爆炸。
问题：
如何高效地找到两点之间的最短路径？
这是一个常见的图论问题算法。
在图论中，最短路径问题是查找两个顶点（或节点）之间路径的问题，路径由其组成边的权重之和最小化。
在道路地图上查找两个交叉口之间的最短路径（图的顶点对应于交叉口，边对应于道路段，每个道路段的权重由其长度加权）可以被建模为图中最短路径问题的特殊情况。
目前有许多实现这个算法。其中一种更简单的实现是Dijkstra算法，其最坏情况性能为O（|E|+|V|log|V|），其中
算法将分配一些初始距离值，并逐步尝试改进它们：
为每个节点分配一个临时距离值：对于我们的初始节点，将其设置为0，对于所有其他节点，将其设置为∞。
将初始节点设置为当前节点。标记所有其他节点为未访问。创建一个名为未访问集合的所有未访问节点的集合。
对于当前节点，请考虑其所有未访问的邻居并计算它们的临时距离。比较新计算的临时距离与当前分配值并分配较小的值。
当我们考虑完当前节点的所有邻居时，将当前节点标记为已访问并从未访问集合中删除它。已访问的节点将不会再次被检查。
如果目标节点已标记为已访问（在两个特定节点之间规划路线时）或未访问集合中节点的最小临时距离为∞（在规划完整遍历时发生；当初始节点和剩余未访问节点之间没有连接时发生），则停止。 算法已完成。
否则，选择标记有最小临时距离的未访问节点，将其设置为新的“当前节点”，并返回步骤3。
您可以在Github仓库mburst/dijkstras-algorithm中找到更多的Dijkstra算法实现。
例如，这里是JavaScript实现。
A*，它类似于Dijkstra，但还使用启发式来帮助集中在可能靠近目标的节点上。 - Tom Leysqueue = [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
#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
}
}
}
}