點(diǎn)我看最終效果

與其一步步增加策略，不如一開始就直奔其本質(zhì)。

——沃?茲基碩德

在幾天前發(fā)布的《實(shí)現(xiàn)全自動(dòng)貪吃蛇的一種可能》一文末尾，我提及最簡單的自動(dòng)貪吃蛇實(shí)現(xiàn)方法——

而本文思路的起源，正是這個(gè)看似最智障、低效率的走法。

原理解釋

一般的貪吃蛇玩法，無非是前期以較短路程奔向食物，后期蛇身太長時(shí)多繞路以騰出活動(dòng)空間。我們的目標(biāo)是“吃滿全圖”，似乎要在后期“如何繞路”上下功夫。

但其實(shí)，貪吃蛇“吃滿全圖”一個(gè)非常重要的充分條件是，蛇身形成“封閉且不自交的曲線”。這才是我們目標(biāo)的本質(zhì)?！袄@路”只是一種方法，一個(gè)表象。

且讓我們回到上面的GIF，以它為例。為什么走S形路徑的蛇能形成封閉不自交曲線，正是因?yàn)椤坝腥ケ赜谢亍?。蛇在奇?shù)行向右走，偶數(shù)行向左走，再利用左邊空出的一列即可回到起點(diǎn)。

這只是一種可能。貪吃蛇并非只能左右往返，也可上下往返，只要“有來有回”，不把自己繞進(jìn)死路，就能形成安全的回路。

例如（這里是人工操作，所以比較慢……）：

若想將10*10的地圖全部填滿封閉的曲線，就要放眼全局。我們不妨讓蛇大致做逆時(shí)針旋轉(zhuǎn)，于是需要限制每一行/列上蛇頭的運(yùn)動(dòng)方向：

????奇數(shù)行只能向右走，偶數(shù)行只能向左走

????奇數(shù)列只能向下走，偶數(shù)列只能向上走

就像這樣：

只須遵照箭頭的方向規(guī)定，就能保證回路形成，蛇最終一定能吃滿全圖！

尋路算法

在BFS的基礎(chǔ)上，限制了不同節(jié)點(diǎn)上搜索的方向（圖片正中“0”為開始點(diǎn)，數(shù)字代表步數(shù)）。視頻版(1:48)

我知道我的字很丑，但如果做動(dòng)畫一定會(huì)很無(ma)聊(fan)????[doge]

理論存在，實(shí)踐開始——

無bug一遍過，實(shí)踐成功。

以上內(nèi)容為UP獨(dú)立思考結(jié)果，后來發(fā)現(xiàn)上述現(xiàn)象與“哈密頓回路”有關(guān)，想必早已有相近思路。

看來年輕人還是要多學(xué)習(xí)? ? [手動(dòng)滑稽]

美化界面

（以下內(nèi)容與貪吃蛇無關(guān)）

當(dāng)前視覺效果不太美觀，蛇身全都擠在一起，看不清路徑。

解決方法來自生活區(qū)視頻《C++寫貪吃蛇AI 附源碼》的評(píng)論區(qū)。非常感謝大佬@柯西丶不是你

學(xué)著畫了個(gè)——

每一個(gè)小小的方格，都是一只生猛的海龜。