algorithm - The “pattern-filling with tiles” puzzle -

i've encountered interesting problem while programming random level generator tile-based game. i've implemented brute-force solver exponentially slow , unfit use case. i'm not looking perfect solution, i'll satisfied “good enough” solution performs well.

problem statement:

say have or subset of following tiles available (this combination of possible 4-bit patterns mapped right, up, left , down directions):

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

you provided grid cells marked (true) , others not (false). generated perlin noise algorithm, example. goal fill space tiles there many complex tiles possible. ideally, tiles should connected. there might no solution input values (available tiles + pattern). there @ least 1 solution if top-left, unconnected tile available (that is, pattern cells can filled tile).

example:

images left right: tile availability (green tiles can used, red cannot), pattern fill , 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 tried:

my brute-force implementation attempts every possible tile everywhere , keeps track of solutions found. finally, chooses solution maximizes total number of connections outgoing each of tiles. time takes exponential regard number of tiles in pattern. pattern of 12 tiles takes few seconds solve.

notes:

as said, performance more important perfection. however, final solution must connected (no tile pointing tile doesn't point original tile). give idea of scope, i'd handle pattern of 100 tiles under 2 seconds.

for 100-tile instances, believe dynamic program based on carving decomposition of input graph fit bill.

carving decomposition

in graph theory, carving decomposition of graph recursive binary partition of vertices. example, here's graph

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

and 1 of carving decompositions

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

the width of carving decomposition maximum number of edges leaving 1 of partitions. in case, {2,5} has outgoing edges 2--1, 2--3, , 5--4, width 3. width of kd-tree-style partition of 10 x 10 grid 13.

the carving-width of graph minimum width of carving decomposition. known planar graphs (in particular, subgraphs of grid graphs) n vertices have carving-width o(√n), , big-o constant relatively small.

dynamic program

given n-vertex input graph , carving decomposition of width w, there o(2^w n)-time algorithm compute optimal tile choice. running time grows rapidly in w, should try decomposing sample inputs hand idea of kind of performance expect.

the algorithm works on decomposition tree bottom up. let x partition, , let f set of edges leave x. make table mapping each of 2^|f| possibilities presence or absence of edges in f optimal sum on x under specified constraints (-infinity if there no solution). example, partition {1,4}, have entries

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

for leaf partitions 1 vertex, subset of f determines tile, it's easy fill in number of connections (if tile valid) or -infinity otherwise. other partitions, when computing entry of table, try different connectivity patterns edges go between 2 children.

for example, suppose have pieces

                       | .    .-    .-    -.    .      |                  

the table {1} is

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

the table {4} is

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

now let's compute table {1,4}. {}, without edge 1--4 have score 0 {1} (entry {}) plus score 0 {4} (entry {}). edge 1--4 have score -infinity + 1 = -infinity (entries {1--4}).

{} -> 0 

for {1--2}, scores 1 + 0 = 1 without 1--4 , 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 end can use tables determine optimal solution.

finding carving decomposition

there sophisticated algorithms finding carving decompositions, might not need them. try simple binary space partitioning scheme.