🇬🇧 English / 🇨🇳 中文
AI version 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 should not just follow a fixed zigzag pattern.
Linux | Windows |
---|---|
-
Install CMake.
-
Build this project using the commands below:
$ mkdir build $ cd build $ cmake ..
-
Contents below will be generated in the
build
directory based on your operating system:Linux OS X Windows Makefile Makefile Visual Studio Project
(Note that you could use command cmake -G "a generator" ..
in step 2 to specify a generator.)
Key | Feature |
---|---|
W | move up |
A | move left |
S | move down |
D | move right |
Space | pause/resume the snake |
Esc | exit game |
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 Space
key again.
-
Snake.decideNext(): compute the next move direction D of the snake S1
-
Compute the shortest path P1 from snake S1's head to the food.
-
Direct a virtual snake, S2 (the same as S1), to eat the food along path P1.
-
Compute the longest path P2 from snake S2's head to its tail. If P2 exists, let D be the first direction in path P1. Otherwise go to step 4.
-
Compute the longest path P3 from snake S1's head to its tail. If P3 exists, let D be the first direction in path P3. Otherwise go to step 5.
-
Let D be the direction that moves the snake along the longest path to the food.
-
-
Map.findMinPath(): compute the shortest path between two positions
The algorithm is based on BFS. In order to make the result path as straight as possible, each time the adjacent positions are traversed, the position at the current searching direction will be traversed first.
Here is a vivid description of how it works:
(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.)
-
Map.findMaxPath(): compute the longest path between two positions
The algorithm is based on DFS and the greedy algorithm. Each time the adjacent positions are traversed, the position that is the farthest from the destination (estimated by the Manhatten distance) will be traversed first. In addition, in order to make the result path as straight as possible, if two positions have the same distance to the destination, the position at the current searching direction will be traversed first. Since this is an NP-hard problem, this method is only approximate.
Here is a vivid description of how it works:
(The green area is scanned when searching and the red area is the longest path. Each number on the point denotes its estimated distance to the destination.)
There are some discussions at reddit.
See the LICENSE file for license rights and limitations.