类似Flow Free的游戏中，用什么来创建随机关卡？

Question

我需要一些建议。 我正在开发一个类似于Flow Free的游戏，其中游戏板由网格和有颜色的圆点组成，用户必须将相同颜色的圆点连接起来，而不重叠其他线，并使用面板上所有的空闲空间。

我的问题是关于级别创建。我希望让关卡随机生成(并至少能够自己解决，以便可以给玩家提示)，但我不知道要使用什么算法。 有什么建议吗？

注意：图像显示了Flow Free的目标，这也是我正在开发的目标。

谢谢你的帮助。 :)

- user1239714

---

好的，这将生成可怕且有时非常无聊（或者其他不想要的）关卡，所以这不是一个答案，但也许可以帮助某些人进行头脑风暴：您可以选择一个空闲的方块，然后重复选择一个随机的空闲邻居方块来延伸路径，直到结束路径并开始新路径。这当然可能导致只允许一个或两个节点路径的布局。也许并查集数据结构可以帮助解决这个问题...或者使用一些不太琐碎的图形算法。 - user395760

这个问题与新冠病毒有什么关系？ - GoojajiGreg

Answer 1

考虑使用一对更简单、更易管理的算法来解决问题：一个可靠地创建简单的预先解决的棋盘的算法，以及一个重新排列流程以使简单的棋盘更加复杂的算法。

第一部分，构建一个简单的预解决板，如果你正在使用n个流在nxn网格上，则是微不足道的（如果你希望如此）：

- 对于每个流... - 将头点放在第一个开放列的顶部。 - 将尾巴点放在该列的底部。

或者，您可以提供自己制作的起始板以传递给第二部分。这个阶段的唯一目标是构建一个有效的板，即使它是微不足道的或事先确定的，所以保持它简单是值得的。

第二部分，重新排列流程，涉及循环遍历每个流程，看看哪个流程可以与其相邻的流程一起增长和缩小：

- 对于一些迭代次数... - 选择一个随机流程f。 - 如果f处于最小长度(比如3个方块长)，则跳过下一个迭代，因为我们现在无法缩小f。 - 如果f的头点紧邻另一个流程g的点(如果有多个g可供选择，则随机选择一个)... - 将f的头点沿着其流程移动一个方块(即向尾部的方向移动一个方块)。f现在变短了一个方块，有一个空方块。(拼图现在未解决。) - 将g的相邻点移到由f腾出的空方块中。现在，g的点移动后会有一个空方块。

从g中流出液体，填补那个空位。现在g比这次迭代开始时多了一个方块。（谜题也已经被解决）

对f的尾点重复上一步骤。

目前的方法存在局限性（点将始终是相邻的），但易于扩展：

• 添加一步循环遍历流f的主体，寻找更棘手的方法来交换空间和其他流...
• 添加一步防止点移动到旧位置...
• 添加您想到的任何其他想法。

这里的总体解决方案可能不如您所期望的理想解决方案，但现在您有两个简单的算法，可以进一步完善，以发挥一个大而全面的算法的作用。最终，我认为这种方法是可管理的、不神秘的、易于调整的，如果没有别的，就是一个好的起点。

---

更新： 我根据上述步骤编写了一个概念验证。从下面的第一个 5x5 网格开始，该过程产生了随后的 5 个不同的棋盘。有些有趣，有些则不是，但它们总是合法的，且具有已知的一个解决方案。

起始点

5 种随机结果 （对于错位的截图表示抱歉）

为了充分说明，这里再来放一张8x8的随机图。起点跟上面那个简单列的方法一样。

- user1201210

---

@GrijeshChauhan 谢谢，Grijesh。我将“流程”数据写成了HTML表格，并对它们进行了截屏。我认为它们在概念验证工作中表现得相当不错。 :) - user1201210

不错！颜色也很好。...我突然想到你可以使用 dia，也许你会喜欢它。 - Grijesh Chauhan

这个过程只生成地图，其中每个“头”都紧挨着另一个“头”。这些地图非常无聊 :( - Ivan Kuckir

@IvanKuckir 我最初认为头/尾会相邻，但并非总是如此。请看上面的8x8图像。它是使用此过程生成的，但 h7 旁边没有其他头/尾。h0 旁边也没有其他头/尾。同样适用于 g0、f0、e0、d11、d0、b11 等等。实际上，在16个头/尾中，我只数到5个是相连的。至于无聊的图形，你得到你所付出的代价。;) 答案展示了如何以可靠和易于接近的方式创建保证可解决的图形。让它们变得有趣则取决于开发人员。 - user1201210

对于这个算法我给出一个赞，我已经在我的应用程序中实现了它，并且它对我来说运行得非常好。我唯一想要补充的是请修改一下“如果f的头部点紧挨着另一个流g的点”的那一行，它不是从流“g”中的任何一个点开始，而应该是从头部或尾部点开始，因为我们的流只能从头部或尾部扩展/缩小。当我第一次阅读这篇文章时有点困惑，但后来弄清楚了。如果您稍微修改一下这句话会更好。无论如何，谢谢。 - Muhammad

Answer 2

更新的回答：我使用“双谜题”思想实现了一个新的生成器。这比我所知道的任何先前方法都可以生成更稀疏和高质量的谜题。代码在github上。我会尝试写更多关于它如何工作的细节，但这里有一个例子谜题： 旧的回答： 我在我的numberlink求解器和生成器中实现了以下算法。它强制执行规则，即路径永远不能触及自己，在大多数“极限”numberlink应用程序和谜题中很常见。

1. 首先，以简单、确定性的方式用2x1多米诺骨牌铺满棋盘。如果在奇数区域纸张上无法这样做，则保留右下角作为单个方块。
2. 然后，通过随机旋转相邻的多米诺骨牌对来随机洗牌。在宽度或高度等于1的情况下不进行此操作。
3. 现在，在奇数区域纸张的情况下，将右下角与其邻居多米诺骨牌之一相连。这总是可能的。
4. 最后，我们可以开始通过多米诺骨牌找到随机路径，同时在通过时将它们组合起来。特别注意不连接“相邻流”，这将创建“反弹”的谜题。
5. 在打印谜题之前，我们会尽可能地“压缩”使用的颜色范围。
6. 通过用.替换所有不是流头的位置来打印谜题。

我的numberlink格式使用ASCII字符而不是数字。这里是一个例子：

$ bin/numberlink --generate=35x20
Warning: Including non-standard characters in puzzle

35 20
....bcd.......efg...i......i......j
.kka........l....hm.n....n.o.......
.b...q..q...l..r.....h.....t..uvvu.
....w.....d.e..xx....m.yy..t.......
..z.w.A....A....r.s....BB.....p....
.D.........E.F..F.G...H.........IC.
.z.D...JKL.......g....G..N.j.......
P...a....L.QQ.RR...N....s.....S.T..
U........K......V...............T..
WW...X.......Z0..M.................
1....X...23..Z0..........M....44...
5.......Y..Y....6.........C.......p
5...P...2..3..6..VH.......O.S..99.I
........E.!!......o...."....O..$$.%
.U..&&..J.\\.(.)......8...*.......+
..1.......,..-...(/:.."...;;.%+....
..c<<.==........)./..8>>.*.?......@
.[..[....]........:..........?..^..
..._.._.f...,......-.`..`.7.^......
{{......].....|....|....7.......@..

我将它输入我的求解器中（使用相同的种子）：

$ bin/numberlink --generate=35x20 | bin/numberlink --tubes
Found a solution!
┌──┐bcd───┐┌──efg┌─┐i──────i┌─────j
│kka│└───┐││l┌─┘│hm│n────n┌o│┌────┐
│b──┘q──q│││l│┌r└┐│└─h┌──┐│t││uvvu│
└──┐w┌───┘d└e││xx│└──m│yy││t││└──┘│
┌─z│w│A────A┌┘└─r│s───┘BB││┌┘└p┌─┐│
│D┐└┐│┌────E│F──F│G──┐H┐┌┘││┌──┘IC│
└z└D│││JKL┌─┘┌──┐g┌─┐└G││N│j│┌─┐└┐│
P──┐a││││L│QQ│RR└┐│N└──┘s││┌┘│S│T││
U─┐│┌┘││└K└─┐└─┐V││└─────┘││┌┘││T││
WW│││X││┌──┐│Z0││M│┌──────┘││┌┘└┐││
1┐│││X│││23││Z0│└┐││┌────M┌┘││44│││
5│││└┐││Y││Y│┌─┘6││││┌───┐C┌┘│┌─┘│p
5││└P│││2┘└3││6─┘VH│││┌─┐│O┘S┘│99└I
┌┘│┌─┘││E┐!!│└───┐o┘│││"│└─┐O─┘$$┌%
│U┘│&&│└J│\\│(┐)┐└──┘│8││┌*└┐┌───┘+
└─1└─┐└──┘,┐│-└┐│(/:┌┘"┘││;;│%+───┘
┌─c<<│==┌─┐││└┐│)│/││8>>│*┌?│┌───┐@
│[──[└─┐│]││└┐│└─┘:┘│└──┘┌┘┌┘?┌─^││
└─┐_──_│f││└,│└────-│`──`│7┘^─┘┌─┘│
{{└────┘]┘└──┘|────|└───7└─────┘@─┘

我已经测试过用一个函数代替步骤（4），该函数会迭代地随机合并相邻路径。然而，这样生成的谜题更加密集，我认为上面的谜题已经足够密集了，难度也很大。

以下是我生成的不同大小的问题列表：https://github.com/thomasahle/numberlink/blob/master/puzzles/inputs3。

- Thomas Ahle

---

你知道如何消除长度为2的路径吗？ - Ivan Kuckir

如果您不喜欢长度为2的路径，您可以使用三格骨牌（L形或l形）来创建初始随机覆盖。这样做可能会更加困难，但由于转弯较少，可能会产生更稀疏的谜题，从而产生积极的效果。 - Thomas Ahle

另一种方法是运行一些启发式算法，尝试将剩余的长度为2的路径分割并重新分配到它们周围的路径上。 - Thomas Ahle

你知道吗，除了“单例”单元格外，你永远不会生成奇数长度的路径？ - Ivan Kuckir

Ivan：使用三格拼图应该可以解决那个问题。但是你应该知道，漂亮的稀疏谜题很少见。我搜索了所有的两种颜色的10x10谜题，经过对称性只有15个不同的谜题。 - Thomas Ahle

Answer 3

最直接创建这样一个级别的方法是找到一种解决方法。这样，您基本上可以生成任何随机起始配置，并通过尝试将其解决来确定它是否是有效级别。这将生成最多样化的级别。

即使您找到了其他生成级别的方法，您仍然需要应用此解决算法来证明生成的级别是否合适;)

暴力枚举

如果板的大小为NxN个单元格，还有N种颜色可用，则枚举所有可能的配置（无论它们是否形成实际路径连接起点和终点节点）会花费：

- N^2个单元格总数 - 2N个单元格已经占据了起点和终点节点 - N^2 - 2N个单元格的颜色尚未确定 - N种可用颜色。 - N^(N^2 - 2N)种可能的组合。

因此，

- 对于N=5，这意味着有5^15 = 30517578125种组合。 - 对于N=6，这意味着有6^24 = 4738381338321616896种组合。

换句话说，可能的组合数量一开始就非常高，但一旦您开始扩大棋盘，它也会以惊人的速度增长。

限制每种颜色的单元格数

显然，我们应该尽可能地减少配置的数量。一种方法是考虑每种颜色的起始单元格和结束单元格之间的最小距离（“dMin”）-我们知道该颜色至少应有这么多个单元格。可以使用简单的泛洪填充或Dijkstra算法来计算最小距离。 （注意，此下一节仅讨论单元格的数量，而不涉及它们的位置）

在您的示例中，这意味着（不计算起点和终点单元格）

dMin(orange) = 1
dMin(red) = 1
dMin(green) = 5
dMin(yellow) = 3
dMin(blue) = 5

这意味着在15个单元格中，还有1个橙色单元格，1个红色单元格，5个绿色单元格，3个黄色单元格和5个蓝色单元格需要确定颜色，总计15个单元格。对于这个特定的例子，这意味着连接每种颜色的起始和结束单元格的（其中之一）最短路径填满整个棋盘 - 即在用最短路径填充棋盘后，没有未着色的单元格剩余。（这应该被认为是“幸运”，并非每个棋盘的起始配置都会导致这种情况发生）。

通常，在这一步之后，我们有许多可以自由涂色的单元格，我们称之为U。当N=5时，通常情况下，U的数量为：

U = 15 - (dMin(orange) + dMin(red) + dMin(green) + dMin(yellow) + dMin(blue))

由于这些单元格可以采用任何颜色，因此我们还可以确定具有特定颜色的单元格的最大数量：

dMax(orange) = dMin(orange) + U
dMax(red)    = dMin(red) + U
dMax(green)  = dMin(green) + U
dMax(yellow) = dMin(yellow) + U
dMax(blue)   = dMin(blue) + U

在这个特定的例子中，U=0，因此每种颜色的单元格数量的最小值也是最大值。

使用距离约束进行路径查找

如果我们要使用这些颜色约束来枚举所有可能的组合，那么我们需要担心的组合将少得多。更具体地说，在这个特定的例子中，我们会有：

  15! / (1! * 1! * 5! * 3! * 5!)
= 1307674368000 / 86400
= 15135120 combinations left, about a factor 2000 less.

然而，这仍然没有给我们实际的路径。因此，更好的想法是进行回溯搜索，逐个处理每种颜色，并尝试找到所有满足以下条件的路径:

• 不穿过已经着色的单元格
• 长度不小于dMin（颜色），也不大于dMax（颜色）。

第二个条件将减少每种颜色报告的路径数，从而使尝试的总路径数大大减少（由于组合效应）。

伪代码如下：

function SolveLevel(initialBoard of size NxN)
{
    foreach(colour on initialBoard)
    {
        Find startCell(colour) and endCell(colour)
        minDistance(colour) = Length(ShortestPath(initialBoard, startCell(colour), endCell(colour)))
    }

    //Determine the number of uncoloured cells remaining after all shortest paths have been applied.
    U = N^(N^2 - 2N) - (Sum of all minDistances)

    firstColour = GetFirstColour(initialBoard)
    ExplorePathsForColour(
        initialBoard, 
        firstColour, 
        startCell(firstColour), 
        endCell(firstColour), 
        minDistance(firstColour), 
        U)
    }
}

function ExplorePathsForColour(board, colour, startCell, endCell, minDistance, nrOfUncolouredCells)
{
    maxDistance = minDistance + nrOfUncolouredCells
    paths = FindAllPaths(board, colour, startCell, endCell, minDistance, maxDistance)

    foreach(path in paths)
    {
        //Render all cells in 'path' on a copy of the board
        boardCopy = Copy(board)
        boardCopy = ApplyPath(boardCopy, path)

        uRemaining = nrOfUncolouredCells - (Length(path) - minDistance)

        //Recursively explore all paths for the next colour.
        nextColour = NextColour(board, colour)
        if(nextColour exists)
        {
            ExplorePathsForColour(
                boardCopy, 
                nextColour, 
                startCell(nextColour), 
                endCell(nextColour), 
                minDistance(nextColour), 
                uRemaining)
        }
        else
        {
            //No more colours remaining to draw
            if(uRemaining == 0)
            {
                //No more uncoloured cells remaining
                Report boardCopy as a result
            }
        }
    }
}

查找所有路径

现在只需要实现FindAllPaths(board, color, startCell, endCell, minDistance, maxDistance)方法。这里的难点在于，我们不仅要搜索最短路径，还要搜索符合minDistance和maxDistance范围内的任意路径。因此，我们不能只使用Dijkstra或A*算法，因为它们只记录到每个单元格的最短路径，而无法记录任何可能的绕路。

一种查找这些路径的方法是，在棋盘上使用多维数组，其中每个单元格都能够存储多个航点。一个航点被定义为一对(前一个航点，距离起点的距离)。需要前一个航点来重构整个路径，当我们到达目的地时，距离起点的距离则防止我们超出maxDistance。

通过从startCell开始向外进行类似洪水填充的探索，可以找到所有路径。对于给定的单元格，递归地探索每个未着色或与当前颜色相同的邻居，直到我们到达endCell或超过maxDistance（除了从起点到原点的路径）。

改进这种策略的一种方法是，我们不仅从startCell朝endCell外部探索，而且从startCell和endCell同时向外探索，使用Floor(maxDistance / 2)和Ceil(maxDistance / 2)作为各自的最大距离。对于较大的maxDistance值，这应该将探索的单元格数从2 * maxDistance^2降低到maxDistance^2。

- Leon Bouquiet

Answer 4

我认为您需要分两步进行。第一步是找到连接所有点的一组不相交路径，然后第二步是将这些路径扩展/移动以填满整个棋盘。

我的想法是，在第一步中同时对所有点执行类似于Dijkstra算法的操作，一起延伸路径。与Dijkstra类似，我认为您需要从每个点开始向外泛洪，选择使用某种启发式方法（我的直觉是首先选择自由度最小的点，然后按距离排序），来决定下一个要搜索的节点。但与Dijkstra非常不同的是，当我们有多条路径尝试延伸到同一节点时，我们可能会被迫回溯。（在更大的地图上，这可能会相当棘手，但在像上面那样小的地图上可能不是很重要。）

在开始上述算法之前，您还可以解决一些较简单的路径，主要是为了减少需要回溯的次数。特别地，如果您可以在棋盘的边缘之间建立一条路径，您可以保证以这种方式连接这两个点永远不会干扰其他路径，因此您可以简单地填充它们并将这些路径从方程中排除。然后，您可以进一步迭代此过程，直到通过沿着棋盘或现有路径的边界进行跟踪找到所有这些“快速简单”的路径。该算法实际上可以完全解决上面的示例棋盘，但在其他地方可能会失败..尽管如此，执行它将非常便宜，并且可以减少前一个算法的搜索时间。

或者，您可以在每组点之间简单地使用Dijkstra算法，首先寻找最近的点（或尝试随机顺序几次）。这可能适用于相当数量的情况，当它失败时，只需放弃地图并生成新地图即可。

一旦您解决了第一步，第二步应该更容易，但不一定是微不足道的。要扩展您的路径，我认为您需要向外延伸您的路径（因此最靠近墙壁的路径首先向墙壁延伸，然后向内部的其他路径向外延伸等）。要进行扩展，我认为您将有两个基本操作：翻转角落和扩展到相邻的一对空方块中..也就是说，如果您有像下面这样的线：

.v<<.
v<...
v....
v....

首先，您需要翻转角落以填补边缘空间。

v<<<.
v....
v....
v....

那么您将希望扩展到相邻的开放空间对。

v<<v.
v.^<.
v....
v....

v<<v.
>v^<.
v<...
v....

请注意，我所概述的方法并不能保证一定有解决方案，但如果存在解决方案，大多数情况下您应该能够找到一个解决方案。如果地图没有解决方案或算法无法找到解决方案，则可以放弃该地图并尝试其他地图 :)

- hexist

Answer 5

你有两个选择：

1. 编写自定义求解器
2. 暴力破解。

我使用选项(2)生成Boggle类型的棋盘，非常成功。 如果您选择选项(2)，请按照以下步骤操作：

所需工具：

• 编写A*求解器。
• 编写随机棋盘创建器

解决：

1. 生成仅由端点组成的随机棋盘
2. 当棋盘未解决时：
   • 获取最接近且尚未解决的两个端点
   • 运行A*以生成路径
   • 更新棋盘，使下一个A*知道新的棋盘布局，并将新路径标记为不可穿越。
3. 在循环退出时，检查成功/失败（是否使用了整个棋盘等），如果需要，则再次运行

10x10上的A*应在几百分之一秒内运行。 您可能可以每秒解决1k+个棋盘。 因此，10秒的运行时间应该能够得到几个“可用”的棋盘。

额外加分：

• 在为IAP（应用内购买）级别包生成级别时，请记得检查镜像/旋转/反射等，以便您不会有一个板是另一个板的副本（这只是无聊的）。
• 想出一个度量标准来确定两个板是否“相似”，如果是，则放弃其中一个。

- Richard