4

ノードグラフ上を移動するコンピューター制御のクリーチャーがいくつかある単純なゲームシミュレーションをプログラミングしています。彼らはターゲットに向かって行きたいと思っています（たとえば、オオカミがウサギに向かって行きたいと考えています）.

クリーチャーが特定のターゲット ノードに直接向かう最速のルートを見つけることができるように、単純な経路探索を既に実装していますが、複数のターゲット (複数のノードにたくさんの食べ物) がある場合は、ヒートマップ グラデーションのようなものを生成したいと思います。オオカミが隣接ノードを照会して、最もホットな隣接ノードに向かうことができるように、グラフ。

グラフ上でヒートマップを生成する効率的な方法を知っている人はいますか? 私が考えることができる最速の方法は、N 回のフル グラフ トラバーサル (N = 食品ノードの数) を実行し、毎回 BFS (または、最も近い/最もホットな未訪問ノード最初のトラバーサル) を各食品ノードから開始して計算することです。グラフの各ノードでその食品ノードからの熱を計算し、1 つのコレクション パスで各食品からのすべての熱を合計します。大きなグラフと多数の食品ノードがある場合、それぞれが多くのノードを持つ多くの完全なグラフトラバーサルを実行する必要がある可能性があるため、私はこれが好きではありません。

私は、すべての食料ノードのオープンセットから始めて、そこから外側に移動する一種の BFS を行うことを考えていましたが、その後、最も近い食料ノードまでの距離のみを計算していました。以前にトラバースしたノードで熱を増加させるために戻ることができないため、食品ノードのクラスターは非常に暑い場所を生成しません (そして、それを許可する場合、基本的に、前の例のようにすべてのノードを N 回訪問します) . たとえば、次から始めると:

F-O-O-O-O-O-O-O-O
| | | | | | | | |
F-O-O-O-O-O-O-O-F

ここで、F は食品、O は空のノードで、食品ノードの熱が 5 で、ノードごとに 1 の減衰があるとします。ヒートマップを次のように表示したいです。

9-7-5-3-1-1-2-3-4
| | | | | | | | |
9-7-5-3-2-2-3-4-5

しかし、BFS スタイルのトラバーサル (どのノードも 1 回しかアクセスできない) は次のようになります。

5-4-3-2-1-1-2-3-4
| | | | | | | | |
5-4-3-2-2-2-3-4-5

誰かがこれを行うためのより賢い方法を持っていますか? 最悪の場合、複数の N 回のグラフ トラバーサルを実行できる可能性がありますが、スケジュールに従って、X 秒ごとに 1 回だけフード ノード トラバーサルを実行します...

4

2 に答える 2

3

グラフの周りの熱の流れをシミュレートしてみませんか? つまり、時刻tにおけるノードiの温度が T i  ( t ) の場合、次のように設定します。

T i  ( t + 1) = α F i  ( t ) + (1 − β) T i  ( t ) + γ Σ j ∈ n( i ) T j  ( t )

ここで、 F i  ( t ) は時間t におけるノードiの食物の量、 n( i ) はノードiの近傍のセット、 α、β および γ はシミュレーションのパラメーターです。α は熱がシステムに入る速度、β は熱がシステムから出る速度、γ はノードから隣接するノードへの熱の流れの速度です。これらはすべて小さい数値である必要があります。実験して適切な値を見つける必要があります。

この式を使用すると、すべてのノードの温度を更新するには O(|nodes| + |edges|) かかるため、定期的に (理想的にはフレームごとに) 計算できるはずです。

上記の方程式は、離散シミュレーション (一定の時間ステップ) 用です。可変時間ステップ δt がある場合は、次を試してください。

T i  ( t + δt) = δt α F i  ( t ) + (1 − β) δt T i  ( t ) + δt γ Σ j ∈ n( i ) T j  ( t )

于 2013-03-22T09:25:36.453 に答える
0

あなたの一般的なアプローチは良いですが、ヒートマップの概念に目がくらんでいると思います。本質的には、すべてのターゲットの加重平均位置を計算し、ハンターをそのポイントに向かわせたいと考えています。これを次のように実装します。

  1. N より近いターゲットがある場合は、最も近いターゲットを追跡します。そうしないと
  2. 重み関数 = D^2 を使用して、Max よりも近いすべてのターゲットの加重平均位置を計算します (単なる推測ですが、平方根が必要ないため計算は迅速です)。ハンターは反復ごとにその場所に向かいます。
  3. 1から繰り返します。
于 2013-03-22T08:59:43.017 に答える