<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>