Computing the shortest path in a labyrinth

Question

I'm currently trying to map how to make a good algorithm that won't have issues to find the shortest path. The labyrinth consists of an X and Y dimensions as input; However, the labyrinth will generate obstacles within the dimensions and randomly spawned. There is one entrance and at least one exit after finding the shortest path. The way to find the exit and shortest path will be in an order of movements. First it checks if going up is available, then left, then right, and finally down (priority movements: up->left->right->down). The movements must be horizontally and vertically, so diagonal moves are illegal, unfortunately.

My thought was to probably build a backtracking algorithm that will solve this problem; but, there is a catch for this. It says the labyrinth will not be more than a billion square, meaning that it can be a larger X and Y. Thus, the program will timeout and have to allocate more memory to execute with a Gigabyte file. So to reduce this amount of memory, maybe use bitfields to reduce and manipulate bitwise (which I never used it as a data structure).

My weak point is to have a strong foundation of how to approach such a problem that can be devastating to code and how to take care. I was wondering what kind of approach I need to consider too. I'm happy to discuss further and be curious about your approaches. I like to ask a lot of questions just for me to understand efficiently.

Answer 1

Path-finding algorithms are well studied. I.e. you'd typically use the A* algorithm if the exit location is known and otherwise the Dijkstra algorithm.

Both operate on graphs not on grids, so you can reduce the size of the problem by finding paths between connected intersections rather than paths between neighbouring tiles.

The problem is more difficult if the labyrinth map is not visible, but must be discovered by “walking” through the labyrinth. In that case, backtracking/depth-first-search is indeed a good solution.

A* is a variant of Dijkstra that knows how to walk in the right direction. It therefore needs to search far fewer nodes in typical problems. For a labyrinth that is designed to mislead, this may not matter.

These algorithms perform a kind of breadth-first search through the graph. They keep a queue of nodes, sorted by their minimum path distance so far. For each iteration, the search continues from the node that has the minimum distance. The advantage is that the first path from start to end that is found is guaranteed to be the shortest path. It is unnecessary to keep searching. In the worst case, the only path is also the longest path. You will then have visited each node once.

Both of these algorithms have optimal worst-case complexity with O(|V| log |V| + |E|), where |V| is the number of vertices (nodes) in the graph, and |E| is the number of edges. This assumes that the queue of to-be-visited nodes is implemented with a Fibonacci heap.

This particular case is easier since the degree of each node is bounded: there are at most 4 (up, down, left, right) connections to each node. Therefore, the number of edges is bounded |E| <= 4 · |V|. Additionally, the worst case only happens if the queue contains nearly all nodes. For a 2D problem, your graph is planar and this can't generally happen. You will therefore see typical runtimes close to |V| log sqrt |V| which scales almost linearly with the labyrinth size.

In case the labyrinth does not have cycles (i.e., there is at most one path from start to end), then you do not need to keep a queue of neigbouring nodes. Instead, a topo-sort based algorithm can find all paths from the start node in Theta(|V| + |E|), i.e. linear time. Note that a search-based algorithm such as A* may still be faster in some cases if it manages to find the exit node quickly.

In the above comments, Jules mentioned a great tutorial https://www.redblobgames.com/pathfinding/a-star/introduction.html on path finding. It contains rich, interactive illustrations that help to build a clear understanding of path finding concepts.