Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Research: Build a Unicursal Maze #18

Open
john-science opened this issue May 14, 2014 · 6 comments
Open

Research: Build a Unicursal Maze #18

john-science opened this issue May 14, 2014 · 6 comments
Labels

Comments

@john-science
Copy link
Owner

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 john-science self-assigned this May 15, 2014
@john-science
Copy link
Owner Author

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
Copy link
Owner Author

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

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

@john-science john-science removed their assignment Jan 7, 2020
@john-science
Copy link
Owner Author

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
Copy link

JiffyRob commented Apr 9, 2022

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
Copy link

JiffyRob commented Apr 9, 2022

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
Copy link
Owner Author

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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants