A TADS3/adv3 module providing several basic data types/data structures

The module: dataTypes github repo.

This is the result of combining and refactoring a bunch of previous modules. The overall goal was to improve/regularize things like class names and method usages, removing code duplicated across multiple modules, and to as much as possible separate out stuff that’s just related to the underlying data structures and the stuff that was in there because of what I happened to want to do with it.

The module provides a number of basic classes. I won’t try to cover everything here but can field any questions on the off chance there’s anyone out there other than me planning on using this stuff.

Graphs

This is “graph” in the graph theory sense of the word. There’s the base Graph class, as well as Vertex and Edge classes. The base Graph class is undirected (so Graph.addEdge('foo', 'bar') is equivalent to Graph.addEdge('bar', 'foo')), and there’s a DirectedGraph subclass for directed graphs.

Examples

Here’s a simple three-vertex directed graph in which all three vertices are connected to each other declared in several different ways. Note: it would be easier to declare this as an undirected graph, but I’m using a directed graph because I think the syntax is slightly clearer because there are no “implicit” edges.

First, the “long form” declaration, using normal TADS3 lexical inheritence rules. In this example the Edge declarations refer to vertices by object reference:

// "Long form" graph declaration.
graph: DirectedGraph;
+foo: Vertex 'foo';
++Edge ->bar;
++Edge ->baz;
+bar: Vertex 'bar';
++Edge ->foo;
++Edge ->baz;
+baz: Vertex 'baz';
++Edge ->foo;
++Edge ->bar;

This declares an identical graph using vertex IDs instead of object references:

// Same as above, using IDs instead of obj references in edge declarations
graph: DirectedGraph;
+Vertex 'foo';
++Edge 'bar';
++Edge 'baz';
+Vertex 'bar';
++Edge 'foo';
++Edge 'baz';
+Vertex 'baz';
++Edge 'foo';
++Edge 'bar';

You can also declare graphs using arrays (this syntax is nearly the same as the one from the old markovChain module):

// "Short form" graph declaration
graph: DirectedGraph
        [       'foo',  'bar',  'baz' ]
        [
                0,      1,      1,      // edges from "foo"...
                1,      0,      1,      // edges from "bar"...
                1,      1,      0       // edges from "baz"...
        ]
;

In the above example the integer values are the edge lengths, with zero indicating no edge.

Finally, here’s the same graph generated at runtime:

// Create the graph
g = new DirectedGraph();

// Add vertices.
g.addVertex('foo');
g.addVertex('bar');
g.addVertex('baz');

// Add the edges.
g.addEdge('foo', 'bar');
g.addEdge('foo', 'baz');
g.addEdge('bar', 'foo');
g.addEdge('bar', 'baz');
g.addEdge('baz', 'foo');
g.addEdge('baz', 'bar');

And for completeness, since our example graph is complete (every vertex is connected to every other vertex) we could probably just use an undirected graph (unless we were expecting to twiddle the graph later and wanted directional edges then):

// Declare a simple three vertex undirected complete graph.
g = new Graph();
g.addVertex('foo');
g.addVertex('bar');
g.addVertex('baz');
g.addEdge('foo', 'bar');
g.addEdge('foo', 'baz');
g.addEdge('bar', 'baz');

The examples above illustrate the basic methods for interacting with graphs:

  • addVertex(vertexID, vertexInstance?) to add a vertex to the graph. If a Vertex instance is passed as the second arg it will be used, otherwise a new instance will be created with the given ID.
  • removeVertex(vertex) to remove a vertex from the graph. The argument can either be a vertex ID or a Vertex instance
  • getVertex(vertexID) returns the Vertex instance with the given ID, assuming it exists

There are equivalent methods for interacting with edges with similar usage:

  • addEdge(vertex0, vertex1, edgeInstance?) adds an edge to the graph. First two args are either vertex IDs or Vertex instances, optional third argument is an Edge instance to use (one being created if none is supplied)
  • removeEdge(vertex0, vertex1) removes the given edge. Arguments are either vertex IDs or Vertex instances
  • getEdge(vertex0, vertex1)returns the given edge, where the args are either vertex IDs or instances.

Finite State Machines

A finite state machine in this context is a set of states in which exactly one is the current state, and a set of allowed transitions between states.

In the module a FiniteStateMachine (or just FSM or StateMachine) is a subclass of DirectedGraph in which the states are the vertices and allowed transitions are the edges.

In addition to working like a basic DirectedGraph, FiniteStateMachine also has:

  • setFSMState(state) sets the current state. Arg is either a state ID or FSMState instance.
    This method does no validation, or bookkeeping, it just sets the current state bypassing the state transition logic.
  • toFSMState(state) is similar to the above but verifies that the requested state transition is valid, returning true on success and nil otherwise.

Markov Chains

A Markov chain is a state machine with probabilistic state transitions.

The module treats edge lengths as transition probabilities. Edge lengths can be declared either as integer weights or floating point probabilities.

If floating point numbers are used they will be interpreted as decimal percentages: 0.25 is a 25% chance of picking that transition, 0.33 is a 33% chance, and so on. In this case all edges leading away from a state should sum to 1.0.

If integers are used they’re interpreted as weights, with the transition probability being the ratio of the individual edge weight to the sum of the weights of all edges leading away from the state. For example if there are two edges on a vertex with weights 250 and 750 then the first will be selected 250 / (250 + 750) or 25% of the time, and the second will be selected 750 / (250 + 750) or 75% of the time. The same probabilities could be given with weights of 1 and 3 respectively.

Floating point probabilities are converted to integer weights during preinit (to avoid the overhead of floating point math at runtime).

Main additions to MarkovChain over the base StateMachine are:

  • markovBaseWeight = 1000 the base weight used for converting decimal probabilities into integer weights
  • pickTransition(fromState?, prng?) picks a random state transition. With no args the current state is used, with a state ID or instance as the first arg a transition from the given state will be used instead. Optional second arg is a PRNG instance to use for picking the state—this is for integrating the instancable PRNG module but the module doesn’t provide any PRNGs itself.
    This method will attempt to change the current state, returning the ID of the new state or nil on error.

Example

The format is mostly the same as for Graph. The addition is an optional intitialization vector which defines the probabilities used for assigning the initial state. Without an IV a random unweighted state will be picked (that is, in an n state chain each state will have a 1 in n chance of being the initial state):

chain: MarkovChain
        [       'foo',  'bar',  'baz'   ]
        [
                0,      0.75,   0.25,
                0.67,   0,      0.33,
                0.5,    0.5,    0
        ]
        [       0.34,   0.33,   0.33    ]
;

That defines a Markov chain with:

  • Three states: “foo”, “bar”, and “baz” (defined in the first array)
  • The state “foo” becomes “bar” 75% of the time and “baz” 25% of the time (first row of the second array)
  • The state “bar” becomes “foo” 67% of the time and “baz” 33% of the time (second row of the second array)
  • The state “baz” becomes “foo” or “bar” with equal probability (third row of the second array)
  • The initial state is “foo” 34% of the time, “bar” 33% of the time, and “baz” 33% of the time.

Rules and Rulebooks

In this module a rulebook is a container for one or more rules and a rule is a wrapper around a method that returns true or nil based on some arbitrary check implemented by the Rule instance. The rule has a boolean value based on the return value of the check method, and a rulebook has a boolean value based on the value of its rules.

The Rulebook class has subclasses for different basic rulebook behaviors:

  • RulebookMatchAll is nil by default and becomes true when ALL of its rules are true
  • RulebookMatchAny is nil by default and becomes true when ANY of its rules are true
  • RulebookMatchNone is true by default and becomes nil when ANY of its rules are true

Note: Unlike the old RuleEngine module, this module provides only the datatype(s). There is no mechanism by which rules and rulebooks are automatically evaluated—that happens in the companion asyncEvent module that’ll come next (as soon as I get around to typing up a post like this for it).

Tuple

A Tuple is a data structure for holding information about a turn and it’s action.

Full documentation is in the module, but this is basically a container for holding a “source” object and actor, a “destination” object and actor, an action, and a location. All of which are optional.

The class also provides a number of “match” methods (e.g. matchAction(obj) and matchSrcActor(obj)) which will return true either if the supplied object matches the corresponding value on the tuple or if the corresponding value isn’t set on the tuple.

That is, a Tuple declared with only an action, for example TakeAction will match any take action (regardless of the actor doing the action or the object being taken), but if you add Pebble as the “destination” object (that is, the object being targetted by the action) then that’ll only match pebbles being taken (by any actor) but not rocks. And so on.

The intent of the class is to make it easier to write rule-based action matching.

Trigger

A Trigger is a Rule that is also a Tuple.

Tweaks to Stock Classes

Collection

  • permutation() a method returninga Vector containing all the permutations of the elements in the given collection.
    NOTE the largest Collection for which the TADS 3 VM can generate all the permutations is 8. Called on larger Collections the method will return nil (instead of throwing an exception)

TadsObject

  • copyProps(obj) copies all the properties directly defined on the passed object (which correspond to properties defined on the calling object).
    That is, given:
    obj0: object { foo = 1 bar = 2 }
    obj1: object { foo = nil }
    
    Then obj1.copyProps(obj0) will produce:
    obj1: object { foo = 1 }
    
    Or alternately if (instead) you did obj0.copyProps(obj1):
    obj0: object { foo = nil bar = 2 }
    

Vector

  • swap(i, j) swaps elements i and j, returning true on success, nil otherwise.

Macros

The module provides a base isType(obj, cls) macro that evaluates true if the given obj is non-nil and is an instance of the given class cls.

This is used to implement a bunch of tests for both base TADS3 types as well as classes provided by the module, for example:

  • isAction()
  • isActor()
  • isCollection()
  • isInteger()
  • isList()
  • isLocation()
  • isObject()
  • isRoom()
  • isString()
  • isThing()
  • isVector()

And module-specific classes:

  • isEdge()
  • isFSM()
  • isGraph()
  • isMarkovChain()
  • isMarkovTransition()
  • isMarkovState()
  • isRule()
  • isRulebook()
  • isTuple()
  • isTrigger()
  • isVertex()

General Utility Macros

  • inRange(value, min, max)
    Evaluates true if value is an integer between min and max (inclusive)
  • nilToInt(value, default)
    Evaluates to default if value is nil, value (cast as an integer) otherwise.
    Example: n = nil; m = nilToInt(n, 0) will result in m = 0; n = '5'; m = nilToInt(n, 0) will yield m = 5.
  • noClobber(obj, value)
    Sets obj to be value, but only if obj is currently nil.
    Example: n = nil; noClobber(n, 2) results in n = 2; n = 5; noClobber(n, 2) resutls in n = 5.

As alluded to above I’ve also got an updated module for all of the “automatic” logic associated with rules, rulebooks, and state machines. There’s also an updated pathfinding module. Rolling this one out first because if I don’t start somewhere I’ll never get around it it.

Everything covered above is covered in documentation in the module; there’s a README.md that covers the above plus a more complete list of all the properties and methods on the various classes.

6 Likes

At this point, it feels like TADS 3 has diverged into three subspecies:

  1. Standard Adv3
  2. The JBG Edition of Adv3
  3. Adv3Lite
5 Likes

I take it this means SimpleGraph, StateMachine, markovChain, RuleEngine, Etc. are now deprecated?

I guess the old modules are deprecated-ish. I don’t think there are outstanding issues with any of them, but further updates will be to their replacements.

I had thought that I was going to immediately (after making dataTypes public) start releasing the rest of the replacement code, but I’m still jiggling the handle on some of it. Mostly API-ish stuff; in addition to writing test cases (which I’ve always done) I’m in the process of trying to integrate everything into a “real” game (or at least the skeleton of one), and that has me going back and forth with some stuff, particularly how complex datatypes (like crafting stuff and procgen map stuff) are declared. And I don’t want to publish anything until I feel like I’m done going back and forth with myself on that stuff. Even though I’m really the primary user of the code.

2 Likes

Understandable. Good luck with that. I feel like you’re the Kevin Forchione of the next generation in many ways, always making extensions that most people never use (aside from Kevin’s TimeSys, which was really popular no matter what language it was ported to, and could honestly use an update or a replacement in T3),but are always really interesting. If Kevin didn’t step away from IF in the 2010’s, I feel like he’d definitely dig a lot of your stuff.

2 Likes

I think that Jbg’s collection needs only a, uh, I don’t know the right word… systematisation ? collationisation ? that is, putting together the seams in an ordered, no-mutual-incompatibilities (if any, that is…) between the single contibuitions; the ideal I envision, to be honest, is something along the lines of:

#include <adv3.h>
#include <en_us.h>
#include <jbglib.h>

Best regards from Italy,
dott. Piergiorgio.

1 Like

In general all you should have to do is include the module’s header file (#include "dataTypes.h" in this case) and when you compile something if there are missing prerequisites it should tell you pretty clearly what they are.

For example, when compiled with support for Markov chains (via -D MARKOV_CHAINS) dataTypes requires the intMath module. The dataTypes.h header file contains:

#ifdef MARKOV_CHAINS

#include "intMath.h"
#ifndef INT_MATH_H
#error "The Markov chain functions of this module require the intMath module."
#error "https://github.com/diegesisandmimesis/intMath"
#error "It should be in the same parent directory as this module.  So if"
#error "dataTypes is in /home/user/tads/dataTypes, then"
#error "intMath should be in /home/user/tads/intMath ."
#endif // INT_MATH_H

[...]

Which means if you compile with -D MARKOV_CHAINS and intMath isn’t present, you’ll get something like:

[...]
../dataTypes.h(128): error: cannot open include file "intMath.h"
../dataTypes.h(130): error: #error :  "The Markov chain functions of this module require the intMath module."
../dataTypes.h(131): error: #error :  "https://github.com/diegesisandmimesis/intMath"
../dataTypes.h(132): error: #error :  "It should be in the same parent directory as this module.  So if"
../dataTypes.h(133): error: #error :  "dataTypes is in /home/user/tads/dataTypes, then"
../dataTypes.h(134): error: #error :  "intMath should be in /home/user/tads/intMath ."
Errors:   6
Warnings: 0

I don’t know of anything more straightforward using just native TADS3 mechanisms; T3 doesn’t have anything like JavaScript/Node.js’s require(). And T3 doesn’t have any way of testing for the existence of objects at compile time.

For my WIP itself I have a Bourne shell script (or actually a few of them) that figures out recursive dependencies and tweaks the main game’s header file and makefile to include everything. But it’s pretty brittle and probably doesn’t map well to general T3 projects.

That reminds me of an old friend of mine who created shell scripts for everything, including reading ebooks, downloading music from youtube, and even installing his own custom ArchLinux distro, all of which was very hacky and brutal. I mean, he was doing things that most blind people use specialized programs for, but attempting to do it in shell scripts, but hey, the stuff worked (most of the time).

1 Like