開源：Snake - 貪吃蛇游戲的人工智能算法實現

貪吃蛇游戲的人工智能算法實現。

我們希望這條蛇盡快的吃掉食物從而使它的身子鋪滿整個地圖，因此它不應該總是按照一個特定的路徑行走。

效果展示

安裝

1. 安裝 CMake。

2. 輸入以下命令build這個項目:

   $ mkdir build
   $ cd build
   $ cmake ..

3. 在build目錄中，你可以找到：

   • 運行于Linux平臺的Makefile
   • 運行于Windows平臺的Visual Studio項目
   • 運行于OS X平臺的Xcode項目

鍵盤控制

AI策略

• 函數Snake.decideNext(): 計算蛇S1的下一個移動方向D

  1. 計算從蛇S1的頭部到達食物的最短路徑P1。

  2. 派一條與蛇S1完全一樣的虛擬蛇S2沿路徑P1吃掉食物。

  3. 計算從蛇S2的頭部到其尾部的最長路徑P2。如果路徑P2存在，將移動方向D設置為路徑P1的第一個方向，否則進行步驟4。

  4. 計算從蛇S1的頭部到達其尾部的最長路徑P3。如果P3存在，將移動方向D設置為路徑P3的第一個方向，否則進行步驟5。

  5. 將移動方向D設置為離食物最遠的方向。

• 函數Map.findMinPath(): 計算兩個位置間的最短路徑

  算法建立在BFS的基礎上。為了使路徑盡可能直，每次遍歷鄰接點時，在當前搜索方向上的位置會被優先遍歷。

  效果展示:

  

  （綠色區域為搜索算法掃描到的區域，紅色區域為最后計算出的最短路徑，每個位置上的數字表示了從起始位置開始到該位置的最短距離）

• 函數Map.findMaxPath(): 計算兩個位置間的最長路徑

  算法建立在DFS與貪心算法的基礎上。每次遍歷鄰接點時，離目標位置最遠（使用曼哈頓距離估計）的位置將會被優先遍歷到。另外，為了使路徑盡可能直，如果兩個位置到目標位置的距離相等，在當前搜索方向上的位置將被優先遍歷到。這個問題是一個NP完全問題，此算法得出的結果路徑只是一個近似最長路徑。

  效果展示:

  

  （綠色區域為搜索算法掃描到的區域，紅色區域為最后計算出的最長路徑，每個位置上的數字表示了從該位置開始到目標位置的估計距離）