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
Answer
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:
- Generate a maze with your favorite maze generation algorithm. There are lots of algorithms to experiment with.
- For each tile, check how many edges are not walled and generate the appropriate tile.
- Rotate all tiles randomly
- 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.
No comments:
Post a Comment