Solved

Optimization

Posted on 1998-11-19
10
198 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

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

Enroll in July's Course of the Month

July's Course of the Month is now available! Enroll to learn HTML5 and prepare for certification. It's free for Premium Members, Team Accounts, and Qualified Experts.

Question has a verified solution.

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

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
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…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
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.

632 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