I have performance issues with the code I'm using to detect collision between items

Question

I managed to make this work and do what I needed after a while but now my problem is performance. As you can see I need it for 14+ items. I tested at first for 5 items and it worked ok but after I added more the performance dropped a lot. As for the collision detection class, I assume you know what it does and how it works(that I managed to make it work since the registration point only works when set to upper left side of the movie clip and mine was in the middle) If you need any other details or information please don't hesitate to ask and I will try my best to provide it. So in a few words what is need is: -

I have 14+ objects and need to display them
I need a unique random position for every object
Make new random position and check to see if it's shape collides with the other objects
If that object doesn't collide with the other object displayed the movieClip
If that object collides with another movieClip get another random position
Check again the object with the other objects to see if it collides
If YES find another position / If NO show the object
Do this until all the objects are positioned without colliding with each other

I believe I'm missing something and that this code could be better but really don't have any other good ideas and didn't find anything on the internet that might help. Please give me a hand.

*** Also keep in mind that I don't want the grid solution for collision detection

private var objArray : Array = new Array (movieClip1, movieClip2, movieClip3, movieClip4, movieClip5, movieClip6, movieClip7, movieClip8, movieClip9, movieClip10, movieClip11, movieClip12, movieClip13, movieClip14);
private function init():void
    {
        trace("[TRACE]:Init GameScreen");
        addEvents();
        startTimerCollision();
    }
private function addEvents():void
    {
        _timer.addEventListener(TimerEvent.TIMER, timer); //Listen for the Timer event _timer and trigger the function timeLeft.
        Repository.STAGE_REF.addEventListener(Event.ENTER_FRAME, frameRate);
    }
private function startTimerCollision():void
    {           
        _timer.start();                         //start the timer

        _collisionCheck = new CollisionTest();
    }
private function frameRate(event:Event):void
    {
        //add 1 to the frame count every frame
        _frame++;
    }
function timer(event:TimerEvent):void
    {   
        timpul--
        _TimerSound.play();

        showObjs();
    }
private function randomPosition(obj:MovieClip):void
    {
        obj.x = obj.width + Math.random() * (stage.stageWidth - obj.width * 2);
        obj.y = obj.height + Math.random() * (stage.stageHeight - obj.height * 2);  
    //  trace(obj + " RANDOM POS= " + "x: " + obj.x + " / y:" + obj.y);
    } 

    private function randomALLPositions():void
    {
        for (var i = 0; i < objArray.length; i++)
        {
            randomPosition(objArray[i]);
        }
    }

    private function checkAllCollision(obj:MovieClip):Boolean
    {
        var collisionStatus : Boolean;
        for (var i = 0; i < objArray.length; i++)
        {
            if (obj != objArray[i])
            {               
                if (_collisionCheck.complex(obj, objArray[i]))
                {
                    collisionStatus = true;
//                  trace("collision detected: " + obj + " and " + objArray[i]);
                    randomPosition(obj);
                    checkAllCollision(obj);
                }
                else
                {
                    collisionStatus = false;
                }
            }
        }
        return collisionStatus;
    }

    private function showObjs():void
    {

        ////////////////////////////////////////////////////////ONLINE
        var i:int = 0;
        var j:int;
        var l:int = objArray.length;

        for (i; i < l; i++)
        {
            randomPosition(objArray[i]); 
            for (j = 0; j < l; j++)
            {
                if (objArray[i] != objArray[j])
                {
    //              trace("OBJ " + (i+1) + " with OBJ " + (j+1) + "---------> CHECKING");
                    //while (checkAllCollision(objArray[i]))
                    if(checkAllCollision(objArray[i]) == true)
                    {
    //                  trace("OBJ " + (i+1) + " with OBJ " + (j+1) + "---------> Collision DETECTED");
                        randomPosition(objArray[i]);
    //                  trace("OBJ "+ (i+1) + " NOW= " + "x: " + objArray[i].x + " / y:" + objArray[i].y);
                    }
    //              trace("OBJ " + (i+1) + " with OBJ " + (j+1) + "---------> OK");
                }
            }
            addChild(objArray[i]);

        }
        ////////////////////////////////////////////////////////ONLINE

        for (var z = 0; z < objArray.length; z++)
        {
            TweenLite.to(objArray[z]["gime" + (z+1)], /*time:*/ 0, {scaleX:0, scaleY: 0});
            TweenLite.to(objArray[z]["gime" + (z+1)], /*time:*/ 0.5, {scaleX:1, scaleY: 1});
        }   
    }

Depending on how large the Sprites are that are being generated, and how big the stage is, this could cause real slow down because if there is only 1 spot available for the final Sprite, it could take a long time to randomly find that spot. A better approach would be to have discreet areas that the Sprite can be placed in (and given a random offset that keeps it within that discreet area) and then removes that area from the list of possible random places to put the next Sprite in. Make sense? — Neal Davis
That way you are only randomly choosing between the 23 remaining spots, then the 22 remaining spots, and not the 12 spots that have already been used, so you don't have to "check if they collide with anything" because they never will with this technique. Now, the downside to this is that it isn't exactly random, but if you need it to be completely random you are going to run into the same problem. — Neal Davis
Just saw your note about the grid solution (which mine is). Sorry. — Neal Davis
Thank you but as I've said the grid solution doesn't help me :( — Alexandru Balea
You need to find some way to limit the randomness. That's the bottom line. Trying to find a needle in a haystack can be done quickly if you look at each piece of hay one at a time and never look at the same piece of hay twice, but that's not random, that's systematic. When you have only one or two objects to add, there is limited space to add them to since much of your stage is already occupied. Finding an available spot is like searching for a needle in a haystack; when you look at each spot randomly it is like randomly selecting a piece of hay and seeing if it is the needle, and if it's not — Neal Davis

Neal Davis Neal Davis · Accepted Answer · 2017-01-25T22:55:05

I have a couple ideas

Random offset to populate possible locations

make an array of points and each point is offset from the previous point by the minimum amount needed to keep it from colliding with an object that is placed at that point. Then you'll have this nice array of points and you can randomly select and none of them will overlap.

That's the idea any way. Do this for the x offset. Then for y offset you'll have to do some more trickery that I haven't figured out yet.

I have performance issues with the code I'm using to detect collision between items

2 Answers