The “pattern-filling with tiles” puzzle

Question

I've encountered an interesting problem while programming a random level generator for a tile-based game. I've implemented a brute-force solver for it but it is exponentially slow and definitely unfit for my use case. I'm not necessarily looking for a perfect solution, I'll be satisfied with a “good enough” solution that performs well.

Problem Statement:

Say you have all or a subset of the following tiles available (this is the combination of all possible 4-bit patterns mapped to the right, up, left and down directions):

alt text http://img189.imageshack.us/img189/3713/basetileset.png

You are provided a grid where some cells are marked (true) and others not (false). This could be generated by a perlin noise algorithm, for example. The goal is to fill this space with tiles so that there are as many complex tiles as possible. Ideally, all tiles should be connected. There might be no solution for some input values (available tiles + pattern). There is always at least one solution if the top-left, unconnected tile is available (that is, all pattern cells can be filled with that tile).

Example:

Images left to right: tile availability (green tiles can be used, red cannot), pattern to fill and a solution

alt text http://img806.imageshack.us/img806/2391/sampletileset.png + alt text http://img841.imageshack.us/img841/7/samplepattern.png = alt text http://img690.imageshack.us/img690/2585/samplesolution.png

What I tried:

My brute-force implementation attempts every possible tile everywhere and keeps track of the solutions that were found. Finally, it chooses the solution that maximizes the total number of connections outgoing from each of the tiles. The time it takes is exponential with regard to the number of tiles in the pattern. A pattern of 12 tiles takes a few seconds to solve.

Notes:

As I said, performance is more important than perfection. However, the final solution must be properly connected (no tile pointing to a tile which doesn't point to the original tile). To give an idea of scope, I'd like to handle a pattern of 100 tiles under about 2 seconds.

Answer 1

For 100-tile instances, I believe that a dynamic program based on a carving decomposition of the input graph could fit the bill.

Carving decomposition

In graph theory, a carving decomposition of a graph is a recursive binary partition of its vertices. For example, here's a graph

1--2--3
|  |
|  |
4--5

and one of its carving decompositions

     {1,2,3,4,5}
     /         \
  {1,4}        {2,3,5}
  /   \        /     \
{1}   {4}  {2,5}     {3}
           /   \
         {2}   {5}.

The width of a carving decomposition is the maximum number of edges leaving one of its partitions. In this case, {2,5} has outgoing edges 2--1, 2--3, and 5--4, so the width is 3. The width of a kd-tree-style partition of a 10 x 10 grid is 13.

The carving-width of a graph is the minimum width of a carving decomposition. It is known that planar graphs (in particular, subgraphs of grid graphs) with n vertices have carving-width O(√n), and the big-O constant is relatively small.

Dynamic program

Given an n-vertex input graph and a carving decomposition of width w, there is an O(2^w n)-time algorithm to compute the optimal tile choice. This running time grows rapidly in w, so you should try decomposing some sample inputs by hand to get an idea of what kind of performance to expect.

The algorithm works on the decomposition tree from the bottom up. Let X be a partition, and let F be the set of edges that leave X. We make a table mapping each of 2^|F| possibilities for the presence or absence of edges in F to the optimal sum on X under the specified constraints (-Infinity if there is no solution). For example, with the partition {1,4}, we have entries

{} -> ??
{1--2} -> ??
{4--5} -> ??
{1--2,4--5} -> ??

For the leaf partitions with only one vertex, the subset of F completely determines the tile, so it's easy to fill in the number of connections (if the tile is valid) or -Infinity otherwise. For the other partitions, when computing an entry of the table, try all different connectivity patterns for the edges that go between the two children.

For example, suppose we have pieces

                       |
.    .-    .-    -.    .
     |                 

The table for {1} is

{} -> 0
{1--2} -> 1
{1--4} -> -Infinity
{1--2,1--4} -> 2

The table for {4} is

{} -> 0
{1--4} -> 1
{4--5} -> 1
{1--4,4--5} -> -Infinity

Now let's compute the table for {1,4}. For {}, without the edge 1--4 we have score 0 for {1} (entry {}) plus score 0 for {4} (entry {}). With edge 1--4 we have score -Infinity + 1 = -Infinity (entries {1--4}).

{} -> 0

For {1--2}, the scores are 1 + 0 = 1 without 1--4 and 2 + 1 = 3 with.

{1--2} -> 3

Continuing.

{4--5} -> 0 + 1 = 1 (> -Infinity = -Infinity + (-Infinity))
{1--2,4--5} -> 1 + 1 = 2 (> -Infinity = 2 + (-Infinity))

At the end we can use the tables to determine an optimal solution.

Finding a carving decomposition

There are sophisticated algorithms for finding good carving decompositions, but you might not need them. Try a simple binary space partitioning scheme.