0
\$\begingroup\$

Not sure if anyone has played Noodles at all https://itunes.apple.com/gb/app/noodles!/id967624193?mt=8 but it is a simple puzzle game, that involves rotating tiles until they link up. The tiles are either 4-sided or 6-sided and each tile can have 1 of a set number of 'pipes' including end pipes. There's only one solution which you reach by joining all the pipes together to a special 'starter' pipe which can take the form of any of the other pipes. There's also no loops.

What type of algorithm would someone use for this? I thought it could perhaps be a maze algorithm, but I'm struggling to understand how you would go about this.I think it's because in essence there aren't any walls, just different styles of connectors. But is this in essence a perfect maze? Does anyone have an idea of a starting point for an algorithm to accomplish something similar?

I'm not specifically looking for code, but a help in the right direction to identify a relevant algorithm or how someone might go about this. Though I have tagged this 'ios' as that's what I would ultimately be targetting

\$\endgroup\$
0
\$\begingroup\$

A standard maze-generation algorithm would work just fine in this case. There are walls. What you see are just the paths through those edges which are not walled. A wall is every edge which is not connected. I added the "invisible" walls to one of the screenshots of the example app you posted:

walls

  1. Generate a maze with your favorite maze generation algorithm. There are lots of algorithms to experiment with.
  2. For each tile, check how many edges are not walled and generate the appropriate tile.
  3. Rotate all tiles randomly
  4. To check the win-condition, do not check if everything is rotated as it was before shuffling. There might be more than one valid solution (unless you are using a maze generation algorithm where you can mathematically prove that this is impossible). Do a flood-fill instead and check if all tiles are covered.
\$\endgroup\$
  • \$\begingroup\$ Thanks, though looking at the algorithm would it work for hexagonal tiles? \$\endgroup\$ – TommyBs Oct 13 '16 at 14:21
  • \$\begingroup\$ @TommyBs You mean the subdivision algorithm I mentioned in an older version of this answer? That's an interesting question you might want to ask as a new one. \$\endgroup\$ – Philipp Oct 13 '16 at 14:23
  • \$\begingroup\$ Silly me, yep I see the answer has been updated! \$\endgroup\$ – TommyBs Oct 13 '16 at 14:24
  • \$\begingroup\$ Probably a silly question but are there any specific algorithms that deal with different shapes grids better than others? \$\endgroup\$ – TommyBs Oct 13 '16 at 15:36
  • \$\begingroup\$ @TommyBs That question is not silly at all, but far too deep to answer with a comment. You should ask a new question about how to implement a maze generator for a hexagonal grid. \$\endgroup\$ – Philipp Oct 13 '16 at 16:38

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.