Sign in to follow this  
Matt77

How to know what player position updates send to another player

Recommended Posts

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.

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Calculating who is close on the server shouldn't take lot of time in the simple case -- certanly be a lot more efficient than sending too much data out from the server.

But, yes, in general, when you do interest management, you have a part of the server which determines which other objects any given user should see. Whether you do that using a quad tree, grid, priority queue or some other system is actually not that important (unless you literally have thousands of objects).

Share this post


Link to post
Share on other sites

Depends on your viewing mechanism -- if the size of a sector X:Y is larger than the maximum sensor range of players then posting it to each adjacent sector (a grid?) neigbors and letting the objects in those sectors there filter the list.
(If the sector size is much greater than the sensor radius then you can cull out sending to specific neighbor sectors if the sensor radius doesnt cross the specific sector edges )

If your view range can cross more than one layer deep of sectors than you have to send to all of those the circle intersect with.


Another thing to take into account is how many objects per sector will react to your objects proximity (how many are in sight of each other at any point in time). If the counts are low, brute force list traversals are often faster than more complex schemes (if the total player count in entire game is low you might get away with a global list for the entire map). Same goes for interaction counts over time (like if you only check once a second). If low, you can afford a simpler (less efficient) mechanism because the total load will not be significant either way.


For specific range checking use 'lazy evaluation' where you cull out negative cases with the cheapest method fisrt -- like a box search
((dX>range) or (dY>range)) to eliminate obvious out of range cases, before you do more costly sqrt range and your other visibility checks.


If you arent using a square grid sector system (ex- using irregular sizes), you can have a precanned list made for each sector as to which adjacent sectors are within view range (to eliminate recalc over and over..)

Of course you will have more fun if different objects have different sensor ranges.

Share this post


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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this