CODEWITHSUNDEEP
javadata-structuresconcurrency
Abe
Abe

Reputation: 9031

Appropriate datastructure or implementation class for holding a small but changing collection

I have written following game server and want to provide a groups feature. Groups will allow to group players together who are "nearby" on screen. In fast action games, this group would be changing fast since players will be moving in and out of their zones constantly.

Since each player would need to listen to events from other players in the group, players will subscribe to the group. This brings me to my question. What is the appropriate datastructure or java collection class which can be used in this scenario to hold the changing set of event listeners on a group? The number of listeners to a group would rarely exceed 20 in my opinion, and should be lesser than that in most scenarios. It is a multi-threaded environment.

The one I am planning to use is a CopyOnWriteArrayList. But since there will be reasonable amount of updates(due to changing subscriptions) is this class appropriate? What other class would be good to use? If you have any custom implementation using array's etc please share.

Upvotes: 4

Views: 205

Answers (3)

mikera
mikera

Reputation: 106351

Do players have integer IDs? If so then I have an lightweight, immutable array-based set class that might make sense for you:

This was written for similar kinds of situations in game engines.

However I also have an alternative approach to consider: If you are updating the groups automatically based on vicinity, then you might want to consider not tracking groups at all. Instead, consider using a spatial data structure that allows you to quickly search for nearby players whenever an event occurs, and directly send the event to nearby players.

Typically you could use a 2D or 3D grid or octree with the smallest division size set to be equal to the max range for your groups. Then a vicinity search will only need to check 9 (2D case) or 27 (3D case) locations in order to find all nearby players. I think doing this search whenever needed will be faster and simpler than the overhead of maintaining lists of groups and listeners all the time....

Upvotes: 1

assylias
assylias

Reputation: 328608

Unless you have millions of changes per second (which seems unlikely in your scenario) a CopyOnWriteArrayList should be good enough for what you need. If I were you, I would use that.

IF you notice a performance issue AND you have profiled your application AND you have identified that the CopyOnWriteArrayList is the bottleneck, then you can find a better structure. But I doubt it will be the case.

Upvotes: 2

user845279
user845279

Reputation: 2804

From what I've gathered, you have choice between CopyOnWriteArrayList and ConcurrentHashMap:

CopyOnWriteArrayList:

  1. Add/remove operation computational cost is linear to the size of the list. May happen multiple times during a single iteration (group notification).
  2. Simpler data structure with constant read time.

ConcurrentHashMap:

  1. Add/remove operation is a constant time operation. Additions or Removal of subscribers do not affect iteration already in progress and blocking is minimized.
  2. Larger data structure that requires slightly longer read time.

Creating a custom solution is possible when it comes to efficiency but probably not as safe when it comes to thread safety. I'm leaning towards ConcurrentHashMap but the winner will probably depend heavily on how your game turns out.

Upvotes: 1

Related Questions