問題タブ [path-finding]

背景
いくつかの障害物がある正方形のマップがあります。障害物はポリゴンで表されます。次のパス検索アルゴリズムを実装しまし
た。1) 精度を選択します (k で示されます)
2) マップを kxk の正方形に分割します。
3) 次のルールに従って、これらの正方形からグラフを作成します。
- すべてのノードは 1 つの正方形を表します
。
4) A* アルゴリズム (またはダイクストラなど) を使用して最短経路を検索します。

マップが動的でない場合、このアルゴリズムは非常にうまく機能します。つまり、障害物は移動できません。

質問
1) そのアプローチは効率的ですか?
2) 障害物を動かすことができる場合はどうすればよいですか?
3) 他のエージェントをどのように扱うか? 部屋に 100 人のエージェントがいる状況を考えてみましょう。2つ存在します。すべてのエージェントは 1 つのグループに属し、そのグループはいずれかの出口の近くにあります。すべてのエージェントが最も近い出口に行くと、ボトルネックが発生します。それらのいくつかは、出口に必要な時間を最小限に抑えるために、他の出口に行く必要があります。そのような結果を得るにはどうすればよいですか？

私は Postgis と pgRouting に基づいたライブラリを探しています。このライブラリは、運転ルートと任意の 2 点間のルートを提供します。2 番目の部分は pgRouting を使用して正常に動作しますが、pgRouting によって出力されたルートから運転ルートを提供するものを見つけることができないようです。そのようなプロジェクトをどこで見つけることができるか知っている人はいますか? 誰かが興味を持っているか、そのようなプロジェクトを開始するのに十分な牽引力を得ることができれば、pgRouting と一緒にそのようなライブラリを提供する新しいオープンソース プロジェクトを開始したいと考えています。

私は、ゲーム ファンサイト用のマップ ビューアー (Google マップなど) として機能する基本的な Java アプレットを作成しました。

その中で、特定のポイントで「接続」された 16 の異なるフロアを持つ 2D マップに A* パスファインディング アルゴリズムを実装しました。フロアは、必要に応じてダウンロードされ、バイト配列に変換される PNG 画像に格納されます。ノード コストはピクセル RGB 値から取得され、バイト配列に格納されます。

マップには、16 フロアにまたがる約 200 万個のタイルが含まれています。画像は 1475 x 2000 (PNG 画像の場合は 15 ～ 140 KB) の大きさであるため、一部のフロアには空のタイルが多数含まれています。

バイト配列はメモリ内で巨大になり、ほとんどの JVM 構成で「java.lang.OutOfMemoryError: Java heap space」エラーが発生します。

だから私の質問は

• これらのバイト配列のサイズを縮小し、パスファインダー機能を適切に維持する方法はありますか?
• メモリにタイルを持たずに、最適なパスを見つけるために別のアプローチを取る必要がありますか?

Web サーバーでパスを見つけるのは、CPU の負荷が高すぎると思います。

よろしく、
A

ゾンビが沼地を走り回るゲームを開発しています。AIに「このターゲットを追いかける」「逃げる」といった機能を持たせたい。主な障害はパスファインディングです。XNA に優れた経路探索/AI エンジンはありますか、それとも自分で作成する必要がありますか?

http://www.codeplex.com/simpleAIの経験はありますか?

私は、力を使って体をウェイポイントに押し込むパスファインディングを行っています。ただし、ウェイポイントに十分近づいたら、力をキャンセルしたいと思います。これどうやってするの？問題の体に加えたすべての力を個別に維持する必要がありますか？

Box2dx（C＃/ XNA）を使用しています。

これが私の試みですが、まったく機能しません。

アップデート

加えた力を追跡していると、それに作用する可能性のある他の力を考慮できません。

反射を使用して_force直接ゼロに設定することもできますが、それは汚い感じがします。

ゲームパックマンを実装したかった。AIについては、多くのフォーラムで見たA*アルゴリズムの使用を考えていました。ただし、いくつかの単純なパスファインディング（特定の障害物を挟んでポイントaからポイントbに移動）の幅優先探索を実装したところ、常に最適なパスが得られることがわかりました。単純なパスファインディングを使用するpacmanのようなゲームでは、グラフにコストの概念がないためかもしれません。それで、パックマンのパスファインディングにA *の代わりにBFSを使用しても大丈夫ですか？

このタイプのマップを Silverlight で実装するにはどうすればよいでしょうか? マップはインタラクティブで、ステーションはクリック可能です。

http://www.afn.org/~alplatt/tube.html

ブレンドで描いてみませんか？ベクター画像をインポートしますか? 経路探索アルゴリズムは駅間の距離/運賃を計算できる必要があるため、選択は非常に重要だと思います (おそらく、XY 位置に基づいて、まだ決定されていません)。

さまざまなアイデアや意見を求めているだけです。

ありがとう

AI を Flash AS3 のトップダウンの戦術戦略ゲームに組み込む必要があるクラスのプロジェクトをまとめています。

ゲームは円形の移動スキームに基づいているため、ノード ベースのパス検索アプローチを使用することにしました。プレイヤーがユニットを動かすとき、プレイヤーは基本的に、プレイヤー ユニットが従うように接続する一連の線分を描きます。

ターゲット ノードにトラバースするノードのリストを作成することで、ゲーム内の AI ユニットに同様の操作をまとめようとしています。したがって、私のAstarの使用（結果のパスを使用してこの行を作成できます）。

これが私のアルゴリズムです

現在、この関数はターゲットに対して最適ではない、または完全に不正確なパスを作成します。これは一般に、パスを使用できないノードがある場合に発生し、現在何が間違っているのかよくわかりません。

誰かがこれを修正するのを手伝ってくれたら、とても感謝しています。

いくつかのメモ

私の OpenSet は本質的にプライオリティ キューであるため、ノードをコストでソートする方法です。ここにその機能があります

ありがとう！

私の質問がかなり漠然としているように思えますが、それをより適切に表現する方法が思いつかないので、私がやろうとしていることを説明することから始めます.

私は現在、マップを与えられたプロジェクトに取り組んでおり、マップ内をナビゲートできる「Critter」をコーディングしています。クリッターには他にもさまざまな機能がありますが、それらは現在の質問には関係ありません。プログラム全体とソリューションは C# で記述されています。

クリッターの速度を制御し、現在の X および Y 位置を返すことでマップ上の現在の位置を取得できます。また、クリッターをブロックする地形と衝突したときの方向を設定することもできます。

私が抱えている唯一の問題は、地図を賢くナビゲートする方法が思いつかないことです。これまでのところ、生き物が地形に衝突したときにどの方向を向いているかに基づいて作成してきましたが、これは決してマップ内を移動する良い方法ではありません!

私はゲーム プログラマーではなく、これはソフトウェアの割り当てのためなので、AI の手法についてはまったくわかりません。

マップと生き物がどのように見えるかの画像へのリンクは次のとおりです。

地図と生き物の画像

完全な解決策を提供してくれる人を探しているわけではありません。マップ ナビゲーションの一般的な方向性を推し進めるだけです。

複雑なポリゴン（おそらく凹面）があり、そのエッジのいくつかが入口/出口ポイントとしてマークされています。このポリゴンの内部に、任意の形状の1つまたは複数の封鎖が存在する可能性があります。入口/出口エッジのペアの間に特定の幅のパスが存在するかどうかを判断するために、どのようなアプローチを使用できますか？

質問を読んだら、宿題のタイプのように見えますが、そうではありません。これは私にとって新しいことなので、私が追求できる少なくともいくつかのリードが欲しいだけです。