什么用于无流动游戏随机级别创建？

Question

什么用于无流动游戏随机级别创建？

use*_*714 28 algorithm graph-algorithm coronasdk

我需要一些建议.我正在开发一种类似于Flow Free的游戏,其中游戏板由网格和彩色点组成,用户必须将相同的彩色点连接在一起而不与其他线重叠,并且用尽所有板中的空闲空间.

我的问题是关于水平创造.我希望随机生成各级(并且至少应该能够自己解决,以便它可以给玩家提示)并且我在使用什么算法.有什么建议？

游戏目标

注意:图像显示了Flow Free的目标,它与我正在开发的目标相同.

谢谢你的帮助.:)

Answer 1

use*_*210 28

考虑使用一对更简单,更易于管理的算法来解决您的问题:一种算法可靠地创建简单的预解决板,另一种算法重新排列流量,使简单的板更复杂.

第一部分,构建一个简单的预解块板,如果你在x 网格n上使用流,那么它是微不足道的(如果你想要的话):nn

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

或者,您可以提供自己的手工制作的启动板以传递到第二部分.这个阶段的唯一目标是建立一个有效的板,即使它只是微不足道或预先确定,所以值得保持简单.

第二部分,重新排列流量,涉及在每个流上循环,看看哪个流可以与其相邻流一起生长和收缩:

对于一些迭代次数......
- 选择随机流程f.
- 如果f是最小长度(比如3个方格长),请跳到下一个迭代,因为我们f现在无法收缩.
- 如果头点位于f另一个点的一个点的旁边g(如果有多个g可供选择,则随机选择一个)...
  - f沿着它的流动将头部移动一个方块(即,朝向尾部移动一个方格).f现在是一个方格更短,有一个空方格.(这个难题现在尚未解决.)
  - 将相邻的点移动g到空出的空方格中f.现在有一个空方块,其中g的点移动了.
  - 用流量填充那个空白点g.现在g比这次迭代开始时长一平方.(这个难题也回归了.)
- 重复上一步f的尾点.

目前的方法是有限的(点将永远是邻居),但它很容易扩展:

添加一个循环遍历流体的步骤f,寻找与其他流交换空间的棘手方法......
添加一个阻止点移动到旧位置的步骤...
添加您提出的任何其他想法.

这里的整体解决方案可能不是你想要的理想解决方案,但现在你有两个简单的算法,你可以进一步充实,以发挥一个大的,无所不包的算法的作用.最后,我认为这种方法是可管理的,不是神秘的,易于调整,如果不是其他的话,这是一个好的起点.

更新:我根据上述步骤编写了一个概念验证.从下面的第一个5x5网格开始,该过程产生了随后的5个不同的板.有些是有趣的,有些则不是,但它们总是对一个已知的解决方案有效.

初始点
图1 - 起始帧

5随机结果(对不对齐的截图)

随机8x8为衡量标准.起点与上述相同的简单列方法相同.

Answer 2

Ast*_*ain 8

创建这样一个级别最直接的方法是找到解决它的方法.这样,您基本上可以生成任何随机启动配置,并通过尝试解决它来确定它是否是有效级别.这将产生最多样化的水平.

即使你找到了一种以其他方式生成关卡的方法,你仍然希望应用这个求解算法来证明生成的关卡是好的;)

蛮力枚举

如果电路板的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

Run Code Online (Sandbox Code Playgroud)

这意味着,在尚未确定颜色的15个细胞中,必须存在至少1个橙色,1个红色,5个绿色,3个黄色和5个蓝色细胞,也总共产生15个细胞.对于这个特定的例子,这意味着通过(最短的)最短路径连接每个颜色的起始和结束单元填充整个板 - 即在用最短路径填充板之后,没有未着色的单元保留.(这应该被视为"运气",并非每个电路板的启动配置都会导致这种情况发生).

通常,在这一步之后,我们有许多可以自由着色的单元格,让我们称这个数字为U.对于N = 5,

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

Run Code Online (Sandbox Code Playgroud)

因为这些细胞可以采用任何颜色,我们还可以确定可以具有特定颜色的最大细胞数:

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

Run Code Online (Sandbox Code Playgroud)

(在此特定示例中,U = 0,因此每种颜色的最小单元数也是最大值).

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

如果我们使用这些颜色限制来强力计算所有可能的组合,我们会担心的组合要少得多.更具体地说,在这个特定的例子中,我们将:

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

Run Code Online (Sandbox Code Playgroud)

但是,这仍然没有给我们实际的路径.因此,更好的想法是回溯搜索,我们依次处理每种颜色并尝试找到以下所有路径:

没有穿过已经有色的细胞
不短于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
            }
        }
    }
}

Run Code Online (Sandbox Code Playgroud)

FindAllPaths

这只会实现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.

Answer 3

Tho*_*hle 8

我在我的numberlink求解器和生成器中实现了以下算法.在强制执行规则时,路径永远不会触及自身,这在大多数"硬核"数字链接应用和谜题中是正常的

首先,该板以简单,确定的方式平铺2x1多米诺骨牌.如果这不可能(在奇数区域纸上),则右下角保留为单个.
然后通过旋转随机对邻居随机改组多米诺骨牌.在宽度或高度等于1的情况下不会这样做.
现在,在奇数区域纸张的情况下,右下角连接到其邻居多米诺骨牌之一.这将永远是可能的.
最后,我们可以开始通过多米诺骨牌找到随机路径,并在我们通过时将它们组合起来.特别注意不要连接'neighboour flow',这将产生"双重回归"的谜题.
在拼图打印之前,我们尽可能"紧凑"使用的颜色范围.
通过用a替换所有非流动头的位置来打印拼图.

我的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.......@..

Run Code Online (Sandbox Code Playgroud)

在这里,我通过我的解算器(相同的种子)运行它:

$ 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???????@??

Run Code Online (Sandbox Code Playgroud)

我已经测试了用迭代地随机合并两个相邻路径的函数替换步骤(4).然而它游戏更加密集,我已经认为上面几乎太密集而不困难.

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

归档时间：	12 年，10 月前
查看次数：	14747 次
最近记录：	5 年，9 月前