Quick links
 Randomized depthfirst search
 Randomized depthfirst search with stack shaking
 Random spanning tree with Prim’s algorithm
 Random spanning tree using Kruskal’s algorithm
 Hybrid of depthfirst search and Kruskal’s algorithm
 Source code
 Online demo
Note
This blogpost requires familiarity with previous one.
Low branching factor
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 deadend 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.
The algorithm
Originally I used recursive version, but to avoid stack overflow, actual demo was done nonrecursive 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.
The glue
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 traverse
(or stackless
depending which approach you used ‘elegant’ or ‘safe’) now it should call stackless
(as 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 shake
):


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.