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