Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (715)
Games in Android Showcase (214)
games submitted by our members
Games in WIP (788)
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  
  Quadtree Efficiency?  (Read 1094 times)
0 Members and 1 Guest are viewing this topic.
Offline cygnus

Junior Newbie





« Posted 2017-02-22 04:13:22 »

Hello!
I was reading a post on optimization of collision detection and I read that a quadtree isn't a good choice after 1000 or so objects. Sadly, I have already spent a while implementing one and my game, by the end, should have many, many entities being moved around simultaneously. If you have played the game Factorio, it is much like this - for those who don't know, a large source of lag in Factorio is thousands of items moving along conveyor belts. Is the impact of a Quadtree likely to make this performance even worse, and, if so, what should I use?
Offline Riven
Administrator

« JGO Overlord »


Medals: 1265
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #1 - Posted 2017-02-22 07:18:07 »

Use grids. They have a lot less cache-trashing, and the logic is trivial. You will have quite a lot of empty cells, but that's OK.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline kappa
« League of Dukes »

JGO Kernel


Medals: 116
Projects: 15


★★★★★


« Reply #2 - Posted 2017-02-22 10:29:59 »

Someone posted this article a while back.

Its a very good read for your problem, especially if you are trying to decide whether to use quad trees for collision detection.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline SHC
« Reply #3 - Posted 2017-02-22 13:19:47 »

Grids are extremely fast and trivial, but you need to spend some time tweaking them when you have objects with negative positions. Since you'll typically implement them as 2D arrays, negative indices will be a problem.

I really really prefer using boundary volume hierarchies, like aabb trees or circle trees. You can read up more here:

https://goharsha.com/blog/aabb-trees-for-collision-detection/

Offline Riven
Administrator

« JGO Overlord »


Medals: 1265
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2017-02-22 13:58:38 »

Grids are extremely fast and trivial, but you need to spend some time tweaking them when you have objects with negative positions. Since you'll typically implement them as 2D arrays, negative indices will be a problem.

You just add a value to the coords to ensure they are positive... you'll never need negative cell index logic.

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

« JGO Spiffy Duke »


Medals: 899
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #5 - Posted 2017-02-22 14:12:24 »

A good pragmatic solution Smiley

Cell grids are currently perfect for my use case which is thousands of approximately similarly sized entities moving slowish around a grid upon which they can only "just" intersect each other on briefly. That's really the important thing... choosing the right data structure for your specific use case. One-size-fits-all never works best.

Cas Smiley

Offline SHC
« Reply #6 - Posted 2017-02-22 14:58:02 »

Cell grids are good, I agree, but @Riven, I don't know which type of game the OP is making, so I recommended one that works for all sorts of games. Even with adding a number to make the indices positive, it won't work well when we have open world games. However, AABB trees are easy to understand, and yet the same time, give good performance.

Offline Riven
Administrator

« JGO Overlord »


Medals: 1265
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2017-02-23 10:56:27 »

Developers asking these questions shouldn't be making games that require anything more than grids Pointing

It may sound patronizing, but it's true Smiley




(I'll show myself out Kiss)

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

Junior Newbie





« Reply #8 - Posted 2017-02-26 01:12:54 »

Thanks for all the info, and it's true, I'm pretty new XD however, I'm sure I'll be able to figure out to some extent AABB trees/grids. Smiley
Pages: [1]
  ignore  |  Print  
 
 

 
CopyableCougar4 (214 views)
2017-03-24 15:39:42

theagentd (196 views)
2017-03-24 15:32:08

Rule (255 views)
2017-03-19 12:43:22

Rule (237 views)
2017-03-19 12:42:17

Rule (242 views)
2017-03-19 12:36:21

theagentd (261 views)
2017-03-16 05:07:07

theagentd (257 views)
2017-03-15 22:37:06

theagentd (186 views)
2017-03-15 22:32:18

theagentd (180 views)
2017-03-15 22:31:11

ral0r2 (166 views)
2017-03-03 11:52:41
List of Learning Resources
by elect
2017-03-13 14:05:44

List of Learning Resources
by elect
2017-03-13 14:04:45

SF/X Libraries
by philfrei
2017-03-02 08:45:19

SF/X Libraries
by philfrei
2017-03-02 08:44:05

SF/X Libraries
by SkyAphid
2017-03-02 06:38:56

SF/X Libraries
by SkyAphid
2017-03-02 06:38:32

SF/X Libraries
by SkyAphid
2017-03-02 06:38:05

SF/X Libraries
by SkyAphid
2017-03-02 06:37:51
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!