Snake-AI貪吃蛇游戲的人工智能

Snake-AI，這是一個用 C/C++ 語言編寫的貪吃蛇游戲的人工智能。

AI 的目的是讓蛇盡可能的吃更多的食物，直到吃滿整個地圖。想?yún)⑴c這個項目，請查看todos。

Demo

使用方法

編譯與運行：

$ make
$ make run

為了解詳細使用方法, 請查看主函數(shù)main()

算法介紹

• 函數(shù)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設置為離食物最遠的方向。

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

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

  效果展示:

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

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

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

  效果展示:

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