mario.py (7577B)
1 import random 2 3 # Map dimensions 4 rows = 10 5 cols = 15 6 7 # Map symbols 8 wall = '#' 9 floor = ' ' 10 goomba = 'G' 11 mario = 'M' 12 end = 'E' 13 14 # Map class that handles moving Mario 15 # Takes in: 16 # map - list of lists 17 # pos - tuple coordinate in the form (X, Y) 18 # exit - same as above 19 class Map: 20 def __init__(self, map, pos, exit): 21 self.map = map 22 self.pos = pos 23 self.exit = exit 24 self.penalties = 0 25 self.dead = False 26 27 # Determine which direction to move in 28 def up(self): 29 # Check to see if in bounds 30 if self.pos[1] - 1 >= 0: 31 # Define move and initiate 32 pos = (self.pos[0], self.pos[1] - 1) 33 self.move(pos) 34 def down(self): 35 if self.pos[1] + 1 < rows: 36 pos = (self.pos[0], self.pos[1] + 1) 37 self.move(pos) 38 def left(self): 39 if self.pos[0] - 1 >= 0: 40 pos = (self.pos[0] - 1, self.pos[1]) 41 self.move(pos) 42 def right(self): 43 if self.pos[0] + 1 < cols: 44 pos = (self.pos[0] + 1, self.pos[1]) 45 self.move(pos) 46 47 # Actually move player 48 def move(self, pos): 49 # If wall is hit, add to penalties (used for fitness function) 50 if (self.is_wall(pos)): 51 self.penalties += 1 52 53 # Mario dies instantly if he lands on a goomba 54 if (self.is_goomba(pos)): 55 self.dead = True 56 57 # Replace floor/exit symbol with Mario 58 if (self.is_done(pos) or self.is_floor(pos)): 59 self.map[self.pos[1]][self.pos[0]] = floor 60 self.map[pos[1]][pos[0]] = mario 61 self.pos = pos 62 63 # Check for certain map symbols 64 def is_wall(self, pos): 65 return self.map[pos[1]][pos[0]] == wall 66 def is_done(self, pos): 67 return self.map[pos[1]][pos[0]] == end 68 def is_floor(self, pos): 69 return self.map[pos[1]][pos[0]] == floor 70 def is_goomba(self, pos): 71 return self.map[pos[1]][pos[0]] == goomba 72 73 # Reset map after fitness evaluation 74 def reset(self): 75 if (self.pos != (0,2)): 76 self.move((0,2)) 77 self.map[7][14] = end 78 self.penalties = 0 79 80 # Print map as visual aid 81 def __str__(self): 82 return '\n'.join([''.join([str(char) for char in row]) for row in self.map]) 83 84 # Genetic algorithm class 85 # Takes in: 86 # map - a Map object 87 # move_limit - maximum amount of moves allowed in chromosome 88 # population_size - how many chromosomes in the population 89 # mutation_chance - what are the odds of a chromosome mutating? (0-1) 90 class Genetic: 91 def __init__(self, map, move_limit, population_size, mutation_chance): 92 self.map = map 93 self.move_limit = move_limit 94 self.population_size = population_size 95 self.mutation_chance = mutation_chance 96 97 # Initialize population with population_size chromosomes containg move_limit 98 # moves 99 self.population = [[random.randint(0, 4) for x in range(self.move_limit)] for y in 100 range(self.population_size)] 101 102 # Determine fitness of a chromosome 103 def fitness(self, chromosome): 104 for move in chromosome: 105 if move == 0: pass # Don't move anywhere 106 # Move up, down, left, right based on number in chromosome 107 elif move == 1: self.map.up() 108 elif move == 2: self.map.down() 109 elif move == 3: self.map.left() 110 elif move == 4: self.map.right() 111 112 # Score is Manhattan distance since we're using a Cartesian coordinate 113 # system 114 score = abs(self.map.exit[0] - self.map.pos[0]) + abs(self.map.exit[1] - 115 self.map.pos[1]) 116 117 # Move Mario back to beginning to evaluate new chromosomes 118 self.map.reset() 119 120 return score 121 122 # Simple function that returns fittest score from a population 123 # Get fitness for every chromosome in population and return list containing 124 # just the scores, sort it numerically, and return first (lowest) score 125 def fittest_score(self, population): 126 fitness = list(map(self.fitness, population)) 127 fitness.sort() 128 return fitness[0] 129 130 # Replace random move in chromosome with another move based on mutation_chance 131 def mutate(self, chromosome): 132 if self.mutation_chance > random.random(): 133 chromosome[random.randint(0, len(chromosome) - 1)] = random.randint(0, 4) 134 135 return chromosome 136 137 # Produce offspring for the population 138 def crossover(self, population): 139 new_population = [] 140 141 for i in range(self.population_size - 1): 142 # Select two random chromosomes from population 143 mom = self.population[random.randint(0, len(population) + 1)] 144 dad = self.population[random.randint(0, len(population) + 1)] 145 146 # The point at which the moves will be combined 147 crossover_point = random.randint(0, self.move_limit - 1) 148 149 # Produce offspring with chance of mutation 150 offspring = mom[0:crossover_point] + dad[crossover_point:len(dad)] 151 offspring = self.mutate(offspring) 152 153 new_population.append(offspring) 154 155 return new_population 156 157 # Find best moves from the population 158 # Start off with absurdly large fitness score 159 def get_optimal_moves(self, population): 160 return self.helper(population, 999) 161 162 # Helper function for finding optimal moves 163 # Iterative solution used since Python does not use tail call optimization 164 def helper(self, population, most_fit_score): 165 # Change this to find a solution within N tiles from exit 166 while most_fit_score > 0: 167 fitness = list(map(lambda x: (self.fitness(x), x), population)) 168 169 # Survival of the fittest, get most fit half from population 170 sorted_fitness = sorted(fitness, key=lambda tup: tup[0]) 171 half_most_fit = sorted_fitness[0:int(len(sorted_fitness) / 2)] 172 173 # Get most fit score from the half and keep trying 174 new_population = self.crossover(list(map(lambda x:(x[1]), half_most_fit))) 175 population = new_population 176 most_fit_score = self.fittest_score(new_population) 177 return population 178 179 def main(): 180 # The maze Mario will be navigating 181 lst = [['#','#','#','#','#','#','#','#','#','#','#','#','#','#','#'], 182 ['#',' ','#',' ',' ',' ',' ',' ','#','#','#',' ','G',' ','#'], 183 ['M',' ',' ',' ',' ','G',' ',' ','#','#','#',' ',' ',' ','#'], 184 ['#',' ',' ',' ','#','#','#',' ',' ','#',' ',' ',' ',' ','#'], 185 ['#',' ',' ',' ','#','#','#',' ',' ',' ',' ',' ','#',' ','#'], 186 ['#','#',' ',' ','#','#','#',' ',' ',' ',' ',' ','#',' ','#'], 187 ['#',' ',' ',' ',' ','#',' ',' ',' ',' ','#','#','#',' ','#'], 188 ['#','G','#','#',' ',' ',' ','#',' ',' ',' ',' ',' ',' ','E'], 189 ['#',' ','#','#',' ',' ',' ','#',' ',' ','G',' ',' ',' ','#'], 190 ['#','#','#','#','#','#','#','#','#','#','#','#','#','#','#']] 191 maze = Map(lst, (0,2), (14,7)) 192 print('\nMario\'s position: (0, 2)\n' + str(maze)) 193 194 # Population size should be kept within a good range (both too low and too 195 # large will result in slow execution 196 # Maximum moves for chromosome is twenty-five (twenty-one required to solve 197 # maze in best case) 198 # Mutation rate should be kept low to reach goal faster 199 genetic = Genetic(maze, 1000, 25, 0.01) 200 201 print('\nFinding solution to the maze...') 202 203 # Get moves required for optimal traversal and score that results 204 optimal_moves = genetic.get_optimal_moves(genetic.population) 205 final_fitness = list(map(lambda x: (genetic.fitness(x), x), optimal_moves)) 206 sorted_final_fitness = sorted(final_fitness, key=lambda tup: tup[0]) 207 print('\nScore: ' + str(sorted_final_fitness[0][0])) 208 209 # Actually move Mario 210 for move in sorted_final_fitness[0][1]: 211 if move == 0: pass 212 elif move == 1: maze.up() 213 elif move == 2: maze.down() 214 elif move == 3: maze.left() 215 elif move == 4: maze.right() 216 217 # Print solved maze 218 print('\nMario\'s position: ' + str(maze.pos) + '\n' + str(maze)) 219 220 if __name__ == "__main__": 221 main()