C++: Finding nearest object using X/Y method. (To be used for collision detection and distance checking, such as finding closest enemy)

I have the following code:

                  minRange = range;
                  foundAt = -1;
                  Nobj = game->N(GameStateClass::ships);
                  for (i = 0; i < Nobj; i++)
                  {
                        ShipClass *ship= &game->ship[i];

                              xd = ship->now.x - this->now.y;
                              yd = ship->now.y - this->now.y;
                              g_logFile << xd << " " << yd << endl;
                              xd2 = xd * xd;
                              yd2 = yd * yd;
                              dist2 = xd2 + yd2;
                              if(dist2 < minRange)
                              {
                                    minRange = dist2;
                                    foundAt = i;
                              }
                  }


This is used to find what the CLOSEST ship. Ths issue is however that this seems to eat up alot of cpu time when theres 100 ships to check, when every 'bullet' is calling this to check if its going to collide/what the nearest enemy is etc.

Basically it works via getting the closest ship, which is the above coding, then a simple check on that nearest ship to see if its collided. The issue here however is the 'checking to see' what enemy is closest.

Can anyone recommend any way to optimize this, or any other ideas that can replace a function like this to run alot faster? It takes alot of cycles to run this on each bullet (weapon fire!)
LVL 7
VallerianiAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

pgnatyukCommented:
If you will calculate the dist as xd2 + yd2, it can be enough.
Of course, the minRange should be calculated as sqrt from range.

Also comment g_logFile << etc.
Also can be ShipClass& ship= game->ship[i];

Probably, these small changes will solve the question. Next step - do not call this function too often.
0
VallerianiAuthor Commented:
Oh sorry the g_log was just a test.

The issue is what if its not called often, won't bullets just pass right through ships for example?
0
ikeworkCommented:
Hi Valleriani,
It the optimizations in the function itsself, like pgnatyuk suggested is not enough, then you might consider Bounding Volume Hierarchies.
  http://en.wikipedia.org/wiki/Bounding_volume_hierarchy

Basically those are trees from bounding volumes, llike the Octree in 3D or the Quadtree in 2D.

   http://en.wikipedia.org/wiki/Quadtree
So your Ships are put in this tree and you can easily filter objects that are nearby, so you dont have to do collsion tests for all objects, only for objects, that are in a given range.
Here is another interesting Wiki-Page about different approaches on Efficient Collision Detection Tests:
  http://en.wikipedia.org/wiki/Collision_detection


ike


0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
The Ultimate Tool Kit for Technolgy Solution Provi

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy for valuable how-to assets including sample agreements, checklists, flowcharts, and more!

pgnatyukCommented:
Of course, ikework gave few perfect solutions.

I can propose a simple one - split all your objects in a separate groups - rectangles, small rectangles, the size should be as two ranges. Then, you will need to find in which of these rectangles your ship is now. Then, you will need to check the objects only from this rectangle. In the worst case, you will have to check four rectangles.
This method allows to minimize the number of objects to check and exclude the heavy calculations.
 
0
ikeworkCommented:
@pgnatyuk: Thats basically, what the Quadtree does ;)
0
pgnatyukCommented:
Yes. Sorry.
I didn't know the name :( and opened your link after the post.
0
ikeworkCommented:
No problem, your idea of simplifying the tree into a grid might worth a try, didnt want to stop you :)
0
ikeworkCommented:
Can you tell us a bit more about your game:

1) What is the size of the game-field?

2) Are there different sized objects in your game? Please give some example-sizes, ships, bullets etc.

3) Can the objects move freely? Orientation freely? Or only 0, 90, 180 and 270 degrees or something similar?

4) Can you post a screenshot so we get an idea?
0
VallerianiAuthor Commented:
pgnatyuk's way reduced the ticks about 30% more, which was a good turn, but still not enough, I will probably try to implement that tree if I can study/figure out how then.

I'll attach a image here of an example. This is just one 'area' atm theres tons of places like this so I feel the quadtree style will probably help tons.

There are different size bullets/etc as you see, very small 4x4,5x5, and ships can be anywhere between 28x28 to 80x80. The size of the gamefield atm is pretty much unlimited right now, depending on how many solar systems are added. Normally there is only 'one' though.


small.png
0
VallerianiAuthor Commented:
We recently added DirectX to the game, but we noticed the game engine was still slow. We found out the reason was the dist/collision updating but its' rather a pain to do. I'm probably going to have to look around for some good examples and try to follow em :)
0
ikeworkCommented:
Another algorithm to minimize collision tests in the so called "Broadphase" is the "Sweep and Prune" aka "Sort and Sweep" Algorithm.

It sorts the bounding boxes of the objects in each axis, x- and y-axis and checks if they overlap in both axes, if not they are not colliding, if yes they are scheduled for the real collision tests.

  http://en.wikipedia.org/wiki/Sweep_and_prune
  http://www.codercorner.com/SAP.pdf

0
ikeworkCommented:
You could also use a Collision-Detection Library. Bullet has one, its called "BulletCollision".

  http://www.bulletphysics.com/Bullet/BulletFull/main.html

That will safe you some time and trouble ;)
0
VallerianiAuthor Commented:
Actually, I found out it is ShipClass& ship= game->ship[i]; causing the remaining delay when checking. Mainly I'm not sure how to solve this so it doesn't 'need' to call this but can still get x/y values in a proper fashion that would be quicker.


Missed that in the first post.. If I can get that fixed I think it should be ok.
0
ikeworkCommented:
Can you show the declaration of game->ship? Is it an array?
0
pgnatyukCommented:
So go back to the original code:
 ShipClass *ship= &game->ship[i];

You can declare this ship variable before the loop. And use const:
 const ShipClass *ship;

It makes sense to re-write this loop. For example so
const ShipClass* begin = &game->ship[0];
const ShipClass* end = begin + Nobj;
ShipClass *ship = &game->ship[0];
while (ship != end)
{
  // the code
   ship++;
}

But all these changes .... you will get 2-3% faster code and that's all. You can write it in assembler, but you will get really nice results, if you will re-arrange your data and algorithm on a higher level.

0
VallerianiAuthor Commented:
Yeah ship is a large array of things.

This is part of it:

  DesignedClass::initialize();

  typeOfObject = ship;
  design = 0;
  sensorThreshold = sensor_threshold;
  dockObj = 0;
  distressFrame = 0;
  portNum = 0;
  videoMode = 0;
  lastVideoMode = 0;
  stealthLevel = 0;
  accuracy = 0;
  tubeSelector = 0;
  blowuptimer = -1;
  PlanetTargeting = -1;
  defensiveTubeSelector = 0;
  pending = 0;
  blockadeFrames = 0;
  short i;
  for (i=0; i<max_tubes_per_ship; i++) {
    tubeOffset[i] = 0;
    beamOffset[i] = 0;
  }

DesignedClass::init loads some more vars for it, some including the position x/y etc, but its pretty much like that.
0
ikeworkCommented:
Can you show the header of the class of the object "game"? If its member "ship" is a normal array, then there is performance issue.
0
VallerianiAuthor Commented:
Hovered over 'ship' gives me Array<ShipClass, short> GameStateClass::ship.

I'm pretty sure the gamestateclass is rather large. I haven't looked much at it yet (didn't start as my own coding).

What could be done to solve that? What other options are there? (And any that won't involve a difficult change hopefully!)
0
ikeworkCommented:
>> Array<ShipClass, short>

Looks like a template that implements a simple c-array of ShipClass's with index type short. I doubt there is much to improve.
Usually these kind of templates are straight forward, just a wrapper to the array, most likely the compiler will optimize it anyway, so there is just a usual c-array access, not much to do there.

If you want real performance improvements changing the algorithm is unavoidable.
Thats where the biggest potential for a performance boost is.
Minimizing the potentially colliding objects, and only make collision tests with them.

Sorry for the bad news.

As a helper for your decision. you could count the number of collision tests each frame. Then measure the time needed for 1 collision test.
Multiply both and you have the time needed currently for all collision test.
This might give you an idea, how much improvement might be there, if you just have 1-5% of the number of collision tests.
0
VallerianiAuthor Commented:
No worries, you both have been a HUGE help to me.

With all the changes, I was able to reduce the cycles per call from 18000 to 1300. A huge difference without major coding changes.


There is one more question I must ask about this whole thing however, (sorry!). A way I am thinking of doing this without ripping the coding apart, is something similar to quadtree spitting in a 'sense'. I was going to turn the map into X and Y sectors of about 1000 pixels each. So then I could call to see if a ship is IN or around the sectors and only check those sectors.

WHat i mean is.. Lets say I have a ship in X=2 Y=2... I would check one square around it in every direction, including the square its in... So minimum range would be 1000 pixels, and maximum 2000 pixels, for example.. Would this be a good idea/ >I would think it would help for very large maps.
0
pgnatyukCommented:
Sounds good.
0
VallerianiAuthor Commented:
Awesome help both!
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.