散文網(wǎng) » 科技 »學(xué)習(xí) » 波函數(shù)坍縮算法

波函數(shù)坍縮算法

2023-07-31 19:32 作者:是傀貓貓啦 0人讀過 | 我要投稿

五月份的時候,差不多就是在比賽開始前吧,云杰說他剛學(xué)了一個做肉鴿隨機地圖生成很好的算法交波坍縮(也就是波函數(shù)坍縮)算法.他甚至寫了個小demo來實現(xiàn)這個算法,唉,為什么我就做不到呢,就算是A*尋路算法也是看別人的面經(jīng)提到說Unity NaviMesh用的算法是A*才去學(xué)了,就這也只是三腳貓功夫罷了根本就沒有實操一下.

不發(fā)牢騷了,我先學(xué)學(xué)波坍縮

1.啥是波函數(shù)坍縮

波函數(shù)坍縮是一個量子力學(xué)上的概念,但是計算機領(lǐng)域借鑒了這個算法的思路,從而有了計算機上的波函數(shù)坍縮生成算法.

它是一種利用局部的現(xiàn)有信息隨機外推到全局,形成一種隨機的確定狀態(tài)集合的方法.這種通過已有的信息推到全局的思路有點像動態(tài)規(guī)劃或者貪心,它們的應(yīng)用場景也是有重疊的.

簡單來說,最開始的時候所有的狀態(tài)都是不確定的,但是通過給定或者隨機確定一些局部的而信息,和這些一直信息相關(guān)的單元的狀態(tài)可以被確定,或者是更加靠近被被確定的狀況.描述一個單元的狀態(tài)確定程度的參數(shù)叫做"熵",這同樣是借鑒了熱物理的概念:熵是對混亂程度的描述.

b站上有個搬運視頻講的很好https://www.bilibili.com/video/BV19z4y127BJ 這個up主也貼心地附上原視頻地址,就是不知道他搬運的時候有沒有獲得許可.

舉個例子,數(shù)獨大家都玩過,它其實就是波坍縮算法最好的應(yīng)用場景,最開始每個格子上都有9種可能出現(xiàn)的數(shù)字,但是最初給定的幾個數(shù)字限制了其中的一些可能,比如說,如果某個格子的數(shù)字是4,那么和它同行/列的所有格子都不可能出現(xiàn)4,這就是發(fā)生了塌縮,這些格子的熵降低了.

熵越低的單元,確定性越大,就越容易給定狀態(tài),所以我們確定狀態(tài)時總會從熵低的單元開始,到數(shù)獨里面就是,我們會從已有數(shù)字更多的行/列上的空格子填數(shù)字.一旦某個單元塌縮到確定的狀態(tài),那它就可以作為給定狀態(tài)去影響和它有關(guān)的其他單元,或許會造成連鎖反應(yīng).不斷地確定更多狀態(tài),最終全局的所有狀態(tài)都能確定,這時就算是完成塌縮了.

2.波函數(shù)坍縮在游戲中的應(yīng)用

我能想到的最適合應(yīng)用波坍縮的地方是隨機地圖生成.4月面4399的時候,周末加班的面試官問了我一個問題:對于神廟逃亡那樣的跑酷游戲,它的每一段地圖都是隨機生成的,請你設(shè)計一種算法實現(xiàn)段地圖生成,要求不允許出現(xiàn)死角.所謂死角就是在玩家無法認(rèn)為躲避的區(qū)域,比如說,如果玩家必須跳過一個障礙,但是在障礙的落腳點處有一個陷阱,那么玩家無論如何都會死在這里,這就是死角.

當(dāng)時我給出的算法是基于貪心 ,首先單元化道路,如果以神廟逃亡為例,那么用數(shù)據(jù)表現(xiàn)道路的話可以用一個num[3][x]二維數(shù)組表示,因為一般陷阱都是出現(xiàn)在左1/3,右1/3或者是中間1/3的.在(可能是隨機)給定陷阱數(shù)量之后,在一條沒有任何機關(guān)陷阱的道路上添加陷阱,每添加一種陷阱,就會將因該陷阱而產(chǎn)生的死角區(qū)域從二維數(shù)組中禁用,所以每次添加陷阱的可選擇區(qū)域會越來越少,但是永遠(yuǎn)不會出現(xiàn)死角.

//我覺得我回答的挺好的啊,咋一面就掛了呢

現(xiàn)在想想,這種思路和波坍縮是共通的,在隨機給出部分陷阱以后,和這些陷阱有關(guān)的區(qū)域,其可能選擇的狀態(tài)就坍縮成"平地"這一種狀態(tài)了.所以,雖然波坍縮聽起來很牛逼但本質(zhì)上也是一種啟發(fā)式的生成算法,沒有聽著那么高深莫測

另外一個例子是肉鴿地圖生成,利用規(guī)則為地圖單元提供約束,在給定初始數(shù)據(jù)(比如說種子)以后就能不斷降低全局的熵,從而最終得到一個隨機生成的確定狀態(tài)地圖.

3.實戰(zhàn):從1開始的基于波函數(shù)坍縮算法的隨機地圖生成器

為什么從1開始,因為我不是0(開個玩笑,我是直男)

設(shè)計一個使用若干瓦片組成的地圖,地圖中的元素只有道路,道路端點和草坪,要求是:所有的道路都必須有頭有尾,不能中斷,這句話是說,任何一條道路,無論它如何分叉,每一個盡頭都要有一個端點,看看下面的瓦片和我的效果圖就明白了:

下面6個瓦片是我要用到的素材,按照它們的特征,用他們四個方向的狀態(tài)命名,如0100表示上右下左四個方向里,右邊這個方向是道路,其他的是草坪

從圖中可以看出來所有的道路都被灰色的端點限制住.

由于僅作學(xué)習(xí),我沒有嚴(yán)格的使用規(guī)范或是框架來規(guī)范化編碼,所以只寫了兩個文件,我會盡可能解釋的清楚一些的

3.1代碼

Slot.ts

每個瓦片單元的數(shù)據(jù)結(jié)構(gòu),需要注意的是,這個數(shù)據(jù)結(jié)構(gòu)沒有繼承component,這是因為這個類被SlotManager類管理,生成對應(yīng)的Node是由Manager負(fù)責(zé),Slot在這里只是數(shù)據(jù)載體.