Solved

Optimization

Posted on 1998-11-19
10
191 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
Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

 

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
 

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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
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 be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

821 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