MMORPG Server [Visible service]

Question

Is there an algorithm for collecting the list of [to_spawn][to_despawn][to_send_movement] players from world on player movement from point A to B.

I have list of player in world. I have function that collects the visible players for a given point. Each player has a list of visible players.

How can I do this fast & efficient?

void p_spawn::filter(player_list &p_l)
{
    player_list to_depsawn;
    player_list to_spawn;
    std::shared_ptr<Node> temp = std::atomic_load(&head);
    if (p_l.size() > 0)
    {
        while (1)
        {
            if (!temp) break;

            bool in = false;
            for (size_t i = 0; i < p_l.size(); i++)
            {
                if (p_l[i]->eid == temp->p->eid)
                {
                    in = true; break;
                }
            }

            if (!in)
            {
                to_depsawn.push_back(temp->p);

                temp->p->spawn.add_erase(parent, false);
                add_erase(temp->p, false);


            }
            temp = temp->next;
        }


        for (size_t i = 0; i < p_l.size(); i++)
        {
            if (!inside(p_l[i]->eid))
            {
                add_erase(p_l[i]);
                p_l[i]->spawn.add_erase(parent);

                to_spawn.push_back(p_l[i]);
            }
        }
    }
    else
    {
        while (1)
        {
            if (!head) break;

            head->p->spawn.add_erase(parent, false);
            to_depsawn.push_back(head->p);
            head = head->next;
        }
    }


}

Answer 1

The short answer to your direct question: generate your list of visible entities in a container (sorted by id or the like) and use std::set_difference with the previous sorted list of visible entities.

You are asking roughly about Area of Interest: finding all objects within range of a player for which it should receive network updates.

The simple algorithm for a range-based test like illustrated would be to gather all objects within range (use your game's bounding volume hierarchy for this), and then calculate a set difference with the previous update's AOI set (just about every programming language has a standard library function for doing this efficiently; std::set_difference in C++ for example).

The difference in one direction tells you which objects have been removed from the AoI set. The difference in the other direction tells you which objects to added to the AoI set.

Note that you really don't just want a single range like this. You want two ranges: a closer "add to AoI" range and a larger "remove from AoI" range. Otherwise, you easily get into a case where objects ping-pong between being in AoI as they move along the edge of the AoI range, which can lead to excessive amounts of network traffic for add/forget packets, along with whatever client-side work those packets trigger (like loading/unloading resources). Using two separate ranges with a suitable distance between them avoids this from happening in every case except where an object is just moving back and forth, close and far.

You can also apply other AoI schemes on top of this. For instance, you might have an Explicit Object of Interest system that ensures a particular object stays in a client's update set independent of range. This can be useful for enemies that are attacking the player or have recently been attacked by the player. You might also use AoI schemes that aren't just simple ranges, such as using the player's look direction to form a Cone of Interest.

Yet another trick is to add a delay to objects leaving the update set. This is another potential solution for objects sitting near the AoI range, as well as avoiding frequent add/forget messages if using a Cone of Interest and the player is looking around a lot.

Note also that this all applies pretty much equally to other range-based systems like chunk loading in an open world game.

Answer 2

Sounds to me like what you are after is known as Potentially Visible Sets. I'd be surprised if there is any 3D game that doesnt implement some form of it.

If you need an implementation, Doom and Quake code implements it.

https://en.wikipedia.org/wiki/Potentially_visible_set