基礎(chǔ) | Roguelike隨機(jī)地圖----洞穴類(lèi)(三)
本系列為筆者初學(xué)c/c++和游戲AI開(kāi)發(fā)的學(xué)習(xí)經(jīng)歷，練習(xí)為主，不涉及到具體的游戲開(kāi)發(fā)軟件學(xué)習(xí)(如unity，虛幻4等),適合剛?cè)腴T(mén)的小伙伴一起學(xué)習(xí)探討，歡迎在評(píng)論區(qū)留下意見(jiàn)。
開(kāi)發(fā)語(yǔ)言：c/c++ (11及以上)
開(kāi)發(fā)平臺(tái)：macOS mojave / Linux
編譯器：vs Code / g++
本章節(jié)知識(shí)點(diǎn)：
queue
list
啟發(fā)式搜索
3.處理地圖
3.1 啟發(fā)式搜索
啟發(fā)式算法可以這樣定義：一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（指計(jì)算時(shí)間和空間）下給出待解決組合優(yōu)化問(wèn)題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度一般不能被預(yù)計(jì)。
----百度百科
嚴(yán)格意義上，前兩個(gè)步驟已經(jīng)可以生成一張完整的隨機(jī)洞穴類(lèi)地圖，但這樣生成的地圖或多或少會(huì)出現(xiàn)一些細(xì)小的洞穴或者墻壁，不夠美觀。
因此我們可以通過(guò)啟發(fā)式搜索，來(lái)找出需要的某類(lèi)區(qū)域，實(shí)現(xiàn)方法可歸納為：
對(duì)某個(gè)點(diǎn)，若其上下左右四個(gè)點(diǎn)中有符合條件的點(diǎn)，則將該點(diǎn)(該點(diǎn)是上下左右四個(gè)點(diǎn)之一)加入搜索隊(duì)列，否則丟棄；
從搜索隊(duì)列中取出一個(gè)點(diǎn)，執(zhí)行1的操作；
重復(fù)1和2，直到隊(duì)列為空，也就是一定區(qū)域內(nèi)再也找不到符合條件的點(diǎn)為止。
這樣，我們通過(guò)啟發(fā)式搜索，就可以將地圖中某一類(lèi)區(qū)域全部標(biāo)記出來(lái)，如圖1所示：
3.2 代碼實(shí)現(xiàn)
首先，我們將處理地圖分為兩個(gè)操作，一是清除數(shù)量小于5的墻壁；二是清除數(shù)量小于15的地面，如圖2所示：
其中，清除區(qū)域的函數(shù)processRegion(),如圖3所示：
pointType: 要清除的區(qū)域的標(biāo)記，1為墻壁，0為地面
thresholdSize: 要清除的區(qū)域的大小
!pointType：清除方式為，若是1則改變?yōu)?，反之亦然；
其中，通過(guò)getRegions()函數(shù)獲取指定區(qū)域的集合，如圖4所示：
代碼實(shí)現(xiàn)如圖5,圖6：
Coord：自定義結(jié)構(gòu)體，用來(lái)存儲(chǔ)地圖上的具體的某個(gè)點(diǎn)的xy坐標(biāo)值，如圖5所示
regions: 二維列表，其形式為 [[區(qū)域1的全部點(diǎn)]，[區(qū)域2的全部點(diǎn)]]
mapFlags：計(jì)算過(guò)程中對(duì)地圖上的點(diǎn)進(jìn)行標(biāo)記
getRegionPoints函數(shù)：計(jì)算具體的某個(gè)區(qū)域的全部點(diǎn)
最后，getRegionPoints函數(shù)具體計(jì)算哪些點(diǎn)是屬于同一個(gè)區(qū)域，如圖6所示：
queue隊(duì)列：存儲(chǔ)下一步需要搜索判斷的點(diǎn)，從上下左右四個(gè)點(diǎn)中選擇
points列表：存儲(chǔ)屬于某個(gè)區(qū)域的全部點(diǎn)，最后返回該列表
到這里，一張可用于Roguelike游戲的洞穴類(lèi)地圖已經(jīng)基本生成完成，后續(xù)便可以往洞穴里面添加各種元素，如陷阱、寶箱、怪物等。
當(dāng)然到這一步，地圖上是有可能存在互不相通的多個(gè)洞穴區(qū)域的(如圖4)，我們可以往洞穴中放入傳送點(diǎn)來(lái)實(shí)現(xiàn)兩個(gè)洞穴區(qū)域的連通，也可以繼續(xù)通過(guò)算法來(lái)在不同洞穴區(qū)域之間生成可以通過(guò)的“道路”。
不同區(qū)域之間的連通算法有很多種，大多可以歸納到迷宮算法里面，下一章節(jié)筆者將運(yùn)用相似的思想，來(lái)簡(jiǎn)單實(shí)現(xiàn)不同區(qū)域的連通方法。
參考：https://www.youtube.com/watch?v=xYOG8kH2tF8
相關(guān)代碼下載：https://github.com/linpeijie/GameToy/tree/master/GameAI/Map
