# Sparsh Pandey
# 23 Jun 2025
# Generate maze

import random

# I made a backtracking example in the maze generation.
# I want to show y'all this, that's why I thought making 
# a maze would be cool. (Also I had a lot of trouble with 
# the undertale attack patterns). Don't let this backtracking 
# approach overwhelm you if you're confused. Should just try 
# to motivate you to realize how we can use programming to 
# solve problems.

# This is the actual backtracking behind the maze gen
def carve_path(maze, x, y, width, height):

    # these are all the directions we can go 
    # ( 2 spaces since we need 1 space for walls in between)
    dirs = [(0, -2), (2, 0), (0, 2), (-2, 0)]

    # don't aways move 0, -2 first! shuffle it so it moves more random
    random.shuffle(dirs)

    # iterate through our CURRENT direction list (save x and y direction movement)
    for dx, dy in dirs:

        # Get our new x and new y by adding d and dy with our old location
        nx, ny = x + dx, y + dy

        # check to see if we went out of bounds
        if 1 <= nx < width - 1 and 1 <= ny < height - 1:

            # if there's a wall, carve it in
            if maze[ny][nx] == 1:
                maze[ny][nx] = 0

                # this is a neat way of destroying the wall in the middle of the path we're carving
                maze[y + dy // 2][x + dx // 2] = 0

                # call the recusrive function to move on to the next part
                carve_path(maze, nx, ny, width, height)

# cool maze generator (backtracking)
def generate_maze(width, height):

    # Start with all walls everywhere (and use our 1 line trick to make our whole list)
    maze = [[1 for _ in range(width)] for _ in range(height)]

    # Start at 1, 1 since our borders are obviously all walls
    maze[1][1] = 0
    carve_path(maze, 1, 1, width, height)

    # Basically put the end block as close to the bottom right as you can (should 
    # always be in bottom right but not sure, so went with this)
    for y in range(height-2, 0, -1):
        for x in range(width-2, 0, -1):
            if maze[y][x] == 0:
                maze[y][x] = 2
                return maze