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()