Here Be Monsters – Message broker that links all things

In our MMORPG title Here Be Mon­sters, we offer the play­ers a vir­tu­al world to explore where they can vis­it towns and spots; for­age fruits and gath­er insects and flow­ers; tend to farms and ani­mals in their home­steads; make in-game bud­dies and help each oth­er out; craft new items using things they find in their trav­els; catch and cure mon­sters cor­rupt­ed by the plague; help out trou­bled NPCs and aid the Min­istry of Mon­sters in its strug­gle against the cor­rup­tion, and much more!

All and all, there are close to a hun­dred dis­tinct actions that can be per­formed in the game and more are added as the game expands. At the very cen­tre of every­thing you do in the game, is a quest and achieve­ments sys­tem that can tap into all these actions and reward you once you’ve com­plet­ed a series of require­ments.

 

The Challenge

How­ev­er, such a sys­tem is com­pli­cat­ed by the snow­ball effect that can occur fol­low­ing any num­ber of actions. The fol­low­ing ani­mat­ed GIF paints an accu­rate pic­ture of a cyclic set of chain reac­tions that can occurred fol­low­ing a sim­ple action:

Chain

In this instance,

  1. catch­ing a Gnome awards EXP, gold and occa­sion­al­ly loot drops, in addi­tion to ful­fill­ing any require­ment for catch­ing a gnome;
  2. get­ting the item as loot ful­fils any require­ments for you to acquire that item;
  3. the EXP and gold award­ed to the play­er can ful­fil require­ments for acquir­ing cer­tain amounts of EXP or gold respec­tive;
  4. the EXP can allow the play­er to lev­el up;
  5. lev­el­ling up can then ful­fil a require­ment for reach­ing a cer­tain lev­el as well as unlock­ing new quests that were pre­vi­ous­ly lev­el-locked;
  6. lev­el­ling up can also award you with items and gold and the cycle con­tin­ues;
  7. if all the require­ments for a quest are ful­filled then the quest is com­plete;
  8. com­plet­ing a quest will in turn yield fur­ther rewards of EXP, gold and items and restarts the cycle;
  9. com­plet­ing a quest can also unlock fol­low-up quests as well as ful­fill­ing quest-com­ple­tion require­ments.

 

The same require­ments sys­tem is also in place for achieve­ments, which rep­re­sent longer term goals for play­ers to play for (e.g. catch 500 spir­it mon­sters). The achieve­ment and quest sys­tems are co-depen­dent and feeds into each oth­er, many of the mile­stone achieve­ments we cur­rent­ly have in the game depend upon quests to be com­plet­ed:

image

Tech­ni­cal­ly there is a ‘remote’ pos­si­bil­i­ty of dead­locks but right now it exists only as a pos­si­bil­i­ty since new quest/achievement con­tents are gen­er­al­ly played through many many times by many peo­ple involved in the con­tent gen­er­a­tion process to ensure that they are fun, achiev­able and that at no point will the play­ers be left in a state of lim­bo.

 

This cycle of chain reac­tions intro­duces some inter­est­ing imple­men­ta­tion chal­lenges.

For starters, the dif­fer­ent events in the cycle (lev­el­ling up, catch­ing a mon­ster, com­plet­ing a quest, etc.) are han­dled and trig­gered from dif­fer­ent abstrac­tion lay­ers that are loose­ly cou­pled togeth­er, e.g.

  • Lev­el con­troller encap­su­lates all log­ic relat­ed to award­ing EXP and lev­el­ling up.
  • Trap­ping con­troller encap­su­lates all log­ic relat­ed to mon­ster catch­ing.
  • Quest con­troller encap­su­lates all log­ic relat­ed to quest trig­ger­ing, pro­gress­ing and com­ple­tions.
  • Require­ment con­troller encap­su­lates all log­ic relat­ed to man­ag­ing the progress of require­ments.
  • and many more..

Func­tion­al­ly, the con­trollers form a nat­ur­al hier­ar­chy where­by high­er-order con­trollers (such as the trap­ping con­troller) depend upon low­er-order con­trollers (such as lev­el con­troller) because they need to be able award play­ers with EXP and items etc. How­ev­er, in order to facil­i­tate the desired flow, the­o­ret­i­cal­ly all con­trollers will need to be able to lis­ten and react to events trig­gered by all oth­er con­trollers..

 

To make mat­ter worse, there are also non-func­tion­al require­ments which also requires the abil­i­ty to tap into this rich and con­tin­u­ous stream of events, such as:

  • Ana­lyt­ics track­ing – every action the play­er takes in the game is record­ed along with the con­text in which they occurred (e.g. caught a gnome with the trap X, acquired item Z, com­plet­ed quest Q, etc.)
  • 3rd par­ty report­ing – noti­fy ad part­ners on key mile­stones to help them track and mon­i­tor the effec­tive­ness of dif­fer­ent ad cam­paigns
  • etc..

 

For the com­po­nents that process this stream of events, we also want­ed to make sure that our imple­men­ta­tion is:

  1. strong­ly cohe­sive – code that are deal­ing with a par­tic­u­lar fea­ture (quests, ana­lyt­ics track­ing, com­mu­ni­ty goals, etc.) are encap­su­lat­ed with­in the same mod­ule
  2. loose­ly cou­pled – code that deals with dif­fer­ent fea­tures should not be direct­ly depen­dent on each oth­er and where pos­si­ble they should exist com­plete­ly inde­pen­dent­ly

Since the events are gen­er­at­ed and processed with­in the con­text of one HTTP request (the ini­tial action from the user), the stream also have a life­time that is scoped to the HTTP request itself.

 

And final­ly, in terms of per­for­mance, whilst it’s not a laten­cy crit­i­cal sys­tem (gen­er­al­ly a round-trip laten­cy of sub-1s is accept­able) we gen­er­al­ly aim for a response time (between request reach­ing the serv­er and the serv­er send­ing back a response) of 50ms to ensure a good round-trip laten­cy from the user’s per­spec­tive.

In prac­tice though, the last-mile laten­cy (from your ISP to you) has proven to be the most sig­nif­i­cant fac­tor in deter­min­ing the round-trip laten­cy.

 

The Solution

After con­sid­er­ing sev­er­al approach­es:

  • Vanil­la .Net events
  • Reac­tive Exten­sions (Rx)
  • CEP plat­forms such as Esper or StreamIn­sight

we decid­ed to go with a tai­lor-made solu­tion for the prob­lem at hand.

In this solu­tion we intro­duced two abstrac­tions:

  • Facts – which are spe­cial events for the pur­pose of this par­tic­u­lar sys­tem, we call them facts in order to dis­tin­guish them from the events we record for ana­lyt­ics pur­pose already. A fact con­tains infor­ma­tion about an action or a state change as well as the con­text in which it occurred, e.g. a Caught­Mon­ster fact would con­tain infor­ma­tion about the mon­ster, the trap, the bait used, where in the world the action occurred, as well as the rewards the play­er received.
  • Fact Proces­sor – a com­po­nent which process­es a fact.

 

As a request (e.g. to check our trap to see if we’ve caught a mon­ster) comes in the des­ig­nat­ed request han­dler will first per­form all the rel­e­vant game log­ic for that par­tic­u­lar request, accu­mu­lat­ing facts along the way from the dif­fer­ent abstrac­tion lay­ers that have to work togeth­er to process this request.

At the end of the core game log­ic, the accu­mu­lat­ed facts is then for­ward­ed to each of the con­fig­ured fact proces­sors in turn. The fact proces­sors might choose to process or ignore each of the facts.

In choos­ing to process a fact the fact proces­sors can cause state changes or oth­er inter­est­ing events to occur which results in fol­low-up facts to be added to the queue.

FactProcessing

 

The sys­tem described above has the ben­e­fits of being:

  • Sim­ple – easy to under­stand and rea­son with, easy to mod­u­larise, no com­plex orches­tra­tion log­ic or spaghet­ti code.
  • Flex­i­ble – easy to change infor­ma­tion cap­tured by facts and pro­cess­ing log­ic in fact proces­sors
  • Exten­si­ble – easy to add new facts and/or fact proces­sors into the sys­tem

The one big down­side being that for the sys­tem to work it requires many types of facts which means it could poten­tial­ly add to your main­te­nance over­head and requires lots of boil­er­plate class set­up.

 

To address these poten­tial issues, we turned to F#’s dis­crim­i­nat­ed unions over stan­dard .Net class­es for its suc­cinct­ness. For a small num­ber of facts you can have some­thing as sim­ple as the fol­low­ing:

image

How­ev­er, as we men­tioned ear­li­er, there are a lot of dif­fer­ent actions that can be per­formed in Here Be Mon­sters and there­fore many facts will be required to track those actions as well as the state changes that occur dur­ing those actions. The sim­ple approach above is not a scal­able solu­tion in this case.

Instead, you could use a com­bi­na­tion of mark­er inter­face and pat­tern match­ing to split the facts into a num­ber of spe­cial­ized dis­crim­i­nat­ed union types.

image

Update  2014/07/28 : thank you to @johnazariah for bring­ing this up, the rea­son for choos­ing to use a mark­er inter­face rather than a hier­ar­chi­cal dis­crim­i­nat­ed union in this case is because it makes interop with C# eas­i­er.

In C#, you can cre­ate the StateChangeFacts.LevelUp union clause above using the com­pil­er gen­er­at­ed StateChangeFacts.NewLevelUp sta­t­ic method but it’s not as read­able as the equiv­a­lent F# code.

With a hier­ar­chi­cal DU the code will be even less read­able, 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 gen­er­ate a response back to the client to report all the changes to the player’s state as a result of this request. To sim­pli­fy the process of track­ing these state changes and to keep the code­base main­tain­able we make use of a Con­text object for the cur­rent request (sim­i­lar to HttpContext.Current) and make sure that each state change (e.g. EXP, ener­gy, etc.) occurs in only one place in the code­base and that change is tracked at the point where it occurs.

At the end of each request, all the changes that has been col­lect­ed is then copied from the cur­rent Con­text object onto the response object if it imple­ments the rel­e­vant inter­face – for exam­ple, all the quest-relat­ed state changes are copied onto a response object if it imple­ments the IHasQuestChanges inter­face.

 

Related Posts

F# – use Dis­crim­i­nat­ed Unions instead of Class­es

F# – extend­ing Dis­crim­i­nat­ed Unions using mark­er inter­faces