在 JavaScript 中使用空间分区检测对象碰撞

Question

我正在尝试创建一个包含许多对象的系统，这些对象在相互碰撞时执行一个动作，我正在使用 P5.min.js 库。

我已经为网格设置了一个数组，为对象设置了一个数组，但我想不出正确的方法来遍历每个网格单元格并在继续之前只检查该单元格内的对象下一个单元格。

这是我目前得到的

let molecules = [];
const numOfMolecules = 100;
let collisions = 0;
let check = 0;
let maxR = 10; //max molecule radius
let minR = 2; //min molecule radius
let numOfCol = 5;
let numOfRow = 5;
let CellW = 600/numOfCol; //gridWidth
let CellH = 600/numOfRow; //gridHeight
let remain = numOfMolecules;
let gridArray = [];



function setup() {
    createCanvas(600, 600);
    background(127);

    for (let i = 0; i < numOfMolecules; i++) {
        molecules.push(new Molecule());
    }
}

function draw() {
    background(127);

    molecules.forEach(molecule => {
        molecule.render();
        molecule.checkEdges();
        molecule.step();
    });

    drawGrid();
    splitIntoGrid();
    collision();
    displayFR();
}

function drawGrid() {
    for (i = 0; i < numOfRow+1; i++){
        for (j = 0; j < numOfCol+1; j++){
            noFill();
            stroke(0);
            rect(CellW*(j-1), CellH*(i-1), CellW, CellH);
        }
    }
}

function splitIntoGrid(){
    for (let i = 0; i < numOfRow; i++){
        for (let j = 0; j < numOfCol; j++){
            tempArray = [];
            molecules.forEach(molecule => {
                if (molecule.position.x > (CellW*j) &&
                    molecule.position.x < (CellW*(j+1)) &&
                    molecule.position.y > (CellH*i) &&
                    molecule.position.y < (CellH*(i+1))) {
                        tempArray.push(molecule.id);
                    }
            });
        }
    }
}

我如何检查所有对象之间的碰撞：

function collision() {
    for (let i=0; i < molecules.length; i++){
        for (let j=0; j < molecules.length; j++){
            let diff = p5.Vector.sub(molecules[j].position, molecules[i].position);
            check++;
            if (i != j && diff.mag() <= molecules[j].radius + molecules[i].radius){
                collisions++;
                molecules[j].changeColor();
            }
        }
    }
}

据我所知，我需要将这些 for 循环放在另一个遍历网格中每个单元格的循环中，但我不知道如何将搜索限制为对象的 tempArray(s)在

如果这有任何意义，这就是我正在尝试做的事情

function collision() {
  for (let k = 0; k < gridArray.length; k++){
    for (let i=0; i < gridArray.tempArray.length; i++){
        for (let j=0; j < gridArray.tempArray.length; j++){
            let diff = p5.Vector.sub(gridArray.tempArray[j].position, gridArray.tempArray.position);
            check++;
            if (i != j && diff.mag() <= gridArray.tempArray[j].radius + gridArray.tempArray[i].radius){
                collisions++;
                gridArray.tempArray[j].changeColor();
                gridArray.tempArray[i].changeColor();
            }
        }
    }
  }
}

Answer 1

网格单元由数组 gridArray 的数组表示。您需要为每个网格单元收集分子 。我的建议是使用 Sets instead of an Array，因为顺序无关紧要。这个想法是能够使用以下语法访问给定网格单元格 (i,j) 上的分子集：

gridArray[i][j]

以下代码将创建一个包含 numOfRow 个数组的数组：

const numOfRow = 5; const gridArray = (new Array(numOfRow)).fill([]);

gridArray 看起来像这样：

[ [], [], [], [], [] ]

在 splitIntoGrid 中，您正在检查哪些分子位于哪些网格单元中。这很好。但是，对于每个网格单元格，您将覆盖全局变量 tempArray。因此，在函数执行结束时，tempArray 将只保留最后一个网格单元格的分子，这不是您想要的。对于给定的网格单元，我们会将正确的分子添加到与该网格单元关联的 Set。

Set 数据结构有一个 #add 方法，可以将一个新元素附加到集合中：

function splitIntoGrid() { for (let i = 0; i < numOfRow; i++) { for (let j = 0; j < numOfCol; j++) { gridArray[i][j] = new Set(); molecules.forEach(molecule => { if (molecule.position.x > (CellW*j) && molecule.position.x < (CellW*(j+1)) && molecule.position.y > (CellH*i) && molecule.position.y < (CellH*(i+1))) { gridArray[i][j].add(molecule); } }); } } }

现在您已准备好检查每个网格单元上的碰撞。我们将在彼此内部总共有四个循环。两个用于浏览网格，两个用于比较每个网格单元格内包含的分子：

function collision() { for (let i = 0; i < numOfRow; i++) { for (let j = 0; j < numOfCol; j++) { gridArray[i][j].forEach(moleculeA => { gridArray[i][j].forEach(moleculeB => { const diff = p5.Vector.sub(moleculeA.position, moleculeB.position); if (moleculeA != moleculeB && diff.mag() <= moleculeA.radius + moleculeB.radius) { collisions++; moleculeA.changeColor(); moleculeB.changeColor(); } }); }); } } }

上面的代码中，#forEach就派上用场了。

在 JavaScript 中使用空间分区检测对象碰撞

Detecting object collision with spatial partitioning in JavaScript

javascript

p5.js