Solved

Optimization

Posted on 1998-11-19
10
183 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
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 

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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

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…
  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 goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

746 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

11 Experts available now in Live!

Get 1:1 Help Now