It is not just a game, it is …
Preamble
Why did Santa bring the MSX-2 (Philips) home computer in 1986? Granted, it was state of the art! I had 256 colours, others only 8! I had a 3 1/2-inch floppy drive while most still struggled with 5 1/4 floppys and— heaven forbid — tape drives! I had 128K of RAM and another 128K of video RAM! The synthesizer module (the thing had two ROM expansion slots too) I got with it was amazing!
All the other pimple faced youths (PFY if you are old enough to know what the BOFH is) had a Commodore 64 or 128 though and had at least some social interaction exchanging games. I on the other hand had to buy every single game I ever owned and those — it not being the popular platform in Europe at the time — came at a premium.
Whilst I never completely caught up on the social skills, I do still play computer games. I’ve been told on numerous occasions that it is a waste of time. This wisdom is usually dispensed by somebody that also does not spend every waking moment 100% focussed on their job. So I ignore it.
What makes a great game is different for everybody. It has little to do with the visuals or the sound or the complexity of what you have to do. Take Vampire Survivors. It doesn’t get much simpler than that and yet it’s wildly popular (with hundreds of clones as a result) because you are stimulated (in a casino-like fashion) to play again, to try again, to get a bit further on the next attempt. One of the most succesful game franchises ever even made this into a slogan. One. More. Turn.
Since I see graphs everywhere these days (got there at last didn’t I), I also see them everywhere in games. Skill trees? Graphs. Sprawling maps? Graphs. Complex story lines? Graphs. Meta progression? Graphs. Procedurely generated anything? Graphs.
In my last post I stated that the quintessential graph use case is reacting in real time on a complex problem where connections matter. In the context of a game we need to add optimization. And what you get is Slipways. Which I will discuss in a future blogpost. Today I want to contradict the statement I made earlier. You can have a great game with much less than what Vampire Survivors does and one Neal Agarwal is a specialist at creating such games. Today I am going to take a look at Infinite Craft.
Modeling
How does it work?
- There are four root components: Water, Fire, Earth and Wind.
- Combine two instances of a component into an instance of another (potentially new) component. The input instances are destroyed.
- If you found a new component, you can now use that for another combination. Rinse and repeat.
- You can have as many instances of a component (root or derived) as you want.
Looks simple enough. Now why did I emphasize the word instance in the rules above? After playing for a short while I found three ways to get to Volcano:
- Fire + Fire
- Fire + Mountain (Earth + Earth)
- Mountain (Earth + Earth) + Steam (Water + Fire)
There are probably many more (almost any kind of reasoning will work in this game), but just looking at these three you can see that each mention of — for example — the Fire component is a specific instance of that component. Which can be modeled in a number of ways, but keeping it simple, just adding a recipe to the GOES_INTO relationship does the trick.
Play the game before it plays you
There is no one way to play Infinite Craft. You can just put components together randomly and see what you get. That keeps my 14-year-old busy for hours. It also has helped to expand his vocabulary massively. Or you can make it more competitive. You and a friend each open up the game, clear the board and pick a word. And then you race each other to find both words. Try helicopter and supercalifragilisticexpialidocious for example.
The volcano-thing got me thinking along other lines though. The three recipes each have a cost. Assuming that the four given components each have a cost of 1, the recipes respectively cost 2, 3 and 4. Interesting. I should always use recipe one. Unless there would be a limit on the number of instances for a component. Or an increasing / decreasing cost for using the same component multiple times.
Does that sound familiar to anyone? Because it sounds like optimizing a supply chain / manufacturing process to me!
Before going into solving there is one more complication that needs discussing. Cycles in the graph!
Earth and Wind combine into Dust. Dust and Water combine into Mud. Mud and Wind combine into Dust. Perfectly sound reasoning. As I said earlier, almost any kind of logic works in this game and if you consider Earth and Mud as synonyms, this makes perfect sense, wind can dry mud into dust. For graph processing however, cycles complicate matters.
Solving
First to set up the database
CREATE CONSTRAINT uniqueComponent IF NOT EXISTS FOR (c:Component)
REQUIRE (c.name) IS NODE KEY;
CREATE (wind:Component:Root {name: "Wind"})
CREATE (earth:Component:Root {name: "Earth"})
CREATE (fire:Component:Root {name: "Fire"})
CREATE (water:Component:Root {name: "Water"});
Adding a new component “X” goes like this
MERGE (new:Component {name: "X"})
WITH new
CALL {
WITH new
MATCH (new)<-[gi:GOES_INTO]-()
RETURN max(gi.recipe) AS recipe
}
WITH new, coalesce(recipe + 1,1) as recipe
MATCH (inputone:Component WHERE inputone.name = "Y")
MATCH (inputtwo:Component WHERE inputtwo.name = "Z")
CREATE (inputone)-[:GOES_INTO {recipe: recipe}]->(new)
CREATE (inputtwo)-[:GOES_INTO {recipe: recipe}]->(new);
Imagine you load many components and recipes. How then do you compute the minimum cost of say, Oven? Well, I found one recipe so far for it, it is the combination of Brick and Barbecue. Let’s look at the details of what is needed to make an oven:
Brick is made of Fire and Mud
Mud is made of Dust and Water
Dust is made of Earth and Wind
Barbecue is made of Farm and Fire
Farm is made of House and Earth
House is made of Brick and Earth
Brick is made of Fire and Mud
Mud is made of Dust and Water
Dust is made of Earth and Wind
The cost of Oven is 11. The main ingredient is Earth.
Intermezzo
I graduated (in IT, what did you expect?) in June 1993 and started working in July of that same year. I was going to change the world, but somewhere in the process of mastering the five steps to match two files on mainframe that hope was lost. I reset my sights somewhat and got involved into building a transport optimization system.
That was a nice challenge. And I solved it. Only to be told in writing (and I still have that note) that my solution was unacceptable because (and I quote) we can not expect that all developers can understand and thus maintain this hokus pokus recursive mumbo jumbo.
I proposed to run a training on the subject. Shot down again. Straight-out-of-school kid teaching the experienced developers? I think not. Back to writing match-two-files mainframe programs. That even back then could and should have been generated but for some reason were not … for another ten years!
P.S. Not ten years of me doing that, I moved to the IDMS (graph database!) DBA team only a few months later, but only when all the mainframe software had to be reviewed for the conversion to Euro in 2002 was code generation considered.
Recursion
There’s a prime (no pun intended) example just above. However, recursion is usually explained with the factorial function.
factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1 * factorial(0)
= 5 * 4 * 3 * 2 * 1 * 1
= 120
Pretty neat, right? The most important thing is the stop condition. In this case that’s factorial(0) which we know is 1.
You can solve this with a loop. Loop to 5, multiply along the way, done. And note that I do agree that for the factorial function that is a simpler — and yes, easier to understand — solution. The number of iterations is known up front.
This is not true of the Infinite Craft problems though. I don’t know beforehand how deep the tree for, say, Oven is. And it’s an unbalanced tree, Brick goes less deep than Barbecue does.
There’s another reason recursion works well here. Remember that there are multiple possible solutions (recipes) for a given component? Once I find one solution, I can stop the recursion for the others. Because the one I found is the cheapest. Yes, it is, think about it! This solves the cycle problem too. Assuming of course there is an acyclic solution (there always is)!
So can I solve this with a loop? Yes, of course. It’s going to be conditional though. Also, I need to keep track of higher levels whilst I go down the tree solving lower levels. What I need is a stack. And that complicates matters. A lot. At which point you can ask the question why am I keeping track of all this when recursively calling a much simpler function automatically does that for me?
Cypher — GQL
I’ve more or less described the steps to solve the cost calculation for any component above. So what you might expect now is some nice concise Cypher (or GQL). Can’t do. Not that I don’t have a solution, I do (and if you are interested, ping me), but it’s far from neat and concise.
Why is that? There is something that most database query languages miss. Try writing a recursive function with just SELECT. I’d love to see it. Cypher has a bit more flexibility (because it’s often used in a pipeline fashion), but proper branching, looping or functions? I don’t think so.
Of course, if you are in the SQL world, you’ll then pull out PL/SQL. Problem solved. Encapsulate your SELECT-statements, save as a stored procedure, done. So what about PL/GQL?
Doesn’t exist.
Custom Code
Cypher can be extended, but currently only by creating what is known as user defined procedures. These are compiled pieces of Java code that are deployed as jar files together with the database software. They are not stored in the database.
This code is flexible. It is not just a wrapper around the Cypher query language (although it can be), it also allows you to traverse the graph database node by node, relationship by relationship in a way that you define. In a way that makes sense to your business.
Whilst Cypher has caught up with the (historical) performance benefits of working this way, custom code is still used a lot to solve problems where the power of the graph needs to be combined with computational constructs.
At some point not so long ago an over-zealous Cypher-engineering team deprecated the kernel-api (the main component for custom code). The backlash was swift and that deprecation disappeared as quickly as it had arrived.
It is not just a game, it is …
Again you might be expecting some code here. The custom code that solves the cost calculation for Infinite Craft. Could do (and it is neat and concise) but not going to. If you are interested, ping me.
I do have a couple of concluding thoughts to share though.
First of all, I could have modeled in such a way that plain Cypher would have worked to solve it in the specific case where each root component has a cost of one. That’s not the point. Try solving a puzzle like this with plain Cypher. Convinced?
Secondly, do not lower the bar of expectations. Not for yourself, not for others. Move to an environment where the bar is high.
Lastly, in his book Designing Virtual Worlds, Richard A. Bartle explains that what our brain experiences inside a game is just as real (to our brain) as a — so called — real life experience. It is not just a game, it is …