-
Notifications
You must be signed in to change notification settings - Fork 0
/
Maze_Reconfigure.py
123 lines (106 loc) · 5.63 KB
/
Maze_Reconfigure.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import pygame
import sys
from collections import deque
import heapq
# Colors
WHITE = (255, 255, 255) # Path
GREY = (128, 128, 128) # Wall
START_COLOR = (0, 0, 255) # Start (Blue)
GOAL_COLOR = (255, 0, 0) # Goal (Red)
ROBOT_COLOR = (0, 255, 0) # Robot (Green)
VISITED_COLOR = (100, 100, 255) # Visited nodes (Light blue)
PATH_COLOR = (255, 255, 0) # Final path (Yellow)
# Initialize Pygame
pygame.init()
screen = pygame.display.set_mode((560, 560)) # Increase size to accommodate larger maze
pygame.display.set_caption("Pygame Maze Solver - Complex Maze")
# Start and Goal positions (Updated)
start_pos = (20, 380) # A20 (Row 20, Column 1)
goal_pos = (520, 140) # AB10 (Row 10, Column 28)
# Complex Maze Layout Representation (0 = Path, 1 = Wall)
complex_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, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 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, 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, 0, 1],
[1, 1, 1, 1, 1, 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, 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, 0, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[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, 0, 1],
[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, 0, 1],
[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, 0, 1],
[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, 0, 1],
[1, 1, 1, 1, 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, 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, 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, 0, 1],
[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, 0, 1],
[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, 0, 1],
[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, 0, 1],
[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, 0, 1],
[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, 0, 1],
[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, 0, 1],
[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, 0, 1],
[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, 0, 1]
]
# Function to draw the complex maze
def draw_complex_maze():
cell_size = 20 # Each cell is 20x20 pixels
for row_index, row in enumerate(complex_maze):
for col_index, value in enumerate(row):
color = WHITE # Default to path
if value == 1:
color = GREY # Wall
pygame.draw.rect(screen, color, (col_index * cell_size, row_index * cell_size, cell_size, cell_size))
# Draw Start and Goal
pygame.draw.rect(screen, START_COLOR, (start_pos[0], start_pos[1], cell_size, cell_size))
pygame.draw.rect(screen, GOAL_COLOR, (goal_pos[0], goal_pos[1], cell_size, cell_size))
# BFS Implementation
def bfs(start, goal):
queue = deque([start])
visited = set()
parents = {}
visited.add(start)
while queue:
current = queue.popleft()
# Visualize the current node
pygame.draw.rect(screen, VISITED_COLOR, (current[0], current[1], 20, 20))
pygame.display.flip()
pygame.time.delay(50)
if current == goal:
reconstruct_path(parents, start, goal)
return
neighbors = [
(current[0] + dx, current[1] + dy) for dx, dy in [(0, 20), (0, -20), (20, 0), (-20, 0)]
]
for neighbor in neighbors:
col, row = neighbor[0] // 20, neighbor[1] // 20 # Convert pixel coordinates to maze coordinates
if (0 <= neighbor[0] < 560 and 0 <= neighbor[1] < 560 and
neighbor not in visited and complex_maze[row][col] != 1):
queue.append(neighbor)
visited.add(neighbor)
parents[neighbor] = current
# Function to reconstruct path
def reconstruct_path(parents, start, goal):
current = goal
while current != start:
current = parents[current]
pygame.draw.rect(screen, PATH_COLOR, (current[0], current[1], 20, 20))
pygame.display.flip()
pygame.time.delay(50)
# Main game loop for visualizing the complex maze
while True:
screen.fill(GREY) # Background is grey to represent the walls more clearly
draw_complex_maze()
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
sys.exit()
elif event.type == pygame.KEYDOWN:
if event.key == pygame.K_b: # Press 'b' to start BFS
bfs(start_pos, goal_pos)
pygame.display.flip()