Collision detection in a separate object?

Game Play & Game Design
#1

Hey everyone. I’d just like a little advice on how I should do collision detection in my game. I have made a few small games in the past (simple pong game, short text adventure) but never anything really big. I decided to try my hand at making a tower defense game.

Right now I have an abstract class “Entity” which is extended by anything that needs to draw itself, so far just an enemy, a canon, and a bullet. I put all my entities in an ArrayList and loop through them to draw everything. I keep a reference to this arraylist in each entity, and when the game loop calls the updateMe() method of an entity, collision detection is done in there. So when a bullet is updated for instance, you check to see if you intersect any enemy, and if you go you kill it.

My question is if this is the best object oriented way to do this. It works fine for a small number of things, but if I decide to add more and more types of entities then things could get a little weird. Enemies for instance totally ignore all other entities and just move along their path, so there’s no reason really for them to have a reference to that array list. The only reason they do is because I built it into the super class. Only putting the array list reference in the subclasses that need it seemed redundant (maybe I am wrong about this?) I thought about writing a “CollisionDetector” class which would handle all this stuff, but again I don’t know if that is good programming practice, or if such a thing would be difficult to deal with in the future. I’d appreciate any advice :slight_smile: Cheers.

#2

That is quite good OOP design. However I don’t think it is necessary for them to have a reference to the actual ArrayList, but maybe a GameWorld class that holds the instance of all entities. A CollisionDetection class would just have a couple static methods to check between different shapes, like rect vs. rect and circle vs. circle. Rect vs.

#3

For the CollisionDetector class I was thinking it would do something like

 for(int i = 0; i < entities.size(); i++) {
    for(int j = 0; j < entities.size(); j++) {
        if(entities.get(i) instanceof Enemy && entities.get(j) instanceof Bullet) {
           if(collision(entities.get(i), entities.get(j)))
               entities.get(i).kill(); }
           }
     }
}

or whatever. Either that or having methods in some Game class (like you suggested) like

ArrayList<Enemy> getAllEnemies();
ArrayList<Tower> getAllTowers();

I am a little worried about performance while I have all these ArrayLists. It isn’t a big deal now, but I don’t want it to cause problems later (either in this game or another);

#4

Yeah, you want to avoid quadratic performance if you can help it. When you do queries for entities in a space, you’re best off querying the space for the list of entities that are within that space. This lets you use a BSP tree or a quadtree or whatever when things start getting crowded so you don’t end up querying the whole world against the whole world.

Ultimately you’re better off keeping a separate list of Enemies and Bullets. Using isinstance at all is a bad code smell. Doing it twice every time through an O(n^2) algorithm is, well, really a no-no :o

Oh and c’mon use for-each syntax already :stuck_out_tongue:


// Still not a good algorithm, but a lot nicer to read, no?
for(Entity e1: entities) {
    for(Entity e2: entities) {
        if(e1 instanceof Enemy && e2 instanceof Bullet) {
           if(collision(e1, e2))
               e1.kill(); }
           }
     }
}
#5

for-each is slower

#6

I am sorry to say that I don’t know enough about tree data structures. I got a minor in computer science at one point, but have been working on my MS in math for the last few years and so haven’t done a ton of programming (except for matlab).

Again thanks for the help. :slight_smile: Are O(n^2) algorithms really that terrible? I assumed that any time you had one type of thing looking for another (for instance, towers only wanting to shoot at enemies that are within some radius) you would end up having to use something of at least O(n^2). But I am no expert in this.

#7

Obviously O(2^n) and O(n!) are way worse, but quadratic is still bad if can can be avoided. You might not do any fancy space partitioning to start, or even ever, but you can at least start with maintaining separate sets of Bullets and Enemies. Then you simply iterate through one set and see if it intersects with any items in the other. As a bonus, you’re not doing any isinstance checks because you know the types ahead of time.

#8

Also be careful to include “if(e1 != e2)” or else e1 will always kill itself :wink:

The best way is to use this O(n^2 - O(n-1)) loop:


for(int a = 0; a < entities.size(); a++) {
    for(int b = a+1; b < entities.size(); b++) {
        if(collision(e1.getBounds(),e2.getBounds())) {
            e1.kill(e2);
        }
    }
}

O(n^2 - O(n-1)) is faster O(n^2)

#9

But doing that would force you to check which one of e1 and e2 would be killed. You’d need to do “two-way” collision! xD
EDIT: How did I manage to do that?! XD

#10

Ok fine add e2.kill(e1) after that…

#11

I have used this method fopr so long and wont change it, because it’s good :smiley:

Also I keep each entities ordered. For example bullet is “higher” than enemy. When bullet hits enemy, bullet will handle everything such us removing itself, calc damage etc. The enemy entity just sit in there.

#12

Thanks for all the input. Here is what I decided to do. I keep a list of enemies stored inside a GameWorld class. Each entity has a reference to the GameWorld it belongs to.


class Bullet extends Entity {
     GameWorld world;
...
     public void updateMe() {
          for(Enemy en : world.getEnemies()) {
               if(collidesWith(en))
                      en.kill();
          } 
     }
}

This seemed a little better because I don’t really care about all collisions, just those between bullets and enemies (at this point). As a plus, the GameWorld class helps keep things a little more organized.

#13

That looks fine. Unless you have a LOT of enemies and bullets, it’s overkill to do more fancy stuff like grids and quad trees.
I have a related question: Sprongie mentioned a quad tree as a possible solution. I know how a quad tree works, but I don’t know how I would effectively apply it to dynamic data. There’s also the problem of the units actually being surfaces and not points. It seems really hard to even get it to work, not to mention getting it to perform well. I’ve never used a BSD tree though…

#14

That’s exactly how I do it in my games :smiley:

#15

Meh, just do a brute force (what you already have) until it turns out to be too slow. I actually made a professional game where I used a quadtree to try to speed things up (when I didn’t need to) and it ended up making things slower because of the overhead of constructing and updating the quadtree. I had already done a lot of optimization around only having currently moving objects collide in this way and only 3 or 4 objects would move at once, so the brute force was quite fast enough.

Obviously your situation could be different, but my main point is don’t optimize until it’s a problem, or you may end up wasting a lot of time.

#16

if it ain’t broke don’t fix it~

#17

Smart is to use timers around various procedures

long timer=System.nanoTime(); //TEST CODE
myFunctionSaveThePrincess();
logger(“TimePrincess:”+(System.nanoTime()-timer)); //TEST CODE

-> this can instantly show you if any optimization or change is actually making it faster.

I just recently made something “more optimized” until I realized, it used 40% more time.
I would not have recognized this without a metric.