Author: Marco A. Villena
LABERINTO automatically solves any 2D labyrinth using a Genetic Algorith.
DISCLAIMER: This script is for training and testing purposes only, so some conceptual errors might be found and many improvements can be considered.
A Genetic Algorithm is an optimization technique inspired by natural selection. We'll use it to find a path through a labyrinth where the possible movements are up, down, left, and right. Below is a step-by-step explanation of how to implement it.
The labyrinth can be represented as a grid (matrix) where:
0= Open path1= Wall (not passable)2= Start position9= Exit position
Each individual (solution) in the population represents a sequence of movements (up, down, left, right) from the start position.
We encode movements as:
0(Right)1(Up)2(Left)3(Down)
A chromosome could be a string like "0011223300" (sequence of moves).
Generate N random individuals, where each chromosome is a sequence of random moves of length L.
Example for N=5:
"0011223300""2230013202""1201330012"
The fitness function evaluates how close an individual is to the exit. We define it as:
Where:
- d = Manhattan distance from the final position of the sequence to the exit.
- If the sequence reaches the exit exactly, give it a high fitness score (e.g., 1000).
Select parents using Tournament Selection or Roulette Wheel Selection:
- Tournament Selection: Pick k random individuals and select the one with the best fitness.
Combine two parent chromosomes to create offspring.
-
One-Point Crossover:
- Choose a random crossover point.
- Swap segments from parents.
Example:
- Parent 1:
"2230013202" - Parent 2:
"1201330012" - Crossover at position 4 → Child:
"2230330012"
With a small probability (e.g., 5%), randomly mutate a gene (change a move).
Example:
"2230330012"→ Mutation at position 3 →"2200330012"
- Replace the worst-performing individuals with the new offspring.
- Keep the best solution found so far (elitism).
Stop when:
- An individual reaches the exit.
- A maximum number of generations is reached.
To use the LABERINTO, you need to run the main.py file. However, you must initially configure a number of parameters included directly in the code. These parameters are included at the beginning of the script in the section called Initial Variables. These variables are:
map_path= Name of the map you want to use (e.g., 'map_01.map'). All maps are placed in the Maps folder.number_of_generations= Number of generations (e.g., 10000).live_per_generation= Number of people in each generation (e.g., 1000).team_size= Size of the team of the tournament selection method (e.g., 10). Note: See theoretical sectionmutation_prob= Mutation probability in the [0, 1] range (e.g., 0.05).ancestors_flag= Enable/disable load paths from file for the initial population.ancestors_path= Name of the file with additional paths. (Default: ancestral_paths.txt)
Once the calculations are finished, the map with the best path found and the evolution of the fitness score are shown. At the same time, this figure will be saved in the Output folder. The information related to the result will be saved in the file results_database.txt located in the same folder.
Maps are generated as plain text files with the extension .map. Each cell of the map matrix is defined in the file, separated by a blank space. Each cell can contain the following elements:
0= Open path1= Wall (not passable)2= Start position9= Exit position
All maps must meet the following conditions:
- The outer edge of each map must always be defined as walls.
- The Start position and the Exit position must be defined.
- A route that connect the Start position and the Exit position must exist.
Tip: To facilitate the generation of maps, an Excel file is included in the Maps folder.
LABERINTO was developed using Python v3.12. This is the list of non-standard libraries used by this code.