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
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})') | |