IF Platform Design with a graph data store

Authoring Other Development Systems
1

I have a graph data store to keep track of the world model. Anytime two things are connected, they have bidrectional EdgeTypes (IsWithin/Contains). Every Node and Edge has a Dictionary of properties for extra information.

Connecting two locations is tricky because the EdgeType is LeadsTo, but I still need to add the compass direction. Do I add a property (“Direction”, Direction.East) or do I add directions to the EdgeType list?

I’m trying to keep the IF stuff out of the data store as much as possible though the EdgeType enumeration is IFfy:

public enum EdgeType
{
    IsWithin,
    Contains,
    IsCarriedBy,
    Holds,
    IsIn,
    Hosts,
    IsSupporting,
    IsOn,
    LeadsTo
}

Or do I alter this list to be some other list of relations?

This is all malleable and really just choices, but wondering if anyone had thoughts.

2

In the past I’ve defined a Transit object, a bit like an arrow on a diagram. It has a starting point, a compass direction, an endpoint, directionality, and sometimes a label (eg: ‘slippery slope’).

Here’s some Python code from back then.

I’m still refining the idea, so this code isn’t exactly what I’d do today. Hope it might give you some options though.

3

That’s sort of what an Edge is in a graph. It does bring up the idea that an edge has two sets of properties, relating to each side of the edge connected to its Node.

(Node) ← props ----- props → (Node)

This would look like this in the Edge class:

    public class Edge
    {
        public string Id1 { get; private set; }
        public string Id2 { get; private set; }
        public EdgeType EdgeType { get; private set; }
        public Dictionary<string, GraphProperty> StartProperties { get; set; }
        public Dictionary<string, GraphProperty> EndProperties { get; set; }

        public Edge(string startNode, string endNode, EdgeType edgeType, GraphProperty startProperty, GraphProperty endProperty)
        {
            StartNode = startNode;
            EndNode = endNode;
            EdgeType = edgeType;
            StartProperties = new Dictionary<string, GraphProperty>();
            EndProperties = new Dictionary<string, GraphProperty>();
        }
    }

public class GraphProperty
{
    public string Key { get; set; }
    public object Value { get; set; }

    public GraphProperty(string key, object value)
    {
        Key = key;
        Value = value;
    }
}

That’s a lot of code to connect a couple of Nodes though this does get “hidden” in the Standard Library.

4

I guess you could put the EdgeType enum into the IF / world model module, and have the Edge class be a generic.

That still leaves the issue that Enums aren’t inheritable in C#, so there’s no easy way for the game author to define new relations. (E.g. “worn” or “part of”.)

5

I’m thinking the EdgeType is what is unnecessary. It hardens the Edge when we want Edges to be fluid. Then we can set directional properties on each side of the edge: EastTo/WestTo, IsWithin/Contains etc.

Those directional strings can come from a static class in the StandardLibrary that is extensible by the author.

Update: This is the way I’m going for now.

1 Like
6

I don’t know what the rest of your engine looks like, but unless you’re really confident that rooms are the only thing you (or other game devs using it) are going to use the graph logic for, then I wouldn’t want an edge to contain any information about things like containment, compass directions, and so on.

From an abstract design perspective (and, again, I don’t know what the rest of your engine looks like) I’d suggest implementing your vertex and edge classes either as mixins (if the language supports it) or just have your other game objects either contain refs to whatever graph elements they correspond to, or put references to the game objects in the vertex and edge classes.

So an edge in and of itself would never know what “west” is, but a room object might have a “west” property that happens to be an instance of the edge class. Or just another room instance, and travel actions just know to consult a room graph (in which each vertex contains a reference to a room object) if it needs to do whatever it is you’re expecting to do with the graph logic.

7

Just checked the latest code in.

I have experience using Neo4j which has ability to store properties on nodes and edges. I’m going one step further and providing a property list on both “ends” of an edge.

The standard library will implement the IF objects leveraging the graph. I actually have a WorldManager class acting as a repository pattern. Any queries of the world model go through the WorldManager.

This allows me to look for nouns, locations, connections (interpreted as IF relationships).

It allows me to check context, such as IsPlayerAndObjectInSameLocation(object)

Or IsPlayerCarryingObject(object)

I’ll likely add many common queries to support IF logic.

8

I’m not trying to talk you out of anything here, and like I said I don’t know what the rest of your code looks like. And I don’t know if you’re interested in general design suggestions. So just talking about this because I like talking about these kinds of design issues.

But not knowing anything about the system you’re designing but knowing a bit about graph theory I’d expect the end of an edge to be a vertex. If you’re adding a layer of abstraction between the edges and vertices, or adding “handedness” or something like that to edges…that makes sense in a lot of IF contexts. But it’s not something to do with graph edges in general, so I wouldn’t expect it to live in the definition of an edge. Presumably you have some specific design case for this…it’s something that’s being demanded by some class or classes of game objects that need edges to record whatever it is you’re recording here. So all else being equal I’d expect that logic/data/whatever to live there, instead of in the edge class. That is, rooms might know what “west” means1, or maybe abstract room connectors2, edges probably shouldn’t.

  1. Although (even if you’re implementing standard IF compass-based navigation semantics) rooms probably actually want to know about some arbitrary set of orthogonal directions, one of which can be identified as “west”.
  2. In TADS3, for example, all Rooms are TravelConnectors with themselves as their destination.
1 Like
9

Definitely appreciate input.

Yes, vertices and nodes are the same thing, but in a graph data structure, we have a list of Nodes (vertices) that contains a list of Edges.

I’m still in experiment mode, so unsure how connections will work (yet).

I’m in the midst of defining how Directions and Exits work and it’s not simple. In Inform 6, Directions are a part of the default Go verb (GO NORTH). But there’s so much cruft in that assumption. It’s easier to define Directions as their own thing like this:

public enum TokenType
{
    Verb,
    Noun,
    Second,
    Third,
    Adjective,
    Article,
    Preposition,
    Direction
}

In the Parser we now check for directions first. I had thought to make each direction its own Verb, but we lose a lot of compass fidelity that way (like handling going nowhere or anywhere by X).

But the graph itself will definitely have Edges that connect two Location Nodes. How I implement the Directionality is a work in progress. I’d started with adding a property on Start and End sides of the Edge for directions. First, we look for an Edge that shares two locations and then determine which directions are used. If I’m trying to go east from Location A, the shared Edge start property “east” should exist and if it doesn’t, you can’t go east from Location A.

However, we need to handle any failed directionality properly and allow the author to define success and failure. That’s where I am at the moment.

Note the code is at: ChicagoDave/chatgpt-ifplatform: I used ChatGPT-4 to design and code an Interactive Fiction platform on top of .NET/C#. (github.com) and compiles. If you have VSCode or Visual Studio, it’s easy enough to clone and run. Cross platform .NET Core too, so Mac, Linux, or Windows. And it’s a console app for now, so no GUI is needed.

1 Like
10

Attaching information to the endpoints of an edge isn’t too unusual in graph theory. Imagine, for example, a weighted digraph where the weight A → B is 5 and the weight B → A is 2. Is that fundamentally different from the direction A → B being west and the direction B → A being east?

2 Likes
11

I think there is some confusion with bi-directionality. I could just as easily create two separate edges with one set of properties, including “direction”. But that seems unnecessary.

12

It just occurred to me that after I added two sets of properties, I forgot to remove the double edge implementation. I’m stepping on my own design mutations. :slight_smile:

13

The situation you’re describing isn’t attaching different weights to the endpoints; you’re describing a directed graph, A → B and B → A are two different edges, and the weight is a property of each edge.

That said, the point I’m trying to make is that stuff like properties specific to room navigation probably shouldn’t be on the base graph classes (graph, vertex, edge) unless room navigation is the only thing the graph logic will be used for. For example, in the IF game I’m working on (in TADS3), I wrote some abstract graph-related classes and I’m using them for room-based pathfinding…but also for dialog nodes, NPC goal-seeking, “quest” tracking, and so on. It doesn’t make sense (at least in this game) to go “west” from “Hello”, for example, so all the logic that handles room-based pathfinding is handled outside the base graph/vertex/edge classes, usually in a room-specific (or dialog-specific, or whatever) subclass.

I’ll just add an aside here that when I’m talking about how things “should be” or “shouldn’t be” done, I’m just expressing an opinion. I’m not trying to argue that doing it some other way is “wrong” or anything prescriptive like that. Just talking about my personal design biases, formed from having run around this particular teacup a whole lot of times looking for the handle.

14

Yeah, I have no idea how Hello would lead to West. The graph is buried underneath a repository pattern and completely segregated from the parser and grammar (outside of locating nouns in the graph).

15

Even if all you’re planning on handling with the logic is room connections, you probably want to at least accommodate the possibility of non-reciprocal connections: trap doors, teleporters, scene transitions, and so on.

16

Sure. My point is that there are a lot of things in gamedev that can be (and typically are) built on graphs, so if you’re going to implement graphs in your system it probably makes sense to keep the base classes as clean as possible unless you’re really sure you’re not going to use them for anything else down the line.

17

Well this particular graph is meant specifically for an IF platform. Part of my experimentation is to identify how much separation is practical between general graph and IF specific data.

18

I was recently introduced to the fast but memory-expensive Hexastore (PDF) strategy for storing graph data. It’s just that for every 3-tuple of (subject. predicate, object) you go ahead and store it by all 6 permutation, you can get all o’s for any s&p, aall p’s for any s&o, etc. It’s wholly agnostic on what can or can’t be in any of the three places. I just thought I’d toss it out; I’ve been having fun futzing with it.

1 Like
19

Sure, but room traversal, dialog trees, NPC goals, and quests are all things that occur in IF. And for that matter in the IF game I’m currently working on I’m using three different kinds of graphs just for room-related stuff (two levels of graph for map traversal, and one for procgen map layout stuff).

20

That’s an interesting thought. Different data structures for different aspects. Definitely keep that in mind.