相关疑难解决方法(0)

地图提供商(例如Google或Yahoo! Maps)如何提供方向？

我的意思是,他们可能有某种形式的真实数据,当然包括距离,但也可能包括行驶速度,人行道的存在,火车时刻表等.但是假设数据格式较简单,比如一个非常大的有向图边缘权重反映距离.我希望能够快速计算从任意点到另一个点的方向.有时这些点将在一起(在一个城市内),而有时它们将相隔很远(越野).

像Dijkstra算法这样的图算法不起作用,因为图形是巨大的.幸运的是,像A*这样的启发式算法可能会起作用.但是,我们的数据非常有条理,也许某种分层方法可能有用吗？(例如,存储远离某些"关键"点之间的预先计算方向,以及一些局部方向.然后,两个远点的方向将涉及到关键点的本地方向,到另一个关键点的全局方向,然后是本地方向方向再次.)

在实践中实际使用了哪些算法？

PS.这个问题的动机是通过在线地图方向找到怪癖.与三角形不等式相反,有时谷歌地图认为XZ需要更长时间,并且比使用XYZ中的中间点更远.但也许他们的步行路线也会针对另一个参数进行优化？

PPS.这是对三角不等式的另一个违反,它暗示(对我来说)他们使用某种分层方法:XZ与XYZ.前者似乎使用着名的Boulevard de Sebastopol,尽管它稍微偏离了方向.

编辑:这些例子似乎都不再起作用,但两者都是在原始帖子时完成的.

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

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

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

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

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

 array[x][y]

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

示例:

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

问题:

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