ohiogogl.blogg.se - We were here together grid puzzle

Note that this entire next section only discusses the number of cells, but does not say anything about their locations) Calculating the minimum distance can be done with a simple flood fill or Dijkstra's algorithm.

One way of doing that is to consider the minimum distance ("dMin") between each color's start and end cell - we know that there should at least be this much cells with that color. Obviously, we should try to reduce the number of configurations as much as possible. Constraining the number of cells per color In other words, the number of possible combinations is pretty high to start with, but also grows ridiculously fast once you start making the board larger. N^2 - 2N cells for which the color has yet to be determined.2N cells already occupied with start and end nodes.If the board has a size of NxN cells, and there are also N colours available, brute-force enumerating all possible configurations (regardless of wether they form actual paths between start and end nodes) would take: This will generate the most diverse levels.Īnd even if you find a way to generate the levels some other way, you'll still want to apply this solving algorithm to prove that the generated level is any good ) Brute-force enumerating This way, you can basically generate any random starting configuration and determine if it is a valid level by trying to have it solved. The most straightforward way to create such a level is to find a way to solve it. The starting point was the same simple columns approach as above. Some are interesting, some are not, but they're always valid with one known solution.ĥ Random Results (sorry for the misaligned screenshots)Īnd a random 8x8 for good measure. Starting with the first 5x5 grid below, the process produced the subsequent 5 different boards. Update: I coded a proof-of-concept based on the steps above. In the end, I think this approach is manageable, not cryptic, and easy to tweek, and, if nothing else, a good place to start. 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. Add any other ideas that you come up with.Add a step that prevents a dot from moving to an old location.Add a step to loop through the body of flow f, looking for trickier ways to swap space with other flows.The approach as it stands is limited (dots will always be neighbors) but it's easy to expand upon: Repeat the previous step for f's tail dot.(The puzzle is back to being solved as well.) Now g is one square longer than it was at the beginning of this iteration. Fill in that empty spot with flow from g.

Now there's an empty square where g's dot moved from.

Move the neighboring dot from g into the empty square vacated by f.

f is now one square shorter and there's an empty square.

Move f's head dot one square along its flow (i.e., walk it one square towards the tail).

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).

If f is at the minimum length (say 3 squares long), skip to the next iteration because we can't shrink f right now.

The second part, rearranging the flows, involves looping over each flow, seeing which one can work with its neighboring flow to grow and shrink: 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.

Place the tail dot at the bottom of that column.Īlternatively, you could provide your own hand-made starter boards to pass to the second part.

Place the head dot at the top of the first open column.

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 nx n grid: 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.