Is my breadth-first search function any good? (Python demo included!)

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 🙂


  • 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))
#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
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
                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

        queue = list(queue2)

    return () #return empty list, no path found

def display():
    display = pygame.display.set_mode(wndsize)

    #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)
        rectpos = (square.x*block_size, square.y*block_size)
        if drawing == True:
            rect = pygame.draw.rect(display, black, ((rectpos), (rectdim)))
            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):
                    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))

#main loop
while True:
    for event in pygame.event.get(): #monitor key presses
        if event.type == pygame.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))
            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
                    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
                if (prev.x, prev.y) not in array(square.x)(square.y): #dd an adjacency from this location to previous location