maze-ga.py

import enum
import math
import random as r

# Maze props
HEIGHT = 20
WIDTH = 33

OBSTACLE = 1000
FLOOR = 1
MOUSE = 0
ILLEGAL_MOUSE = -1

MUTATION_RATE = 0.5
CHROMOSOME_SIZE = 100
POPULATION_SIZE = 100
MAX_GENERATIONS = 1000

MOVES_MAP = {
    0: (0, 0),   # NO-OP (when reached target)
    1: (-1, 0),   # UP, subtract 1 from row
    2: (1, 0),  # DOWN, add 1 to row
    3: (0, 1),   # RIGHT, add 1 to col
    4: (0, -1)   # LEFT, subtract 1 from col
}


# MAZE is a 2D array of characters, where '#' represents an obstacle and ' ' represents an empty space
# For the GA, we'll use 1000 for obstacles and 0 for empty spaces.
# The maze is 20x33 and has a single path from start to finish
MAZE = [
    '### #############################',
    '### ###      ####      ##### ####',
    '##  ########      #### #####   ##',
    '## ###     # ############### ####',
    '## ### ### # ######          ####',
    '##     ### #    ### ### #### ####',
    '########## #### ### ### #### ####',
    '#####  ### #### ### ### ####    #',
    '#####      #### ### ### ##   # ##',
    '##### ########        # ###### ##',
    '##    ######## ######## ###### ##',
    '##### ###      ### ####    ### ##',
    '## ## ### ######   ####### #   ##',
    '## ## ### #### ###    #### # ####',
    '## ## ### #### ### ### ### # ####',
    '##                  ## ### #    #',
    '###   #### ########### ### ## ###',
    '### ############           ## ###',
    '### ##           ###### ###     #',
    '###### ##########################',
]

# Assert Maze is valid
assert (len(MAZE) == HEIGHT), 'Maze height does not match HEIGHT'
for i in range(len(MAZE)):
    assert (len(MAZE[i]) == WIDTH), 'Maze width does not match WIDTH'

# Find start and finish positions
START = (0, MAZE[0].find(' '))
FINISH = (len(MAZE) - 1, MAZE[-1].find(' '))
assert (START[1] != -1 and FINISH[1] != -1), 'Start or Finish not found'


def load_maze(string_maze: list[str]):
    """
    Read MAZE and assign values for obstacles and empty spaces
    """
    parsed_maze: list[list[int]] = []
    for row in MAZE:
        newRow = []
        for cell in row:
            newRow.append(OBSTACLE if cell == '#' else FLOOR)
        parsed_maze.append(newRow)
    return parsed_maze


def print_maze(maze: list[list[int]]):
    for row in maze:
        for cell in row:
            if cell == OBSTACLE:
                print('#', end='')
            elif cell == FLOOR:
                print(' ', end='')
            elif cell == ILLEGAL_MOUSE:
                print('X', end='')
            elif cell == MOUSE:
                print('O', end='')
            else:
                raise ValueError('Invalid cell value')
        print()


def print_chromosome(chromosome: list[int], maze: list[list[int]]):
    """
    Print a chromosome's path throughout the maze
    """
    row, col = START
    print(f'Start: {START}, Row: {row}, Col: {col}')
    for move in chromosome:
        move = MOVES_MAP[move]
        row += move[0]
        col += move[1]
        print(f'Move: {move}, Row: {row}, Col: {col}')
        if (row >= 0 and row < HEIGHT) and (col >= 0 and col < WIDTH):
            maze[row][col] = MOUSE if maze[row][col] != OBSTACLE else ILLEGAL_MOUSE
    print_maze(maze)


def generate_population(population_size: int, chromosome_size: int):
    """
    Generate a population of chromosomes. 
    Each chromosome is a list of moves, represented by a number
    mapping to the appropriate aritmetics that needs to be done
    on the current position to get the next position's coordinates
    """
    population = []
    for _ in range(population_size):
        chromosome = [r.choice(list(MOVES_MAP.keys()))
                      for _ in range(chromosome_size)]
        population.append(chromosome)
    return population


def fitness(chromosome: list[int], maze: list[list[int]]):
    """
    Fitness function for the GA. The fitness of a chromosome is the
    distance between the goal and the current position, plus a penalty.
    Penalty is assigned when
      a) the mouse hits an obstacle, and
      b) when the mouse goes out of bounds
    Optimal solution would then be the path with the least penalty, i.e. 
    the path that reaches the goal without hitting any obstacles
    """
    penalty = 0
    moves = 0
    col, row = START

    for move_key in chromosome:
        move = MOVES_MAP[move_key]
        row += move[0]
        col += move[1]

        # Gone out of bounds, give penalty
        if (row < 0 or row >= HEIGHT) or (col < 0 or col >= WIDTH):
            penalty += OBSTACLE

        else:
            # Hit an obstacle, give penalty
            if (maze[row][col] == OBSTACLE):
                penalty += OBSTACLE
            # Give small penalty for moving
            if move_key != 0:
                moves += FLOOR

    distance = abs(FINISH[0] - row) + abs(FINISH[1] - col)
    return distance + penalty + moves


def fittest_chromosome(population: list[int]):
    """
    Return the fittest chromosome in the population, i.e
    the chromosome with the lowest fitness score
    """
    return min(population, key=lambda x: fitness(x, MAZE))


def crossover(parent1: list[int], parent2: list[int]):
    """
    Perform crossover on two chromosomes
    """
    assert (len(parent1) == len(parent2)), 'Chromosomes must be of same length'

    crossover_point = r.randint(0, len(parent1) - 1)
    offspring = parent1[:crossover_point] + parent2[crossover_point:]

    assert (len(offspring) == len(parent1)
            ), 'Offspring must be of the same length as its parents'
    return offspring


def mutate(chromosome: list[int]):
    """
    Mutate a chromosome, i.e. randomly change a move the
    mouse makes
    """
    if r.random() < MUTATION_RATE:
        mutation_point = r.randint(0, len(chromosome) - 1)
        new_move = r.choice(list(MOVES_MAP.keys()))
        chromosome[mutation_point] = new_move
    return chromosome


def find_fittest(population: list[list[int]], fittest_score: int, generation: int, maze: list[list[int]]) -> list[int]:
    """
    Find the optimal chromosome in the population
    """
    if fittest_score < 30000:
        chromosome = fittest_chromosome(population)
        return (chromosome, fittest_score, generation)

    new_population = []
    for _ in range(POPULATION_SIZE):
        # Select two parents using Roulette Wheel Selection
        total_score = sum([fitness(x, maze) for x in population])
        weights = [total_score / fitness(x, maze) for x in population]
        parents = r.choices(population, weights=weights, k=2)
        # print(f'Fittest parents: {parents}')

        # Crossover and mutate
        child = crossover(parents[0], parents[1])
        child = mutate(child)
        new_population.append(child)

    fittest = fitness(fittest_chromosome(new_population), maze)

    print(
        f'Generation {generation} - This gen fittest: {fittest} - Best fittest: {fittest_score}')
    # Reccursively find the optimal chromosome
    return find_fittest(new_population, min(
        fittest, fittest_score), generation + 1, maze)


def main():
    # Load maze and generate population
    maze = load_maze(MAZE)
    pop = generate_population(POPULATION_SIZE, CHROMOSOME_SIZE)

    # Find the fittest chromosome
    chromosome, score, gen = find_fittest(pop, math.inf, 0, maze)

    # Print the optimal chromosome
    print(f'Finished after {gen} generations')
    print(f'Fittest chromosome\'s score: {score}')
    print_chromosome(chromosome, maze)


if __name__ == '__main__':
    main()