Research: Build a Unicursal Maze

[john-science]

This is a research topic. I think it is doable... if you're willing for the algorithm to be painfully slow. Can it be done smartly?

https://stackoverflow.com/questions/7369945/algorithm-for-maze-generation-with-no-dead-ends
http://www.michaelchaney.com/2014/03/unicursal-mazes/
http://people.cs.aau.dk/~normark/prog3-03/html/notes/fu-intr-2_themes-hilbert-sec.html
https://en.wikipedia.org/wiki/Space-filling_curve

[john-science]

There is a well-described algorithm here, though I am not sure it's right for this project.

And there is, apparently, a working unicursal algorithm here. Though it is not currently working in my browser.

[john-science]

This would work, but would need a little tweaking. Might be too boring though:

https://en.wikipedia.org/wiki/Space-filling_curve

[john-science]

Actually, generating a universal method for interesting, space-filling, unicursal mazes that works for mazes of any size/shape is deceptively hard. This is a research task, indeed.

[JiffyRob]

I don't know if this is helpful, but in research of my own for a separate project, I found this website: (https://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap). If you scroll down to the comments the writer of the blog states:

you just choose a starting point, and then follow the maze, splitting each passage in half lengthwise as you go. So deadends become u-turns, passages become two-way streets, etc. When you’re done, you’ll have a labyrinth that enters at one point, winds over every cell in the maze, and exits at a point neighboring the entrance. It will be exactly twice the dimensions of the original maze.

So the algorithm would look something like this:

1. Create and generate maze using any of the current generators
2. Modify the maze's grid so that every clear passage is multiplied by 3 (so every clear cell becomes a 3x3 square), or use a modified generator that does this for you in step one
3. Find all corridors in the maze (You should be able to use the algorithm found here (https://www.geeksforgeeks.org/find-rectangles-filled-0/), but with modifications to work with a numpy array instead of a list)
4. For every corridor found:
   • Find if it is horizontal or vertical (which dimension of the rectangle is larger)
   • If it is horizontal, then every value (possibly save the first and last) in its second row becomes a wall
   • If it is vertical, then every value (possibly save the first and last) in its second column becomes a wall

You might want to consider adding mazes with larger walls/corridors and the function to find the straight corridors to the main module. Especially the first one would be very useful for game development.

[JiffyRob]

You might also want to try creating a specialized perturbation method that keeps a unicursal maze unicursal, and then applying that liberally to a simple curve, like the peano curve mentioned in the wikipedia article. I don't know how you would go about this.

[john-science]

That's a really interesting algorithm! I haven't seen that before. I can look at it, and see what kinds of results it produces. No reason not to try.

Thanks!