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.

7 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

Bump for a very tiny update, mostly because I want to be sure it doesn’t already exist in some form and I just missed it.

This is another new method on a stock fundamental datatype:

LookupTable

  • keyWhich(fn)
    Returns the first key for which the given check function fn returns boolean true when called with the corresponding table value.

    For example, given the LookTable

    t = [ 'a' -> 1, 'b' -> 2, 'c' -> 3 ];
    

    then t.keyWhich({ x: x == 2 }) will return b.

I’m in the process of implementing a bunch of lookups and reverse lookups for procgen stuff, and this sort of thing comes up a lot. It’s easy enough to write a l’il loop to handle it, but given that we have a valWhich() method on Collection and its various subclasses I’m surpised there’s not already a similar method for picking keys.

2 Likes

Bump for a couple new datatypes.

First, Rectangle, which is what it says on the label. It’s only included when the module is compiled with -D USE_XY.

Rectangle

A Rectangle is defined by its upper left and lower right corner.

The constructor can be called with two or four arguments: two XY instances corresponding to the upper left and lower right corners, respectively; or the same information as the four individual coordinates (in the order x0, y0, x1, y1).

Properties

  • height
    width
    Computed height and width of the rectangle. Should not be set manualy

  • upperLeft
    upperRight
    lowerLeft
    lowerRight

    XY instances giving the coordinates of the given corner. Also should not be set manually

Methods

The complete list of methods is given in the module’s README (and in rectangle.t itself), but the highlights are listed below.

In all cases where a method accepts coordinates as arguments they can either be given by giving the individual coordinates as arguments, or by supplying an XY instance. I’ll spell that out in the first example than skip it for the rest.

  • contains(x, y)
    contains(v)

    Returns boolean true if the rectangle contains the given point, given either as a ordered pair or as an XY instance.

  • expand(x, y)

    Expands the rectangle to include the given point.

  • offset(x, y)

    Returns the minimum offset, as an XY instance, between the rectangle and the given point.

  • manhattanDistance(x, y)

    Returns the minimum Manhattan/taxi distance between the rectangle and the given point.

    The Manhattan distance is the length of the shortest path between two points that only travels parallel to the axes. So the Manhattan distance between (0, 0) and (1, 1) is 2: one unit up and one unit over.

RTree

The RTree class implements simple R-trees.

An R-tree is a data structure for efficient querying of data that’s spatially indexed. That is, it makes things easy to look up by their coordinates.

The current implementation only supports inserts and queries.

Basic usage is simple:

     // Create a new tree
     tree = new RTree();

     // Inserts the value "foo" at (1, 2)
     tree.insert(1, 2, 'foo');

     // The value of v will be [ 'foo' ].
     local v = tree.query(1, 2);

RTree

Properties

  • maxBranches = 10

    Sets the maximum number of branches per node. Larger values give faster inserts but slower queries, and smaller values give the reverse.

    In most cases this probably won’t need to be changed.

Methods

  • insert(x, y, data)

    Inserts the data record data at the given coordinates.

  • query(x, y)

    Returns the data records stored at the given location.

    The return value will be a list containing all matching records on success, an empty list if there are no matches, and nil on errror.

This is more “no idea who else might need it” code, but now it’s out there.

The R-tree stuff is mostly useful when you’ve got a lot of spatial data that isn’t compact or well-behaved. You can accomplish the above examples more easily either by representing 2D positions as an array (linear or 2D), but that grows rapidly and becomes very inefficient if your data points are spread out. Similarly you could just interate over all your datapoints and check their coordinates directly, but that gets very expensive as the number of datapoints grows. The advantage of the R-tree is that queries remain quick for the dataset size and the amount of storage needed scales with the number of datapoints instead of the size of the problem space.

2 Likes

A couple more minor additions.

  • Rectangle.overlaps(x, y?)
    Method that returns boolean true of the given area overlaps the rectangle being queried. Arg can be single XY instance or two integer coordinates (in which case the method behaves exactly like Rectangle.contains() or a single Rectangle instance.

  • RTree.delete(x, y, data)
    RTree.delete(v, data)
    Removes the specified data record from the given location. Returns boolean true on success, nil otherwise

  • RTree.query(rectangle_instance)
    RTree.query() now works when called with a bounding rectangle as its argument.

There’s also been a little tweaking of the underlying R-tree query logic that should give better performance, specifically improvements to the branch splitting logic, which should produce more efficient branches. But none of that should be externally visible.

That’s probably all the major work I’m going to do on the R-tree stuff, unless I run into unexpected problems in integrating it into the procgen stuff I’m working on.

3 Likes

A couple new datatypes:

HashTable

Basically an associative array where collisions are handled with linear arrays. In other words multiple values can be associated with the same key.

Methods

  • insert(id, value)

    Stores the value value with the ID id.

  • delete(id, value)

    Removes given key-value pair.

  • query(id, callback?)

    Returns the values associated with the ID id as a list, or nil on failure.

    If a callback function is provided, it’ll be used as a check function on each potential result.

Matrix

The Matrix class implements generic multi-dimensional arrays.

In general you have to dimension Matrix instances when they’re created and you can’t resize them afterward. Example:

     // Create a 7x5x3 matrix
     local m = new Matrix(7, 5, 3);

Querying outside the dimensioned bounds will return nil but not throw an exception or generate an error.

Properties

  • dim = nil

    The configured number of dimensions. Should not be edited by hand.

  • size = nil

    Array containing the size of each dimension. For example in a 2x3 matrix this would be [ 2, 3 ]. Should not be edited by hand.

Methods

  • set(x, y[...], value)

    Sets the value for the given element. The number of arguments must be the number of dimensions plus one.

  • get(x, y[...])

    Returns the value for the given element. The number of arguments must be the number of dimensions.

  • load(array)

    Loads the contents of the array array into the matrix.

    The argument must be a linearized 2-dimensional square array: a 2x2 array given as a 4-element list; a 3x3 array given as a 9-element list, and so on. To load:

         a b
         c d
    

    …you’d use [ a, b, c, d].

IntegerMatrix

IntegerMatrix is a subclass of Matrix and works basically the same except all stored values must be integers.

Methods

  • determinant()

    Returns the determinant of the matrix, or nil on error.

    Only works for 2-dimensional square matrices.

TS

The TS class provides a very simple wall-clock timestamp service.

The constructor records the time when the instance is created, and then you can get the elapsed time since then by calling getInterval() on the instance.

Methods

  • getInterval()

    Returns the number of seconds since the instance was created.

Just a couple more datatypes I needed.

The timestamp thing because I finally got tired of re-doing something similar every time I need to test a new module. Figure dataTypes is getting included as a dependence in pretty much everything I’m doing so this is as good a place as any for it.

The Matrix class came out of testing. I’d assumed that linearizing arrays was fastest way to approach multi-dimensional arrays in TADS3, but array-of-arrays turns out to be substantially faster. So Matrix is just a utility class so I don’t have to remember if I declared an array as foo[x][y] or foo[y][x].

The HashTable thing is probably of fairly limited use—I’m guessing most people using LookupTable will just use different keys to manage collisions. I might end up re-writing it (to be a “real” hash table implementation) or dropping it later.

3 Likes

Bump for another new datatype, another type of data tree.

QuadTree

The QuadTree class implements, as the name suggests, quadtrees.

A quadtree divides the region it covers into evenly-sized branches, so it works best when the data it stores is roughly evenly distributed. R-trees, by comparison, work better when data is more unevenly distributed. Insert performance with a quadtree should be somewhat better on average than with an R-tree, but general query performance won’t be as good for large datasets.

Properties

  • maxData = 10

    The maximum number of data records stored in a leaf node. Larger number means faster inserts and slower queries, smaller number means the reverse.

    Similar to RTree.maxBranches , but QuadTree nodes always have exactly four branches (if they have any at all), and it’s only the number of leaves on leaf nodes that changes.

Methods

Methods are the same as described previously for RTree, so just a quick summary here:

  • insert(x, y, d)

    Inserts data d at the given location.

  • query(x, y)

    query(rectangle)

    Returns a list of all records stored in the given location(s).

  • delete(x, y, d)

    Removes the given data from the specified location.

Been spending most of my gamedev time working on procgen map layout algorithms, and so I’ve been cleaning up code for basic datatypes and pushing them into this module as I go.

I’m not 100% sure I’m going to need all, or even any, of this outside of testing and debugging during development. But I figure if I’ve invested the effort into writing this stuff in the first place I might as well spend the extra effort to document it and make it available on the off chance someone else could use it.

3 Likes