Are you sure?
Do you want to delete “Maze Solver” permanently? You will not be able to undo this action.
import random SIZE = 19 CELL_SIZE = 100 / SIZE MATRIX_SIZE = SIZE * SIZE def mset(matrix, point, value): matrix[SIZE * point[0] + point[1]] = value def mget(matrix, point): return matrix[SIZE * point[0] + point[1]] def wall_neighbors(cell): x = cell[0] y = cell[1] n = [] if x > 2: n.append((x - 1, y)) if y > 2: n.append((x, y - 1)) if x < SIZE - 3: n.append((x + 1, y)) if y < SIZE - 3: n.append((x, y + 1)) return n def cell_neighbors(wall): x = wall[0] y = wall[1] n = [] if x % 2 == 0: if x > 0: n.append((x - 1, y)) if x < SIZE - 1: n.append((x + 1, y)) else: if y > 0: n.append((x, y - 1)) if y < SIZE - 1: n.append((x, y + 1)) return n def generate_maze(): maze = [(i % SIZE) % 2 == 0 or (i * SIZE) % 2 == 1 for i in range(MATRIX_SIZE)] walls = set() visited = set() point = (1, 1) visited.add(point) walls.update(wall_neighbors(point)) while len(walls) > 0: wall = random.sample(walls, 1)[0] walls.remove(wall) count = 0 for n in cell_neighbors(wall): if n in visited: count += 1 else: unvisited = n if count == 1: mset(maze, wall, False) visited.add(unvisited) walls.update(wall_neighbors(unvisited)) return maze def draw_map(maze): for x in range(SIZE): for y in range(SIZE): color = 'black' if mget(maze, (x, y)) else 'white' Rectangle(width=CELL_SIZE,height=CELL_SIZE,x=(x+.5)*CELL_SIZE,y=(y+.5)*CELL_SIZE,color=color) def maze_neighbors(maze, point): x = point[0] y = point[1] n = [] if x > 1 and not mget(maze, (x - 1, y)): n.append((x - 1, y)) if y > 1 and not mget(maze, (x, y - 1)): n.append((x, y - 1)) if x < SIZE - 2 and not mget(maze, (x + 1, y)): n.append((x + 1, y)) if y < SIZE - 2 and not mget(maze, (x, y + 1)): n.append((x, y + 1)) return n def find_distances(maze, player, target): distances = [MATRIX_SIZE for _ in range(MATRIX_SIZE)] visited = set() visited.add(target) todo = [target] todo_index = 0 mset(distances, target, 0) found = False while not found and todo_index < len(todo): point = todo[todo_index] todo_index += 1 if point == player: found = True else: value = mget(distances, point) for n in maze_neighbors(maze, point): if n not in visited: visited.add(n) mset(distances, n, value + 1) todo.append(n) return distances def find_next(maze, distances, point): best = MATRIX_SIZE top = None for n in maze_neighbors(maze, point): distance = mget(distances, n) if distance < best: best = distance top = n return top center = (SIZE // 2, SIZE // 2) targets = [(SIZE - 2, 1), (SIZE - 2, SIZE - 2), (1, SIZE - 2), (1, 1), center] for _ in range(5): x = random.randint(1, SIZE // 2) * 2 - 1 y = random.randint(1, SIZE // 2) * 2 - 1 targets.append((x, y)) random.shuffle(targets) target = targets[0] player = targets[-1] maze = generate_maze() draw_map(maze) player_circle = Circle(width=CELL_SIZE,height=CELL_SIZE,x=(player[0]+.5)*CELL_SIZE,y=(player[1]+.5)*CELL_SIZE,color='red') target_circle = Circle(width=CELL_SIZE,height=CELL_SIZE,x=(target[0]+.5)*CELL_SIZE,y=(target[1]+.5)*CELL_SIZE,color='blue') for target in targets: distances = find_distances(maze, player, target) with animation(duration = 0.001): target_circle.x = (target[0]+.5)*CELL_SIZE target_circle.y = (target[1]+.5)*CELL_SIZE while player != target: with animation(duration = 0.25): player = find_next(maze, distances, player) player_circle.x = (player[0]+.5)*CELL_SIZE player_circle.y = (player[1]+.5)*CELL_SIZE