4 ms·

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 woul

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.

dvt 3y ago
> 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).
- thethirdone 3y ago
  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.
  - dvt 3y ago
    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.)
    - thethirdone 3y ago
      > 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.*
      - dvt 3y ago
        > 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!
CaptainNegative 3y ago
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.

dvt 3y ago

> 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).

thethirdone 3y ago
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.
- dvt 3y ago
  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.)
  - thethirdone 3y ago
    > 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.*
    - dvt 3y ago
      > 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!

CaptainNegative 3y ago

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.