I Made a Maze Generator in Unity Using the Origin Shift Algorithm

‪@captainluma7991‬ invented new algorithm called the "Origin Shift" algorithm. I wrote a Unity program that implements the algorithm to both generate a maze from scratch and to modify the maze once maze generation is complete. This program can also generate mazes using the Depth First Search algorithm instead of the Origin Shift algorithm, but will always use the Origin Shift algorithm to modify the maze once generated.
CaptainLuma's Video:
• New Maze Generating Al...
Project Download:
tchapman500.it...
Source Code:
github.com/TCh...

[@acomfyslugcat]

Kinda crazy to see that one maze video that I watched on a whim make its round in the niche maze generation community.

[@JMPDev]

0:35 back to the o-

[@TimothyChapman]

Of course there would be an audio malfunction like that!

[@JMPDev]

@@TimothyChapman always happens 😂 keep up the good work

[@RaPsCaLLioN1138]

I really like this algorithm, especially for Minecraft!

[@rajkamallashkari]

The Origin Shift algorithm isn't used to generate a perfect maze, but to change it so that it still remains a perfect maze. So to use the Origin Shift algorithm for generating a new perfect maze, there should already be a perfect maze, even if it's a simple hardcoded one. In the video there's no maze at the beginning, the Origin Shift algorithm actually starts taking place after all the points are already connected to all the other points via exactly one path between them.

[@TimothyChapman]

So what should we call the algorithm when it's used before there's a completed, perfect maze?

[@Mike_Xcz]

6:19 i wont say more...

[@dovos8572]

origin shift takes a perfect maze and changes it. it isn't really a create from nothing generator.
you can use any maze generation algorithm that ends with a perfect maze and then start the origin shift.
the only requirement is that you have the vector map or "ternary tree" that points to the origin point/root.
you can either generate the map by walking the existing maze or by keeping track of it while the other maze generator is running. like you do in the end of the video
i made a version in godot and i'm starting with the simplest maze that is shown in the video. a few friends made more complex starting mazes by starting with a pattern that is spread over the map.
the use of a pattern makes it so that less iterations are needed to make a new unique looking maze.
i also added a visited count to each cell that the random walk uses to change locations faster and not loop back to positions it already went to as fast. sure it is a bit slower but i only need a few iterations every few seconds so i don't really need it to run in

[@abraxas2658]

I believe this is the Aldous-Broder Algorithm at the start. I think Origin Shift is an adaptation of Aldous-Broder Algorithm to modify existing mazes.

[@TimothyChapman]

Interesting. I just looked it up and the two algorithms are nearly identical with one major exception: The Aldous-Broder Algorithm does not modify existing connections. The Origin Shift Algorithm does. Thanks for the info.

[@abraxas2658]

@@TimothyChapman I'm not sure there's an appreciable difference between the algorithms (but modifying the maze as you go might prevent the Aldous-Broder Algorithm's uniformity feature from applying here). I'd guess your algorithm is slightly more complex, as it maintains the direction of each edge in the graph.
I want to clarify that I'm super impressed with your ability to generalize the Origin Shift algorithm to work with empty mazes! I'm going to add it to my list of maze gen algorithms to evaluate for my project. 🙂

[@abraxas2658]

@@TimothyChapman Also! If you're wanting to use Origin Shift with good speed in unity, you might look into switching to Wilson's algorithm after a certain % of the maze is filled. It has the same texture of Aldous-Broder Algorithm/Origin Shift (while depth-first effectively generates one long corridor with short deadends branching from it).

[@Oscaragious]

I'm a bit confused why this algorithm was made in order to prevent large red stone circuits. Those seem like 2 unrelated things?

[@TimothyChapman]

Redstone circuits are inherently large, even when optimized for minimal size. And a dynamic maze is implemented by giving each cell its own copy of the maze generation logic. The more complex the logic, the larger the cell has to be to accommodate the circuit.