"图案填充瓷砖"拼图

Question

在为基于图块的游戏编程随机级别生成器时,我遇到了一个有趣的问题.我为它实现了一个强力求解器,但它指数速度慢,绝对不适合我的用例.我不一定在寻找一个完美的解决方案,我会对一个表现良好的"足够好"的解决方案感到满意.

问题陈述:

假设您有以下可用的全部或部分可用(这是映射到右,上,左和下方向的所有可能的4位模式的组合):

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

您将获得一个网格,其中一些单元格被标记(true)而另一些单元格未被标记(false).例如,这可以通过perlin噪声算法生成.目标是用瓷砖填充这个空间,以便有尽可能多的复杂瓷砖.理想情况下,应连接所有瓷砖.某些输入值可能没有解决方案(可用的tile + pattern).如果左上角,未连接的图块可用(即,所有图案单元格可以用该图块填充),则始终存在至少一个解决方案.

例:

图像从左到右:图块可用性(可以使用绿色图块,红色图案不可用),图案填充和解决方案

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.我们/ img690/2585/samplesolution.png

我尝试了什么:

我的蛮力实施尝试了所有可能的区域,并跟踪找到的解决方案.最后,它选择最大化从每个图块传出的连接总数的解决方案.对于图案中的图块数量,所花费的时间是指数的.12个图块的图案需要几秒钟才能解决.

笔记:

正如我所说,表现比完美更重要.但是,必须正确连接最终解决方案(没有指向不指向原始图块的图块的图块).为了了解范围,我想在大约2秒内处理100个图块的模式.

Answer 1

对于100个图块实例,我认为基于输入图形的雕刻分解的动态程序可以适合该法案.

雕刻分解

在图论中,图的雕刻分解是其顶点的递归二进制分区.例如,这是一个图表

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

和其中一个雕刻分解

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

雕刻分解的宽度是离开其一个分区的最大边数.在这种情况下,{2,5}具有外边缘2--1,2--3和5--4,因此宽度为3. 10 x 10网格的kd树样式分区的宽度为13.

图的雕刻宽度是雕刻分解的最小宽度.众所周知,具有n个顶点的平面图(特别是网格图的子图)具有雕刻宽度O(√n),并且大O常数相对较小.

动态程序

给定n顶点输入图和宽度为w的雕刻分解,存在O(2 ^w n)时间算法来计算最佳图块选择.这个运行时间在w中快速增长,因此您应该尝试手动分解一些样本输入,以了解期望的性能类型.

该算法从下到上在分解树上工作.设X是一个分区,让F为离开X的边集.我们制作一个映射2 ^{| F |的表} F中边缘的存在与否的可能性在指定约束下的X上的最佳和(-Infinity,如果没有解).例如,对于分区{1,4},我们有条目

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

对于只有一个顶点的叶子分区,F的子集完全确定了tile,因此很容易填充连接数(如果tile是有效的)或者-Infinity.对于其他分区,在计算表的条目时,请尝试两个子节点之间的边的所有不同连接模式.

例如,假设我们有件

                       |
.    .-    .-    -.    .
     |                 

表{1}是

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

表{4}是

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

现在让我们计算表格{1,4}.对于{}无边缘1--4,我们有得分0 {1}(项{}),加上得分0 {4}(项{}).有了边缘,1--4我们得分-Infinity + 1 = -Infinity(条目{1--4}).

{} -> 0

因为{1--2},分数是1 + 0 = 1没有1--4和2 + 1 = 3.

{1--2} -> 3

继续.

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

最后,我们可以使用表格来确定最佳解决方案.

寻找雕刻分解

有很复杂的算法可以找到好的雕刻分解,但你可能不需要它们.尝试一个简单的二进制空间分区方案.

Answer 2

作为基础，请看一下我之前在搜索中给出的答案。爬山搜索程序是每个程序员都应该拥有的工具，因为它们比普通的暴力求解器工作得更好。

在这里，即使是相对糟糕的搜索算法也有一个优点，即它不会生成非法板，从而大大减少了预期的运行时间。