Path finding in 2D map with python

Question

I have been given a maze in the form of a labelmap (the matrix pixel either have value 1 or 0). I cannot cross the pixels with value 0. Given a starting point (x1,y1) and an end point (x2,y2), I have to find all possible paths between the two points using python. Is there a way to do this? Is there an algorithm that allows me to find ALL possible paths and save them?

Thank you!

Answer 1

Following Python code based upon modifying C++ routine for counting paths.

Code

# Check if cell (x, y) is valid or not
def is_valid_cell(x, y, N):
    if x < 0 or y < 0 or x >= N or y >= N:
        return False

    return True

def find_paths_util(maze, source, destination, visited, path, paths):
  """Find paths using Breadth First Search algorith """
  # Done if destination is found
  if source == destination:
    paths.append(path[:])  # append copy of current path
    return

  # mark current cell as visited
  N = len(maze)
  x, y = source
  visited[x][y] = True

  # if current cell is a valid and open cell, 
  if is_valid_cell(x, y, N) and maze[x][y]:
    # Using Breadth First Search on path extension in all direction

    # go right (x, y) --> (x + 1, y)
    if x + 1 < N and (not visited[x + 1][y]):
      path.append((x + 1, y))
      find_paths_util(maze,(x + 1, y), destination, visited, path, paths)
      path.pop()

    # go left (x, y) --> (x - 1, y)
    if x - 1 >= 0 and (not visited[x - 1][y]):
      path.append((x - 1, y))
      find_paths_util(maze, (x - 1, y), destination, visited, path, paths)
      path.pop()

    # go up (x, y) --> (x, y + 1)
    if y + 1 < N and (not visited[x][y + 1]):
      path.append((x, y + 1))
      find_paths_util(maze, (x, y + 1), destination, visited, path, paths)
      path.pop()

    # go down (x, y) --> (x, y - 1)
    if y - 1 >= 0 and (not visited[x][y - 1]):
      path.append((x, y - 1))
      find_paths_util(maze, (x, y - 1), destination, visited, path, paths)
      path.pop()

    # Unmark current cell as visited
  visited[x][y] = False

  return paths

def find_paths(maze, source, destination):
  """ Sets up and searches for paths"""
  N = len(maze) # size of Maze is N x N

  # 2D matrix to keep track of cells involved in current path
  visited = [[False]*N for _ in range(N)]

  path = [source]
  paths = []
  paths = find_paths_util(maze, source, destination, visited, path, paths)

  return paths

Test

# Test Maze
maze = [
  [1, 1, 1, 1],
  [1, 1, 0, 1],
  [0, 1, 0, 1],
  [1, 1, 1, 1]
]
N = len(maze)

# Start point and destination
source = (0, 0)  # top left corner
destination = (N-1, N-1)  # bottom right corner

# Find all paths
paths = find_paths(maze, source, destination)

print("Paths with '->' separator between maze cell locations")
for path in paths:
  print(*path, sep = ' -> ')

Output

Paths with '->' separator between maze cell locations
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)
(0, 0) -> (1, 0) -> (1, 1) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3)
(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)
(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (1, 3) -> (2, 3) -> (3, 3)