Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (739)
Games in Android Showcase (224)
games submitted by our members
Games in WIP (820)
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 1972 times)
0 Members and 1 Guest are viewing this topic.
Offline cygnus

Junior Devvie


Medals: 7
Exp: 1 year



« 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: 1313
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: 119
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: 1313
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!
Offline princec

« JGO Spiffy Duke »


Medals: 953
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: 1313
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 Devvie


Medals: 7
Exp: 1 year



« 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  
 
 
You cannot reply to this message, because it is very, very old.

 
Ecumene (61 views)
2017-09-30 02:57:34

theagentd (82 views)
2017-09-26 18:23:31

cybrmynd (189 views)
2017-08-02 12:28:51

cybrmynd (189 views)
2017-08-02 12:19:43

cybrmynd (194 views)
2017-08-02 12:18:09

Sralse (206 views)
2017-07-25 17:13:48

Archive (770 views)
2017-04-27 17:45:51

buddyBro (904 views)
2017-04-05 03:38:00

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

theagentd (1331 views)
2017-03-24 15:32:08
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!