[ActionScript 3.0] RDCアルゴリズムによる衝突判定

オブジェクト同士の衝突判定を行う場合、RDCアルゴリズムを使うと総当たりで判定を行うより判定回数をかなり減らすことができる。
(オブジェクトの位置を元に領域をいくつかに分割して、その領域内のオブジェクト同士だけで衝突判定を行うやり方である）

Main.as

package
{
    import flash.display.*;
    import flash.events.Event;

    [SWF(width="500", height="500", backgroundColor="#ffffff")]
        public class Main extends MovieClip
        {
            public var rdc:RDC;
            public var objects:Array;

            public function Main()
            {
                stage.scaleMode = StageScaleMode.NO_SCALE;
                stage.align = StageAlign.TOP_LEFT;

                // create some simple objects
                createObjects(100);

                // allow a maximum number of 8 objects/group
                RDC.SUBDIVISION_THRESHOLD = 8

                    // create RDC instance with a reference to a function
                    // that handles the collision
                    rdc = new RDC(collide);

                this.addEventListener(Event.ENTER_FRAME, enterFrameHandler);
            }

            private function enterFrameHandler(event:Event):void
            {

                for each (var c:Circle in objects){
                    c.color = 0xff;
                    c.x += c.vx;
                    c.y += c.vy;
                    if(c.x - c.radius <= 0){
                        c.vx = Math.abs(c.vx);
                    }else if(c.x + c.radius >= stage.stageWidth){
                        c.vx = -Math.abs(c.vx);
                    }else if(c.y - c.radius <= 0){
                        c.vy = Math.abs(c.vy);
                    }else if(c.y + c.radius >= stage.stageHeight){
                        c.vy = -Math.abs(c.vy);
                    }
                }

                // run the recursive algorithm
                // x-axis is first analyzed (0), then y-axis (1)
                rdc.recursiveClustering(objects, 0, 1);

            }

            private function collide(a:Circle, b:Circle):void
            {
                // simple bounding sphere distance check
                var r2:Number = a.radius + b.radius;
                var dx:Number = a.x - b.x;
                var dy:Number = a.y - b.y;
                var dist:Number = Math.sqrt(dx * dx + dy * dy) - r2;

                if (dist < -3){
                    for(var i:int = 0 ; i < objects.length ; i++){
                        if(objects[i] == a){
                            removeChild(objects[i]);
                            objects.splice(i,1);
                            newCircle();
                            return;
                        }
                    }
                }
                if (dist <= 0)
                {
                    // do something meaningful
                    a.color = b.color = 0xff0000;

                    // 衝突軸ベクトル
                    var cx:Number = a.x - b.x;
                    var cy:Number = a.y - b.y;

                    // 正規化
                    var len:Number = Math.sqrt(cx*cx+cy*cy);
                    cx /= len;
                    cy /= len;

                    var dot:Number = (a.vx - b.vx)*cx + (a.vy - b.vy)*cy;

                    // 定数ベクトル
                    var constX:Number = dot * cx;
                    var constY:Number = dot * cy;

                    a.vx = -constX + a.vx;
                    a.vy = -constY + a.vy;
                    b.vx = constX + b.vx;
                    b.vy = constY + b.vy;
                }
            }

            private function createObjects(count:Number):void
            {
                objects = [];

                for (var i:Number = 0; i < count; i++)
                {
                    newCircle();
                }
            }

            private function newCircle():void{
                var radius:Number = rand(1, 10);
                var x:Number = rand(radius, stage.stageWidth - radius);
                var y:Number = rand(radius, stage.stageHeight - radius);
                var circle:Circle = new Circle(x, y, radius);
                addChild(circle);
                circle.vx = Math.random()*2;
                circle.vy = Math.random()*2;
                objects.push(circle);
            }

            private function rand(min:int, max:int):int
            {
                return min + Math.floor(Math.random() * (max - min + 1));
            }
        }
}

Circle.as

package
{
    import flash.display.*;

    public class Circle extends Sprite
    {
        public var radius:uint;
        public var vx:Number;
        public var vy:Number;

        public function Circle(x:uint, y:uint, radius:uint)
        {
            this.x = x;
            this.y = y;
            this.alpha = 0.6;
            this.radius = radius;
            this.vx = this.vy = 1;
        }

        public function set color(c:int):void{
            this.graphics.clear();
            this.graphics.lineStyle(2, c, 1);
            this.graphics.beginFill(c);
            this.graphics.drawCircle(0, 0, radius);
            this.graphics.endFill();
        }
    }
}