Munti Threading & collision detection

Munti Threading & collision detection

Ariesnl

Member #2,902

November 2002

Until now I never used multithreading in my games but I came up with an idea..

Make a collision detection thread that puts collision structs in a list/queue
and the main thread would grab the collisions and handle them..
(Producer - Consumer)

Is this a way to go or would it only cause problems ?

Perhaps one day we will find that the human factor is more complicated than space and time (Jean luc Picard)
Current project: [Star Trek Project ] Join if you want ;-)

Audric

Member #907

January 2001

Not getting the result immediately is acceptable if it doesn't matter that the objects temporarily overlapped before you took an action : ex. bullets in shoot them ups.
It's problematic for physics where you need solid objects to really stay out of each other.

The challenge IMO is that your collision thread will have to examine a large piece of data (all collisionable objects) which can change at any moment without warning.
You can't safely traverse a linked list when elements can get add / removed / reordered before you're done with it.

Edgar Reynaldo

Major Reynaldo

May 2007

My preferred approach would be to store all possible collision pair intercept times in a std::list. Then you sort the list and you only need to deal with collisions that happen within a certain time frame. You also don't need to update the entries for a collision pair set if the objects don't change velocity. If you have a lot of non-accelerating objects this works fine, but as soon as you add in acceleration you have to update the collision table on every frame for every object with non-zero acceleration. So this might not work well for gravity based games. However, you can still find intercept times with the quadratic equation, so maybe it would work.

If you want to add threading in, then you need to divide your work somehow, otherwise there's no point in adding threading. And I have the feeling that you would still need to wait for the collision calculation threads in your main thread, so I don't know if the performance increase would be worth the headache.

What is your game? What do you want the physics to be like?

Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide
King Piccolo will make it so Then I could just flip it with some sweet, sweet matrix math. In either case, I’ll ride this wagon until the wheels fall off. Thanks to those that keep it running

Chris Katko

Member #1,881

January 2002

I think I would just:

- Run all pairs as if they're completely independent.
- Store any collision events in say, a list. But don't "process" any of them.

One all actual collision checks are done, have a single thread "resolve" them. That way you have a many reader, one writer, setup. And only if that last thread becomes a serious bottleneck, would I then branch into resolving hazards. (A -> B -> C)

I haven't done this stuff in awhile, so maybe I'm missing something. But if your collision detection (or other event handling) depends on the order of processing, you're going to have serious issues with desyncing if you network it, because if two threads COULD run in different orders (even with the delay from a memory access on different architectures), well, it's going to eventually happen.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin