I traverse a maze using a basic A* implementation (using the Manhattan distance metric). However, after the traversal, I would like to find out what wall would give me the best alternative path. Apart from removing every block and re-running A* on the maze, what's a more clever and elegant solution?
a question I asked on SO over 10 years ago. The SO thread includes working code and very friendly explanations and discussion. The answer Phind gives is the following[2]. It tells me to use D＊-lite (complete overkill), Theta＊ (totally wrong), or "Adaptive-A＊" (not sure if that's an actual thing, all I can find is a random paper).
I was working on this in the context of a game I was making at the time, and while this is certainly a hard (and maybe rare) question, it's still on the level of CS undergrad.
Here you can apply the most common technique for such problems, which is to create a graph whose vertices are pairs made of a vertex of the original graph, plus the "state" of the traversal (or in other words, the essential information about the path used to reach the vertex).
In this case, the state is the number of walls passed, so just create a graph made of (v, k) pairs where for adjacent v and w in the grid, (v, k) connects to (w, k) if there is no wall, and it connects to (w, k + 1) if there is a wall.
Then run A*, finding the shortest path from (start, 0) to (end, 1), reconstruct the path and look at where it transitions from a (v, 0) to a (w, 1) and then return the wall between v and w.
You can use this for all sorts of other constraints, like finding a path that only changes direction up to N times, or a path where you don't get eaten by the monster moving deterministically (in this case the state is the monster position), or a path where you spend up to N time underwater consecutively, etc.
But GPT-4 seems very bad at solving problems, so even though this is an easy problem, it's not unexpected that it would not come up with this solution.
> find out what wall would give me the best alternative path
This, specifically, and the question as a whole are hard to parse as a human. Before clicking through to the SO link (where there seems to be a lot more context), I wouldn't have guessed the problem you were trying to solve.
I'm curious why you changed the prompt at all? Was it to get the model to avoid your question's SO page?
I have 21 years of professional experience as a software engineer with a bachelor in CS before that and have never heard of "Manhattan distance metric", "A* implementation", "D*-lite" or "Theta*" until now. I'm sure if I'd read the explanation of those things I'd eventually figure it out (and I'm sure an LLM would make more sense if fed descriptions instead of gobbledygook.
The SO answer is pretty good and probably the most generalizable pathfinding solution.
My first thought was to also run A* from the end to the start. This would allow you to look at each wall in the maze and check if the A* cost from the start + A* cost from the end < best current path. In my opinion, this would result in simpler code than the SO solution.
An equivalent formulation to the SO solution with a simple implementation is to double the vertices and edges in the graph G by making a duplicate parallel universe G'. One can always move from v in G to its corresponding v' in G' at zero cost, but there is also a cost-1 edge from vertex u in G to v' in G' whenever u and v are separated by a wall. Once one crosses into G', there is no going back.
One can pass the new graph, G ∪ G' plus all the intermediate edges, into the already existing A* implementation to search for an optimal s-t' path. This works as long as the heuristic for v is also admissible for v', but most are. I think all three of these algorithms could in principle run into problems for certain uncommon admissible heuristics.
> My first thought was to also run A* from the end to the start. This would allow you to look at each wall in the maze and check if the A* cost from the start + A* cost from the end < best current path. In my opinion, this would result in simpler code than the SO solution.
Yeah, this is the naive O(n^n) solution. Remove every wall, see what path is the cheapest. Having come up with this, I specifically wanted a more elegant solution. As it turns out, you can do it in one shot (but it's a bit tricky).
I am not explaining an O(n^n) solution. Its an O(E) time and O(V) space solution just like normal A*.
I am assuming you are saving the initial A*run and the subsequent reverse run. Then `A* cost from the start + A* cost from the end < best current path` is a O(1) time operation that occurs a maximum of once per edge.
Maybe I'm totally misunderstanding, but figuring out the "best current path" means re-running A* every time you break a wall, as removing arbitrary walls can give you a totally new path to the goal; to wit, it might be a path not even originally visited by A*. And you have to do that every time you try out a wall candidate, so to me this appears to be quadratic(ish) complexity.
(But maybe this is exactly what the SO answer does "under the hood," to be honest, I haven't done a deep complexity analysis of it and I haven't thought about this problem in ages.)
> Maybe I'm totally misunderstanding, but figuring out the "best current path" means re-running A* every time you break a wall, as removing arbitrary walls can give you a totally new path to the goal; to wit, it might be a path not even originally visited by A*. And you have to do that every time you try out a wall candidate, so to me this appears to be quadratic(ish) complexity.
My algorithm should obviously work using Dijkstra's algorithm instead of A*. You just have to make sure ALL nodes are explored. You don't have to run searches per node.
Why it works with A* too is MUCH more subtle. In fact it only works if your A* implementation is fair to all likely shortest paths; most implementations do not guarantee fairness. You can enforce fairness by changing your heuristic to be only 0.9999 * Manhattan distance. Fairness ensures that any path that will be the best path after deleting a wall will have a cost recorded for both sides of the wall.
> (But maybe this is exactly what the SO answer does "under the hood," to be honest, I haven't done a deep complexity analysis of it.)
If the original maze is 2D with coordinates (x,y), the SO algorithm is essentially searching in a 3D maze with coordinates `(x,y, number of times crossed a wall)` and directional edges from `(x,y,n) to (x+dx,y+dy,n+1)` if there is a wall there.*
> My algorithm should obviously work using Dijkstra's algorithm instead of A*. You just have to make sure ALL nodes are explored.
Gotcha, yeah, that's what I was thinking. You lose basically all of A-star's optimization because you do need all nodes explored (turning it into pure Dijkstra). Makes total sense.
> If the original maze is 2D with coordinates (x,y), the SO algorithm is essentially searching in a 3D maze with coordinates
That's a neat way of looking at that answer, cool insight!
I asked OpenAI that exact question, this is what it said:
> One approach to finding the wall that would give you the best alternative path without having to remove every block and re-run A* is to use the concept of "edge weights."
> When you first run A* to traverse the maze, you can assign each edge a weight equal to the distance between the two adjacent nodes, which is equal to the Manhattan distance in your case. Once you have completed the traversal, you can go through each edge of the path that A* has found and temporarily increase its weight by some factor. Then, you can run A* again, but this time the pathfinder will prefer alternative paths that do not use those edges that have been "blocked" by the increased weight.
> By gradually increasing the weight of each edge one at a time, you can determine which wall would give you the best alternative path without having to re-run A* on the entire maze every time. You can also use a binary search-like approach to speed up the process.
> Here's some pseudocode for this approach:
path = A_star(start_node, goal_node, edge_weights)
for edge in path:
original_weight = edge_weights[edge]
edge_weights[edge] = original_weight * factor
new_path = A_star(start_node, goal_node, edge_weights)
if new_path is better than path:
best_wall = edge
path = new_path
edge_weights[edge] = original_weight
> In this pseudocode, factor is the amount by which you increase the weight of each edge, and better than is some metric for determining whether a path is better than another (e.g., if it is shorter or has fewer turns).
Followed by this question: List ten most relevant links to the information you have summarized above.
> Here are ten relevant links related to A* search and maze traversal:
"A* search algorithm" on Wikipedia: https://en.wikipedia.org/wiki/A*_search_algorithm
"Manhattan distance" on Wikipedia: https://en.wikipedia.org/wiki/Manhattan_distance
"A* Pathfinding for Beginners" tutorial on Red Blob Games: https://www.redblobgames.com/pathfinding/a-star/introduction.html
"Introduction to A*" video on YouTube by Sebastian Lague: https://www.youtube.com/watch?v=-L-WgKMFuhE
"A* Pathfinding Visualization" demo on GitHub by Qiao Zhang: https://qiao.github.io/PathFinding.js/visual/
"A* Pathfinding Tutorial" on Amit's Game Programming Pages: http://theory.stanford.edu/~amitp/GameProgramming/
"A* Pathfinding Algorithm" tutorial on GeeksforGeeks: https://www.geeksforgeeks.org/a-search-algorithm/
"Introduction to Pathfinding" tutorial on Unity Learn: https://learn.unity.com/tutorial/introduction-to-pathfinding
"Pathfinding in Games: A* Search" tutorial on Ray Wenderlich: https://www.raywenderlich.com/3016-pathfinding-in-games-a-search
"Maze generation algorithm" on Wikipedia: https://en.wikipedia.org/wiki/Maze_generation_algorithm
> These links provide a range of resources, including tutorials, demos, and background information on A* search and maze generation.
Followed by: Please rewrite the lua code to golang.
> In this Go code, AStar is a function that takes in the start and goal nodes, as well as the edge weights, and returns the optimal path using A* search. The isBetterThan method is a placeholder for some comparison function that determines whether a path is better than another (e.g., if it is shorter or has fewer turns).
> Note that the syntax and semantics of Go are quite different from Lua, so this is not a direct translation. However, the logic should be equivalent, and the Go code should be easy to understand if you are familiar with the original Lua code.
Finally: Show the declaration of the AStar struct.
> Sure! Here is an example declaration of an AStar struct in Go:
> In this example, the AStar struct has three fields:
startNode: a Node struct representing the starting node of the pathfinding search.
goalNode: a Node struct representing the goal node of the search.
edgeWeights: a map from Edge structs to float64 values representing the weights of each edge in the graph.
> Note that this is just an example, and the actual definition of the AStar struct may depend on the specific implementation of the pathfinding algorithm. The Node and Edge structs may also need to be defined separately, depending on how they are used in the implementation.
And as a cherry on top: Inline comments in the AStar struct.
> Sure, here's an example of adding inline comments to the AStar struct I defined earlier:
type AStar struct {
startNode Node // The starting node of the pathfinding search.
goalNode Node // The goal node of the search.
edgeWeights map[Edge]float64 // A map from edges to their weights in the graph.
}
> In this example, I added comments to explain the purpose of each field in the AStar struct. The comments describe what each field represents and what it is used for in the pathfinding algorithm. By adding comments to the struct definition, it makes it easier for others to understand the role of each field in the codebase.
> When you first run A* to traverse the maze, you can assign each edge a weight equal to the distance between the two adjacent nodes, which is equal to the Manhattan distance in your case. Once you have completed the traversal, you can go through each edge of the path that A* has found and temporarily increase its weight by some factor. Then, you can run A* again, but this time the pathfinder will prefer alternative paths that do not use those edges that have been "blocked" by the increased weight.
Yeah, this is wrong for two reasons. First, it's actually doing things backwards (you would decrease the cost of a wall, you wouldn't need to block any path). And second, it's still predicated on re-running A* after modifying costs (and comparing it with our original path), getting us back to O(n^n).
This is more evidence that AI models are good at regurgitating, but not great at reasoning. GPT-4 probably only saw this problem once or twice (since it was trained on the Pile, which includes all of SO, including my original question), but not enough times to understand what the solution is (or even what you're asking, for that matter).
The unfortunate part is that OpenAI cannot answer a question “show me most relevant stackoverflow links for my original question”.
Edit: however, I went on and grilled it further.
Question: Rewrite the golang code to solve the maze in constant time.
> I'm sorry, but it is not possible to solve a maze in constant time, as the time complexity of the problem depends on the size of the maze and the complexity of the search algorithm used.
> The A* algorithm and its variants are some of the most efficient and widely used algorithms for maze pathfinding, as they can provide near-optimal solutions in a reasonable amount of time. However, they still have a time complexity that is exponential in the worst case.
> There are other algorithms that can solve certain types of mazes faster than A, such as maze-solving algorithms that rely on distance transforms, flood fills, or topological sorting. However, these algorithms are typically specialized and may not work for all types of mazes.
> In summary, it is not possible to solve a general maze in constant time, but there are specialized algorithms that can solve certain types of mazes faster than A.
A couple of attempts to rephrase make the GPT a bit apologetic. It claims it's not possible to do anything about, eventually, when asked to solve the maze of size 20 times 20, it replies:
> With a maze size of 20x20, it is likely that the performance of the A* algorithm is already sufficient for practical purposes. However, if you encounter performance issues or have specific constraints that require faster solutions, you can consider implementing these optimization techniques.
So I ask it: What optimization techniques I could implement?
> There are several optimization techniques that can be implemented to improve the performance of the A* algorithm or other maze-solving algorithms. Here are some examples:
Use a more informed heuristic: The Manhattan distance heuristic used in the original code is a good general-purpose heuristic, but it may not be the most efficient for all maze configurations. Using a more informed heuristic, such as Euclidean distance or diagonal distance, can lead to faster convergence and fewer nodes being explored.
Implement early termination: If you only need a suboptimal solution or are willing to tolerate some error in the solution, you can terminate the search early once a "good enough" solution has been found. For example, you can set a maximum number of nodes to explore or a maximum search depth.
Prune search space: If you know some parts of the maze are not relevant to the solution, you can exclude those parts from the search space to reduce the number of nodes that need to be explored. For example, if you know the goal is located in a certain region of the maze, you can exclude nodes that are outside of that region from the search space.
Use a better data structure: The performance of the A* algorithm is heavily dependent on the data structure used to store the open and closed sets. Using a more efficient data structure, such as a binary heap or Fibonacci heap, can speed up the algorithm.
Parallelize the search: If you have access to multiple processing units, you can split the search space into multiple parts and run the A* algorithm in parallel. This can significantly reduce the search time, especially for large mazes.
> These techniques are not mutually exclusive, and you can combine them in different ways to achieve better performance. However, keep in mind that the optimal combination of techniques will depend on the specifics of the maze-solving problem and the available computational resources.
I still find it pretty good. It also proves my point I was making somewhere else. The challenge in applying GPT to software problems is knowing what to ask next and verifying that it gave a correct answer - as in, one needs to understand the problem without blindly trusting that what it said was right.
I was working on this in the context of a game I was making at the time, and while this is certainly a hard (and maybe rare) question, it's still on the level of CS undergrad.
[1] https://stackoverflow.com/questions/2489672/removing-the-obs...
[2] https://www.phind.com/search?cache=d08cd0e7-4aa8-4d75-b1cd-7...