Javascript: 优化精灵和精灵数组之间的碰撞检测

Question

我有一个 canvas，用户可以在上面上传和放置自己的图片（支持透明）。

我的目标是不允许提交与任何其他现有图像重叠。

为此，我将执行以下操作（伪代码）：

for(let i = 0; i < images.length; i++){
    const existingImage = images[i]
    for(let y = 0; y < existingImage.pixels.length; y++){  
        for(let x = 0; x < newImage.pixels.length; x++){  
            if(newImage.pixels[x] === existingImage.pixels[y])    
              return false;
        }    
    }

}

return true

但是，canvas 分辨率为 1200 x 1200。假设只覆盖了所有可用像素的一半，那么我们将有 720.000 个像素已经被覆盖。给定一个提交像 300 x 300（保守估计）那么我们最终将 720.000 个现有像素与 30.000 个新像素进行比较，这给了我们大约 36.000.000.000 次迭代。在我的笔记本电脑上进行的快速测试最终花费了 20 亿次迭代一分钟。 15分钟一次碰撞检测对我来说是无法接受的。

所以我的问题是，如何在不影响准确性的情况下优化碰撞检测？

Answer 1

先进行边界框碰撞测试，然后仅当边界框重叠时才测试像素。

for ( var existingImage of images ) {
    if ( !(
        existingImage.left > newImage.right || 
        existingImage.right < newImage.left || 
        existingImage.top > newImage.bottom ||
        existingImage.bottom < newImage.top
    )) {
        if ( pixelsOverlap( existingImage, newImage ) ) return false;
    }
}

Javascript: 优化精灵和精灵数组之间的碰撞检测

Javascript: Optimize collision detection between a sprite and an array of sprites

javascript

collision-detection