5

アルゴリズムに関して言えば、私は本当にスピードフリークです。プラグインでは、ゲーム用に作成しました。

速度は..少し..満足のいくものではありません。特に車で運転しているときにパスをたどらない場合は、パスを再計算する必要があります。時間がかかるため、ゲーム内のGPSは多くの「間違った方法」の信号を積み上げています（そして信号を積み上げています）常に更新される高速のライブGPSシステムが必要なため、間違った方向に移動するたびに、後で計算が増えることを意味します。

古いアルゴリズム（いくつかの単純なダイクストラ実装）をboost :: dijkstraに変更して、ノードAからノードBへのパスを計算しました

（合計ノードリストは約15,000ノードで約40k接続です。好奇心旺盛な人のためにここにマップがあります：http：//gz.pxf24.pl/downloads/prv2.jpg（12 MB）、赤い線の端がノードです）、

しかし、実際には速度は上がりませんでした。（少なくとも目立たないように、おそらく50ミリ秒）。

ノード配列に格納される情報は次のとおりです。

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-systemがどのようなものかを見ることができます。

http://www.youtu.be/xsIhArstyU8

ご覧のとおり、赤いルートはゆっくりと更新されています（まあ、私たち-ゲーマー-それは遅いです）。

（ByTheWay：赤い線の間のギャップはずっと前に修正されました：p）

4

2 に答える 2

5

これはGPSであるため、宛先が固定されている必要があります。現在のノードを変更するたびに現在のノードから宛先へのパスを計算する代わりに、宛先からすべてのノードへの最短パスを見つけることができます。宛先から開始してダイクストラを実行するだけです。これには、現在更新が行われている限り、約時間がかかります。

次に、各ノードで、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

スタートを瞬時にするために、次の方法でチートすることができます。

「主要な道のノード」のかなり小さなセットがあります。各ノードについて、その「近隣」（特定の距離内のすべてのノード）を定義します。すべての主要な道のノードから他のすべてのノードへの最短ルートを保存します。各ノードから主要な道までの最短ルートを保存します。

2つのノードが同じ近傍にある場合は、その場で最良の答えを計算できます。それ以外の場合は、「ここから私の近くの主要な道のノードから、その近くの主要な道のノードまで」という形式のルートのみを検討します。すでにそれらを事前に計算しており、組み合わせの数が限られているため、その場でルートを非常にすばやく計算できるはずです。

次に、主要な道のノードのセットを選択することが課題になります。ほとんどの適切なルートが通過するノードのセットはかなり小さいはずです。したがって、主要な通りに沿ってノードを頻繁に選択します。数百のリストは、マップには十分すぎるはずです。

于 2012-07-01T04:07:08.950 に答える