All geek questions in one place

An appropriate data structure or implementation class for holding a small but changing collection

I wrote the following game server and want to provide a group function. Groups allow you to group players together who are "nearby" on the screen. In fast games, this group will change rapidly, as players will constantly move and leave their zones.

Since each player will 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 data class or java collection class that you can use in this script to store a changing set of event listeners in a group? In my opinion, the number of listeners in the group rarely exceeded 20 and should be less than in most scenarios. This is a multi-threaded environment.

I plan to use CopyOnWriteArrayList . But since there will be a reasonable amount of updates (due to a change in the subscription), is this class suitable? What other class would be useful? If you have a custom implementation using an array, etc., please share it.

+4
source share
3 answers

Do players have integer identifiers? If so, then I have a lightweight, immutable array based on a set that may make sense to you:

It was written for similar situations in gaming machines.

However, I also have an alternative review approach . If you automatically update groups based on proximity, you may not consider 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 events to neighboring players.

You can usually use a 2D or 3D grid or octet with the smallest division size set to the maximum range for your groups. Then a neighborhood search will only be needed to check 9 (2D-case) or 27 (three-dimensional cases) to find all nearby players. I think that doing this search as necessary will be faster and easier than the overhead of maintaining lists of groups and students all the time ....

+1
source

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

IF you noticed a performance issue AND that you profiled in your application AND , you found that CopyOnWriteArrayList is a bottleneck, then you can find a better structure. But I doubt it will be so.

+2
source

From what I put together, you have a choice between CopyOnWriteArrayList and ConcurrentHashMap :

CopyOnWriteArrayList:

  • Adding / removing operational computing costs linearly depends on the size of the list. It can happen several times during one iteration (group notification).
  • Simplified data structure with constant read time.

ConcurrentHashMap:

  • Add / remove operation is a constant time operation. Add-ons or Removing Subscribers does not affect an iteration that is already in progress, and blocking is minimized.
  • Larger data structure requiring 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 tend to ConcurrentHashMap , but the winner will probably depend heavily on how your game turns out.

+1
source

Source: https://habr.com/ru/post/1411436/

More articles:


All Articles