Maze solver

README.md

Maze solver

Simple algorithm to calculate the number of steps required to go from a point A to a point B inside a maze. It can handle an unreachable destination.

It's based on BFS

maze.py

class Maze:
    def __init__(self, matrix):
        self.x = 0
        self.y = 0
        self.matrix = matrix
        self.rows = len(matrix)
        self.cols = len(matrix[0])
    
    def getAt(self, x, y):
        if 0 <= x < self.cols and 0 <= y < self.rows:
            return self.matrix[y][x]
        else:
            return -1

    def moveTo(self, x, y):
        if 0 <= x <= self.cols and 0 <= y <= self.rows:
            self.x, self.y = x, y
        else:
            raise ValueError


def solution(maze, src_x, src_y, dest_x, dest_y):
    maze.moveTo(src_x, src_y)

    # Create a queue with the source point
    queue = [ [src_x, src_y] ]

    # Create a matrix, filled with False value
    visited = [
        [ False for i in range(maze.rows) ] for i in range(maze.cols)
    ]

    # Count the moves necessary to go from src(x;y) to dest(x;y)
    moves = 0
    
    while len(queue) > 0:
        # The queue to use at next iteration
        newQueue = []

        # For each point in the queue...
        for [x, y] in queue:
            # Point out of the maze or it is a wall
            if maze.getAt(x, y) != 1:
                continue

            # Already visited
            if visited[x][y]:
                continue

            # We reached destination
            if x == dest_x and y == dest_y:
                return moves

            # Flag the current point as visited
            visited[x][y] = True
        
            # Visit the points near the current one,
            # in the next iteration
            newQueue += [
                [ x + 1, y ],
                [ x - 1, y ],
                [ x, y + 1 ],
                [ x, y - 1 ]
            ]

        queue = newQueue
        moves += 1

    # No solution found
    return -1


# Create a test maze
# 1 = Street
# 0 = Wall
maze = Maze([
        [1,1,1,1,1,0,0,1,1,1],
        [0,1,1,1,1,1,0,1,0,1],
        [0,0,1,0,1,1,1,0,0,1],
        [1,0,1,1,1,0,1,1,0,1],
        [0,0,0,1,0,0,0,1,0,1],
        [1,0,1,1,1,0,0,1,1,0],
        [0,0,0,0,1,0,0,1,0,1],
        [0,1,1,1,1,1,1,1,0,0],
        [1,1,1,1,1,0,0,1,1,1],
        [0,0,1,0,0,0,1,1,1,1]
    ])

# Source and destination points
from_x, from_y = 0, 0
to_x, to_y = 7, 5

# Execute the algorithm
steps_required = solution(maze, from_x, from_y, to_x, to_y)
if steps_required >= 0:
    print(f'{steps_required} steps are required to go from ({from_x};{from_y}) to ({to_x};{to_y})')
else:
    print(f'No way found to go from ({from_x};{from_y}) to ({to_x};{to_y})')