Hi everyone, i am wondering about some techniques of sending to a player the relevant position updates of players around, more specifically, the players that are on screen or close to that. So long i have discussed some approaches with my fellows; One presented was to have the server calculate for each player who is in the area around and send only updates from those players. I think this is complex and not much efficient. Another solution proposed was to have the scenario divided in sectors, and them send updates of those players which are in neighbor sectors. This one may be simple and fast, but maybe it is also a waste of time and resources because not all players in one sector can be seen from another sector. Comments, opinions and other ideas are appreciated. Thank you.

What is your update model?

If actions are stateless (player X receives information that player Y did Foo - is that enough, or do they need to know about what X did earlier?), then you can use proximity check on each action. When you receive an action, you find all other players in range (depending on action), and notify them.


If actions are not stateless (when X comes in range of Y, Y's stats and other data is first sent to X, and actions are then just subset of that), then subscription model works. When two players come into some interaction range, you subscribe them to each other. When X performs an action, it sends notification to all of its subscribers. This drastically reduces number of proximity checks needed. It may however result in oversubscription - if most actions require range 10, and one requires range 100, then each player will need to subscribe to all withing 100 range, even though all beyond 10 will never be able to interact.

Usually, a hybrid between the two works. Second model doesn't make it easy if actions have wildly varying ranges, but is almost required if state synchronization is non-trivial, e.g. if you cannot baseline sync all players to all players, deliberately don't want to do that, or if synchronizaton is expensive. Typically, message dispatching models have three modes - send to subscribers, send to all in range, send to all. Last two are for stateless messages.

Subscription model can be used to implement first model as well, just have dummy emitters with infinite or large range, so everyone in range automatically subscribes to them.


How the above models are implemented is mostly a technical matter. Cells work as form of approximate geohashing, various spatial indexes work as well (quad/sphere/r/kd trees). Implicit tiled structure can also work.

It's primarily about trade-off between accuracy and resources as well as overhead of baseline synchronization.

The second method works well and can be done with all O(1) algorithms (or close) if you're clever. I use a grid normally. Each entity is inserted into the grid and each client entity has a known entity hash set container. It's easy to see that for every client you can iterate through the nearby cells (either a rectangular camera in 2D, or a radius around the player). You can then insert entities into the known entity set for each entity in the cells in view. Also register with the entity you registered using the observer pattern. If you remove an entity from the game it must also be removed from all known entity sets. By registering the client entity with the entity you're adding to the known list you can easily keep track of what client entities to inform if that entity dies. If an entity doesn't exist in the player's set then it requires a full state update (send all the information). However, if the entity already exists in the list then you know a delta update is required (meaning only sending position, velocity or if the health changed). There's a few methods for handling when entities move. You can remove the entity and reinsert it every time into the grid, and that tends to work well. The nice thing about this method is that it can be ran every other game update and such so it becomes extremely cheap to compute. Oh and removing entities from the known entity set is easy. When you're iterating and building the packet remove entities that have moved too far away. If you decide to use this method and are confused just ask.

Or if you don't want to go to all that work just use the grid idea and grab all the nearby entities every time you build the packet for every player. However this method doesn't allow for full and delta states which can save a lot of bandwidth most of the time.

I use a combination of grids plus actual distances. A grid coordinate system is used and every update cycle the server positions the players into the correct grid. Each player's specific update data is created by traversing ships in their grid plus adjacent grids and calculating the distance and only sending information on ships that are within viewing range for the current cycle.

In our case (and I think in most MMOs), limiting the size of the updates is the highest priority so we have to calculate actual distances to ensure we keep the update data as small as possible.

Using the grid system was "optional" for us. In other words, we could have computed distance for every ship but that leads to an n-squared algorithm which we could foresee causing a problem with our expected number of ships.

I think you have to weigh the benefit of the grid system based on how many ships you can eliminate from the distance calculation. In our case, the grid system is 20x20 and the max view distance for a ship is the grid width. So, using the grid system we eliminate ships in 391 out of 400 grids from consideration which is definitely worth the extra computing cost of maintaining the grid ship arrays. We're still n-squared, but by cutting n by 95%, we think we're in the safe zone for our expected ships.

If our ships viewing distance were 1 grid and our space could only be split into 6x6 grids, then there would probably be no point in adding the overhead.

Thank you everyone for the ideas. I may come back later with doubts and what we have implemented.