4
\$\begingroup\$

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()

 
\$\endgroup\$
3
\$\begingroup\$

The app is pleasantly functional! I was not able to find any bugs. Improvements are a mix of aesthetic, organizational and best-practices.

You seem not to use these at all:

from pygame.locals import *
from collections import namedtuple

so delete them.

All of the global constants:

screen_width = 10
screen_height = 10
trail_offset = 6
block_size = 30
adjacency_link_thickness = 6
route_thickness = 18

black = (0, 0, 0)
white = (255, 255, 255)
pink = (255,0,255)
blue = (0,255,255)
yellow = (255,255,0)

should be CAPITALIZED.

build_matrix has a long list of issues, including:

  • It's not useful to show this as a lambda; just show this as a regular function
  • you declare it once, then shadow it on a second declaration - that does a completely different operation. Do not do this.
  • i is unused and so should be _

Classes should be title-cased, i.e. Coordinate. You've also shadowed this one for some reason; delete your second, local declaration.

Rather than type(start.x) != int you should be using not isinstance(start.x, int). However, in this specific case, more appropriate is to write start.x is not None. Even better would be to stop reassigning individual x and y members of your coordinates, and instead set start and end to None instead of their members.

Prefer is None and is not None instead of == None and != None.

You do even more shadowing with display/display; perhaps name the variable to window.

You can delete all of your == True.

When running through your series of if on the event key, convert all but the first to elif.

Your start and end icon drawing code needs to be factored out into a routine to reduce repetition.

Your main loop needs to be broken up into multiple functions and all of its code removed from the global namespace. The same applies to pygame.init().

Given the choice between row-major and column-major order, you've chosen the one that makes life more difficult. In the majority of multi-index situations across multiple programming languages, having y as your first (outer, slow-varying) index and x as your second (inner, fast-varying) index makes things more sensible, particularly if you want to print the contents of your matrices to the console. Otherwise, as with your original code, you'll find that things look rotated comparing the screen to the console/debugger.

You have no animation, so event.get is not a good choice - you'll spin forever and eat up your CPU pointlessly. Instead, event.wait.

You should try to use your coordinate class in more situations than you have now.

Make an attempt at proper exception handling, catching near the top level and resetting the grid if a known error occurs.

Example

from contextlib import contextmanager
from typing import List, Tuple, Optional, Set, Iterable

import pygame
from collections import deque


SCREEN_WIDTH = 10
SCREEN_HEIGHT = 10
TRAIL_OFFSET = 6
BLOCK_SIZE = 30
ADJACENCY_LINK_THICKNESS = 6
ROUTE_THICKNESS = 18

WINDOW_SIZE = (BLOCK_SIZE * SCREEN_WIDTH,
               BLOCK_SIZE * SCREEN_HEIGHT)
RECT_DIM = (BLOCK_SIZE, BLOCK_SIZE)

BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
PINK = (255, 0, 255)
BLUE = (0, 255, 255)
YELLOW = (255, 255, 0)


# class for easier reading of tuple cooordinates
class Coordinate:
    def __init__(self, y: int, x: int):
        self.y = y
        self.x = x

    def __str__(self):
        return f'({self.x}, {self.y})'

    def __repr__(self):
        return str(self)

    def astuple(self) -> Tuple[int, int]:
        return self.y, self.x

    def __iter__(self) -> Iterable[int]:
        yield self.y
        yield self.x

    def __eq__(self, other: 'Coordinate') -> bool:
        return other is not None and self.y == other.y and self.x == other.x

    def copy(self) -> 'Coordinate':
        return Coordinate(self.y, self.x)


VisitMatrix = List[List[Optional[int]]]
AdjMatrix = List[List[Set[Tuple[int, int]]]]


def build_adj_matrix(y: int, x: int) -> AdjMatrix:
    return [
        [set() for _ in range(x)]
        for _ in range(y)
    ]


def build_visit_matrix(y: int, x: int) -> VisitMatrix:
    return [[None] * x for _ in range(y)]


class GridError(Exception):
    pass


class Grid:
    def __init__(self):
        self.drawing = True  # used to define whether nodes are drawn, or the cursor can be moved without drawing
        self.square = Coordinate(0, 0)
        self.start: Optional[Coordinate] = None
        self.end: Optional[Coordinate] = None

        self.array = build_adj_matrix(SCREEN_HEIGHT, SCREEN_WIDTH)
        self.array[self.square.y][self.square.x] = {self.square.astuple()}
        self.solution: Optional[List[Coordinate]] = None

    def pathfind(self):
        self.drawing = False
        self.solution = breadth_first_search(self.array, self.start, self.end)

    def place_start(self):
        self.start = self.square.copy()

    def place_end(self):
        self.end = self.square.copy()

    def delete_node(self):
        self.drawing = False
        sy, sx = self.square
        here = self.array[sy][sx]

        for tup in here:  # iterate through all neighbour adjacencies
            ny, nx = tup
            there = self.array[ny][nx]
            if here is not there:
                there.remove(self.square.astuple())  # from the deleted square from the neighbour

        here.clear()  # remove all neighbour information from deleted square

        # remove start marker if start tile was deleted
        if self.square == self.start:
            self.start = None
        # remove end marker if end tile was deleted
        if self.square == self.end:
            self.end = None

    def switch_pen(self):
        self.drawing = not self.drawing

    def left(self):
        self.square.x = max(self.square.x - 1, 0)

    def right(self):
        self.square.x = min(self.square.x + 1, SCREEN_WIDTH - 1)

    def up(self):
        self.square.y = max(self.square.y - 1, 0)

    def down(self):
        self.square.y = min(self.square.y + 1, SCREEN_HEIGHT - 1)

    @contextmanager
    def move(self):
        prev = self.square.copy()
        yield

        if self.drawing:
            # add an adjacency from this location to previous location
            sy, sx = self.square
            self.array[sy][sx] |= {self.square.astuple(), prev.astuple()}

            # add an adjacency from previous location to this location
            py, px = prev
            self.array[py][px] |= {self.square.astuple()}


def breadth_first_search(graph: AdjMatrix, start: Coordinate, end: Coordinate) -> List[Coordinate]:
    """
    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)
    """

    if start is None:
        raise GridError('Start not set')
    if end is None:
        raise GridError('End not set')

    queue = deque([end])  # use queue.popleft() for FIFO queue
    queue2 = []
    pathfind_counter = 0
    visit_matrix = build_visit_matrix(len(graph), len(graph[0]))
    visit_matrix[end.y][end.x] = pathfind_counter

    while len(queue) > 0:
        pathfind_counter += 1
        for i in queue:
            if i == start:  # 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]
                for steps in range(visit_matrix[start.y][start.x], 0, -1):
                    py, px = path[counter]
                    for adjacency in graph[py][px]:
                        ny, nx = adjacency
                        if visit_matrix[ny][nx] == steps - 1:
                            counter += 1
                            path.append(Coordinate(*adjacency))
                            break
                return path

            for ny, nx in graph[i.y][i.x]:
                # if neighbour has not been visited, mark it with number, and append its location to the queue
                if visit_matrix[ny][nx] is None:
                    visit_matrix[ny][nx] = pathfind_counter
                    queue2.append(Coordinate(ny, nx))

        queue = list(queue2)
        queue2.clear()

    raise GridError('No path found')


class Display:
    def __init__(self):
        sysfont = pygame.font.get_default_font()
        self.in_square_font = pygame.font.Font(sysfont, 14)
        self.display = pygame.display.set_mode(WINDOW_SIZE)

    def route_lines(self, grid: Grid):
        # print route lines
        if grid.solution:
            for step in range(len(grid.solution) - 1):
                here = grid.solution[step]
                there = grid.solution[step + 1]
                pygame.draw.line(
                    self.display, YELLOW,
                    (
                        (here.x * BLOCK_SIZE) + (BLOCK_SIZE / 2),
                        (here.y * BLOCK_SIZE) + (BLOCK_SIZE / 2),
                    ),
                    (
                        (there.x * BLOCK_SIZE) + (BLOCK_SIZE / 2),
                        (there.y * BLOCK_SIZE) + (BLOCK_SIZE / 2),
                    ),
                    ROUTE_THICKNESS,
                )
        else:
            if grid.drawing:
                colour = BLACK
            else:
                colour = BLUE
            rectpos = grid.square.x * BLOCK_SIZE, grid.square.y * BLOCK_SIZE
            pygame.draw.rect(self.display, colour, ((rectpos), (RECT_DIM)))

    def draw_squares(self, grid: Grid):
        # print squares and adjacencies
        for row in range(SCREEN_HEIGHT):
            for col in range(SCREEN_WIDTH):
                if (row, col) in grid.array[row][col]:
                    pygame.draw.rect(
                        self.display, PINK,
                        pygame.Rect(
                            (col * BLOCK_SIZE) + TRAIL_OFFSET,
                            (row * BLOCK_SIZE) + TRAIL_OFFSET,
                            BLOCK_SIZE - (TRAIL_OFFSET * 2),
                            BLOCK_SIZE - (TRAIL_OFFSET * 2),
                        )
                    )

                    for neighbour in grid.array[row][col]:
                        ny, nx = neighbour

                        pygame.draw.line(
                            self.display, PINK,
                            (
                                (col * BLOCK_SIZE) + (BLOCK_SIZE / 2),
                                (row * BLOCK_SIZE) + (BLOCK_SIZE / 2),
                            ),
                            (
                                (nx * BLOCK_SIZE) + (BLOCK_SIZE / 2),
                                (ny * BLOCK_SIZE) + (BLOCK_SIZE / 2),
                            ),
                            ADJACENCY_LINK_THICKNESS,
                        )

    def draw_icons(self, letter: str, loc: Optional[Coordinate]):
        # draws start icon
        if loc is not None:
            text = self.in_square_font.render(letter, True, BLACK)
            self.display.blit(text, ((loc.x * BLOCK_SIZE) + BLOCK_SIZE * 0.4,
                                     (loc.y * BLOCK_SIZE) + BLOCK_SIZE * 0.25))

    def show(self, grid: Grid):
        self.display.fill(WHITE)
        self.route_lines(grid)
        self.draw_squares(grid)
        self.draw_icons('s', grid.start)
        self.draw_icons('e', grid.end)
        pygame.display.update()


def session(display: Display):
    grid = Grid()
    display.show(grid)

    keys = {
        pygame.K_SPACE: grid.switch_pen,
        pygame.K_LEFT: grid.left,
        pygame.K_RIGHT: grid.right,
        pygame.K_UP: grid.up,
        pygame.K_DOWN: grid.down,
        pygame.K_s: grid.place_start,
        pygame.K_e: grid.place_end,
        pygame.K_d: grid.delete_node,
        pygame.K_RETURN: grid.pathfind,
    }

    while True:
        event = pygame.event.wait()

        if event.type == pygame.QUIT:
            exit()

        if event.type == pygame.KEYDOWN:
            if event.key == pygame.K_r:
                return  # reset

            handler = keys.get(event.key)
            if handler:
                with grid.move():
                    handler()

                display.show(grid)

        if event.type in {
            pygame.ACTIVEEVENT,
            pygame.VIDEOEXPOSE,
            pygame.VIDEORESIZE,
        }:
            display.show(grid)


def main():
    pygame.init()

    try:
        display = Display()

        while True:
            try:
                session(display)
            except GridError as e:
                print(str(e))
    finally:
        pygame.quit()


if __name__ == '__main__':
    main()
\$\endgroup\$
2
  • 1
    \$\begingroup\$ There is a lot for me to take in! I've never written code in that way before so I am currently wrapping my head around it Thank you for your feedback; I'll incorporate those items into future projects. \$\endgroup\$
    – blib
    May 5 at 9:09
  • \$\begingroup\$ Just wanted to say that I am still reviewing and wrapping my head around your rewrite. I am finding it hard to follow as it is less linear that the original so I have to keep jumping around to follow the code flow though I suppose that is something I have to get used to :) \$\endgroup\$
    – blib
    May 9 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.