Are you sure?
Do you want to delete “Maze Solver 3D” permanently? You will not be able to undo this action.
################################################################################ # Maze Solver 3D by Scepheo # # # # Generates a random maze, walks to each corner in a random order and renders # # the path in pseudo-3D # ################################################################################ # Configuration ################################################################################ # Size of the maze (number of cells). Setting this higher results in longer # paths, which is more expensive SIZE = 9 # Number of vertical lines used for the render. Setting this higher looks # better, but it gets more expensive very quickly LINE_COUNT = 26 # Camera projection plane size. Controls the field-of-view. 1 corresponds to a # 45 degree FOV, setting it higher increases the FOV. No effect on performance PLANE_SIZE = 1.2 # Time (in seconds) a move (turn/step) should take. No effect on performance MOVE_TIME = 1 # Number of frames to render per move. Again, higher looks better (smoother), # but has a large impact on performance MOVE_STEPS = 8 # Logic ################################################################################ import random import math # Pre-calculated values CELL_SIZE = 100 / SIZE MATRIX_SIZE = SIZE * SIZE LINE_SIZE = 100 / LINE_COUNT MOVE_DURATION = MOVE_TIME / MOVE_STEPS INF = float('inf') def set_2d(matrix, point, value): """ Sets a value in a 2d-array """ matrix[SIZE * point[0] + point[1]] = value def get_2d(matrix, point): """ Gets a value in a 2d-array """ return matrix[SIZE * point[0] + point[1]] def wall_neighbors(cell): """ Gets all the walls neighboring the given 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): """ Gets all the cells neighboring the given 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(): """ Generates a maze of SIZE by SIZE """ # This generates the maze using Prim's algorithm, see # https://en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim's_algorithm # for more information 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: set_2d(maze, wall, False) visited.add(unvisited) walls.update(wall_neighbors(unvisited)) return maze def maze_neighbors(maze, point): """ Gets all the cells reachable in the maze from the given point """ x = point[0] y = point[1] n = [] if x > 1 and not get_2d(maze, (x - 1, y)): n.append((x - 1, y)) if y > 1 and not get_2d(maze, (x, y - 1)): n.append((x, y - 1)) if x < SIZE - 2 and not get_2d(maze, (x + 1, y)): n.append((x + 1, y)) if y < SIZE - 2 and not get_2d(maze, (x, y + 1)): n.append((x, y + 1)) return n def find_distances(maze, player, target): """ Generates a SIZE by SIZE array containing the distances to the target cell. """ distances = [MATRIX_SIZE for _ in range(MATRIX_SIZE)] visited = set() visited.add(target) todo = [target] todo_index = 0 set_2d(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 = get_2d(distances, point) for n in maze_neighbors(maze, point): if n not in visited: visited.add(n) set_2d(distances, n, value + 1) todo.append(n) return distances def find_next(maze, distances, point): """ Finds the next cell to move to from the given one """ best = MATRIX_SIZE top = None for n in maze_neighbors(maze, point): distance = get_2d(distances, n) if distance < best: best = distance top = n return top def trace(maze, position, direction): """ Renders a single line """ dir_x = direction[0] dir_y = direction[1] pos_x = position[0] pos_y = position[1] map_x = int(pos_x) map_y = int(pos_y) distance = 0 hit = False side = False if dir_x < 0: step_x = -1 delta_dist_x = -1 / dir_x side_dist_x = (pos_x - map_x) * delta_dist_x elif dir_x > 0: step_x = 1 delta_dist_x = 1 / dir_x side_dist_x = (map_x + 1 - pos_x) * delta_dist_x else: step_x = 0 delta_dist_x = INF side_dist_x = INF if dir_y < 0: step_y = -1 delta_dist_y = -1 / dir_y side_dist_y = (pos_y - map_y ) * delta_dist_y elif dir_y > 0: step_y = 1 delta_dist_y = 1 / dir_y side_dist_y = (map_y + 1 - pos_y) * delta_dist_y else: step_y = 0 delta_dist_y = INF side_dist_y = INF while not hit: if side_dist_x < side_dist_y: side_dist_x += delta_dist_x map_x += step_x side = False else: side_dist_y += delta_dist_y map_y += step_y side = True hit = maze[SIZE * map_x + map_y] if side: distance = (map_y - pos_y + (1 - step_y) / 2) / dir_y else: distance = (map_x - pos_x + (1 - step_x) / 2) / dir_x return (distance, side) def render(maze, position, direction, lines): """ Renders a single frame """ plane = (direction[1], -direction[0]) for i in range(LINE_COUNT): offset = (i / (LINE_COUNT - 1) - 0.5) * PLANE_SIZE look_target = (direction[0] + offset * plane[0], direction[1] + offset * plane[1]) (distance, side) = trace(maze, position, look_target) lines[i].height = 1 / distance * 70 lines[i].color = 'firebrick' if side else 'darkred' def generate_targets(): targets = [(SIZE - 2, 1), (SIZE - 2, SIZE - 2), (1, SIZE - 2), (1, 1)] random.shuffle(targets) return targets def main(): # We set the random seed to ensure it can finish in time (not every maze # layout) has a short enough solution random.seed(10) Rectangle(height = 50, y = 25, color = 'cornflowerblue') Rectangle(height = 50, y = 75, color = 'forestgreen') lines = [Rectangle(width = LINE_SIZE + 0.2, height = 50, x = (i + 0.5) * LINE_SIZE) for i in range(LINE_COUNT)] maze = generate_maze() targets = generate_targets() prev_dir = (1, 0) prev_pos = targets[-1] for target in targets: distances = find_distances(maze, prev_pos, target) while prev_pos != target: next_pos = find_next(maze, distances, prev_pos) next_dir = (next_pos[0] - prev_pos[0], next_pos[1] - prev_pos[1]) render_pos_x = prev_pos[0] + 0.5 render_pos_y = prev_pos[1] + 0.5 # Animate the turn if next_dir != prev_dir: angle = math.atan2(next_dir[1], next_dir[0]) - math.atan2(prev_dir[1], prev_dir[0]) while angle > math.pi: angle -= 2 * math.pi while angle < -math.pi: angle += 2 * math.pi for i in range(1, MOVE_STEPS + 1): target_angle = angle * i / MOVE_STEPS cs = math.cos(target_angle) sn = math.sin(target_angle) dir_x = prev_dir[0] * cs - prev_dir[1] * sn dir_y = prev_dir[0] * sn + prev_dir[1] * cs with animation(duration = 0.0001): render(maze, (render_pos_x, render_pos_y), (dir_x, dir_y), lines) with animation(duration = MOVE_DURATION): pass # Animate the move pos_dif_x = next_pos[0] - prev_pos[0] pos_dif_y = next_pos[1] - prev_pos[1] for i in range(1, MOVE_STEPS + 1): pos_x = render_pos_x + pos_dif_x * i / MOVE_STEPS pos_y = render_pos_y + pos_dif_y * i / MOVE_STEPS with animation(duration = 0.0001): render(maze, (pos_x, pos_y), next_dir, lines) with animation(duration = MOVE_DURATION): pass prev_pos = next_pos prev_dir = next_dir main()