I wrote a program that is supposed to be a breadth-first search algorithm, but I'm very new to search algorithm so I don't know if my method is very effective or if there is a simpler way to do this. So I'm asking if there is a way to improve my code.

In this case, I have made the program search for the closest 1 in a 2d list where you can enter the start position and it will then find the shortest path between the start position and the 1. Of course, this can be changed in a variety of ways.

I tried to make the variables and function names as clear as possible, so I don't think I need to explain everything about my code, but that's easy for me to say so please comment if you need clarification.

m = [[1, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 1, 0],
     [0, 0, 1, 0, 0, 0],
     [0, 0, 0, 0, 0, 1],
     [0, 0, 0, 0, 1, 0],
     [1, 0, 1, 0, 0, 0],
     [1, 0, 0, 0, 0, 1],
     [0, 0, 0, 0, 1, 0],
     [1, 0, 1, 0, 0, 0]]

visited = []
queue = []

parent = {}
num = 0

def breadth_first(maze, x, y):
    queue.append((x, y))
    visited.append((x, y))

    while queue:
        pos = queue[0]
        x = pos[0]
        y = pos[1]

        # remove from queue

        # find neighbor
        for dir_x, dir_y in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            newx = x + dir_x
            newy = y + dir_y

            neighbor = (newx, newy)

            # add to queue
            if len(maze[0]) > newx >= 0 and len(maze) > newy >= 0 and neighbor not in visited and neighbor not in queue:
                if m[newy][newx] == 1:
                    parent[neighbor] = pos
                    return neighbor

                parent[neighbor] = pos

closest = breadth_first(m, 0, 0)

path = [closest]

def search(traceback):
    while traceback != (0, 0):
        for key, value in parent.items():
            if traceback == key:
                traceback = value

    return path

def solved(maze, input_path):
    for pos in input_path[1:-1]:
        maze[pos[1]][pos[0]] = '+'

    return maze

print(solved(m, search(closest)))
  • 2
    \$\begingroup\$ Welcome to cod review where we review working code and provide suggestions on how the code can be improved. The title may indicate that you don't know if the code is working or not. Does the code do what it is supposed to do? Can you clarify the question a little bit more. \$\endgroup\$
    – pacmaninbw
    Jan 4, 2020 at 17:02
  • \$\begingroup\$ @pacmaninbw It does what it is supposed to do, but I would like suggestions on improvements \$\endgroup\$
    – IsaacK0
    Jan 4, 2020 at 19:25

1 Answer 1

  • The code uses pos=queue[0] and queue.remove(pos). Instead, you could use pos=queue.pop(0). Be aware that popping from the front isn't really efficient, it's O(n), which is bad for big lists.

  • You could use the fact that you can assign to two variables at once: x, y = queue.pop(0). This removes pos completely, fewer variables are easier to understand.

  • You pass a maze and the start position to the BFS. However, the queue and others are global. That's very bad design. Keep things in as small a scope as possible. You can always return a tuple from a function if a single value is not sufficient, if that was the reason.

  • What are len(maze[0]) and len(maze)? Call those width and height and compute them at the start of the function to answer that question.

  • The if-clause in the loop has too many conditions at once, which is really hard to read. There's nothing wrong with a continue when the computed position was already visited, just to illustrate one check that could be extracted.

  • parent[neighbor] = pos is done at two places. Do that exactly once when you first visit a new place.

  • visited seems to be the list of places that were already visited. The type is a Python list, but a set would be a more suitable datatype for that, unless the order of the elements matters.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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