It is necessary to solve several optimization problems in agario-like game - a large room, with several thousand objects of different types, different types interact with each other, but not all with all.

  1. Reduce the cost of rendering the interaction of game objects.
  2. Reduce network traffic and change tracking costs.

As a solution, I chose to replace the monolithic room with a sector map (sector vector corresponding to a two-dimensional map). The interaction is tracked only between objects within the sector. The following sector structure suggests itself:

struct Sector { std::set<Cell*> cells; uint16_t id {0}; };

The interaction itself is simply implemented through double dispatch. It is embarrassing that in this case it is necessary to constantly monitor the interaction of everyone with everyone (but already within the sector). It is clear that this is much more efficient than the same thing in one big sector (the whole room). But, for example now, my interaction is calculated (albeit in a whole room) only between those objects between which, in principle, there can be an interaction.

Shl. Or do not bother and saw double dispatch, but while writing a message I realized that in my game only 4 types of objects and then only the same type do not interact.

  • one
    classic advice in such cases - profiled? - KoVadim
  • @KoVadim, of course yes. Although I already doubt what your comment. I profiled the current version - a room as one large sector and without double dispatch, and it did not suit me. The breakdown into sectors + dual dispatch did not profile as it had not yet begun to cut this option. - sba

2 answers 2

After analyzing the options for the interaction of objects, I found the answer in a slightly different plane. According to game design - fixed bodies do not interact with each other. Therefore, a good solution in conjunction with double dispatch will be the elimination of impossible interaction options from the search.

My solution is to start two containers:

  1. Gridmap - fixed bodies, divided into square sectors (up to 10K objects).
  2. std::set<Cell*> - moving bodies (there are very few such objects, less than 100).

At each iteration, the interactions between each moving body and the bodies from the sectors in which the body is located, as well as all moving bodies, are processed in pairs. Stopped bodies or, on the contrary, those who have begun to move move into the appropriate container.

    To split a map into sectors there is a common name - spatial hashing. In addition to the division into sectors, in this approach additional improvements are applied:

    • interaction is calculated not for objects in the same sector, but for objects located in the same or in neighboring sectors. This implies that the size of the sector exceeds the maximum distance for interaction.
    • if the density of occupied cells is small, then to speed up the update, you can apply object coordinate hashing according to x + y * height with rounding, and store objects in a hash array instead of a two-dimensional matrix.
    • So do. I note that not all possible improvements are listed, and various improvements are appropriate for different tasks. For example, in my case, the size of at least one body can be many times larger than the size of the sector, so it’s common practice to check the central sector and 8 neighboring ones are not applicable here. I use the hashing approach for the sectors themselves - std::vector<Sector> , since this is immutable data. For moving bodies, most likely, there is no benefit from coordinate hashing, since they change too often (or I did not understand how to use it). It will be more optimal to sort by more filled axis. - sba