ゲーム常用アルゴリズム-4種類の迷宮生成アルゴリズム

 
   
简介
 
   
所谓迷宫生成算法，就是用以生成随机的迷宫的算法
 
   
迷宫生成算法是处于这样一个场景：
 
   
 
    
 
一个row行，col列的网格地图，一开始默认所有网格四周的墙是封闭的
 
 
    
 
要求在网格地图边缘，也就是网格的边上打通2面墙
 
 
    
 
所有网格都至少保证网格周围至少有一堵墙打通
 
 
    
 
所有网格都能通过打通的墙能形成一条通路
 
 
   
 
   
博主已实现RecursiveBacktracking(递归回溯)，RecursiveSegmentation(递归分割)，随机Prim算法，Kruskal+并查集四种迷宫生成算法，这篇文章主要对这四种算法进行简要的介绍
 
   
基于Unity的迷宫生成算法代码实现
 
   
 
   
Github链接
 
   
递归回溯算法
 
   
复杂度 
 
   
    ：O（n)，  ：O（n)，n      row*col
  
げんり
1つのスタックを補助とするデータ構造で、貫通領域の順序を記録し、遡及するために使用される.
最初はランダムに地図で領域を選択し、スタックに追加します.
その後、前に選択した領域の周囲でランダムに貫通していない領域を選択し、新しい選択した領域と前に選択した領域の壁を貫通し、新しい領域のスタックに追加します.
周囲の領域が貫通している場合は、スタックをスタックから出し、当期に選択した領域をスタックの新しいスタックトップに設定し、前の領域に戻ることを示します.
その後、すべての領域がオンになるまで、前の手順で次の領域を選択します.
欠点
このアルゴリズムは実現構想が極めて簡単だが、通路が明らかすぎて、上図の迷宮が現れる可能性もあり、だらだらしている!!!
再帰分割アルゴリズム
複雑さ
         ：O(row * col)，       ：O（lgrow + lgcol)，       O（row * col）
  
げんり
長方形の地図を十字で4つの小さな行列に分ける
4つの小さな長方形に隣接する4つの面にそれぞれランダムに壁を貫通し、通路を導通させる.
次に、すべての小さな長方形を繰り返す前に分割操作を行います.
行列が分割できなくなった場合、すなわち行数または列数が一時的であれば、行列内部の壁をすべて貫通する
メリットとデメリット
生成された迷路には明らかな矩形成分があり、不自然で、FPS、ACTなどのゲームに適しています.
ランダムPrimアルゴリズム
複雑さ
    ：O（row*col)，  ：O（  =（row-1）*col+row*（col - 1）） 
  
げんり
現在の領域としてランダムに選択
領域の周囲が貫通していない壁をリストに追加
while(リストは空ではありません)
            
​
                ，      ，                    
​
         
  
メリットとデメリット
自然の迷宮は、歩きにくい、本格的な迷宮ゲームに適しています
Kruskal+並列調査セット
複雑さ
    ：O（row*col)，  ：O（  =（row-1）*col+row*（col - 1）） 
  
げんり
このアルゴリズムは巧みに用いられてセットを調べ,セットを用いて迷宮全体の導通問題を判断した.
  
すべての壁を壁リストに追加
while(壁リストは空ではありません)
             ，               
​
             
​
          
  
リファレンスリンク
三大迷宮生成アルゴリズム
ランダムラビリンス生成アルゴリズム(およびセット+生成ツリーを調べる)
転載先:https://www.cnblogs.com/millionsmultiplication/p/9568766.html