How to improve my 'algorithm'

Hi all,
I need in my game some algorithm which will tell me where is a point of collision with some object beetween Vec2 A position and Vec2 B position.
It looks like that:

It is looking for the first point which collide with this line between Point A and point B.

My first idea:
I calculated offset in X and Y. Then I created a loop which adds offset to my Vec2 A and checks if some PhysicsShape contain this point. If it is, I save the position of collision and go out from my loop.

Some simplified code:
(my_bodies is a std::vector which contains all objects(sprites,PhysicsBodies/Shapes) in my game)

Vec2 delta;
delta.x = B.x - A.x;
delta.y = B.y - At.y;

float dist = sqrtf( ( delta.x*delta.x ) + (delta.y*delta.y)  ); //distance from A to B


Vec2 offset;
offset.x = delta.x/dist;
offset.y = delta.y/dist;

while(collision==false && A!=B)
{
        A.x+=offset.x;
        A.y+=offset.y;
        
        for(int i=0;i<my_bodies.size();i++)
        {
                 my_bodies[i]->check_collision(A)  //if true collision true and end loop

        }

}

And check_collision looks like that:

bool check_collision(cocos2d::Vec2 P)                                                    {

auto shape = PBody->getShapes();

for(int i=0;i<shape.size();i++)
{
    if(shape.at(i)->containsPoint(P))
    {
        return true;
    }
    else if(i==shape.size()-1)
        return false;
    
}}

It works perfect but it was a killer for processor (too much loops, and objects) :wink:

So my second idea was to use RayCast. It works definately faster but it is not perfect. I mean if physicsBody is too small or is rotated and the edges are not ‘sharp’ RayCast doesnt see collision.

So now I dont know what to do;(
Have you got some ideas to improve my upper algorithm or maybe solve it in different way?

Thanks a lot :wink:

Hi, I have 2 simpler ways to do this…
But before that some comment on your code.
Since you’re using containsPoint() for lots of sprites in your game, then obviously it will add a toll on your FPS
Note: 2 loops are nothing except when you’re having lots and lots of bodies…
Now, just see if any of these below helps…

First approach,

  1. Make a physics line joining those 2 points.
    2)Then in the collision handler find the collision contact point
    This way you don’t have to iterate through every body as the physics world will take care.
    Also, in this collision handler itself, just get the physics body/shape whichever you want…

This should solve the issue… No loops from your side :smiley:

Second approach,
find the vector between those 2 points A and B, and then normalize this vector.
And in scheduled update function constantly find a dummy vector(which is difference between position of body and any of the point either A or B). This should be done in a loop for every sprite… Note: here there is no role of physics… Even simple sprites(without physics bodies) can be detected this way.
If the normal vector you calculated earlier and this dummy vector(after normalizing it also) are same then get the Position of that particular sprite which will serve your purpose of collision point, which obviously lies on the line joining A and B.
Some Small Edit:
I think in this second approach, you must also check whether position of the sprite lies between
<=A.x && <A.y && >=B.x && >=B.y (Ingore this blue link… it has come automatically. its not link)
because simply finding vector and normalizing it will make you find the sprite which lies on the line joining A and B but it can be outside the line segment A and B… anyways, this above extra check will help to rectify this also :smile:

Actually, this above thing is also same as containsPoint() but this overall approach removes requirement one additional loop which is you’ve started as

Btw, how many physics bodies are there in your scene. Because I don’t think that your logic should be much of a problem until there are lots of bodies…

If not understood, then please ask again :smile:

Thanks for your fast feedback :wink:

Actually there are 3 loops (one while, and two for). I have about 30 sprites in my scene. But I’ve created my PhysicsBody using PhysicsEditor, so every sprite has about 15 ‘shapes’ :wink: So my check_collision function has a lot to do too :wink:

As I said before I have 30 sprite so 30 bodies, and each body has 15 shapes.
Yeah, it shouldn’t be a big problem but I have 4 that lines which check collision :wink:

I will try your ideas and get you know if it works;)

cocos2d-x provide you with 2 important function here cocos2dx::vec2::IsSegmentIntersect and cocos2dx::vec2::getIntersectPoint.

Simple way, 1st loop through each “line” of your body and check if the segment is intersecting with line AB, then next, get the intersect point.

@Pablo95

yeah, actually it doesnot matter… because it is not too much. As you keep on increasing nested loops so your performance will drop on low end devices… Also, the major problem is your physics bodies with 15 shapes each :smiley:
Anyways, if the size is small enough then it should not be a problem :smile:
Also, hope you’re getting this performance issue on AVD-emulator and not real device… If on real device, oh man… are you checking it on low end device… If yes, then again… oh man… serious problem… tough computation and too much rendering :smile: JUST DON’T SUPPORT FOR LOW END DEVICES IF THE PROBLEM STILL PERSISTS…

One more thing… Also try what @GilzhetNwach said…

I am not much experienced…Can you please explain to us what do you mean by line… Is it vector of motion of the sprite/physicsBody ?

I’ve tried to run my game on Samsung Galaxy S3 and even on that quite good device there was a big problem to calculate it fast.

I will maybe explain a little big my game concept to understand it better.

When I click on ‘Laser’ button then all calculations start work(I mean all loops etc.)
We start at point A and we go do point B and check if there is some body(PhysicsBody) if yes we draw a ray which connect this A and B point. But if this body is a mirror we ‘reflect’ previous ray(line) and continue our calculation(algorithm) as long as our ‘line’ between this points doesn’t touch a edgebox of our screensize, or touch any other object which isnt the mirror :wink:

So I need very fast way to solve this problem,. Tommorow I will try your idea, I hadn’t time to do it earlier

No No,… When i said :

I meant, I was asking @GilzhetNwach about the implementation of below

Ok, I’ve tried all your advices:

It turns out that neither @catch_up second approach , nor the idea of ​ @GilzhetNwach did not solve the problem.
Maybe amout of FPS are a liitle bit better but it is still same ‘crash’ for 0.5sec which is very annoying.

Hmm, I havent checked first approach(Physics line joining those 2 points) because I think it is impossible. Firs I have to check a collision and then I create a sprite (ray), which connect previous point of collision with next if exists.

So I think that this problem is not to resolve on mobile devices;D It works fluently only on my PC (i5 3.2Ghz ) but even here is a drop of fps to 25 from 50-60 during calculation

Maybe run all calculation in separate thread will be a good idea? Maybe we will be waiting 2sec until game draws all rays, but will work fluently, what do you think about it? It will help?