2D PHP图案创建算法

Question

2D PHP图案创建算法

4

我正在寻找一种算法，可以基于规则帮助我构建2D图案。我的想法是，我可以使用给定的参数编写脚本，它将返回一个随机的、最多由规定长度的二维序列组成的结果。

我的计划是利用这个算法生成基于规则的图像模式。例如，像素分形或游戏关卡中的精灵等可能会使用这种算法。

例如，假设您可以使用A、B、C和D来创建该图案。规则是C和A永远不能相邻，而D始终跟在C后面。接下来，假设我想要一个4x4大小的图案。以下结果将遵守所有规则:

A B C D
B B B B
C D B B
C D C D

是否有现成的库可以进行这样的计算？我能阅读哪些数学公式呢？

- Xeoncross

1

什么样的“规则”？这种“规则”的格式是什么？ - mauris

现在只是关于当前符号北/东/南/西方向上的基本规则。我想支持X个空格内的符号也很不错（但可能会慢得多）。 - Xeoncross

http://properundead.com/2009/03/cave-generator.html - Xeoncross

3个回答

1

定义您的规则数据结构；即定义规则可以封装的操作集，并定义可用的交叉引用。完成此操作后，您应该更清楚地了解使用哪种类型的算法将这些规则应用于潜在结果集。

- Paul Sonier

1

假设您的规则仅限于"类型X允许在其左/右/上/下紧邻类型Y"，则可能会出现生成可能模式计算困难的情况。请查看Wang Tiles（Grunbaum和Shephard的书Tilings and Patterns是一个很好的来源），您将看到使用状态集定义Wang Tiles集合的情况。适当的这些集合是图灵完备的。

对于小矩形或您的规则集，这可能只是学术上的兴趣。如其他地方所述，回溯方法可能适用于您的规则集 - 在这种情况下，您可能需要考虑适当的启发式方法来确定向网格添加新组件的顺序。同样，根据您的规则集，其他方法可能有效。例如，如果您的规则集允许多个解决方案，则在尝试填补剩余空白之前，随机分配许多项目到网格中可能会有很大帮助。

- borrible

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Femaref · Accepted Answer

虽然在运行时效率上相对低下，但回溯算法经常用于解决这种问题。

它遵循一种简单的模式，如果编写正确，您可以轻松地将规则集替换为它。