Technical Report
BFS(Breadth First Search) is shortest path search algorithm.
It is a width-first search algorithm using a queue.
This algorithm returns the shortest path through which Snake moves from the start point to the end point.
The shortest path is found by visiting the start node first and then searching all the nodes adjacent to the start node.(In other words, search nodes first in the same level in the tree or graph)
Step 1 : Visit start node and insert into queue
Step 2 : Delete the node at the front of the queue until the queue is empty or visits the end point (The node removed from the queue is the parent node of the nodes to be inserted into the queue)
Step 3 : Insert all nodes into a node queue adjacent
Step 4 : Determine the parent node of each node
Step 5 : From the destination node to the start node, parent nodes are looked upside down and the shortest path is found
The longest path finding algorithm is NP-hard.
NP-Hard is a problem that does not have a way to get an accurate answer other than to check the number of all cases like the TSP problem.
However, this algorithm is only approximate.
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.
STEP 1 : Initialize current location as starting point
STEP 2 : Informs the position of the current position in the specified direction and confirms the specified direction.
If the specified direction is left or right
STEP 3 : After confirming whether two points in the upward direction are visited, if both points have not visited, delete the existing path and move downward. Confirm current direction and move up. The location of the path is specified first.
STEP 4 : After confirming whether two points in the downward direction are visited, if both points have not visited, delete the existing path and move upward. Confirm current direction and move down. The location of the path is specified first.
If the specified direction is up or down
STEP 5 : After confirming whether two points in the left direction are visited, if both points have not visited, delete the existing path and move to the right. Confirm current direction and move to the left. The location of the path is specified first.
STEP 6 : After confirming whether two points in the right direction are visited, if both points have not visited, delete the existing path and move to the left. Confirm current direction and move to the right. The location of the path is specified first.
STEP 7 : If the path can not be extended, the path is incremented and moved to the next position.
This algorithm of main goal is add next direction to snake instance.
Step 1 : Search min path from current virtual snake position to Food
Step 2 : Move virtual snake to searched path and when the virtual snake' body is full in the map, set the first searched direction to real snake
Step 3 : not step2(when the virtual snake' body is full in the map), search max path from virtual snake's head to virtual snake's Tail.
If path is exist, return the first direction to real snake
Step 4 : not step 3(path is exist), search max path from real snake's head to real snake's tail
Step 5 : not step 4(path is exist), search the max path from current to Food position and set direction the first path
- Caution!! step 3's virtual snake and step 4's real snake's position is different, because when step 2, virtual snake is moved.
Hamilton Cycle is a route starting from one vertex and visiting to each vertex exactly once, and then returning to the vertex that started again.
To find the Hamilton Cycle, use the state space tree and place a starting point at level 0.
It is a method to set a route so as to move to a vertex not visited after confirming whether or not the vertices adjacent to one point are visited.
The Hamilton Cycle is a method to find all possible paths to find the optimal path and to compare the paths with each other.
Step 1 : Set the number of rows and columns as an even number
(Hamilton Cycle is only available when the number of rows and columns is even.)
Step 2 : If the size of the initial snake body is 3 spaces, the 3 spaces can not be passed. Change this space temporarily into a wall.
Step 3 : Find the longest path through all the spaces in the map and change it to SNAKE BODY
Step 4 : The first SNAKE BODY part is initialized from the wall to the SNAKE body part, and the rest part is made into the path.
- Downloed CMake
CMake is a build support system for multi-platform, easy to use and easy to manage.
Download the appropriate file according to your platform type(Unix/Linux/Windows).
- Generate build files using the commands below
$ mkdir build
$ cd build
$ cmake ..
- Build files will be generated in the build directory based on your operating system.
Use them to build this project.
Linux : Makefile
OS X : Makefile
Windows : Visual Studio Projext (Only executable after 2011 version)
- Run clone or download the code from github.
Run clone or download from github.
When you execute it, the menu screen is displayed.
If you enter 1, the Snake Game is executed.
If you enter 2, show the Shortest Path algorithm.
If you enter 3, show the Longest Path algorithm.
If you enter 4, show the Hamiltonian Cycle algorithm.
If you enter 5, AI mode Snake Game is executed.
If you enter another number, the game ends.
When Snake game is executed (when you enter 1)
'A' or 'a' => Snake moves to the left.
'D' or 'd' => Snake moves to the right.
'S' or 's' => Snake moves downwards.
'W' or 'w' => Snake moves upwards.
Space => Snake can pause / resume.
Esc => The game ends.
If the snake's head touches the yellow prey, the snake will eat food and the body of the snake increases. When the snake crashes into the wall, the game ends.
- Remove duplicate code
- Create menu GUI
- Modify direction key
- Add Annotation(comments) to code
- Make clear statement in code
Copyright (c) 2016 Steven Liu
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.