Add interest management support to the high-level multiplayer API

[jonbonazza]

Describe the project you are working on

And client-server multiplayer game with an authoritative server and large worlds, whether 2D or 3D.

Describe the problem or limitation you are having in your project

Problem Statement

When working with large worlds in client-server online multiplayer games with an authoritative server, the game world will have a lot going on all the time. Whether it's other players running around and doing various actions, NPC/Enemy AI, World Events, etc... it would be unreasonable to expect a player's computer to be able to handle processing and rendering everything in the game world at once.

Even if you break your world up into various instanced "zones," like many games choose to do, depending on the particular zone, it's still likely going to be too much data to process. Level streaming helps out on the rendering side of things, but it does little to assist in the processing department. Additionally, most of the stuff going on in the world or instanced zone isn't even going to be of interest (heh) to you since it's so far away that you likely can't even see it even if you wanted to.

The solution to this problem that is pretty much ubiquitous in large online worlds these days is Interest Management.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Interest Management

Interest Management can take a couple different forms, but ultimately, it's just reducing the number of things you send netowrk updates for to each player. A particular player will only recieve updates from game actors that are in their "area of interest" (a.k.a. "zone of interest", often abbreviated "AoI" or "ZoI"). In fact, game actors won't even be spawned into the player's client's game world until they are within their AoI and will be promply despawned from the player's local game world once they leave the AoI again.

Types of Interest Management

There are actually several different implementation approaches out there for interest management, however by and far the two most common are distance-based, and region-based. I'll be focusing on these two for the rest of this proposal. If you're interested in reading more about all of the various implementations out there for interest management, this paper does a great job of explaining them and each of their pros and cons.

Euclidean Distance

This is a popular one because we.... it's dead simple. A player will subscribe to server updates from any actor that falls within a set radius around them. In this implementation, this radius is often referred to as the player's "aura." While this is dead simple to implement, and computing the distance between two points in space is extremely fast, it has the major problem that it doesn't scale well at all. The more players that are in the game world or instance zone, the more comparisons need to be made every frame. It's for this reason, that the next approach is by and far the most common.

Grid-based

In this implementation, the world--or zone--is divided into a 2D grid of regions. As actors move about the world, some component (we'll call it the InterestManager here for lack of a better term) is responsible for keeping track of of what actors are in what regions. Any time the server sends an update by an actor, this InterestManager component is consulted to determine which specific peers should receive the update, and it only sends the update to those peers. Generally, this will not only include the other actors in the same region as that actor, but also those in the immediately adjacent regions as well (or sometimes a higher adjacency is used. The specific region size and adjacency are parameters that are unique to each game and require careful tuning to get right). Likewise, when the InterestManager notices that an actor changes regions, it will recalculate its interested parties, and spawn the actor in the game clients of newly interested players, and despawn it from those who are no longer interested.

Unlike the distance approach above, this one scales incredibly well, but it is much more complicated to implement. The biggest downside for this approach however, is that a simple 2D grid is a rather poor approximation of interest, so for games that require higher degrees of precision, other approaches might be considered instead.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

Proposed Implementation

UPDATE: @Faless created a much more elegantly generic API that better fits core here. His proposed implementation supersedes the one documented here, but I left this one for context.

Original Implementation

First, a common interface will be created that all interest management implementations can inherit from.

class InterestManager : public Node {


    // Updates a node's position with the manager. This should be called for every actor
    // on the server any time they move. If appripriate get_multiplayer().get_replicator()._send_spawn()
    // and get_multiplayer().get_replicator()._send_despawn() should be called to (de)spawn the nodes on 
    // specific peers that gain or lose interest.
    //
    // We don't use a Node2D or Node3D directly
    // here so that we can have a single interface that works for both.
    //
    // Note that we are always using a Vector2 here. This is because in most 3D games, there isn't much verticality, so we only
    // really care about 2D positioning. I think this should be fine, even if a game does care about verticality, but I'm 
    // not entirely certain.
    virtual void update_node_position(Node *node, Vector2 position) = 0;
};

With this simple interface, we can implement different types of interest management and users can either put them directly in their scene or even add one as a Singleton. Additionally, multiple implementations could theoretically be used together as well. Whetehr or not that's actually useful in practice however, I'm not so sure.

Now let's take a looks at some pseudocode for a grid-based implementation.

// grid_interest.h

// Implements a region-based solution to interest management described above.
// This is a TOOL class so that it can render a grid in the editor viewport when
// selected in the scene tree. See draw_grid below.
class GridInterestManager : public InterestManager {
protected:

    // InterestGrid here is just a basic class that is used here to abstract the complexities of managing the region grid.
    InterestGrid grid;

public:
    virtual void update_node_position(network_id : int, Node *node, Vector2 position);

    // Updates the overall size of the grid. Should be used sparingly as this is expensive due to
    // needing to recalculate the regions and who is in what region. Generally only done at _ready.
    //
    // exposed in editor inspector.
    void set_grid_bounds(Vector2 grid_bounds) { grid.set_bounds(grid_bounds); }

    // exposed in editor inspector
    Vector2 get_grid_bounds() { return grid.get_bounds(); }

    // Updates the size of each region (cell) in the grid. Similar to set_grid_bounds, this will cause
    // the grid to recalculate everything so it's very expensive and should be used sparingly. Again,
    // only really necessary at _ready.
    //
    // exposed in editor inspector
    void set_region_size(Vector2 region_size) { grid.set_region_size(region_size); }

    // exposed in editor inspector
    Vector2 get_region_size() { return grid.region_size(); }

    // AreaOfInterest is just an aggregation of 9 regions (a center region and the 8 adjacent ones). All areas of 
    // interest for a grid are calculated when the grid is constructed (or reconstructed) and cached in memory, as 
    // well as each individual region. Additionally, a hashmap of node instance id to AreaOfInterest* is maintained 
    // so that this lookup can be O(1).
    AreaOfInterest* get_aoi_for_node(Node *node);

    // I don't know if this function signature is correct, but the idea here is that whenever this node
    // is selected from the scene tree, it will render the configured grid in the editor viewport.
    void draw_grid(Control *overlay);
};


// grid_interest.cpp
void GridInterestManager::update_node_position(network_id : int, Node *node, Vector2 position) {
    // This will calculate the AreaOfInterest for the node and if it's changed, add the node to
    // the new AoI's list and remove it from the old one's. For each AoI, a list of changes
    // is maintained, which is useful later.
    //
    // Also, if position hasn't changed, this is effectively a no-op.
    grid.update(node, position);
};

void GridInterestManager::remove_node(Node *node) {
    grid.remove_node(node);
};

This handles keeping the region list up to date with who's in what region, but now we need to handle those changes somehow. Doing this all in one big for loop obviously isn't great as it will end up bogging the framerate down at runtime. Instead, we will flip the problem on its head and use a second new Node type.

// interest_area.h

// InterestArea keeps track of the AoI for a spefic actor.
class InterestArea2D : public Node {

public:
    // These 3 are exposed in the inspector via their paths. actor will default to ".." for convenience.
    Node2D* actor;
    GridInterestManager* interest_manager;
    int network_id;

protected:
    void _spawn_interests(Region *region);
    void _despawn_interests(Region *region);
};

// interest_area.cpp

// Yea, yea. I know that in the cpp code, _notifaction is used directly, but I'm too lazy to 
// write the glue for that here, so this is what you get. Basically, this is just called once per frame.
void InterestArea::_process(float delta) {

    interest_manager->update_node_position(network_id, actor, actor->get_global_position());

    // We don't want to free this when we are done because it's a pointer to data managed by GridInterestManager.
    AreaOfInterest* aoi = interest_manager->get_aoi_for_node(actor);
    _despawn_interests(aoi);
    _spawn_interests(aoi);
    // This simply clears the dirty interest lists so that next time we process them, they only have new stuff.
    region->clean();
}

void InterestArea::_spawn_interests(AreaOfInterest *aoi) {
    for (int j = 0; j < aoi->gained_interest->size(); i++) {
        // Interest is just a pair of node and its network id.
        Interest interest = aoi->gained_interest[1];
        const ObjectID oid = actor->get_instance_id();
        // These two method actually aren't currently exposed, and will need to be so in order for this to work. Alternatively 
        // (and honestly more preferred imo) is th have an exposed `spawn` method that can derive trhe spawner argument from
        // the passed in Node itself.
        MultiplayerSpawner *spawner = get_multiplayer_api()->get_replicator().get_spawner(oid)
        get_multiplayer_api()->get_replicator()->_send_spawn(interest.node, interest.network_id);
    }
}

void InterestArea::_despawn_interests(AreaOfInterest *aoi) {
    for (int j = 0; j < aoi->lost_interest->size(); i++) {
        Interest interest = aoi->lost_interest[1];
        // This method will need exposed for this to work.
        get_multiplayer_api()->get_replicator()->_send_despawn(node, interest.network_id);
    }
}

There should exist one InterestArea node for each actor that exists in the world, but there should only be one GridInterestManager for an entire "zone." (Though there doesn't strictly need to be, as mentioned above. Maybe users will get creative on uses here.)

Doing the spawning/despawning in this way should be pretty quick, even in super dense areas, as the number of poeple entering and leaving a AoI should be pretty small.

[jonbonazza]

Hmm after more deliberation, ive determined this isn’t quite going to work from a performance standpoint, particularly in especially dense areas of a map. Im considering alternative approaches now and will update this proposal once i think of something better.

[jonbonazza]

Okay, I've updated the proposal with something a bit more complex, but should scale much better.

[stmSi]

Interest Management is also essential for any competitive RTS genre games given the fact that Hacker can change Client's FOW (Fog Of War) code.

[Faless]

Howdy! Thanks for looking into this.

I've been thinking about this topic for a while now, and I'd like to propose something a bit different, but that should also allow implementing the nodes you mention, along with more game-specific custom nodes when needed by the game developers.

This idea stems from the consideration that there a multiple reasons for doing interest management, which does not always overlap, e.g.:

• Player vision
• Team-wise informations
• Rooms/Levels
• ... (other game specific informations?)

Given these premises, the idea is to add a "tag" system to both objects and peers, requiring peers to have a matching tag to be able to "see" the given object.

Currently, tag composition is assumed using OR (see below for examples), but it might be interesting to also add AND composition (multiple tag layers?) which could make more complex use cases easier at the cost of perfromance.

So, here is a brief of the proposed changes.

MultiplayerAPI

class MultiplayerAPI {

	Error tag_object(Object *p_obj, const StringName &p_tag);
	Error untag_object(Object *p_obj, const StringName &p_tag);

	Error tag_peer(Object *p_obj, const StringName &p_tag);
	Error untag_peer(Object *p_obj, const StringName &p_tag);
}

Replication

class MultiplayerReplicationInterface {
	Error on_object_tag_change(Object *p_obj, const StringName &p_tag, bool p_add);
	Error on_peer_tag_change(Object *p_obj, const StringName &p_tag, bool p_add);
}

Note, in this context, spawn/despawn also means disabling sync for path-only nodes (which cannot be despawned).
Tags are composed using OR.

When an object is tagged:

• If it had no tags, despawn from all peers without that tag.
• If it had tags, cycle peers with that tag, spawn if not spawned for that peer.

When an object is untagged:

• If removing means it has no tags, spawn to everybody.
• If removing means it still has tags, for every peer with that tag, despawn if no other tag match.

When a peer is tagged:

• Spawn all objects with the given tag if not spawned already.

When a peer is untagged:

• Despawn all objects with the given tag where no other peer tag is matching.

RPC

This needs further exploration, but I think we could use the tag system for RPCs too.

class MultiplayerRPCInterface {
	Error on_peer_tag_change(Object *p_obj, const StringName &p_tag, bool p_add);
}

We could force that for objects with at least one tag, broadcast rpcs will only be sent to peers with at least a matching tag.
We could add a @rpc(tag) annotation.
We could also filter RPCs on the receiving end using those informations, but multiple tags and OR composition might cause some unexpected behaviour.

Example

MultiplayerVisibility (2D/3D)

A pontential implementation for higher level nodes that can be included with Godot (properly expanded if necessary):

---

An extension of Area2D (or Area3D) that automatically tag/untag overlapping objects.

# Uses an area to detect visibility automatically tagging/untagging other MultiplayerVisibility
MultiplayerVisibility2D : public Area2D {
	var tag_name : StringName
	var root_path : NodePath
}

Given MultiplayerVisibilitys:
MV1 -> [tag_name="player_1", root_path=".."]
MV2 -> [tag_name="player_2", root_path=".."]
MV3 -> [tag_name="", root_path=".."]
Given peers:
P1 -> [tags=["player_1"]]
P2 -> [tags=["player_2"]]

Where MV1 represents P1, MV2 represents P2, and MV3 represents an object not associtated to a player.

When MV1 overlaps MV2:

• MV1 root_path will be tagged to player_2
• MV2 root_path will be tagged to player_1

Player 1 and 2 will see each other.

When MV2 and MV1 no longer overlaps:

• MV1 root_path will be untagged from player_2
• MV2 root_path will be untagged from player_1

Player 1 and 2 will no longer see each other.

When MV1 overlaps MV3:

• MV3 root_path will be tagged to player_1

Player 1 will see root of MV3.

When MV3 leaves MV1:

• MV3 root_path will be untagged from player_1

Player 1 will no longer see root of MV3.

[Ansraer]

Interesting idee to implement this with tags. I suppose you could imitate a distance based system by having a grid of tag-areas...
I personally would still like the hooks available so that I can add my own logic as a gdextension, but for most other use cases this tag based system should work fine.

Not sure how I am feeling about using Strings under the hood. Enums or just numbers would scale significantly better.

Edit: Wait, nevermind, forgot about StringNames.

[Faless]

Not sure how I am feeling about using Strings under the hood. Enums or just numbers would scale significantly better.

Note that it doesn't use Strings but StringNames which under the hood (i.e. beside the creation cost) are compared via pre-computed hash (actually, pointer in the stringnames table IIRC).

EDIT: didn't get the edit in time :)

[Faless]

I personally would still like the hooks available so that I can add my own logic as a gdextension, but for most other use cases this tag based system should work fine.

What hooks are you referring to here? We can probably expose a bit more if it's not enough.

[Ansraer]

In some of the earlier interest management discussion (on rocketchat I think) we discussed the possibilities of exposing the underlying code so that more complicated projects could write their own interest management system as a gdextension.
Been a while, but I think the rough idea was that people could provide a function that, when given the packet, object and receiving peer would return either true or false.

[Faless]

@Ansraer oh yes, I see, we can also add a virtual method to synchronizer _should_sync(object, dest_peer), though I fear that would be really unoptimized? Still, if it solves some problems it's probably worth adding since performance shouldn't change if you don't override it beside an extra if.
What's more tricky in that case though, is spawning/despawning, which I wouldn't know how to handle with such a function.

[Ansraer]

Uh, been a while. I think the general idea was that whenever this method returned true the object would be automatically spawned on the client if it didn't already exist there. Not sure how despawning was supposed to work.

Perhaps an enum with four values could be returned instead of a boolean (spawn&sync, sync if already exists, don't sync, don't sync & despawn)?
I can't remember the exact details, but we all agreed that we would like the possibility to either adjust or just replace godot's default interest management system.

Spent some more time thinking about your proposed tag system btw, and I would really like the ability to provide a conjunctive normal form of tags.
Cause if we have only OR the moment I add position tags all the information ends up at any client that manages to get close enough.

[Faless]

Uh, been a while. I think the general idea was that whenever this method returned true the object would be automatically spawned on the client if it didn't already exist there.

Not sure how despawning was supposed to work.

That is indeed the problem, it would mean that we need to call that function for every peer, for every MultiplayerSynchronizer, every frame, no matter which peer knows about it or not. Which I am not sure is going to work performance-wise unless the function you call is very simple or have a very low number of replicated objects implementing that function.

So I'm not sure this can actually work in anything bigger than a small-sized game due to the high number of calls it requires during each frame.

Cause if we have only OR the moment I add position tags all the information ends up at any client that manages to get close enough.

I agree, this is a quite rigid, and forces to use combined tags (i.e. doing the and manually in the tag name).
As mentioned multi layer tags explodes the complexity and makes untagging quite inefficient in some cases, though we can probably have something like e.g.:

class MultiplayerAPI {
	Error tag_object(Object *p_obj, const StringName &p_tag, int p_layer=0);
	Error untag_object(Object *p_obj, const StringName &p_tag, int p_layer=0);
}

Where different layers are composed using AND, and a peer needs to have at least one matching tag with every layer in the object.
This way adding tags is still rather cheap, while removing them could be heavy (especially in the case where you remove the last tag on a given layer because a full peers/tags check has likely to be performed).

But I think it can still perform well if used appropriately.

[TackerTacker]

I probably misunderstand, but how is there suppose to be an overlap check between two moving players, to check if they should send data to each other, when they are not already sending data to each other about their position?
I understand how it would work on a static grid, every player updates when they enter or leave a cell, requesting everyone in that cell and then send notifications to all of them that you entered or exited. You would also have to update your neighboring cells as well so that there is never the situation of being just at the edge of a cell where things suddenly plop in and out of existence, but it would still be better than overlap, no?!
Without a grid, based on overlap/distance you have to constantly update to check everyone's position relative to you to know if you overlap/are close enough, so you have to constantly update everyone anyways ...right?
But I'm probably missing something.

[Ansraer]

You could implement a grid with a tag based system:
Whenever a player enters a cell he gets the tag for that cell and e.g. the 8 surrounding cells.
Though you are right that we no longer have a convenient data structure so we don't have to iterate over all peers.

[Faless]

I probably misunderstand, but how is there suppose to be an overlap check between two moving players, to check if they should send data to each other, when they are not already sending data to each other about their position?

@TackerTacker The host knows about both players positions at all time, the host is the one doing the tagging/untagging in the MultiplayerVisibility example.

I don't know any way to do position-based interest management in a true p2p scenario.
As far as I know those tend to have fully visible state due to the requirement of consensus, but there might still be areas where interest management can help in a true p2p scenario, e.g. top of my mind: RPCs for a "team chat".

[reduz]

I wanted to suggest some things to this proposal. I want to focus mostly on the usability side as always (what is exposed to the user) How it is implemented underneath we can see later. As such, I am more concerned about the MultiplayerSynchronizer node, which is what I think should allow controlling the interest management (Imo as what we synchronize is scenes, we should not do this at Object level).

API can be something like:

synchronizer.use_peer_filter= true/false

This turns on the interest management for this node. If false (default), this always does synchronization and on every frame with all other peers. When on, certain rules need to be supplied for synchronization to happen:

synchronizer.set_peer_allowed(MultiplayerSynchronizer* peer,true/false)

And thats it. Additionally, I would still like to add the ability to customize, per frame, whether synchronization happens. This being independent of the peer filter (if peer filter is enabled it will only call this after the filter passes):

synchronizer.add_custom_filter(Callable filter)
synchronizer.remove_custom_filter(Callable filter)

Callables are efficient, so the custom function can be implemented as:

func _validate_peer(peer : MultiplayerSynchronizer):
    return (run_some_logic_on_whether_it_should_sync(peer))

So IMO, you can still efficiently implement a tag system or anything you want over this (or even control update frequency by returning true or false intermitently), but it gives you far more control and flexibility on implementing this.

A Tag system can be an extra node (that inherits synchronizer or that exists outside) that users can download from the user library as an add-on and implement this. It can be perfectly implemented outside the multiplayer classes, which allows keeping the MP API simple.

[Faless]

I've added a tentative implementation in godotengine/godot#62961 , see there for details, but here's the gist:

Sets visibility for synchronized objects: $MultiplayerSynchronizer.set_visibility_for(peer_id, visible)

or

extends MultiplayerSynchronizer

func _enter_tree():
	add_visibility_filter(self._is_visible_to)

func _is_visible_to(peer) -> bool:
	return false # Hidden

The visibility is updated on every frame (default), physics frame, or manually.
You can further notify visibility changes by calling $MultiplayerSynchronizer.update_visibility(peer:=0) (where 0 means for all peers).

This also allows players to join mid-game (with some quirks).

[Faless]

I'm reopening this to keep track of the fact that we still need interest management in RPC (i.e. method.rpc() does not yet work as expected when using synchronizers with limited visibility).

It should be implemented soon, but we are planning to do some core changes first godotengine/godot#63049

[Faless]

Closing since RPC visibility is now also implemented via godotengine/godot#68678 .