Path finding solution for a maze whose state changes during the solve

Question

This is not a traditional maze where you find the shortest path (like the gif on the left). In order to solve it, you need to visit every available node before reaching the end, where once a node is visited it turns into a wall (like the gif on the right).

Incorrect maze gif Correct maze gif

My current solution works quickly for smaller mazes or ones with a lot of walls, such as this, usually finding a path within a couple seconds. But it takes a lot longer as the size of the maze increases or has more open space, such as this (nearly 5 minutes to find a path). Ideally I would like solve mazes up to a 15x20 size in ~30 seconds.

Here is an overview:

1. Input the maze (2D list of Tile objects), start node , and end node to the MazeSolver class.

2. A neighboring node is chosen (up, right, down, left).

3. If that node is_open(), then check if it is_safe() to visit. A node is safe if visiting it will not obstruct our path to any other open node in the maze. This involves an A* search from that node to every other open node, to quickly check if the path exists (every node returned in the path can be skipped for its own search to reduce the number of A* searches).

4. If it is_safe(), visit the node and link their next and prev attributes.

5. If the node is not open or not safe, add it to the closed list.

6. If all 4 neighbors are in closed, backtrack to the previous node.

7. Repeat 2-6 until end is reached, return the path if found.

At this point I am unsure how to improve the algorithm. I am aware of techniques like cython to speed up the execution time of your code, but my real goal is to add some logic to make the solution smarter and faster. (Although feel free to recommend these techniques as well, I don't imagine multiprocessing could work here?).

I believe adding some logic as to how a neighbor is chosen may be the next step. Currently, a direction is picked from the list MazeSolver.map, and is used until the neighbor in that direction is not open. Then the next one in the list is chosen, and it just cycles through in order. So there is no intelligent decision making for choosing the neighbor.

Many path finding algorithms assign weights and scores, but how can I tell if one neighbor is more important now than another? The start and end positions can be anywhere in the maze, and you have to visit every node, so the distance to the end node seems insignificant. Or is there a way to predict that a node is not safe without having to do an A* search with each other node? Perhaps separating the maze into smaller chunks and then combining them afterwards would make a difference? All suggestions are welcome, even an entirely new method of solving.

Here is the code.

class Tile:
 def __init__(self, row, column):
 self.position = (row, column)
 self.mode = 1 # 1 = open, 0 = closed (wall)
 self.next = self.prev = None
 self.closed = []
 def __add__(self, other):
 return (self.position[0] + other[0], self.position[1] + other[1])
class MazeSolver:
 def __init__(self, maze, start, end):
 self.maze = maze
 self.h, self.w = len(maze) - 1, len(maze[0]) - 1
 self.start = maze[start[0]][start[1]]
 self.end = maze[end[0]][end[1]]
 self.current = self.start
 self.map = [(-1, 0), (0, 1), (1, 0), (0, -1)] # Up, right, down, left
 def solve(self):
 i = 0
 while self.current != self.end:
 node = self.current + self.map[i]
 if self.is_open(node):
 if self.is_safe(node):
 # Link two nodes like a Linked List 
 self.current.next = self.maze[node[0]][node[1]]
 self.current.next.prev = self.current
 self.current.mode -= 1
 self.current = self.current.next
 continue
 else:
 self.current.closed.append(node)
 else:
 i += 1 if i < 3 else -3 # Cycle through indexes in self.map
 if len(self.current.closed) == 4:
 if self.current == self.start:
 # No where to go from starting node, no path exists.
 return 0
 self.current.closed = []
 self.current = self.current.prev
 self.current.mode += 1
 self.current.closed.append(self.current.next.position)
 return self.get_path()
 def is_open(self, node):
 '''Check if node is open (mode = 1)'''
 if node in self.current.closed:
 return 0
 elif any([node[0]>self.h, node[0]<0, node[1]>self.w, node[1]<0]):
 # Node is out of bounds
 self.current.closed.append(node)
 return 0
 elif self.maze[node[0]][node[1]].mode == 0:
 self.current.closed.append(node)
 return self.maze[node[0]][node[1]].mode
 def is_safe(self, node):
 '''Check if path is obstructed when node is visitied'''
 nodes = [t.position for row in self.maze for t in row if t.mode > 0]
 nodes.remove(self.current.position)
 # Sorting positions by greatest manhattan distance (which reduces calls to astar)
 # decreases solve time for the small maze but increases it for the large maze.
 # Thus at some point the cost of sorting outweighs the benefit of fewer A* searches.
 # So I have left it commented out:
 #nodes.sort(reverse=True, key=lambda x: abs(node[0] - x[0]) + abs(node[1] - x[1]))
 board = [[tile.mode for tile in row] for row in self.maze]
 board[self.current.position[0]][self.current.position[1]] = 0
 checked = []
 for goal in nodes:
 if goal in checked:
 continue
 sub_maze = self.astar(board, node, goal)
 if not sub_maze:
 return False
 else:
 checked = list(set(checked + sub_maze))
 return True
 def astar(self, maze, start, end):
 '''An implementation of the A* search algorithm'''
 start_node = Node(None, start)
 end_node = Node(None, end)
 open_list = [start_node]
 closed_list = []
 while len(open_list) > 0:
 current_node = open_list[0]
 current_index = 0
 for index, item in enumerate(open_list):
 if item.f < current_node.f:
 current_node = item
 current_index = index
 open_list.pop(current_index)
 closed_list.append(current_node)
 if current_node == end_node:
 path = []
 current = current_node
 while current is not None:
 path.append(current.position)
 current = current.parent
 return path
 children = []
 for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
 node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
 if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[0]) -1) or node_position[1] < 0:
 continue
 if maze[node_position[0]][node_position[1]] == 0:
 continue
 new_node = Node(current_node, node_position)
 children.append(new_node)
 for child in children:
 if child in closed_list:
 continue
 child.g = current_node.g + 1
 child.h = ((child.position[0] - end_node.position[0])**2) + ((child.position[1] - end_node.position[1])**2)
 child.f = child.g + child.h
 if child in open_list:
 if child.g > open_list[open_list.index(child)].g:
 continue
 open_list.append(child)
 return []
 def get_path(self):
 path = []
 pointer = self.start
 while pointer is not None:
 path.append(pointer.position)
 pointer = pointer.next
 return path
class Node:
 '''Only used by the MazeSolver.astar() function'''
 def __init__(self, parent=None, position=None):
 self.parent = parent
 self.position = position
 self.g = self.h = self.f = 0
 def __eq__(self, other):
 return self.position == other.position

If you would like to run the mazes from the pictures I linked above (Small, Large):

import time
def small_maze():
 maze = [[Tile(r, c) for c in range(11)] for r in range(4)]
 maze[1][1].mode = 0
 for i in range(11):
 if i not in [3, 8]:
 maze[3][i].mode = 0
 return maze
def large_maze():
 maze = [[Tile(r, c) for c in range(15)] for r in range(10)]
 for i in range(5, 8):
 maze[4][i].mode = 0
 maze[5][5].mode = maze[5][7].mode = maze[6][5].mode = 0
 return maze
C = MazeSolver(small_maze(), (3, 8), (3, 3)) #(large_maze(), (2, 2), (5, 6))
t = time.time()
path = C.solve()
print(round(time.time() - t, 2), f'seconds\n\n{path}')
# The end node should always have some walls around it to avoid
# the need to check if it was reached prematurely.

---

Edit:

Thanks to trentcl for pointing out that this problem is a Hamiltonian path. I have rewritten the code to represent the maze as an adjacency matrix, and implemented the Hamiltonian path algorithm based on this tutorial. The performance on the small maze was identical to my original method, but was much slower on the large maze (I interrupted the execution after 15 minutes).

class MazeSolver:
 def __init__(self, maze, start):
 graph = self.to_graph(maze)
 self.n = len(graph)
 vertices = list(graph.keys())
 self.key_map = {vertices[i]: i for i in range(self.n)}
 self.graph = self.to_matrix(graph)
 self.start = self.key_map[start]
 def to_graph(self, maze):
 '''Convert maze to graph with the structure {position: [neighbor positions]}'''
 graph = {(r, c): [] for c in range(len(maze[0])) for r in range(len(maze)) if maze[r][c]}
 for r, c in graph.keys():
 for pos in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
 try:
 if maze[pos[0]][pos[1]] and pos[0] >= 0 and pos[1] >= 0:
 graph[(r, c)].append(pos)
 except IndexError:
 pass
 return graph
 def to_matrix(self, graph):
 '''Convert graph to adjacency matrix.
 matrix[i][j] == 1 indicates there is an edge from i to j'''
 edges = [(vertex, neighbor) for vertex in graph for neighbor in graph[vertex]]
 edge_numbers = [(self.key_map[edge[0]], self.key_map[edge[1]]) for edge in edges]
 matrix = [[0] * self.n for i in range(self.n)]
 for edge in edge_numbers:
 matrix[edge[0]][edge[1]] = 1
 return matrix
 def solve(self):
 path = [-1] * self.n
 path[0] = self.start
 if self.hamiltonian_path(path, 1):
 index_map = {v: k for k, v in self.key_map.items()}
 return [index_map[vertex] for vertex in path]
 else:
 return 0
 def hamiltonian_path(self, path, pos):
 if pos == self.n:
 return True
 for v in range(self.n):
 if self.is_safe(v, pos, path):
 path[pos] = v
 if self.hamiltonian_path(path, pos+1):
 return True
 path[pos] = -1
 return False
 def is_safe(self, v, pos, path):
 if self.graph[path[pos-1]][v] == 0:
 return False
 return all(vertex != v for vertex in path)
def small_maze():
 maze = [[1] * 11 for i in range(4)]
 maze[1][1] = 0
 for i in range(11):
 if i not in [3, 8]:
 maze[3][i] = 0
 return maze
def large_maze():
 maze = [[1] * 15 for i in range(10)]
 for i in range(5, 8):
 maze[4][i] = 0
 maze[5][5] = maze[5][7] = maze[6][5] = 0
 return maze
C = MazeSolver(small_maze(), (3, 8)) #(large_maze(), (2, 2))
t = time.time()
path = C.solve()
print(round(time.time() - t, 2), f'seconds\n\n{path}')

Another tutorial discusses a faster method using dynamic programming, called the Held-Karp algorithm. However, it seems to perform even worse (I had to interrupt the execution for the small maze). I don't know if I implemented it incorrectly because it worked with the tiny maze I used in the gifs.

 def check_using_dp(self):
 n = self.n
 dp = [[False] * (1 << n) for i in range(n)]
 for i in range(n):
 dp[i][1 << i] = True
 for i in range(1 << n):
 for j in range(n):
 if i & (1 << j):
 for k in range(n):
 if j != k and (i & (1 << k)) and self.graph[k][j] and dp[k][i ^ (1 << j)]:
 dp[j][i] = True
 break
 for i in range(n):
 if dp[i][(1 << n) - 1]:
 return True
 return False
maze = [[0, 0, 1, 1, 0],
 [1, 1, 1, 1, 1],
 [1, 0, 0, 0, 0]]
C = MazeSolver(maze, (1, 4))
C.check_using_dp()

I don't understand how it could be faster when it contains a loop of 2**n iterations (in the case of the small maze this is 17 billion). Can someone explain to me how to implement this algorithm properly?

The most time consuming calculations in my original method are the A* searches. Realizing that an open node only accessible from 1 direction is automatically not safe (except for the end node), I added a check in is_safe() before any calls to astar() to return False if any open node has less than two open neighbors. This resulted in a huge improvement in performance, solving the large maze in 14 seconds! Is it possible to achieve this level of performance with Hamiltonian path algorithms?

• trent: You're looking for a Hamiltonian path in the undirected graph of open nodes with given start and end points.
• alec: Thanks, I will read about it and try to implement it.
• QuantumChris: @alec networkx has some functionality for finding Hamiltonian paths.
• alec: Unfortunately it is only for directed graphs.
• Grajdeanu Alex: Please don't update the question. Just ask another one with the new code that you need reviewed and make a small reference to this question for more context.

Answer 1

Have you run a profiler on your code? It would help identify where the code is spending most of its time. If I had to guess, I would say the A* search is taking up most of the time for larger mazes. Try using a flood fill algorithm instead. If all the empty squares don't change to the same color, then a move has created two disconnected areas and the move is unsafe.

I also don't think you need to check every move to see if it is safe. Only check when a move is likely to be unsafe. For example, the current tile isn't touching a wall (or used tile), but the next tile would be touching.

Pre-calculate all possible moves for small groups of tiles may help. Say 2x2, 2X3, 3x3, ... 5x6, etc. Then use them to try to solve a smaller maze.

• alec: Yes the A* search is the most time consuming calculation, I mentioned in the last paragraph of the question. Using a flood fill algorithm seems like a great idea! I'd imagine one flood fill would be a lot faster than multiple A* searches. Identifying when a move is likely to be unsafe is a bit trickier. I will try these suggestions tomorrow.
• alec: Using a flood fill turned out to be a fantastic suggestion, thank you. The execution time to solve the large maze decreased from 14 seconds all the way down to 0.85 seconds!

Answer 2

Instead of using a different function for your dynamic programming solution (which I believe, if done correctly, will solve your problem), just add an lru_cache decorator to your recursive hamiltonian path function. Make sure to make the arguments sent to that function immutable (tuples recommended). Try it and let us know.

It should look something like:

from functools import lru_cache
@lru_cache
def hamiltonian_path(self, path, pos):
 path = list(path)
 if pos == self.n:
 return True
 for v in range(self.n):
 if self.is_safe(v, pos, path):
 path[pos] = v
 if self.hamiltonian_path(tuple(path), pos+1):
 return True
 path[pos] = -1
 return False

• alec: This would certainly be convenient, but the function needs to pass a list specifically because it's a mutable type, and when it gets updated this is reflected in all copies. I will give a shot at rewriting the structure to work with tuples but just casting between list and tuple in the existing code doesn't get the result.