グラフの深さを探索する方法を使用した迷路の生成と解決

この記事では、「理想的な」迷路を生成するための最も簡単なアルゴリズムと、パスを見つけるためのそのアプリケーションについて説明します。



バックトラッキングベースのアルゴリズムを検討します。このアルゴリズムを使用すると、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{ //,      unsigned int x; unsigned int y; } cell; typedef struct cellString{ cell* cells; unsigned int size; } cellString;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

構造体は、機能間で情報を交換する際の生活を大幅に簡素化します。



生成を担当するコードスニペット：

 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);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ご覧のとおり、アルゴリズムの実装は単純であり、理論からは抽象的です。「子供でも対処できます」と言われています。

記事を過負荷にしないために、上記の文章で使用されている関数のコードはネタバレです。





そのため、複雑な迷路を構築できる迷路ジェネレーターがあり、そのサイズはRAMのサイズによってのみ制限されます。



その結果、次のようなものを取得できます。





ジェネレーションは機能していますが、今は小さなものです。そのような迷路の中で道を見つけることです。



生成アルゴリズムよりも多くの検索アルゴリズムがあり、それらのいくつかは、読者の関心がある場合、以下の記事で説明しますが、今のところ、私たちが持っているものに満足し、同じアルゴリズムで迷路を「通過」します。



さらに、壁を取り外す必要がないため、さらに簡素化されます。



バックトラッキングパス検索アルゴリズム：

1.初期セルを現在のセルにし、訪問済みとしてマークします。

2.まだ出口がない

1.現在のセルに未訪問の「隣人」がある場合

1.現在のセルをスタックにプッシュします

2.隣接するセルからランダムなセルを選択します

3.選択したセルを現在のセルにし、訪問済みとしてマークします。

2.それ以外、スタックが空でない場合

1.スタックからケージを引き出します

2.最新の状態にする

3.そうでなければ、出口はありません。



出力ポイントおよび開始ポイントは、壁ではない迷路の任意のポイントにすることができます。

従来、出口は壁の1つに「押し付けられる」必要がありますが、実際にはどこにでもあります。

この場合、「入口」と「出口」は、パスを見つける必要がある2つのポイントにすぎません。



「終了」を見つけるための基準は非常に簡単です。現在のポイントの座標と「終了」の座標を比較するだけで十分です。それらが等しい場合、開始点と終了点の間のパスが見つかります。



何が起こったのか見てみましょう：





ランダム迷路ジェネレーターの最も簡単な実装に必要なのはそれだけです。



興味がある人のために、GitHubのプロジェクトの完全なソースコード： Maze Generator and Solver（offscreen rendering）

ソース

1. Walter D. Pullen：迷宮だと思います。

2. ウィキペディア：迷路生成アルゴリズム。