Entity Management with ArrayLists

Newbie & Debugging Questions
#1

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 ;D

#2

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).

#3

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?

#4

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.

#5

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.

#6

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.

#7

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.

#8

What everyone else is saying. Split the big array into different, smaller arrays and it’ll be a lot easier.

#9

… and only update the relevant ones. Splitting up 1.8 terabytes of data into smaller parts won’t make it smaller. >_>

#10

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

#11

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.

#12

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?

#13

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.