10
\$\begingroup\$

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?

\$\endgroup\$
  • 4
    \$\begingroup\$ You're looking for a Hamiltonian path in the undirected graph of open nodes with given start and end points. \$\endgroup\$ – trentcl Feb 25 at 18:55
  • \$\begingroup\$ Thanks, I will read about it and try to implement it. \$\endgroup\$ – alec Feb 25 at 19:04
  • \$\begingroup\$ @alec networkx has some functionality for finding Hamiltonian paths. \$\endgroup\$ – QuantumChris Feb 26 at 11:13
  • \$\begingroup\$ Unfortunately it is only for directed graphs. \$\endgroup\$ – alec Feb 27 at 22:12
  • \$\begingroup\$ 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. \$\endgroup\$ – Grajdeanu Alex. Feb 28 at 7:39
3
+100
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – alec Feb 28 at 7:30
  • \$\begingroup\$ 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! \$\endgroup\$ – alec Feb 29 at 19:51
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – alec Feb 28 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.