commit 99ca396c59261ffc6c60fb76d5ade8d8bfce5f02
Author: Matthew Carlson <matt@mcarlson.xyz>
Date: Mon, 15 Mar 2021 21:09:49 -0400
Initial commit
Diffstat:
| A | README.md | | | 11 | +++++++++++ |
| A | mario.py | | | 221 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 232 insertions(+), 0 deletions(-)
diff --git a/README.md b/README.md
@@ -0,0 +1,11 @@
+# Mario
+Uses a genetic algorithm to help Mario solve a maze
+
+
+
+M = Mario
+G = Goomba
+E = Exit
+# = Wall
+
+Algorithm may take up to a minute to complete depending on luck.
diff --git a/mario.py b/mario.py
@@ -0,0 +1,221 @@
+import random
+
+# Map dimensions
+rows = 10
+cols = 15
+
+# Map symbols
+wall = '#'
+floor = ' '
+goomba = 'G'
+mario = 'M'
+end = 'E'
+
+# Map class that handles moving Mario
+# Takes in:
+# map - list of lists
+# pos - tuple coordinate in the form (X, Y)
+# exit - same as above
+class Map:
+ def __init__(self, map, pos, exit):
+ self.map = map
+ self.pos = pos
+ self.exit = exit
+ self.penalties = 0
+ self.dead = False
+
+ # Determine which direction to move in
+ def up(self):
+ # Check to see if in bounds
+ if self.pos[1] - 1 >= 0:
+ # Define move and initiate
+ pos = (self.pos[0], self.pos[1] - 1)
+ self.move(pos)
+ def down(self):
+ if self.pos[1] + 1 < rows:
+ pos = (self.pos[0], self.pos[1] + 1)
+ self.move(pos)
+ def left(self):
+ if self.pos[0] - 1 >= 0:
+ pos = (self.pos[0] - 1, self.pos[1])
+ self.move(pos)
+ def right(self):
+ if self.pos[0] + 1 < cols:
+ pos = (self.pos[0] + 1, self.pos[1])
+ self.move(pos)
+
+ # Actually move player
+ def move(self, pos):
+ # If wall is hit, add to penalties (used for fitness function)
+ if (self.is_wall(pos)):
+ self.penalties += 1
+
+ # Mario dies instantly if he lands on a goomba
+ if (self.is_goomba(pos)):
+ self.dead = True
+
+ # Replace floor/exit symbol with Mario
+ if (self.is_done(pos) or self.is_floor(pos)):
+ self.map[self.pos[1]][self.pos[0]] = floor
+ self.map[pos[1]][pos[0]] = mario
+ self.pos = pos
+
+ # Check for certain map symbols
+ def is_wall(self, pos):
+ return self.map[pos[1]][pos[0]] == wall
+ def is_done(self, pos):
+ return self.map[pos[1]][pos[0]] == end
+ def is_floor(self, pos):
+ return self.map[pos[1]][pos[0]] == floor
+ def is_goomba(self, pos):
+ return self.map[pos[1]][pos[0]] == goomba
+
+ # Reset map after fitness evaluation
+ def reset(self):
+ if (self.pos != (0,2)):
+ self.move((0,2))
+ self.map[7][14] = end
+ self.penalties = 0
+
+ # Print map as visual aid
+ def __str__(self):
+ return '\n'.join([''.join([str(char) for char in row]) for row in self.map])
+
+# Genetic algorithm class
+# Takes in:
+# map - a Map object
+# move_limit - maximum amount of moves allowed in chromosome
+# population_size - how many chromosomes in the population
+# mutation_chance - what are the odds of a chromosome mutating? (0-1)
+class Genetic:
+ def __init__(self, map, move_limit, population_size, mutation_chance):
+ self.map = map
+ self.move_limit = move_limit
+ self.population_size = population_size
+ self.mutation_chance = mutation_chance
+
+ # Initialize population with population_size chromosomes containg move_limit
+ # moves
+ self.population = [[random.randint(0, 4) for x in range(self.move_limit)] for y in
+ range(self.population_size)]
+
+ # Determine fitness of a chromosome
+ def fitness(self, chromosome):
+ for move in chromosome:
+ if move == 0: pass # Don't move anywhere
+ # Move up, down, left, right based on number in chromosome
+ elif move == 1: self.map.up()
+ elif move == 2: self.map.down()
+ elif move == 3: self.map.left()
+ elif move == 4: self.map.right()
+
+ # Score is Manhattan distance since we're using a Cartesian coordinate
+ # system
+ score = abs(self.map.exit[0] - self.map.pos[0]) + abs(self.map.exit[1] -
+ self.map.pos[1])
+
+ # Move Mario back to beginning to evaluate new chromosomes
+ self.map.reset()
+
+ return score
+
+ # Simple function that returns fittest score from a population
+ # Get fitness for every chromosome in population and return list containing
+ # just the scores, sort it numerically, and return first (lowest) score
+ def fittest_score(self, population):
+ fitness = list(map(self.fitness, population))
+ fitness.sort()
+ return fitness[0]
+
+ # Replace random move in chromosome with another move based on mutation_chance
+ def mutate(self, chromosome):
+ if self.mutation_chance > random.random():
+ chromosome[random.randint(0, len(chromosome) - 1)] = random.randint(0, 4)
+
+ return chromosome
+
+ # Produce offspring for the population
+ def crossover(self, population):
+ new_population = []
+
+ for i in range(self.population_size - 1):
+ # Select two random chromosomes from population
+ mom = self.population[random.randint(0, len(population) + 1)]
+ dad = self.population[random.randint(0, len(population) + 1)]
+
+ # The point at which the moves will be combined
+ crossover_point = random.randint(0, self.move_limit - 1)
+
+ # Produce offspring with chance of mutation
+ offspring = mom[0:crossover_point] + dad[crossover_point:len(dad)]
+ offspring = self.mutate(offspring)
+
+ new_population.append(offspring)
+
+ return new_population
+
+ # Find best moves from the population
+ # Start off with absurdly large fitness score
+ def get_optimal_moves(self, population):
+ return self.helper(population, 999)
+
+ # Helper function for finding optimal moves
+ # Iterative solution used since Python does not use tail call optimization
+ def helper(self, population, most_fit_score):
+ # Change this to find a solution within N tiles from exit
+ while most_fit_score > 0:
+ fitness = list(map(lambda x: (self.fitness(x), x), population))
+
+ # Survival of the fittest, get most fit half from population
+ sorted_fitness = sorted(fitness, key=lambda tup: tup[0])
+ half_most_fit = sorted_fitness[0:int(len(sorted_fitness) / 2)]
+
+ # Get most fit score from the half and keep trying
+ new_population = self.crossover(list(map(lambda x:(x[1]), half_most_fit)))
+ population = new_population
+ most_fit_score = self.fittest_score(new_population)
+ return population
+
+def main():
+ # The maze Mario will be navigating
+ lst = [['#','#','#','#','#','#','#','#','#','#','#','#','#','#','#'],
+ ['#',' ','#',' ',' ',' ',' ',' ','#','#','#',' ','G',' ','#'],
+ ['M',' ',' ',' ',' ','G',' ',' ','#','#','#',' ',' ',' ','#'],
+ ['#',' ',' ',' ','#','#','#',' ',' ','#',' ',' ',' ',' ','#'],
+ ['#',' ',' ',' ','#','#','#',' ',' ',' ',' ',' ','#',' ','#'],
+ ['#','#',' ',' ','#','#','#',' ',' ',' ',' ',' ','#',' ','#'],
+ ['#',' ',' ',' ',' ','#',' ',' ',' ',' ','#','#','#',' ','#'],
+ ['#','G','#','#',' ',' ',' ','#',' ',' ',' ',' ',' ',' ','E'],
+ ['#',' ','#','#',' ',' ',' ','#',' ',' ','G',' ',' ',' ','#'],
+ ['#','#','#','#','#','#','#','#','#','#','#','#','#','#','#']]
+ maze = Map(lst, (0,2), (14,7))
+ print('\nMario\'s position: (0, 2)\n' + str(maze))
+
+ # Population size should be kept within a good range (both too low and too
+ # large will result in slow execution
+ # Maximum moves for chromosome is twenty-five (twenty-one required to solve
+ # maze in best case)
+ # Mutation rate should be kept low to reach goal faster
+ genetic = Genetic(maze, 1000, 25, 0.01)
+
+ print('\nFinding solution to the maze...')
+
+ # Get moves required for optimal traversal and score that results
+ optimal_moves = genetic.get_optimal_moves(genetic.population)
+ final_fitness = list(map(lambda x: (genetic.fitness(x), x), optimal_moves))
+ sorted_final_fitness = sorted(final_fitness, key=lambda tup: tup[0])
+ print('\nScore: ' + str(sorted_final_fitness[0][0]))
+
+ # Actually move Mario
+ for move in sorted_final_fitness[0][1]:
+ if move == 0: pass
+ elif move == 1: maze.up()
+ elif move == 2: maze.down()
+ elif move == 3: maze.left()
+ elif move == 4: maze.right()
+
+ # Print solved maze
+ print('\nMario\'s position: ' + str(maze.pos) + '\n' + str(maze))
+
+if __name__ == "__main__":
+ main()
