問題タブ [path-finding]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票する
1 に答える
761 参照

c - グリッドを逆の順序でたどるボット

私はCだけでプログラムを書くことになっています。グリッドフォロワーのコードです。

グリッドの座標系(0-5,0-5)を定義しました。また、ボットの向き(+ y、-y、+ x、-x)と位置も定義されています。(このための適切なコードを作成する方法に関するヒントを歓迎します。)

ボットがグリッド内を移動し、パスを介してグリッド内の座標(x、y)に移動すると、90度と180度の回転のみが許可されます。

同じパスを通過して、(0,0)、つまり開始点に到達するにはどうすればよいですか?方向を逆にして、Cコードを使用して適切な回転指示を与えるにはどうすればよいですか?

0 投票する
2 に答える
5464 参照

algorithm - 最速パスアルゴリズム

私は現在、ヨーロッパを経由するためのナビゲーションシステムを実装しています。これまでのところ、最短経路を実装しています(ダイクストラとA *)。それは簡単な部分でした、今私は最速のパスのためにいくつかのアルゴリズムが必要です。それは速くて信頼できるものでなければなりません。

道路の品質(たとえば、高速道路1つ、幹線道路2つなど)に値を割り当て、これらの値にルートコストを掛けて、最終的にダイクストラまたはA *を使用するだけで実行できることはわかっていますが、十分に洗練されていません。

より正確なアルゴリズムを探しています。地図自体には、道路の質、制限速度、信号機の位置など、あらゆる種類のデータが含まれているので、それを利用したいと思います。

これに適したアルゴリズムはありますか?または、少なくともA *の適切な変更ですか?

0 投票する
1 に答える
349 参照

path-finding - 一連のポイント間のパスを見つける

私の単純なプロジェクトで使用するために、私は少し封鎖しました。

グリッドには、「壁」と「オープンスペース」という一連のポイントがあります。グリッドの外側のスペースは壁と見なされます。このグリッドには任意の数の開いているポイントがあり、グリッド内の1つの特定のブロックをオープンスペースから壁に変更した場合に、接続されているポイントが変わるかどうかを判断する必要があります。

これを行うための効率的な方法は何ですか?

例

例:緑の正方形が壁またはオープンスペースの場合、赤い正方形の間のパスの有無が変わるかどうかを判断します。(追記:ひどいグリッドについて心からお詫び申し上げます)

今のところ、ある種のセルオートマトンが最適だと思いますが、よくわかりません。私は以前にパスファインディングを見たことがありますが、この種の問題に巻き込まれたものは実際には見たことがありません。

注意:パスの長さは関係ありません(最大長はわかっています)。パスは存在する必要があります。したがって、ポイント間の最適なパスを見つける必要はありません。

ああ、それは問題ではないはずですが、私はこのプロジェクトをJavaで書いていますが、任意の言語(または擬似コード)またはアルゴリズムの英語の説明で十分です。(私はほとんどのCurly Bracket言語を知っていますが、HaskellとLISPは限られていますが、すべて知っています。)

0 投票する
3 に答える
2448 参照

c# - 多次元配列でのパスファインディング

私は、パスファインディングの概念と、プログラムが最も効率的な方法でポイントAからポイントBを探す方法を理解しており、A*の概念に漠然と精通しています。しかし、迷路を通り抜ける方法を見つけるのではなく、閉じた迷路の中で、廊下を対角線上に置くことができない最長の廊下を見つけようとしている場合はどうでしょうか。

これが私の迷路の例です:

許可されたパスとして1を使用し、無効なパスとして0を使用する場合、最長のパスは5で、座標は(0,3)、(1,2)、(1,3)、(2,2)、(3、 2)。

この情報を再帰的に見つけるにはどうすればよいですか?

私は(0,0)から始めて、上、下、左、右に移動して、それらが可能な動きであるかどうかを確認する方法について頭を悩ませてきましたが、私が思いついたバージョンでは、重複と繰り返しのカウントが発生します。

0 投票する
2 に答える
421 参照

objective-c - パスファインディング/方向の決定

cocos2d-iphoneを使って簡単なiPhoneゲームを作っています。私は、障害物でいっぱいのフィールドをナビゲートしなければならない「fiendSet」という一連のフィーンドを持っています。私は最後の3泊を過ごして、A*パスファインディングを機能させようとしました。私はここで実際のA*実装をstackoverflowで見つけました、そしてそれは見事に機能します。しかし、フィーンドを動かそうとすると、問題が発生します。

私の各フィーンドには、モーションターゲットと呼ばれるCGPointがあり、フィーンドが移動する場所のx値とy値が含まれています。位置xとyを1秒に1回だけ絶対値に設定すると、次のように機能します。

ただし、これはあまり見栄えがよくありません。悪鬼は、うまくアニメーション化するのではなく、毎秒20pxだけ「ジャンプ」します。パスファインディングを検証するためのプレースホルダーメソッドとしてのみこれを実装しました。今、私はスムーズなアニメーションが欲しいです。これは私がしたことです:

これは、一方向に移動するフィーンドに最適です。悪鬼が曲がり角を曲がるはずだとすぐに、トラブルが始まります。たとえば、最初に上に、次に右に、次に下に行く代わりに。私の悪鬼は上/右の動きを1つに結合します、彼らは「角を切ります」。位置が更新されるたびに、フィーンドを北/南または東/西のいずれかに移動させたいだけです。両方ではありません。つまり、xとyへの変更を同時にアニメートしたくありません。この説明が十分に明確であることを願っています。

私はどこかに論理エラーがあると確信しています..私は仕事の後の最後の3つの眠れない夜の間それを理解することができませんでした..助けて!

0 投票する
1 に答える
44 参照

wcf - wcf とパスファインディング

一般的に、これらの 2 つの単語が同じ文章で一緒に表示されるとは思いませんが、複数の道路で簡単なパスファインディングを行う必要があるプロジェクトに取り組んでおり、それを行うための最良の方法を見つけようとしています.

私はもともと、出発地と目的地を受け入れてそこで作業を行い、結果を送り返すことができるいくつかの wcf サービスを用意することを考えていました。ただし、データはすべてデータベース内にあるため、理想的にはメモリ内のすべてのルートが必要です。そうしないと、非常に遅くなります。それはできますか?

0 投票する
5 に答える
4661 参照

heuristics - グリッドレス2D平面でA*パスファインディングアルゴリズムを使用するにはどうすればよいですか?

ノードやセルのないグリッドレス2D平面にA*アルゴリズムを実装するにはどうすればよいですか?ゴールの邪魔になる比較的多数の静止した障害物や移動する障害物を回避するためのオブジェクトが必要です。私の現在の実装は、オブジェクトの周りに8つのポイントを作成し、それらをオブジェクトの潜在的な位置である可能性のある想像上の隣接する正方形の中心として扱うことです。次に、それぞれのヒューリスティック関数を計算し、最適なものを選択します。始点と移動点の間、および移動点と目標の間の距離は、ピタゴラスの定理を使用して通常の方法で計算します。問題は、この方法では、オブジェクトがすべての障害物を無視することが多く、2つの位置の間を行ったり来たりするときにスタックすることがさらに多いことです。ばかげたmuの質問がどのように見えるかはわかりますが、どんな助けでもありがたいです。

0 投票する
3 に答える
2247 参照

algorithm - メモリに完全に収まらない行列での経路探索の最適アルゴリズム

私は難しい問題に直面しています:

セルの巨大な行列で表された国全体の地図があるとします。各セルは、1 平方メートルの領域を表します。各セルはdouble、セルを通過するコストを表す 0 ~ 1 の値として表されます。

マップは明らかにメモリに収まりません。

始点から終点までのロボットの最適な経路を計算する方法に頭を悩ませようとしています。私が最初に思いついたのは、TCP のような移動ウィンドウを作成し、移動ロボットの周りに実際のマップのミニマップを配置し、その中で A* アルゴリズムを実行することでしたが、巨大な壁のあるマップでいくつかの問題に直面しています。パスファインディングなど...

A* のようなアルゴリズムに関する文献を検索していますが、この問題の適切な解決策を視覚化できませんでした。

誰かが同様の問題に直面したか、解決策のアイデアを手伝ってくれるかどうか疑問に思っています!

前もって感謝します :)

0 投票する
2 に答える
1144 参照

python - py-appscript 経由で Path Finder のファイル選択にアクセスするにはどうすればよいですか?

mac os x で filemanager Path Finder を使用して、選択したファイル/フォルダーをpy-appscriptを使用して python で取得したい。py-appscript は、Python からスクリプト可能な Mac OS X アプリケーションを制御できる高レベルのイベント ブリッジです。

Applescriptでは、次のようになります

Pythonでは、代わりに次のようなものになります

では、selection_list の参照を python-strings に変換するにはどうすればよいですか?

0 投票する
2 に答える
1174 参照

python - 地図の作成とパスファインディングAI

グーグルアースから地図をたどりたいのですが、これらの地図は、AからBへの最速ルートと、いくつかの要因によって定義された位置確率を計算するために使用されます。これらをどのように行うのですか?私の最初の考えはpygameで、すでに作成されているものを使用するか、それらをテンプレートとして使用します。