Maze Solver with A* Algorithm¶

Figure 1: Maze Solver A* Source: Wikipedia

A* Algorithm give always an optimal solution based on a bread-first-search and queues. It is an extension over the previous Lee's Algorithms and Dijkstra's Algorithms, and uses heuristics to guide its search.

A* Algorithm has the in the worst case the same time complexity as Dijkstra which is depending on the queue implementation, where $|E|$ = number of edges and $|V|$ number of nodes.

Fibonacci heap: $O(|E| + |V| log |V|)$
binary heap: $O((|E| + |V|) log |V|)$
unsorted array: $O(|V|^2)$

But A* is based on heuristics which helps to find a more optimal solution much quicker.

Figure 2: A* Algorithms Demo Source: Wikipedia

Terminology¶

Node or State - All uniquely identifiable elements where it's possible to stop
Transition - Moving between states
Source Node - Location to start the search
Destination Node - Location to be found
Search Space - A collection of nodes
Cost - Numerical value representing the cost for moving vom one node to another

Node Values¶

One important aspect of A* is the cost calculations. $f(n) = g(n)+h(n)$. Every time a new node is created these values are calculated:

$f(n)$ = Total cost of a node
$g(n)$ = distance between current node and start node
$h(n)$ = heuristic, estimated distance between current node and the end node

Fibonacci Heap¶

With Heap Collection method such as Binomial or Fibonacci Heap to collect the trees the algorithm can be more time efficient.

Fibonacci Head is a datastructure for priority queue operation. Fibonacci Heap maintains a pointer to minimum value (which is root of a tree). All tree roots are connected using circular doubly linked list, so all of them can be accessed using single ‘min’ pointer.

Figure 3: Fibonacci Heap Source: Wikipedia

Solution¶

Flowchart of the solution

Figure 4: A* Flowchart Source: Wikipedia

Pseudo code¶

// A* (star) Pathfinding
// Initialize both open and closed list
let the openList equal empty list of nodes
let the closedList equal empty list of nodes
// Add the start node
put the startNode on the openList (leave it's f at zero)
// Loop until you find the end
while the openList is not empty
    // Get the current node
    let the currentNode equal the node with the least f value
    remove the currentNode from the openList
    add the currentNode to the closedList
    // Found the goal
    if currentNode is the goal
        Congrat! You've found the end! Backtrack to get path
    // Generate children
    let the children of the currentNode equal the adjacent nodes
    
    for each child in the children
        // Child is on the closedList
        if child is in the closedList
            continue to beginning of for loop
        // Create the f, g, and h values
        child.g = currentNode.g + distance between child and current
        child.h = distance from child to end
        child.f = child.g + child.h
        // Child is already in openList
        if child.position is in the openList's nodes positions
            if the child.g is higher than the openList node's g
                continue to beginning of for loop
        // Add the child to the openList
        add the child to the openList

Imports¶

In [105]:

Copied!





import heapq
from IPython.display import clear_output
# generate maze from other notebook
# Run 008-maze-generation-kruskal notebook
%run 008-maze-generation-kruskal.ipynb
import heapq
from IPython.display import clear_output
# generate maze from other notebook
# Run 008-maze-generation-kruskal notebook
%run 008-maze-generation-kruskal.ipynb

Generated array maze=
[[0 0 0 ... 0 0 0]
 [0 0 1 ... 0 0 0]
 [0 1 1 ... 1 0 0]
 ...
 [0 1 1 ... 1 0 0]
 [0 0 1 ... 1 0 0]
 [0 0 0 ... 0 0 0]]

Loading BokehJS ...

Algorithm¶

In [106]:

Copied!





class Node:
  def __init__(self, g: int = 0, h: int = 0, f: int = float("inf"), pos: list = []):
    """Representation of a cell, vertex or node

    Args:
        g (int): distance between node and source node
        h (int): heuristic, estimated distance between node and destination
        f (int): total cost of the node
        pos (list): [y,x] position of the node in the maze
    """
    self.g = g
    self.h = h
    self.f = f
    self.pos = pos

  def __eq__(self, other):
    return (self.f == other.f)

  def __ne__(self, other):
    return not (self.f == other.f)

  def __lt__(self, other):
    return (self.f < other.f)

  def __gt__(self, other):
    return (self.f > other.f)

  def __le__(self, other):
    return (self.f <= other.f)

  def __ge__(self, other):
    return (self.f >= other.f)

  def printNode(self, prefix: str = "", postfix: str = ""):
    print("{}Node: [{},{}], g:{}, h:{} f:{}{}".format(prefix, self.pos[0], self.pos[1], self.g, self.h, self.f, postfix))


def aStar(maze, src: list, dest: list):
  """Function to find the shortest path between source cell and destination cell with help of the A* algorithm

  Args:
      maze (list): 2 dimensional maze matrix
      src (list): y-x coordinates of source cell
      dest (list): y-x coordinates of destination cell

  Returns:
      list: [distance of the solution, list of the maze solution path]
  """
  # These arrays show the 4 possible movement from a cell
  _rowNum = [-1, 0, 0, 1]
  _colNum = [0, -1, 1, 0]

  # store infinity
  _infinity = float("inf")

  # Checking if source and destination cell have value 1
  if maze[src[0]][src[1]]!=1 or maze[dest[0]][dest[1]]!=1:
    return None

  # get maze size
  _maze_rows = len(maze)
  _maze_cols = len(maze[0])

  # list of visited cells
  _visited = [[False for i in range(_maze_cols)]
             for j in range(_maze_rows)]
  # list of distances fill with infinity
  _f = [[_infinity for i in range(_maze_cols)]
               for j in range(_maze_rows)]

  # Create a queue
  _unvisited = []

  # create source node and mark as visited
  _visited[src[0]][src[1]] = True
  # manhatten distance to dst
  _h = abs(dest[0] - src[0]) + abs(dest[1] - src[1])
  # zero distance to source
  _g = 0
  # zero cost
  _f[src[0]][src[1]] = 0
  _node = Node(_g, _h, _f[src[0]][src[1]], src)

  # enqueue src node
  heapq.heappush(_unvisited, _node)
  #_node.printNode("Push ")

  # Perform A* starting from source cell
  while _unvisited:
    # shortest unexplored path
    _cur_node = heapq.heappop(_unvisited)
    #_cur_node.printNode("Pop ")

    # add node to visited cells
    _visited[_cur_node.pos[0]][_cur_node.pos[1]] = True

    # If we have reached the destination cell, return the final distance
    # return f distances in order to backtrack
    if _cur_node.pos[0] == dest[0] and _cur_node.pos[1] == dest[1]:
      return _f

    # Extend path to all adjacent cells
    for i in range(4):
      _adj_node_pos = (_cur_node.pos[0] + _rowNum[i], _cur_node.pos[1] + _colNum[i])

      # if not visited yet and within maze and a cell (1))
      if (not _visited[_adj_node_pos[0]][_adj_node_pos[1]] and
         ((_adj_node_pos[0] >= 0) and (_adj_node_pos[0] < _maze_rows) and (_adj_node_pos[1] >= 0) and (_adj_node_pos[1] < _maze_cols)) and
         (maze[_adj_node_pos[0]][_adj_node_pos[1]] == 1)):
        # calculate f, g and h values
        # calculate manhattan distance from cur_node to adj_node. Always one because it is a maze
        _d = abs(_cur_node.pos[0] - _adj_node_pos[0]) + abs(_cur_node.pos[1] - _adj_node_pos[1])

        # new distance
        _g = _cur_node.g + _d
        # manhattan distance from adj_node to dest
        _h = abs(dest[0] - _adj_node_pos[0]) + abs(dest[1] - _adj_node_pos[1])
        _f[_adj_node_pos[0]][_adj_node_pos[1]] = _g+_h
        _adj_node = Node(_g, _h, _f[_adj_node_pos[0]][_adj_node_pos[1]], _adj_node_pos)

        # see if node pos already existing in list (this should be improved)
        _in_list = False
        for node in _unvisited:
          if node.pos == _adj_node.pos:
            if _adj_node.g > node.g:
              _in_list = True
        if not _in_list:
          heapq.heappush(_unvisited, _adj_node)
          #_adj_node.printNode("Push ")

  # Return none if destination cannot be reached
  return None


def getSolution(src: list, dst: list,  f: list):
  """Get shortest solution path

  Args:
      src (list): y,x coordinates of the startpoint
      f (list): array of costs for each cell to arrive at the destination

  Returns:
      list: optimum solution path

  """
  _solution_path = []
  # These arrays show the 4 possible movement from a cell
  _rowNum = [-1, 0, 0, 1]
  _colNum = [0, -1, 1, 0]

  # get maze size
  _maze_rows = len(f)
  _maze_cols = len(f[0])
  _maze_size = _maze_cols*_maze_rows

  _cur_pos = dst
  _prev_pos = dst
  # get maximum distance
  _arrived = False
  j = 0
  while(not _arrived and j <= _maze_size):
    _cost = float("inf")
    # for all 4 adjacent cells select the one with the smallest cost
    for i in range(len(_rowNum)):
      _next_pos = [_cur_pos[0] + _rowNum[i], _cur_pos[1] + _colNum[i]]
      # check in on the board
      if (_next_pos[0] >= 0) and (_next_pos[0] < _maze_rows) and (_next_pos[1] >= 0) and (_next_pos[1] < _maze_cols):
        # Check if not the previous cell
        if not (_prev_pos == _next_pos):
          if f[_next_pos[0]][_next_pos[1]] < _cost:
            _temp_pos = _next_pos
            _cost = f[_next_pos[0]][_next_pos[1]]
    if _cost != float("inf"):
      _solution_path.append(_temp_pos)
      _prev_pos = _cur_pos
      _cur_pos = _temp_pos

    if _cur_pos == src:
      return _solution_path
    j += 1


def drawSolution(maze: list, src: list, dst: list, solutionpath: list):
  """draw the start- and endpoint as well as the solution
     0 = wall
     1 = cell
     2 = path
     3 = start- endpoint

  Args:
      maze (list): 2 dimensional array of the maze
      src (list): y,x coordinates of the startpoint
      dst (list): y,x coordinates of the endpoint
      solutionpath (list): array of points of the solution

  Returns:
      list: 2d array of the maze including solution

  """
  maze_tmp = maze.copy()
  # draw solution
  for point in solutionpath:
    maze_tmp[point[0]][point[1]] = 2
  # draw start and endpoint
  maze_tmp[src[0]][src[1]] = 3
  maze_tmp[dst[0]][dst[1]] = 3
  return maze_tmp

def findEmptyCell(maze: list, corner: int):
  """find empty cell in cell starting at a corner

  Args:
      maze (list): maze to search through
      corner (int): where to start (0=bottomleft, 1=topleft, 2=topright, 3=bottomright)

  Returns:
      list: row,col coordinates of the first empty cell
  """
  maze_rows = len(maze)
  maze_cols = len(maze[0])

  if corner == 0:
    range_rows = range(0, maze_rows-1, 1)
    range_cols = range(0, maze_cols-1, 1)
  elif corner == 1:
    range_rows = range(0, maze_rows-1, 1)
    range_cols = range(maze_cols-1, 0, -1)
  elif corner == 2:
    range_rows = range(maze_rows-1, 0, -1)
    range_cols = range(maze_cols-1, 0, -1)
  else:
    range_rows = range(maze_rows-1, 0, -1)
    range_cols = range(0, maze_cols-1, 1)

  # find empty cell
  for row in range_rows:
    for col in range_cols:
      if maze[row][col] == 1:  #  valid cell found
        return  [row, col]
class Node:
  def __init__(self, g: int = 0, h: int = 0, f: int = float("inf"), pos: list = []):
    """Representation of a cell, vertex or node

    Args:
        g (int): distance between node and source node
        h (int): heuristic, estimated distance between node and destination
        f (int): total cost of the node
        pos (list): [y,x] position of the node in the maze
    """
    self.g = g
    self.h = h
    self.f = f
    self.pos = pos

  def __eq__(self, other):
    return (self.f == other.f)

  def __ne__(self, other):
    return not (self.f == other.f)

  def __lt__(self, other):
    return (self.f < other.f)

  def __gt__(self, other):
    return (self.f > other.f)

  def __le__(self, other):
    return (self.f <= other.f)

  def __ge__(self, other):
    return (self.f >= other.f)

  def printNode(self, prefix: str = "", postfix: str = ""):
    print("{}Node: [{},{}], g:{}, h:{} f:{}{}".format(prefix, self.pos[0], self.pos[1], self.g, self.h, self.f, postfix))


def aStar(maze, src: list, dest: list):
  """Function to find the shortest path between source cell and destination cell with help of the A* algorithm

  Args:
      maze (list): 2 dimensional maze matrix
      src (list): y-x coordinates of source cell
      dest (list): y-x coordinates of destination cell

  Returns:
      list: [distance of the solution, list of the maze solution path]
  """
  # These arrays show the 4 possible movement from a cell
  _rowNum = [-1, 0, 0, 1]
  _colNum = [0, -1, 1, 0]

  # store infinity
  _infinity = float("inf")

  # Checking if source and destination cell have value 1
  if maze[src[0]][src[1]]!=1 or maze[dest[0]][dest[1]]!=1:
    return None

  # get maze size
  _maze_rows = len(maze)
  _maze_cols = len(maze[0])

  # list of visited cells
  _visited = [[False for i in range(_maze_cols)]
             for j in range(_maze_rows)]
  # list of distances fill with infinity
  _f = [[_infinity for i in range(_maze_cols)]
               for j in range(_maze_rows)]

  # Create a queue
  _unvisited = []

  # create source node and mark as visited
  _visited[src[0]][src[1]] = True
  # manhatten distance to dst
  _h = abs(dest[0] - src[0]) + abs(dest[1] - src[1])
  # zero distance to source
  _g = 0
  # zero cost
  _f[src[0]][src[1]] = 0
  _node = Node(_g, _h, _f[src[0]][src[1]], src)

  # enqueue src node
  heapq.heappush(_unvisited, _node)
  #_node.printNode("Push ")

  # Perform A* starting from source cell
  while _unvisited:
    # shortest unexplored path
    _cur_node = heapq.heappop(_unvisited)
    #_cur_node.printNode("Pop ")

    # add node to visited cells
    _visited[_cur_node.pos[0]][_cur_node.pos[1]] = True

    # If we have reached the destination cell, return the final distance
    # return f distances in order to backtrack
    if _cur_node.pos[0] == dest[0] and _cur_node.pos[1] == dest[1]:
      return _f

    # Extend path to all adjacent cells
    for i in range(4):
      _adj_node_pos = (_cur_node.pos[0] + _rowNum[i], _cur_node.pos[1] + _colNum[i])

      # if not visited yet and within maze and a cell (1))
      if (not _visited[_adj_node_pos[0]][_adj_node_pos[1]] and
         ((_adj_node_pos[0] >= 0) and (_adj_node_pos[0] < _maze_rows) and (_adj_node_pos[1] >= 0) and (_adj_node_pos[1] < _maze_cols)) and
         (maze[_adj_node_pos[0]][_adj_node_pos[1]] == 1)):
        # calculate f, g and h values
        # calculate manhattan distance from cur_node to adj_node. Always one because it is a maze
        _d = abs(_cur_node.pos[0] - _adj_node_pos[0]) + abs(_cur_node.pos[1] - _adj_node_pos[1])

        # new distance
        _g = _cur_node.g + _d
        # manhattan distance from adj_node to dest
        _h = abs(dest[0] - _adj_node_pos[0]) + abs(dest[1] - _adj_node_pos[1])
        _f[_adj_node_pos[0]][_adj_node_pos[1]] = _g+_h
        _adj_node = Node(_g, _h, _f[_adj_node_pos[0]][_adj_node_pos[1]], _adj_node_pos)

        # see if node pos already existing in list (this should be improved)
        _in_list = False
        for node in _unvisited:
          if node.pos == _adj_node.pos:
            if _adj_node.g > node.g:
              _in_list = True
        if not _in_list:
          heapq.heappush(_unvisited, _adj_node)
          #_adj_node.printNode("Push ")

  # Return none if destination cannot be reached
  return None


def getSolution(src: list, dst: list,  f: list):
  """Get shortest solution path

  Args:
      src (list): y,x coordinates of the startpoint
      f (list): array of costs for each cell to arrive at the destination

  Returns:
      list: optimum solution path

  """
  _solution_path = []
  # These arrays show the 4 possible movement from a cell
  _rowNum = [-1, 0, 0, 1]
  _colNum = [0, -1, 1, 0]

  # get maze size
  _maze_rows = len(f)
  _maze_cols = len(f[0])
  _maze_size = _maze_cols*_maze_rows

  _cur_pos = dst
  _prev_pos = dst
  # get maximum distance
  _arrived = False
  j = 0
  while(not _arrived and j <= _maze_size):
    _cost = float("inf")
    # for all 4 adjacent cells select the one with the smallest cost
    for i in range(len(_rowNum)):
      _next_pos = [_cur_pos[0] + _rowNum[i], _cur_pos[1] + _colNum[i]]
      # check in on the board
      if (_next_pos[0] >= 0) and (_next_pos[0] < _maze_rows) and (_next_pos[1] >= 0) and (_next_pos[1] < _maze_cols):
        # Check if not the previous cell
        if not (_prev_pos == _next_pos):
          if f[_next_pos[0]][_next_pos[1]] < _cost:
            _temp_pos = _next_pos
            _cost = f[_next_pos[0]][_next_pos[1]]
    if _cost != float("inf"):
      _solution_path.append(_temp_pos)
      _prev_pos = _cur_pos
      _cur_pos = _temp_pos

    if _cur_pos == src:
      return _solution_path
    j += 1


def drawSolution(maze: list, src: list, dst: list, solutionpath: list):
  """draw the start- and endpoint as well as the solution
     0 = wall
     1 = cell
     2 = path
     3 = start- endpoint

  Args:
      maze (list): 2 dimensional array of the maze
      src (list): y,x coordinates of the startpoint
      dst (list): y,x coordinates of the endpoint
      solutionpath (list): array of points of the solution

  Returns:
      list: 2d array of the maze including solution

  """
  maze_tmp = maze.copy()
  # draw solution
  for point in solutionpath:
    maze_tmp[point[0]][point[1]] = 2
  # draw start and endpoint
  maze_tmp[src[0]][src[1]] = 3
  maze_tmp[dst[0]][dst[1]] = 3
  return maze_tmp

def findEmptyCell(maze: list, corner: int):
  """find empty cell in cell starting at a corner

  Args:
      maze (list): maze to search through
      corner (int): where to start (0=bottomleft, 1=topleft, 2=topright, 3=bottomright)

  Returns:
      list: row,col coordinates of the first empty cell
  """
  maze_rows = len(maze)
  maze_cols = len(maze[0])

  if corner == 0:
    range_rows = range(0, maze_rows-1, 1)
    range_cols = range(0, maze_cols-1, 1)
  elif corner == 1:
    range_rows = range(0, maze_rows-1, 1)
    range_cols = range(maze_cols-1, 0, -1)
  elif corner == 2:
    range_rows = range(maze_rows-1, 0, -1)
    range_cols = range(maze_cols-1, 0, -1)
  else:
    range_rows = range(maze_rows-1, 0, -1)
    range_cols = range(0, maze_cols-1, 1)

  # find empty cell
  for row in range_rows:
    for col in range_cols:
      if maze[row][col] == 1:  #  valid cell found
        return  [row, col]

Test¶

In [107]:

Copied!





no_solution = True
while no_solution:

  # generate maze with function from 008 notebook
  size = {'x': 80,'y': 40}
  maze = generateMaze(size['x'], size['y'])
  maze = createBorder(maze)

  # get maze size
  maze_rows = len(maze)
  maze_cols = len(maze[0])

  # find empty cell in topleft corner
  src = findEmptyCell(maze, 0)

  # find empty cell in bottomright corner
  dst = findEmptyCell(maze, 2)

  print("Maze Size           : {}x{}".format(maze_cols, maze_rows))
  print("Source Cell is      : {}".format(src))
  print("Destination Cell is : {}".format(dst))

  # execute A* algorithm
  f = aStar(maze, src, dst)

  # draw points and solution
  if f:
    no_solution = False
    path = getSolution(src, dst, f)
    print("Length of the Shortest Path is", len(path))
    maze_solved = drawSolution(maze, src, dst, path)
  else:
    #no_solution = False##
    print("No solution exists")
    clear_output(wait=True)
no_solution = True
while no_solution:

  # generate maze with function from 008 notebook
  size = {'x': 80,'y': 40}
  maze = generateMaze(size['x'], size['y'])
  maze = createBorder(maze)

  # get maze size
  maze_rows = len(maze)
  maze_cols = len(maze[0])

  # find empty cell in topleft corner
  src = findEmptyCell(maze, 0)

  # find empty cell in bottomright corner
  dst = findEmptyCell(maze, 2)

  print("Maze Size           : {}x{}".format(maze_cols, maze_rows))
  print("Source Cell is      : {}".format(src))
  print("Destination Cell is : {}".format(dst))

  # execute A* algorithm
  f = aStar(maze, src, dst)

  # draw points and solution
  if f:
    no_solution = False
    path = getSolution(src, dst, f)
    print("Length of the Shortest Path is", len(path))
    maze_solved = drawSolution(maze, src, dst, path)
  else:
    #no_solution = False##
    print("No solution exists")
    clear_output(wait=True)

Maze Size           : 81x41
Source Cell is      : [1, 10]
Destination Cell is : [39, 76]
Length of the Shortest Path is 144

In [108]:

Copied!

output_notebook()

plot = figure(x_range=(0, 1), y_range=(0, 1),
              plot_height=maze_rows*10, plot_width=maze_cols*10)
plot.axis.visible = False
plot.outline_line_color = '#ffffff'

plot.image([maze_solved], x=0, y=0, dw=1, dh=1, palette=['#228b22', '#ffffff', '#add8e6', '#ff7f7f'])

show(plot)
output_notebook()

plot = figure(x_range=(0, 1), y_range=(0, 1),
              plot_height=maze_rows*10, plot_width=maze_cols*10)
plot.axis.visible = False
plot.outline_line_color = '#ffffff'

plot.image([maze_solved], x=0, y=0, dw=1, dh=1, palette=['#228b22', '#ffffff', '#add8e6', '#ff7f7f'])

show(plot)

Loading BokehJS ...