I am trying to make a breadth first search pathfinding tool and this is where I have got to so far:
from collections import deque
import pygame as pg
import sys
# Set the size of the window
width, height = 960, 640
size = (width, height)
GREEN = (0, 200, 0)
RED = (200, 0, 0)
ORANGE = (205, 165, 0)
pg.init()
# Create the game window
win = pg.display.set_mode(size)
pg.display.set_caption('Breadth First Search')
clock = pg.time.Clock()
# Set the number of columns and rows for the grid
cols, rows = int((3 * width / 80)), 32
# Calculate the width and height of each square in the grid
w = int(width * (3 / 4)) // cols
h = height // rows
# Initialize empty lists for the grid, queue, visited squares, and path
grid = []
queue, visited = deque(), []
path = []
# Define a class called Square to represent each square in the grid
class Square:
def __init__(self, i, j):
self.x = i
self.y = j
self.neighbors = []
self.prev = None
self.wall = False
self.visited = False
self.start = False
self.end = False
# Function to draw the square on the window
def show(self, win, col):
if self.wall:
col = (255, 255, 255)
elif self.start:
col = (0, 255, 0) # Green for start node
elif self.end:
col = (255, 0, 0) # Red for end node
pg.draw.rect(win, col, (self.x * w, self.y * h, w - 1, h - 1))
# Function to add neighboring squares to the current square
def add_neighbors(self, grid):
deltas = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dx, dy in deltas:
new_x, new_y = self.x + dx, self.y + dy
if 0 <= new_x < cols and 0 <= new_y < rows:
self.neighbors.append(grid[new_x][new_y])
class Button:
def __init__(self, x, y, width, height, text, font_size, colour, id):
self.rect = pg.Rect(x, y, width, height)
self.text = text
self.font_size = font_size
self.font = pg.font.Font(None, font_size)
self.colour = colour
self.update_hover()
self.is_hovered = False
self.id = id
def update_hover(self):
self.hover_colour = tuple(map(lambda i, j: i + j, self.colour, (50, 50, 50)))
def draw(self, surface):
self.update_hover()
current_colour = self.hover_colour if self.is_hovered else self.colour
pg.draw.rect(surface, current_colour, self.rect)
text_surface = self.font.render(self.text, True, (0, 0, 0))
text_rect = text_surface.get_rect(center=self.rect.center)
surface.blit(text_surface, text_rect)
def check_hover(self, mouse_pos):
self.is_hovered = self.rect.collidepoint(mouse_pos)
def check_click(self, mouse_pos):
return self.rect.collidepoint(mouse_pos)
# Function to handle mouse clicks and update wall states
def click_wall(pos, state):
i = pos[0] // w
j = pos[1] // h
if pos[0] <= width * 0.75:
grid[i][j].wall = state
# Function to place start or end node on click
def place_node(pos, is_start, is_end):
i = pos[0] // w
j = pos[1] // h
# Clear existing start or end nodes
for row in grid:
for square in row:
if is_start:
square.start = False
else:
square.end = False
# Set the new start or end node
if is_start:
grid[i][j].start = True
start_node = grid[i][j]
return i, j
elif is_end:
grid[i][j].end = True
end_node = grid[i][j]
return i, j
def reset():
for i in range(cols):
for j in range(rows):
grid[i][j].wall = False
grid[i][j].visited = False
grid[i][j].prev = None
grid[i][j].start = False
grid[i][j].end = False
# Clear the queue, visited list, and path list
queue.clear()
visited.clear()
path.clear()
# Create the grid of squares
for i in range(cols):
arr = [Square(i, j) for j in range(rows)]
grid.append(arr)
# Add neighbors to each square
for i in range(cols):
for j in range(rows):
grid[i][j].add_neighbors(grid)
# Set the initial start and end points
button_col = (150, 150, 150)
buttons = [
Button((0.75 * width) + (width * 0.025), height * 0.08, width / 5, height / 15, 'START', 40, button_col, 'start'),
Button((0.75 * width) + (width * 0.025), height * 0.08 + height / 15 + 10, width / 5, height / 15, 'BFS', 40,
(200, 0, 0), 'alg')
]
# Main loop for the game
def main():
completed = False
noflag = True
start = False
algorithm = 1
colours = {1: RED, 2: ORANGE, 3: GREEN}
alg_name = {1: 'BFS', 2: 'DFS', 3: 'A STAR'}
start_node = None
end_node = None
# Event handling loop
while True:
for event in pg.event.get():
if event.type == pg.QUIT:
pg.quit()
sys.exit()
if event.type == pg.MOUSEBUTTONDOWN:
if buttons[0].check_click(pg.mouse.get_pos()):
start = True
if buttons[1].check_click(pg.mouse.get_pos()):
if algorithm != 3:
algorithm += 1
else:
algorithm = 1
buttons[1].colour = colours[algorithm]
buttons[1].text = alg_name[algorithm]
print(algorithm)
if event.type == pg.MOUSEBUTTONUP:
if pg.mouse.get_pressed()[0]:
click_wall(pg.mouse.get_pos(), True)
if pg.mouse.get_pressed()[2]:
click_wall(pg.mouse.get_pos(), False)
if event.type == pg.MOUSEMOTION:
for button in buttons:
button.check_hover(pg.mouse.get_pos())
if pg.mouse.get_pressed()[0]:
click_wall(pg.mouse.get_pos(), True)
if event.type == pg.KEYDOWN:
if event.key == pg.K_RETURN:
if start_node and end_node:
start = True
if event.key == pg.K_c:
reset()
start = False
start_node = None
end_node = None
completed = False
# Check for 's' key press to place the start node
if event.key == pg.K_s:
start_node = grid[place_node(pg.mouse.get_pos(), True, False)[0]][place_node(pg.mouse.get_pos(), True, False)[1]]
# Check for 'e' key press to place the end node
if event.key == pg.K_e:
end_node = grid[place_node(pg.mouse.get_pos(), False, True)[0]], [place_node(pg.mouse.get_pos(), False, True)[1]]
# Check if the start flag is set
if start:
queue.append(start_node)
start_node.visited = True
# Check if the queue is not empty
if len(queue) > 0:
current = queue.popleft()
# Check if the current square is the end point
if current.end:
temp = current
while temp.prev:
path.append(temp.prev)
temp = temp.prev
if not completed:
completed = True
print("Done")
elif completed:
continue
# If not at the end, add neighbors to the queue
if not completed:
for i in current.neighbors:
if not i.visited and not i.wall:
i.visited = True
i.prev = current
queue.append(i)
else:
if noflag and not completed:
print("Not completed")
font = pg.font.Font(None, 36)
text = font.render('No Solution', True, (255, 255, 255))
text_rect = (width-100, height-100)
win.blit(text, text_rect)
noflag = False
else:
continue
# Update the window with the current state of the grid
win.fill((200, 200, 200))
for i in range(cols):
for j in range(rows):
square = grid[i][j]
square.show(win, (0, 0, 0))
if square in path:
square.show(win, (0, 95, 115))
elif square.visited:
square.show(win, (202, 103, 2))
if square in queue:
square.show(win, (174, 32, 18))
pg.draw.rect(win, (0, 0, 0), (width * 0.75, 0, width * 0.25, height))
for button in buttons:
button.draw(win)
pg.display.flip()
# Run the main loop
main()
However, I would also like to add other pathfinding algorithms in the future. To be able to do this I need to separate the bfs (the bit after # Check if the start flag is set) from the main loop I think.
Any idea on how to do this?
I have tried taking the existing code and putting it in a function, passing in values but can't seem to get it to work.