0
\$\begingroup\$

Based off my previous question here Maze or puzzle algorithm for something similar to noodles are there specific algorithms that would be best suited to building a maze with only 1 solution for

  1. A grid made of squares.
  2. A grid made from hexagonal tiles

Thanks

\$\endgroup\$
  • \$\begingroup\$ Note that you're using a somewhat unusual definition of "only 1 solution" for the context of mazes. Usually when we say that, we mean "there is exactly one path from the beginning to the end of the maze." In your case though, judging by your previous question, you mean "there is exactly one way to rotate all the tiles in the maze so that they all connect to one another." If I've interpreted your problem correctly, you should put this criterion explicitly into this question, otherwise you're likely to get answers for the more common maze case of finding paths. \$\endgroup\$ – DMGregory Oct 15 '16 at 14:38
  • \$\begingroup\$ @DMGregory When would it make a difference? Do you have a counter example? p.s I'm not suggest there isn't one, just asking (our of curiosity) cause I don't wish to bother to think about it currently. \$\endgroup\$ – wolfdawn Oct 19 '16 at 11:21
  • 1
    \$\begingroup\$ @zehelvion Yes, there are mazes with only one solution in the "how do I get to this tile" sense, but multiple solutions in the "how many ways can I rotate these tiles to connect them all to the source" sense. See this example. I'm not sure it's a problem for gameplay - if the player found either solution from an initially disconnected set, I think they'd be pretty pleased, and may not realize other solutions exist. It does slightly complicate hint systems though (which solution do we hint the player toward?) which might be why the asker requested only 1 solution. \$\endgroup\$ – DMGregory Oct 19 '16 at 12:34
  • \$\begingroup\$ Very nice example. So the question is far more complicated... \$\endgroup\$ – wolfdawn Oct 19 '16 at 16:09
  • \$\begingroup\$ Thanks for the comments all, sorry for the late response got caught up in other things (don't we all). I think maybe the one solution isn't necessary now as I can keep track of making sure everything is connected so even if there are multiple solutions I should be able to work out a 'win' state. And people won't want hints surely - where's the fun in that :P \$\endgroup\$ – TommyBs Nov 2 '16 at 7:15
1
\$\begingroup\$

For all maze algorithm problems, Think Labyrinth: Maze Algorithms usually has what you want.

Mazes with only one solution are known as Perfect Mazes. The page I linked lists more than a dozen algorithms for generating those, as well as a comparison table, under the heading Perfect Maze Creation Algorithms. Take your pick.

All these algorithms can be adapted for hexagonal mazes (or any topology and tessellation).

\$\endgroup\$
1
\$\begingroup\$

You would simply use Union Find and randomize the pair orders. When you are unifying, connect the two hexagons or squares (remove the border between them) and when you aren't unifying, leave the border as is. Randomize the order of unification.

Union Find is used to keep track of which rooms are accessible from which other rooms so you end with a maze where there is only one path between any pair of rooms (no cycles). Then you can add an entrance and an exit wherever you want.

\$\endgroup\$
  • \$\begingroup\$ Pairs are adjacent squares or hexagons that share a border. \$\endgroup\$ – wolfdawn Oct 13 '16 at 17:48
  • \$\begingroup\$ courses.cs.washington.edu/courses/cse326/08sp/lectures/… \$\endgroup\$ – wolfdawn Oct 13 '16 at 17:50
  • \$\begingroup\$ Homework due on Friday! That's tomorrow and I've got loads of reading to do to get my head around this! \$\endgroup\$ – TommyBs Oct 13 '16 at 18:12
  • \$\begingroup\$ Just use an existing implementation Union Find and and randomly pick adjacent pairs of squares or hexagons and if you can unify them, remove the border between them. It is doable. \$\endgroup\$ – wolfdawn Oct 19 '16 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.