Хороша ли моя функция поиска в ширину? (Демонстрация Python включена!)

Я изучаю Python и написал функциональный алгоритм поиска в ширину, который хотел сделать как можно более общим. Я написал код, чтобы нарисовать сетку и визуально показать найденный путь.

Мой код расскажет вам о моих способностях кодирования, поэтому имейте это в виду, когда оставляете отзывы; в любом случае я выслушаю то, что вы скажете.

Спасибо 🙂

Инструкции:

• клавиши со стрелками = рисовать узлы на 2-мерной карте
• s ключ = разместить маркер начала (где начинается поиск в ширину)
• клавиша e = разместить конечный маркер
• клавиша пробела = прекратить рисование узлов («поднимает» перо из сетки, чтобы вы могли его перемещать)
• d ключ = удалить узел
• введите ключ = выполнить поиск и возвращает путь от начала до конца
• клавиша r = сбросить после поиска

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

 

Приложение приятно функциональное! Я не смог найти никаких ошибок. Улучшения — это сочетание эстетического, организационного и передового опыта.

Похоже, вы их совсем не используете:

from pygame.locals import *
from collections import namedtuple

так что удали их.

Все глобальные константы:

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)

должны быть ЗАГЛАВНЫМИ.

build_matrix имеет длинный список проблем, в том числе:

• Показывать это как лямбду бесполезно; просто покажите это как обычную функцию
• вы объявляете его один раз, а затем дублируете его во втором объявлении — это выполняет совершенно другую операцию. Не делайте этого.
• i не используется, и так должно быть _

Классы должны быть в заголовке, т. Е. Coordinate. Вы тоже по какой-то причине скрыли это; удалите вторую, локальную декларацию.

Скорее, чем type(start.x) != int ты должен использовать not isinstance(start.x, int). Однако в этом конкретном случае более уместно написать start.x is not None. Еще лучше было бы прекратить переназначать отдельные члены x и y ваших координат и вместо этого установить start а также end к None вместо их членов.

Предпочитать is None а также is not None вместо == None а также != None.

Вы делаете еще больше затенения с помощью display/display; возможно, назовите переменную window.

Вы можете удалить все свои == True.

При прохождении вашей серии if на ключе события преобразовать все, кроме первого, в elif.

Ваш код начального и конечного рисования значков должен быть включен в рутину, чтобы уменьшить повторение.

Ваш основной цикл необходимо разбить на несколько функций и удалить весь его код из глобального пространства имен. То же самое относится и к pygame.init().

Имея возможность выбора между порядком размещения основных строк и столбцов, вы выбрали тот, который усложняет жизнь. В большинстве многоиндексных ситуаций на нескольких языках программирования, имея y в качестве вашего первого (внешнего, медленно меняющегося) индекса и x поскольку ваш второй (внутренний, быстро меняющийся) индекс делает вещи более разумными, особенно если вы хотите вывести содержимое ваших матриц на консоль. В противном случае, как и в случае с исходным кодом, вы обнаружите, что все выглядит повернутым по сравнению с экраном консоли / отладчика.

У вас нет анимации, поэтому event.get не лучший выбор — вы будете крутиться вечно и бессмысленно съедаете свой процессор. Вместо, event.wait.

Вам следует попытаться использовать свой класс координат в большем количестве ситуаций, чем сейчас.

Попытайтесь правильно обработать исключения, перехватить верхний уровень и сбросить сетку в случае возникновения известной ошибки.

Пример

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