この記事では、「理想的な」迷路を生成するための最も簡単なアルゴリズムと、パスを見つけるためのそのアプリケーションについて説明します。
バックトラッキングベースのアルゴリズムを検討します。このアルゴリズムを使用すると、2つのポイント間に単一のパスを持ち、サイクルなしで迷路を作成できます。 アルゴリズムは
、オイラーまたはクラスカル
アルゴリズムと比較し
て 、最速ではなく、むしろリソースを要求し
ますが 、実装が非常に簡単で、非常に長い行き止まりのブランチを持つブランチラビリンスを作成できます。
興味のある人-猫をお願いします。
ロシア語のインターネット上の迷宮生成アルゴリズムに関する情報はほとんどありません。これがこの記事を書いた理由です。
CコードサンプルとGitHubプロジェクトの完全なソースコードは、GNU GPLv3ライセンスで利用できます。
英語のリソースおよび記事の最後にあるプロジェクトへのリンク。
アルゴリズムの説明
注：最初は、各セルには4つの側面すべてに壁があり、隣接するセルから分離されていると想定されています。
1.初期セルを現在のセルにし、訪問済みとしてマークします。
2.未訪問のセルがある限り
1.現在のセルに未訪問の「隣人」がある場合
1.現在のセルをスタックにプッシュします
2.隣接するセルからランダムなセルを選択します
3.現在のセルと選択したセルの間の壁を削除します
4.選択したセルを最新にし、訪問済みとしてマークします。
2.それ以外、スタックが空でない場合
1.スタックからケージを引き出します
2.最新の状態にする
3.それ以外の場合
1.未訪問のランダムなセルを選択し、現在のセルにし、訪問済みとしてマークします。
おそらく、条件3が満たされると、完成した迷路には孤立した領域があることに気づくでしょう。
この条件は例外としてアルゴリズムに含まれています;実際には、アルゴリズムの正常な動作中および正しい初期データでは、決して満たされません。
実装
前述のように、アルゴリズムの開始時には、すべてのセルが壁で区切られていると想定されています。
アルゴリズム操作図
0。
<-初期行列。
1。
<-開始点の開始点を選択します。
2.1。
<-ランダムに訪問されていない隣人に移動しますが、隣人はいます。
2.2。
<-訪問者なし。 招待されていない隣人がなくなるまで、スタックに沿って戻ります。
2.1。
<-訪問されていない隣人がいます。 ランダムに訪問されていない隣人に移動します。
2。
<-未訪問のセルはありません。 ラビリンスが生成されました。
プログラムコード
楽しい部分に到達します。
順番に始めて、最初にアルゴリズムが機能する初期行列を生成しましょう。
便宜上、すべてのタイプのセルが列挙で指定されることに同意します。
int maze[height][width]; // - for(i = 0; i < height; i++){ for(j = 0; j < width; j++){ if((i % 2 != 0 && j % 2 != 0) && // x y, (i < height-1 && j < width-1)) // maze[i][j] = CELL; // else maze[i][j] = WALL; // . } }
すべての準備が完了したので、世代に進むことができます。
typedef struct cell{
構造体は、機能間で情報を交換する際の生活を大幅に簡素化します。
生成を担当するコードスニペット：
cell startCell = {1, 1} cell currentCell = startCell; cell neighbourCell; do{ cellString Neighbours = getNeighbours(width, height, maze, startPoint, 2); if(Neighbours.size != 0){ // randNum = randomRange(0, Neighbours.size-1); neighbourCell = cellStringNeighbours.cells[randNum]; // push(d.startPoint); // maze = removeWall(currentCell, neighbourCell, maze); // currentCell = neighbourCell; // maze = setMode(d.startPoint, d.maze, VISITED); free(cellStringNeighbours.cells); } else if(stackSize > 0){ // , startPoint = pop(); } else{ // , , cellString cellStringUnvisited = getUnvisitedCells(width, height, maze); randNum = randomRange(0, cellStringUnvisited.size-1); currentCell = cellStringUnvisited.cells[randNum]; free(cellStringUnvisited.cells); } while(unvisitedCount() > 0);
ご覧のとおり、アルゴリズムの実装は単純であり、理論からは抽象的です。「子供でも対処できます」と言われています。
記事を過負荷にしないために、上記の文章で使用されている関数のコードはネタバレです。
機能コードgetNeighbors関数は、訪問されていないセル近傍の配列を返します
cellString getNeighbours(unsigned int width, unsigned int height, int** maze, cell c){ unsigned int i; unsigned int x = cx; unsigned int y = cy; cell up = {x, y - distance}; cell rt = {x + distance, y}; cell dw = {x, y + distance}; cell lt = {x - distance, y}; cell d[4] = {dw, rt, up, lt}; unsigned int size = 0; cellString cells; cells.cells = malloc(4 * sizeof(cell)); for(i = 0; i < 4; i++){ // if(d[i].x > 0 && d[i].x < width && d[i].y > 0 && d[i].y < height){ // unsigned int mazeCellCurrent = maze[d[i].y][d[i].x]; cell cellCurrent = d[i]; if(mazeCellCurrent != WALL && mazeCellCurrent != VISITED){ // \ cells.cells[size] = cellCurrent; // ; size++; } } } cells.size = size; return cells;
removeWall関数は、2つのセル間の壁を削除します。
mazeMatrix removeWall(cell first, cell second, int** maze){ short int xDiff = second.x - first.x; short int yDiff = second.y - first.y; short int addX, addY; cell target; addX = (xDiff != 0) ? (xDiff / abs(xDiff)) : 0; addY = (yDiff != 0) ? (yDiff / abs(yDiff)) : 0; target.x = first.x + addX; // target.y = first.y + addY; maze[target.y][target.x] = VISITED; return maze; }
最初に、2番目と1番目のポイントの座標の差分値が計算されます。 明らかに、値は負、正、または0のいずれかです。
これらの座標を最初の点の座標に追加すると、壁の座標が取得されるように、そのような座標xyを見つける必要があります。
壁座標と最初の点との差のベクトルが（| 1 |、0）または（0、| 1 |）のいずれかであることが確実であるため、これを使用できます。
したがって、xDiff！= 0のx座標の加算は、xDiff / | xDiff |と等しくなり、xDiff = 0、ゼロとなります。 それぞれyについて。
xとyの添加物を受け取ったら、最初のセルと2番目のセルの間の壁の座標を簡単に計算し、訪問したこれらの座標にセルを割り当てます。
そのため、複雑な迷路を構築できる迷路ジェネレーターがあり、そのサイズはRAMのサイズによってのみ制限されます。
その結果、次のようなものを取得できます。
ラビリンス。 注意トラフィック！100x100
500x500
ジェネレーションは機能していますが、今は小さなものです。そのような迷路の中で道を見つけることです。
生成アルゴリズムよりも多くの検索アルゴリズムがあり、それらのいくつかは、読者の関心がある場合、以下の記事で説明しますが、今のところ、私たちが持っているものに満足し、同じアルゴリズムで迷路を「通過」します。
さらに、壁を取り外す必要がないため、さらに簡素化されます。
バックトラッキングパス検索アルゴリズム：
1.初期セルを現在のセルにし、訪問済みとしてマークします。
2.まだ出口がない
1.現在のセルに未訪問の「隣人」がある場合
1.現在のセルをスタックにプッシュします
2.隣接するセルからランダムなセルを選択します
3.選択したセルを現在のセルにし、訪問済みとしてマークします。
2.それ以外、スタックが空でない場合
1.スタックからケージを引き出します
2.最新の状態にする
3.そうでなければ、出口はありません。
出力ポイントおよび開始ポイントは、壁ではない迷路の任意のポイントにすることができます。
従来、出口は壁の1つに「押し付けられる」必要がありますが、実際にはどこにでもあります。
この場合、「入口」と「出口」は、パスを見つける必要がある2つのポイントにすぎません。
「終了」を見つけるための基準は非常に簡単です。現在のポイントの座標と「終了」の座標を比較するだけで十分です。それらが等しい場合、開始点と終了点の間のパスが見つかります。
何が起こったのか見てみましょう：
ランダム迷路ジェネレーターの最も簡単な実装に必要なのはそれだけです。
興味がある人のために、GitHubのプロジェクトの完全なソースコード：
Maze Generator and Solver（offscreen rendering）注意！OSMesaはUNIXベースの一部のドライバーで
はサポートされて
おらず 、Windowsでは
まったくサポートされていないため、OS /ハードウェアに不運な人のために、関連プロジェクトである
Maze GeneratorとSolverについて理解してください。
どちらのプロジェクトも同じアルゴリズムを実装していますが、最初のプロジェクトではメモリに描画して一連のpng画像を表示し、2番目のプロジェクトでは画面に表示します。
ビルドcd build && ../configure && make、不都合な場合は、srcフォルダーにQtCreatorプロジェクトファイルがあります。
ソース
1.
Walter D. Pullen：迷宮だと思います。2.
ウィキペディア：迷路生成アルゴリズム。