吃滿(mǎn)全圖？實(shí)現(xiàn)全自動(dòng)貪吃蛇的一種可能（基于Python Turtle）
【本文富含GIF，請(qǐng)作好準(zhǔn)備】
剛學(xué)會(huì)做貪吃蛇游戲時(shí)，B站就向我推了這個(gè)：
細(xì)膩的操作、精準(zhǔn)的計(jì)算，每一步穿插避讓都如此完美，想必是由程序控制。
也不知哪來(lái)的勇氣，我決定自己學(xué)著寫(xiě)一個(gè)……
v0.0：廣度優(yōu)先搜索實(shí)現(xiàn)尋路
查閱了幾個(gè)自動(dòng)貪吃蛇的實(shí)現(xiàn)思路后，無(wú)一例外提及了“搜索算法”，所以第一天的任務(wù)確定：學(xué)會(huì)一種能用于貪吃蛇尋路的“搜索算法”！
利用B站知識(shí)區(qū)豐富的資源，我首先使用廣度優(yōu)先搜索算法（BFS）實(shí)現(xiàn)了尋路（其實(shí)是只學(xué)了這一種后就怠惰了），當(dāng)天成果如下：
v0.1：生搬硬套BFS的笨蛇
在真正開(kāi)始前，有必要明確一下貪吃蛇游戲的規(guī)則：
????1. 蛇分為多節(jié)，每吃到一次食物增加一節(jié)
????2. 蛇頭可以向前、向左、向右行進(jìn)，后面的蛇身跟隨之
????3. 蛇頭行進(jìn)方向上撞到圍墻或自身身體，即為游戲失??；遇到食物，則身體加一節(jié)
畫(huà)一個(gè)10*10的地圖，把起點(diǎn)和終點(diǎn)改為蛇頭和食物，套用BFS算法，即實(shí)現(xiàn)如下效果：
貪吃蛇動(dòng)起來(lái)了！然而，當(dāng)身體變長(zhǎng)，它很快就掛了。可見(jiàn)，無(wú)盡的貪婪終將把自己逼上絕路
進(jìn)行幾次實(shí)驗(yàn)后，我發(fā)現(xiàn)了貪吃蛇的兩大致死原因：
????1. 蛇身過(guò)長(zhǎng)，將地圖分為至少兩個(gè)封閉圖形，蛇頭與食物間無(wú)通路（如下圖a，我愿稱(chēng)這種情況為“生存狀態(tài)”）
????2. 食物出現(xiàn)在了刁鉆的位置，蛇吃到后將走入死路（如下圖b，我稱(chēng)之為“迷茫狀態(tài)”）
#能吃到食物且吃到食物后，還能追到蛇尾的狀態(tài)，我稱(chēng)之為“快樂(lè)狀態(tài)”? ? [手動(dòng)滑稽]
于是有兩個(gè)對(duì)應(yīng)的解決策略：
????1. 因?yàn)?span id="s0sssss00s" class="color-green-04">蛇每往前走一格，蛇尾就會(huì)空一格出來(lái)，所以蛇頭跟著蛇尾方向走肯定不會(huì)死；
????2. 如果食物出現(xiàn)在死路里，就不應(yīng)該去吃它。但如何判斷？其實(shí)，“食物在死路里”的一個(gè)充分條件是“吃了這塊食物后，蛇頭與蛇尾沒(méi)有通路”。所以，要讓蛇學(xué)會(huì)“三思而后行”，在奔向食物前想想，吃了這塊“毒蘋(píng)果”后是不是再走向蛇尾，如果不能，就只好去追趕蛇尾，以伺良機(jī)（指進(jìn)入能夠安全吃食的“快樂(lè)狀態(tài)”）。
v0.2 學(xué)會(huì)了“追尾”的憨憨蛇
增加了上述兩個(gè)策略后，貪吃蛇進(jìn)入“生存狀態(tài)”和“迷茫狀態(tài)”后仍能繼續(xù)行進(jìn)并有效地生長(zhǎng)，壽命明顯提高，甚至在進(jìn)行了50余次實(shí)驗(yàn)后表演了一波“吃滿(mǎn)全圖”：
只簡(jiǎn)單增加了一次BFS尋找蛇頭到蛇尾的通路，就取得如此明顯的效果，簡(jiǎn)直是把我明天的歐氣都耗盡了。其實(shí)這時(shí)我才開(kāi)始遭遇貪吃蛇真正的難題。
學(xué)會(huì)追蛇尾的貪吃蛇，再也不會(huì)輕易地死掉，但它大部分時(shí)候會(huì)進(jìn)入某種死循環(huán)，像這樣：
還有特別氣人的這樣……
也就是當(dāng)食物出現(xiàn)在某個(gè)位置時(shí)，蛇再也找不到安全的路線去吃它，而自身形成了一個(gè)曲折的回路，無(wú)法破解。
冥思苦想+翻找博客之后，我稍稍改變了“生存狀態(tài)”或“迷茫狀態(tài)”下蛇的行進(jìn)策略……
v0.3 比較聰明的成年蛇
“你已經(jīng)是一只成年蛇了，要學(xué)會(huì)自己找出路。”
如果蛇總是以最短路徑向食物靠近，蛇身不可能全部貼合，勢(shì)必產(chǎn)生許多小洞，留下死循環(huán)的隱患。讓我們回到本文最開(kāi)頭的GIF，不難發(fā)現(xiàn)那條貪吃蛇似乎從一開(kāi)始就沒(méi)有走最短路徑，而是常常貼著自身走，并且繞各種S形彎，保證了行進(jìn)的可持續(xù)。
這啟發(fā)我改變“生存狀態(tài)”或“迷茫狀態(tài)”下蛇的行進(jìn)策略：蛇應(yīng)該遠(yuǎn)離食物，直至回到“快樂(lè)狀態(tài)”。進(jìn)入“生存狀態(tài)”或“迷茫狀態(tài)”后，需要先尋找蛇頭周邊的空位，并選擇一個(gè)走過(guò)去。其中有兩個(gè)要點(diǎn)：
????1. 蛇走進(jìn)這個(gè)位置后，蛇頭與蛇尾間仍要有通路；
????2. 在所有符合條件1的空位中，選擇離食物最遠(yuǎn)的一個(gè)。
利用這兩個(gè)條件，貪吃蛇就會(huì)自發(fā)地貼著自身走并繞一些S彎了。
以上圖為例，蛇處于“生存狀態(tài)”。蛇頭左邊是墻，不可走；走右邊和前方都可到達(dá)蛇尾，但前方離食物更遠(yuǎn)，故向前走。
現(xiàn)在，重新捋一下思路：
最終效果如下：
實(shí)驗(yàn)發(fā)現(xiàn)，吃滿(mǎn)全屏的概率似乎已經(jīng)從1/50上升到了60%以上，算是有一定的提高了。
而最后一個(gè)未解決的問(wèn)題如下：
仍然是死循環(huán)的問(wèn)題，常常在剩余1格未填滿(mǎn)時(shí)陷入死循環(huán)，極少數(shù)時(shí)候還出現(xiàn)過(guò)剩余3格未填滿(mǎn)的情況。
寫(xiě)在最后
對(duì)于最后的死循環(huán)，既有的改進(jìn)思路是：在蛇身達(dá)到一定長(zhǎng)度時(shí)，就開(kāi)始S形繞彎，預(yù)防“最后幾個(gè)洞”的出現(xiàn)。
但應(yīng)該在蛇身達(dá)到多少時(shí)改換策略呢？填滿(mǎn)70%的地圖時(shí)？50%？或是蛇達(dá)到能繞地圖一周的長(zhǎng)度時(shí)就要開(kāi)始繞S形，就像本文最開(kāi)頭的GIF那樣？我暫時(shí)沒(méi)有能力探索下去……
如果只是為了做到“吃滿(mǎn)全圖”，其實(shí)早已有完美的解決方案，即不停地S形繞彎（用不自交的封閉曲線填滿(mǎn)地圖），就像這樣：
難道應(yīng)該基于這種最“無(wú)腦”的S形吃法，去改進(jìn)它的效率？
我猜想這個(gè)視頻中的蛇正是如此，因此前期顯得“有點(diǎn)不太聰明的亞子”。簡(jiǎn)單粗暴，但保證有效：2分鐘看完貪吃蛇全集
S形吃法并非唯一保穩(wěn)的操作，參見(jiàn)這個(gè)視頻中貪吃蛇的華麗走位：人工智能AI挑戰(zhàn)貪吃蛇，這就是人工智能的藝術(shù)！
還有一種十分接近人類(lèi)的走法：貪吃蛇理論最高分
這是一個(gè)13*8的地圖，走法直接了當(dāng)，前期轉(zhuǎn)向很少，后期也是繞最小的S形彎。如果說(shuō)這是真人操作我也愿意相信。
最后的一點(diǎn)點(diǎn)想法都放在這里了。有朝一日做出能100%成功吃滿(mǎn)全圖的貪吃蛇，再來(lái)更新v1.0吧……
思路主要參考
https://blog.csdn.net/fox64194167/article/details/19965069
您竟然看到了這里……悄悄引個(gè)流吧? [doge]
