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
6 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

Minor update.

Two new classes, both of which are disabled by default but can be enabled via compile-time flags.

XY

Description

A data structure for storing and manipulating 2D coordinates/vectors. Basic declaration syntax is:

local foo = new XY(2, 5);

This creates an object with an x property of 2 and a y property of 5.

The main utility is in the methods provided by the class. All of them use integer approximations for performance reasons. They’re documented in the module’s README, but most of the interesting ones are:

Methods

  • length()
    Treats the coordinates as the elements of a 2D vector and returns its length (this is the same as the distance from the coordinates to the origin)

  • add(v)
    subtract(v)
    Add/subtract the argument, which must be another XY instance, returning a new XY instance containing the result

  • multiply(n)
    divide(n)
    Multiply/divide by the argument, which must be an integer, returning a new XY instance containing the result

  • distance(v)
    Returns the distance to the argument, which must be another XY instance

  • equals(v)
    Returns boolean true if the argument is another XY instance with the same values

  • isAdjacent(v)
    Returns boolean true if the argument, which must be another XY instance, is in the Moore neighborhood (checkerboard adjacent, including diagonals)

  • normalize()
    Sorta misleadingly named, this returns an integer-valued approximation of the vector, scaled to be ~10 units long. The idea here to use only integer math (because floating point is crushingly slow in the TADS3 VM) to kinda-sorta normalize the vector. But the coordinates for a unit vector that isn’t coincident with one of the axes would a real number in [0, 1). Which would end up being either zero or one in an integer approximation. So instead of computing a unit vector in the same direction as the original vector, normalize() computes a 10-unit long vector in the same direction, with the idea that you can then do whatever to it and then divide by 10 afterward to get approximately the same result. This obviously won’t work for everything, but most of the stuff I need this for involves multiplying the “real” normal by a scalar, so doing that and then dividing by 10 works fine (for some definition of “fine” which hopefully involves getting this damn thing out the door sometime this century).

Enabling

The XY class is enabled by compiling with the -D USE_XY flag.

AsciiCanvas

Description

A very simplistic data structure for constructing simple ASCII art(-ish) output. This is more intended for debugging stuff than for rendering ASCII “images” in-game—the XY class is part of some procgen stuff I’m working on and AsciiCanvas is part of debugging it.

Basic usage is:

// Creates a 20x10 canvas
local canvas = new AsciiCanvas(20, 10);

This creates a canvas 20 characters wide and 10 character tall. The coordinate origin is in the upper left, with positive values moving to the right and down, and values number from zero. This follows the conventions of the curses/ncurses library, but I might provide options for alternate sign conventions later (like origin in lower left with positive right and up).

Drawing outside the bounds of the canvas has no effect. So if you create a 10x10 canvas and try to put something at (-1, -1) or (10, 10) (because a 10x10 canvas is indexed 0 to 9 on both axes) it won’t throw an error or anything but it won’t remember what you tried to draw there. If you try to draw a line from (-1, -1) to (10, 10) it will work, but the out of bounds portions of the line won’t be preserved.

Methods

All the methods below that take x and y coordinates as arguments can either be called by passing integer coordinates or an XY instance. So for example:

v = new XY(5, 7);
canvas.setXY(v, 'x');

…is equivalent to…

canvas.setXY(5, 7, 'x');
  • getXY(x, y)
    Returns the current value of the canvas at the given coordinates

  • setXY(x, y, v)
    Sets the value of the canvas at the given coordinates. The assumption is that the value of v will be a printable character, but nothing actually enforces this and other values will work if you’re not planning on using the native output method

  • fill(v)

    Fills the entire canvas with the given character

  • display()
    Outputs the canvas. By default elements with no value assigned will display as . (a period). This can be changed by setting the instance’s blankChr property.

  • line(x0, y0, x1, y1, v)
    Draws a line from (x0, y0) to (x1, y1), using the character given by v.
    Can also be called with three arguments: two XY instances and the character to use.
    Uses Bresenham’s algorithm to draw the line, which only uses integer arithmetic.

  • circle(x, y, r, v)
    Draws a circle centered at (x, y) with radius r, using the character given by v.
    Can also be called with three args: an XY instance for the center, the radius, and the character to use.
    Uses the midpoint circle algorithm (itself derived from Bresenham’s algorithm), which only uses integer arithmetic.

  • recangle(x0, y0, x1, y1, v)
    Draws a rectangle with corners at (x0, y0) and (x1, y1), using the character v.
    Can be called with three args: two XY instances for the corners and the character to use.

Enabling

The AsciiCanvas class is enabled by compiling with the -D USE_XY -D ASCII_CANVAS flags.

3 Likes

Wow. Yet again, more interesting code people will either manage to find a use for, or scan through a couple of times before moving on. Side note: actual chances of TADS being a capable platform for Roguelikes now only 42%.

1 Like

Oh it’s been 100% for a while, but now it’s more streamlined.

And when one finally gets made, it’s gonna be dope. Take that, Kerkerkruip. Fun fact: Kerkerkruip actually means Dungeon Crawl in Dutch, something I didn’t know until google translate randomly popped up once.

1 Like