問題タブ [path-finding]

「オン」と「オフ」の 2 つの状態を持つ四角形のグリッドを使用しています。すべての「ON」コンポーネントを見つけるかなり単純な接続コンポーネントラベリングアルゴリズムがあります。通常、常にではありませんが、「ON」コンポーネントは 1 つだけです。

オン/オフ セルのマトリックス、コンポーネントのラベリング (おそらくセルのハッシュセットのリストとしてフォーマットされている)、およびラベリングが形成されてから変更されたセルのリストを入力として取り、出力するアルゴリズムを構築したいと考えています。新しいラベリング。明白な解決策は、ゼロから再計算することですが、これは効率的ではありません。一般に、変更されたセルのリストは小さくなります。

変更リストがオンになっているセルのみの場合、これは簡単に実行できます。

ただし、変更にオフになっているセルが含まれている場合、どうすればよいかわかりません。すべての ON セルは、1 つのグループのメンバーでなければならないことに注意してください。したがって、1 つの解決策は、新しくオフになったセルに隣接する各セルを取得し、それらが互いに接続されているかどうかを確認することです (たとえば、パスファインディングを使用)。これにより、1 ～ 4 個の連続したグループが生成されます (セルがそのグループ内の唯一のセルであり、チェックする隣接セルが 0 である場合を除きます。この場合、0 個のグループが生成されます)。ただし、これはゼロから始めるよりも少しだけ良いにすぎません。なぜなら、通常 (常にではありませんが) これらの隣接する正方形を一緒に接続することは、隣接するグループを見つけるのと同じくらい難しいからです (誰かがそれを行うためのスマートな方法を提案していない限り)。また、変更されたセルがたくさんある場合は少し怖いです...ただし、通常はそうではないことは認めます。

文脈、なぜ私がこれをやっているのかを知りたがっている方のために:ぬりかべパズルのルールの 1 つは、連続する壁のグループは 1 つだけだということです。私が解決しようとしている問題を単純化して、速度を上げる (そしてパスファインディングで遊ぶ) ことは上記のとおりです。基本的には、以前のこのようなテストで得られた情報を無駄にすることなく、隣接する壁をチェックしたいと考えています。O(f(Δ)) が O(f(Δ)) (N はパズルのサイズで、Δ はアルゴリズムが最後に実行されてから行われた変更です)。

プロファイリングは、このアルゴリズムを改善すると実行時間に違いが生じることを示していますが、これは利益のためではなく楽しみのためのプロジェクトであるため、変更が何らかの影響を与えたかどうかを測定できることを除いて、それほど重要ではありません.

注: 現在のアルゴリズムの説明は省略しましたが、基本的には、最初に見つかった ON の正方形に対してスタックベースのフラッド フィルアルゴリズムを実行し、さらに ON の正方形があるかどうかを確認します (つまり、複数の正方形があることを意味します)。グループであり、調べる必要はありません)。

編集: 機能強化のアイデア: Yairchu と John Kugelman の提案は、私の頭の中でこの改善に具体化されました。これは、実際にはこの問題自体の解決策ではありませんが、コードのこの部分と他のいくつかのコードの実行を高速化する可能性があります。

現在のループ:

改善案:

これには、いくつかの m.NeighborsXX インスタンス (強化する必要のあるマッチの種類ごとに 1 つ) を維持し、正方形が変更されるたびにすべてを更新する必要があります。これが実際に役立つかどうかを確認するには、これをベンチマークする必要がありますが、速度を犠牲にしてメモリを交換する標準的なケースのようです。

少し前にJava2Dパスファインディングについて質問しました...パスファインディング2DJava ゲーム？

開発中のゲームは、テーマホスピタルのアイデアに基づいています。私の質問から選ばれた答え、A *パスファインディング、リンクは素晴らしく、とても役に立ちました。最終的にはこれをゲームに実装するようになりますが、それに関してさらにいくつかの質問/問題があります。

私のゲームでは、マップが変更されます。チュートリアルでは、マップが静的であると想定しています（私は思います）。私はコードを見てきましたが、うまくいく限り、パスファインディングコードでゲームマップを更新するために呼び出すメソッドを作成する必要があります。

次に、GameMapクラスが表示されます。私はすべてのタイルを収容するボードと呼ばれる私自身のクラスを持っています。GameMapのメソッドをBoardクラスに統合できると思います。右？

第三に、私はどの部屋もブロックされていると見なされるという推論に取り組んできました。つまり、部屋が覆っている正方形はすべてブロックされたものとして数えられます。人々が部屋に入る場所を前もって考えていました。その後、さまざまな場所に移動するために、これらの部屋を移動する必要があります。正方形ごとにBlockedブール値を反転するだけだと思っていましたが、2つの理由で機能しませんでした。1、部屋には隣接する壁があり、パスファインディングを台無しにする可能性があります。2、ブロックされた状態が単純に反転された場合、部屋の固体アイテムは、反転されたときに固体ではないと見なされ、壁に触れているときに問題が発生する可能性があります。

考えてみると、実際の正方形全体ではなく、正方形の辺をブロックしたほうがいいと思います。これは可能である必要がありますが、前の質問のチュートリアルを使用して取得しているだけで、これを行うためにA *を変更するか、ルームアイテムの問題の回避策に取り組む必要があるかわかりません。

これらの問題のいずれかについての考えや提案はありますか？今日は簡単なパスファインディングを実装していますが、自分の前で考えています。

私は単純な2Dグリッドベースのシミュレーションゲームを開発中であり、完全に機能するパスファインディングを持っています。

前の質問で見つかった回答を、A*パスファインディングを実装するための基礎として使用しました。（パスファインディング2D Javaゲーム？）。

私が本当に求めていることをあなたに示すために、私が作ったこのビデオスクリーンキャプチャをあなたに示す必要があります。私はちょうどその人がどのように場所に移動して戻ってくるかをテストしていました、そしてこれは結果でした...

http://www.screenjelly.com/watch/Bd7d7pObyFo

方向によってパスの選択が異なり、予期しない結果になります。何か案は？

大規模で動的な無向グラフを Google appengine に保存する必要があります。これを行う最善の方法は何ですか? グラフ表現は、一連の頂点 (ページ上でのレンダリング用) と特定の頂点からのすべてのリンクの迅速な引き出し、およびグラフ全体のパスファインディングをサポートできなければなりません (ただし、最適なパスは実際には必要ありません。良いもの）

この件に関する私の考え: 最も明白な方法は、頂点モデルと、2 つの頂点を参照するエッジ モデルを使用することですが、それでは、すべての操作に対して非常に多くのクエリを使用することになるように思えます。より良い方法があります（リンク情報を各頂点に何らかの方法で構築するかもしれません）

さて、これは宿題の質問です。どのように始めればよいかわかりません。いくつかのヘルプとヒントをいただければ幸いです。

迷路タイプの問題を解決するには、ヒューリスティック関数を使用する必要があります。

5x5 のグリッドがあり、ロボットが (1,5) の位置にあり、ロボットを (5,1) に移動することが目標であるとします。道に沿っていくつかの障害があり(X,1,3)ます(X,2,3)。(X,5,3)(X,4,2)

ロボットが通過したルートを印刷します。

貪欲な最良の最初の検索アルゴリズムを使用して、ロボットがゴールまでの経路を見つけることを考えています

私の問題は、私はスキームに慣れていないため、このような問題の解決をどのように開始すればよいかわかりません。

するべきか ？

この問題を解決するために ？

グリッドを作成するにはどうすればよいですか? この問題にどのようにアプローチすればよいですか? ロボットが移動するステップを印刷するにはどうすればよいですか?

助けていただければ幸いです:)

私は、最小コストのルートを見つけるためにパスファインディングを実行する必要があるプロジェクトに取り組んでいます。最短ルートで構いません。これまでのところ、A* は問題外のようで、正直に言って Prim のアルゴリズムを理解していません。

ルートを見つけるために必要な地図の種類について説明しましょう。これはマップの例です:

「*」は出発地、「@」は目的地です。行内の「+」記号は、a) 1 つのステップと同じコストがかかり、b) ルート全体のコストが半分になる直接ルートを示します。

これは、開始位置から「+」ルートを経由して目的地まで 10 の「ステップ」があることを意味し、最終的にコストは 5 になります。左端の「|」を使用するには 15 のステップがあります。ルート (「|」は「-」よりも低コストですが、「+」よりは劣ります)、最終的にコストは 15 になります。明らかに、コストが 5 のルートが使用するルートです。

現在、これを C# で実装するのに問題があります。私は現在、方法がブロックされた場合、またはステップのコスト、および新しい位置に移動して戻る「ステップ」機能を持っています。これはうまく機能しますが、現時点では「|」で終わるという点で非常に単純です。「+」の前に見つかった場合 (より速いルートが見つからないため、移動全体の費用が大幅に高くなることを意味します)。

各場所を「訪問済み」としてマークすることを考えていましたが、最低コストのルートがループバックすることは完全にありえます。また、多くの異なるパスがあり、それぞれが一意であり、それぞれが異なるパス セグメントを使用する場合があります (以前の実行で既にアクセスされている可能性があります)。明らかに、最も安価なパスを見つけるために各パスをたどる必要がありますが、同じルートを何度も何度も検索することなしにそれを行う方法を理解することはできません.

より簡単にする場合は、移動を目的地に向かってのみに制限できます (つまり、下降した後に再び上昇することはできません)。

誰かが洞察を提供できれば、それは素晴らしいことです!

次のように格納されている配列があります。

特定の ID へのルートを見つける簡単な方法を見つけようとしています。現在、foreach を使用して、考えられるすべての配列を反復処理し、ルートを見つけています。

例：

私の質問が意味をなさない場合は、それに対する適切な解決策を見つけるのに何時間も費やしたせいだと思います...

ルーティング関数を作成しようとしていますが、必要な結果が得られないようです。これがこれまでのコードです。先行者は、N にリンクされているノードを見つけて、それを P として返します。

実行すると、traceroute(placeA, Y).このデータが返されます.. Y = [ (_G575, _G575)|_G579] .

基本的に、traceroute の最初の行では、いずれかのメンバーがそれ自体の先行者である場合、再帰を終了しようとしています。2 番目の部分は、すべてのノードをループし、それらをリスト (L) に追加する必要があります。

ノードは [(placeA,placeB),(placeB,placeC)] のように保存され、リストは [placeA,placeB,placeC] のように保存する必要があります

なぜこれらの結果が得られるのか理解できません。

AIMA ( Artificial Intelligence: A Modern Approach ) のアルゴリズムの説明はまったく正しくありません。「必要」とはどういう意味ですか? メモリ制限とは何ですか? キューのサイズまたは処理されたノード? 現在のノードに子がまったくない場合はどうなりますか?

このアルゴリズム自体が正しいかどうか疑問に思っています。私はインターネットを検索しましたが、まだ誰も実装していません。

ありがとう。

(これはまさに私が抱えている問題ではありませんが、同形であり、この説明が他の人にとって最も理解しやすいと思います。)

n次元空間に一連の点があるとします。たとえば、3 次元を使用すると、次のようになります。

この空間で可能な動きを表す一連のベクトルもあります。

次に、点destが与えられた場合、最も効率的な方法で dest に移動する開始点pと一連のベクトル移動を見つける必要があります。効率は「最小の移動数」として定義され、必ずしも「最小の直線距離」ではありません。移動セットがより少ない移動でそこに到達できるようなものである場合、他の候補よりもdestから離れたpを選択することは許容されます。移動中のベクトルは、使用可能なベクトルの厳密なサブセットでなければなりません。入力セットに複数回出現しない限り、同じベクトルを複数回使用することはできません。

入力には ~100 個の開始点とおそらく ~10 個のベクトルが含まれており、次元数は ~20 です。開始点と利用可能なベクトルは、アプリの存続期間中固定されますが、非常に多くの異なる目的地へのパスを見つけます。メモリではなく速度を最適化したい。アルゴリズムが失敗することは許容されます ( destへの可能なパスが見つからないため)。

承認されたソリューションで更新

以下で「承認済み」とマークされているものと非常によく似た解決策を採用しました。すべてのポイントとベクトルを繰り返し処理し、到達可能なすべてのポイントのリストとそれらに到達するためのルートを作成します。このリストを < dest , p+vectors >のハッシュに変換し、目的地ごとに最短のベクトル セットを選択します。(ハッシュ サイズの最適化も少しありますが、ここでは関係ありません。) 後続のdestルックアップは一定の時間で発生します。