Maze Solver 3D

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

Don't know what to do? Don't worry, we can help!
Learn about: shapes, icons, colors, animations, and the Python language.