maze2.py

import random
import sys
import time
from termcolor import colored



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


class MazeSolver:

    def __init__(self):
        self.currX = 0
        self.currY = 0

    def init_maze(self, maze):
        self.intersections = []
        self.maze = maze
        self.currX = maze.startX
        self.currY = maze.startY
        self._init_visited()
    
    def _init_visited(self):
        self.visited = []
        for x, line in enumerate(self.maze.matrix):
            self.visited.append([])
            for cell in line:    
                self.visited[x].append(cell)

    def _is_not_visited(self, x, y):
        return self.visited[x][y] != 2
    
    def _is_not_wall(self, x, y):
        return self.maze.matrix[x][y] != 1
    
    def _is_in_bounds(self, x, y):
        return x >= 0 and x < len(self.maze.matrix[x]) and y >= 0 and y < len(self.maze.matrix)
        
    def _can_go(self, x, y):
        return self._is_in_bounds(x, y) and self._is_not_wall(x, y) and self._is_not_visited(x, y)

    def _get_options(self, x, y):
        options = [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]
        return [option for option in options if self._can_go(option[0], option[1])]
    
    def _walk(self):
        self.visited[self.currX][self.currY] = 2
        options = self._get_options(self.currX, self.currY)
        if len(options) == 0:
            return False
        elif len(options) > 1:
            self.intersections.append((self.currX, self.currY))
        self.currX, self.currY = options.pop()
        return True
    
    def _go_to_last_intersection(self):
        if len(self.intersections) == 0:
            return False
        last_intersection = self.intersections.pop()
        self.currX = last_intersection[0]
        self.currY = last_intersection[1]
        return True
    
    def solve(self, animate=False):
        while self.currX != self.maze.endX or self.currY != self.maze.endY:
            
            if animate:
                print_maze(self.visited, clear=True)
                time.sleep(0.1)
            can_walk = self._walk()
            if not can_walk:
                can_go_to_last_intersection = self._go_to_last_intersection()
                if can_go_to_last_intersection:
                    continue
                self.visited[self.maze.startX][self.maze.startY] = 3
                self.visited[self.maze.endX][self.maze.endY] = 4
                print_maze(self.visited)
                return None # We cannot walk and have nowehere to go back to
        self.visited[self.maze.startX][self.maze.startY] = 3
        self.visited[self.maze.endX][self.maze.endY] = 4
        return self.visited


def print_maze(maze, clear=False):
    print('')
    print('')
    print('      ', end='')
    for i in range(len(maze[0])):
        print("{0:0=2d}".format(i), '', end='')
    print('')
    rows = 3
    for i, line in enumerate(maze):
        print(' ', "{0:0=2d}".format(i) ,' ', 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='')
        rows += 1
    print('')
    print('')
    rows += 2
    if clear:
        for i in range(0, rows):
                sys.stdout.write("\033[K")  # remove line
                sys.stdout.write("\033[1A") # up the cursor  




class MazeGenerator:

    def init_maze(self, size, max_path_len=10):
        self.size = size
        self.max_path_len = max_path_len
        self.maze = []
        self.track = []
        for i in range(0, size):
            self.maze.append([])
            for j in range(0, size):
                self.maze[i].append(1)

    def _create_starting_and_ending_points(self):
        self.startX = 1
        self.startY = 1
        self.endX = 1
        self.endY = 1
        while self.startX == self.endX or self.startY == self.endY or abs(self.startX - self.endX) < (self.size/2) or abs(self.startY - self.endY) < (self.size/2):
            random.seed()
            self.startX = random.randint(1, self.size-2)
            self.startY = random.randint(1, self.size-2)
            self.endX = random.randint(1, self.size-2)
            self.endY = random.randint(1, self.size-2)
        
    def _is_in_bounds(self, x, y):
        return x >= 1 and x < self.size - 1 and y >= 1 and y < self.size -1
    
    def _is_not_destroying_wall(self, x, y):
        options = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
        num_of_zeros = 0
        for option in options:
            if self.maze[option[0]][option[1]] == 0:
                num_of_zeros += 1
        return num_of_zeros <= 1
        
    def _can_walk_to(self, x, y):
        return self._is_in_bounds(x, y) and self._is_not_destroying_wall(x, y) and self.maze[x][y] != 0

    def _is_near_ending(self, x, y):
        options = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
        for option in options:
            _x, _y = option
            if _x == self.endX and _y == self.endY:
                return True

    def _randomize_direction(self):
        left = lambda: (self.currX - 1, self.currY)
        right = lambda: (self.currX + 1, self.currY)
        up = lambda: (self.currX, self.currY + 1)
        down = lambda: (self.currX, self.currY - 1)
        directions = [left, right, up, down]
        options = []
        for direction in directions:
            x, y = direction()
            if self._can_walk_to(x, y):
                options.append(direction)
        if len(options) == 0:
            return None
        random.seed()
        return options[random.randint(0, len(options)-1)]

    def _try_walk(self, num_of_steps):
        steps_taken = 0
        direction = self._randomize_direction()
        if direction is None:
            return steps_taken
        for i in range(0, num_of_steps):
            if self._is_near_ending(self.currX, self.currY):
                self.currX = self.endX
                self.currY = self.endY
                self.maze[self.currX][self.currY] = 0
                return 0
            x, y = direction()
            if self._can_walk_to(x, y): 
                self.maze[x][y] = 0
                self.currX = x
                self.currY = y
                self.track.append((x, y))
                steps_taken += 1
        return steps_taken

    def _go_back(self):
        self.currX, self.currY = self.track.pop()
    
    def generate(self):
        self._create_starting_and_ending_points()
        self.currX = self.startX
        self.currY = self.startY
        self.maze[self.currX][self.currY] = 0
        self.track.append((self.currX, self.currY))
        while len(self.track) > 0:
            random.seed()
            num_of_steps = random.randint(1, self.max_path_len)
            steps_taken = self._try_walk(num_of_steps)
            if steps_taken == 0:
                self._go_back()

        self.maze[self.startX][self.startY] = 3
        self.maze[self.endX][self.endY] = 4

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


def main():
    
    size = 30
    maze_generator = MazeGenerator()
    maze_generator.init_maze(size, max_path_len=20)
    maze = maze_generator.generate()
    if maze == None:
        print("Can't generate maze")
        return
    maze_solver = MazeSolver()
    maze_solver.init_maze(maze)
    solved = maze_solver.solve(animate=True)  
    if solved == None:
        print("Can't solve maze")
        return
    print_maze(solved)



    
if __name__ == '__main__':
    main()