標題借鑒了一下老羅的風格，哈哈(*^__^*)?

原來圍住神經貓游戲剛火的時候，恰巧當時正在學QML，順手就給弄了一個，不知道大家還記不記得這個游戲，簡單說就是設置障礙把中間的貓圍住就獲勝了（橙色圓即為障礙），而貓可以向周圍六個方向中的非障礙區域逃跑，如果貓逃跑到四周邊界的圓上則玩家失敗，界面是醬紫的：

然后在 Qt 貼吧里面也共享了一下：http://tieba.baidu.com/p/3241650033

因為當時做這個的時候主要是想練下 QML，所以草草弄了個隨機方向選擇算法（應該沒資格叫算法吧...），然后這只小貓就蠢得不要不要的，到了邊界都往回跑。。。

最近突然又翻到這個東西，就還是想把這個草率的東西弄得完整一點，于是又花了幾天時間，先是增加了兩個游戲難度，一個就是原版以及網絡上大部分版本所使用的基于貪心法的實現，說直白點就是打表了，找到最短通路，然后朝那個方向跑。但是這個方式很容易被玩家使用“挖陷阱”的方式破掉，大部分“攻略”也是基于此的。第二個就是這篇博文的主題了——這個游戲人類幾乎無法取勝。不過我們后頭來談，這里先把嗑嘮完O(∩_∩)O~

之后呢，為了在手機也可以玩這個游戲，調整了界面布局以適應不同屏幕尺寸，然后就有了下面這個apk：

http://pan.baidu.com/s/1eQ0ePhg，下面上個圖，上排多了難度選擇的內容。

為毛apk要放百度網盤呢，原本也是想試試這個小游戲能不能在百度91助手和豌豆莢上線，畢竟良心應用，無須任何權限且免費無廣告。不過最后還是因為copyright的問題沒能成功，想想也是，畢竟除了代碼是自己寫的，其它的都是用的人家的東西-.-

然后這個小游戲也托管在Github上，如果大家有興趣也可以共同維護一下：

https://github.com/uCloudCastle/ShenJingMao

好，再嘮下去就成單口相聲了，趕快開始我們的正片部分：

我們可以再看一眼上面的三個難度選擇，“歡樂模式”就是隨機方向了，“普通模式”就是貪心法+最大通路算法，這個算法在大多數情況下都比較好用，但如果是下面這樣：

每一個邊界上的數字表示從該點到邊界需要的步數，障礙值我們直接設100了，因為總共也就81個點；邊界上的點不用說，當然除了邊界障礙，其他的都是0了。

除了邊界值和障礙值，其他點上的數字則是周圍6個點數值中的最小值+1，有了這樣一個矩陣，神經貓在移動時只需要往身邊值最小的格子上移動就可以了。

如上圖所示，"0"號格子表示的就是地圖的邊界，基于"普通模式"的算法，神經貓會判斷現在走"1"號格子再到"0"號格子就能以最快的速度逃出去。所以，“挖陷阱”捉神經貓的方法就是：現在玩家封上“1”為綠色的那個格子，神經貓只會向左側的“1”移動，然后玩家封上“0”，神經貓后退到“2”，玩家再封“3”，就 GameOver 了。

現在的問題就是，如何讓神經貓能夠知道玩家在封綠色“1”那個格子的時候是在“make trap”，而直接調頭回"3"號格子呢？或者說，看起來充滿誘惑的路到底該不該走？

如上圖，如果當前輪到神經貓移動，而貓在“2”的位置，“1”的周邊僅有那一個值為“0”的邊界點，神經貓能移動到“1”處嗎？答案是取決于“1”周邊其他格子的數值，但稍微理智點的玩家應該都不會讓貓從這個“0”出去，所以，神經貓最終要取勝，一定是踏上了某個擁有兩個“0”值邊界的節點：

此時，神經貓在“E1”處，玩家無論封住哪個“0”都無法阻止神經貓逃出，我們把這樣的“1”節點命名為“E1”。也就說，如果神經貓到達“E1”，它就已經贏了。那么同樣的，如果神經貓到達“E2”，結局也就寫好了（當然也包含超過兩個“E1”的情況）：

注意這里我們再把開始那個“周圍只有一個邊界的格子”的問題再處理一下：

這個“1”周圍只有一個出口，但當神經貓到達該點時，玩家勢必要將它身邊這個“0”封住，然后神經貓也就能夠順利到達“E1”了，也就是說，這個“1”等同于身邊最小的“Ex”，所以在其之上的“E2”也就成立了。

對于這個情況有一個更一般的推論：如果把邊界“0”看做“E0”，那么兩個“Ex”(x代表任一數字)的父節點為兩者中的較大值，也就是說，下面這個圖是成立的：

到了這里問題似乎變得很明了，我們繼續向上推到“E3”、“E4”。。只要神經貓踏上其中的任何一個點，游戲其實就已經結束了，但是，在這個map中，大多數結構是下面這樣的：

有一個邊界被兩個“E1”共享，如果 cat 目前位于“E2”，玩家稍微聰明點不去封其中一個“E1”，而是封住了紅色箭頭所指向的關鍵邊界點Key，那么無論神經貓到達哪個“E1”，玩家都可以將其截住。（比如神經貓走到藍色箭頭處，而玩家再封住綠色箭頭所指節點。）

因此，我們需要保證該拓撲是一個真正的樹形結構，每個節點的子節點不能被其他成員共享。在9*9并且包含障礙節點的map中，如果我們想從邊界點開始建立完全由獨立互不影響的“E1”、 “E2”、 “E3”。。構成的樹形網絡，一方面是計算量特別大，因為每個邊界“0”點換到一個新的“E1”名下都會從下至上影響每一層的計算，另一方面是，該map的結構決定了能夠作為“E3”的點也就那么幾個，“E4”就不用想了，下圖顯示了需要多少個非障礙節點才能構成一個“E3”節點。

因此，從神經貓所在的節點向外擴張反而是更好的選擇，即便神經貓當前不在“必勝路徑上”，玩家要想識別出每條通往“E3”、“E2”和“E1”的路徑并破壞它卻并不容易，我們使用一個多叉樹的結構來存儲神經貓的路徑，為了保證節點不會反向跳到自己的祖輩造成無限循環，這里按層次遍歷方式建樹，并用 QHash 存儲祖輩及其所在層數。各節點的子節點與其兄弟節點的子節點可能相同，這樣保證了神經貓在比較靠近中心或者障礙較多的位置仍然能夠找到一條非“必勝”但仍較優的路徑，玩家稍微下錯一步，該路徑可能就成為“必勝”路徑了。

所用到的數據結構是下面這個樣子的：

struct TreeNode {int val;int depth;QVector<TreeNode*> childList;TreeNode(int v = nullInit, int d = nullInit) :val(v), depth(d){}~TreeNode(){TreeNode* n;foreach(n, childList)delete n;} };struct PathStruct {QHash<int, int> m_Hash;TreeNode *m_Node;PathStruct() { m_Node = NULL; }~PathStruct() { delete m_Node; } };

呼，更多的細節大家可以到上面貼的 Github 上看看，只要想法到了代碼反而是其次了，最后給大家留個圖吧，猜猜"燒腦模式"下的神經貓應該會往哪兒跑呢？~

總結

以上是生活随笔為你收集整理的可能是最难围住的神经猫——寻找必胜路径的算法实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。