如何优化JavaScript中删除数组碰撞对象的collisions函数

需求 #

现有可运行的船只碰撞检测函数，需要移除数组中距离小于判定值的所有碰撞船只，目标是优化代码的简洁性与可读性。

场景参数 #

船只数组 #

var boats = [
  {name: "A", position: [1,1] }, // 与E、G碰撞
  {name: "B", position: [7,8] }, // 与D碰撞
  {name: "C", position: [8,2] }, // 无碰撞
  {name: "D", position: [7,9] }, // 与B碰撞
  {name: "E", position: [2,1] }, // 与A、G碰撞
  {name: "F", position: [1,7] }, // 无碰撞
  {name: "G", position: [2,2] }, // 与A、E碰撞
]

碰撞判定规则 #

两船欧氏距离小于collisionDistance则判定为碰撞，碰撞的两艘船都要从数组中移除，原有距离计算和判定参数如下：

const collisionDistance = 5;

function distance(boat1, boat2) {
  return Math.sqrt(
    Math.pow(boat1.position[0] - boat2.position[0], 2) +
    Math.pow(boat1.position[1] - boat2.position[1], 2)
  );
}

原有可运行实现 #

function collisions() {
  var collidingBoatIndices = new Set();
  // 遍历所有两两组合
  for (let i = 0; i < boats.length; i++) {
    for (let j = i+1; j < boats.length; j++) {
      if (distance(boats[i], boats[j]) < collisionDistance) {
        collidingBoatIndices.add(i);
        collidingBoatIndices.add(j);
      }
    }
  }
  // 从最大索引开始删除，避免数组元素移位导致索引错乱
  for (let index of Array.from(collidingBoatIndices).sort().reverse()){
    console.log("Boat sank: ", boats[index])
    boats.splice(index, 1);
  }
}

测试用例 #

预期运行后仅保留船只C和F：

console.log("Boats at start:", boats.map((boat => boat.name)));
collisions()
console.log("Boats left over:", boats.map((boat => boat.name)));

优化后实现 #

核心优化点 #

1. 距离计算优化：直接比较距离平方，省去开根号操作，性能更优，结果完全一致
2. 避免索引操作：改用对象集合标记碰撞船只，最后直接过滤得到结果，不用处理倒序删除的索引偏移问题
3. 纯函数设计：不直接修改原数组，返回新的结果数组，副作用更小，更易测试
4. 语义化命名：代码逻辑更清晰易读

// 新增距离平方计算、碰撞阈值平方常量，省去重复计算
const collisionDistanceSq = collisionDistance ** 2;
function calcDistanceSq(boatA, boatB) {
  const dx = boatA.position[0] - boatB.position[0];
  const dy = boatA.position[1] - boatB.position[1];
  return dx * dx + dy * dy;
}

function collisions(boats) {
  const collided = new Set();
  // 遍历所有两两不重复的船只组合
  for (let i = 0; i < boats.length; i++) {
    const boatA = boats[i];
    for (let j = i + 1; j < boats.length; j++) {
      const boatB = boats[j];
      if (calcDistanceSq(boatA, boatB) < collisionDistanceSq) {
        collided.add(boatA);
        collided.add(boatB);
        console.log("Boat sank: ", boatA.name, boatB.name);
      }
    }
  }
  // 直接过滤未碰撞的船只返回
  return boats.filter(boat => !collided.has(boat));
}

// 调用示例
const remainingBoats = collisions(boats);
console.log("Boats left over:", remainingBoats.map(b => b.name));

保留修改原数组逻辑的精简版本 #

如果业务要求必须修改原数组而非返回新数组，可以简化原有索引删除逻辑：

function collisions() {
  const collidedIndices = new Set();
  for (let i = 0; i < boats.length; i++) {
    for (let j = i + 1; j < boats.length; j++) {
      if (calcDistanceSq(boats[i], boats[j]) < collisionDistanceSq) {
        collidedIndices.add(i).add(j);
      }
    }
  }
  // 索引从大到小排序后删除，无需先升序再反转
  Array.from(collidedIndices).sort((a, b) => b - a).forEach(idx => {
    console.log("Boat sank: ", boats[idx]);
    boats.splice(idx, 1);
  });
}

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