問題タブ [maze]

N x Mグリッド上に、1つのパスがあり、行き止まりがたくさんある単純な迷路が必要だとしますが、それは「正しい」ように見えます（つまり、小さな行き止まりがあまり多くなく、誰かが手作業で作ったように見えます。 ）。これを行うための既知の方法はありますか？

迷路を前進するのはとても簡単ですが、迷路を戻って新しいルートを試す方法がわかりません。

私は、2 人から 4 人のプレイヤーが迷路の別々のエントリ ポイントに配置され、ゴール ポイントに到達する必要がある単純なマルチプレイヤー ゲームに取り組んでいます。一般的に迷路を生成するのは非常に簡単ですが、この場合、ゲームの目標は他の誰よりも早くゴールに到達することであり、生成アルゴリズムが特定のプレイヤーを他のプレイヤーよりも大幅に優先することは望ましくありません。

だから私は迷路生成アルゴリズムを探しています。このアルゴリズムでは、各プレーヤーの開始点からゴールまでの最適なパスは、平均パスよりも 10% 以上歩数が多くなりません。このようにして、プレイヤーは多かれ少なかれ平等な競技場にいます。誰かがそのようなアルゴリズムを思いつくことができますか?

（現状では1つのアイデアがありますが、よく考えられておらず、最適とはほど遠いようです-回答として投稿します。）

C++でランダム迷路を作ろうとしているのですが、グリッドやセルの作り方がわからないので始められません。どうすれば作成できますか？また、ASCII 文字を使用して作成したいと考えています。どうすれば配列に格納できますか? (誰でもサンプルコードといくつかの説明を提供して、よりよく理解できるようにすることができます)

別の質問: どのようなデータ構造を学習して使用する必要がありますか? エラーのアルゴリズムまたはクラスカルのアルゴリズムを使用する予定です。

私を助けてくれてありがとう！私は初心者のプログラマーで、これについて学びたいと思っています。これは私のプロジェクトの一部であるためです。

C++ で迷路を表すデータ構造を作成しようとしています。

迷路について保持する必要があるすべてのデータは、(迷路の各セルを表すために) ビット演算を使用して 16 ビット整数で格納できます: _{(ソース: mazeworks.com )} 16 ビット符号なし整数

それで、私は 16 ビット整数の 2 次元配列を計算しました。これで、Maze データ構造に進むことができました。非常に密集した迷路を簡単に作成できるように、データ構造のサイズを小さくしたかったのです。

したがって、n*m サイズの 16 ビット整数の 2 次元配列を実行時に動的に作成できる必要があります。SO のどこかで、C++ の 2 次元配列は [n m] サイズの 1 次元配列の単純なシンタティック シュガーであり、*[行 + 列 * 幅] を介して要素にアクセスできることを読みました。

これが私の試みです：

C++ の知識を持っている人で、私の Maze クラスに関する提案はありますか? 私は C++ に非常に慣れていないので、これはすべて私にとって学習経験です。

迷路を解くように設計されたアルゴリズムに問題があります。

ここからアルゴリズムを使用しました。http://www.cs.bu.edu/teaching/alg/maze/

FIND-PATH(x, y)

1. if (x,y out of maze) return false
2. (x,y が目標) の場合、true を返す
3. (x,y が開いていない) の場合、false を返す
4. x、y をソリューション パスの一部としてマークする
5. if (FIND-PATH(x,y の北) == true) true を返す
6. if (FIND-PATH(x,y の東) == true) true を返す
7. if (FIND-PATH(x,y の南) == true) true を返す
8. if (FIND-PATH(x,y の西) == true) true を返す
9. ソリューション パスの一部として x,y のマークを外す
   10. false を返す

これは再帰的な解決策です。他の解決策も見つけられるように、出口を見つけた後も続行するように変更しました。私が知っている解決策の総数の半分が可能であるように見えるというだけで、うまくいくようです。

2. if (x,y is goal) return true が false を返すように変更されました。

そのようなアルゴリズムの問​​題が何であるかを知っている人は、可能なソリューションの総数の半分になりますか? 行き止まりのパスの総数を見つけるのにも問題がありますが、それに関する提案はありますか?

これは、最小限のコードで解決できる興味深い問題です。再帰的なソリューションが最も人気があると思います。

キャラクターのマップとして定義された迷路があります。ここ=で、 は壁、スペースはパス、+開始点、#終了点です。信じられないほど単純な例は次のようになります。

できるだけ少ないコードで、このスタイルの迷路を解くための最短経路を見つけるプログラムを作成できますか?

交差するパスや膨大な数の分岐があるものなど、すべての迷路入力で機能する場合はボーナス ポイントです。プログラムは大きな迷路 (たとえば、1024x1024 - 1 MB) で動作できる必要があり、迷路をプログラムに渡す方法は重要ではありません。

「プレイヤー」は斜めに移動することがあります。入力迷路には斜めの通路がないため、基本的な動きのセットは上、下、左、右になります。斜めの動きは、上下と左右がマージできるかどうかを判断するために、少し前を見ているだけです。

出力は、アスタリスク文字 ( ) を使用して強調表示された最短パスを持つ迷路自体である必要があります*。

私は迷路を与えられ、道を見つけようとするプログラムを書こうとしています。Mは入口、Eは出口、1は壁、0は通路です。各パスを見つけて、パスにPを入れることになっています。利用可能なすべてのパスを見つけることになっています。現在、パスの一部が見つかります。

コードは次のとおりです。

テスターは次のとおりです。

現在の出力は次のとおりです。

編集：if（board [x] [y] .equals（ "P"））board [x] [y] = "1"; findIndexの先頭。x<=0の問題も修正しました。出力を現在取得しているものに更新しました（実際には348枚の同様のボードを印刷しています）。

「迷路」を表すファイル内の 7x15 のテキスト ブロックを読み取るコードを書いています。

これは私の最初のドラフトでしたが、戻ってきたのでうまくいきませんでしたか? 読み取った各文字に対して。これは迷路の im テストです:

編集: cout はこれを印刷しています:

\n をエスケープしていませんか?

私は数時間コーディングを行ってきたので、今私をつまずかせているのは、私が見つけていない単純な間違いだと思います. ありがとう！