更快的替代Dijkstra的GPS系统算法

Question

如果它涉及算法,并且在我为游戏制作的插件中,我是一个真正的速度怪胎.

速度有点......不满意.特别是在驾驶汽车并且不遵循自己的路径时,必须重新计算路径..这需要一些时间,因此游戏中的GPS会叠加许多"错误方式"信号(并堆叠信号)意味着之后的更多计算,对于每个错误的方式移动)因为我想要一个不断更新的快速,实时gps系统.

我将旧算法(一些简单的dijkstra实现)改为boost :: dijkstra's来计算从节点A到节点B的路径

(总节点列表约为~15k节点,有~40k连接,对于好奇的人,这里是地图:http://gz.pxf24.pl/downloads/prv2.jpg(12 MB),红线边缘是节点)

但它并没有真正提高速度.(至少不明显,可能是50毫秒).

存储在Node数组中的信息是:

The ID of the Node,
The position of the node,
All the connections to the node (and which way it is connected to the other nodes, TO, FROM, or BOTH)
Distance to the connected nodes.

我很好奇是否有人知道更快的C/C++替代品？任何建议(+代码示例？)表示赞赏!

---

如果有人对该项目感兴趣,这里是(源+二进制):

https://gpb.googlecode.com/files/RouteConnector_177.zip

在本视频中,您可以看到gps系统是什么样的:

http://www.youtu.be/xsIhArstyU8

你可以看到红色路线正在缓慢更新(好吧,对我们来说 - 游戏玩家 - 它很慢).

(ByTheWay:很久以前红线之间的差距已经修复:p)

Answer 1

由于这是一个GPS,它必须有一个固定的目的地.每次更改当前节点时,您都​​可以找到从目标到所有节点的最短路径,而不是计算从当前节点到目标的路径:只需从目标开始运行Dijkstra.只要现在更新,这将花费大约时间.

然后,在每个节点中,保持prev = the node previous to this on the shortest path to this node(从您的目的地).您在计算最短路径时更新此项.或者你可以prev[]在节点之外使用一个数组 - 基本上你现在用来重建路径的任何方法都应该可行.

在移动您的汽车时,您的路径是由currentNode.prev -> currentNode.prev.prev -> ....

这将解决更新延迟并保持最佳路径,但进入目的地后仍会有轻微延迟.

即使您计划使用A*或其他并不总是给出最佳答案的启发式方法,您也应该考虑这种方法,至少如果您仍然使用这些方法滞后.

例如,如果您有此图表:

1 - 2 cost 3
1 - 3 cost 4
2 - 4 cost 1
3 - 4 cost 2
3 - 5 cost 5

该prev阵列是这样的(当你计算的距离计算d[]):

       1 2 3 4 5
prev = 1 1 1 2 3

含义:

shortest path FROM TO 
                 1  2 = prev[2], 2 = 1, 3
                 1  3 = prev[3], 3 = 1, 3
                 1  4 = prev[ prev[4] ], prev[4], 4 = 1, 2, 4 (fill in right to left)
                 1  5 = prev[ prev[5] ], prev[5], 5 = 1, 3, 5 
                 etc.