```################################################################################
# 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 + point] = value

def get_2d(matrix, point):
""" Gets a value in a 2d-array """
return matrix[SIZE * point + point]

def wall_neighbors(cell):
""" Gets all the walls neighboring the given cell """
x = cell
y = cell
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
y = wall
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

maze = [(i % SIZE) % 2 == 0 or (i * SIZE) % 2 == 1 for i in range(MATRIX_SIZE)]
walls = set()
visited = set()
point = (1, 1)
walls.update(wall_neighbors(point))
while len(walls) > 0:
wall = random.sample(walls, 1)
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)
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
y = point
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()
todo = [target]
todo_index = 0
set_2d(distances, target, 0)
found = False
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:
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

def trace(maze, position, direction):
""" Renders a single line """
dir_x = direction
dir_y = direction

pos_x = position
pos_y = position
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, -direction)

for i in range(LINE_COUNT):
offset = (i / (LINE_COUNT - 1) - 0.5) * PLANE_SIZE
look_target = (direction + offset * plane, direction + offset * plane)
(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 - prev_pos, next_pos - prev_pos)

render_pos_x = prev_pos + 0.5
render_pos_y = prev_pos + 0.5

# Animate the turn
if next_dir != prev_dir:
angle = math.atan2(next_dir, next_dir) - math.atan2(prev_dir, prev_dir)

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 * cs - prev_dir * sn
dir_y = prev_dir * sn + prev_dir * 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 - prev_pos
pos_dif_y = next_pos - prev_pos

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

# Maze Solver 3D

by Scepheo

Created 2 years, 3 months ago.