3

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?

Senca
  • 33
  • 5
  • Why not ask Jamis? His email & Twitter account are at the bottom of the linked blog post. – Dave Mar 12 '21 at 12:21
  • Good point. I will try. – Senca Mar 12 '21 at 12:32
  • Buck's use of "novel" in that description indicates that it is his algorithm and it was new with that 2011-01-12 source. "novel" is mutually exclusive with "previously invented by someone else". – L. Scott Johnson Mar 12 '21 at 12:44
  • But it could be "novel" only in the context of his blog. Anyways i send him an email and will report back. – Senca Mar 12 '21 at 12:48
  • 1
    Wow! I did invent it, wrote the original Wikipedia material, and contributed the illustrations (which someone improved). In 2005 or 2006 I was writing a game for my son’s birthday, and for various reasons devised this algorithm, whose simplicity appealed to me. After that I nearly forgot it; I dug up the code recently and scolded myself for never implementing other, "serious" algorithms. I’ve had no idea that anyone paid attention to the algorithm, let alone included it in a book. As a mathematician I'm delighted to learn that there is a fractal-like aspect to it. – John Perry Mar 13 '21 at 16:04

2 Answers2

3

No, the algorithm is not mine; I learned it from Walter Pullen’s page, here: https://www.astrolog.org/labyrnth/algrithm.htm. He also does not cite an author for this algorithm. It should be noted that many maze algorithms are adaptations of more general graph algorithms, so it could be that this one has an analog in graph theory somewhere...

At any rate, it’s not mine. I used the word “novel” in my post in the second sense given here (https://www.merriam-webster.com/dictionary/novel) “original or striking especially in conception or style”, not in the sense of “new”.

Jamis Buck
  • 76
  • 4
2

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

Cruiser1
  • 36
  • 4