Interactive Fiction and Graph Databases

(originally posted on my IF blog)

I’ve been puttering on my own .NET-based IF platform for years. I rarely talk about it because it’s never gotten past the idea-stage. I originally started experimenting with Visual Basic .NET because I thought the verbosity was a good thing for IF authors. I recently switched everything over to C# with the idea of building a Fluent interface to all of the internal structures.

One of the many challenges of any IF platform is how data structures are implemented so that querying the “world model” is simple and fast. Graham gives some examples of the complexity of parser-based interactive fiction in his recent London IF Meetup presentation, specifically around assumed relationships between objects. (There’s no easy way to embed an exact reference, so you’ll just have to read through the part about natural language in IF).

Another thing I’ve been doing for about ten years is entrepreneurship. Most of you know I attempted to create a commercial/educational IF publishing firm, Textfyre. In recent years I was working on a contextual social network (Wizely) premised on offering globally shared wisdom. I have recently abandoned this startup because machine learning + Search has come close enough to contextual to make my ideas quaint and likely to fail.

However, one of the aspects of trying to build a real business is that you force yourself to learn a lot of new things. One of the things I picked up building Wizely was graph databases. I had been using Neo4j as my tool of choice, but the graph database world has matured and there are several prominent players and interfaces. I still think Neo4j’s Cypher language is the most readable and accessible, but fluent interfaces seem to becoming the standard.

Anyway, graph databases are really interesting when solving relational data problems, especially natural language problems. When you’re building a story in Inform 7, you may find yourself “selecting” things that relate based on “criteria”. One of the core features of Inform 7 is the ability to define very complex relationships and build rules from their current and future state.

A graph database (or data store) would help do the same thing. A graph is made up of vertices and edges, but also known as nodes and relationships.

Player -> IS IN -> Kitchen Player -> IS CARRYING -> Elvish Sword Elvish Sword -> IS CARRIED BY -> Player

As you can see, the elements of a graph align directly with how we perceive the world model of a parser-based interactive fictions story.

So extrapolate this to pushing all of the data (or beginning state) of a story into a graph data store, then add the standard graph querying capabilities of either Gremlin or Cypher, you could build an IF platform that focused on the state of a graph.

Cypher example relating to IF:

MATCH (person:Person {"name": "George"})-[:IS IN]-(location:Location)->[]<-(object:Object) RETURN object;

Which would return all of the objects in the location of the PC/NPC named George.

Cypher, Gremlin, and other graph query interfaces are very sophisticated and allow a great deal of querying power and I think this is a very interesting foundation for an IF platform.

In my current efforts, currently named “refly”, I’m building a serializable in-memory graph data store in C# and plan to implement a gremlin and/or Cypher interface. Once that’s complete, I’m going to build a working implementation of a story built in C# fluent interfaces to this in-memory data store. Then I plan to use Blazor to have it run completely in a standard browser that supports Web Assembly.

2 Likes

Thanks for posting this-- very interesting idea. I’ve been looking at using XML as the data store and XPATH as the query language for an IF system. With well named nodes, XPATH can be fairly human friendly for many queries, but I’m running into some issues when trying to create and query complex (and sometimes circular) relationships.

Hi,

I have this in KL;

There are two operators “|-” and “~” which approximately mean set and get. A similar example in KL goes like this:

First make a database; (setq kb {})

Let george be in the kitchen; (|- '(george (in kitchen)) kb)

Where is george?

(setq a (~ '(george (in _x)) kb)) ({(_x kitchen)}) (unwinds a) (kitchen)

Make a helper function that “unwinds” for us;

(setq getprop (fn (p s) (unwinds (~ (list p '_x) (eval s kb))) ))

Where is george?

(getprop 'in 'george) (kitchen)

Let moose be in the kitchen; (|- '(moose (in kitchen)) kb)

What is in the kitchen?

code kb))
(george moose)[/code]

What is in the location of george?

(setq a (first (getprop 'in 'george))) (unwinds (~ (list '_x (list 'in a)) kb)) (george moose)

The dog is in the kennel (|- '(dog (in kennel)) kb)

What things are in other things?

(~ '(_x (in _y)) kb) ({(_x dog) (_y kennel)} {(_x george) (_y kitchen)} {(_x moose) (_y kitchen)})

What’s in the database? {(dog (in kennel)) (george (in kitchen)) (moose (in kitchen))}

If the end goal is to have it run in a browser, is there any reason why you aren’t using javascript for this project?

Probably because JS is something you use when you did something wrong and are being punished :stuck_out_tongue:

2 Likes

As noted, you can run C# assemblies in the browser using Web Assembly at near native speed. My personal experience with C# is that I can write it, test, and debug it more efficiently than I can JavaScript. Fluent interfaces can be nicely done in JavaScript too and the patterns I develop for my in-memory graph data store would be portable to JavaScript, so that is an option. If I did go that route, I’d probably go with TypeScript.

For now, this is a really sporadic hobbyist endeavor. I’m still working on the graph data store, which is not a trivial piece of work. I’ve been cracking open an old Data Structures textbook to learn how graphs are searched. Fun times. ZZZzzz…

Sounds like time to upgrade from XPath to XQuery.

Or ditch XML entirely, which is what I did. Working on a graph based solution in JavaScript using a fluent interface. Will have much more to say about it in a couple of months.

2 Likes