制作背景

大一結束的暑假經(jīng)常喜歡寫各種程序，有一天，好友 Rutubet 要求我們兩個人進行一場編程比賽，比賽的內(nèi)容是：用自己熟悉的語言做一個游戲：生成二維隨機俯視地形，能夠讓主角在地形中進行移動，地圖由“墻體”、“空氣”方塊組成，就像“Minecraft”一樣，只不過是二維的，像“推箱子”小游戲的那種地形。選做內(nèi)容是：保存地圖，讀取地圖，新的方塊，生成處處可達的地形。比賽時間是兩個小時。

生成處處可達的地形的意思就是說，比如在一個推箱子中游戲關卡中，每一個空氣方塊都是主角能夠到達的地方，地圖里沒有一個“空穴”，就是沒有一個封閉的、進不去的地方，處處都是連通的。（這一項本來是必須做的，但是考慮到了時間和難度，我們都同意將它改為選做了）

我們兩個人在比賽內(nèi)都沒做這個處處可達的效果，但是我在比賽時間外經(jīng)過一番思考，增添了這個功能。

主要思路

對于處處可達的地形生成，我是這樣做的（沒有參考任何相關資料，自己設計的，可能有不妥的地方）：

做一個能夠判斷地形是否是處處可達的判斷函數(shù)，這個函數(shù)實現(xiàn)后，生成地形的時候就很輕松了。

生成地形的時候就在一個全是空氣的地圖里的隨機位置上丟一個墻體，然后調(diào)用這個判斷函數(shù)，如果丟一塊墻體這個操作使得整個地圖由通達狀態(tài)變成了不通達狀態(tài)，就“撤銷”這一步操作，即把丟到的位置改為空氣方塊。

（后來我在做成功的時候，又想到了一種效果，那就是可以直接丟一個2x2的大墻體，或者一個更大的接近圓形的墻體塊作為每次丟的內(nèi)容，甚至還可以丟各種形狀的大墻塊，只要丟的大墻塊本身自己不是閉合的，就可以，比如說丟一個空心的o形墻就不行。在撤銷的時候，會直接把這個丟的內(nèi)容中含有墻的方塊對應的地圖上的位置變成空氣方塊，可能丟的內(nèi)容有一部分已經(jīng)在墻上，有一部分不在墻上，但是這一丟導致了地圖變成了非處處可達狀態(tài)，于是就會把剛剛丟在空氣里的和丟在墻上的墻體都變成空氣，即：會出現(xiàn)撤銷的時候會把墻直接吃掉一部分的這種效果，不過這并不影響處處可達的結果，反而我覺得這就是我想要的效果）

上述步驟執(zhí)行很多很多次，每丟一個方塊就判斷一次處處可達，等到丟的方塊非常多的時候，就生成了一個處處可達的地形了。（我知道這樣很費時間，但是我認為這是非常好想到并且比較容易實現(xiàn)的方法了，我于是抱著看看效果的心態(tài)先就做出來）

那么接下來的重點就放在實現(xiàn)那個地形處處可達的判斷函數(shù)了。

在想判斷函數(shù)的時候我想到了一幅畫面，在空氣方塊中滴一滴墨水，這個墨水開始向四周擴散，但是會受到墻體的阻礙，等墨水擴散完畢了之后，如果所有的空氣方塊都被墨水所侵染，那么整個地圖就是處處通達的，否則就說明有的地方墨水無法觸及，整個地圖不是處處通達的。

根據(jù)上面的想法，只要遍歷整個地圖里的每一個方塊，只要一找到空氣方塊，就開始執(zhí)行“滴墨水”的操作，實時統(tǒng)計被墨水感染的方塊的數(shù)量，如果被墨水感染的數(shù)量等于空氣方塊的數(shù)量，那么判斷函數(shù)就通過了。

那么接下來的重點就放在怎么實現(xiàn)墨水擴展上了

我們把每一個被感染的空氣方塊想象成一個“哨兵”、“傳播者”或者“拓荒者”。（也許是因為高中英語有一個這個單詞記憶的比較深刻，所以就給變量名這么取名了），這個拓荒者是一個類對象，它有很多的屬性和功能。

首先它能向周圍（給上下左右四個格子，不能斜著）傳遞信息，讓更多的拓荒者誕生，那么我們就給它一個directions屬性，用來表示它接下來會向哪個方向發(fā)射信息，這時候就有問了，每個拓荒者不都是向周圍四個方向上發(fā)射信息嗎？不用這個屬性也無妨。但是這只是第一個拓荒者，它是向四個方向傳播的，第二代拓荒者就不是了，第二代拓荒者中位于最開始拓荒者右邊的新的拓荒者它就沒有必要再往左側傳遞信息了，（因為它就是從左邊傳來的信息誕生出來的，所以它只需要向右，上，下三個方向傳遞信息。）

拓荒者有以下屬性：

• 位置（表示自己在地圖中的作標位置）

• 是否是第一個拓荒者isFirst（第一個拓荒者比較特殊，因為它的傳播方向有四個，其他的都是三個）

• 受到的信息massage（表示這個拓荒者是從上一個拖航這的哪個方向上傳來的，這屬性決定它接下來發(fā)消息的三個方向，如果是第一個拓荒者，那么它沒有收到消息，就用(0, 0)來表示沒有）

• 接下來的傳播方向directions（一般是三個，但是如果是第一個拓荒者，那么它就有四個方向）

• 是否工作isWorking（用來在接下來迭代的過程中方便遍歷每一個拓荒者用）

整個傳播的過程需要三個一維列表，也用于表示拓荒者的三種狀態(tài)：

1. workingPioneerArray：里面存放正在工作中的拓荒者，每次遍歷的時候只遍歷這個數(shù)組就可以了

2. pioneerArray：里面存放工作完成的拓荒者，最終統(tǒng)計數(shù)量的時候直接len這個列表就可以了

3. nextWorkingPioneer：里面存放下一步中才開始執(zhí)行工作的拓荒者，也就是當前一步中剛誕生的

還需要一個二維數(shù)組，這個二維數(shù)組和地圖一樣大，相當于又建立了一個只表示拓荒者有無的圖層：

• pioneerFlag[Y][X]：里面存放所有不同狀態(tài)的拓荒者，這個用于防止拓荒者傳播的時候出現(xiàn)兩個拓荒者重復站在一個位置上

接下來

只要循環(huán)直到?jīng)]有工作中的拓荒者了，就結束了，循環(huán)執(zhí)行什么操作呢？

循環(huán)遍歷執(zhí)行每個拓荒者的傳播操作，就是遍歷每一個拓荒者的傳播方向?qū)傩?，如果這個傳播方向上的對應的位置上既不是不可走上去的墻體，同時在pioneerFlag對應位置上沒有拓荒者，滿足這兩個條件就可以讓這個位置上的拓荒者誕生，并讓誕生的拓荒者添加到nextWorkingPioneer。怎么讓拓荒者誕生？就創(chuàng)建一個新的拓荒者類的實例，傳入相應參數(shù)就可以了，但是注意需要根據(jù)massage屬性來確定它接下來的傳播方向

遍歷結束后需要對三個列表進行內(nèi)容上的修改：

• 每遍歷結束一個拓荒者，這個拓荒者的工作就結束了，讓它的isWorking屬性改為False，并將它添加到pioneerArray。

• 每迭代一次，即遍歷完所有工作中的拓荒者一波，就需要讓nextWorkingPioneer中的拓荒者覆蓋workingPioneerArray，并清空nextWorkingPioneer中的拓荒者。

詳細信息可以看代碼

效果截圖

源代碼

此源代碼為整個項目的所有源代碼

總結與反思

我的這種算法時間復雜度太大，空間復雜度也不小，因此還需要改進。

我還需要學習一些相關算法知識，純自己做出來的感覺有些地方可能有點冗余。