本次使用的演算法概念是Randomized Kruskal's algorithm(https://en.wikipedia.org/wiki/Maze_generation_algorithm)，大概就是只先把所有的牆面紀錄列表，亂數取一個牆，兩兩格子為一組，如果這一組格子是被這個牆面切兩半，並且成為獨立兩個個體，就把這面牆打通。
有點難懂，不過我換個方式來做判斷，同樣使用遞迴的方式，亂數從陣列中取一點，從這一點隨意往四周取一個方向，該方向還有牆面，並且那個方向過去點還沒踩過，接著從過去的那個點用遞迴取得所有路徑，來判斷是否有連回起始點形成封閉迴圈，如果沒有形成封閉迴圈就把這兩個點連起來。
跟Depth-first search形成的圖來看，可以發現Depth-first比較容易出現長且沒有分支的路，很明顯因為這個方法要一直走到死路沒得走後才會回頭再找還沒判斷完的格子。
同樣使用方形格子，設定牆面資料，這次不會一次把一個格子所有方向檢查完，所以用3個數字記錄三種狀態。
private class Cell
{
//使用一個陣列來設定四個牆的屬性，0還沒檢查，1是有牆面，2則是打通的通道
public int[] wall = new int[4]; //陣列四個依序為N, E, S, W
public Cell[] nextCell = new Cell[4]; //紀錄通道通往的下一個格子
public int x, y;
}
然後開始建立地圖，首先先把所有格子存入一張列表，每次從這張表裏隨機取一個格子跟四周做連線判斷，當這個格子四面都已經檢查完畢(牆壁或走道而不是0)就把這個格子從列表中移除，一直到所有格子都判斷完畢這張列表清空，地圖就建立完畢。
每次取格子然後跟下一個方向做連線判斷時，用遞迴把所有路徑都取出來看有沒有形成封閉迴圈，有的話這個方向就設定為牆壁，沒有的話就打通成為走道。
//概念
private bool IsClosedCircuit(...)
{
//把這個點加入列表避免重複檢查
visitedList.Add(thisCell);
//往四個方向依序跑
for(int i = 0; i < 4; ++i)
{
if(wall == 2) //只檢查路徑
{
//如果下一個方向的格子已經檢查過，就跳過
if(visitedList.Contains(nextCell))
continue;
//如果下一個方向的格子就是起始點的格子，代表有形成封閉迴圈，結束遞迴
if(nextCell == startCell)
return true;
//繼續檢查，只要有形成封閉迴圈就跳出
if(IsClosedCircuit(...))
return true;
}
}
//全部路線都跑完，沒有形成封閉迴圈
return false;
}
跑完後可以發現地圖跟Depth-first會有點不同，不過同樣陣列越大花的時間越久，跟我使用的方法也不算是非常的有效率也有關係就是了。
這兩個方法都是跑完全部陣列的資料，雖然這種類型的迷宮也算滿好用的，但有時候並不是需要把全部都填滿的那種地圖，這種需求像這種全部陣列跑完的可能就不太適合了。
參考Component，不過要注意的是這個Component只是單純產生完Cell[][]的陣列資料，要如何運用這個資料還是需要看自己的需求去建立場景或圖片等等。
public class KruskalMaze : MonoBehaviour
{
private class Cell
{
//使用一個陣列來設定四個牆的屬性，0還沒檢查，1是有牆面，2則是打通的通道
public int[] wall = new int[4]; //陣列四個依序為N, E, S, W
public Cell[] nextCell = new Cell[4]; //紀錄通道通往的下一個格子
public int x, y;
}
public int width = 10; //地圖的寬
public int height = 10; //地圖的高
private Cell[][] cellArr; //地圖陣列
void Start ()
{
//這次使用Coroutine來跑
StartCoroutine(Maze (width, height));
}
//這邊用一個簡單的Draw Gizmos在Unity編輯室窗上顯示地圖形成的過程
void OnDrawGizmos()
{
float size = 1.5f;
Gizmos.color = Color.yellow;
if(cellArr != null)
{
for(int i = 0; i < height; ++i)
{
for(int j = 0; j < width; ++j)
{
Gizmos.DrawCube(new Vector3(j*size, i*size, 0), new Vector3(0.5f, 0.5f, 0.5f));
if(cellArr[i][j].wall[0] == 2) Gizmos.DrawCube(new Vector3(j*size, i*size + 0.5f, 0), new Vector3(0.5f, 0.5f, 0.5f));
if(cellArr[i][j].wall[1] == 2) Gizmos.DrawCube(new Vector3(j*size + 0.5f, i*size, 0), new Vector3(0.5f, 0.5f, 0.5f));
if(cellArr[i][j].wall[2] == 2) Gizmos.DrawCube(new Vector3(j*size, i*size - 0.5f, 0), new Vector3(0.5f, 0.5f, 0.5f));
if(cellArr[i][j].wall[3] == 2) Gizmos.DrawCube(new Vector3(j*size - 0.5f, i*size, 0), new Vector3(0.5f, 0.5f, 0.5f));
}
}
}
}
//建立地圖
IEnumerator Maze(int width, int height)
{
//初始化地圖陣列跟所有點的列表
List<Cell> cellList = new List<Cell>();
cellArr = new Cell[height][];
for(int i = 0; i < height; ++i)
{
cellArr[i] = new Cell[width];
for(int j = 0; j < width; ++j)
{
cellArr[i][j] = new Cell();
//順便設定邊界的牆
if(j == 0) cellArr[i][j].wall[3] = 1;
if(j == width-1) cellArr[i][j].wall[1] = 1;
if(i == 0) cellArr[i][j].wall[2] = 1;
if(i == height-1) cellArr[i][j].wall[0] = 1;
cellArr[i][j].y = i;
cellArr[i][j].x = j;
//加入列表
cellList.Add(cellArr[i][j]);
}
}
//只要列表的格子還沒檢查完就一直檢查
while(cellList.Count > 0)
{
//從列表亂數選一個格子
Cell cell = cellList[Random.Range(0, cellList.Count)];
//先判斷這個格子四個方向是否都檢查完，如果檢查完就移除列表並且重新再選一個格子
if(IsCellFinished(cell))
{
cellList.Remove(cell);
continue; //Re-Pick cell
}
//亂數選一個方向並確定該方向是還沒檢查過的
int dir = Random.Range(0, 4);
while(true)
{
if(cell.wall[dir] == 0)
break;
dir = Random.Range(0, 4);
}
//取得該方向的下一個格子資料
int dirY = (dir == 0) ? 1 : (dir == 2) ? -1 : 0;
int dirX = (dir == 1) ? 1 : (dir == 3) ? -1 : 0;
int nextY = cell.y + dirY;
int nextX = cell.x + dirX;
Cell nextCell = cellArr[nextY][nextX];
//從這個格子開始檢查是否連回最初的格子
if(IsClosedCircuit(cell, nextCell, new List<Cell>()))
{
//起始格跟下一個方向的格子連線會形成封閉迴圈，把這個方向設定為牆壁
cell.wall[dir] = 1;
nextCell.wall[(dir+2)%4] = 1;
//順便檢查這兩個格子是否都檢查完
if(IsCellFinished(cell)) cellList.Remove(cell);
if(IsCellFinished(nextCell)) cellList.Remove(nextCell);
continue; //從頭步驟在開始
}
//都檢查完，把起始格跟下一個方向的格子連線形成通道
cell.wall[dir] = 2;
cell.nextCell[dir] = nextCell;
nextCell.wall[(dir+2)%4] = 2;
nextCell.nextCell[(dir+2)%4] = cell;
//順便檢查這兩個格子是否都檢查完
if(IsCellFinished(cell)) cellList.Remove(cell);
if(IsCellFinished(nextCell)) cellList.Remove(nextCell);
yield return null;
}
}
//檢查封閉迴圈
private bool IsClosedCircuit(Cell checkCell, Cell start, List<Cell> visitedList)
{
visitedList.Add(start);
for(int i = 0; i < 4; ++i)
{
if(start.wall[i] == 2)
{
//If this cell has checked
if(visitedList.Contains(start.nextCell[i]))
continue;
if(start.nextCell[i] == checkCell)
return true;
if(IsClosedCircuit(checkCell, start.nextCell[i], visitedList))
return true;
}
}
return false;
}
//格子是否全部方向都檢查完
private bool IsCellFinished(Cell cell)
{
bool isFinished = true;
for(int i = 0; i < 4; ++i)
{
if(cell.wall[i] == 0) isFinished = false;
}
return isFinished;
}
}
No comments:
Post a Comment