在“图案填充砖”之谜 [英] The “pattern-filling with tiles” puzzle
问题描述
而编程的基于区块的游戏随机生成的水平我遇到了一个有趣的问题。我已经实现了一个强力解算器，但它是指数慢，绝对不适合我的使用情况。我不一定要找一个完美的解决方案，我会满足于足够好的解决方案，性能良好。
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.
问题描述：
假设你有全部或提供以下砖的一个子集（这是所有可能的4位模式映射到右的组合，上，左，下的方向）：
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):
您提供，其中一些细胞标记别人没有（假）的网格（真）。这可以通过一个Perlin杂算法来产生，例如。我们的目标是使得有尽可能多的复杂的瓦片尽可能来填补这个空间与瓷砖。理想的情况下，所有的瓷砖应连接。可能有一些输入值无解（可用砖+模式）。总是存在至少一种解决办法，如果左上角，未连接的瓦片是可用的（即，所有图案细胞可以填充有瓷砖）。
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).
示例：
图片从左到右依次为：瓦可用性（青瓦可以使用，红色不能），图案填充和解决方案
Images left to right: tile availability (green tiles can be used, red cannot), pattern to fill and a solution
+ =
我的尝试：
我的蛮力实现尝试一切可能的瓦随处可见，并跟踪找到的解决方案。最后，它选择最大化连接传出从每个切片的总数的溶液。所花费的时间是指数对于瓷砖图案的数目。 12瓦的模式需要几秒钟来解决。
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.
注：
正如我所说的，性能比完美更重要。然而，最终的解决方案必须正确连接（无瓦片指向不指向原来的砖一瓦）。为了给范围的想法，我想处理下2秒的100瓦的模式。
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.
推荐答案
有关100瓦情况下，我认为，基于输入图的雕刻分解一个动态的方案可以适合该法案。
For 100-tile instances, I believe that a dynamic program based on a carving decomposition of the input graph could fit the bill.
雕刻分解的
在图论，图的雕刻分解为它的顶点递归二元分割。例如，这里有一个图
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
和它的雕刻分解一个
{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的kd树式分区的宽度10格为13。
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.
的雕刻宽度的曲线图是一个雕刻分解的最小宽度。据了解，平面图（特别是格图的子图）有n个顶点的有雕刻宽度O（√N），和大O常数相对较小。
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.
动态程序的
给定一个正的顶点输入图形和宽度的雕刻分解W，有一个O（2 是W N） - 时间算法来计算最优瓷砖的选择。这个运行时间的增长迅速，W，所以你应该尽量分解一些样本输入由专人得到一个什么样的表现期望的想法。
Given an n-vertex input graph and a carving decomposition of width w, there is an O(2w 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.
该算法上从下往上的分解树。设X是一个分区，并让F为边集的离开X.我们做一个表映射每2 | F | 对于F中的边缘的presence或不存在可能性下指定的约束条件的X最优总和（-Infinity如果没有解决）。例如，分区 {1,4} ，我们有项
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.
例如，假设我们有个
|
. .- .- -. .
|
的表 {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 我们有得分负无穷大+ 1 =负无穷大（项 {1--4} ）。
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
有关 {1--2} ，分数为1 + 0 = 1无 1--4 和2 + 1 = 3。
For {1--2}, the scores are 1 + 0 = 1 without 1--4 and 2 + 1 = 3 with.
{1--2} -> 3
继续。
{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.
查找雕刻分解的
有寻找好的雕刻分解复杂的算法，但你可能并不需要它们。尝试一个简单的二进制空间分割方案。
There are sophisticated algorithms for finding good carving decompositions, but you might not need them. Try a simple binary space partitioning scheme.
这篇关于在“图案填充砖”之谜的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
