一种基于分裂树构造的关卡数值分布生成方法及装置与流程

本发明涉及计算机数据处理，具体涉及一种数字合并消除类游戏中关卡数值分布的生成方法及装置。

背景技术：

1、在数字合并消除类游戏中，一个关卡由若干层格位组成，每个格位上放置一个携带数值的游戏元素；玩家将游戏元素放入存放区，当同一数值的游戏元素累积到聚合基数所要求的个数时，它们经一次聚合操作归并为数值高一档的一个游戏元素。关卡的数值分布（即各档位游戏元素各有多少个）与初始牌面由关卡生成环节产出。

2、现有的关卡生成路径可归纳为四类；此外，针对消除类游戏还存在一类在运行阶段作版面修正的做法，虽不属于生成环节，亦一并列明如下。

3、其一为基于学习模型的生成。例如，申请公布号 cn121911107a（申请日2024.10.23，公开日 2026.04.24）所记载的方案，获取历史游戏关卡信息并对其特征进行标识与训练以建立生成模型，再据此自动生成关卡；以及申请公布号 cn120617962a（申请日 2025.05.07，公开日 2025.09.12）所记载的方案，通过多任务学习网络生成动态用户画像向量，再由双通道生成对抗网络产出候选关卡集合并以可玩性指标筛选。此类方案的输出受历史数据分布支配，不承载「张数守恒」「总和守恒」这类可验证的算术关系。再如申请公布号 cn119425055a（申请日 2024.11.22，公开日 2025.02.14）所记载的方案，随机生成游戏关卡后以强化学习网络模型执行游戏解题并获得关卡通过率，通过率不低于设定阈值时输出该关卡；其可解性由解题验证取得，而非由生成过程本身保证。

4、其二为基于规则抽取与路径探索的生成。例如申请公布号 cn121243778a（申请日2025.09.25，公开日 2026.01.02）所记载的数独关卡生成方案，从初始关卡的题目元素与解元素中抽取以生成关卡；以及申请公布号 cn120860601a（申请日 2025.08.26，公开日2025.10.31）所记载的方案，对关卡词语作拆分处理并基于拆分结果作路径探索。此类方案依据抽取或路径连通性生成，难度评估位于生成之后，不反向约束生成过程。

5、其三为直接读取预先配置的关卡数据。例如申请公布号 cn116116003a（申请日2023.02.24，公开日 2023.05.16）所记载的方案，在网络正常时从服务端获取关卡配置数据、网络断开时获取默认关卡配置数据，关卡内容本身仍为预先配置的静态数据。

6、其四为以逆推（反向构造）方式保证关卡可解。公开于 2018 年 7 月的技术文章《游戏人工智能 读书笔记（十一）游戏内容生成》记载：「解密游戏中一种最简单的内容生成方法：逆推。从谜题解开的状态开始，一步一步根据游戏逻辑，找出可能的上一步，然后逆推回去」，并指出滑块类游戏的关卡生成最常用逆推方法，「这样能够百分之百保证生成的关卡是可解的」。开源项目 runar-rkmedia/gotally 的按目标格值生成模块则从期望达成的目标格值出发反向推导：将目标值反复除以合并基数直至降到本关的最大格值，据此得出达到该目标所需的最小方块个数，再由一个因数替换步骤把其中若干必需方块替换为其因数组合以增加合成步数，最后由求解器在给定时限内验证该棋盘是否可解，验证不通过则重新生成并设有重试次数上限。

7、就消除类游戏而言，还存在一类在运行阶段保证可解的做法。例如申请公布号cn121588458a（申请日 2026.01.20，公开日 2026.03.03）所记载的方案：扫描游戏显存区域提取残局拓扑矩阵，在影子内存中构建虚拟版面并执行全路径消除模拟以检测死局，再针对锁定的异常坐标区域构建以「存在可解路径」为目标的约束满足方程组，以回溯搜索与前向检测迭代求解元素类型组合，最后将修正后的填充序列转换为图形指令流写入帧缓冲。该类做法解决的是运行阶段对既有版面的动态修正，其求解对象是网格元素的类型组合，既不涉及各档位元素的数量分布，也不涉及元素张数与数值总和的守恒关系。

8、此外，申请公布号 cn121944496a（申请日 2025.11.28，公开日 2026.05.01）、cn121988024a（申请日 2026.03.03，公开日 2026.05.08）与 cn114602185a（申请日2022.01.20，公开日 2022.06.10）分别涉及消除合并的交互闭环、体感投掷类网格填充消除与数字合并游戏的服务端实现，其棋盘数值由预先配置或随机落子产生。

9、上述现有技术存在如下不足：

10、一、生成结果的可通关性无法在生成阶段得到保证。学习模型法与抽取法的输出是对历史数据或既有元素的近似与变形；逆推类方案虽由构造方式承担可解性，但其产物是达成目标所需的最小元素集合，补入额外元素之后是否仍可被完全消除仍依赖求解器事后校验与重试。一旦出现无法配对的残留元素，玩家必然失败，而该缺陷只能在生成之后由人工或程序抽查发现。

11、二、依赖迭代试凑与事后校验，求解开销与失败率不可控。依赖随机扰动的生成方式通过设置迭代次数上限反复校验来逼近目标；逆推类方案通过设置校验重试次数上限工作；以解题验证取得可解性的方式（如上引 cn119425055a）则先随机生成关卡、再以模型解题计算通过率，仅在通过率不低于设定阈值时输出该关卡，未达阈值的结果不再输出。三种方式的共同点是：可解性都是在生成之后被验证出来的，而不是由生成过程本身保证的；达到迭代上限、重试上限或未达阈值时，只能输出生成失败的提示或丢弃该结果，关卡生产流程无法闭环。

12、三、结构硬约束需要事后打补丁。「每种数值至少出现一次」这类要求若不在求解过程中作为硬约束处理，会出现某些档位张数为零的情况，只能追加补零与搬运的修正逻辑，而修正本身可能破坏已满足的其他约束。

13、四、分布均匀性缺乏全局最优目标。依权重等间接方式塑形只能决定分布的粗略骨架，无法保证在全部可行解中取到均匀性最优的一个。

14、五、难以同时满足多种聚合基数。当同一关卡内需要按不同聚合基数处理不同数值链时，各链的张数与总和约束各自独立，现有方案缺少对多链分别求解后统一排布的机制。

15、六、运行阶段的动态修正只能事后补救，且无法解决分布层面的缺陷。针对消除类游戏在运行阶段检测死局并修正版面的做法（如上引 cn121588458a），其求解对象是网格元素的类型组合，只能在版面已经生成之后对个别坐标区域作局部修正。若该关各档位元素的数量分布在生成阶段本身就不合理，例如某些档位覆盖不全、或张数分布失衡，则运行阶段无论重复多少次局部修正，都只能改变元素类型而无法改变该关可用的元素总数量与档位构成，问题被反复掩盖而不能被消除。因此，该缺陷的根因位于生成阶段的数量分配环节，而不是运行阶段的版面调整环节。

技术实现思路

1、要解决的技术问题

2、本发明要解决的技术问题是：在游戏元素总数量与数值总和均已给定的前提下，如何一次求得各档位元素数量的分布，使该分布同时满足元素张数守恒、数值总和守恒、每种数值至少出现一次、以及生成结果必然可被完全消除四项结构要求，并且在该约束下取到分布均匀性最优的那一个，从而无需依赖迭代试凑与事后校验。

3、技术方案

4、为了实现上述目的，本发明采用如下技术方案。

5、一种关卡数值分布的生成方法，包括如下步骤：

6、（1）获取待生成关卡的关卡参数，包括该关待生成的游戏元素总数量 n、数值总和s、数值范围下界 vmin 与上界 vmax、档位间的比值基数 step、以及聚合基数 gs；其中聚合基数 gs 为 gs 个同值游戏元素经一次聚合操作归并为高一级的一个游戏元素所需的游戏元素个数，数值总和 s 为该关全部游戏元素聚合至最终时那一个游戏元素的数值。

7、（2）以 vmin 为首项、以 step 为公比逐级推高至不超过 vmax，确定该关允许出现的各档位数值及档位数 k，所述档位数 k 不小于二；其中，所述比值基数 step 与所述聚合基数 gs 取相同的值；

8、（3）以待生成关卡的最终聚合结果为根节点，按 gs 作反向分裂构造：将一个数值为 v 的游戏元素分裂为 gs 个数值为 v/gs 的游戏元素，逐级分裂至叶子值落入所述数值范围；将由根节点分裂至全部叶子所需的分裂次数 t 按 t=(n-1)/(gs-1) 确定，并要求t 为整数，即 n-1 能被 gs-1 整除。由于每分裂一次节点数增加 gs-1，分裂次数 t 等于分裂树的内部节点数。

9、（4）引入进位变量 s_j，表示自第 j-1 档进位至第 j 档的游戏元素张数，j 取值1 至 k；并依据该进位变量将各档张数表示为 x_0 = gs × s_1、x_j = gs × s_(j+1) -s_j（1 ≤ j ≤ k-2）、x_(k-1) = gs × s_k - s_(k-1)。

10、（5）由满足 vmin × gs^t = s 的根档位序号 t 固定末档进位变量 s_k = gs^(t-k)，并要求 t 不低于 k；自 t 中扣除由根档位至最高档之间已固定消耗的部分，得到可供自由分配的预算，令各自由进位变量之和等于该预算，且令各档张数不小于一。

11、（6）以各档张数与平均张数 n/k 之差的平方和为代价函数，在所述预算的等式约束与各档张数不小于一的可行域约束下，用动态规划自最高档向最低档逐档推进求解；动态规划的状态由当前档进位变量的取值与已累计的进位变量之和共同确定，每次由当前档向低一档转移时一并确定低一档的张数并将其平方偏差计入代价，取总代价最小的一组进位变量为最优解。

12、具体地，状态记为二元组 (v, u)，其中 v 为当前档进位变量的取值，u 为自最高档至当前档的进位变量的累计之和，所述 v 与 u 均以所述预算为上界。自最高档起逐档向低一档推进时，枚举低一档进位变量的取值，按步骤（4）的对应关系确定被该次转移所决定的张数，并将其与平均张数之差的平方累加至代价；推进至最低档后，再累加最低档张数自身的平方偏差。在所有到达最低档且累计之和等于所述预算的状态中，取总代价最小者，并沿该状态回溯，得到各档进位变量的最优取值。

13、（7）按所述对应关系还原各档张数，将各档张数展开为长度为 n 的数值序列，并连同所述关卡参数输出为该关的关卡数据。

14、关于所述比值基数 step 与所述聚合基数 gs 须取相同的值，其原因为：档位定义给出相邻两档数值之比为 step；而分裂树定义要求一个数值为 v 的节点分裂为 gs 个数值为 v/gs 的子节点，且子节点数值仍须为合法档位值，故相邻档位之比又必须为 gs。两者同时成立即得 step ≡ gs。若 step ≠ gs，则 v/gs 可能落在该关数值范围内却不是合法档位值，分裂树无法在档位集合上闭合，步骤（3）至步骤（6）均无法实施；故该条件是方案可实施的前提。在一实施方式中，step 与 gs 同取 2，或者同取 3。

15、进一步地，步骤（3）之前还包括前置可解性门槛校验：校验 n-1 能否被 gs-1 整除、数值总和 s 是否落在以 vmin 为起点且以 gs 为比的幂链上、根档位序号 t 是否不低于档位数 k；并且还校验所述预算 β 是否满足 β ≥ k-1 且不超过各档进位变量的上界之和，其中第 j 档进位变量的上界由 s_j ≤ gs × s_(j+1) - 1 给出。任一项不满足时转入兜底构造路径。

16、进一步地，兜底构造路径包括：当关卡参数满足可解前提时，按同一分裂树模型作一致构造——以 s_k = gs^(t-k) 固定末档进位变量，各自由进位变量先各取 1，再令 j依次取 k-1, k-2, …, 1，逐档按 add = min [ r, gs × s_(j+1) - 1 - s_j ] 取填充量并令 s_j arrow s_j + add、r arrow r - add，其中 r 为剩余预算；随后按上述对应关系还原各档张数。所述上界不可省略：由 x_j = gs × s_(j+1) - s_j 与 x_j ≥ 1 反解即得 s_j ≤ gs × s_(j+1) - 1；若不加上该上界而把剩余预算整段填入当前档，x_j 将随之减小并可能小于一。由于第 j 档进位变量的上界只取决于更高一档的 s_(j+1)，而s_(j+1) 在本档填充时已经确定，故自高档向低档推进时各档上界均可计算；又因填充 s_j 只会抬高其下一档的上界而不会收紧，故在参数可解时该规则必能恰好用尽预算。当各自由进位变量取 1 后剩余预算为负，或者填充至最低档后剩余预算 r 仍大于零时，判定该关卡参数不可解，输出形式完整的占位分布并标记为需人工复核。

17、进一步地，步骤（7）之前还包括：自最低档起逐档进位，校验每一档的累积张数能否被所述聚合基数 gs 整除，并校验每一档张数是否不少于一张；任一项不满足时不输出该分布。应当说明，由于步骤（4）还原出的各档张数来自分裂树的构造关系，且数值总和已被约束在聚合基数的幂链上，各档张数在逐档进位过程中的整除性由数值总和守恒自动成立，故该校验在正常运行中系形式确认，其作用是在数值精度或实现异常导致确认失败时避免把不合法分布输出到关卡数据中。

18、进一步地，当待生成关卡包含多条数值链时，为每一条数值链分别获取该链的游戏元素总数量与数值总和，并按该链自身的聚合基数与幂次分别执行上述步骤（2）至步骤（6），再合并展开与统一排布；各链的游戏元素总数量之和等于该关的格位总数，故各链展开所得序列的长度之和恰等于格位数，合并后的序列与格位一一对应，不存在某一链接入后无位可放或格位空缺的情形；各链仅按各自链内的聚合基数结算，不参与其他链的聚合。

19、进一步地，步骤（7）中，将各档张数展开为长度为 n 的数值序列之后，还包括：对包含多条数值链的关卡，将各链展开所得的序列合并为单一序列后再打乱；将打乱后的数值序列按各层格位依序铺放形成该关的初始牌面；并将关卡数据输出为供关卡加载环节消费的数据结构。

20、一种关卡数值分布的生成装置，包括关卡参数获取模块、档位确定与反向构造模块、预算确定与求解模块与还原输出模块；其中，所述关卡参数获取模块用于执行上述步骤（1），所述档位确定与反向构造模块用于执行上述步骤（2）至步骤（4），所述预算确定与求解模块用于执行上述步骤（5）与步骤（6），所述还原输出模块用于执行上述步骤（7）。

21、关于术语：本发明所称「关卡数据」指包含该关各档位游戏元素的数值序列、该关各层格位的排布关系以及该关关卡参数在内的、供关卡加载环节直接读取的数据结构；本发明所称「游戏元素」指关卡中携带一个数值、占一个格位的可操作对象，在实施例中为方块；所称「聚合操作」指若干同值游戏元素归并为高一级的一个游戏元素的操作，在实施例中为合并；所称「聚合基数」即实施例中之合并基数；所称「元素总数量」即实施例中之方块总张数。

22、有益效果

23、与现有技术相比，本发明具有以下有益效果：

24、一、一次求解即得满足全部约束的分布，消除了求解失败。由于元素张数守恒与数值总和守恒由分裂次数唯一确定，不存在需要迭代满足的约束。在取自实际关卡表的去重后 118 组关卡参数（含单链与双链各链）上，求解成功率为 100.0%，分布均匀性的变异系数 cv 均值为 0.4319。（作为参照，另一类依赖随机扰动的实现方式在同一测试集上的成功率为 91.7%。）需说明的是，该收益来自求解范式的替换而非计算量的节省：本发明采用动态规划，单次求解耗时均值约 12 ms，高于上述另一类实现方式的约 0.17 ms；由于关卡生成仅在关卡加载时执行一次而非逐帧执行，该量级开销可接受。

25、二、结构要求由求解可行域直接施加，无需事后打补丁。「每种数值至少出现一次」作为各档张数不小于一的边界条件直接施加，不会出现修正破坏其他约束的情形。

26、三、分布均匀性在全部可行解中达到最优。以各档张数与平均张数之差的平方和为代价函数并用动态规划求解，所得分配在该代价函数下的全部可行解中为最优。

27、四、成功求解的输出必然可被完全消除。由于数值总和被约束在聚合基数的整数幂链上，各档张数在逐档进位中的整除性由数值总和守恒自动成立，故不需要依赖一次可能失败的事后判定；生成出口的逐档进位确认每档最多进位一次，时间开销与档位数成正比，且在移动端设备的关卡加载阶段不带来不可接受的开销。

28、五、关卡生产流程闭环，不留失败出口。求解未得到结果时转由兜底构造路径产出仍满足四项结构要求的分布；参数本身不可解时输出占位分布并标记人工复核，不向外输出生成失败提示而中断关卡生产；同时支持在同一关内按不同聚合基数求解多条数值链并按张数之和与格位总数对齐。