0
\$\begingroup\$

I have a Node.js game that sends update packets to players every 30ms.

The code I currently use works this way:

  1. Get the entities within each player's vision.

  2. Create a temporary object that stores only the necessary properties of the entities that need to be sent.

  3. Compare this object to the entity that the client knows to get the differences.

  4. Compress using pako, and send to the client

This code takes about 2 milliseconds to run for 100 visible objects, but this is too slow as the server will be unable to handle more than 15 players.

Comparing to get the changed properties (step 3) took the longest time to execute.

What changes do I need to make?

\$\endgroup\$
2
  • \$\begingroup\$ When you profile this code, what seems to be taking the longest? Enumerating the objects to check visibility, constructing your temporary objects, performing the diff, compression, etc? Identifying the bottleneck can help focus efforts on improving that rate-determining step. If you want to scale to very large numbers of players though, you may need to consider switching to a language that gives you more control over performance than JavaScript — it's not really set up for high performance computing. \$\endgroup\$
    – DMGregory
    Nov 4, 2023 at 10:37
  • 1
    \$\begingroup\$ If you know that step 3 is taking the longest, you might want to post the code that you use for comparison \$\endgroup\$
    – Zibelas
    Nov 5, 2023 at 16:38

1 Answer 1

1
\$\begingroup\$

As DMGregory said, You can locate the performance problems of each step, or try another communication protocol and programming language. But I think the more significant problem is that your synchronization solution is not suitable for handling a large number of players on the same screen.

For cases like this, such as MMOs, an algorithm called AOI(Area Of Interest) is often used. I don't know if this is an official term as search engines don't give many valid results. Anyway I will introduce this method here.

The basic idea of AOI algorithm is as follows:

  1. Divide the space into 2D or 3D grids. Each grid object records a list(the observed) of entities which are in the grid, and a list(observers) of entities whose field of view covers the grid.
  2. When an entity moves, check whether the grid it is in has changed. If it has changed, move it from the the observed list of the previous grid to the new grid.
  3. When a client's field of view changes, remove it from the observer list in the grids those are no longer covered by the field of view, and add it to the new grids those are covered by the field of view.
  4. When an entity's properties change, mark it as dirty.
  5. In a new tick, traverse all grids and synchronize all dirty entities in a grid to all observers of this grid. And clear dirty mark of all.
  6. When a new observer joins the grid, the full data of all entities in the observed is synchronized to it. When an observer leaves the grid, send the observer a list of IDs of the observed, so that the client will delete them and no longer treats them as objects being tracked.

This will solve most of the problems you describe:

Get the entities within each player's vision.

No more repeated searches for entities within the field of view. Only the changes in the field of view coverage grid need to be calculated. This is much less computationally intensive

Create a temporary object that stores only the necessary properties of the entities that need to be sent.

The temporary object is still required, but the temporary object becomes unique per entity. There is no need to create a lot of new objects (allocate memory) every tick. You can reset this object after clearing the dirty mark.

Compare this object to the entity that the client knows to get the differences.

For all players in the grid, the synchronization data they need to receive is the same, and there is no need to repeat comparisons.

Compress using pako, and send to the client

All observers in the same grid need to receive the same data. Data for each dirty entity is compressed only once.

If AOI is used, it will bring considerable performance improvements. Here are a few more tips:

  1. The appropriate size value of the AOI grid needs to be tested. So make it configurable. It is best not to be larger than the actual field of view size of the client, because the minimum number of grids covered by the field of view is 4. If the grid size is too large, it will cause redundancy of transmitted data. If the grid size is too small, grid maintenance costs will increase.

  2. Since entities will only move to adjacent grids, using a cross-linked list instead of a two-dimensional array will bring performance improvements.

  3. A large amount of practice has shown that(I think) the importance of in-game data is inversely related to the frequency of its changes. Dirty data could be grouped according to its importance. They can have different synchronization frequencies. For example, entity positions can be synchronized to the client when they are created and velocity changes(or/and every 100 ticks), and the client can predict and interpolate the rest of the time. At the same time, important data such as entity HP and death status can be synchronized every tick.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ "For all players in the grid, the synchronization data they need to receive is the same" this is true except when one of the players just gained line of sight on that grid cell for the first time. That player might need more information about the thing being observed (e.g. what kind of object is it, what long-lived state is it currently in) than players who have been observing it in a recent update (who only need to know its latest incremental update). You cover this in point 6, it might just be worth clarifying that newly-observing-players aren't counted in the "all". \$\endgroup\$
    – DMGregory
    Nov 4, 2023 at 22:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .