NuclearStrawberry
patreon
New browser game, Panel Flux!
🕑 Added 2021-01-18 23:42:51 +0000 UTCHello, Azure here! I just released a little browser game called Panel Flux, which is a random puzzle generator based on Panel de Pon. It has a bunch of difficulty settings, sick chiptunes, and a gif export button, so go check it out!
The generator was super fun to write and I think the logic is really interesting, so I thought I'd write an article about how the algorithm works. This shouldn't get too technical, so you should be able to follow along even if you don't know anything about programming or the game itself.
The basic gameplay is that you get a limited number of moves to try to make all the blocks disappear by matching 3 or more in a row or column. You can swap them horizontally (but not vertically), and they fall down if nothing's below them. You can easily undo your moves to try different combinations, until you figure out the perfect sequence that makes the entire thing collapse!
Every puzzle is solveable in one giant chain – that is, only the final move will break any blocks, and it'll clear the entire stack as they all fall into place step-by-step. This is a restriction in the original Panel de Pon games as well (although they have a few exceptions), and it's key to making the entire thing feel satisfying.
This "chain rule" is also the backbone of the entire generation algorithm, which works backwards. The first task is making the completed puzzle state, as a big chain reaction that'll collapse on its own.
First, the generator places a set of blocks at random. This will be the final step of the chain. The generator runs through a few checks after placing each set, but none of them are relevant for this first one, so I'll just skip to the second set and explain from there.
Here's the second step, which displaces any existing blocks upwards. Each set of blocks is a random color, and it can be horizontal, or vertical, or one of each (crossing each other, but not necessarily in the middle). It doesn't always have to be at the bottom, but in this case it needed to be. The generator can also place more than one set in a single chain step for more complicated clears, which can look super cool! (There's some examples of that later.)
Here's a few possibilities for the third step, but there's a catch. The one on the far right doesn't actually form a 3-chain like the rest, since it didn't displace any of the cyan blocks from the second step! The check to prevent that is pretty elegant, though, and it weeds out a ton of more complex generation issues too.
It turns all the newly-placed blocks unbreakable temporarily, and then runs a really quick check to see if any of the other blocks are lined up in a matching set of 3. If none of them break, then that means the new ones displaced the old ones so the chain's good! If any do break, then it knows this setup's faulty, so it retries until it finds one that works. (If it fails too many times in a row then it undoes two steps instead of one.)
It turns the new blocks back to normal, and then runs the sim to see if the puzzle solves itself. This step is necessary to make sure that the new blocks didn't interfere with any of the existing ones, like if it placed two sets of the same color too close to each other.
Here's the full sequence for building this puzzle. Note how each step pushes the other blocks upwards:
So, now it has the completed state! Next step is to shuffle it so it's an actual puzzle. It picks a block at random, and moves it to anywhere that it could have come from. This can be as simple as swapping it with the block next to it, but also includes stuff like putting it up in a place that it could've dropped from (while displacing all the blocks above it). After every move, it checks to see if any blocks break, and if any do then it retries until it finds a move that makes the stack stable. It does this whole thing a different of times based on the current settings, with higher difficulties requiring more moves to clear.
Here's the shuffle steps that it picked. And now the puzzle's done!
Now it runs a few algorithms to calculate how hard the puzzle is, and also how cool it is. Both of these are pretty rough for the sake of speed, but they're accurate enough for my purposes. The difficulty check mostly looks at the numbers of each color of block, since more blocks is harder... but even if there's a ton of blocks, if only 3 of them are red, then that's a big clue for where to focus your attention on! It also gives a huge difficulty multiplier for every extra move it requires.
The coolness check mainly (but not exclusively) looks at the length of the chain and how many blocks get cleared in each step, giving bigger weight to later in the chain since it's way cooler to end on a huge 10-clear than to begin with one.
If the puzzle's too hard or too easy for the player's selected settings... it throws it all away and starts over. I tried a few different ways to make it more intelligent about its parameters to build up towards the target difficulty more reliably, but it always caused less interesting puzzles and didn't actually lead to faster gen times. Better to be fast than to be smart, I guess!
Puzzles are always generated as a set, defaulting to 5 but players can pick how many they want. It actually generates more than you ask for, though, so then it can do a bit of culling for consistency. If you ask it to generate 5, it actually generates 10 of them. It sorts them by algorithmically-determined coolness, and throws out the 5 worst ones. Then it sorts them by ascending difficulty for the actual playing order, except it always ends on the coolest one, since it'd be lame if it didn't!
That's all the important stuff! There's a few more interesting details I'd like to cover for people who are really into this, though:
• Move count, average chain length, and number of colors are determined ahead of time by your difficulty setting, in addition to changing the actual target difficulty that it aims for. All of these are given as a min/max range and it picks separately for each puzzle. You can tweak all the settings yourself too, by going to the Customize menu!
• Each difficulty setting has a range of 2 different move counts, like how Easy puzzles are always either 1 or 2 moves. It's not actually randomly picked, but instead it always ensures there's an exactly-balanced number of them both during generation and during culling. A set of 10 Easy puzzles will always have 5 one-move puzzles and 5 two-move puzzles.
• Big puzzles with only two colors are brutal, since it's really hard to tell what's supposed to match with what. They can be fun but only if they're rare, so the generator rerolls the number of colors once if it lands on 2.
• The generator exhaustively checks to make sure there's no solutions shorter than the move count, and also that there's no solutions that involve clearing blocks on anything except the last move. These are expensive checks though, so they get a bit more lenient on higher move counts, so maybe you can still find one...
• There used to be a problem in easier difficulties where you'd get several puzzles in a row that feel very similar. I implemented a system where it'll throw out any puzzles that have the same number of blocks cleared in every chain step as any previously-generated puzzle, which helps weed out most of those.
• Easy mode has a special case where it throws out any 1-move puzzles where only one possible swap can actually clear blocks.
• The "chain rule" where every puzzle is always one big chain seems like it'd limit the possibility space to be less interesting, but I think it'd be much worse without it. There's a lot of fun high-level solving logic that relies on the chain rule, and it means you never need to wait for blocks to clear during the setup steps, just the final one when you set it all into motion. Plus, it's just more fun to see it all collapse from one well-placed swap!
Links:
- Panel Flux
- Copy Kitty, our intense action game that we spent 7 years on!
- Our Patreon, where you can follow our updates on Sunfluffs, our adorable new game!
- Our Discord server, where you can post all your cool puzzle gifs!
