-
Notifications
You must be signed in to change notification settings - Fork 1
/
main.py
255 lines (191 loc) · 7.34 KB
/
main.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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
import pygame
from collections import deque
# initialize font
pygame.font.init()
# screen size
SCREEN_WIDTH, SCREEN_HEIGHT = 1000, 1000
# screen setup
SCREEN = pygame.display.set_mode((SCREEN_WIDTH, SCREEN_HEIGHT))
pygame.display.set_caption("BFS Visualizer")
# color definitions
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
GREY = (80, 80, 80)
PURPLE = (76, 0, 153)
ORANGE = (255, 128, 0)
BLUE = (0, 0, 255)
LIGHT_BLUE = (0, 255, 255)
MAGENTA = (255, 0, 255)
# setup frame rate
FPS = 60
clock = pygame.time.Clock()
# grid variables
ROW = COL = 25
# font setup
#font = pygame.font.SysFont("Comic Sans")
class Spot:
def __init__(self, x, y, width, height, color):
self.x = x
self.y = y
self.width = width
self.height = height
self.color = color
self.isStart = False
self.isEnd = False
def make_start(self):
self.color = PURPLE
def make_end(self):
self.color = ORANGE
def make_border(self):
self.color = GREY
def make_visited(self):
self.color = BLUE
def make_visiting(self):
self.color = LIGHT_BLUE
def make_path(self):
self.color = MAGENTA
def resetColor(self):
self.color = WHITE
def drawSpot(self, screen, x, y, width, height, color):
pygame.draw.rect(screen, color, (x, y, width, height), width=0) # fill the spot
# bfs implementation
def BFS(queue, row, col, grid):
foundEnd = False
while queue:
if foundEnd:
break
x, y, curPath = queue.popleft()
spot = grid[x][y]
# if spot is not a starting spot, make it visited
if not spot.isStart:
spot.make_visited()
spot.drawSpot(SCREEN, spot.x, spot.y, spot.width, spot.height, spot.color)
for nx, ny in [[x+1,y], [x-1,y], [x,y+1], [x,y-1]]:
if 0<=nx<col and 0<=ny<row and (nx,ny) not in curPath:
newSpot = grid[nx][ny]
if newSpot.color == WHITE: # make it the currently visiting spot
newSpot.make_visiting()
newSpot.drawSpot(SCREEN, newSpot.x, newSpot.y, newSpot.width, newSpot.height, newSpot.color)
queue.append((nx,ny,curPath | {(nx,ny)}))
elif newSpot.isEnd:
for (col, row) in curPath:
curSpot = grid[col][row]
if curSpot.isStart is not True:
curSpot.make_path()
curSpot.drawSpot(SCREEN, curSpot.x, curSpot.y, curSpot.width, curSpot.height, curSpot.color)
foundEnd = True
# function to get clicking position of the mouse
def get_clicked_pos(screenWidth, screenHeight, col, row):
# get coordinates of the mouse
x_pos, y_pos = pygame.mouse.get_pos()
# get the spot width and height
spotWidth = screenWidth / col
spotHeight = screenHeight / row
# calculate the index of row and column for the grid
x = x_pos // spotWidth
y = y_pos // spotHeight
return int(x), int(y)
# function to build the grid in a 2D array
def createGrid(row, col, screenWidth, screenHeight):
grid = []
y_pos = 0
x_pos = 0
spotWidth = screenWidth / col
spotHeight = screenHeight / row
for y in range(row):
temp_list = []
for x in range(col):
spot = Spot(x_pos, y_pos, spotWidth, spotHeight, WHITE)
temp_list.append(spot)
x_pos = x_pos + spotWidth
grid.append(temp_list)
y_pos = y_pos + spotHeight
x_pos = 0
return grid
# function to draw the lines for the grid
def drawLines(screen, screenWidth, screenHeight, row, col):
count_x = 0
count_y = 0
spotWidth = screenWidth / col
spotHeight = screenHeight / row
# draw horizontal lines
for _ in range(row):
pygame.draw.line(screen, BLACK, (0, count_y), (screenWidth, count_y), width=1)
count_y += spotHeight
# draw vertical lines
for _ in range(col):
pygame.draw.line(screen, BLACK, (count_x, 0), (count_x, screenHeight), width=1)
count_x += spotWidth
# function to draw background
def drawBG(screen):
screen.fill(WHITE)
# main game loop
def main():
grid = createGrid(ROW, COL, SCREEN_WIDTH, SCREEN_HEIGHT)
#print(grid)
# main game loop variables
Start = False
End = False
run = True
queue = deque([])
# draw background
drawBG(SCREEN)
while run:
clock.tick(FPS)
# draw lines
drawLines(SCREEN, SCREEN_WIDTH, SCREEN_HEIGHT, ROW, COL)
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
if pygame.mouse.get_pressed(num_buttons=3)[0]: # left click
row, col = get_clicked_pos(SCREEN_WIDTH, SCREEN_HEIGHT, ROW, COL)
spot = grid[col][row]
#print(spot.isStart, spot.isEnd)
if Start == False: # make starting position
spot.make_start()
Start = True
spot.isStart = True
queue.append((col, row, set([(col, row)])))
elif End == False and Start == True and not spot.isStart: # make ending position
spot.make_end()
End = True
spot.isEnd = True
else: # make border
if spot.isStart:
spot.make_start()
elif spot.isEnd: # if the spot is CURRENTLY a start or end position
spot.make_end()
else:
spot.make_border()
spot.drawSpot(SCREEN, spot.x, spot.y, spot.width, spot.height, spot.color)
if pygame.mouse.get_pressed(num_buttons=3)[2]: # right click
row, col = get_clicked_pos(SCREEN_WIDTH, SCREEN_HEIGHT, ROW, COL)
spot = grid[col][row]
if spot.isStart:
Start = False
spot.isStart = False
elif spot.isEnd:
End = False
spot.isEnd = False
spot.resetColor()
spot.drawSpot(SCREEN, spot.x, spot.y, spot.width, spot.height, spot.color)
keys_pressed = pygame.key.get_pressed()
if keys_pressed[pygame.K_SPACE]: # reset the grid
# redraw the background
drawBG(SCREEN)
drawLines(SCREEN, SCREEN_WIDTH, SCREEN_HEIGHT, ROW, COL)
# reset Start and End variables
Start = False
End = False
# reset the queue and target
queue = deque([])
# reset the grid
grid = createGrid(ROW, COL, SCREEN_WIDTH, SCREEN_HEIGHT)
if keys_pressed[pygame.K_c]: # start BFS algorithm
if Start and End: # if we have a start and end position
BFS(queue, ROW, COL, grid)
# reset the deque when the path is found
queue = deque([])
pygame.display.update()
if __name__ == "__main__":
main()