<h2>Snake</h2>    <p>This project focuses on the AI algorithm of the snake game. The AI's goal is to direct the snake to eat the food and fill the map with its body as quickly as possible, so it <strong>should not</strong> just follow a fixed pattern(e.g., zigzagging).</p>    <h2>Build Status</h2>    <table>     <thead>      <tr>       <th>Linux</th>       <th>Windows</th>      </tr>     </thead>     <tbody>      <tr>       <td> </td>       <td> </td>      </tr>     </tbody>    </table>    <h2>Demo</h2>    <ul>     <li> <p>AI based on the hamiltonian cycle, slower but easier to succeed.</p> <p><img src="https://simg.open-open.com/show/e96923827d0f89bfcd2ae70e4e64cae2.gif"></p> </li>     <li> <p>AI based on graph search, faster but harder to succeed.</p> <p><img src="https://simg.open-open.com/show/e74cd52f43001715948ae79d8c86e67a.gif"></p> </li>    </ul>    <h2>Installation</h2>    <ol>     <li> <p>Install <a href="/misc/goto?guid=4958978886605118454" rel="nofollow,noindex">CMake</a> .</p> </li>     <li> <p>Generate build files using the commands below:</p> <pre>  $ mkdir build  $ cd build  $ cmake ..</pre> </li>     <li> <p>Build files will be generated in the build directory based on your operating system. Use them to build this project:</p>      <table>       <thead>        <tr>         <th>Linux</th>         <th>OS X</th>         <th>Windows</th>        </tr>       </thead>       <tbody>        <tr>         <td>Makefile</td>         <td>Makefile</td>         <td>Visual Studio Project</td>        </tr>       </tbody>      </table> </li>    </ol>    <h2>Keyboard Controls</h2>    <table>     <thead>      <tr>       <th>Key</th>       <th>Feature</th>      </tr>     </thead>     <tbody>      <tr>       <td>W</td>       <td>move up</td>      </tr>      <tr>       <td>A</td>       <td>move left</td>      </tr>      <tr>       <td>S</td>       <td>move down</td>      </tr>      <tr>       <td>D</td>       <td>move right</td>      </tr>      <tr>       <td>Space</td>       <td>pause/resume the snake</td>      </tr>      <tr>       <td>Esc</td>       <td>exit game</td>      </tr>     </tbody>    </table>    <p>Tips:When the snake is running, you could press the Space key to pause the snake and then press the W/A/S/D key to move the snake step by step. Anytime if you want the snake to start running again, just press the Space key again.</p>    <h2>Algorithm</h2>    <ul>     <li>Shortest path</li>     <li>Longest path</li>     <li>AI Algorithm</li>    </ul>    <h3>Shortest path</h3>    <p>Source: <a href="/misc/goto?guid=4959735836765217280" rel="nofollow,noindex">Snake.findMinPath()</a></p>    <p>We use breadth-first search to find the shortest path. We additionally expect the path to be as straight as possible so there will be less scattered empty points on the map, which will improve the AI's success rate.</p>    <p>The image below illustrates how this algorithm works on a 18*18 map. The green area is scanned when searching and the red area is the shortest path. Each number on the point denotes its minimum distance to the starting point.</p>    <p><img src="https://simg.open-open.com/show/ea96fecfe972fd947c72962b07f9ed43.gif"></p>    <h3>Longest path</h3>    <p>Source: <a href="/misc/goto?guid=4959735836864465556" rel="nofollow,noindex">Snake.findMaxPath()</a></p>    <p>Suppose we want to find the longest path from point A to point B on a 4*4 map. The algorithm generates the shortest path between the two points first and then extends each pair of points on the path until no extensions can be found. Since the longest path problem is NP-hard, this algorithm is only an approximation.</p>    <p><img src="https://simg.open-open.com/show/2bbf48aca44a172dff949c04d6cc732f.png"></p>    <p>The image below shows the longest path generated in a 18*18 map, where point 0 and point 1 is the beginning and the ending point respectively.</p>    <p><img src="https://simg.open-open.com/show/0e6f9b19e74c9cda2e1bfff9f273aeaf.gif"></p>    <h3>AI Algorithm</h3>    <p>This is a widespread picture of a perfect snake:</p>    <p><img src="https://simg.open-open.com/show/3c74aa04500d8cd2ccbddfa623c64e7c.gif"></p>    <p>From the picture we can figure out that in order to fill the map with the snake's body, the whole body must form a hamiltonian cycle when the game ends. To ensure a hamiltonian cycle exists, the map must have <strong>even(not odd)</strong> amount of rows or columns.</p>    <p>There are two versions of AI algorithm to guide the snake, the first one isbased on graph searchand the other isbased on the hamiltonian cycle. Both of them are implemented in <a href="/misc/goto?guid=4959735836948469160" rel="nofollow,noindex">Snake.decideNext()</a> .</p>    <p>AI based on graph search</p>    <p>To find the snake( <strong>S1</strong> )'s next moving direction( <strong>D</strong> ), the AI follows the steps below:</p>    <ol>     <li>Compute the shortest path <strong>P1</strong> from snake <strong>S1</strong> 's head to the food. If <strong>P1</strong> exists, go to step 2. Otherwise go to step 4.</li>     <li>Direct a virtual snake, <strong>S2</strong> (the same as <strong>S1</strong> ), to eat the food along path <strong>P1</strong> .</li>     <li>Compute the longest path <strong>P2</strong> from snake <strong>S2</strong> 's head to its tail. If <strong>P2</strong> exists, let <strong>D</strong> be the first direction in path <strong>P1</strong> . Otherwise go to step 4.</li>     <li>Compute the longest path <strong>P3</strong> from snake <strong>S1</strong> 's head to its tail. If <strong>P3</strong> exists, let <strong>D</strong> be the first direction in path <strong>P3</strong> . Otherwise go to step 5.</li>     <li>Let <strong>D</strong> be the direction that makes the snake the farthest from the food.</li>    </ol>    <p>AI based on the hamiltonian cycle</p>    <p>The algorithmgenerates a hamiltonian cycleon the map first and then moves the snake along the cycle. To avoid following this fixed cycle incessantly, the snake must have the ability totake shortcutsto eat the food whenever possible.</p>    <p>Generate a hamiltonian cycle</p>    <p>Source: <a href="/misc/goto?guid=4959735837036278272" rel="nofollow,noindex">Snake.buildHamilton()</a></p>    <p>Suppose we want to build a hamiltonian cycle on a 4*4 map. Then our goal is to assign the path index to each point on the map. The image below shows a possible hamiltonian cycle.</p>    <p><img src="https://simg.open-open.com/show/7fd49cb941deef2ab7459d27e3925065.png"></p>    <p>To construct the cycle above, we fix the point 0, 1 and 2 first since they are the initial positions of the snake. Then we make point 1 unreachable and generate the longest path from point 2 to point 0. Finally we join the starting and the ending point, which forms a hamiltonian cycle:</p>    <p><img src="https://simg.open-open.com/show/cc1858be5a2167fd11b094bb51f0fa3f.png"></p>    <p>Take shortcuts</p>    <p>Sometimes the snake can eat the food directly(take shortcuts) instead of following the hamiltonian cycle. The image below explains this idea briefly. For more details, please refer to <a href="/misc/goto?guid=4959735837115904138" rel="nofollow,noindex">this article</a> .</p>    <p><img src="https://simg.open-open.com/show/d6cb8ab790d27024d5341e9b34fd60e7.png"></p>    <h2>License</h2>    <p>See the <a href="/misc/goto?guid=4959735837202456010" rel="nofollow,noindex">LICENSE</a> file for license rights and limitations.</p>    <p> </p>