Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Dark GDK / Bullet Collision needs optimizing

Author
Message
Plystire
21
Years of Service
User Offline
Joined: 18th Feb 2003
Location: Staring into the digital ether
Posted: 31st Dec 2008 07:29
In my game, there are bullets going everywhere. Sometimes there are around 5 bullets to each ship.

Now, my current bullet collision code is as follows:
- Update bullet position on screen
- Use bullet's last position and current position to produce a line segment
- Loop through all existing ships of opposing affiliation (in relation to the bullet's affiliation) and calculate their distance to the bullet's line segment


Now, when I have hundreds of enemies running around and each bullet (up to 5x the ship count) has to run through all of those enemies to see if it collided with them, this causes a huge slowdown.


Does anyone know of a better way to do this? Am I calculating more than I need to or am I stuck with what I have and need to optimize other areas to squeeze some speed out of the engine?


The one and only,


prasoc
15
Years of Service
User Offline
Joined: 8th Oct 2008
Location:
Posted: 31st Dec 2008 12:26
Is it 3d or 2d?
Plystire
21
Years of Service
User Offline
Joined: 18th Feb 2003
Location: Staring into the digital ether
Posted: 31st Dec 2008 20:07
The game is 2-dimensional. Sorry, I should've mentioned that.


The one and only,


jason p sage
17
Years of Service
User Offline
Joined: 10th Jun 2007
Location: Ellington, CT USA
Posted: 31st Dec 2008 20:39
So the bullets are sprites then? If so - then I would use the sprite collision, and I thought you can just check if a sprite has hit another sprite, and when it has it returns what sprite it hit.

Now optimization - perhaps you don't use pixel perfect approach if you have tons of bullets going. Perhaps 5 bullets instead gets displayed as one sprite versus 5 to give illusion, and making the actual sprite collision have less work to do.

--Jason

Plystire
21
Years of Service
User Offline
Joined: 18th Feb 2003
Location: Staring into the digital ether
Posted: 31st Dec 2008 21:16
Well, I can't use sprite collision, because:

Say the bullet is going so fast that on the next loop, it completely jumps over a ship. That bullet never "collided" with the ship, per se, but in reality it went through it, so technically collision should have occured.

The same goes for a ship that's moving very fast.



The way I'm doing it is pure math. The sprite is just there for looks, nothing more. The bullet produces a line segment (ax,ay) - (bx,by) and the ship being checked provides a point (cx,cy)

Now, with this information, I made a "distance to line segment" function to check how far away the ship's center is from the bullet. If the distance is <= the ship's size/2 + bullet's width/2, then the bullet must have hit the ship.

Here's the "distance to line segment" function I wrote:



So, what I'm hoping for is some sort of technique, maybe, for checking tons of information like this.



The one and only,


Sebast
15
Years of Service
User Offline
Joined: 31st Dec 2008
Location:
Posted: 1st Jan 2009 01:26
Wow, you're serious about collision detection... but all those floating point operations are going to kill your execution time.

I recommend prechecking. Run disttolineseg only if the enemy ship's position is within the rectangle defined by the two ends of the line segment. Subtract a constant that's the max of (bullet width/2 + ship width/2) from the lowest (x,y) point, and add the same constant to the highest (x,y) point to ensure you don't throw out cases where the bullet overlaps at the ends.
dark coder
21
Years of Service
User Offline
Joined: 6th Oct 2002
Location: Japan
Posted: 1st Jan 2009 04:12
The easy option is to just use Sparky's Collision lib, you can easily modify this to work in a 2D environment and is rather efficient for large scenes.

The hard option(but faster), is to rewrite what Sparky's Collision lib does, but in 2D. This will be a lot more efficient than his 3D implementation due to cutting out a whole axis, but it also means a lot of work. If you watch the recordings from the convention Sparky(Paul Johnston) explains in quite great detail how the lib works for raycasting, you could similarly implement this for 2D.

jason p sage
17
Years of Service
User Offline
Joined: 10th Jun 2007
Location: Ellington, CT USA
Posted: 1st Jan 2009 07:48
Also - Your distance calculation could be changed to use the vector length function - and you might find that processes much faster than a ton of SQRT. I never seen one implemented for 2D - but - it should be fine.

In the DBPRo Ironinfantry code, I create a "Vector" at start up - then my distance function just reused it over and over.

--Jason

sydbod
16
Years of Service
User Offline
Joined: 14th Jun 2008
Location: Just look at the picture
Posted: 1st Jan 2009 13:57 Edited at: 1st Jan 2009 13:58
Quote: "I recommend prechecking. Run disttolineseg only if the enemy ship's position is within the rectangle defined by the two ends of the line segment. Subtract a constant that's the max of (bullet width/2 + ship width/2) from the lowest (x,y) point, and add the same constant to the highest (x,y) point to ensure you don't throw out cases where the bullet overlaps at the ends. "


Brilliant early stage culling technique.
Will look into this in 3D mode for my small project. Thanks for sharing.
It even looks to be simple enough to do the computations in straight machine code directly.

Login to post a reply

Server time is: 2024-09-30 13:13:51
Your offset time is: 2024-09-30 13:13:51