LambdaMOO data structures in MySQL
Now and again I get entirely sidetracked from my usual day to day programming madness into some other temporary realm of programming madness. I find it good for the soul.
There was a good reason behind my most latest foray, however: I wanted to take a quick refresher course in the latest PHP, Symfony, and MySQL updates to keep my hand in.
So I thought I?d set myself a little project. Which quickly got out of hand.
There?s a couple of games from the old BBS era (hence the spawning of the last post) that I actually miss playing, the main one called ?Hack & Slash?, written by Robert Hirst, although he?s ported it to Unix and it?s now called RPGD).
I thought it could be fun to port it to a web based game, so I sat down and started hacking away.
After a day of frenetic keyboard abuse, I had a Symfony based Finite State Machine, the character classes, monsters, and game objects in place, and the mechanics of fighting (albeit without magic spells, for which I wanted to introduce a new class hierarchy for) and things were progressing rather well.
The way I was writing the interface was very much mirroring the original game just with clickable links rather than needing to type in instructions.
My aim of spending a weekend getting some kind of proof of concept out of the door was then flummoxed by another, stronger train of thought.
I?d got the basic menu structure in place, which in part kind of models a small village (with shops, a fighting arena, and the like) that you can ?walk? around and buy things and generally supplement your character. I started to imagine what this village might look like, and whether the layout in the game would be at all like how a real village might organise itself as it grows organically.
Of course nothing good can come of thinking along such lines but I continued undaunted with a cup of tea and a pad of graph paper.
MOO Time
What I realised is that I wanted to be able to create and add features to the game over time, rather than having to write the whole thing before putting it online.
There is a well established model for this type of game. It is called a MOO (or multi-user dungeon, object-orientated) of which one of the most developed and long running is LambdaMOO ? you can still play it online.
A MOO shares the same text based interface as RPGD, though the user can enter freeform commands rather than being limited to a small list of commands.
I started thinking about how both systems could be combined, and it seemed feasible to create the game-play of RPGD within the structure of a MOO using its internal programming language, while also gaining the ability to build the village on the fly as and when I found a spare 15 minutes.
And, let me just mention at this point that I have no reason to believe anyone might actually play this game, I?m just enjoying the mental challenge of designing it 
It would also be very interesting, I continued to muse, if that rigid interface structure could be broken up further from a single session (both games assume a user is connected via telnet or similar) to a state based game, and utilise a database as the backend storage (LambdaMOO keeps the whole world in memory, RGPD keeps all the objects of the users session in memory).
This would enable web, telnet, or even mobile access to the game world, and create a nicer server application that could be written in something like PHP and be deployed on a standard web hosting package, rather than needing to run a server side program (as both games required).
There was some further thinking about completely redesigning the web interface to something very flashy and dynamic to replace as much typing with clicking as possible, but that?s for another time.
Let?s Hurt Me Some MySQL
Leaping back on the keyboard, I started to create a database structure that very closely mirrored LambdaMOO?s internal structures.
I quickly came across the rather unique requirements that the MOO required for its world:
- Everything in the world (including players) is an object and is descended, except for the top level object, from a parent object
- Each object has properties, either inherited from its parents, or defined on this object
- Each object has verbs (or actions), also inherited or defined
Each object, property and verb also has a set of permission bits that control how properties and verbs can be controlled on objects, and how objects themselves can be structured and controlled.
While each object having a parent is obviously a simple foreign key, the inheritance model proved to be a little more complicated.
Remember, the original system stores the entire world in memory so it can quite easily dance through its internal data structures with simple controls on locking parts of the object tree to avoid more than one thread changing things at the same time.
We could of course use table locks in MySQL for similar control, but it was my intention to create an atomic system that could be quickly and safely updated from a request session.
Bad Programmer, go to your room!
Now, I like to think of myself as quite a good programmer, but sometimes I get it quite, quite wrong and I?d like to share this with you now. As they say, success is a lousy teacher. (This doesn?t follow that a lousy teacher is a success, unfortunately, badoom-tish?)
I thought a good idea would be to duplicate all the properties and all the verbs on each descendant object. The reasoning behind this being that SELECT?ing an object should be fast as it would happen ofter, whereas object/property/verb creation and destruction would happen much less often, and by duplicating all that data, it would be a simple join between the tables.
To facilitate the inheritance, each property and verb would have:
- An object id, the object whose property this instance belongs to
- A parent id pointing to the same property/verb in the object?s parent
- A source id pointing to a parent property/verb that actually defines the property (explained below)
So, if we had a very simple structure like this:
Object #1 (has a property called ?foo? that is equal to ?bar?)
|
Object #2 (has a property called ?spa? that is equal to ?fon?)
|
Object #3 (has a property called ?foo? that is equal to ?notbar?)
The properties for each object would be like this:
- Object #1
- foo = bar (object = #1, parent = null (no parent), source = null)
- Object #2
- foo = bar (object = #2, parent = #1, source = #1)
- spa = fon (object = #2, parent = null, source = null)
- Object #3
- foo = notbar (object = #3, parent = #2, source = null)
- spa = fon (object = #3, parent = #2, source = #2)
Then reading an object and its properties is simply:
SELECT * FROM objects, properties, verbs WHERE properties.object = objects.id;
Nice. Then to update a property (on Objects #1 and #2, Object #3 still overrides)
UPDATE properties SET value=?foo? WHERE source = #1
This is all going swimmingly. But what about adding a new property or deleting properties, or even adding objects. Well, then it all goes a bit wrong as you need to INSERT or DELETE instances of all the properties and verbs from all the parent objects, and possibly the descendants too. It gets very messy and is certainly not very atomic.
Building The Nest
So I had a break, another cup of tea (I am British, don?t you know), and a meander around the InterWebs to see if there was a better model I could utilise for my own devious ends.
I found a good one, first described by Michael Kamfonas, and later coined as ?nested sets? by Joe Celko.
There?s a nice article with lots of example code on the MySQL dev site.
Go on, read the article, I?m not going to describe it here and if you don?t know the technique, you should!
Welcome back. So now I have a structure that looks like this. This schema is in Symfony format but should be fairly simple to understand by all (apart from the word wrapping, sorry):
rpg_object:
_attributes: { phpName: rpgObject, package: lib.model.rpg }
id:
parent_id: { type: integer, required: true }
left_id: { type: integer, required: true }
right_id: { type: integer, required: true }
scope_id: { type: integer, required: true }
owner_id: { type: integer, foreignTable: rpg_object, foreignReference: id, required: false, onDelete: cascade }
name: { type: varchar(30), required: true }
location_id: { type: integer, foreignTable: rpg_object, foreignReference: id, required: false, onDelete: setnull }
programmer: { type: boolean, required: true, default: false }
wizard: { type: boolean, required: true, default: false }
r: { type: boolean, required: true, default: false }
w: { type: boolean, required: true, default: false }
f: { type: boolean, required: true, default: false }
is_player: { type: boolean, required: true, default: false }rpg_prop:
_attributes: { phpName: rpgProp, package: lib.model.rpg }
id:
object_id: { type: integer, foreignTable: rpg_object, foreignReference: id, required: true, onDelete: cascade }
owner_id: { type: integer, foreignTable: rpg_object, foreignReference: id, required: true, onDelete: cascade }
parent_id: { type: integer, foreignTable: rpg_prop, foreignReference: id, required: false, onDelete: cascade }
source_id: { type: integer, foreignTable: rpg_prop, foreignReference: id, required: false, onDelete: cascade }
name: { type: varchar(20), required: true }
r: { type: boolean, required: true, default: true }
w: { type: boolean, required: true, default: true }
c: { type: boolean, required: true, default: true }
value: { type: longvarchar, required: false }rpg_verb:
_attributes: { phpName: rpgVerb, package: lib.model.rpg }
id:
owner_id: { type: integer, foreignTable: rpg_object, foreignReference: id, required: true, onDelete: cascade }
names: { type: varchar(255), required: true }
r: { type: boolean, required: true, default: true }
w: { type: boolean, required: true, default: true }
x: { type: boolean, required: true, default: true }
d: { type: boolean, required: true, default: true }
arg_preposition: { type: tinyint, required: true }
arg_direct: { type: tinyint, required: true }
arg_indirect: { type: tinyint, required: true }
With this structure we can defined properties and verbs on objects and get the whole cascading, inherited tree with a single MySQL query.
Also, within Symfony, there?s a plugin to handle nested set records.
We can add and delete objects quickly, change their parents, and we don?t need to copy verbs and properties (and cascading will delete the properties and verbs on any object).
I should probably give some examples but this post is getting quite long already and I?m really jonesing for another cup of brown joy.
So, where?s the game, you ask!
Well, it was coming along but then I started writing an interpreted JavaScript type language within PHP to handle the MOO scripting (and that?s for another post) and I just plain ran out of time. Anyway, the nested set thing is the important bit!
Ah well, some fun, but back to the day job!
