In our MMORPG title Here Be Monsters, we offer the players a virtual world to explore where they can visit towns and spots; forage fruits and gather insects and flowers; tend to farms and animals in their homesteads; make in-game buddies and help each other out; craft new items using things they find in their travels; catch and cure monsters corrupted by the plague; help out troubled NPCs and aid the Ministry of Monsters in its struggle against the corruption, and much more!
All and all, there are close to a hundred distinct actions that can be performed in the game and more are added as the game expands. At the very centre of everything you do in the game, is a quest and achievements system that can tap into all these actions and reward you once you’ve completed a series of requirements.
However, such a system is complicated by the snowball effect that can occur following any number of actions. The following animated GIF paints an accurate picture of a cyclic set of chain reactions that can occurred following a simple action:
In this instance,
- catching a Gnome awards EXP, gold and occasionally loot drops, in addition to fulfilling any requirement for catching a gnome;
- getting the item as loot fulfils any requirements for you to acquire that item;
- the EXP and gold awarded to the player can fulfil requirements for acquiring certain amounts of EXP or gold respective;
- the EXP can allow the player to level up;
- levelling up can then fulfil a requirement for reaching a certain level as well as unlocking new quests that were previously level-locked;
- levelling up can also award you with items and gold and the cycle continues;
- if all the requirements for a quest are fulfilled then the quest is complete;
- completing a quest will in turn yield further rewards of EXP, gold and items and restarts the cycle;
- completing a quest can also unlock follow-up quests as well as fulfilling quest-completion requirements.
The same requirements system is also in place for achievements, which represent longer term goals for players to play for (e.g. catch 500 spirit monsters). The achievement and quest systems are co-dependent and feeds into each other, many of the milestone achievements we currently have in the game depend upon quests to be completed:
Technically there is a ‘remote’ possibility of deadlocks but right now it exists only as a possibility since new quest/achievement contents are generally played through many many times by many people involved in the content generation process to ensure that they are fun, achievable and that at no point will the players be left in a state of limbo.
This cycle of chain reactions introduces some interesting implementation challenges.
For starters, the different events in the cycle (levelling up, catching a monster, completing a quest, etc.) are handled and triggered from different abstraction layers that are loosely coupled together, e.g.
- Level controller encapsulates all logic related to awarding EXP and levelling up.
- Trapping controller encapsulates all logic related to monster catching.
- Quest controller encapsulates all logic related to quest triggering, progressing and completions.
- Requirement controller encapsulates all logic related to managing the progress of requirements.
- and many more..
Functionally, the controllers form a natural hierarchy whereby higher-order controllers (such as the trapping controller) depend upon lower-order controllers (such as level controller) because they need to be able award players with EXP and items etc. However, in order to facilitate the desired flow, theoretically all controllers will need to be able to listen and react to events triggered by all other controllers..
To make matter worse, there are also non-functional requirements which also requires the ability to tap into this rich and continuous stream of events, such as:
- Analytics tracking – every action the player takes in the game is recorded along with the context in which they occurred (e.g. caught a gnome with the trap X, acquired item Z, completed quest Q, etc.)
- 3rd party reporting – notify ad partners on key milestones to help them track and monitor the effectiveness of different ad campaigns
For the components that process this stream of events, we also wanted to make sure that our implementation is:
- strongly cohesive – code that are dealing with a particular feature (quests, analytics tracking, community goals, etc.) are encapsulated within the same module
- loosely coupled – code that deals with different features should not be directly dependent on each other and where possible they should exist completely independently
Since the events are generated and processed within the context of one HTTP request (the initial action from the user), the stream also have a lifetime that is scoped to the HTTP request itself.
And finally, in terms of performance, whilst it’s not a latency critical system (generally a round-trip latency of sub-1s is acceptable) we generally aim for a response time (between request reaching the server and the server sending back a response) of 50ms to ensure a good round-trip latency from the user’s perspective.
In practice though, the last-mile latency (from your ISP to you) has proven to be the most significant factor in determining the round-trip latency.
After considering several approaches:
- Vanilla .Net events
- Reactive Extensions (Rx)
- CEP platforms such as Esper or StreamInsight
we decided to go with a tailor-made solution for the problem at hand.
In this solution we introduced two abstractions:
- Facts – which are special events for the purpose of this particular system, we call them facts in order to distinguish them from the events we record for analytics purpose already. A fact contains information about an action or a state change as well as the context in which it occurred, e.g. a CaughtMonster fact would contain information about the monster, the trap, the bait used, where in the world the action occurred, as well as the rewards the player received.
- Fact Processor – a component which processes a fact.
As a request (e.g. to check our trap to see if we’ve caught a monster) comes in the designated request handler will first perform all the relevant game logic for that particular request, accumulating facts along the way from the different abstraction layers that have to work together to process this request.
At the end of the core game logic, the accumulated facts is then forwarded to each of the configured fact processors in turn. The fact processors might choose to process or ignore each of the facts.
In choosing to process a fact the fact processors can cause state changes or other interesting events to occur which results in follow-up facts to be added to the queue.
The system described above has the benefits of being:
- Simple – easy to understand and reason with, easy to modularise, no complex orchestration logic or spaghetti code.
- Flexible – easy to change information captured by facts and processing logic in fact processors
- Extensible – easy to add new facts and/or fact processors into the system
The one big downside being that for the system to work it requires many types of facts which means it could potentially add to your maintenance overhead and requires lots of boilerplate class setup.
To address these potential issues, we turned to F#’s discriminated unions over standard .Net classes for its succinctness. For a small number of facts you can have something as simple as the following:
However, as we mentioned earlier, there are a lot of different actions that can be performed in Here Be Monsters and therefore many facts will be required to track those actions as well as the state changes that occur during those actions. The simple approach above is not a scalable solution in this case.
Instead, you could use a combination of marker interface and pattern matching to split the facts into a number of specialized discriminated union types.
Update 2014/07/28 : thank you to @johnazariah for bringing this up, the reason for choosing to use a marker interface rather than a hierarchical discriminated union in this case is because it makes interop with C# easier.
In C#, you can create the StateChangeFacts.LevelUp union clause above using the compiler generated StateChangeFacts.NewLevelUp static method but it’s not as readable as the equivalent F# code.
With a hierarchical DU the code will be even less readable, e.g. Fact.NewStateChange(StateChangeFacts.NewLevelUp(…))
To wrap things up, once all the facts are processed and we have dealt with the request in full we need to generate a response back to the client to report all the changes to the player’s state as a result of this request. To simplify the process of tracking these state changes and to keep the codebase maintainable we make use of a Context object for the current request (similar to HttpContext.Current) and make sure that each state change (e.g. EXP, energy, etc.) occurs in only one place in the codebase and that change is tracked at the point where it occurs.
At the end of each request, all the changes that has been collected is then copied from the current Context object onto the response object if it implements the relevant interface – for example, all the quest-related state changes are copied onto a response object if it implements the IHasQuestChanges interface.
F# – use Discriminated Unions instead of Classes
F# – extending Discriminated Unions using marker interfaces