What to use for flow free-like game random level creation?

Question

I need some advice. I'm developing a game similar to Flow Free wherein the gameboard is composed of a grid and colored dots, and the user has to connect the same colored dots together without overlapping other lines, and using up ALL the free spaces in the board.

My question is about level-creation. I wish to make the levels generated randomly (and should at least be able to solve itself so that it can give players hints) and I am in a stump as to what algorithm to use. Any suggestions?

Note: image shows the objective of Flow Free, and it is the same objective of what I am developing.

Thanks for your help. :)

Answer 1

Consider solving your problem with a pair of simpler, more manageable algorithms: one algorithm that reliably creates simple, pre-solved boards and another that rearranges flows to make simple boards more complex.

The first part, building a simple pre-solved board, is trivial (if you want it to be) if you're using n flows on an nxn grid:

• For each flow...
  • Place the head dot at the top of the first open column.
  • Place the tail dot at the bottom of that column.

Alternatively, you could provide your own hand-made starter boards to pass to the second part. The only goal of this stage is to get a valid board built, even if it's just trivial or predetermined, so it's worth keeping it simple.

The second part, rearranging the flows, involves looping over each flow, seeing which one can work with its neighboring flow to grow and shrink:

• For some number of iterations...
  • Choose a random flow f.
  • If f is at the minimum length (say 3 squares long), skip to the next iteration because we can't shrink f right now.
  • If the head dot of f is next to a dot from another flow g (if more than one g to choose from, pick one at random)...
    • Move f's head dot one square along its flow (i.e., walk it one square towards the tail). f is now one square shorter and there's an empty square. (The puzzle is now unsolved.)
    • Move the neighboring dot from g into the empty square vacated by f. Now there's an empty square where g's dot moved from.
    • Fill in that empty spot with flow from g. Now g is one square longer than it was at the beginning of this iteration. (The puzzle is back to being solved as well.)
  • Repeat the previous step for f's tail dot.

The approach as it stands is limited (dots will always be neighbors) but it's easy to expand upon:

• Add a step to loop through the body of flow f, looking for trickier ways to swap space with other flows...
• Add a step that prevents a dot from moving to an old location...
• Add any other ideas that you come up with.

The overall solution here is probably less than the ideal one that you're aiming for, but now you have two simple algorithms that you can flesh out further to serve the role of one large, all-encompassing algorithm. In the end, I think this approach is manageable, not cryptic, and easy to tweek, and, if nothing else, a good place to start.

---

Update: I coded a proof-of-concept based on the steps above. Starting with the first 5x5 grid below, the process produced the subsequent 5 different boards. Some are interesting, some are not, but they're always valid with one known solution.

Starting Point

5 Random Results (sorry for the misaligned screenshots)

And a random 8x8 for good measure. The starting point was the same simple columns approach as above.