本文深入探讨了如何自动生成Double-Choco谜题，重点介绍了基于2D单元格矩阵的数据结构设计，以及利用递归式连通组件识别（如洪水填充算法）来提取和验证谜题块的算法。我们将详细阐述从棋盘初始化、形状生成与匹配到边界定义和最终验证的完整生成流程，并提供关键代码示例和实现注意事项，旨在为开发者提供一套可行的谜题生成方案。
一、核心数据结构：单元格表示
在double-choco谜题中，棋盘由一个个单元格组成，这些单元格可以是白色或灰色。为了有效地表示棋盘状态和块的边界，我们采用一个2d数组来存储自定义的cell对象。每个cell对象不仅包含其在棋盘上的坐标，还承载了颜色、数字（如果适用）、边界信息以及是否已被分配到某个块的状态。
一个cell对象的核心属性定义如下：
let cell = { x: Number, // 单元格的X坐标 y: Number, // 单元格的Y坐标 color: "white" | "gray", // 单元格的颜色 number: null | Number, // 如果有数字提示，表示该颜色区域的单元格数量 top: true | false, // 顶部是否有边界线 (true: 有边界, false: 无边界) bottom: true | false, // 底部是否有边界线 left: true | false, // 左侧是否有边界线 right: true | false, // 右侧是否有边界线 taken: false, // 是否已被分配到某个完成的谜题块中 blockId: null // 所属谜题块的唯一ID，或存储整个块的引用};
关键属性解析：
x, y: 单元格的二维坐标，方便定位。color, number: 用于表示谜题的特定规则，即白/灰区域及其大小提示。top, bottom, left, right: 这四个布尔值是定义谜题块边界的关键。当值为true时，表示该方向存在一条实线，将当前单元格与相邻单元格分隔开；当值为false时，表示该方向没有实线，当前单元格与相邻单元格相连，属于同一个连通区域。taken: 在生成过程中，用于标记已被成功分配到某个合法谜题块的单元格，避免重复处理。blockId: 用于在提取块后，将所有属于同一块的单元格关联起来。
二、块提取算法：基于边界的连通组件识别
在谜题生成过程中，我们需要能够根据已定义的边界线（即cell对象的top/bottom/left/right属性）来识别和提取独立的谜题块。这可以通过一个递归的洪水填充（Flood-Fill）算法来实现。
该算法从一个未被标记的单元格开始，递归地访问所有与其相连（即之间没有边界线）的相邻单元格，直到遇到边界线或已访问过的单元格。所有被访问到的单元格共同构成一个完整的谜题块。
/** * 递归地提取一个连通的谜题块。 * @param {Array<Array>} cells - 整个棋盘的2D单元格数组。 * @param {cell} currentCell - 当前正在处理的单元格。 * @param {Array} currentBlock - 用于存储当前块中所有单元格的数组。 * @param {number} blockId - 当前块的唯一标识符。 */function extractBlock(cells, currentCell, currentBlock, blockId) { // 边界检查：确保单元格在棋盘范围内 if (!currentCell || currentCell.taken) { return; } currentCell.taken = true; // 标记为已访问/已分配 currentCell.blockId = blockId; // 分配块ID currentBlock.push(currentCell); // 将单元格添加到当前块中 const { x, y } = currentCell; const rows = cells.length; const cols = cells[0].length; // 向上移动：如果顶部没有边界线且上方单元格存在 if (!currentCell.top && y > 0) { extractBlock(cells, cells[y - 1][x], currentBlock, blockId); } // 向下移动：如果底部没有边界线且下方单元格存在 if (!currentCell.bottom && y 0) { extractBlock(cells, cells[y][x - 1], currentBlock, blockId); } // 向右移动：如果右侧没有边界线且右侧单元格存在 if (!currentCell.right && x < cols - 1) { extractBlock(cells, cells[y][x + 1], currentBlock, blockId); }}/** * 遍历整个棋盘，提取所有独立的谜题块。 * @param {Array<Array>} cells - 整个棋盘的2D单元格数组。 * @returns {Array<Array>} 所有提取出的谜题块的数组。 */function findAllBlocks(cells) { const allExtractedBlocks = []; let nextBlockId = 1; for (let y = 0; y < cells.length; y++) { for (let x = 0; x 0) { allExtractedBlocks.push(newBlock); } } } } return allExtractedBlocks;}
工作原理：
extractBlock函数是核心的递归函数。它接收当前单元格、一个用于累积当前块单元格的数组以及块ID。在
以上就是生成Double-Choco谜题：高效数据结构与算法实践的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1513650.html
微信扫一扫 
支付宝扫一扫 
