Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (524)
Games in Android Showcase (127)
games submitted by our members
Games in WIP (592)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 [2]
  ignore  |  Print  
  Quadtree-like structure for dynamic / moving Game Objects  (Read 6176 times)
0 Members and 1 Guest are viewing this topic.
Offline matheus23

JGO Kernel


Medals: 113
Projects: 3


You think about my Avatar right now!


« Reply #30 - Posted 2012-11-23 14:42:41 »

Yes, you have a grid, but not a grid-like datastructure. Remember that a HashMap is 'just' an array of linkedlists. And everybody knows linkedlists are a bad fit for, well, everything.

But since almost every Vec2i gives me different Hashcodes, I won't have hash collisions, which means I don't need to fill those linkedlists more than one or two objects.

After some little time the HashMap has built up it's size, and then it's not even necessary to delete or put in entries, so I guess it's not too bad.

And I diagree that LinkedLists are bad for everything Wink It's true that they're bad for storing entities (they're really bad there), but they're not bad for everything.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline krasse
« Reply #31 - Posted 2012-11-23 14:51:36 »


It's a grid... actually...
but how exactly would I go about making the grid aware of fast objects to avid tunneling?

Small and fast objects like bullets that travel far every tick can be assumed to travel along a line that is used for the collision testing. So basically you just create the line from the previous tick to the current and check against your grid/accelerator. For large and fast objects you probably need to do something more fancy like sweep areas... brrrr

Offline Roquen
« Reply #32 - Posted 2012-11-23 15:33:16 »

And everybody knows linkedlists are a bad fit for, well, everything.
I...err..nevermind.

Roquen wanders off humming about traffic jams
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #33 - Posted 2012-11-23 15:33:51 »

But since almost every Vec2i gives me different Hashcodes, I won't have hash collisions
That is not how hash maps work. Different hashcodes will cause hash collisions, unless your backing array has 4.2 billion entries.


And I diagree that LinkedLists are bad for everything
They are bad for everything. But let's not go there, as other threads have done so before.


Why don't you just use a List[w][h] ? It's so much better in every possible way. But it seems you have made up your mind, too bad, as the disadvantages have been explained already in this thread, and you just said 'no'. Oh well, in the end, it's about what works, not how it's done. So good luck with your game - if there's one in the making.



And as for tunneling / swept shapes: it's normally good enough to make your entities queries so fast, that you can simply iterate the movement of the shape within a single game tick. In games you don't need perfect solutions, so just moving a bullet with 100 positional updates (and querying for collisions) per tick will simply be enough. Another approach is to query series of overlapping bounding rectangles / circles along the movement vector and do a broad scan of potential colliders.

Nobody in their right minds will simulate more than 1 high speed colliding object, so don't even bother solving that problem. Complexity increases so rapidly that you can just as well write a scientific simulator, and ditch any plans for your game.

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

JGO Knight


Medals: 29
Exp: 18 years


Computers can do that?


« Reply #34 - Posted 2012-11-25 14:36:14 »

The grid vers Quad tree performance depends on some details. If "things" are similar sizes and you have fairly well bounded space so that you don't need too many grid cells, grids are pretty fast. Since these 2 things are typically true in games then the generalization that grids are faster easier than quad trees is not a bad approximation.

However with very large spaces, with very uneven distribution of "things" and/or things have quite a  wide range of sizes. Then quad trees are faster and have smaller memory footprints.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 833
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #35 - Posted 2012-11-25 16:01:27 »

Quadtrees are also faster for frustum culling.

Just don't insert/update/remove items through the quadtree.
Just query them, and for large, odd shapes only.

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

toopeicgaming1999 (55 views)
2014-11-26 15:22:04

toopeicgaming1999 (48 views)
2014-11-26 15:20:36

toopeicgaming1999 (8 views)
2014-11-26 15:20:08

SHC (24 views)
2014-11-25 12:00:59

SHC (24 views)
2014-11-25 11:53:45

Norakomi (26 views)
2014-11-25 11:26:43

Gibbo3771 (23 views)
2014-11-24 19:59:16

trollwarrior1 (36 views)
2014-11-22 12:13:56

xFryIx (75 views)
2014-11-13 12:34:49

digdugdiggy (52 views)
2014-11-12 21:11:50
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

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
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!