前言
原始資料是油管上的視頻教程，鏈接戳我降铸，播主是南非小哥Sebastian Lague住拭，專門在油管上做Procedural Generation和Unity的相關(guān)教程視頻。Unity官方也把這個(gè)系列加到了推薦教程中柱嫌。"Procedural Cave Generation"這個(gè)系列已經(jīng)完結(jié)锋恬，自己跟著后面做了一遍，收獲頗多编丘，這里做個(gè)整理和翻譯与学，也算幫助自己理解彤悔。他還有一個(gè)正在連載的系列“Landmass Generation”，動(dòng)態(tài)生成3D Terrain索守，等完結(jié)了也可以考慮做個(gè)整理晕窑。
這個(gè)整理以理解和介紹背景知識(shí)為主，會(huì)貼部分代碼卵佛，想看詳細(xì)代碼的可以看他的Github項(xiàng)目主頁(yè)杨赤。部分代碼小哥是一筆帶過(guò)，可能看完你知道怎么做截汪，但為什么這么做理解起來(lái)可能有些困難疾牲，我也盡量找出相關(guān)資料輔助理解，Let's Start!
Cellular automata(細(xì)胞自動(dòng)機(jī))
Cellular Automata最早是馮諾曼依大爺提出的離散數(shù)學(xué)模型衙解，詳細(xì)的信息可以參考Wiki阳柔，在洞穴生成里面我們只需要借鑒這個(gè)模型的三個(gè)特點(diǎn)：
- 一個(gè)由多個(gè)格子Cell組成的N維網(wǎng)格（這里只要用到2維網(wǎng)格）
- 每格Cell狀態(tài)有限（這里只取兩個(gè)狀態(tài)，每格值是0-空地蚓峦，或者1-墻）
- 網(wǎng)格按照某種規(guī)則演變舌剂，每格Cell狀態(tài)變化受周圍格子狀態(tài)的影響而變化
背景知識(shí)就介紹這么多，接下來(lái)開(kāi)始一步步實(shí)現(xiàn)枫匾。
隨機(jī)生成2維網(wǎng)格
根據(jù)上面介紹的Cellular automata第一和第二條規(guī)則架诞，在Unity中建立一個(gè)腳本"MapGenerator"負(fù)責(zé)二維網(wǎng)格的實(shí)現(xiàn)。
public int width;
public int height;
public string seed;
public bool useRandomSeed;
[Range(0,100)]
public int randomFillPercent;
int[,] map;
width和height為可設(shè)置的地圖大小干茉。生成地圖的規(guī)則也很簡(jiǎn)單谴忧，設(shè)置一個(gè)randomFillPercent值，對(duì)每一點(diǎn)進(jìn)行遍歷角虫，隨機(jī)取值沾谓，如果小于randomFillPercent，將該點(diǎn)設(shè)置為1戳鹅，否則設(shè)置為0均驶。一般設(shè)置randomFillPercent為50左右。
考慮到有時(shí)候我們需要能夠存儲(chǔ)和重新生成相同的地圖枫虏，所以在初始化網(wǎng)格時(shí)并不是完全隨機(jī)妇穴，而是設(shè)置一個(gè)seed，進(jìn)行偽隨機(jī)生成隶债。
void RandomFillMap() {
if (useRandomSeed) {
seed = Time.time.ToString();
}
System.Random pseudoRandom = new System.Random(seed.GetHashCode());
for (int x = 0; x < width; x ++) {
for (int y = 0; y < height; y ++) {
if (x == 0 || x == width-1 || y == 0 || y == height -1) {
map[x,y] = 1; //設(shè)置邊緣固定為墻
} else {
map[x,y] = (pseudoRandom.Next(0,100) < randomFillPercent)? 1 : 0;
}
}
}
}
首次生成的圖可能是這個(gè)樣子腾它，別著急，接下來(lái)根據(jù)Cellular Automata的第三個(gè)特征處理網(wǎng)格死讹。
應(yīng)用規(guī)則處理網(wǎng)格
Cellular Automata網(wǎng)格的處理規(guī)則并不是固定的瞒滴，比較經(jīng)典的如Conway's Game of Life生命游戲的規(guī)則，不過(guò)我們這里處理規(guī)則比較簡(jiǎn)單：
- 統(tǒng)計(jì)當(dāng)前格子Cell周圍8個(gè)網(wǎng)格狀態(tài)為1（墻）的總和S
- 如果S大于4赞警，則把Cell設(shè)為1妓忍。如果S小于4虏两，則把Cell設(shè)為0。
- 如果S等于4世剖，則Cell值保持不變定罢。
void SmoothMap() {
for (int x = 0; x < width; x ++) {
for (int y = 0; y < height; y ++) {
int neighbourWallTiles = GetSurroundingWallCount(x,y);
if (neighbourWallTiles > 4)
map[x,y] = 1;
else if (neighbourWallTiles < 4)
map[x,y] = 0;
}
}
}
int GetSurroundingWallCount(int gridX, int gridY) {
int wallCount = 0;
for (int neighbourX = gridX - 1; neighbourX <= gridX + 1; neighbourX ++) {
for (int neighbourY = gridY - 1; neighbourY <= gridY + 1; neighbourY ++) {
if (IsInMapRange(neighbourX, neighbourY)) {
// 統(tǒng)計(jì)周圍8個(gè)點(diǎn)的情況，請(qǐng)參考Moore neighborhood(https://en.wikipedia.org/wiki/Moore_neighborhood)
if (neighbourX != gridX || neighbourY != gridY) {
wallCount += map[neighbourX, neighbourY];
}
}
else {
wallCount ++;
}
}
}
return wallCount;
}
循環(huán)上述步驟5次搁廓，可以看到地圖的變化如下：
如果你對(duì)其他處理規(guī)則感興趣引颈，可以查閱下面兩個(gè)鏈接：
1.Generate Random Cave Levels Using Cellular Automata
2.Procedural Level Generation in Games using a Cellular Automaton
規(guī)則是先設(shè)定一個(gè)DeathLimit（如3）和BirthLimit（如4）：
- 統(tǒng)計(jì)當(dāng)前Cell周圍為1（墻）的值S
- 如果Cell為1（墻），S值小于DeathLimit境蜕，則設(shè)置Cell為0
- 如果Cell為0（空地），S值大于BirthLimit凌停，則設(shè)Cell為1
需要解決的問(wèn)題
雖然目前可以生成一個(gè)賣相不錯(cuò)的地圖粱年，但還存留一些問(wèn)題：
- 地圖中依然存在小塊的空地集合或墻集合。
- 大塊的空地并不確狈Ｄ猓互相連通台诗。
要解決這兩個(gè)問(wèn)題，可以參考下面這篇文章赐俗，在生成規(guī)則上做一些優(yōu)化
Cellular Automata Method for Generating Random Cave-Like Levels
也可以參考Procedural Cave Generation這個(gè)系列教程里拉队，Sebastian小哥引入的“房間Room”的概念，去除過(guò)小的房間阻逮，然后對(duì)空房間進(jìn)行連接粱快，這個(gè)是part2要講的部分。
注：原始教程中叔扼，講完本文的內(nèi)容事哭，Sebastian小哥先去講了怎么在Unity里生成二維網(wǎng)格的Mesh，然后再回頭講房間連接瓜富，這里我先換個(gè)順序鳍咱，把和網(wǎng)格處理相關(guān)的內(nèi)容一塊說(shuō)了，再把Mesh生成放到最后說(shuō)与柑。
