前言

這兩天在網(wǎng)上看到一張讓人漲姿勢(shì)的圖片滔蝉，圖片中展示的是貪吃蛇游戲， 估計(jì)大部分人都玩過(guò)塔沃。但如果僅僅是貪吃蛇游戲蝠引，那么它就沒(méi)有什么讓人漲姿勢(shì)的地方了。 問(wèn)題的關(guān)鍵在于蛀柴，圖片中的貪吃蛇真的很貪吃XD螃概，它把矩形中出現(xiàn)的食物吃了個(gè)遍， 然后華麗麗地把整個(gè)矩形填滿鸽疾，真心是看得賞心悅目吊洼。作為一個(gè)CSer， 第一個(gè)想到的是肮韧，這東西是寫(xiě)程序?qū)崿F(xiàn)的(因?yàn)槿邗澹话闳烁刹怀鲞@事旺订。 果斷是要讓程序來(lái)干的)第二個(gè)想到的是，寫(xiě)程序該如何實(shí)現(xiàn)超燃，該用什么算法区拳？ 既然開(kāi)始想了，就開(kāi)始做意乓。因?yàn)門(mén)alk is cheap樱调，要show me the code才行。 (從耗子叔那學(xué)來(lái)的)

開(kāi)始之前届良，讓我們?cè)傩蕾p一下那只讓人漲姿勢(shì)的貪吃蛇吧：( 如果下面的動(dòng)態(tài)圖片瀏覽效果不佳的話笆凌，可以右鍵保存下來(lái)查看)

語(yǔ)言選擇

Life is short, use python! 所以，根本就沒(méi)多想士葫，直接上python乞而。

最初版本

先讓你的程序跑起來(lái)

首先，我們第一件要做的就是先不要去分析這個(gè)問(wèn)題慢显。 你好歹先寫(xiě)個(gè)能運(yùn)行起來(lái)的貪吃蛇游戲爪模，然后再去想AI部分。這個(gè)應(yīng)該很簡(jiǎn)單荚藻， c\c++也就百來(lái)行代碼(如果我沒(méi)記錯(cuò)的話屋灌。不弄復(fù)雜界面，直接在控制臺(tái)下跑)应狱， python就更簡(jiǎn)單了共郭，去掉注釋和空行，5疾呻、60行代碼就搞定了除嘹。而且，最最關(guān)鍵的罐韩， 這個(gè)東西網(wǎng)上肯定寫(xiě)濫了憾赁，你沒(méi)有必要重復(fù)造輪子污朽， 去弄一份來(lái)按照你的意愿改造一下就行了散吵。

簡(jiǎn)單版本

我覺(jué)得直接寫(xiě)perfect版本不是什么好路子。因?yàn)閜erfect版本往往要考慮很多東西蟆肆， 直接上來(lái)就寫(xiě)這個(gè)一般是bug百出的矾睦。所以， 一開(kāi)始我的目標(biāo)僅僅是讓程序去控制貪吃蛇運(yùn)動(dòng)炎功，讓它去吃食物枚冗，僅此而已。 現(xiàn)在讓我們來(lái)陳述一下最初的問(wèn)題：

在一個(gè)矩形中蛇损，每一時(shí)刻有一個(gè)食物赁温，貪吃蛇要在不撞到自己的條件下坛怪，

找到一條路(未必要最優(yōu))，然后沿著這條路運(yùn)行股囊，去享用它的美食

我們先不去想蛇會(huì)越來(lái)越長(zhǎng)這個(gè)事實(shí)袜匿，問(wèn)題基本就是，給你一個(gè)起點(diǎn)(蛇頭)和一個(gè)終點(diǎn)( 食物)稚疹，要避開(kāi)障礙物(蛇身)居灯，從起點(diǎn)找到一條可行路到達(dá)終點(diǎn)。 我們可以用的方法有：

BFS

DFS

A*

只要有選擇内狗，就先選擇最簡(jiǎn)單的方案怪嫌，我們現(xiàn)在的目標(biāo)是要讓程序先跑起來(lái)， 優(yōu)化是后話柳沙。so岩灭，從BFS開(kāi)始。我們最初將蛇頭位置放入隊(duì)列赂鲤，然后只要隊(duì)列非空川背， 就將隊(duì)頭位置出隊(duì)，然后把它四領(lǐng)域內(nèi)的4個(gè)點(diǎn)放入隊(duì)列蛤袒，不斷地循環(huán)操作熄云， 直到到達(dá)食物的位置。這個(gè)過(guò)程中妙真，我們需要注意幾點(diǎn)：1.訪問(wèn)過(guò)的點(diǎn)不再訪問(wèn)缴允。 2.保存每個(gè)點(diǎn)的父結(jié)點(diǎn)(即每個(gè)位置是從哪個(gè)位置走到它的， 這樣我們才能把可行路徑找出來(lái))珍德。3.蛇身所在位置和四面墻不可訪問(wèn)练般。

通過(guò)BFS找到食物后，只需要讓蛇沿著可行路徑運(yùn)動(dòng)即可锈候。這個(gè)簡(jiǎn)單版本寫(xiě)完后薄料， 貪吃蛇就可以很歡快地運(yùn)行一段時(shí)間了”昧眨看圖吧：(不流暢的感覺(jué)來(lái)自錄屏軟件＠_＠)

為了盡量保持簡(jiǎn)單摄职，我用的是curses模塊，直接在終端進(jìn)行繪圖获列。 從上面的動(dòng)態(tài)圖片可以看出谷市，每次都單純地使用BFS，最終有一天击孩， 貪吃蛇會(huì)因?yàn)檫@種不顧后果的短視行為而陷入困境迫悠。 而且，即使到了那個(gè)時(shí)候巩梢，它也只會(huì)BFS一種策略创泄， 導(dǎo)致因?yàn)楫?dāng)前看不到目標(biāo)(食物)艺玲，認(rèn)為自己這輩子就這樣了，破罐子破摔鞠抑， 最終停在它人生中的某一個(gè)點(diǎn)板驳，不再前進(jìn)。(我好愛(ài)講哲理XD)

BFS+Wander

上一節(jié)的簡(jiǎn)單版本跑起來(lái)后碍拆，我們認(rèn)識(shí)到若治，只教貪吃蛇一種策略是不行的。 它這么笨一條蛇感混，你不多教它一點(diǎn)端幼，它分分鐘就會(huì)掛掉的。 所以弧满，我寫(xiě)了個(gè)Wander函數(shù)婆跑，顧名思義，當(dāng)貪吃蛇陷入困境后庭呜， 就別讓它再BFS了滑进，而是讓它隨便四處走走，散散心募谎，思考一下人生什么的扶关。 這個(gè)就好比你困惑迷茫的時(shí)候還去工作，效率不佳不說(shuō)数冬，還可能阻礙你走出困境节槐； 相反，這時(shí)候你如果放下手中的工作拐纱，停下來(lái)铜异，出去旅個(gè)游什么的〗占埽回來(lái)時(shí)揍庄， 說(shuō)不定就豁然開(kāi)朗，土地平曠东抹，屋舍儼然了蚂子。

Wander函數(shù)怎么寫(xiě)都行，但是肯定有優(yōu)劣之分府阀。我寫(xiě)了兩個(gè)版本缆镣，一個(gè)是在可行的范圍內(nèi)芽突， 朝隨機(jī)方向走隨機(jī)步试浙。也就是說(shuō)，蛇每次運(yùn)動(dòng)的方向是隨機(jī)出來(lái)的寞蚌， 總共運(yùn)動(dòng)的步數(shù)也是隨機(jī)的田巴。Wander完之后钠糊，再去BFS一下，看能否吃到食物壹哺， 如果可以那就皆大歡喜了抄伍。如果不行，說(shuō)明思考人生的時(shí)間還不夠管宵，再Wander一下截珍。 這樣過(guò)程不斷地循環(huán)進(jìn)行÷崞樱可是就像“隨機(jī)過(guò)程隨機(jī)過(guò)”一樣岗喉，你“隨機(jī)Wander就隨機(jī)掛”。 會(huì)Wander的蛇確實(shí)能多走好多步炸庞∏玻可是有一天，它就會(huì)把自己給隨機(jī)到一條死路上了埠居。 陷入困境還可以Wander查牌，進(jìn)入死胡同，那可沒(méi)有回滾機(jī)制滥壕。所以纸颜， 第二個(gè)版本的Wander函數(shù)，我就讓貪吃蛇貪到底绎橘。在BFS無(wú)解后懂衩， 告訴蛇一個(gè)步數(shù)step(隨機(jī)產(chǎn)生step)，讓它在空白區(qū)域以S形運(yùn)動(dòng)step步金踪。 這回運(yùn)動(dòng)方向就不隨機(jī)了浊洞，而是有組織有紀(jì)律地運(yùn)動(dòng)。先看圖胡岔，然后再說(shuō)說(shuō)它的問(wèn)題：

沒(méi)錯(cuò)法希，最終還是掛掉了。S形運(yùn)動(dòng)也是無(wú)法讓貪吃蛇避免死亡的命運(yùn)靶瘸。 貪吃蛇可以靠S形運(yùn)動(dòng)多存活一段時(shí)間苫亦，可是由于它的策略是：

while沒(méi)有按下ESC鍵:if蛇與食物間有路徑:走起，吃食物去else:Wander一段時(shí)間

問(wèn)題就出在蛇發(fā)現(xiàn)它自己和食物間有路徑怨咪，就二話不說(shuō)跑去吃食物了屋剑。 它沒(méi)有考慮到，你這一去把食物給吃了后形成的局勢(shì)(蛇身布局)诗眨， 完全就可能讓你掛掉唉匾。(比如進(jìn)入了一個(gè)自己蛇身圍起來(lái)的封閉小空間)

so，為了能讓蛇活得久一些，它還要更高瞻遠(yuǎn)矚才行巍膘。

高瞻遠(yuǎn)矚版本

我們現(xiàn)在已經(jīng)有了一個(gè)比較低端的版本厂财，而且對(duì)問(wèn)題的認(rèn)識(shí)也稍微深入了一些。 現(xiàn)在可以進(jìn)行一些比較慎密和嚴(yán)謹(jǐn)?shù)姆治隽讼啃浮Ｊ紫攘Пィ屛覀兞_列一些問(wèn)題： (像頭腦風(fēng)暴那樣，想到什么就寫(xiě)下來(lái)即可)

蛇和食物間有路徑直接就去吃肪康，不可取荚恶。那該怎么辦？

如果蛇去吃食物后磷支，布局是安全的裆甩，是否就直接去吃？(這樣最優(yōu)嗎齐唆？)

怎樣定義布局是否安全嗤栓？

蛇和食物之間如果沒(méi)有路徑，怎么辦箍邮？

最短路徑是否最優(yōu)茉帅？(這個(gè)明顯不是了)

那么，如果布局安全的情況下锭弊，最短路徑是否最優(yōu)堪澎？

除了最短路徑，我們還可以怎么走味滞？S形樱蛤？最長(zhǎng)？

怎么應(yīng)對(duì)蛇身越來(lái)越長(zhǎng)這個(gè)問(wèn)題剑鞍？

食物是隨機(jī)出現(xiàn)的昨凡，有沒(méi)可能出現(xiàn)無(wú)解的布局？

暴力法(brute force)能否得到最優(yōu)序列蚁署？(讓貪吃蛇盡可能地多吃食物)

只要去想便脊，問(wèn)題還挺多的。這時(shí)讓我們以面向過(guò)程的思想光戈，帶著上面的問(wèn)題哪痰， 把思路理一理。一開(kāi)始久妆，蛇很短(初始化長(zhǎng)度為1)晌杰，它看到了一個(gè)食物， 使用BFS得到矩形中每個(gè)位置到達(dá)食物的最短路徑長(zhǎng)度筷弦。在沒(méi)有蛇身阻擋下肋演， 就是曼哈頓距離。然后，我要先判斷一下惋啃，貪吃蛇這一去是否安全哼鬓。 所以我需要一條虛擬的蛇监右，它每次負(fù)責(zé)去探路边灭。如果安全，才讓真正的蛇去跑健盒。 當(dāng)然绒瘦，虛擬的蛇是不會(huì)繪制出來(lái)的，它只負(fù)責(zé)模擬探路扣癣。那么惰帽， 怎么定義一個(gè)布局是安全的呢？ 如果你把文章開(kāi)頭那張動(dòng)態(tài)圖片中蛇的銷魂走位好好的看一下父虑， 會(huì)發(fā)現(xiàn)即使到最后蛇身已經(jīng)很長(zhǎng)了该酗，它仍然沒(méi)事一般地走出了一條路。而且士嚎， 是跟著蛇尾走的呜魄！嗯，這個(gè)其實(shí)不難解釋莱衩，蛇在運(yùn)動(dòng)的過(guò)程中爵嗅，消耗蛇身， 蛇尾后面總是不斷地出現(xiàn)新的空間笨蚁。蛇短的時(shí)候還無(wú)所謂睹晒，當(dāng)蛇一長(zhǎng)， 就會(huì)發(fā)現(xiàn)括细，要想活下來(lái)伪很，基本就只能追著蛇尾跑了。在追著蛇尾跑的過(guò)程中奋单， 再去考慮能否安全地吃到食物是掰。(下圖是某次BFS后，得到的一個(gè)布局辱匿， 0代表食物键痛，數(shù)字代表該位置到達(dá)食物的距離，+號(hào)代表蛇頭匾七，*號(hào)代表蛇身絮短， -號(hào)代表蛇尾，#號(hào)代表空格昨忆，外面的一圈#號(hào)代表圍墻)

# # # # # # # # 0 1 2 3 4 # # 1 2 3 # 5 # # 2 3 4 - 6 # # 3 + * * 7 # # 4 5 6 7 8 # # # # # # # #

經(jīng)過(guò)上面的分析丁频，我們可以將布局是否安全定義為蛇是否可以跟著蛇尾運(yùn)動(dòng)， 也就是蛇吃完食物后，蛇頭和蛇尾間是否存在路徑席里，如果存在叔磷，我就認(rèn)為是安全的。

OK奖磁，繼續(xù)改基。真蛇派出虛擬蛇去探路后，發(fā)現(xiàn)吃完食物后的布局是安全的咖为。那么秕狰， 真蛇就直奔食物了。等等躁染，這樣的策略好嗎鸣哀？未必。因?yàn)樯呙窟\(yùn)動(dòng)一步吞彤， 布局就變化一次我衬。布局一變就意味著可能存在更優(yōu)解。比如因?yàn)樯呶驳南模?原本需要繞路才能吃到的食物饰恕，突然就出現(xiàn)在蛇眼前了挠羔。所以，真蛇走一步后懂盐， 更好的做法是褥赊，重新做BFS。然后和上面一樣進(jìn)行安全判斷莉恼，然后再走拌喉。

接下來(lái)我們來(lái)考慮一下，如果蛇和食物之間不存在路徑怎么辦俐银？ 上文其實(shí)已經(jīng)提到了做法了尿背，跟著蛇尾走。只要蛇和食物間不存在路徑捶惜， 蛇就一直跟著蛇尾走田藐。同樣的，由于每走一步布局就會(huì)改變吱七， 所以每走一步就重新做BFS得到最新布局汽久。

好了，問(wèn)題又來(lái)了踊餐。如果蛇和食物間不存在路徑且蛇和蛇尾間也不存在路徑景醇， 怎么辦？這個(gè)我是沒(méi)辦法了吝岭，選一步可行的路徑來(lái)走就是了三痰。還是一個(gè)道理吧寺， 每次只走一步，更新布局散劫，然后再判斷蛇和食物間是否有安全路徑稚机； 沒(méi)有的話，蛇頭和蛇尾間是否存在路徑获搏；還沒(méi)有赖条，再挑一步可行的來(lái)走。

上面列的好幾個(gè)問(wèn)題里都涉及到蛇的行走策略颜凯，一般而言夸赫， 我們會(huì)讓蛇每次都走最短路徑敬扛。這是針對(duì)蛇去吃食物的時(shí)候， 可是蛇在追自己的尾巴的時(shí)候就不能這么考慮了但荤。我們希望的是蛇頭在追蛇尾的過(guò)程中早芭， 盡可能地慢彼城。這樣蛇頭和蛇尾間才能騰出更多的空間，空間多才有得發(fā)展退个。 所以蛇的行走策略主要分為兩種：

1. 目標(biāo)是食物時(shí)募壕，走最短路徑2. 目標(biāo)是蛇尾時(shí)，走最長(zhǎng)路徑

那第三種情況呢语盈？與食物和蛇尾都沒(méi)路徑存在的情況下舱馅， 這個(gè)時(shí)候本來(lái)就只是挑一步可行的步子來(lái)走，最短最長(zhǎng)關(guān)系都不大了刀荒。 至于人為地讓蛇走S形代嗤，我覺(jué)得這不是什么好策略，最初版本中已經(jīng)分析過(guò)它的問(wèn)題了缠借。 (當(dāng)然干毅，除非你想使用最最無(wú)懈可擊的那個(gè)版本，就是完全不管食物泼返， 讓蛇一直走S硝逢，然后在墻邊留下一條過(guò)道即可。這樣一來(lái)绅喉， 蛇總是可以完美地把所有食物吃完渠鸽，然后占滿整個(gè)空間，可是就很boring了柴罐。 沒(méi)有任何的意思)

上面還提到一個(gè)問(wèn)題：因?yàn)槭澄锸请S機(jī)出現(xiàn)的徽缚，有沒(méi)可能出現(xiàn)無(wú)解的局面？ 答案是：有丽蝎。我運(yùn)行了程序猎拨，然后把每一次布局都輸出到log膀藐，發(fā)現(xiàn)會(huì)有這樣的情況：

# # # # # # # # * * * * * # # * * - 0 * # # * * # + * # # * * * * * # # * * * * * # # # # # # # #

其中，+號(hào)是蛇頭红省，-號(hào)是蛇尾额各，*號(hào)是蛇身，0是食物吧恃，#號(hào)代表空格虾啦，外面一圈# 號(hào)代表墻。這個(gè)布局上痕寓，食物已經(jīng)在蛇頭面前了傲醉，可是它能吃嗎？不能呻率！ 因?yàn)樗酝晔澄锖笥脖希L(zhǎng)度加1，蛇頭就會(huì)把0的位置填上礼仗，布局就變成：

# # # # # # # # * * * * * # # * * - + * # # * * # * * # # * * * * * # # * * * * * # # # # # # # #

此時(shí)吐咳，由于蛇的長(zhǎng)度加1，蛇尾沒(méi)有動(dòng)元践，而蛇頭被自己圍著韭脊，掛掉了〉ヅ裕可是沪羔， 我們卻還有一個(gè)空白的格子#沒(méi)有填充。按照我們之前教給蛇的策略象浑， 面對(duì)這種情況蔫饰，蛇頭就只會(huì)一直追著蛇尾跑，每當(dāng)它和食物有路徑時(shí)融柬， 它讓虛擬的蛇跑一遍發(fā)現(xiàn)死嗦，得到的新布局是不安全的，所以不會(huì)去吃食物粒氧， 而是選擇繼續(xù)追著蛇尾跑越除。然后它就這樣一直跑，一直跑外盯。死循環(huán)摘盆， 直到你按ESC鍵為止。

由于食物是隨機(jī)出現(xiàn)的饱苟，所以有可能出現(xiàn)上面這種無(wú)解的布局孩擂。當(dāng)然了， 你也可以得到完滿的結(jié)局箱熬，貪吃蛇把整個(gè)矩形都填充滿类垦。

上面的最后一個(gè)問(wèn)題狈邑，暴力法是否能得到最優(yōu)序列。從上面的分析看來(lái)蚤认， 可以得到米苹，但不能保證一定得到。

最后砰琢，看看高瞻遠(yuǎn)矚的蛇是怎么跑的吧：

矩形大小10*20蘸嘶，除去外面的邊框，也就是8*18陪汽。Linux下錄完屏再轉(zhuǎn)成GIF格式的圖片训唱， 優(yōu)化前40多M，真心是沒(méi)法和Windows的比挚冤。用下面的命令優(yōu)化時(shí)况增， 有一種系統(tǒng)在用生命做優(yōu)化的感覺(jué)：

convertoutput.gif-fuzz10%-layersOptimizeoptimised.gif

最后還是拿到Windows下用AE，三下五除二用圖片序列合成的動(dòng)態(tài)圖片 (記得要在format options里選looping你辣，不然圖片是不會(huì)循環(huán)播放的)

源碼加群923414804免費(fèi)獲取巡通，更有大量免費(fèi)學(xué)習(xí)資料尘执。