Jump to content
  • Advertisement
Sign in to follow this  
P0jahn

Entity storage, ArrayList or HashMap?

This topic is 1941 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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)

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!