The Level Generator

The Basic Rules

The puzzles in my games are a variation of the Numberlink puzzle, where each number is represented by a different color.  There are two basic rules to the puzzles:

1. Draw lines to connect same color dots – lines cannot cross each other (except on bridges).  
2. Fill the entire board with the lines (or “pipe”). 

All of the levels in my puzzle games were generated by a computer program that I wrote, which I refer to as the Level Generator.

Examples

My latest game, Connect Unlimited 2, features rectangular boards with a minimum grid size of 5×5 and a maximum size of 18×12.  Here’s an example level of each, along the solution:

 

Supported Modifications

In addition to rectangular grids, the level generator also supports irregularly shaped boards and hexagonal boards.  It also supports various modifications including:

• Interior walls and “blocks.”
• Bridges that allow two lines to cross each other.
• Shadows (or “warps”) that allow lines to go from one side of the board to the other.
• Portals, which come in pairs. A line can enter a portal from all four sides and will come out on the opposite side of the matching portal.
• Hexagonal two-way and three-way bridges (which I call “crosses”).

The Flow Solver

My puzzle games are based on the Flow Free series. Before I wrote the puzzle games, I wrote a program that was able to solve over 95% of the puzzles in the original Flow Free.
To help solve this problem, I created line drawing algorithms based on common patterns I noticed in the levels of Flow Free.

From Solver To Generator

Once I had written these line drawing algorithms, I decided to use them to generate brand new levels.  The basic premise of the level generator is simple:
Starting with an empty board, randomly place a pair of dots and then draw a line to connect them.  Keep adding pairs of dots until the board is filled.

Additional Rules

From my experience playing Flow Free, I noticed that in addition to following the basic rules above, there were two other characteristics shared by all levels:

1. Same color dots are never next to each other (corollary:  all lines are at least 3 tiles long, including the endpoints).  
2. The no “zig-zag” rule, which informally means that lines can’t have unnecessary bends in them.

Here’s one way to explicitly define the no “zig-zag” rule: If a line could have entered a square at an earlier point but didn’t, it can’t ever enter that square.

The red rectangle covers 3 squares that this line is not allowed to enter based on the beginning of the line.  

Without this rule, it is possible for a single line connecting a pair of dots to fill an entire board: 

The Line Drawing Algorithm:  Follow the Edges

The line drawing algorithm I created for the Flow Solver follows the above two rules – but when allowed to, follows the edges of the board such that the distance to the edge remains the same:

The line above is an example:  it is always 1 square away from the edge of the board.  

The Spiral

Using the above algorithm and following the “no touch” rules results in a lot of levels that feature the “spiral.”  The spiral pattern is most efficient for filling up a square board with dots:  only 2 pairs of dots are needed: 

This is what I call a perfect level.  A perfect level is a level with the minimum number of lines necessary to fill the board according to the above rules.  The first level in CTD: Portals is the only board design where this can be achieved with only 1 line.  

While it looks pretty – the levels become redundant when you see the same pattern over and over.  

To keep the levels interesting, I enforced a set a minimum number of dots and maximum individual line length for the levels that were generated for my game.  

Adjusting for bridges

Bridges are forced tiles – if a line touches a square next to a bridge, it must cross the bridge.  Adding this rule to the line drawing algorithm was simple.  A setting told the level generator how many bridges to add to a level, and the bridges are randomly placed on the board.  

Different Tile Shapes

 

Although different tile shapes required a lot more additional code than bridges – the basic premise is the same.  The code for the level generator is almost identical to that for square boards – it just needs to be told which tiles are adjacent to each other.  Each hexagonal tile is adjacent to 6 other tiles – compared to 4 with square shaped tiles. 

However, at each point in the line only 3 of the adjacent tiles are valid according to the No Touch rule – thus hexagonal levels aren’t that much different from square levels. 

The green line above must continue to one of the 3 tiles shaded green – the red shaded tiles break the touch rule.  

Hexagonal levels were the first time I tried different board shapes – with the two images above representing the main two shapes tested.  The first shape – which I called a “hive”, is more natural for hexagons and can produce the spiral.  The latter shape is what you see in most levels of Flow Free: Hexes.  It has the advantage of making better use of the space on the screen.  

Other Line Drawing Algorithms

When I created the Flow solver – the “follow the edges” line drawing algorithm (in code, I called it “Default”) was a necessity to solve many of the levels.  

Because of that, for a long time I assumed it was necessary for the level generator too.  It isn’t – there are many other ways the program can draw lines to create complete levels that follow all of the rules.  I created and tested several other algorithms – some of them take longer than others, and they produce levels that look quite a bit different from each other.  Here are a few of them: 

The random line drawing algorithm is what it is – the program randomly selects the next tile for each line, as long as it doesn’t break the touch rule.  This algorithm is the slowest and tends to produce levels with many more dots than the other algorithms. 

The green line shows a common pattern in levels produced by the backwards line drawing algorithm. 

While the backwards algorithm tries to keep lines straight, the backwards random line drawing algorithm doesn’t.  It frequently results in lots of long, crazy looking lines like this, with the rest of the board filled in with many shorter lines. 

Warps and Walls

Flow Free:  Warps inspired Connect the Dots:  Shadows – and required major updates to the level generator.  

Warps – or “shadows” as I call them – didn’t require too much effort.  All I had to do was update the adjacent tiles for each tile in each board according to the warps.  The generator itself hardly needed any changes.  

Walls – although seemingly simple, were an entirely different matter.  It wasn’t that hard to make the generator respect the walls – and I was generating levels with various warp/wall patterns fairly quickly.  

The work came in making the levels look like the walls.  

The Step Pattern

The step pattern turned into one of my favorite types of levels and is seen frequently in CTD: Shadows.  

This level was generated with the old “follow the edge” line drawing algorithm that I had termed “Default”.  

The lines in the level follow the edge of the board, according to the algorithm.  The algorithm itself doesn’t know or care that the “edges” of this board are warps – nor does it care that there are walls on the inside of the board.  

Follow the Walls

I played a lot of levels with warps and walls like that above that were generated with algorithms that didn’t care about the warps/walls.  They weren’t bad, but when I added a new algorithm that follows the walls and not the edges, everything clicked and I knew I had a new game on my hands. 

Here we see a perfect level with step walls.  

Board Design vs. Board Pattern

A board pattern defines the basic shape of the board and the walls.  

A board design defines the exact size of the board and placement of the walls.  Usually special tiles like bridges and portals are not part of a board design and instead randomly added to certain levels.  There are many possible board designs based off a single pattern.

In CTD: Shadows, there are nearly 200 different board designs, but only about 30 different patterns (depending on the specific definition of a pattern – it can get a bit hairy). 

Perfect Board Designs

A perfect level is a level with the fewest possible lines for a specific board design. 

A perfect design is a design that can be filled with the fewest possible lines for a board pattern.  

These are two levels from the Stepping Up pack in CTD: Shadows.  The board designs both follow the “Block Step” pattern (similar to the step pattern show above, but with block walls) – the first level is the 6×6 version and the 2nd level is the 7×7 version.  

Although the level itself isn’t perfect – the 7×7 block step board design is perfect – my program has generated levels that fill the board with just 2 pairs of dots.  Despite being the smaller of the two designs, the 6×6 block step design is not perfect.  

In fact – all block steps design with odd dimensions are perfect, while all block step designs with even dimensions are not.  

Quest for Perfection – Designs

A large portion of the work I put into CTD: Shadows was in trying to find perfect board designs for each pattern in the game.  I also wanted to find new and interesting patterns that had perfect designs with fewer dots.  I tested over 100 different patterns and 1000 different designs of which maybe 20% actually made it into the game.  

Quest for Perfection – Levels

The work above had nothing to do with the level generator itself – though I put a lot into a front end interface for creating new designs and generating levels.  

My level generator already could make perfect levels for basic squares and steps and did “good enough” for the rest of the patterns – so I didn’t put much work into it until after I released an update to CTD: Shadows that included a new level pack:  The River.  

The above may or may not be a perfect level.  All I know is it has the fewest pairs of dots (4) for any of the thousands of levels generated for the design. 

The River wall pattern is interesting in that the walls have both straight portions and step portions.  

I made many tweaks to the line drawing algorithm to try to optimize it for this pattern.  This resulted in over 30 different variations of my line drawing algorithm. 

Follow the Walls and the Lines

After my level generator draws a line, that line is treated the same as a wall for subsequent lines that it draws. 

While I was teaching my line drawing algorithms to follow walls of all different patterns – I was simultaneously teaching them how to follow the “walls” it created itself with existing lines.  

This is how big, often random-looking patterns show up so often in my Computer Art galleries.  The program draws a few lines, and then the rest of the lines (for the most part) follow along the same path. 

While I never did succeed at writing the perfect line drawing algorithm, the search for it led to many different algorithms that help increase the variation of the levels.  And it turns out that the less perfect algorithms generally perform better according to my similarity filtering. 

I only look at the line drawing algorithms used for each level after I pick my favorites – and they are close enough to each other that I can’t tell just by looking at a level.  This way, I’m able to see which algorithms I prefer compared to my program.  With the exception of a couple of algorithms I briefly used and hated – by the numbers, I don’t have any clear favorites or least favorites.  My favorites are distributed relatively equally according to how many of each algorithm were chosen by the similarity filtering.