Genetic Algorithm for Maze Solving

Introduction

Genetic algorithms are a fascinating class of optimization methods inspired by the process of natural selection. In this project, I applied a genetic algorithm to solve a maze with a fun twist: the algorithm never sees the maze layout. Instead, it provides a list of moves of a fixed length and only receives feedback in the form of the distance to the exit and how many times it has bumped into a wall.

This project was a playground for experimenting with genetic algorithms and object-oriented programming in Python, and also a great opportunity to build a simple game interface with Pygame.

The repository is available here.

Game Visualization

Image of the game

Problem Formulation

Input: A list of moves (right, left, up, down) of fixed length
Output: Distance to exit and number of collisions with walls after following the moves
Goal: Find a sequence of moves that minimizes the distance to the exit (and ideally, reaches it)
Constraint: No direct information about the maze layout or the current position

What is a Genetic Algorithm?

A genetic algorithm (GA) is an evolutionary method inspired by the concept of natural selection. I has the following components:

Population: Start with a random population of individuals (here, each individual is a list of moves of fixed length).
Selection: Evaluate the “fitness” (score) of each individual using a scoring function (distance to exit, number of collisions). At each generation, the best individuals are selected to produce the next generation while worst individuals are replaced by the new offspring.
Crossover and Mutation: Select the best individuals to produce the next generation via crossover (mixing moves from two parents) and mutation (randomly altering some moves).
Repeat: Iterate this process until a satisfactory solution is found (i.e., the exit is reached or the distance is minimized).

The beauty of GAs is their flexibility: crossover, mutation, and scoring functions can all be tailored to the problem at hand. Moreover, GAs do not require any property on the scoring function like differentiability or even continuity.

Technical Implementation

Maze Generation

To make things interesting, I used a random maze generator based on a recursive division algorithm. The maze can be resized easily, and the generator ensures a fair and challenging puzzle each time. The algorithm works by:

Recursively dividing the maze area with random horizontal or vertical walls,
Creating openings between divided sections,
Continuing this process until the entire maze is partitioned.

For large mazes, I used a queue-based approach to avoid recursion depth issues.

See Maze Generation Algorithm (Recursive Implementation) for more details.

Genetic Algorithm Design

Genome Representation: Each individual’s genome is a fixed-length sequence of moves (up, down, left, right, or “do nothing” to regulate length).
Population: The algorithm maintains a population of these move sequences.
Crossover: For breeding, a child is generated by taking a random prefix from one parent and the suffix from another, favoring the better parent’s start.
Mutation: Randomly change a few moves in a child’s genome to introduce variation. The mutation can replace moves randomly or repeat previous actions to encourage longer runs in one direction.
Fitness Function: The score penalizes distance to the exit and the number of wall collisions.
Elitism: The fraction of the best individuals are kept in the population to ensure that the best solutions are not lost.

I experimented with several crossover and mutation strategies to improve performance on larger mazes.

Game Loop and Visualization

I built the game interface using Pygame. One challenge was updating the visualization in sync with the algorithm’s progress. Rather than running all generations and then displaying the result, I refactored the loop to update the display and handle user interactions in real-time, with each generation’s progress visible as it happened.

Thoughts

This project was a fun side project that I did between two exams because I did not want to study. It gave me a chance to revisit object-oriented programming and experiment with genetic algorithms. It was satisfying to see the algorithm gradually “learn” to solve mazes, and to debug and improve both the code and the approach along the way.

Some potential extensions include:

Comparing the genetic algorithm’s performance with reinforcement learning agents
Experimenting with different scoring, crossover, or mutation strategies
Scaling up to larger or more complex mazes

Solving Maze Game with Genetic Algorithm - Just for Fun!