5

如果涉及到算法，以及我为游戏制作的插件，我是一个真正的速度狂。

速度……有点……不满意。尤其是当你开车四处行驶并且你没有按照自己的路径行驶时，必须重新计算路径..这需要一些时间，所以游戏中的 GPS 会堆积许多“错误的方式”信号（并堆积信号之后意味着更多的计算，对于每一个错误的方向移动），因为我想要一个快速、实时的 gps 系统，它会不断更新。

我将旧算法（一些简单的 dijkstra 实现）更改为 boost::dijkstra 以计算从节点 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）

4

2 回答 2

5

由于这是一个 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.
于 2012-06-30T22:37:15.023 回答
2

要立即开始，您可以通过以下方式作弊。

拥有相当少的“主要通道节点”。为每个节点定义其“邻居”（一定距离内的所有节点）。存储从每个主要通道节点到其他每个节点的最短路线。存储往返每个节点到其主要通道的最短路线。

如果两个节点在同一个邻域中，您可以即时计算最佳答案。否则只考虑“这里到我附近的主要通道节点到它附近的主要通道”形式的路线。由于您已经预先计算了这些，并且组合数量有限，您应该能够很快地计算出飞行路线。

然后挑战变成了选择一组主要的通道节点。它应该是大多数好的路线都应该经过的一组相当小的节点——所以要经常沿着主要街道选择一个节点。几百张的清单对您的地图来说应该已经足够了。

于 2012-07-01T04:07:08.950 回答