How to Build an AI‑Powered Snake Game in C++ Using Hamiltonian Cycles

Repository

https://github.com/stevennl/Snake – C++ implementation of an AI‑enhanced Snake game where the snake attempts to fill the entire board.

Setup

Install CMake (download from https://cmake.org/download/).

Generate build files, e.g.: cmake -S . -B build.

Build the project: cmake --build build.

Run the executable. Space pauses/resumes; W/A/S/D moves the snake manually.

AI Algorithms

Two strategies are provided.

Hamiltonian‑cycle AI – constructs a Hamiltonian cycle that visits every cell and moves the snake along it, pausing to eat food when reachable. Reliable but slower.

Graph‑search (image‑search) AI – uses breadth‑first search (BFS) to find the shortest path to food, then attempts to extend to the tail via a five‑step decision process.

Hamiltonian Cycle Details

The function Snake.findMinPath() runs BFS to obtain the shortest path, preferring straight‑line segments to improve success. The following GIF illustrates BFS on an 18×18 grid (green = explored, red = shortest path).

The heuristic longest‑path approximation is performed by Snake.findMaxPath(). It starts from the shortest path between two points and iteratively expands each segment until no further extension is possible. The GIF below shows a generated longest path on an 18×18 grid.

Graph‑Search AI Decision Process

The AI decides the next move (direction D) using the following steps:

Compute the shortest path P1 from the snake’s head to the food. If none, go to step 4.

Simulate a virtual snake S2 that follows P1 and consumes the food.

Compute the longest path P2 from S2 ’s head to its tail. If it exists, set D to the first direction of P1; otherwise, go to step 4.

Compute the longest path P3 from the original snake’s head to its tail. If it exists, set D to the first direction of P3; otherwise, go to step 5.

Choose the direction that moves the snake farthest from the food.

Key Observations

To fill the entire map, the final board configuration must form a Hamiltonian cycle; therefore the grid must have an even number of rows or columns.

The AI functions are accessible via Snake.findMinPath(), Snake.findMaxPath(), and the main decision routine Snake.decideNext(). Full source code and README are available in the GitHub repository.