I am learning Python and I wrote a functional breadth-first search algorithm which I wanted to be as general as possible. I wrote some code to draw a grid and visually show the path found.

My code will tell you about my coding abilities so please bear that in mind when providing any feedback; either way I will hear what you have to say.

Thanks ðŸ™‚

Instructions:

- arrow keys = draw nodes in a 2d map
- s key = place start marker (where the breadth first search begins)
- e key = place end marker
- space key = stop drawing nodes (‘lifts’ the pen from the grid so you can move it about)
- d key = delete a node
- enter key = perform search and returns path from start to end
- r key = reset after a search

```
import pygame
from pygame.locals import *
from collections import deque
from collections import namedtuple
###### VARIABLES ######
screen_width = 10
screen_height = 10
trail_offset = 6
block_size = 30
adjacency_link_thickness = 6
route_thickness = 18
################## BODY ###################
build_matrix = lambda x,y : ((()) * x for i in range(y))
pygame.init()
#define colours for pygame
black = (0, 0, 0)
white = (255, 255, 255)
pink = (255,0,255)
blue = (0,255,255)
yellow = (255,255,0)
#define font for start and end markers
sysfont = pygame.font.get_default_font()
in_square_font = pygame.font.Font(sysfont, 14)
#class for easier reading of tuple cooordinates
class coordinate:
def __init__(self, x, y):
self.x = x
self.y = y
#init
square = coordinate(0,0)
start = coordinate(None,None)
end = coordinate(None,None)
prev = coordinate(square.x,square.y)
drawing = True #used to define whether nodes are drawn, or the cursor can be moved without drawing
array = build_matrix(screen_height,screen_width)
array(square.x)(square.y) = ((square.x,square.y))
wndsize = (block_size * screen_width, block_size * screen_height)
rectdim = (block_size, block_size)
solution = ()
def breadthFirstSearch(graph: list, start_location: tuple, goal: tuple) -> list:
"""
This function recieves a 2d matrix of x/y coordinates where each location contains
a list of tuples which contain adjacency information. The function will return
a list of tuples of the route from start_location to goal or an empty list if
no route is found. start_location and goal must be tuples in the format (x,y)
"""
class coordinate: #used for easier reading of tuple coordinates
def __init__(self, x, y):
self.x = x
self.y = y
build_matrix = lambda x,y : ((None) * x for i in range(y))
visit_matrix = build_matrix(len(graph(0)),len(graph))
start = coordinate(start_location(0), start_location(1))
end = coordinate(goal(0), goal(1))
if type(start.x) != int or type(start.y) != int or type(end.x) != int or type(end.y) !=int:
print("Start or End not set")
return ()
queue = deque((end)) #use queue.popleft() for FIFO queue
queue2 = ()
pathfind_counter = 0
visit_matrix(end.x)(end.y) = pathfind_counter
while len(queue) > 0:
pathfind_counter += 1
for i in iter(queue):
if i.x == start.x and i.y == start.y: #if location = the start, the search is complete
counter = 0
#builds the path back from end to start into a list of tuples
path = ((start.x, start.y))
for steps in range(visit_matrix(start.x)(start.y),0,-1):
for adjacency in graph(path(counter)(0))(path(counter)(1)):
neighbour = coordinate(adjacency(0),adjacency(1))
if visit_matrix(neighbour.x)(neighbour.y) == steps-1:
counter += 1
path.append(adjacency)
break
return path
for adj in graph(i.x)(i.y):
neighbour = coordinate(adj(0),adj(1))
if visit_matrix(neighbour.x)(neighbour.y) == None: #if neighbour has not been visited, mark it with number, and append its locationn to the queue
visit_matrix(neighbour.x)(neighbour.y) = pathfind_counter
queue2.append(coordinate(neighbour.x,neighbour.y))
queue = list(queue2)
queue2.clear()
return () #return empty list, no path found
def display():
display = pygame.display.set_mode(wndsize)
display.fill(white)
#print route lines
if len(solution) > 0:
for step in range(len(solution)-1):
here = solution(step)
there = solution(step+1)
line = pygame.draw.line(display, yellow, ((here(0)*block_size)+(block_size/2),(here(1)*block_size)+(block_size/2)), ((there(0) * block_size)+(block_size/2), (there(1) * block_size)+(block_size/2)), route_thickness)
else:
rectpos = (square.x*block_size, square.y*block_size)
if drawing == True:
rect = pygame.draw.rect(display, black, ((rectpos), (rectdim)))
else:
rect = pygame.draw.rect(display, blue, ((rectpos), (rectdim)))
#print squares and adjacencies
for col in range(screen_height):
for row in range(screen_width):
if (row,col) in array(row)(col):
rect = pygame.draw.rect(display, pink, pygame.Rect((row*block_size)+trail_offset,(col*block_size)+trail_offset, block_size-(trail_offset*2), block_size-(trail_offset*2)))
for adjacency in array(row)(col):
neighbour = coordinate(adjacency(0),adjacency(1))
tup = (row,col)
if tup not in array(neighbour.x)(neighbour.y):
array(neighbour.x)(neighbour.y).append(tup)
line = pygame.draw.line(display, pink, ((row*block_size)+(block_size/2),(col*block_size)+(block_size/2)), ((adjacency(0) * block_size)+(block_size/2), (adjacency(1) * block_size)+(block_size/2)), adjacency_link_thickness)
#draws start icon
if start.x != None and start.y != None:
text = in_square_font.render("s", True, black)
display.blit(text, ((start.x*block_size)+block_size*0.4, (start.y*block_size)+block_size*0.25))
#draws end icon
if end.x != None and end.y != None:
text = in_square_font.render("e", True, black)
display.blit(text, ((end.x*block_size)+block_size*0.4, (end.y*block_size)+block_size*0.25))
pygame.display.update()
#main loop
while True:
for event in pygame.event.get(): #monitor key presses
if event.type == pygame.QUIT:
pygame.quit()
quit()
if event.type == pygame.KEYDOWN:
prev.x = square.x
prev.y = square.y
if event.key == pygame.K_RETURN: # start pathfind from S to E
drawing = False
solution = breadthFirstSearch(array,(start.x,start.y),(end.x,end.y))
print(solution)
if event.key == pygame.K_s: #place a start marker
start.x = square.x
start.y = square.y
if event.key == pygame.K_e: #place an end marker, the goal
end.x = square.x
end.y = square.y
if event.key == pygame.K_r: #reset after route find
start.x = None
start.y = None
end.x = None
end.y = None
solution = ()
array = build_matrix(screen_height,screen_width)
if event.key == pygame.K_d: # delete a node
drawing = False
for tup in reversed(array(square.x)(square.y)): #iterate through all neighbour adjacencies
neighbour = coordinate(tup(0),tup(1))
array(neighbour.x)(neighbour.y).remove((square.x,square.y)) #from the deleted square from the neighbour
array(square.x)(square.y).clear() #remove all neighbour information from deleted square
#remove start marker if start tile was deleted
if square.x == start.x and square.y == start.y:
start.x = None
start.y = None
#remove end marker if end tile was deleted
if square.x == end.x and square.y == end.y:
end.x = None
end.y = None
if event.key == pygame.K_SPACE: #Raise 'pen' off the grid
if drawing == True:
print("pen up")
drawing = False
else:
print("pen down")
drawing = True
#defines movement
if event.key == pygame.K_RIGHT and square.x+1 < screen_width:
square.x += 1
if event.key == pygame.K_LEFT and square.x-1 >= 0:
square.x -= 1
if event.key == pygame.K_UP and square.y-1 >= 0:
square.y -= 1
if event.key == pygame.K_DOWN and square.y+1 < screen_height:
square.y += 1
if drawing == True:
if (square.x,square.y) not in array(square.x)(square.y): #if current location does not contain its own coordinates (suggesting it has never been visited) add them
array(square.x)(square.y) = ((square.x,square.y))
if (square.x,square.y) not in array(prev.x)(prev.y): #add an adjacency from previous location to this location
array(prev.x)(prev.y).append((square.x,square.y))
if (prev.x, prev.y) not in array(square.x)(square.y): #dd an adjacency from this location to previous location
array(square.x)(square.y).append((prev.x,prev.y))
display()
```