Bubbles --- making more efficient

Question

I made a program similar to the bubble screensaver It works fine, but is a bit slow and is a increase the no of bubbles, it looks as if its stuck

Suggest what should i do, to add more speed, the code that i made:

#include<dos.h>
#include<math.h>
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
#include<process.h>
#include<graphics.h>

void movement(int&,int&,int);
void bubbles(int,int,int,int);
void clearbubbles(int,int,int);


void main()
{
    int gdriver = DETECT,gmode;
    initgraph(&gdriver,&gmode,"C:\\Turboc3\\BGI");
    int x[10],y[10],r=40,d[10],i,j,k,l,c[10],n=10,t=100;
    randomize();
    // Initial Position, Direction & Color of Bubbles
    for(i=0;i<n;i++)
    {
        x[i]=random(getmaxx()-80)+41;
        y[i]=random(getmaxy()-80)+41;
        d[i] = random(8);
        c[i] = random(15)+1;
    }

    // Everything else

    for(i=0;i<=t;i++)   // Motiton of Bubbles
    {
        for(j=0;j<n;j++)        // Number of Bubbles
        {
            clearbubbles(x[j],y[j],r);
            // Checking Bubble Boundary Limits
            while(x[j] <= 1 || y[j] <= 1 || x[j] >= getmaxx()-1 || y[j] >= getmaxy()-1)
            {
                d[j] = random(8);
                movement(x[j],y[j],d[j]);
            }


            // Checking Collasion of Bubbles
            for(k=0;k<=n;k++)
            {
                clearbubbles(x[j],y[j],r);
                l = sqrt(pow(x[j]-x[k],2)+pow(y[j]-y[k],2));
                if(j != k)
                {
                    while(l <= 2*r)
                    {
                        d[j] = random(8);
                        movement(x[j],y[j],d[j]);
                        l = sqrt(pow(x[j]-x[k],2)+pow(y[j]-y[k],2));
                    }
                }
                movement(x[j],y[j],d[j]);
                bubbles(x[j],y[j],r,c[j]);
            }
        }
    }
    getch();
    closegraph();


}


void movement(int &x,int &y,int d)
{
    switch(d)
    {
        case 0: // Top Direction
            y = y - 1;
            break;
        case 1: // Top Right Direction
            x = x + 1;
            y = y - 1;
            break;
        case 2: // Right Direction
            x =x +1;
            break;
        case 3: // Bottom Right Direction
            x=x+1;
            y=y+1;
            break;
        case 4: // Bottom Direction
            y = y + 1;
            break;
        case 5: // Bottom Left Direction
            x = x-1;
            y=y+1;
            break;
        case 6: // Left Direction
            x=x-1;
            break;
        case 7: // Top Left Direction
            x=x-1;
            y=y-1;
            break;
    }
}

void bubbles(int x,int y,int r,int c)
{
    setcolor(c);
    circle(x,y,r);
}

void clearbubbles(int x,int y,int r)
{
    setcolor(BLACK);
    circle(x,y,r);
}

After all the suggestions i made a few changes in the code But, now the program hangs after a while and the control doesn't return back

the part i made changes in:

// Checking Collasion of Bubbles
     for(k=j+1;k<n;k++)
     {
      clearbubbles(x[j],y[j],r);
      l = ((x[j]-x[k])*(x[j]-x[k]))+((y[j]-y[k])*(y[j]-y[k]));
       while(l <= 4*r*r)
       {
        d[j] = random(8);
        movement(x[j],y[j],d[j]);
        l = ((x[j]-x[k])*(x[j]-x[k]))+((y[j]-y[k])*(y[j]-y[k]));
       }
      movement(x[j],y[j],d[j]);
      bubbles(x[j],y[j],r,c[j]);
     }

Why does `k` loop up to `k<=n`? Looks like a boundary error there. — Thomas W, Nov 17 '13 at 06:42

score 3 · Answer 1 · edited May 23 '17 at 10:31

Your N^2 algorithm is grossly inefficient. It requires time at least proportional to the square of the number of bubbles, to check for collisions.

'Boundary checking' and the 'collision resolution' algorithm are also possible to go into unproductive loops, as they rely on random movement to resolve the problem -- rather than taking directed action.

You should also use multiplication rather than pow() to calculate power 2. There's a huge difference in efficiency.

You could try a function to calculate distance, and/or you could recognize that you don't use the distance other than to compare it against 2 * r. This could cut out the sqrt and need for floating point.

For example, in pseudo-code:

const int TWO_R_SQUARED = r * r * 4;

int distanceSq (int dx, int dy) {
    return (dx * dx) + (dy * dy);
}

To fix it.. Boundary/ Collision resolution:

Change the 'boundary resolution' algorithm, to just clamp the bubble within valid coordinates. Single action, no looping, no possibility to get stuck.
Change the 'collision resolution' algorithm somewhat similarly. Pick a distance vector between the two bubbles, extend it to length 2*r and then the bubble to that point. (Ignore secondary collisions, they'll be dealt with next iteration.) Again, single action & no possibility to get stuck.

But, most of all, Collision Detection is the biggie.

Faster collision detection, requires an efficient method to find nearby bubbles. This would ideally be a Quadtree. https://en.wikipedia.org/wiki/Quadtree
If you wished to fake something up quickly, you could use a HashMap on size 2*r tiles & search the 9 surrounding tiles of a given bubble. Any bubble within 2*r distance has to be within those tiles, so this would at least let you get the subset reduced quickly. A cost of 9 hash lookups and perhaps 5-10 bubbles, versus 100s or thousands of bubble comparisons.

See:

So any idea on how to reduce N^3 n N^2 and some times it totally freezes, what can be done for it? — anmol mithal, Nov 17 '13 at 06:34
What does "clamp the bubble within valid coordinates" means. The movement, the bubble chooses after it hits the boundary is random, as there's no fixed position to which side of the boundary does the bubble hits — anmol mithal, Nov 17 '13 at 08:38
Getting stuck? You must have changed it in an incorrect way! :) Clamping within valid coordinates means, on X for example: `new_X=max(0, min(width, orig X))`. Just forcing the number into range, not fumbling round a loop hoping for randomness to return your system to a valid state. — Thomas W, Nov 18 '13 at 08:13
ok, i get it.one more thing, is a loop better or an if else statement? — anmol mithal, Nov 19 '13 at 01:29
i have posted the edited code above, you can check the condition that i made — anmol mithal, Nov 19 '13 at 02:00
Why not use a function to calculate `dx*dx + dy*dy`?? Write your code properly, for God's sake. Anyway, I've got projects on at the moment & fully committed so I'll leave you to it. I do notice you haven't even accepted my answer yet! Good luck. — Thomas W, Nov 21 '13 at 09:41

Bubbles --- making more efficient

1 Answers1