私は簡単なゲームをコーディングしていて、現在AIの部分をやっています。NPCは彼が訪問する必要がある彼の「興味のあるポイント」のリストを取得します。各ポイントには、マップ上の座標があります。キャラクターが与えられたすべてのポイントを訪れるための最速のパスを見つける必要があります。
私が理解している限り、このタスクは「強く接続された重み付き無向グラフで最速のトラバースパスを見つける」と説明できます。
それを計算するためのアルゴリズムの名前を取得するか、名前がない場合は、自分でプログラミングする際のいくつかのキーポイントを取得したいと思います。
前もって感謝します。
これは、巡回セールスマンの問題に非常に似ていますが、同等性をすぐに証明しようとするつもりはありません。TSP は NP 完全です。つまり、問題を正確に解くことは、関心点の数によっては非現実的である可能性があります。より便利な近似アルゴリズムがあります。
ツリー トラバーサルに関する以前の投稿を参照してください。
私は次のようなアルゴリズムを使用します：antアルゴリズム。
直接的ではありませんが、MMO エミュレーターで行ったことは、ウェイポイント インデックスを残りのパス データと共に保存することでした。あなたの要件が TSP の解決策を示すことである場合は、これを無視してください。そうでない場合は、IMO を検討する価値があります。
私の場合、それが最善の解決策でした。そうしないと、サーバーで数百のモブが (再) スポーンする可能性があり、他のすべての AI ロジックと共に、ルート ロジックを計算するサイクルをバーンする必要があるからです。