获取网格中两个点连线经过的格子

/**
 * @description 获取网格中两个点连线经过的格子
 * bresenham 算法
 * ES6+
 * @param {Array} p0 点1
 * @param {Array} p0 点2
 * @return {Array[]} 格子数组
 */
function determineTouchedTiles(p0, p1) {
  const touched = [];

  let [x0, y0] = p0;
  let [x1, y1] = p1;

  // 判断斜率的绝对值是否大于1
  const steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);

  // 将斜率的绝对值大于1的情况转换为小于等于1的情况
  if (steep) {
    [y0, x0] = p0;
    [y1, x1] = p1;
  }

  // 调整 [x0, y0] 表示的是两点中左边的点
  if (x0 > x1) {
    [x0, x1] = [x1, x0];
    [y0, y1] = [y1, y0];
  }

  // 斜率的绝对值
  const ratio = Math.abs((y1 - y0) / (x1 - x0));
  // 斜率的正负
  const mirror = y1 > y0 ? 1 : -1;

  // 从 x0 向下取整 到 x1 向下取整 一列一列 计算过去
  for (let col = Math.floor(x0); col <= Math.floor(x1); col += 1) {
    // 交点的纵坐标
    const currY = y0 + mirror * ratio * (col - x0);

    // 因为斜率的绝对值小于等于1
    // 所以在每一列上最多跨一格
    // 即每一列上经过的格子为1个或2个
    // 当经过2格时，记为本格和邻格
    // 斜率为正，邻格为本格相邻的上面格子
    // 斜率为负，邻格为本格相邻的下面格子

    let skip = false;

    // 第1列单独处理
    // 当第1列经过2格，且 [x0, y0] 在邻格中时，不放入本格
    if (col === Math.floor(x0)) {
      // 判断是否为同一格
      // 因为
      // parseInt(0.4) === parseInt(-0.4) 为 true
      // Math.floor(0.4) === Math.floor(-0.4) 为 false
      // 所以
      // 为保证在负数情况下成立，使用 Math.floor
      // 如 [[-0.5, 0.2], [0.5, 0.8]] 使用 parseInt 就无法跳过[-1, -1]
      skip = Math.floor(currY) !== Math.floor(y0);
    }

    // 根据 skip 放入本格
    if (!skip) {
      if (!steep) {
        touched.push([col, Math.floor(currY)]);
      } else {
        touched.push([Math.floor(currY), col]);
      }
    }

    // 根据斜率计算是否有跨格
    if (
      (mirror > 0 ? Math.ceil(currY) - currY : currY - Math.floor(currY)) <
      ratio
    ) {
      const crossY = Math.floor(currY) + mirror;

      // 判断是否超出范围
      if (
        crossY > Math.max(Math.floor(y0), Math.floor(y1)) ||
        crossY < Math.min(Math.floor(y0), Math.floor(y1))
      ) {
        continue;
      }

      // 跨线格子
      if (!steep) {
        touched.push([col, crossY]);
      } else {
        touched.push([crossY, col]);
      }
    }
  }

  return touched;
}

验证

// 输出
console.log(
  [
    [
      [-0.5, 0.2],
      [0.5, 0.8]
    ],
    [
      [1.4, 1.4],
      [3.9, 2.1]
    ],
    [
      [1.4, 1.4],
      [3.4, 1.9]
    ],
    [
      [1.5, 1.5],
      [1.5, 3.3]
    ],
    [
      [1.5, 1.5],
      [3.5, 3.3]
    ],
    [
      [1.5, 1.5],
      [3.5, 3.7]
    ],
    [
      [1.5, 1.5],
      [-0.5, 3.3]
    ],
    [
      [1.5, 1.5],
      [-0.5, 3.7]
    ],
    [
      [-1.2, -1.8],
      [-3.5, -3.5]
    ],
    [
      [-1.8, -2.2],
      [-3.5, -3.5]
    ],
    [
      [-1.8, -2.2],
      [-3.5, -1.5]
    ],
    [
      [-1.2, -2.1],
      [-3.5, -1.5]
    ]
  ].map(x => determineTouchedTiles(...x))
);

// 结果
[
  [
    [-1, 0],
    [0, 0]
  ],
  [
    [1, 1],
    [2, 1],
    [3, 1],
    [3, 2]
  ],
  [
    [1, 1],
    [2, 1],
    [3, 1]
  ],
  [
    [1, 1],
    [1, 2],
    [1, 3]
  ],
  [
    [1, 1],
    [2, 1],
    [2, 2],
    [3, 2],
    [3, 3]
  ],
  [
    [1, 1],
    [1, 2],
    [2, 2],
    [2, 3],
    [3, 3]
  ],
  [
    [-1, 3],
    [-1, 2],
    [0, 2],
    [0, 1],
    [1, 1]
  ],
  [
    [1, 1],
    [1, 2],
    [0, 2],
    [0, 3],
    [-1, 3]
  ],
  [
    [-4, -4],
    [-3, -4],
    [-3, -3],
    [-2, -3],
    [-2, -2]
  ],
  [
    [-4, -4],
    [-3, -4],
    [-3, -3],
    [-2, -3]
  ],
  [
    [-4, -2],
    [-3, -2],
    [-3, -3],
    [-2, -3]
  ],
  [
    [-4, -2],
    [-3, -2],
    [-2, -2],
    [-2, -3]
  ]
]