I really like the maze analogy! The pictures help a whole bunch in explaining the concepts!
Related:
I don’t know if this has a direct analog to a CS algorithm, but one other heuristic which seemed like it might have been good to try was drawing a line from both start and finish incrementally to see how they could touch in the middle.
Also not sure if it’s a standard concept in path search, but searching from both ends seems fruitful, even in its most naive implementations:
if the graph is sufficiently random, I think it should take the expected fraction of the maze you have to walk from N/2 to sqrt(N)
you can apply it to either BFS or DFS, though I suspect that in practice DFS works better (and even better still if you DFS by switching your first decision (rather than the OP’s algorithm of switching your last)
naturally, there’s plenty of room for layering heuristics on top, like seeking towards the opposing cursor, or even the nearest point of the opposing explored-so-far surface...
I really like the maze analogy! The pictures help a whole bunch in explaining the concepts!
Related: I don’t know if this has a direct analog to a CS algorithm, but one other heuristic which seemed like it might have been good to try was drawing a line from both start and finish incrementally to see how they could touch in the middle.
Also not sure if it’s a standard concept in path search, but searching from both ends seems fruitful, even in its most naive implementations:
if the graph is sufficiently random, I think it should take the expected fraction of the maze you have to walk from N/2 to sqrt(N)
you can apply it to either BFS or DFS, though I suspect that in practice DFS works better (and even better still if you DFS by switching your first decision (rather than the OP’s algorithm of switching your last)
naturally, there’s plenty of room for layering heuristics on top, like seeking towards the opposing cursor, or even the nearest point of the opposing explored-so-far surface...