1

非常に大きなマップを持つゲームがあり、多くのウェイポイント (数十億ではないにしても数百万) を保存して、A* アルゴリズムを使用した経路探索に使用する必要があります。

必要なもの:

  1. たくさん収納する効率的な方法
  2. A* アルゴリズムでそれらに直接アクセスする高速な方法。

最初は単純なベクトルを使用することを考えましたが、これはすぐに使用可能なすべてのメモリを使用します。次に、mysql を使用する必要があると考えました。ウェイポイントの領域についてデータベースにクエリを実行できるため、これはおそらく良い考えです。

大きな問題は、A* の場合、できるだけ早くウェイポイントにアクセスする必要があるため、ウェイポイントごとに一意の ID が必要になることです。

これを達成するための最良の方法は何ですか？

4

1 に答える 1

0

メモリを自分で管理することで、少しレベルを下げることを検討する必要があると思います---グラフのすべてのノードに対してnewand を明示的に呼び出します。deleteノードをメモリアドレスで参照します。メモリの小さなチャンクをたくさん割り当てることが心配な場合は、tcmallocライブラリの使用を検討できます。

ノードには隣接リストが含まれている必要があります。グラフが静的な場合、各ノードで動的に作成された配列に隣接関係を格納することをお勧めします。このサイズは、隣接ノードの数と正確に一致します。隣人の数が時間の経過とともに変化するstd::vector可能性がある場合は、次善の策かもしれません。

注: グラフは不規則だと思います。通常のグラフ (Potatoswatter が指摘したグリッドなど) の場合、ノードの位置は暗黙的に学習できます。

于 2013-01-11T08:31:53.430 に答える