PDA

View Full Version : Collisions and performance



Vincent22
05-23-2012, 12:42 AM
Hi, I need some suggests about collisions and performance.

I'm developing a simple 3D demo of a "tron arcade" game. I'm implementing collisions using something similar to bounding box but exluding y coordinate (because cycle moves along x and z coordinates).

I have one bounding box array that include coordinates of arena's boundaries and coordinates of obstacles inside the arena and a list that include trail coordinates.
Collisions algorithm works fine but sometimes (a 10%) it doesn't catch collisions with trail, I think the problem is something related to performance:
trail list is made up of about 100 elements and maybe iterate it each frame can cause some problem.
Trail is made up several contiguos objects because it curves (when cycle curves) and I have to remove first elements (FIFO -like) when it reach a specific length.

Do you have some seggestions about performance improvement? I have to modify trail generation or I can improve collisions algorithm?

Thank you

thokra
05-23-2012, 12:56 AM
As you're in 2D a quad tree will suit you just fine. How many dynamic objects are in the scene? Do static objects outweigh the dynamic ones?


[..]but sometimes (a 10%)[..]

I wouldn't call 10% of all cases to be something that happens sometimes. If you have a 10% fault rate when detecting collisions you might want to check if the algorithm is actually working properly.

Stuart McDonald
05-23-2012, 03:25 AM
Do you have to/want to do the collisions that way? Depending on memory/size of world/collision resolution you could just store a large 2D 1bit array of which locations have a trail and which don't. Not clever, but fast. If you want to be clever you could probably do it on the GPU in a texture.

Vincent22
05-23-2012, 06:25 AM
How many dynamic objects are in the scene? Do static objects outweigh the dynamic ones?

Dynamic objects are two: player cycle and IA cycle, but at the moment I've implemented only the player cycle.
Trail is static but it's generated procedurally while cycle is moving. You suggest quad tree?
Ok 10% fault maybe is too much, but I'd like to improve collisions performance to avoid collision catch loss.


Do you have to/want to do the collisions that way? Depending on memory/size of world/collision resolution you could just store a large 2D 1bit array of which locations have a trail and which don't. Not clever, but fast. If you want to be clever you could probably do it on the GPU in a texture.

Sorry, but I don't understand your suggestion. Can you explain your methods with more details?
thank you

Vincent22
05-23-2012, 07:01 AM
As you're in 2D a quad tree will suit you just fine

I've read something about quad tree.
I think I could implement a simplified version of quadtree (because I have only two dynamic objects and simple arenas with small dimension). I could divide space in four quadrants and test cycle collision only with objects in the quadrants that cycle overlaps

The only problem is: if I split trail elements in four lists (one for each quadrants) how can I delete trail elements in a FIFO way when trail reaches max length?

thokra
05-23-2012, 07:22 AM
Ok 10% fault maybe is too much, but I'd like to improve collisions performance to avoid collision catch loss.

How can improving performance simultaneously increase precision? In general that's actually a trade-off. The precision of you algorithm has effects on performance but isn't depending on performance in any way.


I could divide space in four quadrants and test cycle collision only with objects in the quadrants that cycle overlaps

That's sort of the idea of the quad tree - to reduce the number of tests by early rejection of a number of objects unlikely to collide.


because I have only two dynamic objects and simple arenas with small dimension

If so, a quad tree would probably be too powerful actually. How many objects at max are we talking here?

thokra
05-23-2012, 07:33 AM
if I split trail elements in four lists (one for each quadrants) how can I delete trail elements in a FIFO way when trail reaches max length?

Could you please define what a trail is? I think the disc is that thing you shoot. Is the trail left by disc when it is shot?

Dan Bartlett
05-23-2012, 07:48 AM
If you are checking at each frame if the bounding box of your player is colliding with a trail and the player is moving fast relative to thin trails, it won't work at low frame-rate since it might have passed through the object + be on the other side already. You'll need to do something more like a raycast or sphere/bounding bound sweep test.

A nice book on collision detection is Real Time Collision Detection by Christer Ericson:
http://realtimecollisiondetection.net/
http://www.amazon.com/exec/obidos/tg/detail/-/1558607323?tag=realtimecolli-20

Vincent22
05-23-2012, 08:03 AM
The precision of you algorithm haseffects on performance but isn't depending on performance in any way.

You're right, I check collisions using precise cycle position and objects "bounding box" but sometimes it fails and I don't know why. I thought it's because collision algorithm have to iterate a vector of 100 elements, but maybe I'm wrong



If so, a quad tree would probably be too powerful actually. How many objects at max are we talking here?

Static objects: Few objects into the arena (2/4), arena boundaries (4) and trail compose by about 100 objects
Dynamic: two cycle

Vincent22
05-23-2012, 08:06 AM
If you are checking at each frame if the bounding box of your player is colliding with a trail and the player is moving fast relative to thin trails, it won't work at low frame-rate since it might have passed through the object + be on the other side already. You'll need to do something more like a raycast or sphere/bounding bound sweep test.

A nice book on collision detection is Real Time Collision Detection by Christer Ericson:
http://realtimecollisiondetection.net/
http://www.amazon.com/exec/obidos/tg/detail/-/1558607323?tag=realtimecolli-20

Yes it's my case: fast cycle relative to thin trail! Should I use raycast?

thokra, trail is like a "wall" left behind the cycle while it's moving. I don't have disc in my demo.

Vincent22
05-23-2012, 11:04 AM
Solved!
I've implemented ray casting (using bresenham algorithm to "draw" my ray) to check collisions and now it works

Thank you all for your answers!

Stuart McDonald
05-24-2012, 04:21 AM
Sorry, but I don't understand your suggestion. Can you explain your methods with more details?
thank youThe simple brute force way to do collision detection in a light cycle game is to have a large 2D grid of your world which you set the X,Y points of where there are walls/trails/anything you can hit. If you only need to know "Collision or not" then you can use 1 bit.

It might be the size of your world means the grid is too big (10k by 10k using 1bit is over a gig), but maybe you don't need a 1-to-1 resolution i.e. if the grid 5k by 5k, would the player notice? If the minimum speed is 2 then definitely not.

Hopefully that makes more sense.