- Randomized depth-first search
- Randomized depth-first search with stack shaking
- Random spanning tree with Prim’s algorithm
- Random spanning tree using Kruskal’s algorithm
- Hybrid of depth-first search and Kruskal’s algorithm
- Source code
- Online demo
This blogpost requires familiarity with previous one.
One of the disadvantages of using DFS to build mazes is “low branching factor”. The problem is that it actually runs for long time before hitting dead-end and having to backtrack, so it creates very long corridors with no room to “make the wrong turn” for potential maze explorer.
Let’s deal with it.
Originally I used recursive version, but to avoid stack overflow, actual demo was done non-recursive version of DFS.
This version will be modified to allow “shaking the stack”. I’ll introduce one argument (
shake) and use
shake stack instead of just
stack in match statement.
That’s absolutely it in “The algorithm” layer.
There was a “glue” layer adapting “The algorithm” to “The domain” and it just stopped working as we added new argument to the function. Don’t worry, though, it just a simple fix.
Previously it was calling
stackless depending which approach you used ‘elegant’ or ‘safe’) now it should call
traverse does not support shaking) with this extra argument. So the old code:
should be changed to:
and the code will compile again and work exactly as it was working before (you may remember that
id function does absolutely nothing). Why we did that then?
Because now, on every single step we have an ability to modify the backtracking stack.
I’ll suggest something like:
Which in 99% of cases returns
stack unmodified but from time to time shuffles it completely. Of course, it would be nice to use it now (
id gets replaced by
Please note, that from algorithm complexity point of view this is not good approach, as complexity just jumped from O(N) to O(N^2) (it’s a little but more complicated than that), but definitely it gives better results, as it tries to branch earlier.
The bottom line is that I did not really modify the algorithm (DFS) I just injected some extra behavior into it, but it is totally externally controlled (kind of definition of “injected”, right?). Functional composition rlz.