Is there any point in a digraph implementation?

Question

The Foreword

Hi! I'm just your average, fairly beginner, computer science student doing personal programming side projects, and who is probably out of his depth and has no clue what he's doing. So, I might need some extra help/explanation to understand things.

The Context

Games and Branching Narratives

It's very frustrating to put this context into words, but this diagram/picture really helps frame my question (Note: Potential spoilers for The Stanley Parable):

Something that has always been on my mind is how games can have branching 'paths'. There is only so far you can go with nested if-statements before you get a horrible mess. Now, after some research - I discovered the 'digraph'...

What I've Done

Well, I began to plan out a way to implement a digraph. I found this guide: https://medium.com/basecs/from-theory-to-practice-representing-graphs-cfd782c5be38 To be very useful, and I was going to implement an adjacency list.

To traverse the graph, I'd create a "graph cursor". The graph cursor could be set to a position if needed, but otherwise had to follow the directional rules of whichever node it currently 'sat' on.

The nodes would contain the data for whatever the 'event' was (e.g. A story dialog event where the player would have to choose which fraction to side with), in addition, it would also contain rules for 'prerequisites' to disable certain branches if the player didn't meet them (e.g. Player needs at least 100 reputation before being able to access a dialog option/quest line).

Now, there is the issue of how in the world each node would have any knowledge of what the other nodes are (How to know which nodes to link together) - which can be solved by taking a page from the web, and assign each node with a resource identifier...

But, here's where my inexperience is really leading to my downfall.

The Problem

I defined node as an 'event' but that... isn't quite correct.

In an overview, a digraph is just a set of related data. The rules define the directional nature of the data, but does not define the conditions for choosing one path over another.

I'm trying to force the data structure to store 'events', as if that's meaningful to the digraph. The digraph doesn't care what data it stores, it just defines how it is stored!

So... what does that mean?

Well, I came up with an alternative model/abstraction. Based more so on webpages/choose your own adventure books. Rather then representing each nodes and the connections between nodes - there is just a list of "pages" with IDs. A page can contain outgoing links based on the ID. If a page is deleted or a link points to the wrong thing, you just get a 404 error, or just a wrong link.

But... you can create a digraph model of this too.

The Question

So at the end of it all, is there any point in trying to implement a digraph structure? At least in this sort of context, I mean, obviously it's useful for any graph theory heavy stuff.

But like, was there any advantages of the digraph structure in the first place?

I haven't implemented/attempted to create any of this yet... this is just what I've found out from planning things out.

I just want to make sure I've got it right this time.

---

In reply to @Doc Brown

Bad pseudocode examples of the kinda thing I mean:

class digraph {

    private List<node> myNodes;
    private Dictionary<Node, List<Node>> myAdjacencyList;

    public Digraph() {
        //Constructor
    }

    public list<node> NeighboursOf (Node node) {
        // Gets neighbours of node
    }

    public list<node> GetNode (string NodeResourceID) {
        // Gets neighbours of node based on ID.
    }

    // Add node method, Add Adjacency, Remove Adjacency, etc.
}

class node {
    // Does whatever a node does.
    // GetNeighbours method, GetDataStoredByNode, CheckNodeRules

}

vs

public List<string> pages;

class PageInterpreter {
    public LoadPage() {
        //Loads a page, 
    }
    // BAsicly, a 'web page', with everything in the bag.
}

void RunEngineCode() (
    if (current_page has updated) {
        LoadPage(currentPage);
    }
    UpdateAllElementsOfLoadedPage();
    redrawScreenIfNeeded();
    //etc.
)

main {
    while (true) {
        RunEngineCode();
    }
}

---

If my question has issues, please contact me so I can improve it.

If my question is wrong, well... I don't know what to say. I need help from someone more experienced then me. If this isn't the right place to put it - tell me where else I should go.

Thank you.

Answer 1

The representation you chose should make implementing your idea possible, and hopefully easy and clear. What you have in that diagram is a finite state machine. At any given state, the inputs determine what the next state is. The inputs can be literal inputs from the user via keyboard, mouse, game controller, etc. And they can also be data from the game world, such as whether the player has the gold key in their inventory.

The way you store the data is less important that how you use it and that it represents what you want it to. If that helps you to realize your goal doing it one way, then do it. One way might be to have a node that contains such things as 1) What to show to the user (perhaps dialog or actions from other characters), 2) A list of possible next states, and 3) A list of constraints or requirements necessary to go to each of those states.

So it might be something like this:

node 1

Tell User: You are in a dimly lit room. There is a table in the center of the room. On the table is a flickering candle next to a sharp knife. You hear a howl in the distance. There is an open door to the west. There is a locked door to the north. There is a staircase to the east.

Possible Next States:

node 2

node 3

node 4

Constraints

node 2: Player must go west

node 3: Player must have key and go north

node 4: Player must go east or up

In code, what you tell the user might be just a string. The next states might just be indexes into your array of nodes. And the constraints might just be a list of commands and required inventory items.

Another term that might be useful is data driven programming. This is where a set of data controls the flow of the program rather than the code itself.

Answer 2

It appears to me the gist of your question is:

• Should one implement such an adventure game by interweaving the allowed transitions between locations/game states directly utilizing some kind of markup language (which also describes the dialogs/pages/location description etc.), together with an interpreter for that language?

• Or: should to utilize some kind of separate digraph structure?

IMHO this answer is to some degree opinionated, but I think having a declarative, domain specific language for defining the game's location structure, containing the locations description as well as the allowed transitions and maybe constraints and conditions for them in one place is definitely a good idea for making games of a complexity comparable to the example picture you gave.

So, you will then need an interpreter for this "domain specific language", which generates the HTML/UI from the description of a location. Will this interpreter need some abstract "digraph structure" internally? I don't see immediately a compelling reason why it will need one, but for the high-level design this is IMHO quite unimportant. What this interpreter will need is obviously

• some cursor / active location (at which location is the current player)

• other game state information (for example, inventory of the player, state of some items in the game, etc)

So just go ahead, start to design your language and your interpreter, and when it comes to the gory details of the implementation, then you will surely find out if you need additional data structures, and which one.