1.簡介
之前在Github上看到《無限城市的隨機程序化生成算法》,效果很驚艷,所以花了一些時間對這個項目源碼進(jìn)行了學(xué)習(xí),在此備忘和分享學(xué)習(xí)過程中的一些心得體會.
在這個項目中,提到的算法叫做《波函數(shù)坍縮》.光是聽到這個名字,就想:"這啥啊?波函數(shù)?坍縮?啥跟啥啊?",然后經(jīng)過查閱,發(fā)現(xiàn)是跟量子力學(xué)有關(guān)的,"量子力學(xué)我沒學(xué)過啊",覺得量子力學(xué)會不會太過難以理解,一度差點棄坑...在看到一些這個算法的應(yīng)用示例以后,終于下定決心想把這個算法原理弄明白,結(jié)果發(fā)現(xiàn)并不是想象中的那么難懂.希望讀者們也不要像我開始一樣.因為"量子力學(xué)我不會啊","波函數(shù)坍縮是啥玩意啊"等等原因就放棄了,其實這個算法很簡單的.
1.1 波函數(shù)坍縮是什么？
OK,那我們先來簡單介紹一下什么是"波函數(shù)坍縮"(由于本人對量子力學(xué)沒有經(jīng)過專業(yè)的學(xué)習(xí),所以僅僅是表達(dá)個人理解,不對的地方,請不要深究細(xì)節(jié)).
《雙縫干涉》實驗
在量子力學(xué)中,有一個很著名的實驗,叫做《雙縫干涉》.實驗的過程可以看看這個視頻 世界十大經(jīng)典物理實驗之首——電子雙縫干涉實驗.實驗的結(jié)果就當(dāng)沒有觀測時,光子呈現(xiàn)的是波的性質(zhì).當(dāng)觀測時,光子呈現(xiàn)的是粒子的性質(zhì).(這是人類在科學(xué)實驗中正式遭遇靈異的著名試驗.)
薛定諤的貓
著名的奧地利物理學(xué)家(Nue Mao Kuang Ren)薛定諤提出了一個思想實驗,實驗的內(nèi)容可以看這里「薛定諤的貓」是指什么逻翁？.實驗的結(jié)論就是當(dāng)匣子里的貓被觀測時,貓的狀態(tài)要么死要么活,只能在兩者之間二選一,而沒有觀測的話,那么貓的狀態(tài)既不死也不活(這個狀態(tài)不符合實際,但是量子力學(xué)確實是這么定義它的).
介紹完上面兩個著名實驗以后,肯定有人提出疑問了,那么它們跟"波函數(shù)塌陷"有什么關(guān)系呢?關(guān)系大著呢.上面兩個實驗都有表現(xiàn)了一個物質(zhì)在量子力學(xué)中,可能存在多種狀態(tài)(光子:波,粒子; 貓:死,活,不死不活.)而當(dāng)物質(zhì)被觀測時,它的狀態(tài)就被確定了.這個"狀態(tài)被確定了"的過程,我們就稱之為"波函數(shù)坍縮".(所以專業(yè)術(shù)語就是如此,用一個看起來很高大上的名字來形容一個現(xiàn)象或者性質(zhì),就算"波函數(shù)坍縮"這五個字換成"XXXXX"也不影響理解)
1.2 熵是什么？
介紹完"波函數(shù)坍縮"以后,再來談?wù)勈裁词?熵(shang)"吧,熵是熱力學(xué)的表示物質(zhì)狀態(tài)的參量,它的物理意義表示物質(zhì)的混亂程度,熵越大,說明物質(zhì)越混亂,熵越小,說明物質(zhì)越穩(wěn)定,例如水加熱變成霧,這個過程熵值增加(熵增),水降溫變成冰,這個過程熵值減少(熵減),把這一概念引入到量子力學(xué)中,可以表示當(dāng)一個物質(zhì)從疊加態(tài)坍縮到某一個狀態(tài)時,熵減,反之則熵增.
以薛定諤的貓的實驗為例,可以這么理解,當(dāng)沒有觀察貓的時候,貓?zhí)幱诓凰啦换畀B加態(tài),此時貓死的概率是50%,活的概率也是50%,熵值最大,當(dāng)打開匣子去觀察貓的時候,貓的狀態(tài)就從不死不活坍縮成死或活的狀態(tài),坍縮完以后熵值最小.
既然熵是個度量值,那么就有求熵公式,針對事件發(fā)生的概率而言,標(biāo)準(zhǔn)求熵公式(也叫信息熵)為:
其中p(x)表示事件x發(fā)生的概率.H(X)就是熵值.
到此為止.量子力學(xué)的部分簡單介紹完畢,其實這些目前看不懂不明白也沒關(guān)系,不會影響了解這個隨機算法.只是這個算法借用了這些概念和術(shù)語而已.
2.原理概述
以日常生活中,以去看電影為例(下面會經(jīng)常引用到這個例子),假設(shè)一家電影院的出售的電影票是沒有座位號的,入座由一位入座引導(dǎo)員安排,設(shè)總座位個數(shù)(即影院容納人數(shù))為n,從入座引導(dǎo)員的角度來說,如果客人沒有要求,那么任何一個人
都可以坐到他想坐的座位上,也就是說,每個人能坐在任一座位的概率都是1/n,而現(xiàn)在我們要加入一些規(guī)則了,比如你跟你的朋友一起去,你就需要跟引導(dǎo)員提要求,說你們必須挨著座位坐,那么引導(dǎo)員給你選好了一個座位以后,就會再把你的朋友安排在旁邊.從座位的角度來說,你一旦入座,當(dāng)前你的座位人選概率塌陷成只有你,而旁邊的座位人選是你朋友的概率被大大提高.所以類似這樣的從混亂變成確定的現(xiàn)象,用一個術(shù)語來表示就叫做波函數(shù)塌陷.
所以算法的核心原理,就是動態(tài)使每個座位的候選對象的范圍變得越來越小,直到最后所有的座位都能夠選取到合適的對象.(比如每個座位都入座了一個觀眾(對應(yīng)坍縮的對象)).而如何動態(tài)使候選對象范圍變小呢?就是通過約束規(guī)則,傳播和回溯.
2.1 約束規(guī)則
在初始情況下(宇宙一片混沌?)(理論上此時熵值最大),每個座位的可選對象集合都一樣,如果沒有規(guī)則,那隨機選取以后的結(jié)果,也將會雜亂無章,約束規(guī)則的存在,就類似上面提到的"跟引導(dǎo)員提要求,我的朋友要坐在我旁邊",各種各樣的規(guī)則,使得當(dāng)一個座位被確定(坍縮)了以后,會根據(jù)規(guī)則影響到其他的座位的可選對象集合.
2.2 傳播
當(dāng)一個座位的人選被確定了(坍縮)了以后,通過規(guī)則加上傳播,就可以對其他的座位的可選對象集合進(jìn)行處理.(比如,按上述場景,給引導(dǎo)員一個"我的右手邊只能坐妹子"的規(guī)則,那么一旦我入座,我右手邊的座位可選集合就被處理成只包含妹子了),
在2D世界中,一個物體有4個面(前后左右),而在3D世界中,一個物體有6個面(前后左右上下).每個面對應(yīng)的一個鄰居,所以波函數(shù)坍縮的算法傳播思路,就可以根據(jù)已坍縮位置的鄰居進(jìn)行傳播.把規(guī)則套進(jìn)去,對每個鄰居的可選集合進(jìn)行處理.
2.3 回溯
有的時候,當(dāng)我們的算法在傳播過程中,出了錯(比如:我給引導(dǎo)員提的規(guī)則是"我的右手只能坐我朋友",而我朋友給引導(dǎo)員提的規(guī)則是"我不要坐第一排",這樣就有可能出現(xiàn)這樣的一個情況,一旦引導(dǎo)員把我的座位安排在第一排,我一入座,算法傳播以后,我右邊的座位可選集合被處理成只能坐我朋友,又因為我朋友"不坐第一排"的規(guī)則,最終導(dǎo)致了我右邊的座位沒有一個人能坐,而我右邊沒人又跟"我的右手只能坐我朋友"這個規(guī)則相悖....這樣容易造成沖突矛盾,資源浪費),我們就希望能夠把出錯的方案排除,然后再回退.重新選一遍.這就是回溯的意義.
3.源碼解析
了解上述基本概念和原理以后,結(jié)合源代碼來看看是如何實現(xiàn)的吧.
3.1 Slot(插槽?座位?)
Slot這個類對象對應(yīng)了上述例子中的座位.這個類有個很重要的成員對象,就是Modules,它代表了當(dāng)前Slot所有可選模塊的集合**.
//表示一個可以放置模塊的插槽,
public class Slot
{
public Vector3Int Position; //位置
public ModuleSet Modules; //可選的模塊集合
public short[][] ModuleHealth; //6個方向,可選模塊對應(yīng)的Health,Health為0時,表示不可選取
private AbstractMap map; //地圖的引用
public Module Module; //最終選取的模塊
public bool Collapsed; //是否已坍縮
//其他....略
}
3.2 ModuleProtoType, Module, ModuleSet (模塊相關(guān))
ModuleProtoType即模塊原型,它包含了6個面的信息(前后左右上下),每個面都對應(yīng)了一個ConnectorID,只有相同的ConnectorID才可以相互連接(這是最基礎(chǔ)的約束規(guī)則),面的信息分成HorizontalFaceDetails(水平面,前后左右)和VerticalFaceDetails(垂直面,上下),作者通過一個比較Mesh頂點的輔助代碼,來自動批量的生成FaceDetails信息.
// 通過計算Mesh的六個面的數(shù)據(jù),得到6個方向的ConnectorId,相同的ConnectorId才可以連接,通過Flipped / Rotation來決定要如何連接
public class ModulePrototype : MonoBehaviour
{
[System.Serializable]
public abstract class FaceDetails
{
public bool Walkable; //此面是否允許行走
public int Connector; //ConnectorID,相同的ConnectorID才可以相連
public Fingerprint Fingerprint; //指紋,通過mesh頂點計算得到vector4數(shù)組,用以批量生成ConnectorID
public ModulePrototype[] ExcludedNeighbours; //想要排除在外的鄰近模塊原型
//其他....略
}
public float Probability = 1.0f; //被隨機選取的概率,求熵時也需要用到
public bool Spawn = true; //是否可用
public FaceDetails[] Faces; //6個朝向
}
Module即模塊,對應(yīng)了上述例子中的看電影的觀眾,在算法做規(guī)則判斷時候用來的模塊,它是由ModuleProtoType(模塊原型)繞著Y軸旋轉(zhuǎn)以后得到的.比如:一個ModuleProtoType,分別繞著Y軸旋轉(zhuǎn)0,90,180,270度,就得到4個Module,這樣可以使得模塊原型的資源得到復(fù)用.
public class Module
{
public string Name; //名稱
public ModulePrototype Prototype; //模塊原型
public GameObject Prefab; //GameObject
public int Rotation; //繞Y軸旋轉(zhuǎn)度數(shù),0-0 1-90 2-180 3-270
public ModuleSet[] PossibleNeighbors; //6個方向鄰居的可選模塊集合
public Module[][] PossibleNeighborsArray; //6個方向鄰居的可選模塊數(shù)組
[HideInInspector] public int Index; //索引,與ModuleSet位數(shù)組相對應(yīng)
public float PLogP; //概率p*log(p),求熵時需要用到
//構(gòu)造方法
public Module(GameObject prefab, int rotation, int index)
{
this.Rotation = rotation;
this.Index = index;
this.Prefab = prefab;
this.Prototype = this.Prefab.GetComponent<ModulePrototype>();
this.Name = this.Prototype.gameObject.name + " R" + rotation;
this.PLogP = this.Prototype.Probability * Mathf.Log(this.Prototype.Probability);
}
}
ModuleSet即模塊集合,它使用位數(shù)組的方式(什么是位數(shù)組,請看這),把預(yù)處理好的所有Module都封裝到集合中,在Slot中的ModuleSet就表示了當(dāng)前Slot所有可選的模塊了.
public class ModuleSet : ICollection<Module>
{
[SerializeField] private long[] data; //位數(shù)組,1個位對應(yīng)1模塊index,0表示不可選,1表示可選
private float entropy; //熵
private bool entropyOutdated = true; //熵是否過期(下次需要重新計算)
public int Count; //可選模塊的總數(shù)量
//其他...略
}
3.3 AbstractMap(地圖相關(guān))
AbstractMap這個抽象基類,可以與上述例子的入座引導(dǎo)員做類比,它負(fù)責(zé)生成和管理了所有地圖上的Slot,接下來就看看它是如何執(zhí)行波函數(shù)坍縮的核心算法的.
先獲取當(dāng)前所有需要處理的Slot:
// 坍縮函數(shù)
public void Collapse(Vector3Int size, IEnumerable<Vector3Int> targets, bool showProgress = false)
{
//其他...略
this.workArea = new HashSet<Slot>(targets.Select(target => this.GetSlot(target)).Where(slot => slot != null && !slot.Collapsed)); //把所有需要處理的Slot加到workArea中,等待處理
//其他...略
}
然后計算每個Slot中可選集合的熵,找到熵值最小的Slot
// 坍縮函數(shù)
public void Collapse(Vector3Int size, IEnumerable<Vector3Int> targets, bool showProgress = false)
{
//其他...略
this.workArea = new HashSet<Slot>(targets.Select(target => this.GetSlot(target)).Where(slot => slot != null && !slot.Collapsed));
while (this.workArea.Any())
{
float minEntropy = float.PositiveInfinity;
Slot selected = null;
foreach (var slot in workArea) //遍歷Slot,找出熵值最小的那個
{
float entropy = slot.Modules.Entropy;
if (entropy < minEntropy)
{
selected = slot;
minEntropy = entropy;
}
}
try
{
selected.CollapseRandom(); //對Slot進(jìn)行隨機坍縮
}
catch (CollapseFailedException) //捕獲出錯的異常,為了回溯
{
//回溯,暫略,下文介紹
}
//其他...略
}
對這個Slot進(jìn)行坍縮,坍縮就是在ModuleSet(可選模塊集合)中隨機取一個模塊(模塊的概率越大,越容易被選中)
public void CollapseRandom()
{
if (!this.Modules.Any()) //一個可選模塊都沒有
{
throw new CollapseFailedException(this);
}
if (this.Collapsed)
{
throw new Exception("Slot is already collapsed."); //此Slot已坍縮
}
float max = this.Modules.Select(module => module.Prototype.Probability).Sum(); //所有可能性累加
float roll = (float)(InfiniteMap.Random.NextDouble() * max); //獲取Roll值
float p = 0;
foreach (var candidate in this.Modules)
{
p += candidate.Prototype.Probability;
if (p >= roll)
{
this.Collapse(candidate); //在可選模塊中隨機選擇一個
return;
}
}
this.Collapse(this.Modules.First()); //坍縮完畢
}
坍縮完畢以后,就需要對6個方向的鄰居的ModuleSet按規(guī)則進(jìn)行處理.即傳播.
// 坍縮完畢的函數(shù)
public void Collapse(Module module)
{
if (this.Collapsed)
{
Debug.LogWarning("Trying to collapse already collapsed slot.");
return;
}
this.map.History.Push(new HistoryItem(this)); //加入歷史記錄,便于回溯
this.Module = module;
ModuleSet toRemove = new ModuleSet(this.Modules); //復(fù)制一份當(dāng)前可選模塊的集合
toRemove.Remove(module); //在集合中刪除當(dāng)前模塊
this.RemoveModules(toRemove); //將其他的模塊集合從當(dāng)前集合中刪除
this.map.NotifySlotCollapsed(this);
}
//從當(dāng)前集合中刪除一個模塊集合,并傳播影響鄰居
public void RemoveModules(ModuleSet modulesToRemove, bool recursive = true)
{
//其他...略
for (int d = 0; d < 6; d++) //6個方向
{
int inverseDirection = (d + 3) % 6; //反方向,也就是指向自己
var neighborSlot = this.GetNeighbor(d);
if (neighborSlot == null || neighborSlot.Forgotten)
{
continue;
}
foreach (var module in modulesToRemove)
{
for (int i = 0; i < module.PossibleNeighborsArray[d].Length; i++)
{
var possibleNeighbor = module.PossibleNeighborsArray[d][i];
if (neighborSlot.ModuleHealth[inverseDirection][possibleNeighbor.Index] == 1 && neighborSlot.Modules.Contains(possibleNeighbor)) //如果鄰居的可選模塊是屬于待刪模塊集合中的話,如果Health減完以后變成0,就從鄰居的模塊集合中刪除掉
{
this.map.RemovalQueue[neighborSlot.Position].Add(possibleNeighbor); //添加進(jìn)刪除隊列
}
#if UNITY_EDITOR
if (neighborSlot.ModuleHealth[inverseDirection][possibleNeighbor.Index] < 1)
{
throw new System.InvalidOperationException("ModuleHealth must not be negative. " + this.Position + " d: " + d);
}
#endif
neighborSlot.ModuleHealth[inverseDirection][possibleNeighbor.Index]--; //將Health-1
}
}
}
//其他...略
}
通過try..catch..來捕獲出錯的情況,然后回溯,回溯的方式就是將保存在History中最后的兩個元素取出,把刪除掉的ModuleSet還回去.
//坍縮函數(shù)
public void Collapse(Vector3Int size, IEnumerable<Vector3Int> targets, bool showProgress = false)
{
//其他...略
try
{
selected.CollapseRandom(); //嘗試隨機坍縮
}
catch (CollapseFailedException) //捕獲異常
{
this.RemovalQueue.Clear();
if (this.History.TotalCount > this.backtrackBarrier)
{
this.backtrackBarrier = this.History.TotalCount;
this.backtrackAmount = 2;
}
else
{
this.backtrackAmount += 4;
}
if (this.backtrackAmount > 0)
{
Debug.Log(this.History.Count + " Backtracking " + this.backtrackAmount + " steps...");
}
this.Undo(this.backtrackAmount); //回溯backtrackAmount步
}
//其他...略
}
這一套流程下來,波函數(shù)坍縮的算法就完成了.增加各式各樣的約束規(guī)則,可以將模塊拼成想要的整體.
以下是我自己制作一些簡單的模塊原型,然后套用這個算法制作出來的效果:
僅有五個模塊原型:
生成結(jié)果:
4.應(yīng)用案例
以下是其他國外開發(fā)者,用《波函數(shù)坍縮》的算法,制作出來的案例:
 生成城堡.gif
|
 生成管道.gif
|
 生成地球表面.gif
|
|---|---|---|
 生成島嶼.gif
|
 生成樓房.gif
|
 生成風(fēng)格化模型.gif
|
5.總結(jié)
從以上案例可以看出,通過這個算法,可以做出各式各樣的隨機地形.以為它是依賴規(guī)則,在規(guī)則以下做隨機坍縮.加以學(xué)習(xí)和使用,可以做出來很多很驚艷的東西~
5.1 利與弊
好處:
相對于地圖拼接的算法( Warcraft3地形拼接算法),這種算法實現(xiàn)出來的效果更靈活更豐富,更能適應(yīng)各種需求.
壞處:
1.算法復(fù)雜度較高而且不好量化,需要計算機自己試錯再回溯...(可以通過多線程來計算)
2.暫時沒有成熟的制作規(guī)范,模塊原型的制作難以考慮所有可能的情況.制作進(jìn)度不好把控.
5.2 模塊原型的制作流程?
關(guān)于模塊原型的制作流程,我個人有個建議可以先使用Unity的建模插件(ProBuilder等)制作簡單的原型,然后再讓美術(shù)同學(xué)細(xì)化原型.或者美術(shù)先制作整體的模型,再通過模型切割工具,把整體切分成多個模塊原型.
