algorithm - “pattern-filling with tiles” 谜题

Question

我在为基于图 block 的游戏编写随机关卡生成器时遇到了一个有趣的问题。我已经为它实现了一个强力求解器，但它的速度呈指数级下降，而且绝对不适合我的用例。我不一定要寻找完美的解决方案，我会对性能良好的“足够好”的解决方案感到满意。

问题陈述:

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

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

为您提供了一个网格，其中一些单元格被标记 (true)，而其他单元格未标记 (false)。例如，这可以由柏林噪声算法生成。目标是用瓷砖填充这个空间，以便有尽可能多的复杂瓷砖。理想情况下，所有瓷砖都应该连接起来。某些输入值(可用图 block + 图案)可能没有解决方案。如果左上角未连接的图 block 可用(即，所有图案单元格都可以用该图 block 填充)，则始终至少有一个解决方案。

示例:

图像从左到右:瓷砖可用性(可以使用绿色瓷砖，不能使用红色瓷砖)、要填充的图案和解决方案

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

我尝试了什么:

我的蛮力实现尝试了所有可能的瓷砖，并跟踪找到的解决方案。最后，它选择最大化从每个图 block 传出的连接总数的解决方案。它花费的时间与图案中的瓷砖数量成指数关系。 12 block 瓷砖的图案需要几秒钟才能解决。

注意事项:

正如我所说，性能比完美更重要。但是，最终解决方案必须正确连接(没有指向未指向原始图 block 的图 block 的图 block )。为了给出范围的概念，我想在大约 2 秒内处理 100 个图 block 的图案。

Answer 1

对于 100-tile 实例，我相信基于输入图雕刻分解的动态程序可以满足要求。

雕刻分解

在图论中，图的雕刻分解是其顶点的递归二元划分。例如，这是一个图表

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) 时间的算法来计算最佳图 block 选择。此运行时间在 w 中快速增长，因此您应该尝试手动分解一些样本输入，以了解预期的性能。

该算法自下而上地作用于分解树。令 X 为分区，令 F 为离开 X 的边集。我们制作一个表，将 F 中存在或不存在边的 2^|F| 种可能性映射到最佳总和在指定约束下的 X 上(-Infinity 如果没有解决方案)。例如，分区 {1,4} , 我们有条目

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

对于只有一个顶点的叶子分区，F 的子集完全决定了瓦片，因此很容易填写连接数(如果瓦片有效)或 -Infinity 否则。对于其他分区，在计算表的条目时，为两个 child 之间的边尝试所有不同的连接模式。

例如，假设我们有棋子

                       |
.    .-    .-    -.    .
     |                 

{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 {1} 得分为 0 (条目 {} )为 {4} 加分 0 (条目 {})。带边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))

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

寻找雕刻分解

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