where to place collision detection, and why?

Newbie & Debugging Questions
#1

First, I’m not talking about specific algorithms, there’s plenty of discussion on collision algorithms.

The question that I’m curious about is what are the strategy you guys use for collision detection and why?

What I mean; I’ve been trying a strategy of having a collision handler that sorts through all the game objects that can collide versus each other. In the game loop I update all the game objects, then I send the objects to the collision handler to check collisions.

I don’t have any particular reason why I went that route, I just kinda figured that would be the easiest way to keep things ecapsulated.

An alternative strategy I could think of would be to have a collision test as part of each object, so, each game entity would check for collisions as part of its update.

How about you guys, what insights do you have in how you setup collision detection?

#2

For 2D collision detection I use rectangles.


public boolean collision(int x1, int y1, int w1, int h1, int x2, int y2, int w2, int h2) {
    Rectangle rect1 = new Rectangle(x1, y1, w1, h1);
    Rectangle rect2 = new Rectangle(x2, y2, w2, h2);
    return rect1.intersects(rect2);
}

This is the (as far as I know) the fastest way for collision detection.

You could make a class called ‘Collision.java’ and place it in there (maybe some more there).

  • winspeednl
#3

That wasn’t quite what I was getting at, I was meaning, more do you have each game object looking at what other objects it collides with, do you have a collision handler that looks to each object and sees which ones collide or are about to collide, or a different strategy?

and why do you choose to do things this way?

#4

My games don’t usually have very much collision detection in them, but this is how I usually do it for the bullets in my game.

Each bullet is added to the Game object which updates them and renders them, and every update of the game loop the Game iterates through the bullets and checks for a collision between each bullet and all of the enemies. If there is a collision, the Game triggers the bullet’s onCollideWith(Enemy) method :slight_smile:

#5

TheMeatMans method with collision callbacks is very good for smaller games with less different collisions happening.

A more scaleable approach is to have a separate physics-world where not the game objects themselves are added but their corresponding physics-representation, which are accessible by an ID or something.
This allows you to separate physics and other stuff.

Once your physics world world is built, you can solve collisions and let the owners of the physics representation ask:
-did i collide?
-with what did i collide?

You could also implement callbacks like TheMeatMan.

The physics world is then updated in every game-loop iteration.
This separation allows for great optimizations like updating only what changed, optimized memory layout and spatial partitioning.

#6

I agree with VaTTeRGeR, it depends how much entities do you have and scope of your project: fan made or professional ?

From my point of view, if is just a “simple” project, don’t waste time on complex algorithms if you don’t have too much entities or complex behavior.

My strategy is the following:

  1. start from a World class with list of all game entities
  2. add to each collidable entity a simple flag
  3. on each entity update method, if movement is required (for example on player command, or in player-controlled agent command ), simulate movement: there is a collision with other entity ? To determinate it, just cycle on all collidable entities in my world

As example, check here and here

#7

Not sure I understand the question, but in Vangard I handle thousands of moving objects per frame, with tens of thousands of collidable objects.

  1. Things only check for collision if they want to move, and they check for collision at their new target location before they move.

  2. The world is divided into 10k sectors and moving objects only check for collision with objects in their sector and adjacent sectors.

  3. The sectors are divvied up in such a way that I can process them in parallel.

I don’t see why you would have a collision handler or what it would help with. In fact having a collision handler seems to create another object registration issue, and requires another iteration through all entities. I have the objects that can move capable of making their own collision checks if and when they want to move.

#8

In my game, I have class GameObject which have a bunch of specialised subclasses, for example Missile. The constructor of this class takes a list of GameObjects which is the entities the missile can interact with. During the game loop, the missile will check for collision between the given game objects and it self.

#9

First, thanks for your responses.

The reason I asked was that, while i have the collision algorithms working,
I felt my approach was going to become overly complex as I move along beyond just checking that the player collides with the environment.

This approach was what I was thinking of going for, where each entity has a “body” (the position, speed, and shape of the game entities), and then just cycle through all the objects by cycling and checking where they were going to move and if there was a collision.

I like this approach… I hope you don’t mind if I adapt your approach.

The way I was doing that with the collision object was that it was initialized with all the bodies of all entities, would weed out anything too far away, and then perform the collision detection, and when a collision happened would call the response() from the bodies that were collided.

That said, I do see your point and your argument why it’s better to have each moving object check for collisions.

Thanks again all, gives some food for thought.

#10

Granted my game doesn’t have a ton of collisions, but I put them in the update method of the object. And only check if the two are both in bounds of the screen.

#11

Thanks for all the pointers, especially @Gornova

I finally got a strong system that will make it easy to add functionality to instead of the limiting approaches I had done before.

SO, I now have “perfect” collision detection, even with absurd speeds…

The approach, I changed to creating a “world” that will hold, and update all the objects.

Each entity now has flags that keep track of what they are and what they will collide with, this allows for a lot of early outs, where each object that is too far is dismissed.

I now have each entity check for collisions before movement, and works by advancing each entity to its next position, checking for collision and then sending each object to a collision response.

Then, for terrain, it verifies a good MTV, and if it manages to go fast enough that the MTV is bad, it draws a point from each point in the polygon, determines which ones are in the polygon and reduces the speed so that it will stop at the intersection point.

Then, because each entity will be able to know what it collides with there can be custum responses to the specific collisions…

Its seriously been about 2 months to get this working the way I was hoping (half the time was spent determining that what I was doing prior was inneffective).

So happy right now…

#12

cool you are happy! Well done!