开源：Snake - 贪吃蛇游戏的人工智能算法实现
LindseyStin
7年前
<p>贪吃蛇游戏的人工智能算法实现。</p> <p>我们希望这条蛇<strong>尽快的</strong>吃掉食物从而使它的身子铺满整个地图，因此它不应该总是按照一个特定的路径行走。</p> <h2>效果展示</h2> <p style="text-align: center;"><a href="/misc/goto?guid=4959733348428600780"><img alt="开源：Snake - 贪吃蛇游戏的人工智能算法实现" src="https://simg.open-open.com/show/49b8d0c395521a61d46c3ac6199b94b0.gif" width="133" height="149"></a></p> <h2>安装</h2> <ol> <li> <p>安装 <a href="/misc/goto?guid=4959718249612783599">CMake</a>。</p> </li> <li> <p>输入以下命令build这个项目:</p> <pre> $ mkdir build $ cd build $ cmake ..</pre> </li> <li> <p>在build目录中，你可以找到：</p> <ul> <li>运行于Linux平台的Makefile</li> <li>运行于Windows平台的Visual Studio项目</li> <li>运行于OS X平台的Xcode项目</li> </ul> </li> </ol> <h2>键盘控制</h2> <table> <thead> <tr> <th>Key</th> <th>Feature</th> </tr> </thead> <tbody> <tr> <td>W</td> <td>上移</td> </tr> <tr> <td>A</td> <td>左移</td> </tr> <tr> <td>S</td> <td>下移</td> </tr> <tr> <td>D</td> <td>右移</td> </tr> <tr> <td>Space</td> <td>（暂停/恢复）蛇的移动</td> </tr> <tr> <td>Esc</td> <td>退出游戏</td> </tr> </tbody> </table> <h2>AI策略</h2> <ul> <li> <p>函数<a href="/misc/goto?guid=4959733348557085801">Snake.decideNext()</a>: 计算蛇<strong><em>S1</em></strong>的下一个移动方向<strong><em>D</em></strong></p> <ol> <li> <p>计算从蛇<strong><em>S1</em></strong>的头部到达食物的最短路径<strong><em>P1</em></strong>。</p> </li> <li> <p>派一条与蛇<strong><em>S1</em></strong>完全一样的虚拟蛇<strong><em>S2</em></strong>沿路径<strong><em>P1</em></strong>吃掉食物。</p> </li> <li> <p>计算从蛇<strong><em>S2</em></strong>的头部到其尾部的最长路径<strong><em>P2</em></strong>。如果路径<strong><em>P2</em></strong>存在，将移动方向<strong><em>D</em></strong>设置为路径<strong><em>P1</em></strong>的第一个方向，否则进行步骤4。</p> </li> <li> <p>计算从蛇<strong><em>S1</em></strong>的头部到达其尾部的最长路径<strong><em>P3</em></strong>。如果<strong><em>P3</em></strong>存在，将移动方向<strong><em>D</em></strong>设置为路径<strong><em>P3</em></strong>的第一个方向，否则进行步骤5。</p> </li> <li> <p>将移动方向<strong><em>D</em></strong>设置为离食物最远的方向。</p> </li> </ol> </li> <li> <p>函数<a href="/misc/goto?guid=4959733348648421040">Map.findMinPath()</a>: 计算两个位置间的最短路径</p> <p>算法建立在BFS的基础上。为了使路径尽可能直，每次遍历邻接点时，在当前搜索方向上的位置会被优先遍历。</p> <p>效果展示:</p> <p style="text-align: center;"><a href="/misc/goto?guid=4959733348725895365"><img alt="开源：Snake - 贪吃蛇游戏的人工智能算法实现" src="https://simg.open-open.com/show/cf2b6d046ad1cf838efbaa16ebf5c1e5.gif" width="292" height="329"></a></p> <p>（绿色区域为搜索算法扫描到的区域，红色区域为最后计算出的最短路径，每个位置上的数字表示了从起始位置开始到该位置的最短距离）</p> </li> <li> <p>函数Map.findMaxPath(): 计算两个位置间的最长路径</p> <p>算法建立在DFS与贪心算法的基础上。每次遍历邻接点时，离目标位置最远（使用曼哈顿距离估计）的位置将会被优先遍历到。另外，为了使路径尽可能直，如果两个位置到目标位置的距离相等，在当前搜索方向上的位置将被优先遍历到。这个问题是一个NP完全问题，此算法得出的结果路径只是一个近似最长路径。</p> <p>效果展示:</p> <p style="text-align: center;"><a href="/misc/goto?guid=4959733348815593259"><img alt="开源：Snake - 贪吃蛇游戏的人工智能算法实现" src="https://simg.open-open.com/show/bf12b5a20104a59161cefd2044ee2403.gif" width="292" height="329"></a></p> <p>（绿色区域为搜索算法扫描到的区域，红色区域为最后计算出的最长路径，每个位置上的数字表示了从该位置开始到目标位置的估计距离）</p> </li> </ul> <p> </p>