Setting up for collision detection and then dealing with a collision in a 2D game

1
votes

I searched for collision detection topics, but they were all about the detection itself. My question is more about before and after the detection process. I'm writing my first big game and I want to make it as efficient as reasonably possible.

The premise of the game is that you fly a ship around a playing field. In this field are going to be obstacles of varying nature provided by the environment, enemy ships, and projectiles flying and floating around in space. The objects will be able to rotate around their centers and such, if they are required to or want to.

My idea for setting up the test is to have objects load themselves in some manner into a queue and a list. The game would then take whatever is on the front of the queue and test against everything in the list. It would first check to make sure the thing in the list is not itself (which would generate a collision for everything all the time lol). Next, the game would check if there is a collision between the object in the queue and the object in the list. If there is a collision, then it will flag the objects saying they have collided and save a reference or whatever of what the object collided with.

For example, if A collided with B, the game would tell A to run a collision function, B to run collision function, and would store into A a reference to B and B would store a reference to A.

The game will then continue to check collisions for the object in the queue until it runs through the list, doing the above each time to account for an object hitting or getting hit by multiple objects.

For example, if there were three balls, A, B, and C, and A were to be hit by both B and C in the same frame, A would have its velocity modified by B and then by C, and B and C would have their velocities modified by A.

Would this be a smart way to go about doing this? I'm not worried about the actual detection of collisions right now, there are plenty of articles or tutorials available plus my own thinking to solve that problem. I haven't run across anything that talks the before and after. I'm not sure how many things in a queue and list would begin to cause a large load and slow the game down. Right now my objects are all just x,y positions, x,y velocities, what direction they are facing, and a few other things.

Now I think I'm beginning to ramble about unrelated things. Any insight or wisdom would be appreciated.

1
c++collision-detection
Are the movement vectors updates as you traverse the queue? It seems like B and C would have their movement vectors modified by A after A has had it's movement vector changed. – Edvard Pedersen
It would save the old values and the new values, run through the detection process, and then all objects would update themselves if need be. So in the example, A would interact with B and A would save it's new velocities. Then, it would interact with C, which would modify and save the even newer velocities. Then once the game exits the detection, it would run an process to update the objects which would have them use their new velocities or do whatever. – Azaral
Yes, but wouldn't C then use A's newer velocities when you're calculating the new velocities for C? Assuming the most simple collision response I can think of, with A having starting velocity (0,1) and C has (0, -1), B has (0, -1) as well, A collides with B and C in the same frame, first it's modified by B, giving A velocity (0,-1), then it collides with C, but as they have the same velocity vector, neither changes (or they both increase speed in the same direction). Or did you mean that the new velocities are stored in a new list, and the lists are swapped after all calculations are done? – Edvard Pedersen
Yes, the new velocities would be stored separate and then swapped once all collision functions are done. – Azaral

1 Answers

2
votes

As for many game-development topics, there is no generic answer to this and it depends on your type of game, but keep some things in mind when it comes to traversal of your objects:

  • Try to think about how you will do the actual reaction after a collision detection (will you use double dispatch, visitor, downcasting/rtti, storing traits that can be used in a function map, ...). There are multiple techniques and all have their advantages and disadvantages. The method you pick can reflect in how you do the actual traversal.
  • Try to split up your scenes in types of objects. For example, if you have many static objects that will never move, it would be ridiculous to test those all against each other, you should separate these. But as a rule of thumb, do not try to specialize this too much, having something like static vs dynamic will probably give big benefits, having 100 types will produce a maintenance-hell with usually no real gain.
  • This can be related to your occlusion mechanism. For example, if it is portal-based, it is unlikely that objects from different cells ever will collide.

There are probably some other tips I'm forgetting right now, as this is a complex topic, but I hope it gets you going.