Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
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  
  Entity Management with ArrayLists  (Read 1712 times)
0 Members and 1 Guest are viewing this topic.
Offline lucasfraser

Innocent Bystander





« Posted 2012-10-01 14:31:34 »

Hi,

I have a question about entity management, at the moment a game I am working on uses an entity management system using an ArrayList with instances of every entity. Every game loop update (the thread sleeps for 50ns or ms (cant remember what it is)) it goes through the ArrayList and for each entity it moves the entity if it is a moving entity and if it is within the players view, it renders it... So, as i have a big map (4000000 x 4000000 tiles) and will end up having maybe close to a million separate entities it will need to be quick... With my current system, having say 100 trees or so works fine... but when i spawn 10000 instances of an object (say a tree) the game almost stops and updates at roughly 1 frame every 2-3 seconds...

As I'm sure there is a way to do this, I would like your suggestions...

Thank you,
Lucas Fraser  Grin
Offline DrHalfway
« Reply #1 - Posted 2012-10-01 15:53:40 »

Millions of GameObjects or entities, I don't think any engine will be able to iterate through it all fast enough. What you want is some kind of spacial partitioning of scenes or better yet, create a hierarchy of GameObjects to be able to manage the scene in a fast and efficient manner.

Consider our solar system, its planets and moons as a hierarchy. The main node would be the solar system, sun would be its child and the planets would be children of the sun and moons as children of planets and so on so fourth. A quick check would be done against the solar system node for viability, if its not visible, and child nodes would be automatically ruled out as invisible.

As far as managing millions of GameObjects, your best bet would be some kind of custom container that allows O(1) insert time and O(1) remove time. Consider removing entities from the scene among millions of Objects, ArrayList is an O(n) operation (correct me if i'm wrong).

Offline Vladiedoo
« Reply #2 - Posted 2012-10-01 16:46:51 »

Would it be possible for you to combine certain objects? Instead of drawing each tree individually you could possibly draw groups of five trees having you'd then only need to draw 2000 objects instead of 10,000 objects. This isn't a very advanced way of fixing the problem but maybe something to consider.

How are you making your game, Java2D, Slick2D, LWJGL, something else?
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ctomni231

JGO Wizard


Medals: 98
Projects: 1
Exp: 7 years


Not a glitch. Just have a lil' pixelexia...


« Reply #3 - Posted 2012-10-01 21:31:34 »

4000000 x 4000000 = 16000000000000 entity loop iterations.

"Divide and conquer!"

Yeah, if you are iterating through that much entities, no processor of today's age is going to do it fast. You can produce all the entities, but you should only update the entities in the player's viewpoint. If this is a type of evolution game, then you are going to have to group each entity by type, and use the type to update all the entities around the board when they reach the player's viewpoint.

Another option would be to split the huge map into smaller chunks. Then, when the player crosses from one section to another you can load the new section of the map, then you can use the previous methods I talked about to update the entities. Doing a straight iteration is definitely going to be really slow.

Good luck.

Offline Ultroman

JGO Knight


Medals: 24
Projects: 1


Snappin' at snizzes since '83


« Reply #4 - Posted 2012-10-01 23:27:51 »

Maybe use the same animation of each tile-type? So they all draw from the same Sprite-sheet.

Also, you shouldn't update or run/draw animations of objects that aren't within the screen-view. You can have them move, maybe, or use a simpler AI when they're not on screen. That's the best approach I've found.

- Jonas
Online Roquen
« Reply #5 - Posted 2012-10-02 08:08:23 »

Simplest solution: Something along the lines of a uniform grid of uniformed grids, where the smaller is perhaps screen size.  Non thinking entities are stored with the lower level uniform grid in which they live.  Thinking (but not doing anything ATM) are stored separate but likewise in the grid they are in.  Priority Queue like structure for thinking entities which are far away from camera, but ACTIVELY doing something.  PQ so they only think at some low rate determine by their "slow AI".  Or simpler (but less flexible) is to round-robin far away thinkers...still requires a slow AI.  When moving, wake out nearby (whatever is approp for the game style) nearby thinker and sleep (or slow AI) ones moving outside of that range.

@DrHalfway - very large scale with large voids = break into local frames IHMO.
Offline Best Username Ever

Junior Member





« Reply #6 - Posted 2012-10-06 04:30:11 »

4000000 x 4000000 is 16 trillion. If each of your tiles was only one bit then you would still need 1.8 terabytes of RAM to hold only tile data. Certainly you're not going to be able to process the entire map at once if you don't even have space to store it. What types of things are your trees doing in your game that require individual attention? (Still, 10,000 seems relatively low for times that long.)

You need to give more information. But you definitely should split the game world into chunks. It would be better to disregard far away objects to give yourself more time/memory for handling nearby objects the player might interact with.
Offline Jimmt
« League of Dukes »

JGO Kernel


Medals: 128
Projects: 4
Exp: 3 years



« Reply #7 - Posted 2012-10-06 05:33:17 »

What everyone else is saying. Split the big array into different, smaller arrays and it'll be a lot easier.
Offline theagentd
« Reply #8 - Posted 2012-10-06 16:48:58 »

What everyone else is saying. Split the big array into different, smaller arrays and it'll be a lot easier.
... and only update the relevant ones. Splitting up 1.8 terabytes of data into smaller parts won't make it smaller. >_>

Myomyomyo.
Offline Cero
« Reply #9 - Posted 2012-10-06 18:01:17 »

if its really that big, and it seems unnecessarily big, in games we do all kind of tricks to scale things down, but if it really is really big, you just have to stream everything and not calculate / iterate things which are far away

just like GTA 3, or actually even GTA 2

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 748
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #10 - Posted 2012-10-06 18:04:29 »

Didn't it occur to anybody the OP has no idea what he's talking about, and just throws some numbers around? (Besides not having returned to JGO after his initial post, so why bother?)

Further, he says he wants about a million entities, so there would not be 16 trillion loop iterations, unless you'd want to render each tile, and check it for an entity - which is the wrong approach.

If you want a massive world, with a million entities, you can simply get away with something similar to Map<Coord, Entity>, and not ticking all entities every frame (with the suggested priority queue, or a similar concept).


Anyway, it's all very doable, both in required memory and in required CPU time.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline theagentd
« Reply #11 - Posted 2012-10-07 00:36:21 »

Still, if the objects need to pathfinding or collision detection against the terrain, you'd need all relevant parts of the world loaded. Yes, it's still solvable since you'd definitely not need most of the world in memory, but if there's nothing there why have it in the first place?

Myomyomyo.
Offline Best Username Ever

Junior Member





« Reply #12 - Posted 2012-10-07 00:48:23 »

Didn't it occur to anybody the OP has no idea what he's talking about, and just throws some numbers around? (Besides not having returned to JGO after his initial post, so why bother?)

Further, he says he wants about a million entities, so there would not be 16 trillion loop iterations, unless you'd want to render each tile, and check it for an entity - which is the wrong approach.

If you want a massive world, with a million entities, you can simply get away with something similar to Map<Coord, Entity>, and not ticking all entities every frame (with the suggested priority queue, or a similar concept).


Anyway, it's all very doable, both in required memory and in required CPU time.

Ya, it's pretty obvious, but since it's not a "How do I make a fps minecraft mmo game?" question I would give him the benefit of the doubt. Given the apparent lack of knowledge, I would not spend time giving specifics. Better to pose some questions so that it will help the original poster or someone else with the same problem that may stumble upon this topic. Obviously one could create a big map with lots of sparse entities, but giving specifics would probably fall on deaf ears.
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.

CogWheelz (15 views)
2014-07-30 21:08:39

Riven (22 views)
2014-07-29 18:09:19

Riven (14 views)
2014-07-29 18:08:52

Dwinin (12 views)
2014-07-29 10:59:34

E.R. Fleming (32 views)
2014-07-29 03:07:13

E.R. Fleming (12 views)
2014-07-29 03:06:25

pw (42 views)
2014-07-24 01:59:36

Riven (42 views)
2014-07-23 21:16:32

Riven (30 views)
2014-07-23 21:07:15

Riven (31 views)
2014-07-23 20:56:16
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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!