遠隔操作による経路探知

Question

私は、ロボットが迷路の中にいて、そこをナビゲートしなければならない仮想ロボット（ComputerCraft mod for MinecraftのTurtles）を使ってプロジェクトを進めています。世界は既にタイルに分割されています（それぞれの2Dカルテシアングラフ、それぞれにブール値の可/不可値があります）。トンネルを構築しているロボットは、移動中にそれらをマップします。

さらに、ロボットがそれらの間をすばやく移動する必要がある領域には、テレポータ「ショートカット」が散在しています。

質問は次のとおりです。ロボットを目的地まで誘導するにはどうすればよいですか？テレポーターを必要とする領域をシステムがどのように特定していますか？ A *は最も有名なアルゴリズムですが、アプリケーションに適したアルゴリズムがありますか？私はpathfindingアルゴリズムの経験がほとんどないので、理解するために基本的な用語に分解しなければならないかもしれないことに留意してください。助言がありますか？

Answer 1

A *を使用する場合の唯一の問題は、問題のadmissible heuristicを見つけることです。幸いにも、これはすでにhereと答えられています。

テレポーターが必要な領域をシステムがどのように特定しますか？

これは、カメの実際の移動先によって異なります。彼が常に同じスタート/エンドポイントに移動している場合、その答えは簡単です：開始時にテレポートを追加して終了します。より複雑な設定では、これはNPハードであると私は推測します。もし真実ならば、global-optimization strategiesを調べなければなりません。（またはランダムな位置をとり、最良のものを取ってください）。