c++ - 泡泡---让效率更高-6ren

c++ - 泡泡---让效率更高

转载作者：行者123 更新时间：2023-11-30 02:50:58

我做了一个类似泡泡屏保的程序它工作正常，但有点慢并且增加了气泡的数量，看起来好像卡住了

建议我应该怎么做，以提高速度，我制作的代码:

#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);
}

在所有建议之后我对代码做了一些修改但是，现在程序在一段时间后挂起并且控件没有返回

我修改的部分:

// 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]);
     }

最佳答案

您的 N^2 算法效率极低。检查碰撞所需的时间至少与气泡数量的平方成正比。

“边界检查”和“冲突解决”算法也有可能进入非生产性循环，因为它们依靠随机移动来解决问题——而不是采取定向行动。

您还应该使用乘法而不是pow() 来计算2 的幂。这在效率上存在巨大差异。

您可以尝试一个函数来计算距离，和/或您可以认识到除了将它与 2 * r 进行比较之外，您不使用该距离。这可以减少 sqrt 和 float 的需要。

例如，在伪代码中:

const int TWO_R_SQUARED = r * r * 4;

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

修复它..边界/碰撞解决:

更改“边界分辨率”算法，将气泡限制在有效坐标内。单一 Action ，不循环，不卡顿。
以类似的方式更改“冲突解决”算法。在两个气泡之间选择一个距离 vector ，将其扩展到长度 2*r，然后将气泡扩展到该点。 (忽略二次碰撞，它们将在下一次迭代中处理。)同样，单一 Action 且不可能卡住。

但是，最重要的是，碰撞检测是个大问题。

更快的碰撞检测，需要一种有效的方法来找到附近的气泡。理想情况下，这将是四叉树。 https://en.wikipedia.org/wiki/Quadtree
如果您想快速伪造一些东西，您可以在大小为 2*r 的图 block 上使用 HashMap 并搜索给定气泡周围的 9 个图 block 。 2*r 距离内的任何气泡都必须在这些图 block 内，因此这至少可以让您快速减少子集。 9 次哈希查找和可能 5-10 次气泡的成本，与 100 次或数千次气泡比较的成本相比。

参见:

关于c++ - 泡泡---让效率更高，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20027903/