这篇文章描述了我的
Linjat益智
游戏的关卡生成器。 无需准备即可阅读帖子，但是如果您在多个级别玩游戏，则会更容易吸收。 我
将源代码
发布在github上 ； 本文讨论的所有内容都在
src/main.cc 。
样品后计划：
- Linjat是一种逻辑游戏，您需要在其中用线关闭网格中的所有数字和点。
- 难题是通过使用求解器，生成器和优化器的组合来生成的。
- 求解器尝试以人的方式解决难题，并为每个难题分配兴趣等级。
- 拼图生成器的设计使其可以轻松更改拼图的一部分（数字），同时更改所有其他部分（点），从而使拼图保持可解决的状态。
- 拼图优化器反复解决这些关卡，并从当前发现的最有趣的关卡中产生新的变化。
规则
不幸的是，要了解关卡生成器的工作原理，您需要了解游戏规则。 幸运的是，它们非常简单。 拼图由一个包含空正方形，数字和点的网格组成。 一个例子：
玩家的目标是在三个条件下通过每个数字画一条垂直或水平线：
- 穿过数字的线的长度必须与数字相同。
- 线不能相交。
- 所有点必须用线封闭。
解决方案示例：
万岁！ 游戏设计已经准备就绪，UI已经实现，现在剩下的唯一一件事就是找到数百个好拼图。 对于此类游戏，尝试手动创建此类拼图通常没有任何意义。 这是计算机工作。
要求条件
是什么让这个游戏的谜题好？ 我倾向于相信益智游戏可以分为两类。 在某些游戏中，您需要从头到尾探索复杂的状态空间（例如，
推箱子或“
尖峰时刻” ），并且游戏中存在哪些状态可能并不明显。 在有些游戏中，从一开始就知道所有状态，我们通过消除不必要的状态（例如
Sudoku或
Picross ）来逐步形成状态空间。 我的游戏肯定属于第二类。
玩家对这些不同类型的谜题有非常不同的要求。 在第二种情况下，他们希望只能通过演绎来解决难题，并且他们永远都不需要回去/猜测/反复试验
[0] [1] 。
仅知道难题是否只能通过逻辑来解决还不够。 此外，我们需要以某种方式了解所创建的拼图的质量。 否则，大多数水平将只是微不足道的炉渣。 在理想情况下，也可以使用此原理创建平滑的进度曲线，以便随着玩家在游戏中的进行，等级逐渐变得更加困难。
解算器
满足这些要求的第一步是创建为此目的而优化的游戏求解器。 回溯求解器使您可以快速而准确地确定难题是否可以解决。 此外，可以对其进行修改以确定解决方案是否唯一。 但是他无法给出难题的真正复杂性，因为人们以不同的方式解决难题。 解算者必须模仿人类的行为。
一个人如何解决这个难题？ 以下是游戏教程中教导的一些明显的动作：
- 如果只能从一个数字到达一个点，则要关闭一个点，您需要从该数字画一条线。 在此示例中，只能从三个点到达该点，而不能从四个点到达：
这导致这种情况：
- 如果该线不适合一个方向，则必须将其放置在另一个方向上。 在上面的示例中，这四个不能再垂直放置，因此我们知道它将是水平的：
- 如果已知长度X的线必须在某个位置（垂直/水平），并且没有足够的空白空间来在两侧放置X线空单元，那么您需要在中间覆盖几个正方形。 如果在上面显示的示例中四个是三个，那么我们将不知道它是一直延伸到右边还是左边。 但是我们知道该线应该覆盖两个中间的正方形：
类似的推理是游戏的基础。 玩家寻求伸展一点线的方法，然后再次检查该区域，因为它可以给他提供信息以得出另一个合乎逻辑的结论。 创建一个遵循这些规则的求解器就足以确定
一个人是否可以不退而解决难题。
但是，这并没有告诉我们有关该级别的复杂性或趣味性的任何信息。 除了可解性，我们还需要以某种方式量化复杂性。
评级功能的一个明显的第一个想法：解决难题所需的动作越多，难度就越大。 在其他游戏中，这可能是一个很好的指标，但是我的最有可能比玩家允许的移动次数更重要。 如果一个玩家可以做出10个合乎逻辑的结论，那么他很可能会很快找到其中一个。 如果只有一个正确的举动，将需要更多的时间。
也就是说，作为第一个近似值，我们需要决策树深而窄：从头到尾的移动之间存在长期的依赖关系，并且在每个时刻，只有少数几种方法可以沿链条向上移动
[2] 。
我们如何确定树的宽度和深度？ 对于难题和对所创建树的评估的单一解决方案将无法给出确切的答案。 进行移动的确切顺序会影响树的形状。 我们需要考虑所有可能的解决方案，并对其进行处理，例如针对最佳和最坏情况进行优化。 我熟悉
益智游戏中搜索图的
粗略搜索技术，但是对于这个项目，我想创建一个单遍求解器，而不是穷举搜索。 由于处于优化阶段，我试图确保求解器的运行时间不是以秒为单位，而是以毫秒为单位。
我决定不这样做。 取而代之的是，我的求解器实际上并没有一次做出任何动作，而是分层解决了这个难题：采取一种状态，他找到了所有可以做出的有效动作。 然后他同时应用所有这些动作，并以新的状态重新开始。 然后，将层数和在一层上找到的最大移动数用作整个搜索树的深度和宽度的近似值。
这是解决该模型难题之一的方法。 虚线是在求解器的此层上拉伸的线，实线是未更改的线。 绿线是正确的长度，红线尚未完成。
下一个问题是，玩家做出的所有举动都是相等的。 我们在本节开头列出的只是常识。 这是一个更复杂的推导规则的示例，对其进行搜索将需要更多的思考。 考虑以下字段：
C和D中的点只能被五个和中间四个点覆盖（并且没有一个数字可以同时覆盖两个点）。 这意味着中间的四个应该覆盖两个点之一，因此不能用来覆盖A。因此，点A应该封闭左下角的四个。
显然，认为这种推理链等于简单的结论“这一点只能从这个数字得出”是愚蠢的。 在评估功能中是否可以对这些更复杂的规则给予更多的重视？ 不幸的是，在基于层的求解器中，这是不可能的，因为不能保证以最低的成本找到解决方案。 这不仅是一个理论上的问题-在实践中，经常发生该领域的一部分可以通过一个复杂的论点或一系列简单得多的举动来解决的问题。 实际上，基于层的求解器会找到最短的路径，而不是最不昂贵的路径，并且这不能反映在评估函数中。
结果，我做出了这个决定：我更改了求解器，以便每一层仅包含一种类型的推理。 该算法以复杂度的近似顺序绕过推理规则。 如果规则找到了一些移动，则将其应用，并且迭代结束，而下一次迭代将从一开始就开始列表。
然后为该决策分配评估：根据决策层中使用的一条规则为每一层分配成本。 这仍然不能保证解决方案将是最低成本的，但是如果正确选择权重，那么如果有便宜的解决方案，该算法至少不会找到昂贵的解决方案。
而且，这非常类似于人们解决难题的方式。 他们首先尝试找到简单的解决方案，然后仅在没有简单动作的情况下才开始主动动脑子。
发电机组
上一节确定了特定级别的好坏。 但这还不够，我们仍然需要以某种方式生成级别，以便求解器可以评估它们。 随机产生的世界是不可能解决的，更不用说有趣了。
主要思想（绝不是什么新鲜事物）是求解器和生成器的交替使用。 让我们从一个难题开始，这可能是无法解决的：只需将2到5个数字放在单元格的随机正方形中即可：
解算器可以工作，直到可以进一步发展为止：
然后，生成器以点的形式将更多信息添加到拼图中，此后继续执行求解器。
在这种情况下，添加到求解器的点不足以进一步开发。 然后，生成器将继续添加新点，直到满足求解器为止：
然后求解器继续他的常规工作：
此过程将继续进行，直到解决难题为止，或者直到剩下更多信息要添加为止（例如，当从数字可以到达的每个单元格已经包含一个点时）。
仅当添加的新信息无法使先前得出的任何结论不正确时，此方法才有效。 将数字添加到网格时，这将很难做到
[3] 。 但是，向该字段添加新点具有此属性。 至少是出于我在该程序中使用的推理规则。
该算法应在哪里加分？ 最后，我决定将它们添加到空白处，该空白处在初始状态下可以用尽可能多的行封闭，以便每个点都试图提供尽可能少的信息。 我没有尝试将特定点放在求解器被卡住的那一刻对解决难题有帮助的地方。 这产生了一个非常方便的效果：难题开始时的大多数要点似乎完全没有用，这使难题比实际难度更大。 如果这一切都是玩家可以采取的许多显而易见的举动，但由于某种原因，其中的任何一个都不能正常工作。 结果，证明了拼图生成器的行为有点像猪。
这个过程并不总是可以创建一个解决方案，但是它相当快（大约50-100毫秒），因此要生成一个关卡，您只需重复几次即可。 不幸的是，他通常会创造平庸的难题。 从一开始就有太多明显的动作，该字段很快就被填满，决策树变得相当浅。
优化器
上述过程创建了平庸的难题。 在最后阶段，我将这些级别用作优化过程的基础。 它的工作原理如下。
优化器创建一个包含最多10个拼图选项的池。 用新生成的随机拼图初始化池。 在每次迭代中，优化器从池中选择一个拼图并执行其变异。
突变会删除所有点，然后稍微改变数字（即减少/增加随机选择的数字的值，或将数字移动到网格中的另一个单元格）。 您可以同时将多个突变应用于该字段。 然后，我们以上一节中描述的特殊级别生成模式运行求解器。 他为难题添加了足够的分数，以便可以再次解决。
之后，我们再次以正常模式启动求解器。 在此运行期间，求解器监视a）决策树的深度，b）对不同类型规则的需求的频率，c）在不同时间点的决策树的宽度。 拼图是根据上述标准进行评估的。 评估功能更喜欢深度和狭义的解决方案，复杂程度的提高也为需要更复杂推理规则的难题增添了更多的分量。
然后，将新拼图添加到池中。 如果池中包含10个以上的难题，那么最差的难题将被丢弃。
此过程重复了几次（大约花了10,000-50000次迭代）。 之后，拼图的最高评级版本将保存到拼图级别数据库。 这是一次优化运行中最佳难题的进度，如下所示：
我尝试使用其他方式进行结构优化。 在一个版本中，使用了模拟退火；其他版本是具有各种交叉操作的遗传算法。 没有一个解决方案比朴素的算法执行得更好，它还具有返回到顶部的选项池。
独特的单一解决方案
当难题具有独特的独特解决方案时，就会产生有趣的困难。 是否有可能让玩家假设有一个解决方案并据此得出结论？ 如果谜题生成器建议玩家这样做，那会公平吗？
我在HackerNews上的帖子中说过，有四种方法可以解决这种情况：
- 从一开始就声明解决方案的唯一性，并迫使生成器创建需要这种推理的关卡。 这是一个错误的决定，因为它会使对规则的理解变得复杂。 通常这些都是人们忘记的细节。
- 不要保证决策的唯一性：可能有很多决策，并且全都做出 实际上，这不能解决问题，但是可以解决问题。
- 只需假设这是一个非常罕见的事件，实际上这并不重要。 （这是初始实现中使用的解决方案。）
- 更改难题生成器，使其不会生成对解决方案的唯一性有所帮助的难题。 （可能是正确的解决方案，但需要其他工作。）
最初，我选择了后者，这是一个可怕的错误。 事实证明，我只考虑了解决方案的唯一性导致信息泄漏的一种方式，而这种方式实际上很少见。 但是还有其他。 实际上，其中之一存在于我生成的每个级别，并且常常导致解决方案变得微不足道的事实。 因此，在2019年5月，我使用第三个选项更改了Hard和Expert模式。
最烦人的情况是在此字段中用虚线表示的演习：
为什么狡猾的玩家会得出这样的结论？ 一个平局可以覆盖四个相邻的正方形中的任何一个。 它们都没有点，因此不必用线覆盖。 并且下面的正方形没有与任何其他数字的叠加。 如果有一个解决方案，则其他数字覆盖其余三个正方形，而两个数字将其下面的正方形封闭时，情况就是这样。
解决方案是在识别此类情况时再增加一些要点：
另一个常见的情况是此字段中带有虚线的破折号：
两者的左侧和顶部的正方形相同。 他们中没有一个有重点，从任何其他数字都无法达到。 派克覆盖顶部正方形的任何解决方案都将具有对应的解决方案，其中将其封闭左正方形，反之亦然。 如果只有一个唯一的解决方案，那么就不可能了，而推销应该已经覆盖了底部的方框。
我以“如果伤了就别碰它”的方式来决定这种情况。 求解器在优先级列表的早期阶段应用了此规则，并为此类举动分配了负面影响。 具有此功能的谜题通常会被优化程序丢弃，而剩下的很少的谜题会在最终选择已发布游戏的关卡阶段被丢弃。
这不是一个完整的列表，在进行游戏测试并故意寻找错误的过程中，我发现了许多其他解决独特问题的规则。 但是大多数游戏似乎都很稀有，而且足以找到它们，因此它们并没有大大简化游戏。 如果有人使用这种推理解决了难题，那么我不会将其归咎于他们。
结论
最初，该游戏是作为拼图程序生成中的实验而开发的。 游戏的设计和生成器是紧密相连的，因此技术本身很难直接应用于其他游戏。
我没有答案的问题：在程序生成上进行此类努力的投资本身是否合理？
玩家对关卡设计的反馈意见很有争议。在积极的评论中，通常会说，难题总是让人感到有些棘手。在大多数负面评论中，他们写信给我说游戏缺乏复杂性。在婴儿期我仍然有一些困惑，而且我非常喜欢生成器，以至于我很可能会为他们使用类似的过程方法。我将只更改一件事：从一开始，我将进行主动的游戏测试并寻找错误。注意事项
[0]或者，至少在我看来。但是当我看着玩家的生活时，几乎有一半的玩家只是猜测，然后反复遍历他们。哦好[1]我的文章的读者还应该阅读解决扫雷并使之更好的文章Magnus Hoff。[2]我将澄清一棵树的深度/狭窄度是我认为对我的游戏有意义的指标，而不是对所有其他难题而言重要的指标。例如，有一个很好的论据认为，“高峰时间”难题是有趣的，如果它有几种方法可以解决几乎但并非完全相同的长度。但这之所以发生，是因为“高峰时间”是一款能够找到最短解决方案的游戏，而不仅仅是任何解决方案。[3]不包括单位的增加。拼图的第一个版本中没有圆点，并且计划是供生成器在必要时添加单位。但这似乎太过严格了。