开发一笔画填充解谜游戏的路径生成算法选型咨询

你的需求本质是在网格图上生成覆盖所有单元格的无重复连续路径，以下是适配性最高的几种算法：

1. 哈密顿路径生成算法 #

• 完全匹配你的需求：哈密顿路径的定义就是恰好访问图中每个节点一次的路径，对应到你的游戏场景就是路径不重复经过任何网格单元格，且覆盖所有空白区域。
• 无障碍物的规则矩形网格可以用分治策略实现，时间复杂度低至O(n)（n为网格单元格总数），适合快速批量生成随机关卡。
• 带自定义障碍物的网格可以用回溯+剪枝的实现方案：只要新增预判逻辑，当剩余未访问单元格被当前路径分割为两个及以上不连通区域时，直接终止当前分支的回溯，生成效率远高于暴力枚举。

2. 启发式优化的深度优先搜索（DFS） #

• 灵活度最高，支持各类自定义关卡规则：如果你后续要加指定起点终点、单向通道、特殊格子等玩法规则，都可以直接在DFS的分支判断逻辑里加约束。
• 搭配Warnsdorff规则优化可以大幅提升生成效率：每次延伸路径时，优先选择相邻未访问单元格数量最少的方向移动，能把回溯概率降到极低，中小规模网格的路径生成速度比普通DFS快数十倍。

3. 规则化路径生成算法（适合快速验证原型） #

• 初期验证玩法逻辑时可以直接用固定规则生成路径，不需要复杂的算法实现：比如横向蛇形、纵向蛇形、螺旋形路径，只需要按坐标规则遍历网格即可生成可用路径，后续再叠加随机扰动、障碍物调整就能产出差异化的关卡。

内容的提问来源于stack exchange，提问作者Romain Charles