問題タブ [maze]

私がやろうとしているのは、最短経路を使用してゴールに到達するまでに何回移動する必要があるかを数えることです。これは、幅優先検索を使用して行う必要があります。8x8 グリッドを 2 次元配列に入れ、4 つの文字のいずれかで満たされます。E は空 (これらのスポットに移動できます)、B はブロック (ここでは移動できません)、R はロボット (開始点)、または G です。ゴールのために。アルゴリズムは、可動スペースを上、左、右、下の順にチェックする必要がありましたが、これは正しく行ったと思います。ノードがチェックされると、その内容が「B」に変わります。目標に到達できない場合は、0 を返す必要があります。

Kshitij が私に言ったことを実装するためにコードを変更しました。新しいデータ セットが作成されるたびに、キューを初期化していないことに気がつきませんでした (笑)。助けてくれてありがとう！

壁やオープンスペースなどの値を保持するために列挙型を使用して迷路ゲームを作成していますが、このコードが機能しない理由がわかりません。新しいボードを作成し、すべてを開くように設定してから、通過します。アレイ内のスポットにランダムに値を設定します。

タワー ディフェンス ゲームでは、開始点、終了点、壁の数を含む NxM グリッドがあります。

敵は最初から最後まで壁を通過せずに最短経路をたどります(通常、敵はグリッドに拘束されていませんが、簡単にするために拘束されているとしましょう。どちらの場合も、斜めの「穴」を通過することはできません)。

問題(少なくともこの質問では)は、最大K 個の壁を追加して、敵がたどらなければならない経路を最大化することです。たとえば、K=14 の場合

私の直感では、(私が望んでいるように)フィニッシュに移動する前に訪問しなければならないウェイポイントを含むようにこれを一般化すると、この問題は NP 困難であることがわかります。

しかし、最適に近い解決策を見つけるためのまともなヒューリスティックはありますか?

[編集]関連する質問をここに投稿しました。

迷路の垂直壁と水平壁を参照して、2 セットのブール配列で構成される 2D 迷路を作成しました。この迷路は現在 12 x 12 ですが、5 x 5 のみを表示したいと考えています。

迷路をユーザーがいる場所の 5 x 5 の周囲にズームし、移動するたびに次のブロックを表示するだけで、5 x 5 のみを表示する方法はありますか?

理想的には、全体を描画してから、鳥瞰図ズームを使用することに固執したいと考えています (これにより、使いやすさが向上し、一般的にアプリが高速化されます)。

編集 以下は、迷路を描くために現在使用しているコードです。ただし、ユーザーの円を移動すると、以下のコードは正しい v と hLines を描画していないようです。

注 - mazeSizeX と Y は最初は 5 に設定されています。

編集 2: 下の画像を参照して、私が抱えている問題をさらに説明するためにユーザーが実行した可能性のある 3 つの異なる手順を示してください。最初の画像は開始点であり、必要に応じて描画されていますが、ユーザーの円を線の周りに移動し始めると、正しく描画されません。

最後に、Waze の壁を描画するために使用している現在のブール配列を以下に示します。

前もって感謝します

私は迷路生成アルゴリズムを書いていますが、このウィキペディアの記事が私の目に留まりました。私はそれを Java で実装することにしました。私が抱えている問題は、迷路のような画像が生成される一方で、迷路が解けないことが多く、面白くないことが多いということです。興味深いとは、到達できない場所が膨大にあり、多くの場合、多くの解決策があるということです。

私は 1234/3 ルールを実装しました (これは簡単に変更できますが、説明についてはコメントを参照してください)。迷路は常に、t ステップ間で変化がない平衡状態に達します。

私の質問は、固定された開始点と終点から迷路の解決可能性を保証する方法はありますか? また、迷路を解決するのをより面白くする方法はありますか (より少ない/1 つのソリューションと、到達できない場所がほとんど/まったくありません)。これがセルオートマトンで不可能な場合は、教えてください。ありがとうございました。

C++ で迷路を解くためにこの関数を使用していますが、プログラムを実行すると、再帰で Bad Access Error が発生します。たぶん無限ループだと思います。どこで何が問題になっているのかわかりません。

迷路のデータ構造をグラフに変換しようとしています。迷路は、グリッドとセル間のいくつかの壁のようなものです。

この迷路をグラフに変換したいのですが、どうすればよいですか?

私は、迷路をうまく通り抜けることができる再帰的な迷路ソルバーアルゴリズムを持っています。唯一の問題は、始点と終点の間の最短経路を保存する方法が見つからないことです。最短経路の座標を保存するにはどうすればよいですか?

これが再帰関数です

座標を格納するためのベクトルを追加した後、この出力を得ました

すべての座標を保存しますが、取りたくないパスの座標も保存します ((7,2)(8,2)(9,2) から (7,3) に戻る)。最短パスを保存するだけで保存できる方法はありますか?

ミニプログラムは、迷路を通るすべての可能なルートを印刷することになっています。ここで、入口/開始点は常に左上隅から1つ下にあり、すべての可能な出口は常に右の壁にあります。テキストファイルから迷路を取得します。

迷路は実際には単なるテキストの集まりです。迷路は、壁である「＃」記号で構成されるnxnグリッドと、歩行可能な領域/パスを表すさまざまな文字[a...z]で構成されます。文字は繰り返すことができますが、並べることはできません。

迷路は15x15です。

大文字のSは常に入り口にラベルを付け、2番目に高い場所の左側の壁にあります。可能なパスは文字のみです-＃記号の上を歩くことはできません。右側の壁にある文字はすべて出口を表しています。

例えば、

迷路の可能性があります。私の小さなプログラムは、実際に迷路を含むテキストファイルを読んだ後、すべての可能なルートを印刷することになっています。

プログラムを呼び出すと、画面に次の出力が生成されます。

これをやってみませんか？完全なコードの答えは必要ありません。この問題に取り組む方法についてのガイダンスが必要です。

これまでのところ、隣接する正方形を再帰的にチェックしてそれらの上を歩くことができるかどうかを確認する実際のアルゴリズム自体を除いて、すべてを実行しました。複数のパスでどのように作業するかわかりません。

これは私がこれまでに持っているものです（パスチェックが間違っていることは知っていますが、他に何をすべきかわかりませんでした）：

ありがとう！

私のC++vec割り当てでは、基本的に、左側の2番目の上の文字から始まるテキストファイル（ベクターにストリーミングされる）内のテキストのチャンクを検索しようとしています。それはテキスト迷路のためのものであり、私のプログラムは最終的にそれを通るパスの文字を印刷することになっています。

迷路の例は次のようになります。

ここで、「＃」は歩けない壁であり、常に左側の2番目の上の文字から開始します。アルファベット文字は歩きやすい正方形を表します。出口は常に右側にあります。迷路は、maze.textファイルでは常に15x15サイズです。アルファベットの文字は同じ迷路の中で繰り返されますが、互いに直接並んでいるわけではありません。

私がここでやろうとしているのは、現在の正方形の隣の正方形にアルファベット文字がある場合、それをベクトルに追加しvec、迷路の終わりに到達するまでこのプロセスを繰り返します。最終的には、いくつかの迷路に存在する複数のパスを画面に印刷することで、これをより複雑にすることになっています。

これまでのところ、アルゴリズム自体にこれがありますが、これは間違っていることがわかっています。

visited訪問した正方形を追跡する私のベクトルです。

これを更新して実際に機能させ、最終的に複数のパスを管理できるようにするにはどうすればよいですか（つまり、パスが2つある場合、プログラムは両方のパスを画面に出力します）。すでにアクセス/チェックした正方形を追跡する別のベクトル/配列が必要になる可能性があると言われたことを思い出しますが、それをここで正確に実装するにはどうすればよいですか？