前言
本節我們來做迷宮生成。生成迷宮的演算法其實有很多種，最簡單的比如遞迴。而這一節我們選擇prim演算法生成迷宮，因為這種演算法生成的迷宮較為自然，並且演算法原理簡易。
專案需求
使用prim演算法和預製體生成迷宮。
Prim演算法生成迷宮
1 演算法思路介紹
本部分中的所有圖示採用RPG Maker XP建立。順便吐槽一句，現在網上流傳的有關prim演算法生成迷宮的演算法描述（那個據說來自維基的）簡直是語文不及格產物。
Prim演算法與圖論有關（我在http：//theodor。top/article/105中介紹過基本的圖搜尋演算法和一個使用Ruby書寫的搜尋模版），它最開始被用於在加權連通圖裡搜尋一個最小生成樹。個人認為它還有些像用堆實現的二叉樹遍歷演算法。其具體資料請讀者自行學習，筆者在此只給出一個用於迷宮生成場景下較為通俗的描述。
我們假設在區域內有一個N*M列的迷宮。對於迷宮的每個格子，它們只有兩個狀態：通路/牆。在初始狀態下，這個迷宮裡的所有格子都是牆。設定一個
牆
的類Wall，其資料為［Vector2Int pos， Vector2Int relative］，也就是其位置向量pos與其相對格子的位置向量relative（在後續步驟中會解釋）。同時，我們建立一個牆的空列表M。
然後我們選定一個起點A，將此位置的牆移除：
將與起點A相鄰的所有牆加入M中，其中A作為這些牆的父格子。對於一面牆而言，我們稱在其父格子另一邊的格子為
相對格子
。它們的例子如圖：
在M中隨機選擇一個元素x。對於x，如果其相對格子為牆，則移除相對格子和x的牆，然後將相對格子作為父格子，將相鄰牆加入列表。否則則只從M中移除x。如此迴圈直到M中為空。
2 程式碼示例
我們會建立一個牆的類Wall與生成迷宮的類Maze。
Wall。cs
public class Wall //內部類Wall{ public Vector2Int pos； //位置向量 public Vector2Int relative； //相對格子向量 public Wall（Vector2Int pos，Vector2Int anc）{ this。pos=pos； ancToRelative（anc）； } public void ancToRelative（Vector2Int ancestor）{ //輸入一個父格子，求出其相對格子並賦值 this。relative=pos*2-ancestor； //int不能左乘Vector2Int（因為這裡的*是Vector2Int的運算子過載） }}
Maze。cs
public class Maze //內部類Maze{ private Vector2Int［］ e={new Vector2Int（1，0），new Vector2Int（-1，0），new Vector2Int（0，1），new Vector2Int（0，-1），}； //四方向 private int width； private int height； //迷宮矩陣的寬和高 預設［寬，高］，Maze位置的遊標在<［0。。width］，［0。。height］> private Vector2Int origin； //起點 public List 在生成迷宮時，宣告一個Maze類的例項並且呼叫其exec方法，就可得到一個迷宮。 3 用於測試的程式碼 此程式碼在Start方法內呼叫，可以在控制檯生成一份迷宮示意圖。 string a=“”； Maze maze=new Maze（30，20，new Vector2Int（0，0））； maze。exec（）； for（int i=0；i<30；i++）{ for（int j=0；j<20；j++）{ if（maze。maze。Contains（new Vector2Int（i，j）））{ a=a+“-”； } else{ a=a+“#”； } } a=a+“\n”； } print（a）； 預製體（預製件） -本節相關內容請讀者參考： -https://docs.unity3d.com/cn/current/Manual/Prefabs.html，《預製件》 -https://docs.unity.cn/cn/current/ScriptReference/Object.Instantiate.html，《Object.Instantiate》 1 定義 預製體（英文為prefab，在unity手冊中被稱為預製件）可以看做是一個檔案化的遊戲物件，一個已經構建好了的樣板。如果從程式設計的角度進行類比，預製體可以被看成一個用於派生類的基類，或者是一個單純的被複制物件。預製體以實體檔案（。prefab）的形式存在於unity中，並可以在有需要時動態載入進遊戲場景。 預製體通常被應用於如下兩個場景中：一，被經常使用的遊戲物件（比如森林場景中的一棵樹）；二，在場景被載入時不應當存在於場景中的遊戲物件（比如說闖關遊戲中的通關畫面）。 2 構建迷宮牆體預製體 首先確認預製體的形狀和大小。由於迷宮的場地是正方形的，我們採用以正方形為底的四稜柱作為預製體的形狀，則底邊長設定為scale1單位，高度為scale2單位。 建立一個Cube，調整其大小和位置直到滿足上文中的條件。然後，重新命名Cube為prefab，選中prefab並將其拖動到Project選項卡下的遊戲資原始檔夾內部，可以看到出現了一個同名檔案，即為預製體。 將預製體檔案拖動到Hierarchy選項卡下，可以看到預製體又出現在場景中了。需要注意的是，如果要編輯預製體檔案本身，請點選預製體右邊的“>”，在場景中直接編輯的不是預製體，而只是其的一個副本。預製體在場景中以藍色顯示。 完善工程 將目的區域的大小調整到與球體相同的水平，也就是scale0。1大小（順便要調整變色和音效生效的區域）。 建立一個空遊戲物件MazeController，搭載用於生成迷宮的指令碼MazeController。cs。 敲程式碼。 MazeController。cs using System。Collections；using System。Collections。Generic；using System。Text；using System。Threading。Tasks；using UnityEngine；using Random=UnityEngine。Random；public class Wall //內部類Wall{ public Vector2Int pos； //位置向量 public Vector2Int relative； //相對格子向量 public Wall（Vector2Int pos，Vector2Int anc）{ this。pos=pos； ancToRelative（anc）； } public void ancToRelative（Vector2Int ancestor）{ //輸入一個父格子，求出其相對格子並賦值 this。relative=pos*2-ancestor； //int不能左乘Vector2Int（因為這裡的*是Vector2Int的運算子過載） }}public class Maze //內部類Maze{ private Vector2Int［］ e={new Vector2Int（1，0），new Vector2Int（-1，0），new Vector2Int（0，1），new Vector2Int（0，-1），}； //四方向 private int width； private int height； //迷宮矩陣的寬和高 預設［寬，高］，Maze位置的遊標在<［0。。width］，［0。。height］> private Vector2Int origin； //起點 public List 運行遊戲，如圖所示：
