Solved

Optimization

Posted on 1998-11-19
10
186 Views
Last Modified: 2010-05-18
Hello

As some of you know, I am creating an Asteroids clone.  I am having some trouble getting this code to run fast however.

    // Move current shots:
    for (j = 0; j < 1000; j++)
    { if (m_Players[i].m_Shots[j].IsDead () == true)
      { continue; }
      COLORREF color = dc->GetPixel ((int) m_Players[i].m_Shots[j].GetX (), (int) m_Players[i].m_Shots[j].GetY ());

      for (k = 0; k < m_NumRocks; k++) // Asteroid <-> shot collision
      { if (m_Rocks[k].IsDead () == true)
        { continue; }

        if (color > 0)
        { if (m_Rocks[k].Distance (m_Players[i].m_Shots[j].GetX (), m_Players[i].m_Shots[j].GetY ()) < m_Rocks[k].GetSize ())
          { m_Rocks[k].Explode (dc);
            m_Rocks[k].Spawn (dc, m_Rocks, m_NumRocks);
            m_Players[i].m_Shots[j].Explode (dc, m_Players[i].m_Particles, 1000, 10);
          }
        }
      }

      for (k = 0; k < 2; k++) // Player <-> shot collision
      { if (k == i)
        { continue; }
        if (m_Players[k].IsDead () == true)
        { continue; }

        if (m_Players[i].m_Shots[j].Distance (m_Players[k].GetX (), m_Players[k].GetY ()) < 20)
        { m_Players[k].Hit (dc, 3);
          m_Players[i].m_Shots[j].Explode (dc, m_Players[i].m_Particles, 1000, 50);
        }
      }
    }

You see, occasionally as the result of a power up, a lot of shots are generated.  These shots must be checked each frame to make sure they haven't collided with anything.  The code above is what is doing the checking.

There are a few problems with the code, however.  The main one is the fact that it is so slow at times.  Note that the asteroids are polygons hence the "GetPixel" to make sure the shot is indeed within the polygon.
0
Comment
Question by:a121496
10 Comments
 
LVL 8

Expert Comment

by:Answers2000
ID: 1178285
Why not store a bounding rectangle for the polygon (the smallest rectangle that contains each polygon) ?

You can then add a test to check it's within any bounding rectangle before doing the GetPixel etc.  In most cases, assuming no many asteriods, it won't be inside any rectangle, so it will be faster.  This can be a test after the rock IsDead test.

I assume you don't want fundamental re-design type answers...so I won't give one of these..

By the way, use the profiler to check what you think is the slow bit, really is.
0
 
LVL 5

Expert Comment

by:scrapdog
ID: 1178286
The player is not going to notice much difference if you just use bounding rectangles.  The GetPixels you are using is what is eating up a lot of time.

If you REALLY need to be accurate and insist on checking the pixels, you should check the bounding rectangle first.  If it is not inside the rectangle then short circuit the evaluation and go to the next one.  If it is, THEN check the pixels.

Chances are you will only have to check the pixel no more than once in a loop, so you can save a lot of time by avoiding it.  You will have NumRocks more boolean evaluations, but the tradeoff is NumRocks less of the expensive pixel checks, so overall the code will be faster.
0
 

Expert Comment

by:Mithander
ID: 1178287
Just one comment, the way I would read you code is that you get the color that is at where the pixel is at.  Wouldn't this always return the color of the pixel.  If it does than you are going to go through the loop once for every bullet you have, regardless if it hit anything.
0
 

Author Comment

by:a121496
ID: 1178288
Okay, I see what I have to do.  I have attempted to implement the bounding box idea, but since I'm no pro-programmer, I am not sure if the algorithm is right.  Here it is:

void CRock::GeneratePoints (void)
{ double Angle = 0.0;
  int p;

  m_NumPoints = rand () % 4 + 4;

  for (p = 0; p < m_NumPoints; p++)
  { m_Points[p].x = (long) (cos (Angle) * (rand () % m_Size));
    m_Points[p].y = (long) (sin (Angle) * -(rand () % m_Size));
    Angle += DEG2RAD * (360 / (rand () % 2 + m_NumPoints - 1));
  }

  m_BoundRect.top = 1000;
  for (p = 0; p < m_NumPoints; p++)
  { if (m_Points[p].y < m_BoundRect.top)
    { m_BoundRect.top = m_Points[p].y; }
  }

  m_BoundRect.left = 1000;
  for (p = 0; p < m_NumPoints; p++)
  { if (m_Points[p].x < m_BoundRect.left)
    { m_BoundRect.left = m_Points[p].x; }
  }

  m_BoundRect.bottom = -1000;
  for (p = 0; p < m_NumPoints; p++)
  { if (m_Points[p].y > m_BoundRect.bottom)
    { m_BoundRect.bottom = m_Points[p].y; }
  }

  m_BoundRect.right = -1000;
  for (p = 0; p < m_NumPoints; p++)
  { if (m_Points[p].x > m_BoundRect.right)
    { m_BoundRect.right = m_Points[p].x; }
  }
}

This is the code used to generate the points relative to the center of the asteroid.  The code after that is for determining the bounding box.  I am not sure if the problem lies here, or here:

if ((m_Players[i].m_Shots[j].GetX () > m_Rocks[k].m_BoundRect.left) &&
    (m_Players[i].m_Shots[j].GetX () < m_Rocks[k].m_BoundRect.right) &&
    (m_Players[i].m_Shots[j].GetY () > m_Rocks[k].m_BoundRect.top) &&
    (m_Players[i].m_Shots[j].GetY () < m_Rocks[k].m_BoundRect.bottom))
{ if (color > 0)
  { m_Rocks[k].Explode (dc);
    m_Rocks[k].Spawn (dc, m_Rocks, m_NumRocks);
    m_Players[i].m_Shots[j].Explode (dc, m_Players[i].m_Particles, 1000, 10);
  }
}

The collisions don't seem to be detected properly.  I am at a loss as to what the problem is.  Does the above code look right?

Thanks, I have increased points to 50 for your extra help (25 was a bit low).
0
 
LVL 5

Expert Comment

by:scrapdog
ID: 1178289
You made it much more complex than it need be...

xdist = abs(ObjectA.X - ObjectB.X);
ydist = abs(ObjectA.Y - ObjectB.Y);
if ((xdist < (ObjectA.RectWidth + ObjectB.RectWidth)) &&       (ydist < (ObjectA.RectHeight + ObjectB.RectHeight)))   { do collision }


(the values of RectWidth and RectHeight should be set to 1/2 of the object's width and height, respectively)
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

Author Comment

by:a121496
ID: 1178290
I found the problem (I was comparing the shot's to the bounding box without correction for the asteroid's current position).

scrapdog - I changed the second piece of code I mentioned in my last comment to:

if (fabs (m_Players[i].m_Shots[j].GetX () - m_Rocks[k].GetX ()) <= fabs (m_Rocks[k].m_Bound.left - m_Rocks[k].m_Bound.right) &&
    fabs (m_Players[i].m_Shots[j].GetY () - m_Rocks[k].GetY ()) <= fabs (m_Rocks[k].m_Bound.top - m_Rocks[k].m_Bound.bottom))
{ if (color > 0)
  { m_Rocks[k].Explode (dc);
    m_Rocks[k].Spawn (dc, m_Rocks, m_NumRocks);
    m_Players[i].m_Shots[j].Explode (dc, m_Players[i].m_Particles, 1000, 10);
  }
}

which seems a little faster than my version.  Is there any way I can change any of the other code?  Or perhaps I am still doing this poorly? =)
0
 
LVL 5

Expert Comment

by:scrapdog
ID: 1178291
Let's take this one step at a time.

First of all get rid of all your floating points.  Use integers instead.  Floating point operations can be a lot of dead weight.

Second, you do not need to define the left, right, top, and bottom of the bounding rectangle.  Doing this would require you to recalculate all four of these values every frame.  Instead, use width and height of the rectangle  (as in the code I showed you).

Calculate the top, bottom, left, right ONCE (after you generate the points).  After you do this, don't store these;  instead calculate the height and width from these and store these...
0
 

Author Comment

by:a121496
ID: 1178292
Okay, thank you for your help scrapdog, the program runs about 50% faster now (no kidding).  Please post an answer and I can give you the points.  Thank you!
0
 
LVL 5

Accepted Solution

by:
scrapdog earned 50 total points
ID: 1178293
You're welcome.

=)
0
 

Author Comment

by:a121496
ID: 1178294
=)
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Connecting to MS SQL db from Win32 application written in C 3 79
How to convert MFC::CString to UTF8 wchar_t* 10 150
Issues with C++ Class 19 81
VS2015 Redefinition errors 4 30
Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

864 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now