Jump to content

  • Log In with Google      Sign In   
  • Create Account


Entity storage, ArrayList or HashMap?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
6 replies to this topic

#1 P0jahn   Members   -  Reputation: 260

Like
0Likes
Like

Posted 31 May 2013 - 01:00 PM

Currently, all my game objects are stored in an ArrayList. Each frame, the game loop iterate over this ArrayList and do its work to move/update the entities.

 

I have been thinking lately... an ArrayList may be affecting performance negatively. The get(Object) and remove(Object) are not constant-time operations. In my game, these two functions are often called. HashMap solves that problem, but gives me a new problem, the order of the elements is beyond your control. 

 

ArrayList:

+ Fast to iterate over it

+ Control over the position(index = render priority)

- Slow remove(object) and get(object) functions

 

HashMap:

+ Constant-time remove(object) and get(object) operations

+ Allows no dublicates

- Slow to iterate through. You have to call values()(every frame, or cache it) which returns a Collection object that you can iterate through

- Unknown order. No way to control render priority.

 

What should I do?


Edited by P0jahn, 01 June 2013 - 05:46 PM.


Sponsor:

#2 Waterlimon   Crossbones+   -  Reputation: 2456

Like
0Likes
Like

Posted 31 May 2013 - 01:27 PM

I believe a linked list is what you want, for fast insertion and deletion of elements. Note that accessing by index is slow (needs to iterate from start) but this wont affect normal iteration over the whole list (even though that might be slower than a plain array)

o3o


#3 swiftcoder   Senior Moderators   -  Reputation: 9845

Like
0Likes
Like

Posted 01 June 2013 - 09:02 AM

I have been thinking lately... an ArrayList may be affecting performance negatively...
 
What should I do?

Profile your application, and find out for sure that it is a performance problem.

If you don't have hard data to back up your intuition here, it's meaningless to talk optimisation.

Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#4 TheChubu   Crossbones+   -  Reputation: 4062

Like
0Likes
Like

Posted 01 June 2013 - 02:01 PM

What should I do?

What you think its best!


"I AM ZE EMPRAH OPENGL 3.3 THE CORE, I DEMAND FROM THEE ZE SHADERZ AND MATRIXEZ"

 

My journals: dustArtemis ECS framework and Making a Terrain Generator


#5 Sudi   Members   -  Reputation: 705

Like
0Likes
Like

Posted 01 June 2013 - 06:49 PM

Well have you thought about using both?

Using the array for the iteration tasks the the hasmap for random access? besides do you really need to completely remove the entry? What is your entity?



#6 frob   Moderators   -  Reputation: 20119

Like
4Likes
Like

Posted 01 June 2013 - 11:03 PM

From your lists of pros and cons, it seems like you are using the collection of game objects for things it ought not be used for.

Many games have a list of all the objects in the world. A hash map is great for this.


HashMap:
+ Constant-time remove(object) and get(object) operations
+ Allows no dublicates
- Slow to iterate through. You have to call values()(every frame, or cache it) which returns a Collection object that you can iterate through
- Unknown order. No way to control render priority.

Why are you iterating over every object in your game? Unless your game world is quite small you will only ever want to iterate over a tiny subset of the world.
Why do you care about the order of game objects? Game objects could be created and destroyed at any time.

Generally the need to iterate is done based on spatial needs, or based on objects notifying the engine that they need special processing. Game objects should have their locations registered in a spatial tree and queries for their ID made against that. Objects needing processing should have their ID registered in a separate list for processing.

Similarly for render priority, rendering is different than a game object existing. If a game object needs to be rendered it should have the ID placed in a list of renderable objects that includes details including render priority.


There is generally a single collection of all the game objects. If it is a game object, it exists within that giant hash table.

Everything else references the ID of that object, not the object itself. Getting the actual object from the giant hash table is a simple task involving minimal resources. On the grand scheme of things, looking up objects by ID from a hash map is not a performance issue.
Check out my personal indie blog at bryanwagstaff.com.

#7 lithos   Members   -  Reputation: 413

Like
1Likes
Like

Posted 02 June 2013 - 09:13 AM

You can do both.  

 

When you put something in a list you're putting the reference in there, rather than the object(A reference tends to be 32-64 bits, but the size isn't guaranteed.  And references to other parts of the list and management won't hurt you too badly).    

 

If you can only do one it's trivial(though resource intensive) to convert a Hash Table/Map to an Array List with collections.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS