javascript - 円衝突検出 HTML5 キャンバス

Question

円が互いに衝突しているかどうかを確認したい。

円の 2 つの中心間の距離を取得し、その距離から各円の半径を差し引いて、「距離」が > 1 であるかどうかを確認することで、これを行うことができます。

たとえば、1000円でこれを効率的に行うにはどうすればよいですか? 多分私はどういうわけか最も近い20円かそのようなものを手に入れて、これらをチェックすることができますか? どうすれば効率的にそれを始められるかわかりません..

何か案は？

次に例を示します。

http://experiments.lionel.me/blocks/

score 6 · Accepted Answer

距離の正確な差を計算する前に、少なくとも中心と半径の x/y 位置を比較できます。その情報は円内で暗黙的に利用可能であり、単純な比較と加算/減算だけが必要です。

これにより、すべての円のペア間で x/y の単純な距離を比較し、明らかに衝突候補ではないものを破棄できます。

abs(x2 - x1) > (r2 + r1)
abs(y2 - y1) > (r2 + r1)

...円の中心間の X または Y の距離が半径の合計よりも大きい場合、それらは衝突することはできません。

可能なコライダーを絞り込んだら、正式な正確なデカルト距離を実行します。ここで、「重い」乗算/除算が行われます。

score 2 · Accepted Answer

四分木に円の中心の座標を格納することを検討すると、円がその四分円または隣接する四分円内の他の円と交差するかどうかを確認するだけで済みます。

1 つの注意点は、クアッドツリーのリーフノードの直径が最大円の半径の最小値であることを確認する必要があることです。そうしないと、隣接するノード以上の交差をチェックする必要があります。

http://en.wikipedia.org/wiki/Quadtree

円が十分に散在している場合、簡単な最適化として、円を x または y 軸で並べ替えて保存し、x または y 座標が円の半径内にある円を確認するだけで済みます。

score 0 · Accepted Answer

効率は、使用しているアルゴリズムの速度に関係します。たとえば、距離を計算する平方根アルゴリズムの速度であり、アルゴリズムに加えて、データ構造によってメモリの効率が決まります。計算を高速化する別の方法は、距離計算の精度を下げることです。

あなたが言ったように、円が衝突しているかどうかを検出する最良の方法は、円の中心座標と半径を変数に保存し、半径を差し引いたときに中心間の距離が0に等しいかどうかを計算することです。

score 0 · Accepted Answer

Keith Peter のAdvancED ActionScript 3.0 Animation book を強くお勧めします。この本には、Actionscript での Quadtree アルゴリズムの具体的な実装が記載されています。

基本的な手順は次のとおりです。

最初に 2 次元のグリッドを作成し、すべてのボールをフィールド全体にランダムに散らします。

private function createGrids():void {
    _grids = new Array();
    for (var i:int = 0; i< stage.stageWidth / GRID_SIZE; i++) {
        _grids[i] = new Array();
        for (var j:int = 0; j< stage.stageHeight / GRID_SIZE; j++) {
            _grids[i][j] = new Array();
        }
    }
}

ボールをグリッドセルに割り当てる

private function assignBallsToGrid():void {
    for (var i:int = 0; i< numBalls; i++) {
        var ball:Ball = Ball(_balls[i]);
        var xpos:int = Math.floor(ball.x / GRID_SIZE);
        var ypos:int = Math.floor(ball.y / GRID_SIZE);
        _grids[xpos][ypos].push(ball);
    }
}

1 つのセルで 2 つのボールが衝突しているかどうかを確認してから、隣接するセルのボールを確認します。Charles Ma がここで唯一の考慮事項を述べたように、グリッドセルの寸法は最大のボール直径以上でなければなりません。

private function checkOneCell(x1:Number, y1:Number):void {
    var _cell:Array = _grids[x1][y1] as Array;
    for (var i:int = 0; i< _cell.length-1; i++) {
        var ballA:Ball = _cell[i] as Ball;
        for (var j:int = i+1; j< _cell.length; j++) {
            var ballB:Ball = _cell[j] as Ball;
            checkCollision(ballA, ballB);
        }
    }
}

private function checkTwoCell(x1:Number, y1:Number, x2:Number, y2:Number):void {
    if (x2 < 0) { return } 
    if (x2 >= _grids.length) { return }
    if (y2 >= _grids[x2].length) { return }

    var _cell0:Array = _grids[x1][y1] as Array;
    var _cell1:Array = _grids[x2][y2] as Array;

    for (var i:int = 0; i< _cell0.length; i++) {
        var ballA:Ball = _cell0[i] as Ball;
        for (var j:int = 0; j< _cell1.length; j++) {
            var ballB:Ball = _cell1[j] as Ball;
            checkCollision(ballA, ballB);
        }
    }
}

private function checkCollision(ballA:Ball, ballB:Ball):void {
    var dx:Number = ballB.x - ballA.x;
    var dy:Number = ballB.y - ballA.y;
    var dist:Number = Math.sqrt(dx*dx + dy*dy);
    if (dist < ballB.radius + ballA.radius) {
                     // do something
    }
}

メインメソッドは次のようになります。

private function checkBallsCollision():void {
    for (var i:int = 0; i< _grids.length; i++) {
        for (var j:int = 0; j< _grids[i].length; j++) {
            checkOneCell(i, j);

            checkTwoCell(i, j, i+1, j);
            checkTwoCell(i, j, i, j+1);
            checkTwoCell(i, j, i-1, j);
            checkTwoCell(i, j, i+1, j+1);
        }
    }
}

ノート：

コードは Actionscript で記述されていますが、Javascript で簡単に実装できます。

javascript - 円衝突検出 HTML5 キャンバス

4 に答える 4

Related

Reference