🥔 😷 🎂 途方もなく単純なラビリンス生成アルゴリズムの不可分の単純な実装 🚧 👉🏼 👩🏾‍🎨

この記事の続きは、長方形のラビリンスを生成するための非常に簡単なアルゴリズムについてです。この記事では、C ++でのアルゴリズムの実装を紹介し、退屈した脳が生み出した追加機能もいくつか示します。読み続けようとするなら、私の前の記事を必ず読んでください。見たことがありますか？よくやった、続ける。

コードはどこにありますか？

最初から始めましょう-標準ライブラリをプルアップし、関数を宣言します。

#include<iostream> #include<cstdlib> #include<ctime> using namespace std; bool deadend(int, int, int**, int, int); //  ,   void visual(int**, int, int); //       void mazemake(int**, int, int); //   const int wall = 0, pass = 1;

とても簡単です主に、変数heightおよびwidthでラビリンスの寸法を決定できます（ラビリンスの寸法は非常に奇妙で、アルゴリズムのコストが高いことを思い出します）。これらのパラメータはメインの外に移動して定数または単純にグローバル変数にすることができ、プログラムはこれに悩まされません。

 int main(){ srand((unsigned)time(NULL)); int height = 21, width = 21; int** maze = new int*[height]; for(int i = 0; i < height; i++) maze[i] = new int[width]; mazemake(maze, height, width); visual(maze,height,width); for(int i = 0; i < height; i++) delete[] maze[i]; delete[] maze; return 0; }

実際、それがすべてメインです。迷路全体は、問題なく2次元の動的配列に格納され、それを使用して作業します。 mazemake関数を実行した後、完成した迷路は迷路配列に保存されます。0は壁で、1は通路です。

行き止まりの機能を続けて、ほくろの絶望的な状況を探します-4つの方向すべてにすでに通路があるとき。

 bool deadend(int x, int y, int** maze, int height, int width){ int a = 0; if(x != 1){ if(maze[y][x-2] == pass) a+=1; } else a+=1; if(y != 1){ if(maze[y-2][x] == pass) a+=1; } else a+=1; if(x != width-2){ if(maze[y][x+2] == pass) a+=1; } else a+=1; if(y != height-2){ if(maze[y+2][x] == pass) a+=1; } else a+=1; if(a == 4) return 1; else return 0; }

少し行き止まり 。この関数は、ほくろが行き詰まっている場合はtrueを返し、そうでない場合はfalseを返します。なぜ、論理ANDではなく2回ですか？非常にシンプル-最初のチェック-近くに外部から侵入できない壁があるかどうか。いくつかの理由で侵入できません-配列にそれぞれ割り当てられたこれらの次元（メモリ管理、Anyan ^> ^）を選択するだけで、実際には配列の（-1）番目の要素をチェックしません。また、プライマリifの後の波括弧に注意してください-elseが具体的にそれを指している場合、 ~~それを記述する別の方法がわかりません~~ 。

 void visual(int** maze, int height, int width){ for(int i = 0; i < height; i++){ for(int j = 0; j < width; j++) switch(maze[i][j]){ case wall: cout<<"0 "; break; case pass: cout<<" "; break; } cout<<endl; } cout<<endl; }

幸せには他に何が必要ですか？次の目的地はmazemakeです。

 void mazemake(int** maze, int height, int width){ int x, y, c, a; bool b; for(int i = 0; i < height; i++) //   - for(int j = 0; j < width; j++) maze[i][j] = wall; x = 3; y = 3; a = 0; //      while(a < 10000){ // , , ,   ,   maze[y][x] = pass; a++; while(1){ //  ,     c = rand()%4; // ,    switch(c){ //         case 0: if(y != 1) if(maze[y-2][x] == wall){ //  maze[y-1][x] = pass; maze[y-2][x] = pass; y-=2; } case 1: if(y != height-2) if(maze[y+2][x] == wall){ //  maze[y+1][x] = pass; maze[y+2][x] = pass; y+=2; } case 2: if(x != 1) if(maze[y][x-2] == wall){ //  maze[y][x-1] = pass; maze[y][x-2] = pass; x-=2; } case 3: if(x != width-2) if(maze[y][x+2] == wall){ //  maze[y][x+1] = pass; maze[y][x+2] = pass; x+=2; } } if(deadend(x,y,maze,height,width)) break; } if(deadend(x,y,maze,height,width)) //     do{ x = 2*(rand()%((width-1)/2))+1; y = 2*(rand()%((height-1)/2))+1; } while(maze[y][x] != pass); } //    . }

簡単すぎる？一般的には、そうです。それは途方もなく簡単です。同じ理由で、すべて同じdouble ifsがあります。不満はありません。それはカウンターの形の松葉杖です。彼があなたの気持ちを傷つけたら-私たちの物語の第二章へようこそ。

機能とピース

お部屋

哺乳類に迷路を作るように教えました。この生き物を作って私たちをいくつかの部屋にしてみませんか？私たちはinなサディスティックな科学者であり、貧しい動物をどこに置くべきかわかりません。

部屋を作り、パラメーターを決定できるようにしたい場合、コードはあちこちで少し変更されます。部屋のサイズも変わっています。

 void mazemake(int**, int, int, int, int, int); //     const int wall = 0, pass = 1, room = 4; //   ... int height = 59, width = 111, k = 30; //      int rheight = 7, rwidth = 5; //   ... void mazemake(int** maze, int height, int width, int k, int rheight, int rwidth){ int x, y, c, a; bool b, swap = 1; for(int i = 0; i < height; i++) for(int j = 0; j < width; j++) maze[i][j] = wall; rheight--; rwidth--; //    for(int l = 0; l < k; l++){ //   b = 1; while(b){ do{ // -  if(rwidth%4 == 0) // ,     4   x = 2*(rand()%(width/2))+1; //  ,  else x = 2*(rand()%(width/2))+2; if(rheight%4 == 0) y = 2*(rand()%(height/2))+1; else y = 2*(rand()%(height/2))+2; } while(x < (rwidth+2) || x > (width-rwidth-2) || y < (rheight+2) || y > (height-rheight-2)); b = 0; //     for(int i = (y-rheight-2); i < (y+rheight+2); i++) for(int j = (x-rwidth-2); j < (x+rwidth+2); j++) if(maze[i][j] == room) b = 1; if(b) continue; for(int i = (y-rheight/2); i < (y+rheight/2+1); i++) //   for(int j = (x-rwidth/2); j < (x+rwidth/2+1); j++) maze[i][j] = room; c = rand()%4; //   ,     // , ,     //    rand()...   ,      //   if(c == 0) maze[y+rheight/2+1][x-rwidth/2+2*(rand()%(rwidth/2+1))] = room; if(c == 1) maze[y-rheight/2-1][x-rwidth/2+2*(rand()%(rwidth/2+1))] = room; if(c == 2) maze[y-rheight/2+2*(rand()%(rheight/2+1))][x+rwidth/2+1] = room; if(c == 3) maze[y-rheight/2+2*(rand()%(rheight/2+1))][x-rwidth/2-1] = room; // swap       90° if(swap){ rheight += rwidth; rwidth = rheight - rwidth; rheight -= rwidth; } //        } } ... int deadend(int x, int y, int** maze, int height, int width){ int a = 0; //  deadend    ,        if(x != 1){ if(maze[y][x-2] == pass || maze[y][x-2] == room) a+=1; } else a+=1; ...

きのこ

うーん...いいえ、固体ではありません。理想的な迷路におけるキノコのような経路探索アルゴリズム。それは良いです。さて、言葉を減らし、コードを増やしてください。

 ... void shroom(int**, int, int); const int wall = 0, pass = 1, liveshroom = 2, deadshroom = 3, room = 4, start = 5, finish = 6; int main(){ srand((unsigned)time(NULL)); int height = 59, width = 111, k = 30; //       - int rheight = 7, rwidth = 5; //    int** maze = new int*[height]; for(int i = 0; i < height; i++) maze[i] = new int[width]; mazemake(maze, height, width, k, rheight, rwidth); visual(maze,height,width); maze[1][1] = start; maze[height-2][width-2] = finish; shroom(maze,height,width); //     ,    visual(maze,height,width); //     for(int i = 0; i < height; i++) delete[] maze[i]; delete[] maze; return 0; ... void shroom(int** maze, int height, int width){ int x, y; for(int i = 0; i < height; i++) //   for(int j = 0; j < width; j++) if(maze[i][j] == start){ x = j; y = i; } while(maze[y][x] != finish){ //   -    maze[y][x] = liveshroom; //   //    , ,    , //        if(maze[y][x+1] == pass){ maze[y][x+1] = liveshroom; x+=2; continue; } if(maze[y][x-1] == pass){ maze[y][x-1] = liveshroom; x-=2; continue; } if(maze[y+1][x] == pass){ maze[y+1][x] = liveshroom; y+=2; continue; } if(maze[y-1][x] == pass){ maze[y-1][x] = liveshroom; y-=2; continue; } if(maze[y][x+1] != pass && //      -  , maze[y][x-1] != pass && //    (x, y)    maze[y+1][x] != pass && //   maze[y-1][x] != pass){ maze[y][x] = deadshroom; if(maze[y][x+1] == liveshroom){ maze[y][x+1] = deadshroom; x+=2; continue; } if(maze[y][x-1] == liveshroom){ maze[y][x-1] = deadshroom; x-=2; continue; } if(maze[y+1][x] == liveshroom){ maze[y+1][x] = deadshroom; y+=2; continue; } if(maze[y-1][x] == liveshroom){ maze[y-1][x] = deadshroom; y-=2; continue; } } } for(int i = 0; i < height; i++) //   ,      for(int j = 0; j < width; j++) if(maze[i][j] == deadshroom) maze[i][j] = pass; } }

正直なところ、言うことはありません。ポイントとショーの間の唯一の方法を見つけてください。 視覚的に追加する場合を除き、liveshroom：cout << "*"; 休憩;

松葉杖ではない

メインアルゴリズムのカウンターが本当に気に入らなかった場合、次の方法が最適です。100サイクルごとに1回実行されるチェック機能です。

 ... x = 3; y = 3; a = 0; while(1){ a++; if(a%100 == 0) if(ended(maze, height, width)) break; maze[y][x] = pass; ... bool ended(int** maze, int height, int width){ bool b = 1; for(int i = 1; i < (height - 1); i += 2) for(int j = 1; j < (width - 1); j += 2) if(maze[i][j] == wall) b = 0; return b; }