本文深入探讨了如何为“双巧克力”（Double-Choco）谜题游戏自动生成可解谜题。我们将介绍一种高效的数据结构——基于2D网格的单元格对象，该对象包含边界信息、颜色和状态。在此基础上，我们将详细阐述一种递归的块识别算法（类似于深度优先搜索），以及如何将其整合到迭代式谜题生成流程中，以确保生成的谜题满足游戏规则，并具备可解性。文章将提供示例代码，并讨论生成过程中的关键考量与优化策略。
双巧克力谜题概述
“双巧克力”（double-choco）是一款由nikoli杂志推出的独特逻辑谜题。游戏在一个由白色和灰色单元格组成的2d网格上进行。玩家的目标是通过绘制线条将网格划分为若干个“块”。每个块必须包含一对形状和大小完全相同的白色区域和灰色区域。这两个区域可以是彼此的旋转或镜像。某些区域可能带有数字，表示该颜色在该块中的单元格数量。
自动生成此类谜题的关键挑战在于，不仅要创建满足基本规则的块，还要确保整个谜题是可解的，并且没有遗留下无法形成合法块的孤立区域。
核心数据结构设计
为了高效地表示谜题板并支持生成算法，我们推荐使用一个二维数组来存储自定义的“单元格”（Cell）对象。每个Cell对象应包含以下属性，以全面描述其状态和边界信息：
let Cell = {
x: Number, // 单元格的X坐标
y: Number, // 单元格的Y坐标
color: "white" | "gray", // 单元格的颜色，初始化时可为空或未定义
number: null | Number, // 如果有数字提示，则为数字，否则为null
// 边界标志：true表示该方向有边界线（墙），false表示与相邻单元格连通
top: Boolean, // 上方是否有边界
bottom: Boolean, // 下方是否有边界
left: Boolean, // 左方是否有边界
right: Boolean, // 右方是否有边界
blockId: null, // 用于标记该单元格所属的块ID，null表示未分配
isOccupied: Boolean // 在生成过程中标记单元格是否已被某个块占据
};
数据结构解释：
- x, y：坐标信息便于引用和调试。
- color：存储单元格的颜色，这在生成阶段会被赋值。
- number：用于存储谜题提示数字。
- top, bottom, left, right：这些布尔值是定义块形状的关键。true表示在该方向上有一条实线，将当前单元格与相邻单元格分隔开。false表示它们是连通的，属于同一个块。在初始状态下，所有这些都可以设置为false，表示一个完全开放的网格。
- blockId：在块识别算法中使用，确保每个单元格只属于一个块，并能快速查询其所属块。
- isOccupied：在生成过程中，标记单元格是否已被分配到某个最终的谜题块中，避免重复处理。
谜题板本身可以表示为一个Cell对象的二维数组：let board = Array(rows).fill(0).map(() => Array(cols).fill(0).map(() => ({…Cell})));
块识别算法：从网格中提取块
生成谜题的核心在于能够准确地识别出当前网格状态下形成的“块”。这可以通过一种类似于深度优先搜索（DFS）或广度优先搜索（BFS）的遍历算法实现。该算法会从一个未被访问的单元格开始，沿着没有边界线的路径，收集所有连通的单元格，形成一个完整的块。
/**
* 递归函数：从指定单元格开始，寻找并收集所有连通的单元格，形成一个块。
* @param {Array<Array<Object>>} grid - 谜题网格
* @param {number} x - 当前单元格的X坐标
* @param {number} y - 当前单元格的Y坐标
* @param {number} currentBlockId - 当前块的唯一ID
* @param {Array<Object>} blockCellsList - 用于收集当前块所有单元格的列表
*/
function findBlockCells(grid, x, y, currentBlockId, blockCellsList) {
// 边界检查：确保坐标在网格范围内
if (x < 0 || x >= grid[0].length || y < 0 || y >= grid.length) {
return;
}
const cell = grid[y][x];
// 检查：如果单元格已经被分配到某个块，或者已在当前遍历中访问过，则停止
if (cell.blockId !== null) {
return;
}
cell.blockId = currentBlockId; // 将当前单元格分配给当前块
blockCellsList.push(cell); // 将单元格添加到当前块的列表中
// 递归探索相邻单元格，前提是它们之间没有边界线
if (!cell.top) findBlockCells(grid, x, y - 1, currentBlockId, blockCellsList);
if (!cell.bottom) findBlockCells(grid, x, y + 1, currentBlockId, blockCellsList);
if (!cell.left) findBlockCells(grid, x - 1, y, currentBlockId, blockCellsList);
if (!cell.right) findBlockCells(grid, x + 1, y, currentBlockId, blockCellsList);
}
/**
* 从整个网格中提取所有独立的块。
* @param {Array<Array<Object>>} grid - 谜题网格
* @returns {Array<Array<Object>>} 包含所有识别出的块的列表，每个块是一个单元格列表
*/
function extractAllBlocks(grid) {
let allBlocks = [];
let blockCounter = 0;
// 在每次提取前，重置所有单元格的blockId，确保重新识别
grid.forEach(row => row.forEach(cell => cell.blockId = null));
for (let y = 0; y < grid.length; y++) {
for (let x = 0; x < grid[0].length; x++) {
// 如果当前单元格尚未被分配到任何块
if (grid[y][x].blockId === null) {
blockCounter++; // 为新块生成一个ID
let currentBlockCells = [];
findBlockCells(grid, x, y, blockCounter, currentBlockCells);
// 只有当成功找到单元格形成块时才添加
if (currentBlockCells.length > 0) {
allBlocks.push(currentBlockCells);
}
}
}
}
return allBlocks;
}
注意事项：
- findBlockCells函数是递归的，用于探索单个连通组件。
- extractAllBlocks函数遍历整个网格，确保所有未分配的单元格都被用作新块的起点，从而找到所有独立的块。
- 在每次调用extractAllBlocks之前，重置blockId是至关重要的，以确保每次分析都是基于当前边界状态的全新识别。
谜题生成算法流程
谜题生成是一个迭代和回溯的过程，其核心思想是逐步填充网格，每次放置一对符合规则的白色和灰色区域，并同时定义其边界。
-
初始化网格：
- 创建一个MxN的Cell对象二维数组，所有单元格的isOccupied设为false，color未定义，top/bottom/left/right边界全部设为false（表示初始时无边界）。
暂无评论内容