3

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): Flow chart of the branching narrative of 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.

  • I don't understand what your "alternative model" means and why you think it is something different than a digraph. If you have pages with links between them, those pages and links represent the mathematical abstraction "digraph", so this is a digraph implementation. – Doc Brown Nov 17 '17 at 7:04
  • Well, in this way... I'm not explicitly storing the relationships... Um... again I don't quite know what I'm doing... I mean... although you can model the internet as a digraph, you don't normally call it a digraph implementation? A webpage's content defines a bunch of outgoing links, but you can never guarantee that a link is valid until you check? I'm probably misunderstanding the characteristics of a digraph. I mean, I know I am because I'm struggling with it. – Gry- Nov 17 '17 at 8:12
  • When you say "digraph structure", I guess you have an implementation in mind which uses terms like "nodes" and "edges", so somewhat "nearer" to the mathematical digraph definition. However, I think what you wrote quite vague, maybe just a problem of different naming? Can't you give an example, maybe written in pseudo code how your idea of a "digraph implementation" looks like and how this is different from "your alternative model"? Currently, I have problems to understand where you see the primary differences. – Doc Brown Nov 17 '17 at 9:55
  • @DocBrown 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 } Hmmm... I'll add it to the question.... bad formatting in this. – Gry- Nov 17 '17 at 11:42
  • So in your "PageInterpreter" approach, are you actually thinking of html pages as a container, maybe with formatted text and images, maybe with some dynamic parts in them, and the "graph edges" are implemented as links between those html pages? – Doc Brown Nov 17 '17 at 13:55
3

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.

  • The idea was to create some sort of node-builder, that can take some markup (probably xml) for each node. It would also mean I could export nodes too. Hmm, but the one issue I had with that idea is "how does a node, know that it is a node?". I could use a node class... which could then have sub classes like "dialogNode", "questNode", "rewardNode", etc. But then I'm forcing this node "thing" over any other data/object wanted to be stored. – Gry- Nov 17 '17 at 7:59
  • That sounds like the way that I would do it! I mean you have to have some sort of class or structure that holds the data from your file, and that data has to have some sort of structure to it to be useable. – user1118321 Nov 17 '17 at 16:08
  • Hmm, well... I was considering using generics, because a graph is kinda a collection... Although I haven't made my own generic stuff before, I wouldn't quite know what I'm doing : P. But I reasoned that if it accepted a generic input, then the input wouldn't know it's a node? Hmm, but I could create a digraph collection of "GameEvents", and something else that understood what it all meant. What I was trying to do was to expose the "choice logic" to the cursor in a generic way, I think? But in any case, having a digraph class with an adjacency list didn't seem to be helpful. – Gry- Nov 18 '17 at 2:08
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.