Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (121)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Collision detection in a separate object?  (Read 3140 times)
0 Members and 1 Guest are viewing this topic.
Offline DavidW
« Posted 2011-10-14 20:05:19 »

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 Smiley  Cheers.

Hello!
Offline ra4king

JGO Kernel


Medals: 352
Projects: 3
Exp: 5 years


I'm the King!


« Reply #1 - Posted 2011-10-14 21:48:30 »

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.

Offline DavidW
« Reply #2 - Posted 2011-10-14 23:41:04 »

For the CollisionDetector class I was thinking it would do something like
1  
2  
3  
4  
5  
6  
7  
8  
 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

1  
2  
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);

Hello!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline sproingie

JGO Kernel


Medals: 202



« Reply #3 - Posted 2011-10-14 23:52:41 »

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 Shocked

Oh and c'mon use for-each syntax already :p
1  
2  
3  
4  
5  
6  
7  
8  
9  
// 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(); }
           }
     }
}

Offline counterp

Senior Duke


Medals: 11



« Reply #4 - Posted 2011-10-15 00:24:06 »

for-each is slower
Offline DavidW
« Reply #5 - Posted 2011-10-15 00:44:26 »

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 Shocked

Oh and c'mon use for-each syntax already :p
1  
2  
3  
4  
5  
6  
7  
8  
9  
// 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(); }
           }
     }
}



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. Smiley  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.

Hello!
Offline sproingie

JGO Kernel


Medals: 202



« Reply #6 - Posted 2011-10-15 03:44:54 »

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.

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.

Offline ra4king

JGO Kernel


Medals: 352
Projects: 3
Exp: 5 years


I'm the King!


« Reply #7 - Posted 2011-10-15 06:18:36 »

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:
1  
2  
3  
4  
5  
6  
7  
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)

Offline theagentd
« Reply #8 - Posted 2011-10-15 06:57:10 »

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:
1  
2  
3  
4  
5  
6  
7  
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)
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

Myomyomyo.
Offline ra4king

JGO Kernel


Medals: 352
Projects: 3
Exp: 5 years


I'm the King!


« Reply #9 - Posted 2011-10-15 07:33:18 »

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

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ReBirth
« Reply #10 - Posted 2011-10-15 11:17:54 »

Ok fine add e2.kill(e1) after that...
I have used this method fopr so long and wont change it, because it's good  Cheesy

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.

Offline DavidW
« Reply #11 - Posted 2011-10-15 18:49:02 »

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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
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.

Hello!
Offline theagentd
« Reply #12 - Posted 2011-10-15 21:04:32 »

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...

Myomyomyo.
Offline ra4king

JGO Kernel


Medals: 352
Projects: 3
Exp: 5 years


I'm the King!


« Reply #13 - Posted 2011-10-15 22:41:30 »

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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
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.
That's exactly how I do it in my games Cheesy

Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #14 - Posted 2011-10-16 05:09:01 »

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.

See my work:
OTC Software
Offline ReBirth
« Reply #15 - Posted 2011-10-20 14:20:48 »


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.

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

Offline Damocles
« Reply #16 - Posted 2011-11-16 17:24:42 »

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.

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

theagentd (19 views)
2014-10-25 15:46:29

Longarmx (52 views)
2014-10-17 03:59:02

Norakomi (46 views)
2014-10-16 15:22:06

Norakomi (34 views)
2014-10-16 15:20:20

lcass (39 views)
2014-10-15 16:18:58

TehJavaDev (68 views)
2014-10-14 00:39:48

TehJavaDev (68 views)
2014-10-14 00:35:47

TehJavaDev (60 views)
2014-10-14 00:32:37

BurntPizza (74 views)
2014-10-11 23:24:42

BurntPizza (45 views)
2014-10-11 23:10:45
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!