maze.py

import random
from termcolor import colored



m = [[1, 1, 1, 1, 1, 1, 1],
     [0, 0, 1, 0, 1, 1, 1],
     [1, 0, 0, 0, 0, 1, 1],
     [1, 0, 1, 1, 0, 1, 1],
     [1, 0, 1, 0, 0, 0, 0],
     [1, 1, 1, 1, 1, 1, 1]]


class Point:

    def __init__(self, x, y):
        self.x = x
        self.y =y


def solve_maze(maze, startX, startY, endX, endY):
    visited = []
    for x, line in enumerate(maze):
        visited.append([])
        for cell in line:    
            visited[x].append(cell)
    
    visited[startX][startY] = 3
    currX = startX
    currY = startY

    options = []

    while currX != endX or currY != endY:

        if currX+1 < len(maze[currX]) and maze[currX+1][currY] != 1 and visited[currX+1][currY] < 2:
            options.append(Point(currX+1, currY))

        if currX-1 >= 0 and maze[currX-1][currY] != 1 and visited[currX-1][currY] < 2:
            options.append(Point(currX-1, currY))
        
        if currY+1 < len(maze[currX]) and maze[currX][currY+1] != 1 and visited[currX][currY+1] < 2:
            options.append(Point(currX, currY+1))
        
        if currY-1 >= 0 and maze[currX][currY-1] != 1 and visited[currX][currY-1] < 2:
            options.append(Point(currX, currY-1))

        if len(options) == 0: # no options means nowhere to go
            return None
        
        go_to_point = options.pop()
        currX = go_to_point.x
        currY = go_to_point.y
        visited[currX][currY] = 2

    visited[endX][endY] = 4
    return visited


def print_maze(maze):
    print('')
    print('')
    for line in maze:
        print('   ', end='')
        for cell in line:
            if cell == 1:
                print(colored('##', 'red'), end='')
            elif cell == 0:
                print('  ', end='')
            elif cell == 3:
                print('@@', end='')
            elif cell == 4:
                print('&&', end='')
            else:
                print(colored('**', 'green'), end='')
        print('\n', end='')
    print('')
    print('')



class Maze:

    def __init__(self, matrix, startX, startY, endX, endY):
        self.matrix = matrix
        self.startX = startX
        self.startY = startY
        self.endX = endX
        self.endY = endY


def generate_maze(size):

    maze = []
    # initialize our matrix
    for i in range(0, size):
        maze.append([])
        for j in range(0, size):
            maze[i].append(1)

    startX = 1
    startY = 1
    endX = 1
    endY = 1

    # create a random starting point and ending point
    while startX == endX or startY == endY or abs(startX - endX) < (size/2) or abs(startY - endY) < (size/2):
        random.seed()
        startX = random.randint(1, size-2)
        startY = random.randint(1, size-2)
        endX = random.randint(1, size-2)
        endY = random.randint(1, size-2)
    
    currX = startX
    currY = startY
    
    options = []
    maze[currX][currY] = 0
    # start creating the maze halls
    while (currY != endY or currX != endX):
        

        if currX > 1 and maze[currX-1][currY] != 0: # left
            options.append(Point(currX-1, currY))

        if currX + 2 < size and maze[currX+1][currY] != 0: # right
            options.append(Point(currX+1, currY))

        if currY +2 < size and maze[currX][currY+1] != 0: # up
            options.append(Point(currX, currY+1))

        if currY > 1 and maze[currX][currY-1] != 0: # down
            options.append(Point(currX, currY-1))

        if len(options) == 0: # no options means nowhere to go
            return None

        random.seed()
        rand_opt = random.randint(0, len(options)-1)
        go_to_point = options.pop(rand_opt)
        while True:
            zeros = 0
            if maze[go_to_point.x-1][go_to_point.y] == 0:
                zeros+=1
            if maze[go_to_point.x+1][go_to_point.y] == 0:
                zeros+=1
            if maze[go_to_point.x][go_to_point.y+1] == 0:
                zeros+=1
            if maze[go_to_point.x][go_to_point.y-1] == 0:
                zeros+=1
                
            if zeros == 1:
                break
            if len(options) == 0:
                break
            
            rand_opt = random.randint(0, len(options)-1)
            go_to_point = options.pop(rand_opt)

        currX = go_to_point.x
        currY = go_to_point.y
        maze[currX][currY] = 0

    return Maze(maze, startX, startY, endX, endY)

def main():
    
    size = 20
    maze = generate_maze(size)
    while maze == None:
        maze = generate_maze(size)
    solved = solve_maze(maze.matrix, maze.startX, maze.startY, maze.endX, maze.endY)
    if solved == None:
        print("Can't solve maze")
        print_maze(maze.matrix)
        return
    print_maze(solved)
    


if __name__ == '__main__':
    main()