Canvas无重叠随机放置Sprite：递归栈溢出与位置偏移求助

我尝试在Canvas上随机放置多个不重叠的精灵（每个精灵宽高80），用种子随机数生成器保证位置一致，但遇到两个问题：

1. 避免碰撞的递归逻辑很快触发最大调用栈溢出，哪怕只放15个实体就会出现
2. 成功运行时，实体都集中在Canvas左上区域，碰撞频繁

我试过用Math.random()替代自定义的myrng()，结果一样。相关代码如下：

//80 是单个精灵的宽高
const getLocation = () => {
    let x = Math.floor(myrng() * (canvas.width - 80));
    let y = Math.floor(myrng() * (canvas.height - 80));

    x = x < 0 ? 0 : x;
    y = y < 0 ? 0 : y;

    const overlap = entities.some((entity) => {
      return (x - entity.position.x < 80 || y - entity.position.y < 80);
    });

    if (!overlap) {
      return [x, y];
    } else {
      return getLocation();
    }
  };

myrng()是基于种子的随机数生成器，实体初始化代码：

for (let i = 0; i < 15; i++) {
      const [x, y] = getLocation();
      entities.push({ position: { x, y } });
    }

1. 核心问题：碰撞检测逻辑完全错误 #

你当前的碰撞判断x - entity.position.x < 80 || y - entity.position.y < 80完全不符合矩形碰撞的规则，这是导致所有问题的根源：

• 这个逻辑会把大量不重叠的位置误判为碰撞，比如新生成的x远大于已有实体的x时，只要y方向差值小于80就会被判定碰撞，完全不符合矩形重叠的实际情况
• 错误的检测导致大部分随机位置被过滤，只能不断递归重试，很快触发栈溢出；同时只有左上区域的位置能通过错误检测，造成实体集中

正确的矩形碰撞检测逻辑：两个矩形重叠的条件是，新位置的x范围（x到x+80）与已有实体的x范围（entity.position.x到entity.position.x+80）有重叠，且y范围也有重叠。用代码表示为：

const overlap = entities.some(entity => {
  return !(x + 80 <= entity.position.x || 
           x >= entity.position.x + 80 || 
           y + 80 <= entity.position.y || 
           y >= entity.position.y + 80);
});

逻辑说明：如果新矩形在已有矩形的左、右、上、下任意一侧完全不重叠，就没有碰撞；反之则判定为重叠。

2. 解决递归栈溢出：用循环替代递归 #

递归重试的方式极易触发栈溢出，改成循环重试更安全，还可以添加最大重试次数限制，避免极端情况下的死循环：

const getLocation = () => {
  const MAX_RETRIES = 1000; // 设定最大重试次数，可根据Canvas大小调整
  for (let i = 0; i < MAX_RETRIES; i++) {
    let x = Math.floor(myrng() * (canvas.width - 80));
    let y = Math.floor(myrng() * (canvas.height - 80));
    x = Math.max(0, x); // 简化边界值处理
    y = Math.max(0, y);

    // 正确的碰撞检测
    const overlap = entities.some(entity => {
      return !(x + 80 <= entity.position.x || 
               x >= entity.position.x + 80 || 
               y + 80 <= entity.position.y || 
               y >= entity.position.y + 80);
    });

    if (!overlap) {
      return [x, y];
    }
  }
  // 多次重试失败时返回默认位置，或根据需求抛出错误
  console.warn("无法找到合适的无重叠位置，返回默认值");
  return [0, 0];
};

3. 位置分布优化（可选） #

如果Canvas空间充足，正确的碰撞检测已经能让位置均匀分布；若空间紧张，可进一步优化：

• 网格划分法：将Canvas划分为80x80的网格，每个网格仅放置一个精灵，随机选择未占用的网格，完全避免碰撞和重试
• 拒绝采样优化：若多次重试失败，缩小随机范围至剩余可用空间，但实现相对复杂，对于15个实体的场景，循环重试+正确检测已足够

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