Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (476)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (533)
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  
  Better collision detection method  (Read 1971 times)
0 Members and 1 Guest are viewing this topic.
Offline roland
« Posted 2009-10-16 10:16:45 »

Hi I am making a game with towers which fall down and land on top of eachother, and the only way to think of checking if one collided with another was:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
for int i = 0; i < towers.size; i++)
{
    for int j = 0; j < towers.size; j++)
   {
       if (i == j) continue;
       if (tower[i] collides with tower[j])
       {
             DoSomeThing;
       }
   }
}


the collision works fine but I start to see the lag after only about 20-30 towers. I would like to have at least 150 towers being able to be  on the screen at once without any significant slowdown as I have lots of other stuff in my game thats going to drain the cpu. Is there a much better way to do it? eg so that the tower doesnt check all the towers in the vector/array and only checks towers below it or something. Thanks
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 743
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2009-10-16 10:38:09 »

This saves you *half* of the checks, but more importantly, is better:


for int i = 0; i < towers.size; i++)
{
    for int j = 0; j < towers.size; j++)
   {
       if (i >= j) continue; // !!



To really reduce the amount of checks, use some spatial algortihm like a quadtree for 2D and a octtree for 3D


Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #2 - Posted 2009-10-16 10:42:12 »

or even:
1  
2  
3  
4  
5  
for (int i = 0; i < numTowers; i ++) {
   for (int j = i + 1; j < numTowers; j ++) {
      // check here
  }
}


Cas Smiley

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 743
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #3 - Posted 2009-10-16 11:07:20 »

Doh  persecutioncomplex Lips Sealed

I wrote it like that, because I sometimes have non-equal (subsets) 'inner/outer loop'-collections, where I do:


for(Object a: ...)
   for(Object b: ...)
      if(a.hashCode() > b.hashCode())
         // collide


Which is almost like comparing the pointer in C, as long as the hashCode is the identity hashcode

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #4 - Posted 2009-10-16 11:27:41 »

Which is almost like comparing the pointer in C, as long as the hashCode is the identity hashcode

System.identityHashCode( Object o ), for when your objects have overridden hashCode().
Offline princec

JGO Kernel


Medals: 342
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #5 - Posted 2009-10-16 12:10:15 »

I always wondered how System.identityHashCode worked... I can see that it could easily be intrinsified to just use the actual pointer to the object on the heap, except that all the modern garbage collection stuff since Hotspot has involved moving objects around, so that number would change. Or maybe it uses a pointer to the VM's internal structure that points to the object? (Does such a structure even exist?)

Cas Smiley

Offline appel

JGO Wizard


Medals: 50
Projects: 4


I always win!


« Reply #6 - Posted 2009-10-16 12:49:39 »

Hi I am making a game with towers which fall down and land on top of eachother, and the only way to think of checking if one collided with another was:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
for int i = 0; i < towers.size; i++)
{
    for int j = 0; j < towers.size; j++)
   {
       if (i == j) continue;
       if (tower[i] collides with tower[j])
       {
             DoSomeThing;
       }
   }
}


the collision works fine but I start to see the lag after only about 20-30 towers. I would like to have at least 150 towers being able to be  on the screen at once without any significant slowdown as I have lots of other stuff in my game thats going to drain the cpu. Is there a much better way to do it? eg so that the tower doesnt check all the towers in the vector/array and only checks towers below it or something. Thanks


Yes.

Split up your screen into a grid, for example a grid consisting of 32x32 tiles.

Each tile in the grid can contain references to multiple towers.

So if you're dropping a tower on tile 12x14 (and maybe adjacent tiles) then you simply look up this tile in the grid and check if the tower collides with any other towers there.

This requires some modification to the datastructure of your game.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline JL235

JGO Coder


Medals: 10



« Reply #7 - Posted 2009-10-16 13:43:17 »

I use a grid bast collision detection routine and it will be much faster. I have a 2D array of Sets of game objects (or of Towers in your case). It should be a set because a tower should only be stored in an array location once. You need to calculate the towers minimum and maximum x and y locations. Typically the minimum is their bottom left corner, and the maximum is the Towers top right corner.

You then divide the x values of these corners by the width of the array, and the y value by the height of the array. Then you iterate from the new minimum x and y through to the maximum x and y, adding the tower into the Set in each location in the array.

This is untested psudo code for adding a tower...
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
final int TOWER_GRID_WIDTH  = 20;
final int TOWER_GRID_HEIGHT = 20;
Set<Tower>[][] towerGrid = new Set<Tower>[TOWER_GRID_WIDTH][TOWER_GRID_HEIGHT];
    /* grid setup code here */

Tower tower = // get tower
int minX = Math.floor( (tower.getX()-tower.getWidth()/2) / TOWER_GRID_WIDTH );
int minY = Math.floor( (tower.getY()-tower.getHeight()/2) / TOWER_GRID_HEIGHT );
int maxX = Math.ceil( (tower.getX()+tower.getWidth()/2) / TOWER_GRID_WIDTH );
int maxY = Math.ceil( (tower.getY()+tower.getHeight()/2) / TOWER_GRID_HEIGHT );

for (int x = minX; i <= maxX; x++) {
    for (int y = minY; i <= maxY; y++) {
        towerGrid[x][y].put( tower );
    }
}


When a Tower's size or location changes (i.e. moved or resized) then you need to remove it from all of it's locations and then re-add it. There are then a range of optimizations you can run to make this more efficient (like checking if a Tower has moved from one grid space to another before removing/re-adding, and only updating when you check for collisions).

When you want to perform a collision check you just work out what array elements the Tower is in (like above) and then iterate over all the towers in each of those sets. Those are the towers to check against.

You should also try different grid sizes as they will yield different amounts of performance.

Offline roland
« Reply #8 - Posted 2009-10-16 13:56:19 »

WOW! thankyou everyone for all your comments!
I think I will look into doing a grid type thing as that seems the fastest.
thanks  Grin
Offline JL235

JGO Coder


Medals: 10



« Reply #9 - Posted 2009-10-16 14:31:36 »

WOW! thankyou everyone for all your comments!
I think I will look into doing a grid type thing as that seems the fastest.
thanks  Grin
Actually no, it isn't. I've seen various benchmarks on collision detection routines and 2D grids are never at the top. For example oct-trees are faster. There is also a Wikipedia page on spatial partitioning that you can look at. But it is significantly faster then your original brute-force approach.

A 2D grid is also relatively easy and straight forward to implement.

A few more remarks; unless you build in some sort of system to deal with this then you can't have Towers outside of the grid (i.e. offscreen). I also highly advise building an interface for your collision detection routine so you can easily implement a new algorithm. Also make sure you benchmark your algorithm (and it's optimizations) with real data. Otherwise you don't know if the optimizations help, or not. Also how will you deal with inheritance? Even if you choose not to you need to decide about what to do with this (i.e. everything is stored as a Tower).

A big issue for my own grid collision system was the high number of nodes and iterators used by the sets. I found when I had a thousand objects all constantly moving and intersecting against each other, it would be creating millions of objects per-second just to detect collisions. This caused the garbage collector to run ALOT and so I've since optimized it to remove this.

Finally there is a bug in my code above, dividing by the grid width and height is incorrect. It should be dividing by the width and height of each cell in the array in pixels, not the number of elements in the array. You can see my full grid collision code here. It's not perfect, but for now it's good enough.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Roquen
« Reply #10 - Posted 2009-10-16 17:44:35 »

@Cas:  A common method is to (maybe mix) the raw address and set a tag bit when an identity hash has been called on an object.  When moved by GC, the object is again marked and the hash value is stored in an extra memory slot.
Offline roland
« Reply #11 - Posted 2009-10-17 06:56:57 »

thanks for the info, JL235.

Quote
unless you build in some sort of system to deal with this then you can't have Towers outside of the grid (i.e. offscreen).
I'm not worried about this really - I already thought about it. If the towers are above the grid then they are not going to collide with anything, just fall. And if they are left or right or below the grid they are off the map so I will delete them.

I will not iterate through anything except the towers. Check which grid piece it is in by it's position and move it down one if there is no tower in the grid below. Otherwise if there is perform a collision detection between the two towers.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 743
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #12 - Posted 2009-10-17 15:42:15 »

Actually no, it isn't. I've seen various benchmarks on collision detection routines and 2D grids are never at the top. For example oct-trees are faster.

Seriously, it depends. If you're simulating liquids, then the particles are more or less evenly spread, and the grid approach will be running circles around any tree implementation.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
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.

pw (22 views)
2014-07-24 01:59:36

Riven (20 views)
2014-07-23 21:16:32

Riven (17 views)
2014-07-23 21:07:15

Riven (20 views)
2014-07-23 20:56:16

ctomni231 (48 views)
2014-07-18 06:55:21

Zero Volt (44 views)
2014-07-17 23:47:54

danieldean (35 views)
2014-07-17 23:41:23

MustardPeter (38 views)
2014-07-16 23:30:00

Cero (53 views)
2014-07-16 00:42:17

Riven (52 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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!