javascript - 用javascript实现四叉树碰撞？

Question

我正在开发一款类似于 agar.io 和 slither.io(使用 node.js 和 socket.io)的 io 游戏，其中在 map 上的二维空间中一次最多有 50 名玩家和大约 300 种食物。球员和食物都是圆形的。每一帧，服务器都需要检查玩家是否与食物发生碰撞并采取相应行动。玩家和食物都是具有不同坐标和大小的 JSON 对象数组。蛮力方法将遍历所有食物，并且对于每种食物，遍历所有玩家以查看他们是否发生碰撞。当然，这会进行 300*50 次迭代，每秒 60 次(60fps)，这对于服务器来说当然太重了。

我确实遇到过四叉树方法，这对我来说是一个新概念。此外，我对 javascript 的了解让我想知道我究竟应该如何实现它。我无法解决的问题如下:1.既然理论上玩家可以是任意大小(甚至和 map 一样大)，那么我将 map 划分成多大的部分呢？2. 即使我确实将 map 分成几个部分，我认为它起作用的唯一方法是对于每个玩家，我需要获得与玩家共享相同部分的食物。这是个大问题——现在不管我怎么想，我仍然需要遍历每一种食物并检查它是否在所需的部分。 如果不循环我该怎么做？因为这仍然会进行 50*300 次迭代，每秒 60 次，这对我来说并没有任何更快的速度。

tldr:我需要找到一种方法来检测一组 50 个对象和一组 300 个对象之间的碰撞，每秒 60 次。如何在不以 60 fps 循环 50*300 次迭代的情况下做到这一点？

我无法在网上找到任何可以回答我问题的信息。如果我遗漏了一些可能会产生我寻求的答案的地方，我提前道歉。

Answer 1

这是一个仅检查单个层的小示例，但我认为它演示了如何在不遍历所有对象的情况下检查碰撞。

// 2d array of list of things in said square
// NOT A QUADTREE JUST DEMONSTRATING SOMETHING
let quadlayer = [];
for (let i=0;i<4;++i) {
    quadlayer[i] = [];
    for (let j=0;j<4;++j) {
        quadlayer[i][j] = [];
    }
}

function insertObject(ur_object) {
    quadlayer[ur_object.x][ur_object.y].push(ur_object);
}

function checkCollision(ur_object) {
    let other_objects = quadlayer[ur_object.x][ur_object.y];
    console.log('comparing against '+other_objects.length+' instead of '+100);
}

for (let i=0;i<10;++i) {
    for (let j=0;j<10;++j) {
        insertObject({
            x:i%4,
            y:j%4
        })
    }
}


checkCollision({x:1,y:2});