I am working on a project that uses a form of the recursive division algorithm that is normally used to create a fractal-like maze. Now I would like to cite the creator/author of this algorithm to give them credit, but I am unsure who invented it.
Jamis Buck has a very famous blog entry https://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm , that is titled: "A novel method for generating fractal-like mazes is presented, with sample code and an animation" but did he actually came up with that idea? I do not understand his post as that he invented it, to me it sounds more like he is just describing it.
I was not able to find a clear publication/author through Google and Wikipedia(en) or any other specifically maze-focused site. Does anyone know about the origin of this algorithm?
The recursive division algorithm was invented and named by John Perry, who added it to Wikipedia's Maze generation algorithm page in November 2006.
To assist with questions like this, Walter Pullen's Maze generation algorithms page has been updated to add a "Source" column to the table of Maze generation and solving algorithms, to list who invented, named, or otherwise popularized each algorithm. Yes, it is true that many Maze algorithms are adaptations of general graph theory algorithms, and that many algorithms are similar to or variations on others, etc.
For example, recursive division is a type of "nested Mazes", "fractal Mazes", or "Mazes by subdivision", which means generating smaller Mazes within each cell of a larger Maze. That is an older and more general concept, and others (for example the Maze generation program Daedalus) have done nested cell Mazes since 2003. However, it would always divide the Maze into the SAME sized submazes, e.g. a 2x2 equal sized cell Maze with equal sized 2x2 cell Mazes within each cell, with the process repeated 6 times.
John Perry introduced the idea of dividing a Maze into RANDOM sized 2x2 cell Mazes instead of just fixed sized 2x2 cell Mazes, which can generate a Maze of any dimensions instead of just 2^N power passages as with nested cell. The result looks a bit more organic (like a tree trunk) instead of grid based (like a Borg cube). Note that the implementation of recursive division in Daedalus is a bit more generalized, in that Daedalus divides the Maze into either 1x2 or 2x1 cell Mazes (option chosen randomly too) which looks even more random and organic. Also, note that both same and random sized division ("nested cell" algorithm and "recursive division" algorithm) can be implemented in a virtual manner to produce virtual Mazes of enormous size (in which not all of the Maze has to be in memory at once).
