問題タブ [maze]

DFS、BFS、および A* 検索アルゴリズムに開いた迷路または閉じた迷路を使用した場合の結果の変化を知りたいですか? 拡張ノード数の増加、コストなど、出力に大きな違いはありますか?

私は、左手の法則を使用して迷路を横断する必要があるプロジェクトに取り組んでおり、プログラムが遭遇する交差点に基づいて、グラフに接続するノードを作成する必要があり、それから最短経路を決定します。目標は、プログラムが迷路を通過してからプログラムを終了し、グラフを含むファイルから読み取り、ゴールまでの最短経路を決定することです。私がやったことは、左手の法則を使用して迷路を横断できることです。私が考えているのは、交差点を見つけたときにノードを作成し、その後プログラムが移動するたびにそのパスのコストを1ずつ増やすことです。余談ですが、ダイクストラのアルゴリズムを使用する場合、隣接行列が必要ですか?

ユーザーが迷路の中をボールをナビゲートする必要がある単純な2Dゲームを作成したいと思います（もちろん、加速度計を使用します）。シンプルなビューを使用して、加速度計を使用し、画面上でボールを動かしました。では、迷路を構築するにはどうすればよいですか？cocos2dなどを使用する必要がありますか？ボールが迷路の壁に当たったときにボールを停止またはリバウンドさせるにはどうすればよいですか？

セルが0または1であるMxNビットマップについて考えてみます。「1」は塗りつぶされ、「0」は空を意味します。

ビットマップ内の「穴」の数を見つけます。ここで、穴は空のセルの連続した領域です。

たとえば、これには2つの穴があります。

...そしてこれには1つしかありません：

MとNが両方とも1から8の間にある場合、最速の方法は何ですか？

明確化：対角線は隣接しているとは見なされず、隣接関係のみが重要です。

注：データ形式を利用するものを探しています。これをグラフに変換して[BD]FSする方法は知っていますが、それはやり過ぎのようです。

ねえ、私は地元のプログラミングコンテストに参加していて、彼らは私にこの質問をしましたが、私にはできませんでした。この質問について私を助けてください。

ファイルから迷路のサイズをロードし、次に迷路自体をロードするプログラムを作成します。迷路をモデル化するために、開始セル「。」を指定する文字「S」を使用します。これは空きセルを指定し、「＃」は壁、「F」は最後のセルです。開始セルから最終セルへのパスを見つけるプログラムを作成します。迷路の中にはコマンドに従うロボットがあると考えることができるので、次の迷路では、ロボットは次のコマンドを受け取る必要があります：上、上、右、右、下、下。

迷路1テキストファイル

迷路2テキストファイル

一般的にプログラムを作成します（迷路の最大入力は最大200x200です）。

助けていただければ幸いです。私は新進気鋭の2年生なので、コードを提供していただければ、私はそれを理解でき、彼らは自分でそれをやり直します。

以下のsudoコードを使用して左手の出口ルールを使用して迷路を解こうとしていますが、ほとんど機能していますが、行き止まりにぶつかって戻ってきたときに新しい方向を選択することに問題があります(上が真であるが左、下、右の壁が偽である正方形の場合、最初のフェーズでコードが正しく移動し、エントリが下または右の2つのいずれかに左に移動した場合、戻ってきたときに左が選択されます下ではなく方向、下を選択するにはどうすればよいですか）。

誰かが新しい方向を選択する方法について私にアドバイスできますか - 私はあなたの参考文献のために問題の方法の周りに二重アスタリスク (**) を入れました。

再帰的バックトラッカー アルゴリズムを実装して迷路の問題を解決したいのですが、2.3 コマンド (「現在のセルと選択したセルの間の壁を取り除く」) が理解できません。

1. 現在のセルを「訪問済み」としてマーク
2. 現在のセルに訪問されていない隣接セルがある場合
   1. 未訪問の近隣の 1 つをランダムに選択する
   2. 現在のセルをスタックに追加する
   3. 現在のセルと選択したセルの間の壁を取り除く
   4. 選択したセルを現在のセルにする
   5. この関数を再帰的に呼び出す
3. そうしないと
   1. スタックから最後の現在のセルを削除します
   2. この関数の前の実行に戻る

編集 実際、スタックを使用して迷路の問題を解決するアルゴリズムが必要です。

私はクラスで行っているJAVAの迷路ゲームを持っています。迷路はアプレットの帆布で作られています。私に提供された別の写真（彫像のようなもの）をゲームのキャラクターとして機能させて、矢印キーで迷路の周りを移動するので、移動したり制御したりできるオブジェクトをキャンバスに配置するにはどうすればよいですか？現時点では、迷路に彫像を配置する唯一の方法は、画像のピクセルを迷路にコピーすることでした。そのため、現在は背景の一部にすぎません...助けてください！私は役に立たない助けを探してどこにでも投稿してきました。

私はさらに別の迷路ゲームを作成するという考えを持っています. ただし、重要な違いがあります。迷路はゲーム中にオンザフライで変化します。この問題について考えると、次の制限が頭に浮かびます。

1. 迷路には変わることのないメインルートがある
2. メインルートはフィニッシュにつながる唯一のルートです
3. 迷路の突然変異は、メイン ルートに戻るパスをブロックしてはなりません

また、制御するのも良いでしょう (ゲームの難易度に影響します):

1. 1回の突然変異で迷路がどれだけ変化するか
2. 必要に応じて、制限 #3 を無効にします (つまり、プレーヤーはしばらく迷路でブロックされる可能性があります)

編集: 質問は: 指定された制限に違反しない、説明された迷路の生成/突然変異のアルゴリズムを提案 (またはアイデアを提供) できますか?

迷路 (NxN 配列) を表示するのに適切な gui ライブラリと、そのセルの状態を表す色で各セルを塗りつぶすことができるか疑問に思っていました。また、迷路のある部分から別の部分へのパスを生成し、そのようなパスを表示したいと考えています。

これには、Gui フレームワークを選択する必要があります。助言がありますか？