import pygame import time import collections # ----------------- # Pygame Setup # ----------------- pygame.init() # Constants WIDTH, HEIGHT = 900, 650 BLOCK_SIZE = 19 DARK = (109, 104, 117) # Colors MOVABLE_CELL = (255, 205, 178) WALL = (229, 152, 155) START = (120, 150, 100) DESTINATION = (255, 183, 0) # Initialize Display gameDisplay = pygame.display.set_mode((WIDTH, HEIGHT)) pygame.display.set_caption("Autonomous Maze Solver") # Maze definition maze = [ [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], [1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,1], [1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1], [1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,0,1], [1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,0,1], [1,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1], [1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1], [1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1], [1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,1], [1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,0,0,1,0,1], [1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1], [1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1], [1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1], [1,0,1,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,1], [1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1], [1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,2,2,2,1,0,1,0,1,0,0,0,1,0,0,0,1,0,1], [1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,2,1,2,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1], [1,0,0,0,1,0,1,0,0,0,1,0,0,0,1,2,2,2,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1], [1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,0,1,0,1], [1,0,1,0,1,0,0,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,0,1], [1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,1,1,0,1,0,1], [1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1], [1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1], [1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,0,0,1,0,1], [1,0,1,0,1,0,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1], [1,0,1,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1,0,1], [1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,0,1,0,1], [1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1], [1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1], [1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1], [1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1], [1,3,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], ] # ----------------- # Maze Drawing # ----------------- def render_maze(maze_array): """Renders the maze onto the display surface.""" for row_index, row in enumerate(maze_array): for col_index, block in enumerate(row): x, y = col_index * BLOCK_SIZE, row_index * BLOCK_SIZE if block == 0: # Movable cell pygame.draw.rect(gameDisplay, MOVABLE_CELL, (x, y, BLOCK_SIZE, BLOCK_SIZE)) elif block == 1: # Wall pygame.draw.rect(gameDisplay, WALL, (x, y, BLOCK_SIZE, BLOCK_SIZE)) elif block == 2: # Destination pygame.draw.rect(gameDisplay, DESTINATION, (x, y, BLOCK_SIZE, BLOCK_SIZE)) elif block == 3: # Start pygame.draw.rect(gameDisplay, START, (x, y, BLOCK_SIZE, BLOCK_SIZE)) # ----------------- # Text Rendering # ----------------- def display_text(text): """Displays text on the screen (centered) and waits briefly.""" font = pygame.font.Font('freesansbold.ttf', 45) text_surface = font.render(text, True, DARK) text_rect = text_surface.get_rect(center=(WIDTH // 2, HEIGHT // 2)) gameDisplay.blit(text_surface, text_rect) pygame.display.update() time.sleep(2) # ----------------- # BFS Search # ----------------- def bfs_search(maze_array): """ Finds a path from the Start block (3) to the Destination block (2) using BFS. Returns the path as a list of (row, col) from the start to the goal. """ rows = len(maze_array) cols = len(maze_array[0]) # Find the start (3) and all possible goals (2) start = None goals = [] for r in range(rows): for c in range(cols): if maze_array[r][c] == 3: start = (r, c) elif maze_array[r][c] == 2: goals.append((r, c)) if not start or not goals: return [] # No start or no goals found # BFS setup queue = collections.deque() queue.append(start) visited = set([start]) parent = dict() # Keep track of where we came from # Directions (row, col) directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # BFS loop while queue: current = queue.popleft() if current in goals: # Goal found, reconstruct path return reconstruct_path(parent, start, current) for d in directions: nr, nc = current[0] + d[0], current[1] + d[1] if 0 <= nr < rows and 0 <= nc < cols: if maze_array[nr][nc] != 1 and (nr, nc) not in visited: visited.add((nr, nc)) parent[(nr, nc)] = current queue.append((nr, nc)) # If we exhaust the queue without finding a path: return [] def reconstruct_path(parent, start, goal): """ Reconstructs the path from start to goal using the parent dictionary. Returns a list of (row, col) coordinates. """ path = [] current = goal while current != start: path.append(current) current = parent[current] path.append(start) path.reverse() return path # ----------------- # Main Loop # ----------------- def main(): path = bfs_search(maze) if not path: print("No path found from Start (3) to Destination (2)!") return # Path is a list of (row, col) from start to goal # We will move along this path autonomously. # Current index in the path (start at 0) path_index = 0 running = True clock = pygame.time.Clock() while running: gameDisplay.fill((0, 0, 0)) render_maze(maze) pygame.display.update() # Check if we've reached the end of the path if path_index == len(path) - 1: display_text("Yay! Destination Reached!") running = False for event in pygame.event.get(): if event.type == pygame.QUIT: running = False # Move along the path at a fixed speed # We'll do one step per iteration so we can see the movement. if path_index < len(path) - 1: current_pos = path[path_index] next_pos = path[path_index + 1] # Remove start marker from current cell (turn back to 0) if maze[current_pos[0]][current_pos[1]] == 3: maze[current_pos[0]][current_pos[1]] = 0 # Move player to next cell maze[next_pos[0]][next_pos[1]] = 3 path_index += 1 # Limit the frame rate so movement is visible clock.tick(5) pygame.quit() if __name__ == "__main__": main()