午夜18 视频在线观看,欧美日韩性爱,日韩AV中文字幕在线,豆花AV网站入口,亚洲毛片在线观看,一级成人片免费看,91天天干天天日,无码激情

作者：Hawstein。（本文閱讀需要約 9 分鐘）

小帥b?

前言

這兩天在網(wǎng)上看到一張讓人漲姿勢的圖片，圖片中展示的是貪吃蛇游戲，估計(jì)大部分人都玩過。但如果僅僅是貪吃蛇游戲，那么它就沒有什么讓人漲姿勢的地方了。問題的關(guān)鍵在于，圖片中的貪吃蛇真的很貪吃XD，它把矩形中出現(xiàn)的食物吃了個(gè)遍，然后華麗麗地把整個(gè)矩形填滿，真心是看得賞心悅目。作為一個(gè)CSer，第一個(gè)想到的是，這東西是寫程序?qū)崿F(xiàn)的(因?yàn)椋话闳烁刹怀鲞@事。果斷是要讓程序來干的)第二個(gè)想到的是，寫程序該如何實(shí)現(xiàn)，該用什么算法？既然開始想了，就開始做。Talk is cheap，show me the code。

開始之前，讓我們再欣賞一下那只讓人漲姿勢的貪吃蛇吧：( 如果下面的動(dòng)態(tài)圖片瀏覽效果不佳的話，可以保存下來查看)

語言選擇

Life is short, use python! 所以，根本就沒多想，直接上python。

最初版本

先讓你的程序跑起來

首先，我們第一件要做的就是先不要去分析這個(gè)問題。你好歹先寫個(gè)能運(yùn)行起來的貪吃蛇游戲，然后再去想AI部分。這個(gè)應(yīng)該很簡單， c\c++也就百來行代碼(如果我沒記錯(cuò)的話。不弄復(fù)雜界面，直接在控制臺下跑)， python就更簡單了，去掉注釋和空行，5、60行代碼就搞定了。而且，最最關(guān)鍵的，這個(gè)東西網(wǎng)上肯定寫濫了，你沒有必要重復(fù)造輪子，去弄一份來按照你的意愿改造一下就行了。

簡單版本

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

在一個(gè)矩形中，每一時(shí)刻有一個(gè)食物，貪吃蛇要在不撞到自己的條件下，找到一條路(未必要最優(yōu))，然后沿著這條路運(yùn)行，去享用它的美食

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

只要有選擇，就先選擇最簡單的方案，我們現(xiàn)在的目標(biāo)是要讓程序先跑起來，優(yōu)化是后話。so，從BFS開始。我們最初將蛇頭位置放入隊(duì)列，然后只要隊(duì)列非空，就將隊(duì)頭位置出隊(duì)，然后把它四領(lǐng)域內(nèi)的4個(gè)點(diǎn)放入隊(duì)列，不斷地循環(huán)操作，直到到達(dá)食物的位置。這個(gè)過程中，我們需要注意幾點(diǎn)：

1.訪問過的點(diǎn)不再訪問。2.保存每個(gè)點(diǎn)的父結(jié)點(diǎn)(即每個(gè)位置是從哪個(gè)位置走到它的，這樣我們才能把可行路徑找出來)。3.蛇身所在位置和四面墻不可訪問。

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

為了盡量保持簡單，我用的是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)。(我好愛講哲理XD)

BFS+Wander

上一節(jié)的簡單版本跑起來后，我們認(rèn)識到，只教貪吃蛇一種策略是不行的。它這么笨一條蛇，你不多教它一點(diǎn)，它分分鐘就會(huì)掛掉的。所以，我寫了個(gè)Wander函數(shù)，顧名思義，當(dāng)貪吃蛇陷入困境后，就別讓它再BFS了，而是讓它隨便四處走走，散散心，思考一下人生什么的。這個(gè)就好比你困惑迷茫的時(shí)候還去工作，效率不佳不說，還可能阻礙你走出困境；相反，這時(shí)候你如果放下手中的工作，停下來，出去旅個(gè)游什么的。回來時(shí)，說不定就豁然開朗，土地平曠，屋舍儼然了。

Wander函數(shù)怎么寫都行，但是肯定有優(yōu)劣之分。我寫了兩個(gè)版本，一個(gè)是在可行的范圍內(nèi)，朝隨機(jī)方向走隨機(jī)步。也就是說，蛇每次運(yùn)動(dòng)的方向是隨機(jī)出來的，總共運(yùn)動(dòng)的步數(shù)也是隨機(jī)的。Wander完之后，再去BFS一下，看能否吃到食物，如果可以那就皆大歡喜了。如果不行，說明思考人生的時(shí)間還不夠，再Wander一下。這樣過程不斷地循環(huán)進(jìn)行。可是就像“隨機(jī)過程隨機(jī)過”一樣，你“隨機(jī)Wander就隨機(jī)掛”。會(huì)Wander的蛇確實(shí)能多走好多步。可是有一天，它就會(huì)把自己給隨機(jī)到一條死路上了。陷入困境還可以Wander，進(jìn)入死胡同，那可沒有回滾機(jī)制。所以，第二個(gè)版本的Wander函數(shù)，我就讓貪吃蛇貪到底。在BFS無解后，告訴蛇一個(gè)步數(shù)step(隨機(jī)產(chǎn)生step)，讓它在空白區(qū)域以S形運(yùn)動(dòng)step步。這回運(yùn)動(dòng)方向就不隨機(jī)了，而是有組織有紀(jì)律地運(yùn)動(dòng)。先看圖，然后再說說它的問題：

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

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

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

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

高瞻遠(yuǎn)矚版本

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

蛇和食物間有路徑直接就去吃，不可取。那該怎么辦？
如果蛇去吃食物后，布局是安全的，是否就直接去吃？(這樣最優(yōu)嗎？)
怎樣定義布局是否安全？
蛇和食物之間如果沒有路徑，怎么辦？
最短路徑是否最優(yōu)？(這個(gè)明顯不是了)
那么，如果布局安全的情況下，最短路徑是否最優(yōu)？
除了最短路徑，我們還可以怎么走？S形？最長？
怎么應(yīng)對蛇身越來越長這個(gè)問題？
食物是隨機(jī)出現(xiàn)的，有沒可能出現(xiàn)無解的布局？
暴力法(brute force)能否得到最優(yōu)序列？(讓貪吃蛇盡可能地多吃食物)

只要去想，問題還挺多的。這時(shí)讓我們以面向過程的思想，帶著上面的問題，把思路理一理。一開始，蛇很短(初始化長度為1)，它看到了一個(gè)食物，使用BFS得到矩形中每個(gè)位置到達(dá)食物的最短路徑長度。在沒有蛇身阻擋下，就是曼哈頓距離。然后，我要先判斷一下，貪吃蛇這一去是否安全。

所以我需要一條虛擬的蛇，它每次負(fù)責(zé)去探路。如果安全，才讓真正的蛇去跑。當(dāng)然，虛擬的蛇是不會(huì)繪制出來的，它只負(fù)責(zé)模擬探路。

那么，怎么定義一個(gè)布局是安全的呢？如果你把文章開頭那張動(dòng)態(tài)圖片中蛇的銷魂走位好好的看一下，會(huì)發(fā)現(xiàn)即使到最后蛇身已經(jīng)很長了，它仍然沒事一般地走出了一條路。

而且，是跟著蛇尾走的！嗯，這個(gè)其實(shí)不難解釋，蛇在運(yùn)動(dòng)的過程中，消耗蛇身，蛇尾后面總是不斷地出現(xiàn)新的空間。蛇短的時(shí)候還無所謂，當(dāng)蛇一長，就會(huì)發(fā)現(xiàn)，要想活下來，基本就只能追著蛇尾跑了。在追著蛇尾跑的過程中，再去考慮能否安全地吃到食物。(下圖是某次BFS后，得到的一個(gè)布局， 0代表食物，數(shù)字代表該位置到達(dá)食物的距離，+號代表蛇頭，*號代表蛇身， -號代表蛇尾，#號代表空格，外面的一圈#號代表圍墻)

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

經(jīng)過上面的分析，我們可以將布局是否安全定義為蛇是否可以跟著蛇尾運(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)行安全判斷，然后再走。

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

好了，問題又來了。如果蛇和食物間不存在路徑且蛇和蛇尾間也不存在路徑，怎么辦？這個(gè)我是沒辦法了，選一步可行的路徑來走就是了。還是一個(gè)道理，每次只走一步，更新布局，然后再判斷蛇和食物間是否有安全路徑；沒有的話，蛇頭和蛇尾間是否存在路徑；還沒有，再挑一步可行的來走。

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

目標(biāo)是食物時(shí)，走最短路徑

目標(biāo)是蛇尾時(shí)，走最長路徑

那第三種情況呢？與食物和蛇尾都沒路徑存在的情況下，這個(gè)時(shí)候本來就只是挑一步可行的步子來走，最短最長關(guān)系都不大了。至于人為地讓蛇走S形，我覺得這不是什么好策略，最初版本中已經(jīng)分析過它的問題了。(當(dāng)然，除非你想使用最最無懈可擊的那個(gè)版本，就是完全不管食物，讓蛇一直走S，然后在墻邊留下一條過道即可。這樣一來，蛇總是可以完美地把所有食物吃完，然后占滿整個(gè)空間，可是就很boring了。沒有任何的意思)

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

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

其中，+號是蛇頭，-號是蛇尾，*號是蛇身，0是食物，#號代表空格，外面一圈# 號代表墻。這個(gè)布局上，食物已經(jīng)在蛇頭面前了，可是它能吃嗎？不能！因?yàn)樗酝晔澄锖螅L度加1，蛇頭就會(huì)把0的位置填上，布局就變成：

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

此時(shí)，由于蛇的長度加1，蛇尾沒有動(dòng)，而蛇頭被自己圍著，掛掉了。可是，我們卻還有一個(gè)空白的格子#沒有填充。按照我們之前教給蛇的策略，面對這種情況，蛇頭就只會(huì)一直追著蛇尾跑，每當(dāng)它和食物有路徑時(shí)，它讓虛擬的蛇跑一遍發(fā)現(xiàn)，得到的新布局是不安全的，所以不會(huì)去吃食物，而是選擇繼續(xù)追著蛇尾跑。然后它就這樣一直跑，一直跑。死循環(huán)，直到你按ESC鍵為止。

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

上面的最后一個(gè)問題，暴力法是否能得到最優(yōu)序列。從上面的分析看來，可以得到，但不能保證一定得到。

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

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

      convert?output.gif?-fuzz?10% -layers?Optimize?optimised.gif

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

Last but not least

如果對源代碼感興趣，請戳以下的鏈接:

https://github.com/Hawstein/snake-ai?

另外，本文的貪吃蛇程序使用了 curses 模塊，類 Unix 系統(tǒng)都默認(rèn)安裝的，使用 Windows 的童鞋需要安裝一下這個(gè)模塊，送上地址：

http://www.lfd.uci.edu/~gohlke/pythonlibs/#curses

以上的代碼仍然可以繼續(xù)改進(jìn)(現(xiàn)在加注釋不到 300 行，優(yōu)化一下可以更少)，也可用 pygame 或是 pyglet 庫把界面做得更加漂亮，Enjoy！

出處：

http://hawstein.com/2013/04/15/snake-ai/

如何用 Python 寫一個(gè) AI 貪吃蛇

先讓你的程序跑起來

簡單版本