Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (562)
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  
  How long should a very good collision algorithm take? *My NEW algorithm*  (Read 1701 times)
0 Members and 1 Guest are viewing this topic.
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Posted 2005-11-03 07:38:32 »

I've just developed a new algorithm to do collision detection. I've tested it and it works as it should.


With 100 sprites to do collision detection on it takes just over 0.0003 seconds.
With 1000 sprites to do collision detection on it takes just over 0.03 seconds (while the Big-O(n^2) takes well over 20 seconds).
With 10000 (ten thousand yes) it takes 4.6 seconds, while the Big-O(n^2) one takes about, well, I gave up waiting :]


Are there any better ones out there?

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

JGO Kernel


Medals: 164
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #1 - Posted 2005-11-03 09:28:26 »

Normally just spatially partioning them is enough to cut down the actual number of comparisons going on. In 2D, sort into grid cells and only compare those sprites in the same cell - vary the cell size dependent on the size of the community being collided and their likely proximity to each other.

In your tests - how many collisions are being detected? In the 10000 test.. whats the speed if every sprite is colliding with every other sprite?

Kev

Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #2 - Posted 2005-11-03 09:39:38 »

Click to Play

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #3 - Posted 2005-11-03 09:48:43 »

The thing is, if you have 3 sprites, and they all intersect each other, then only 2 of the sprites will actually collide since they destroy each other and the other one is left alive. This is logical since, let's say a bullet hits 2 units, then it destroys the first unit it hits and not the 2nd unit.


Below: 4999 collisions detected, since when 2 sprites collide that's ONE collision. When 4999*2 = 9998, which means there are 2 sprites left that don't collide :] good luck finding those.

Click to Play

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

JGO Kernel


Medals: 164
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #4 - Posted 2005-11-03 10:46:32 »

Quote
The thing is, if you have 3 sprites, and they all intersect each other, then only 2 of the sprites will actually collide since they destroy each other and the other one is left alive. This is logical since, let's say a bullet hits 2 units, then it destroys the first unit it hits and not the 2nd unit.

Thats pretty specific to a game genre - and a particular game - my unit might have health, at that point both bullets count, or I might be making things bounce off each other, in which case I'm interested in all the collisions at a given time.

Not to say it doesn't look pretty! Smiley

Kev

Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #5 - Posted 2005-11-03 10:53:12 »

Quote
The thing is, if you have 3 sprites, and they all intersect each other, then only 2 of the sprites will actually collide since they destroy each other and the other one is left alive. This is logical since, let's say a bullet hits 2 units, then it destroys the first unit it hits and not the 2nd unit.

Thats pretty specific to a game genre - and a particular game - my unit might have health, at that point both bullets count, or I might be making things bounce off each other, in which case I'm interested in all the collisions at a given time.

Not to say it doesn't look pretty! Smiley

Kev

It's just a matter of how you implement the algorithm. In my demo I simply kill 2 colliding rectangles, I might decide not to kill both, but only one and withdraw energy from one. (like destroy the bullet and subtract health from unit)


Download the JAR file containing the *algorithm* and some demos, and tell me your opinion: (ignore the uglyness of the code Smiley

http://www.private.is/arni/colldet.jar


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

JGO Kernel


Medals: 164
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #6 - Posted 2005-11-03 11:29:11 »

Had a quick look, nothing wrong with the "code ugliness"  - readable and clean Smiley

Your algorithm seems to be your using the collision rectangles x and y coordinates added together as a heuristic to group which sprites need to be checked against each other. Could be just my very quick read failing me - but won't this mean you'd compare for instance a sprite at (50,1) to a sprite at (1,50)?

Presumably this would have problems with different size objects also in that your heuristic only considers their position and not their size.

As I said, I've only got a few minutes between work.. Smiley

Kev

Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #7 - Posted 2005-11-03 11:43:25 »

This is true.

Sprites at (50,1) and (1,50)  (group 51) would need to be checked for collision. But the tests I've done don't indicate that that's much of an overhead.
If those sprites are, let's say 10x10 pixels in dimension, then groups 41 through 61 need to be checked for collision.

If you add another sprite that is 20x20 in dimension, then you would need to expand the range of what groups to perform collision detection on, from 41-61 to 31-71. It's better if the sprites are of some similar dimension, 10x10, 20x20 even 100x100 is fine, but as soon as you have a single sprite that is 1000x1000 then the point of the algorithm fades out. So, units, bullets etc. something that is a lot of and relatively similar dimension is very good.


You could look at this as some sort of groupping, but still with a very limited code to implement and also VERY fast, at least the fastest I've seen as of yet.

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

JGO Kernel


Medals: 164
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #8 - Posted 2005-11-03 11:57:33 »

Your first step is to sort, you *might* find its actually faster to just sort into buckets based on imposing a grid on the play area. At that point you could just compare the sprites in the same grid cell - this would be just as tunable, would prevent 50,1 - 1,50 checks and is probably faster than sorting the whole list based on compareTo, would be a consistent O(n) rather than potentially much worse using standard sorting.

But then really, like most of these things, it ends up being application specific.

Kev

Offline appel

JGO Wizard


Medals: 51
Projects: 4


I always win!


« Reply #9 - Posted 2005-11-03 12:04:26 »

True.

And thanks for discussing this with me. I see now how I can change this to become O(n)

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline kevglass

JGO Kernel


Medals: 164
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #10 - Posted 2005-11-03 12:44:27 »

Quote
And thanks for discussing this with me. I see now how I can change this to become O(n)

No worries, I've enjoyed thinking about it Smiley Been a while since I engaged the brain Smiley

Kev

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.

radar3301 (9 views)
2014-09-21 23:33:17

BurntPizza (28 views)
2014-09-21 02:42:18

BurntPizza (18 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (27 views)
2014-09-20 20:14:06

BurntPizza (29 views)
2014-09-19 03:14:18

Dwinin (46 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (102 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56
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

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!