A snake game, with multiple ai algorithms.
Currently, this project is used to test the neuralnetwork library.
- About the game
- Implemented AI
2.1 Hamiltonian cycle
2.2 A* algorithm - Purpose of this project
- Project structure
- How to get it
The game offers a manual mode, which is controlled by the keyboard.
- arrow left, arrow right, arrow up, arrow down: will switch to this direction for the next snake move(s).
Alternatively, a bot can overtake the moves. Currently, the gui does not allow choosing between different modes.
One of the most known algorithms to solve snake with an ai is to implement a hamiltonian cycle as base path. A hamiltonian
cycle is basically a circular path, with runs through every node (here 'cell') of a graph (here 'game panel').
This algorithm only works though, if the game panel has an even number of cells (e.g. a 25x25 panel will fail as one cell will
never be included in the path).
The snake can strictly follow this path. As a result, it will never run into its own body or a wall.
If the snake is small, this may result in unreasonable long paths, thus an inefficient timing. To solve this, path sections can
be skipped in earlier stages. The snake will remain basically on the base path, which will avoid that a whole new path
has to be calculated after a goodie is reached.
But - how to find the best shortcut efficiently?
A good option to find the best shortcut fast is offered by the A*-algorithm (which is used also in map software to calculate the shortest routes).
This algorithm will first build up a graph, then - based on weight and distance - calculate the shortest possible shortcut.
In the current implementation, the graph is build for the current hamilton path section to the next goodie. Meaning: the snake will
still stay on the hamiltonian cycle.
This project ist mainly for playing around with Java.
ai
here, all ai related code is inapplication
this package contains the main method (inDriver.java
), and gui related codegame
here most part of the game logic is inutil
helper classes
Clone the repository with:
git clone https://github.com/lpapailiou/snake your-target-path
For further help, click here.