本系列為筆者初學(xué)c/c++和游戲開(kāi)發(fā)時(shí)的入門博文，以算法和C/C++練習(xí)為主，不涉及到游戲開(kāi)發(fā)軟件(如unity，虛幻4等),適合剛?cè)腴T的小伙伴一起學(xué)習(xí)探討，歡迎在評(píng)論區(qū)留下意見(jiàn)。該系列重點(diǎn)講述Roguelike類型游戲，在早期開(kāi)發(fā)會(huì)涉及到的一些基礎(chǔ)算法。

• 開(kāi)發(fā)語(yǔ)言：c/c++

• 開(kāi)發(fā)平臺(tái)：macOS mojave / Linux

• 編譯器：vs Code

一、核心內(nèi)容

• 細(xì)胞自動(dòng)機(jī)（Cellular Automata）

• STL庫(kù)（vector，queue，list等）

• 啟發(fā)式搜索

二、實(shí)現(xiàn)方法

一張洞穴類地圖上包含兩個(gè)最基本的元素：墻壁，地面。前者阻擋角色的行動(dòng)，后者構(gòu)成可容納其他元素的“洞穴”。

我們最直觀的的構(gòu)造一個(gè)洞穴的方式，就是在墻壁中挖一個(gè)洞，這樣就形成一個(gè)最簡(jiǎn)單的洞穴。但是在游戲中，一個(gè)地圖往往需要一定的復(fù)雜度，來(lái)放置各式各樣的元素（如怪物、陷阱、寶箱等）。因此在上述方法的基礎(chǔ)上，我們可以通過(guò)細(xì)胞自動(dòng)機(jī)算法來(lái)構(gòu)造更復(fù)雜的洞穴。

由此可以形成最初的方案：

• 在大地圖的墻壁上隨機(jī)挖一些洞

• 每個(gè)細(xì)胞自動(dòng)吞食周圍一定范圍內(nèi)的墻壁，形成空洞

為了保證地圖的隨機(jī)性，我們加入一個(gè)隨機(jī)數(shù)，細(xì)化后可歸納出以下的實(shí)現(xiàn)步驟：

1. 構(gòu)建一個(gè)大地圖以二維平面圖表示，以二維數(shù)組存儲(chǔ)；地圖最外圍一圈為墻壁不變，地圖內(nèi)每個(gè)點(diǎn)以小于0.45的概率生成墻壁，其余為地面

2. 遍歷數(shù)組，對(duì)每個(gè)點(diǎn)執(zhí)行下列規(guī)則（細(xì)胞自動(dòng)機(jī)算法）：

• 對(duì)當(dāng)前點(diǎn)，若其周圍墻壁數(shù)量大于4個(gè)，則其設(shè)為墻壁

• 對(duì)當(dāng)前點(diǎn)，若其周圍墻比數(shù)量小于4個(gè)，則其設(shè)為地面

3. 遍歷地圖，對(duì)每個(gè)區(qū)域執(zhí)行下列規(guī)則（區(qū)域?yàn)榻?jīng)過(guò)2之后形成的“墻壁”和"洞穴",不是單獨(dú)的點(diǎn)，而是點(diǎn)的集合；啟發(fā)式搜索算法）：

• 對(duì)當(dāng)前區(qū)域，若該區(qū)域?yàn)閴Ρ谇覕?shù)量小于5個(gè)，則將該區(qū)域設(shè)為地面

• 對(duì)當(dāng)前區(qū)域，若該區(qū)域?yàn)榈孛媲覕?shù)量小于20個(gè)，則將該區(qū)域設(shè)為墻壁

4. 遍歷地圖，將所有獨(dú)立區(qū)域連通（也可以不連通，通過(guò)其他方式來(lái)抵達(dá)）。

三、最終成果示例

洞穴類地圖的簡(jiǎn)單生成方法核心部分介紹完畢，接下來(lái)會(huì)分幾章節(jié)詳細(xì)講解具體算法的實(shí)現(xiàn)，會(huì)給出相應(yīng)的代碼。歡迎有不同意見(jiàn)的小伙伴留言討論。