MHServerEmu Progress Report: June 2024

June has been jam-packed full of developments, and we have a lot to cover.

MHServerEmu 2: Electric Boogaloo

This month we released the second stable release of MHServerEmu - version 0.2.0. This release contains all the backend work we had been working on since March, including, but not limited to:

• General server architecture improvements.

• An overhaul of the serialization system.

• An implementation of navi, locomotion, and physics systems.

• An overhaul of the entity management system.

• An implementation of the inventory system.

• An implementation of the game event system.

• A significantly upgraded version of the area of interest system.

• Most of the backend for the AI system.

We have barely scratched the surface of what is now possible. One significant improvement that happened almost as a side effect of all of this is that now you can see and interact with other players in the game world.

And in just a few days we were able to build a very rough early iteration of the loot system (disclaimer: quantity exaggerated for dramatic purposes, may not match what you see in the final product):

As soon as 0.2.0 was out, we started work on version 0.3.0. Our current tentative target for its release is September 2024, but you can check out all the latest features we are working on early via nightly builds or by building the source code yourself. Now that a significant bulk of the backend work is out of the way, we can focus more on aspects you can actually see in the game. One good example of this you can check out yourself right now in nightly 0.3.0 builds is an early iteration of pets and team-ups that rely on navi, locomotion and AI systems for pathfinding, physically moving around, and being aware that they need to follow their owner respectively.

I Am Running Out of Interesting Puns

This month our implementation of the area of interest (AOI) system received a major upgrade, which literally made visible the results of our work on other systems. Now that it is mostly working, we can dive deeper into the specifics.

First, a quick recap. Marvel Heroes is a server-authoritative game, meaning the entire game simulation (where everything is, what powers everyone is using, how much health everyone has, and so on) runs on the server. The server is the ultimate dungeon master, aware of everything happening to everyone. The client program you are using to play the game also has a simulation of its own that runs in parallel based on the data it receives from the server. However, the data clients receive is just a small slice of the overall server pie, and each client’s slice if referred to as its area of interest.

Putting it into more concrete terms, the AreaOfInterest class in the server code determines what data needs to go to the client it is bound to and keeps track of things the client is already aware of. The data managed by AOI can be separated into two categories: environment (a region with its areas and cells) and entities (game objects that populate the region).

Everything starts with entities. When a client logs into a game server, a Player entity is created for it that gets bound to an AreaOfInterest instance. This entity does not physically exist in the game world and is used to represent the player’s account: what heroes are unlocked, how much of each currency there is, when was the last time this player logged in, and so on. Hero and team-up unlocks are internally represented as “items” held in various hidden inventories, such as PlayerAvatarLibrary and PlayerTeamUpLibrary (see the previous report for more on that).

This player entity is automatically considered by the area of interest it is bound to. Consideration is a process of determining what (if any) interest policies (also referred to as replication channels) a specific entity has in relation to an area of interest. If an area of interest determines that an entity matches one or more interest policies, it starts tracking the entity and notifies the client by sending network messages containing information about this entity. The client uses this information to create a copy of this entity in its local simulation. When an entity loses all of its replication policies, it is removed from the AOI and the client simulation. In addition to player entity creation, consideration can be triggered by other events, such moving around the game world, but more on that later.

In total there are five possible replication policies: Owner, Proximity, Discovery, Party, and Trader. When the player entity is considered by its AOI, it always enters it with the Owner policy. Then, the AOI recursively considers all entities stored in the player’s various inventories, which is how avatars and team-ups owned by the player with all of their equipment enter the AOI. Entities that enter the AOI by being present in the player entity’s inventories also have the Owner interest policy.

With this initialization step done, the server proceeds to put one of the player’s avatars at a specific RegionLocation, which includes a region instance id, coordinates within this region instance, and the initial orientation of the avatar. The AOI scans the environment within a certain radius around this location to determine what cells the client needs to load. The server then sends a message packet that instructs the client to put up a loading screen and load all determined cells. For every loaded cell the client sends a notification message to the server. The server tracks these notifications, and when all requested cells are loaded, it instructs the client to remove the loading screen, and player’s selected avatar enters the world at the required region location.

When the avatar enters world, it and everything within a certain radius is considered for a Proximity policy. Some entities do not get the Proximity policy despite being physically near the player’s avatar in the game world. One good example of this is loot, which is restricted to the player it dropped for until it is picked up. As the player’s avatar moves around the game world, the AOI periodically scans the proximity to determine cells and entities that need to be added or removed.

Here is what it looks like if we artificially reduce the proximity radius:

When entities in proximity are considered, the contents of their inventories are considered in a similar fashion to the player, and there is a set of conditions that determines when an entity stored in an inventory can enter an area of interest. This is what ultimately allows you to see items equipped on nearby players, such as their costumes and artifacts with fancy visual effects, while avoiding the necessity of loading items stored in their stashes like a certain other game.

In some cases when an entity enters proximity and/or satisfies some other condition, it also gains a Discovery policy, which allows it to remain in the client’s simulation even after it leaves proximity. For example, this is how the client can draw map icons for NPCs and waypoints even when they are no longer in proximity.

There are two special cases that have their own replication policies: Party and Trade. What makes them different from the other three is that they are the only cases when player entities belonging to other clients can enter your area of interest. We are still investigating the specifics of them, and we will talk more about this in a future report when we get to work on various social features.

Interest policies play an important role in the serialization process. For example, world entity power collections are omitted unless they have the Proximity policy, and some properties are added or removed based on changing policies. The latter one was the cause of one of the issues we had to solve when implementing team-up spawning. For some reason, the client failed to recognize team-ups as belonging to the current avatar and did not display a green circle indicator under them that should look like this:

As it turned out, the issue was that the property that the client uses to determine this ownership relation, PowerUserOverrideID, is compatible only with Proximity and Trader policies, and it is filtered out in other cases. Because team-ups are initially added to the AOI and serialized to the client with just the Owner policy during initial loading, this property was not included. The solution was to implement handling for the interest policy change event on the server to automatically send newly revealed properties to the client when existing entities in its AOI gain new interest policies.

While there is still some work to do on this system, at this stage it is already capable of performing its most essential operations that allows it to act as a window to what is happening on the server for the client.

Time is of the Essence

Another important area where we have recently had significant advancements is game simulation timing and event scheduling. We first started seriously considering this back in April, and are now at a point where we are approaching client-accuracy.

As we were researching this, we discovered an intricate system of numerous clocks that would fit right in at Dr. Emmett Brown’s lab.

In total there are five clocks that are actively used, and we had to add a sixth one to the mix for compatibility with .NET.

• .NET DateTime - a point in time from January 1, 1 to December 31, 9999. This is the default date time format used by C# that you get from DateTime.Now and DateTime.UtcNow.

• DateTime - the number of microseconds since January 1, 1970. Also known as Unix time.

• CoreGameTime - the number of microseconds since September 22, 2012 09:31:18 GMT+0000. This epoch is not arbitrary: the game’s closed beta began on October 1, 2012, and this point in time must have been when the development team was making final preparations. In a way, this is the game’s true birthday.

• RealGameTime - the number of microseconds in full fixed time frames since September 22, 2012. More on that later.

• Game.CurrentTime - the current time step of the game simulation.

• GameEventScheduler.CurrentTime - the current game simulation time adjusted for the currently executing scheduled event. This is the clock used by most of the gameplay logic. If GameEventScheduler is not available, it falls back to Game.CurrentTime.

Let’s unwrap what is happening here step by step.

During server initialization we query system time with DateTime.UtcNow to get a timestamp of the initialization time. For performance and accuracy reasons, rather than querying system time each time the game wants to know what time it is, we create and start a Stopwatch class instance when we query the initialization timestamp. When time is requested, we add elapsed time from the stopwatch to our timestamp and convert it to DateTime or CoreGameTime. With that we have half of our required clocks taken care of.

RealGameTime is represented using a class called FixedQuantumGameTime. Behind this sci-fi sounding name we have basically a less accurate version of CoreGameTime that advances in fixed intervals, which in our case are 50 ms.

When the game does the UpdateFixedTime() stage of the update loop, which handles time-sensitive processing such as physics and timers, it synchronizes the value of RealGameTime by calling the FixedQuantumGameTime.UpdateToNow() method that does something along these lines:

// Get current CoreGameTime and time step length.
TimeSpan gameTime = Clock.GameTime;
TimeSpan quantumSize = TimeSpan.FromMilliseconds(50);

// Calculate the total number of steps.
// Because Ticks are integers, we lose the remainder
// of the division and get a nice round number.
long numTimeQuantums = gameTime.Ticks / quantumSize.Ticks;

// Get a new TimeSpan representing the number of full steps.
TimeSpan realGameTime = quantumSize * numTimeQuantums

The game then advances its CurrentTime in 50 ms intervals until it catches up to RealGameTime. For every time its clock advances, the game calls DoFixedTimeUpdate() once. When everything is going smoothly and there are no time-consuming tasks running, like region generation, an UpdateFixedTime() call should do only a single DoFixedTimeUpdate(). To keep the simulation from being stuck in an endless loop in situations where it for some reason cannot keep up, there is an additional check that breaks the loop when it exceeds the expected frame time of 50 ms.

// _gameTimer is a Stopwatch instance that starts with the game.
TimeSpan updateStartTime = _gameTimer.Elapsed;
while (_currentGameTime + FixedTimeBetweenUpdates <= RealGameTime)
{
    _currentGameTime += FixedTimeBetweenUpdates;

    DoFixedTimeUpdate();

    // Bail out if we have exceeded the frame budget
    if (_gameTimer.Elapsed - updateStartTime > FixedTimeBetweenUpdates)
        break;
}

Everything up until this point has been relatively straightforward, but now the real time shenanigans begin. During DoFixedTimeUpdate() the reins are partially handed over to the GameEventScheduler:

private void DoFixedTimeUpdate()
{
    // Current simulation time is passed as an argument
    GameEventScheduler.TriggerEvents(_currentGameTime);
    // Everything else
}

In fact, GameEventScheduler’s clock has priority over the game’s when current time is requested by various systems:

public TimeSpan CurrentTime { get => GameEventScheduler != null ? GameEventScheduler.CurrentTime : _currentGameTime; }

So what does EventScheduler do? Essentially, it allows the game to set up timers and trigger actions when they expire. You provide it with with a TimeSpan representing a delay before something should happen and an object representing the callback that needs to be executed, and it does everything else.

Believe it or not, this system appears to be an evolution of a similar system from Diablo II. Take a look at this code snippet from the D2MOO decompilation project:

// AI think delay setup
int32_t nAiDelay = 0;
if (pGame->nGameType || pGame->dwGameType)
{
    // Get delay for the current difficulty from MonStats.txt
    nAiDelay = pMonStatsTxtRecord->nAIdel[pGame->nDifficulty];
}
else
{
    // Fall back to normal difficulty
    nAiDelay = pMonStatsTxtRecord->nAIdel[0];
}

// Fall back to the default delay value
if (nAiDelay <= 0)
{
    nAiDelay = 15;
}

// Schedule the next think event
EVENT_SetEvent(pGame, pModeChange->pUnit, UNITEVENTCALLBACK_AITHINK, nAiDelay + pGame->dwGameFrame, 0, 0);

Diablo II’s timing is completely frame-based with the game running at a constant framerate of 25 Hz. The code in this example retrieves the monster AI think delay value from a data file (MonStats.txt) and schedules a think event. At 25 FPS each frame is going to take 1000 / 25 = 40 ms, meaning this delay will take 15 * 40 = 600 ms. At Nightmare and Hell difficulty modes this delay is 14 * 40 = 560 ms and 13 * 40 = 520 ms respectively.

And here is reverse engineered code that does the equivalent in Marvel Heroes:

public void Think()
{
    // ...
    float thinkTime = 500; // slow think 
    if (TargetEntity != null || AssistedEntity != null)
        thinkTime = 100; // fast think
    ScheduleAIThinkEvent(TimeSpan.FromMilliseconds(thinkTime) * Game.Random.NextFloat(0.9f, 1.1f));
    // ...
}

public void ScheduleAIThinkEvent(TimeSpan timeOffset)
{
    // Various checks and additional variation
    // for the offset happening here are omitted.

    eventScheduler.ScheduleEvent(_thinkEvent, nextThinkTimeOffset, _pendingEvents);
    _thinkEvent.Get().OwnerController = this;
}

Diablo II’s units are now called entities, Excel .txt files became prototypes, and instead of the number of frames we provide a TimeSpan as an argument for scheduling an event. The “slow thinking mode” is pretty much equivalent to the thinking rate from Diablo II. And this is not where similarities end: internally, EventScheduler still operates based on frames, just like Diablo II.

All scheduled events are grouped by “buckets”, with each bucket representing a frame. When an event is scheduled, it is put into a bucket based on the current time and requested delay, and its precise fire time is recorded.

When the TriggerEvents() method is called from DoFixedTimeUpdate(), the event scheduler advances its clock in fixed time steps until it catches up to the _currentGameTime that was passed as an argument, and each time it advances it executes all events in the bucket corresponding to the frame. Here is what a simplified version of this code looks like:

// Determine time window
long startFrame = CurrentTime.CalcNumTimeQuantums(_quantumSize);
long endFrame = updateEndTime.CalcNumTimeQuantums(_quantumSize);

// Process all frames that are within our time window
for (long i = startFrame; i <= endFrame; i++)
{
    foreach (ScheduledEvent @event in _buckets[i])
    {
        // Set event scheduler's time to the precise event fire time
        CurrentTime = @event.FireTime;

        // Invalidate event
        _scheduledEvents.Remove(@event);
        @event.EventGroupNode?.Remove();
        @event.InvalidatePointers();

        // Run event callback
        @event.OnTriggered();
    }
}

// Synchronize time with the game
CurrentTime = currentGameTime;

Before the event scheduler triggers an event, it sets its clock to the precise time when the event is supposed to be fired. And because Game.CurrentTime returns the value of GameEventScheduler.CurrentTime, any game logic that runs as a result of the event callback is going to have precise time despite the simulation advancing in 50 ms steps.

But here is the crazy thing: as far as I can tell, events within their frame buckets are not sorted by fire time. Therefore, it is possible for the time to go backwards, although only within the confines of a single frame. Which in a way makes sense: events happening within the same frame are batched together and happen “simultaneously”, so the execution order here is not critical. The main potential problem would be inconsistent timing due to an event callback potentially scheduling another event, but because time is always set to the precise fire time, it’s going to remain consistent.

RIght now we have most of this system working, with the exception of the bucket management system. As a temporary solution we are storing all events in a single collection that we iterate to determine the events that would go in the bucket we would be processing, which is not ideal for performance, but it does the job well enough for now. The API for the system is pretty much done, and we can worry about optimizing internal implementation later.

And this is how time in Marvel Heroes works.

Finding a Path Forward

AlexBond is back again this month to talk about his work on pathfinding and AI.

---

Hello, it’s AlexBond again. In this report I would like to talk about how AI works and the NaviPath generation process.

AIController

For an agent’s AI to work, the agent needs to enter the simulation using SetSimulated(), and its AI controller needs to be activated. (Editor’s note: “agent” is the term the game uses to refer to world entities that can interact with the game world, such as avatars, enemies, team-ups, and so on).

AI controller activation happens when an agent enters the game world, in the OnEnteredWorld() function: if the agent has a defined BehaviorProfile, an AIController instance is created. AIController consists of three main parts:

• Brain - a behavior profile for the ProceduralAI system.

• Senses - a class for determining potential allies and enemies that scans everyone every second in the defined AggroRange.

• Blackboard - AI’s memory where temporary state is stored in the form of a PropertyCollection, as well as various vectors.

The main function of a controller is Think(). To keep server load in check, this function runs via a scheduled event every 90-110 ms in the “fast” thinking mode and every 450-500 ms in the “slow” thinking mode. When it runs, it activates the Brain and runs commands defined in the AI profile. AI profiles include some state logic and defines behavior templates for each state.

Let’s take a look at a concrete example - the think function for ProceduralProfileVanityPetPrototype:

public override void Think(AIController ownerController)
{
    // Guard checks omitted
    ProceduralAI proceduralAI = ownerController.Brain;
    Agent agent = ownerController.Agent;
    WorldEntity master = ownerController.AssistedEntity;
    Game game = agent.Game;

    if (master != null && master.IsInWorld)
    {
        float distanceToMasterSq = Vector3.DistanceSquared2D(agent.RegionLocation.Position, master.RegionLocation.Position);
        if (distanceToMasterSq > MaxDistToMasterBeforeTeleportSq)
        {
            // Teleport to master
            HandleContext(proceduralAI, ownerController, TeleportToMasterIfTooFarAway);
        }
    }

    // Move normally
    HandleMovementContext(proceduralAI, ownerController, agent.Locomotor, PetFollow, false, out _);
}

First, the pet determines its master (AssistedEntity) and the distance between them. If this distance exceeds the defined value, the pet teleports using HandleContext(). Then movement is initiated using HandleMovementContext().

HandleMovementContext() sets the state to MoveTo, which consists of four stages:

• Validate

• Start

• Update

• End

The agent then receives a command based on the settings defined in the ContextPrototype. In our vanity pet example this command is simply generating a path to AssistedEntity.

GeneratePath

Path generation begins inside the Locomotor class. First, it disables influence points for owner (the pet) and other (the avatar) by calling the DisableNavigationInfluence() method. It then proceeds to the generation process itself - GeneratePathInternal().

This process consists of three main steps:

• GeneratePathStep() - we scan all NaviTriangle instances near the startTriangle until we find our destination - goalTriangle. All steps are recorded in genPathState.

• FunnelStep() - a hard to understand algorithm, the goal of which is to remove unnecessary NaviPoint instances and determine NaviSide - the side to steer to avoid collision with an object (either left or right). The radius of the node to steer around is determined by summing the radiuses of the owner (the pet) and the influenceRadius - the radius of the object bound to the NaviPoint.

• CalcAccurateDistance() - now that we have a path, we calculate its actual length taking into account all necessary steering and picking the shortest sides.

To illustrate this process, I have prepared two examples of path generation:

As you an see, there are two entities between the pet and the avatar: S.T.A.S.H. and Maria Hill.

Now let’s take a look at a more involved example:

In this case we have obstacles in the form of walls. The radiuses of nodes to steer around will be equal to the pet’s. Three paths are generated, and the shortest one is picked.

Finding and fixing bugs in implementations of these algorithms took me a week. I even had to implement SVG export for the navi system to visualize what was happening. In the end, all issues were solved, and now we have pets and team-ups working in the server emulator.

As you run around with them, keep in mind that every 200 ms they perform complex calculations to find their path to you. In addition to that, Locomotor has a repath feature that checks and potentially rebuilds the path every 250 ms in case new objects appear in the way.

Now you should have a better understanding of how AI works. Although team-ups currently do not attack, they scan for targets every second, and when we enable these targets, combat will begin!

---

It is time for us to get back to coding. We hope you all are going to join us again in July for a special one year anniversary report!