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).
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:
Input the
maze(2D list ofTileobjects),startnode , andendnode to theMazeSolverclass.A neighboring node is chosen (up, right, down, left).
If that node
is_open(), then check if itis_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).If it
is_safe(), visit the node and link theirnextandprevattributes.If the node is not open or not safe, add it to the
closedlist.If all 4 neighbors are in
closed, backtrack to the previous node.Repeat 2-6 until
endis 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?
