Modelling game economy with Neo4j

In Here Be Mon­sters, we have a MMORPG that is con­tent-heavy with over:

  • 5000 items
  • 800 recipes
  • 500 loca­tions
  • 1500 quests

and since the con­tents are high­ly con­nect­ed, it makes bal­anc­ing the game a rather inter­est­ing and chal­leng­ing prob­lem for our small team behind the project.

The Challenge

Con­sid­er a sim­ple exam­ple involv­ing the Cam­ou­flage Trap, which is one of the very first traps you’ll make. It’s made from a num­ber of ingre­di­ents, each can be:

  • found in the cer­tain parts of the world
  • pur­chased at shops
  • award­ed for com­plet­ing quests/achievements
  • craft­ed using oth­er ingre­di­ents

Now, sup­pose you want to raise the price of basic ingre­di­ents such as Water, that increase needs to prop­a­gate all the way through the chain.

Fur­ther­more, when you con­sid­er how many items are made from Water, and how many more items are made from those items.

There’s a huge knock-on effect here. Fail­ing to address these knock-on effects will cre­ate arbi­trage oppor­tu­ni­ties in your econ­o­my for play­ers to exploit. They will be able to mine coins by buy­ing and sell­ing items and will there­fore have less need to make real-mon­ey pur­chas­es with us.

As a game design­er, when­ev­er you want to make a change you are faced with this huge uncer­tain­ty because of the hid­den knock-on effects that you don’t see.

It’s a com­plex­i­ty that we have to man­age, but man­ag­ing this com­plex­i­ty by hand is:

  • labo­ri­ous — involv­ing many iter­a­tions of tri­al and error, and like­ly repeat­ed each time new con­tents are added
  • slow
  • error prone
  • sub­jec­tive — what ‘feels’ right can vary great­ly from per­son to per­son

Instead, we opt­ed for a more auto­mat­ed process where­by every item’s intrin­sic val­ue in the game can be eval­u­at­ed based on the val­ues of its inputs (e.g. baits for mon­sters, ingre­di­ents for craft­ed items, etc.). The amount of time involved, and your chance of suc­cess is also tak­en into account. We can then use the intrin­sic val­ue of an item to dri­ve or quan­ti­fy oth­er less tan­gi­ble aspects of the game’s mod­el.

This is where Neo4j comes in.

Hello, Neo

One of the main chal­lenges that came up in our effort to auto­mate the eco­nom­ic bal­anc­ing was to under­stand the com­plex rela­tion­ships between items, quests, achieve­ments, as well as loca­tions and activ­i­ties that can be per­formed against/with spe­cif­ic items at spe­cif­ic loca­tions.

Take Big­foot as an exam­ple, from his almanac page in the game:

We can see that to catch the Big­foot you need to con­sid­er:

  • loca­tion — he’s only avail­able in cer­tain parts of the world
  • bait — to lure him out you need the Allur­ing Goat which gives you a rough­ly 4 in 7 chance of see­ing the mon­ster
  • trap — you need a trap strong enough to hold him after you’ve man­aged to lure him out, the Mus­ket-teer Trap has a 5 in 7 chance of suc­cess
  • loot — upon a suc­cess­ful catch, Big­foot occa­sion­al­ly drops Big­foot Toe­nail Clip­pings as loot, which you might need in future quests or as ingre­di­ent to make oth­er items

We can mod­el all the infor­ma­tion we see on this screen as a graph in Neo4j:

Addi­tion­al­ly, each node and edge can have an arbi­trary set of prop­er­ties.

For instance, Big­foot and the Mus­ket-teer Trap will have their stats. The lootsrela­tion­ship that exists between Big­foot and his loot will also spec­i­fy the chance of him drop­ping the loot.

Look­ing beyond the imme­di­ate con­nec­tions to Big­foot, the Allur­ing Goat and Mus­ket-teer Trap each have numer­ous con­nec­tions of their own.

To make the Allur­ing Goat, you need to gath­er:

  • Hon­ey, which you need to build a Bee Hive in your home­stead and har­vest from it;
  • Goat, which you can buy from ani­mal traders in cities around the world such asLon­don and Nan­Jing;
  • Gold­en Hair, which is a loot dropped by Blonde Mer­maid, Dan­de­lion Pix­ie and Blonde Selkie;

This dia­gram illus­trates the high­ly con­nect­ed and com­plex nature of the data we’re deal­ing with — the result of us mak­ing a game where every­thing you can do and every item you find has a pur­pose and can be used for some­thing else.

It is also by no means an uncon­nect­ed sub­set of the over­all graph. For sim­plic­i­ty sake I have omit­ted many types of rela­tion­ships and con­nect­ed nodes.

Visu­al­iz­ing the 8,000+ nodes and around 40,000+ edges in Gephi, where the colour and size of the nodes rep­re­sent the num­ber of con­nec­tions they have, this is what the inter­nal data mod­el for Here Be Mon­sters look like:

As you can see, the degree of con­nect­ed­ness varies great­ly. For com­mon low-lev­el mon­sters such as Sylph, Sprig­gan, Sprite and Sala­man­der, they are each con­nect­ed to no less than 300 loca­tions, traps and items.

Sim­i­lar­ly, for com­mon ingre­di­ents such as Salt, it can be found through many items (e.g. most fish drop Sea­weed and Salt as loot when you catch them) and is used in many recipes — Pas­try, Piz­za Base, Ketchup to name a few.

With the inter­nal data mod­el cap­tured as a graph in Neo4j, we were able to ask some inter­est­ing ques­tions that would have been dif­fi­cult or impos­si­ble to answer oth­er­wise.

To give you a few exam­ples.

Impact Analysis

In the ear­li­er pric­ing exam­ple with Water and Cam­ou­flage Trap, the key chal­lenge is to be able to under­stand the impact of change. This is a very sim­i­lar prob­lem to the ones you face in deriv­a­tive pric­ing in Finance.

If you take White Bread as an exam­ple, to work out the blast radius of a price change, let’s look at the rela­tion­ships that exist between an item and a recipe.

To find all the items that are made from White Bread, direct­ly or indi­rect­ly, we can run the fol­low­ing Cypher (which is the built-in query lan­guage for Neo4j) query against our Neo4j data­base:

MATCH
(wb:BaseItem { Name:“White Bread”})
-[rel:CRAFTS | IS_USED_IN*1..]
->(i:BaseItem)
RETURN i, rel, wb

Cou­ple of things to note from this query.

  • notice how we are basi­cal­ly pat­tern match­ing against the graph using the pat­tern node-[relationship]->node?
  • we cap­ture the nodes and rela­tion­ships into vari­ables wb, i and rel so we can return them from the query;
  • we can option­al­ly fil­ter the nodes by type, e.g. (i:BaseItem) will only match against nodes that are of type BaseItem;
  • to iden­ti­fy White Bread, we also fil­ter one of the nodes by the val­ue of its prop­er­ties, in this case the node wb must have a Name prop­er­ty with the val­ue of White Bread;
  • we can use OR seman­tic when fil­ter­ing on rela­tion­ship types, here we’re look­ing for rela­tion­ships of type CRAFTS or IS_USED_IN;
  • for the pat­tern to work, there must exist 1 or more instance of such rela­tion­ships between any two nodes, hence the car­di­nal­i­ty of *1..

Run­ning this query yields the fol­low­ing result, where the pur­ple nodes are items and red nodes are recipes.

From this graph we can see that White Bread is used direct­ly in 10 recipes, and then indi­rect­ly (virtue of being an ingre­di­ent for mak­ing Sausage) in a fur­ther 5. If we were to change the price of White Bread, all 15 of these items will need to have their prices adjust­ed based on the num­ber of White Bread required to make them.

For exam­ple, if it takes 2 pieces of White Bread to make 1 Sausage and 2 Sausage to make a Full Eng­lish Break­fast, then the change to White Bread’s price would need to be mul­ti­plied by 4 when applied to Full Eng­lish Break­fast.

Scarcity Analysis

Not all items can be priced as deriv­a­tives of oth­ers. Some need to be priced based on their scarci­ty in the world, such as the fruits that you can for­age from fruit trees you find on your trav­els.

To find out how scarce­ly avail­able Duri­an and Drag­on­fruit is, we can use the fol­low­ing Cypher query:

MATCH
(fruit)<-[:FORAGES]-(tree)-[:EXISTS_IN]->(spot)
WHERE
fruit.Name=‘Durian’ OR fruit.Name=‘Dragonfruit’
RETURN fruit, tree, spot

Again, we’re sim­ply pat­tern match­ing against our graph using the pat­tern node<-[relationship1]-node-[relationship2]->node. The expres­sive pow­er of Cypher lies in the abil­i­ty to take our rela­tion­ship dia­gram above and trans­late it like-for-like into an exe­cutable query.

You might also noticed that I’m not fil­ter­ing any of the nodes by type here. This is because I know those rela­tion­ships exist only between the spec­i­fied types of nodes, hence it’s safe for me to omit them.

Imme­di­ate­ly, you can see that Drag­on­fruit Tree is much more read­i­ly avail­able in the world com­pared to Duri­an Tree. How­ev­er, you still need to con­sid­er:

  • the num­ber of trees at each loca­tion, which you can find out from the EXISTS_IN rela­tion­ship
  • the num­ber of fruits you get by for­ag­ing the tree, which you can find out from the FORAGES rela­tion­ship

Tak­ing all these fac­tors into account, we can set prices for Duri­an and Drag­on­fruit which reflects their scarci­ty in the world.

Quest Progression

Some quests require spe­cif­ic items to com­plete. For instance, an NPC might ask you to fetch an item from Bob in Cam­bridge, or find some fea­ture under a rock some­where, or catch a Grif­fin and get a Grif­fin Egg as loot.

On the oth­er hand, com­plet­ing a quest can some­times award you items as well. If the quest is part of a quest line then you will also unlock fol­low-up quests too, so there is a self-recur­sive rela­tion­ship there.

To answer ques­tions such as

What comes after the Year of the Horse quest?

you can use a sim­ple Cypher query like the one below.

MATCH
(q1:Quest { Name: “Year of the Horse” })
-[:UNLOCKS]
->(q2:Quest)
RETURN q1, q2

From the result­ing graph, you can quick­ly see the quests that are unlocked by com­plet­ing the Year of the Horse quest.

In fact, if you con­nect all the quests in the game then you’ll end up with the fol­low­ing.

No won­der our game design­ers need a hand work­ing with the data!

But, just being able to work out how quests are con­nect­ed to each oth­er and visu­al­ize them is not all that excit­ing or use­ful. We can do much more.

With our price mod­el in full swing, we are able to:

  1. price base­line items based on fac­tors such as scarci­ty
  2. price items that are derived from the base­line items

Since the price of an item reflects the dif­fi­cul­ty in obtain­ing it, we can make use of the rela­tion­ships between quests and items to “price” quests the same way — i.e. the more expen­sive the items a quest require, the more dif­fi­cult that quest is to com­plete.

From there, you can estab­lish sim­ple rules such as:

  • cheap­er quests should come before more expen­sive ones, to ensure a sense of pro­gres­sion for the play­ers
  • a quest should not reward items whose total price exceeds the quest’s price

Monster Hierarchy

Final­ly, mon­ster trap­ping is a big part of the game as its name sug­gests. As men­tioned ear­li­er, to catch a mon­ster you need the right com­bi­na­tion of bait and trap.

To catch a mon­ster, some­times you have to first catch a low­er lev­el mon­ster; get its loot; and use the loot to make the bait for the mon­ster you want to catch. Using the fol­low­ing rela­tion­ships you can place the mon­sters into a hier­ar­chy.

Which can be trans­lat­ed into the fol­low­ing Cypher query:

MATCH
(monster1:Monster)-[:LOOTS]->(loot)
-[r:IS_USED_IN | CRAFTS*0..]
->(bait)-[:CAN_ATTRACT]->(monster2)
RETURN monster1,  monster2

Again, see how it mir­rors our dia­gram?

Sup­pose we are on a quest to catch Big­foot, we can use this query to iden­ti­fy the mon­sters we have to catch first in order to get the ingre­di­ents to make the bait for Big­foot. The query yields the fol­low­ing result where the pur­ple nodes are mon­sters and the red node in the mid­dle is the recipe for craft­ing the Allur­ing Goat.

This places Big­foot at the peak of its hier­ar­chy.

If you repeat the same exer­cise for every mon­ster in the game and com­pose their hier­ar­chies togeth­er, then you’ll end up with a more com­plete mon­ster hier­ar­chy cov­er­ing most of the mon­sters that exist in the game.

Once we have both the quest hier­ar­chy and mon­ster hier­ar­chy we can do some inter­est­ing analy­sis.

For instance, if com­plet­ing Quest 1 unlocks Quest 2, and catch­ing Mon­ster 2 gives you the loot you need to make the bait for Mon­ster 1:

then Quest 1 can­not ask the play­er to catch Mon­ster 1 if Quest 2 asks the play­er to catch Mon­ster 2.

This is to ensure that we do not break the sense of pro­gres­sion as the play­er pro­gress­es through the quests.

Oth­er­wise, as a play­er, you have to catch Mon­ster 2 mul­ti­ple times to get the loot to make the bait for Mon­ster 1, and then take sev­er­al attempts to suc­cess­ful­ly catch Mon­ster 1. Just as you had fin­ished with that cycle, the very next quest (or short­ly after) you are asked to catch the same mon­ster again, which doesn’t make for a very sat­is­fy­ing play­ing expe­ri­ence.

Remem­ber, the sit­u­a­tion might be even worse if you have to first catch oth­er mon­sters in order to make the bait for Mon­ster 2.

Even more Impact Analysis

We looked at how impact analy­sis applies to item pric­ing ear­li­er, but we have anoth­er inter­est­ing use for impact analy­sis with regards to the mon­ster hier­ar­chy.

When you suc­cess­ful­ly catch a mon­ster, you receive a gold reward from the Min­istry of Mon­sters and a chance to get the monster’s loot.

Suc­cess­ful Catch = Gold + (maybe)Loot

There­fore, for mon­ster catch­ing, there’s an equa­tion that needs to be bal­anced:

When­ev­er you change the price of an item that is either a bait or a loot, it can have a pro­found impact on the mon­ster hier­ar­chy:

  • change to one side of the equa­tion (item price, drop/attraction rate, gold reward) requires change to the oth­er side to keep things in bal­ance
  • change to the input side of the equa­tion requires changes to all pre­ced­ing mon­sters in the hier­ar­chy
  • change to the out­put side requires changes to all sub­se­quent mon­sters in the hier­ar­chy

Thank­ful­ly, Neo4j makes this real­ly easy, which is impor­tant because when­ev­er we intro­duce a new mon­ster (and it hap­pens pret­ty reg­u­lar­ly) it has an impact on all oth­er mon­sters in the same region as there is a new com­peti­tor for food!

Conclusions

I hope I have giv­en you a flavour of our use case with Neo4j. In gen­er­al I find graph data­bas­es to be the most pow­er­ful and nat­ur­al way to mod­el a domain, espe­cial­ly for domains with com­plex and/or high­ly con­nect­ed datasets.

Slides and Recording