Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (808)
Games in Android Showcase (239)
games submitted by our members
Games in WIP (872)
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  
  Most optimal collision detection algorithms  (Read 11604 times)
0 Members and 1 Guest are viewing this topic.
Offline VoidBuffer

Junior Devvie


Medals: 4
Exp: 2 years



« Posted 2016-12-13 00:58:25 »

Hi all,

I'm fairly new so I hope this isn't a repost, however i came across this extremely useful article while I was trying out some different collision detection methods: https://0fps.net/2015/01/23/collision-detection-part-3-benchmarks/

It's an author that benchmarks different types of collision detection against each other. I hope it helps someone out in the future, because I was very close to implementing a quadtree until I came across this info Smiley
Offline Roquen

JGO Kernel


Medals: 518



« Reply #1 - Posted 2016-12-13 08:52:50 »

Optimal collision detection (as noted in link) is going to be a function of the distribution of objects and how it evolves over time combined with chosen method and how it's actually implemented.  So a quad-tree can be the best choice...but it actually very quite hard to implement a good quad-tree (or forest of them more likely).  And in the case where it would be "best" something much simpler to correctly implement is likely to be approaching the same performance.
Offline VoidBuffer

Junior Devvie


Medals: 4
Exp: 2 years



« Reply #2 - Posted 2016-12-13 17:29:03 »

I don't see a case where the quadtree can be good, especially with the difficulty of it's implementation versus much more simple and efficient algorithms. Going through the uniform figures for quadtree, it seems that anything past 1000 entities quickly starts to show the flaws of quadtree overhead and efficiency. For non-uniform data we can still see clear winners that far surpass quadtree efficiency.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline bmanmcfly
« Reply #3 - Posted 2016-12-13 18:15:42 »

That's why I liked the SAT algorithm for collision detection...

- There are lots of early outs if its clear that there's no contact potential
- Can reserve collision detection for moving objects
Offline Roquen

JGO Kernel


Medals: 518



« Reply #4 - Posted 2016-12-13 20:58:14 »

@VoidBuffer - It all depends on how you can move less data (and not cache-thrash) and keep the local neighborhood 'n' small.

@bmanmcfly - different topic..this is broad-phase.  SAT's only claim to fame is it's easy to implement (that's not a bad thing). 
Offline princec

« JGO Spiffy Duke »


Medals: 1147
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #5 - Posted 2016-12-13 23:28:34 »

@VoidBuffer - It all depends on how you can move less data (and not cache-thrash) and keep the local neighborhood 'n' small.
And here is Java's Achilles heel... many structures designed to work with known memory contiguity of C fall over in Javaland, leading to nightmarishly complex implementations in Java using bodges like struct libraries etc. etc.

Cas Smiley

Offline Roquen

JGO Kernel


Medals: 518



« Reply #6 - Posted 2016-12-14 01:14:06 »

Yeap...
Offline princec

« JGO Spiffy Duke »


Medals: 1147
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #7 - Posted 2016-12-14 01:53:54 »

/muses how forthcoming value types implementation in Java might solve this...

Cas Smiley

Offline VoidBuffer

Junior Devvie


Medals: 4
Exp: 2 years



« Reply #8 - Posted 2016-12-14 05:45:57 »

Obviously it depends wildly on what you're designing, but do you all have a general go to collision optimization strategy? Looking into the topic a little more, it seems that a static grid-like algorithm should be enough without too much overhead. Store static non-moving entities and only update the moving entities capable of dynamic collision.
Offline Roquen

JGO Kernel


Medals: 518



« Reply #9 - Posted 2016-12-14 06:29:24 »

Yeah, it depends too much on data.  For wide-open areas then a uniform grid is a nice easy choice and will perform reasonably.  Couple that with sweep-and-prune for the broad pass.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

« JGO Spiffy Duke »


Medals: 1147
Projects: 3
Exp: 20 years


Eh? Who? What? ... Me?


« Reply #10 - Posted 2016-12-14 10:02:53 »

Grids and pooled lists for me. Most my my entities are roughly uniform in size, and the median number of entities in a grid cell is 1 when there are any entities at all. With a grid I'm computing collisions between about 5-6000 entities in next to no time at all.

Cas Smiley

Offline theagentd
« Reply #11 - Posted 2016-12-14 16:50:34 »

Can confirm, uniform grids are awesome for collision detection!

Myomyomyo.
Offline bmanmcfly
« Reply #12 - Posted 2016-12-14 17:27:18 »


@bmanmcfly - different topic..this is broad-phase.  SAT's only claim to fame is it's easy to implement (that's not a bad thing). 

My bad... easy to implement???  god damn, it took me about 3 weeks trying to write my own before I figured out how to use libgdx intersector class....

For broad phase, I just made large collision boxes and if a box is both within the screen box and is in collision with another collision box then check with SAT.  Probably not ideal by any stretch, but THAT was easy to wrap my head around and easy to implement.

Does that sound like sweep and prune?
Offline delt0r

JGO Wizard


Medals: 145
Exp: 18 years


Computers can do that?


« Reply #13 - Posted 2016-12-14 23:35:34 »

+1 for Grid.
However i implemented it as a array with linear probing when i have 2 things in the same place. It works super fast even for area quires.

For more advanced cases and scales i have used Vantage Point Trees. These however tend to come into there own with much more than 3 dimensions. ie k nearest quires for things like case based reasoning. 

In the past i have tried kd trees, quad tree etc. I end up with similar performance access the the board.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Archive
« Reply #14 - Posted 2016-12-15 00:26:21 »

BSP isnt bad if you want to have some sick FPS maps Smiley. The BSP tree is very good for other things as well like rendering, lightmapping, and pathfinding

Offline codematic

Junior Newbie





« Reply #15 - Posted 2016-12-21 06:08:35 »

What are some efficient ways of storing entities within grids for broad-phase collision? I'm working on implementing grids for broad phase collision detection and I'm dealing with a large variety of entities that will have different reactions depending on what they collide with.

My current structure is a GridMap which holds Grids. The grids hold their own dimensions as well as Arrays of all the different types of entities that they could 'potentially' hold. This seems pretty inefficient though which is why I'm asking.

Option 1 - Have Grids store many Arrays of different sub-classed entities. Check collisions between these entities if they're in the same grid. This may obviously lead to lots of empty and unused Arrays which seems wasteful.

Option 2 - Have one generic Entity array in each grid, and iterator over it in a n^2 fashion checking for collision against different types of entities.

Option 3 - *insert here* Pointing
Offline delt0r

JGO Wizard


Medals: 145
Exp: 18 years


Computers can do that?


« Reply #16 - Posted 2016-12-21 06:29:00 »

Empty cells in an array are  cheap in terms of space. So i wouldn't worry about it. However depending on size i suspect both will mostly work most of the time.

There is always some extreme case that can break it. But will this case even be possible in your game?

I have no special talents. I am only passionately curious.--Albert Einstein
Offline codematic

Junior Newbie





« Reply #17 - Posted 2016-12-21 06:52:01 »

I guess we'll find out! I'm looking to support 'hopefully' ~1000 players on my network however the AI bodies will be in magnitudes. I realize I won't have to worry about the AI that players can't see, but I'm just trying to get it semi-right the first time around.

Right now I'm clearing my old GridMap, then creating a new GridMap every frame. After running a profiler, everything seems fine and dandy. Just being wary Smiley
Pages: [1]
  ignore  |  Print  
 
 

 
mercenarius (4 views)
2020-06-04 19:26:01

mercenarius (2 views)
2020-06-04 19:13:43

Riven (850 views)
2019-09-04 15:33:17

hadezbladez (5834 views)
2018-11-16 13:46:03

hadezbladez (2635 views)
2018-11-16 13:41:33

hadezbladez (6251 views)
2018-11-16 13:35:35

hadezbladez (1504 views)
2018-11-16 13:32:03

EgonOlsen (4739 views)
2018-06-10 19:43:48

EgonOlsen (5797 views)
2018-06-10 19:43:44

EgonOlsen (3282 views)
2018-06-10 19:43:20
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04: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!