Generating noodles puzzles
Haven't noodled yet? Download noodles here!
So it must take a long time to think up so many connected noodles puzzles, right?
Wrong! Even though the levels look and feel amazing, each one more impressive than the last, they are actually generated using what the cool kids call "algorithms". And here's how:
In the last post I mentioned that Noodles puzzles are graphs. But we can go further. Fully-connected puzzles have no cycles, so it's a fully-connected acyclic graph. In fact, if you want to consider the source node as a root, the whole thing is an n-ary tree, though that doesn't impact puzzle generation.
So who cares? Well, to generate puzzles we fall back on some nice graph algorithms. To generate puzzles, here's what we do:
- Start with a bunch of nodes with no edges.
- Choose a node randomly. That's your graph so far.
- Pick a random node in the graph, connect it to a random adjacent node not in the graph.
- Repeat 3 until all nodes are in the graph.
- Pick a piece to be your Source. (whispers) which piece doesn't actually affect the puzzle at all...
There are a few complications in those directions. One is that sometimes a node in the graph can't connect to anything around it, because it's reached the max connections (in square games, I set that max to 3. In hex games, 4) or because everything around it is in the graph. When this happens, you can just try another node, or keep track of the nodes that can be used, and take the problem node out of that list.
Another is that there's a small chance that this process will connect your graph in such a way that makes it impossible to have a fully-connected graph. So you have to have a way to error out and try again. Luckily, the error rate isn't very high.
So why does this work? Well, the short answer is this: Any acyclic, connected graph is a valid puzzle. At each step of the algo you're making a new edge, and one of the nodes is not in the graph. You're never connecting two already-connected nodes, so you can't create any cycles that way.
Best part? The algorithm works great for any puzzle type. The rules just change in step 3, for which nodes are candidates to connect with which other ones.
Michael, does this mean I could have a game with heptagons? FOOL. THAT'S JUST WHAT HEPTAGONS WOULD HAVE YOU THINK.