Interest management is a very important technique to make massively multiplayer online games scale better. In this article, I’ll first start by explaining what it is and why it is useful. I’ll proceed with a concrete example, showing how it was implemented in Phaser Quest.

What is interest management

Imagine you have just rolled out your brand new MMO, featuring a vast open world to explore. Naturally, you’ll have tons of players. At a given moment, some of these players might be visiting a dungeon in one corner of the world, while some others might be exploring a forest far, far away.

In a basic implementation, when a player performs an action, the server will receive a command from the corresponding client. After validating the action, it will then broadcast it to all the other connected clients, to ensure that all clients are properly synchronized. However optimized this process might be, if you have a lot of connected players, this will mean a lot of data to send during each update cycle.

The question is : do the players in the dungeon really need to be informed of what the players in the forest do? The answer is no, naturally. Not receiving the information from other parts of the game world will not affect the experience of the players in the dungeon (provided that, as soon as they move to a different area, they are able to catch up to the missed updates), while greatly diminishing the amount of data to process.

Interest management consists in determining which updates are interesting to which clients, in order to exclusively send relevant information. In the context of multiplayer online games, this is determined based on the location of the players. Events are broadcast to players nearby, and only to them. What is “nearby”? This is typically defined by partitioning the world in Areas Of Interest (AOI). For example, the world can be divided in a grid, as in the picture below:

Then, nearby players are players belonging to the same AOI. If a player in AOI 2 performs an action, only players inside AOI 2 will receive the corresponding update.

What if two players are in two adjacent AOIs, but very close to the border between the two? They will be able to see each other, but they won’t receive each other’s update because they belong to different AOIs. I call this the “border effect”. In order to fix that, the solution is to notify players of what happens within their own AOI, as well as within each neighboring AOI, to avoid this problem.

In this example, the AOIs have rectangular shapes. Multiple variations exist, with circular or even hexagonal shapes, with various benefits depending on the game. In more advanced implementations, no areas are used at all. The relevance of updates are determined by computing whether an event is taking place within the field of vision of the player. The latter is a bit more computationally expensive and mostly useful for first-person games rather than top-down ones, but is interesting to mention.

Now that we have seen what interest management is, let’s have a look at the implementation of this system in Phaser Quest.

Interest management in Phaser Quest

Overview

Based on the shape and size of the area of the map that the players can see, I opted for rectangular AOIs of 34 by 20 tiles. The goal is to make the AOIs as small as possible, to filter the updates as much as possible, while not risking missing something happening nearby. Based on this AOI size and the size of the map, this results in 96 AOIs in total, with numerical ID’s ranging from 0 to 95.

js/server/AOI.js

Each AOI is represented by an AOI object, which stores its ID and coordinates.

function AOI(x,y,w,h){
    this.id = AOIutils.lastAOIid++;
    this.x = x;
    this.y = y;
    this.width = w;
    this.height = h;
    this.entities = []; // list of game objetcs (players, monsters, items...) situated within the area corresponding to this AOI
    this.updatePacket = new UpdatePacket();
}

In addition, it stores two important objects:
– A list of the game objects currently present within the AOI,
– An UpdatePacket object which records the changes in local game state (the changes that happened within the AOI). These UpdatePacket objects follow the same principles as described in here, except there are now 96 of them instead of one.

Game objects store at all time the ID of the AOI they are currently in. Whenever they move, this ID is updated accordingly.

Whenever an event takes place (a player moves, picks up an object, kills a monster…), the update packet of the corresponding AOI, as well as those of the neighboring AOIs, record the change. The set of affected AOIs is called the neighborhood. Then, during each update cycle, for each player, the changes stored in the update packet of his/her current AOI are fetched and transmitted, and only those.

I call this principle of updating multiple AOIs but fetching updates from only one, “update many, fetch one”. The rationale is to make the more expensive operations take place less often than the cheaper ones. The more expensive operation here (although still quite cheap) is the update of multiple AOIs, while the cheap one is the fetching of a single update packet. Changes occur less often than the update cycles do; it is therefore more economical to update all neighboring areas when the change occur, rather than looking up all neighboring areas for updates each time an update has to be sent.

Finally, when a player moves from one AOI to another, he is brought up to speed with the game objects in the neighborhood of the new AOI that were not in the neighborhood of the previous one. The next sections present these operations in more details.

Creating the AOI objects

js/server/GameServer.js

The height and width of an AOI are the only predefined parameters, the rest is computed when the server starts, in GameServer.readMap(). This function reads a few JSON files, including the map file, and sets up useful data structures, such as:

GameServer.AOIs = {}; // Maps AOI id to AOI object
GameServer.dirtyAOIs = new Set(); // Set of AOI's whose update package have changes since last update
GameServer.AOIfromTiles = new spaceMap(); // maps tiles coordinates to AOI id (e.g. the tile (3,2) is in AOI 0)

GameServer.AOIs can be used to fetch the AOI object corresponding to a given ID, for example to obtain the UpdatePacket of the AOI a player is currently in (since player objects keep track of their AOI id). GameServer.dirtyAOIs is the set of AOI objects which have recorded a change since the last update. Keeping track of these allows to avoid having to iterate through all of them. Finally, GameServer.AOIfromTiles maps tile coordinates to the id of the AOI containing the tile, in order to easily identify which AOI need to be notified of an action which has taken place at a given position.

GameServer.readMap() then proceeds to iterate over all the tiles of the map, to generate the collision array used for the pathfinding. At the same time, it creates the AOI objects on the fly, and populates the data structures introduced above. Each AOI object contains a new, empty instance of an UpdatePacket object.

Updating the Areas of Interest

js/server/GameObject.js

When something changes in the game, it always corresponds to a change of a property of a GameObject instance (a player, a monster or an item). When this happens, the GameObject.updateAOIs() method is called. It lists all the AOIs adjacent to the one containing the game object (including the containing one) and updates the UpdatePacket instance of each of these to reflect the change. In addition, all affected AOIs are added to the GameServer.dirtyAOIs set.

GameObject.prototype.updateAOIs = function(property,value){
    // When something changes, all the AOI around the affected entity are updated
    var AOIs = this.listAdjacentAOIs(true);
    var category = this.category; // type of the affected game object: player, monster, item
    var id = this.id;
    AOIs.forEach(function(aoi){
        GameServer.updateAOIproperty(aoi,category,id,property,value);
    });
};

js/server/GameServer.js

The main update function is GameServer.updatePlayers(). For each player, it fetches the UpdatePacket of the AOI the player is currently in and perform a few “cleaning” operations before sending it to the client. Once all clients have received their UpdatePacket, all the non-empty update packets are emptied, ready to store new changes for the next update cycle. The non-empty update packets are the update packets of the AOIs listed in GameServer.dirtyAOIs.

Keeping track of the position of game objects

js/spaceMap.js

First, a word on how the server keeps track of the location of game objects. This is done using 2D associative arrays, dubbed space maps because it sounds cool. These arrays require two keys to retrieve an entry: the x and y coordinates of the object. For example, playersMap[10][11] will return the player objects at position (10,11). This can be viewed as a form of hashing, where pairs of x and y coordinates map to buckets that immediately correspond to tiles of the game.

This is appropriate for Phaser Quest, as the game is tiles based: the game world is divided in a finite set of discrete coordinates. Continuous coordinates would require another kind of data structure suited for spatial indexing, such as a quad-tree or R-tree.

js/server/GameServer.js

Since a space map basically maps tile coordinates to game objects, it can also be used to find which AOIs contains an object, if the coordinates of the object are known. The space map GameServer.AOIfromTiles is filled in GameServer.readMap(), and maps coordinates to instances of AOI objects.

GameServer.AOIfromTiles.add(x,y,GameServer.AOIs[getIDfromCoords(x,y)]);

The hashing function getIDfromCoords() returns the id of an AOI given a set of coordinates. GameServer.AOIs maps the id of an AOI to the corresponding AOI object.

Moving between Areas of Interest

js/server/GameServer.js

When a game object is added to the world, it is done so using GameServer.addAtLocation(). This method does two things. First, it adds the game object to the proper space map. Second, it fetches the relevant entity based on the object’s coordinates, and adds the object to the AOI’s list of objects (remember that each AOI keeps a list of the game objects it contains). Similar (but opposite) manipulations are performed when a game object disappears from the world.

GameServer.addAtLocation = function(entity){
    // Add some entity to all the data structures related to position (i.e. the spaceMap of the category of the entity, and the AOI)
    var map = GameServer.getSpaceMap(entity);
    map.add(entity.x,entity.y,entity);
    GameServer.AOIfromTiles.getFirst(entity.x,entity.y).addEntity(entity,null);
};

When a game object moves, GameServer.moveAtLocation() updates the space maps accordingly. If the move crosses the boundary between two adjacent AOIs, their lists of objects are also updated, to reflect that the object is now in a new AOI. Each object also keep track of the id of the AOI it is in; this property is updated as well at this point.

GameServer.moveAtLocation = function(entity,fromX, fromY,toX,toY){
    // entity is the game object (player, monster, item) that is moving
    // Update the position of an entity in all data structures related to position (spaceMap and AOI)
    var map = GameServer.getSpaceMap(entity);
    map.move(fromX, fromY, toX, toY, entity);
    var AOIfrom = GameServer.AOIfromTiles.getFirst(fromX,fromY);
    var AOIto = GameServer.AOIfromTiles.getFirst(entity.x,entity.y);
    if(AOIfrom.id != AOIto.id){
        entity.setProperty('aoi',AOIto.id);
        var previousAOI = AOIfrom.id;
        AOIfrom.deleteEntity(entity);
        AOIto.addEntity(entity,previousAOI);
    }
};

When a player moves from one AOI to another, a final step has to be taken. Consider the picture below.

Each cell corresponds to an AOI. The dark-blue cells constitute the neighborhood of the player. If something happens in one of the dark-blue cells, the player’s cell will receive the update as well, since all adjacent cells will receive the update. Therefore, the player will receive updates about all that happens in the dark-blue neighborhood. Conversely, the player will not receive any information about what happens in the light-blue cells. For example, he won’t receive updates about the rabbit. Actually, the player will not even know of the existence of the rabbit, and the client will not have any rabbit sprite created.

If the player moves one AOI to the left (right side of the picture), his neighborhood will change, but only a part of it. The new part corresponds to the light-green cells. Now, the player and the rabbit are sufficiently close to each other that one of the two could make a move that should make him visible to the other. Therefore, the player needs to catch up about the status of the rabbit.

This is accomplished in GameServer.handleAOItransition(), where the AOIs corresponding to the light-green cells are identified, and stored in a list called newAOIs.

GameServer.handleAOItransition = function(entity,previous){
    // When a player moves from one AOI to another, identify which AOIs should be notified and update them
    var AOIs = entity.listAdjacentAOIs(true);
    if(previous){
        var previousAOIs = AOIutils.listAdjacentAOIs(previous);
        // Array_A.diff(Array_B) returns the elements in A that are not in B
        // This is used because only the AOIs that are now adjacent, but were not before, need an update. Those who where already adjacent are up-to-date
        AOIs = AOIs.diff(previousAOIs);
    }
    AOIs.forEach(function(aoi){
        if(entity.constructor.name == 'Player') entity.newAOIs.push(aoi); // list the new AOIs in the neighborhood, from which to pull updates
        GameServer.addObjectToAOI(aoi,entity);
    });
};

Then, when the time comes for an update, GameServer.updatePlayers() fetches all the game objects present in these new AOIs and send them to the client, so that they can be created in the client’s view of the game state.

Conclusion

Interest management and areas of interest constitute an important and useful concept for networked games. Hopefully, the explanations about how it was implemented in Phaser Quest will inspire you for your own implementation, tailored to the specifics of your own game. As you have seen, there is nothing difficult to it, it’s mostly a matter of keeping track of things with appropriate data structures (as efficiently as possible of course). Don’t hesitate to have a look at the source code if it can help you make these explanations more concrete, and of course, don’t hesitate to contact me if you have any questions.