同樣使用Kruskal's algorithm來做為迷宮產生的判斷。
這次不用做太多的修改，只需要改幾個部分而已，也就是Component中使用到Random.Range()的部分，這個亂數目前是無法自己控制的，所以做個小小的調整改為使用Seed即可。
先建立一個類別來裝需要的東西，使用Static也可以，就可以直接呼叫使用，不過如果還有其他地方也會用到的話，就要小心先後呼叫的順序不同會造成同個Seed卻不同結果，所以這邊還是用需要建立instance的方法。
public class MyRandom
{
private System.Random random;
public MyRandom(int seed)
{
random = new System.Random(seed); //使用System的Random來丟入Seed
}
//回傳整數
public int Range(int min, int max) //使用跟Random.Range()相同的方法名稱，之後把原本的Random取代
{
return random.Next(min, max);
}
//回傳浮點數
public float Range(float min, float max)
{
double range = (double)max - (double)min;
double sample = random.NextDouble();
double scaled = (sample * range) + min;
return (float)scaled;
}
}
之後跟原本的Component差不多，不過多加Seed參數可以在編輯器輸入數值，以及把原本的Random.Range()改為MyRandom.Range()而已，這樣就可以亂數產生迷宮的同時，使用Seed來複製某一個想要重來的迷宮。
參考Component。
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; //地圖陣列
public int seed; //輸入Seed數值
private MyRandom myRandom; //使用自己的類別
void Start ()
{
myRandom = new MyRandom(seed); //初始化
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[myRandom.Range(0, cellList.Count)]; //改為myRandom
//先判斷這個格子四個方向是否都檢查完，如果檢查完就移除列表並且重新再選一個格子
if(IsCellFinished(cell))
{
cellList.Remove(cell);
continue; //Re-Pick cell
}
//亂數選一個方向並確定該方向是還沒檢查過的
int dir = myRandom.Range(0, 4); //改為myRandom
while(true)
{
if(cell.wall[dir] == 0)
break;
dir = myRandom.Range(0, 4); //改為myRandom
}
//取得該方向的下一個格子資料
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(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