如何合并网格输出中高亮单元格的范围数据以优化碰撞检测？

我正在开发一款游戏，需要一套高效的碰撞检测系统。目前用1和0组成的数组表示边界，冗余度很高。
我写了个简易网格创建工具，能高亮要标记为边界的单元格，但不知道怎么简化输出实现快速访问。目标是基于连续高亮单元格重构边界（稀疏矩阵形式，无高亮单元格时不生成条目）。比如单元格大小为10时：

0,0
[_ _ ]- - -[ _ _]

期望输出：

{ x: [0,30], y: [0,10] },
{ x: [60,90], y: [0,10] }

但现在每个单元格都会返回空对象，下面是我尝试合并高亮单元格范围的代码：

function mergeConsecutiveCells(boundaries) {
    const mergedBoundaries = [];
   
    if (boundaries.length === 0) {
        return mergedBoundaries;
    }
   
    boundaries.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
   
    let currentBoundary = boundaries[0];
   
    for (let i = 1; i < boundaries.length; i++) {

        const nextBoundary = boundaries[i];
   
        if (
            currentBoundary[1] === nextBoundary[1] &&
            currentBoundary[2] === nextBoundary[2] &&
            currentBoundary[3] === nextBoundary[3] &&
            currentBoundary[0] + cellSize === nextBoundary[0]
        ) {

            // Consecutive cells, extend the range
            currentBoundary[0] = nextBoundary[0];
        } else {
           // Non-consecutive cells, add the current boundary to the result
           mergedBoundaries.push({
               x: { start: currentBoundary[0], end: currentBoundary[0] + cellSize },
               y: { start: currentBoundary[1], end: currentBoundary[3] }
           });
           currentBoundary = nextBoundary;
        }
    }
    // Add the last boundary
    mergedBoundaries.push({
        x: { start: currentBoundary[0], end: currentBoundary[0] + cellSize },
        y: { start: currentBoundary[1], end: currentBoundary[3] }
    });
    return mergedBoundaries;
}

原代码核心问题 #

1. 连续区间合并逻辑错误：合并时覆盖了当前区间的起始x坐标，导致无法记录连续单元格的起始位置，最终只能输出单个单元格范围。
2. 依赖变量不明确：cellSize作为外部变量未传入函数，可能导致未定义错误。
3. 区间计算逻辑混乱：输出格式和区间起始/结束值的对应关系不清晰，不符合预期的数组形式输出。

修正后的实现方案 #

假设输入的boundaries是单元格左上角坐标数组（格式如[[x1,y1], [x2,y2], ...]），以下是适配你需求的简化版本：

function mergeConsecutiveCells(boundaries, cellSize) {
    const mergedBoundaries = [];
    if (boundaries.length === 0) return mergedBoundaries;

    // 按y坐标分组，确保仅合并同一水平线的单元格
    const yGroups = {};
    boundaries.forEach(([x, y]) => {
        if (!yGroups[y]) yGroups[y] = [];
        yGroups[y].push(x);
    });

    // 遍历每个y组，合并连续x区间
    Object.entries(yGroups).forEach(([y, xList]) => {
        // 对当前y组内的x坐标排序
        xList.sort((a, b) => a - b);
        
        let startX = xList[0];
        // 遍历判断连续单元格
        for (let i = 1; i < xList.length; i++) {
            // 当前x与前一个x不连续（差值不等于单元格大小）
            if (xList[i] !== xList[i-1] + cellSize) {
                mergedBoundaries.push({
                    x: [startX, xList[i-1] + cellSize],
                    y: [parseInt(y), parseInt(y) + cellSize]
                });
                startX = xList[i];
            }
        }
        // 加入最后一个连续区间
        mergedBoundaries.push({
            x: [startX, xList[xList.length-1] + cellSize],
            y: [parseInt(y), parseInt(y) + cellSize]
        });
    });

    return mergedBoundaries;
}

使用示例 #

输入单元格坐标数组（cellSize=10）：

const input = [[0,0], [10,0], [20,0], [60,0], [70,0], [80,0]];
console.log(mergeConsecutiveCells(input, 10));

输出结果：

[
  { x: [0, 30], y: [0, 10] },
  { x: [60, 90], y: [0, 10] }
]

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