Layered Design:

• Client Communications
• Object Management
• Rules Engine

Client Communications Layer

Threaded system pattern

1. Server creates a Listener
2. The Listener waits for TCP connections
3. When a connection is established, the Listener passes that to a new Handler and the Handler is registered with the Listener (to allow for management)
4. The Listener continues waiting for connections until signaled to shut down. When asked to shut down, it stops listening and then tells each Handler to shut down.
5. The Handler establishes a good connection with the Client, including setting up any I/O streams as needed.
6. The Handler receives asynchronous messages for the Client, formats them appropriately, and sends them to the Client via the output stream.
7. The Handler waits for messages from the Client, decodes them, and sends them to the Rules Engine for processing.
8. The Handler can be asked to shut down by the Rules Engine or the Listener. When asked to shut down, it will immediately disconnect from the Client. It is the responsibility of the Rules Engine to ask the Handler to notify the Client about pending shut down messages. It is the responsibility of the Client to cleanly handle disconnected connections.
9. The Handler is responsible for determining the state of the connection with the Client. Every n seconds (where n >= 10) of idle time on the connection with the Client, the Handler will sent an empty message. If an exception occurs, the connection will be tested o times (where o >= 3) with pauses of t seconds (where t >= 1). If more than o tests fail, the Client is considered to have prematurely disconnected and the Rules Engine is notified. The Handler will then shut down the connection to the Client.
10. The Handler will notify the Listener when it has closed the connection with the Client so that the Listener will no longer need to manage the Handler.

select() system pattern

1. Server creates a Listener
2. The Listener waits for TCP input
3. When input occurs, the Listener determines which Handler is associated with that file handle. If no Handler is found, it passes the file handle to a new Handler and the Handler is registered with the Listener (to allow for management and message passing). If a Handler is found, the Handler is given the input to process.
4. The Listener continues waiting for connections until signaled to shut down. When asked to shut down, it stops listening and then tells each Handler to shut down.
5. The Handler establishes a good connection with the Client, including setting up any command buffering as needed.
6. The Handler receives asynchronous messages for the Client, formats them appropriately, and sends them to the Client via the output stream.
7. The Handler waits for messages from the Client, decodes them, and sends them to the Rules Engine for processing.
8. The Handler can be asked to shut down by the Rules Engine or the Listener. When asked to shut down, it will immediately disconnect from the Client. It is the responsibility of the Rules Engine to ask the Handler to notify the Client about pending shut down messages. It is the responsibility of the Client to cleanly handle disconnected connections.
9. The Handler is responsible for determining the state of the connection with the Client. Every n seconds (where n >= 10) of idle time on the connection with the Client, the Handler will sent an empty message. If an exception occurs, the connection will be tested o times (where o >= 3) with pauses of t seconds (where t >= 1). If more than o tests fail, the Client is considered to have prematurely disconnected and the Rules Engine is notified. The Handler will then shut down the connection to the Client.
10. The Handler will notify the Listener when it has closed the connection with the Client so that the Listener will no longer need to manage the Handler.

Object Management Layer

The object management layer has the following requirements:

1. Provide instances of objects as needed (load new objects)
2. Keep track of instances of objects (references) for object lookups
3. Serialize object contents at checkpoints or when the object is released from the system
4. Remove deleted objects from the system
5. Provide a unique method of tracking object identities between invocations of the server, independent of the instance object reference
6. Manage memory, including signaling of the Rules Engine when the system is low on available memory and, if possible, serialization and removal of objects in memory
7. Interface with the implementation specific Data Store for object data

Object ids should take the form of a case-sensitive alphanumeric string ([a-z,A-Z,0-9]), at least 15 characters in length, allowing for (15^62) 8.272905x10^72 unique object ids (more than 8,272,905,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 ,000,000 objects). Alternatively, object ids can take the form of a numeric id, at least 10 characters in length, though this will limit the total number of unique object ids to (10^10) 1x10^10 unique object ids (10,000,000,000 objects).
 

1. A Registry and Factory pattern can be used to provide for some object management (especially new instances, and object lookups):
2. When created, the Registry will create a dynamic, resizable in-memory index of object ids and instance references. Additionally, the Factory will establish a connection to the Data Store for retrieval of objects. The Registry will be sized to at least 1/10th (a tunable parameter) the number of objects in the Data Store.
3. The Registry will accept requests from the Rules Engine to get objects by object id. If the object is already in the in-memory index with a valid reference, the reference to the object will be returned to the Rules Engine. Otherwise, the object will be created and loaded from the Data Store. If the object id is invalid, the Registry will raise an exception which must be handled by the Rules Engine.
4. The Registry will accept requests from the Rules Engine to release objects by object id. If the object is in the in-memory index with a valid reference, the object will be removed from the in-memory index, serialized to the Data Store and the memory referenced by the object will be freed. If the object is not in the Data Store, but is in the in-memory index, a new entry will be created for the object in the Data Store and then the object will be serialized, removed from the in-memory index, and freed. If the object is not in the in-memory index, the request will raise an exception which must be handled by the Rules Engine.
5. The Registry will accept requests from the Rules Engine to delete objects by object id. If the object is in the in-memory index with a valid reference, the object id will be removed from the in-memory index and the memory referenced by the object will be freed. The Data Store will then be instructed to remove the object's data. This will create a hole in the Data Store (the object id).
6. The Registry will accept requests from the Rules Engine to create new objects. The object will be created and initialized with default values, then entered into the in-memory index. The object reference will then be returned to the Rules Engine (which can look up the object id from the reference, if needed). If the parent object was not found, an exception will be passed to the Rules Engine which must handle it properly. The new object's id should be based on the request time plus some random factor, put into a hash value and compared against all the object ids in the Data Store for uniqueness this process will be repeated at 1/10th of a second intervals until a unique id is created. Alternatively, the Data Store can return a new, unique number (such as an identity field in a table).
7. The Registry will accept requests from the Rules Engine to return the object ids of all objects (in-memory and in the Data Store) that match a particular criteria (typically, via inheritance, implementation, or which use a component). The Registry will query the Data Store for matching objects, then return that list and should work to asynchronously cache those objects in memory for subsequent lookups.
8. The Registry should queue Data Store activity. Get requests from the Rules Engine are promoted to the front of the queue. Release requests are medium priority. Match requests that are caching objects are low priority. Delete requests are very low priority. Data Store activity will be performed in priority-fifo order. If the Data Store supports it, multiple Data Store interfaces may be made available to handle the queue better.
9. An asynchronous thread or task should run to check memory at 30 second or greater intervals. If memory is less than 10% free, the Rules Engine will be signaled to release unneeded objects.

Rules Engine Layer

• Object Management
• Request Handling
• Script Processing

The request handling portion of this layer parses requests from the Handler and invokes the appropriate script and accepts requests from scripts.

The script processing portion of this layer implements a scripting language that can invoke scripts associated with other objects, as well as intrinsic methods defined on objects. The scripting language is Python which will allow for on-line creation of persistent objects via methods on the object management portion of the layer. In-memory, transient objects can also be created using standard Python calls. A rich library of task management, event handling and notification, and object lookups and manipulation is provided by this layer, as well. 

The map can be layered, if you like...

TOP:  mobiles

MID:  immobiles

BOT:  landscape mod

Mobiles are defined as objects that can move or be moved. Avatars,
items, NPCs, etc. Drop money on the ground and it turns into a mobile.
Drop your sword and it's a mobile. Walk someplace and you're a mobile.

Immobiles are defined as objects that are placed and not moved.
Frequently, they include changes to the landscape. Immobiles include 
houses, walls, decorations, trees, and brush. Some immobiles may 
intrinsicly change the landscape (say, but ensuring a flat foundation 
for a house). Others (like trees) won't.

Landscape modifications are cumulative changes to the landscape,
typically by changing the characteristics of elevation, terrain type,
and environment. Elevation indicates the altitude of the land. The
terrain type is something like bare earth, grassland, mud, swamp,
desert, or water. Environment includes special effects like poison
gas, raditation, or fire. Landscape modifications should be area
based, with a central coordinate or set of bounding coordinates (in a
polygon) to minimize representation size. (Thus, an entire town could
be brought to the same elevation with a single modification...the
modelling engine would have to be intelligent enough to modify
surrounding land unless you like abrupt, step-like cliffs.) An
additional really cool feature to this is that player activity can
have a semi-permanent impact on the landscape (say, if a player 
decided to dig a trench). The lifetime of these modifications should 
be limited.

The underlying landscape is fractally (?) generated from a seed value
(thanks, Raph, for the reminder...haven't done this since I wrote the
terrain module of a battletech simulator on LambdaMOO). It is modified
by the landscape modifier (stored in the database) and other layers
are sucessively drawn upon it. 

Avatar movement across the landscape is typically limited by factors
of:
- significant elevation change (more than 1/2 the avatar's height)
- placement of immobiles that are flagged impassable or are more than
  1/2 the avatar's height
- placement of mobiles that are flagged impassable (other avatars, for
  instance) or are more than 1/2 the avatar's height
- attempted entry into a terrain that does not allow entry (say,
  water)

Sparse mapping assists in one other crucial element in a coordinate
based system. In a coordinate based system, event propagation is
crucial. Certain events propagate farther than others (distances are
in radius):

- whisper is only audible in the immediately adjacent area (less than
  one meter)
- talk is only audible to roughly three meters
- shout is only audible to roughly thirty meters
- a fireball propagates to roughly five meters

A sparse map allows for faster, easier collection of adjacent objects
than other methods. For comparison, we'll look at a tile-based
containment system.

In a tile-based containment system, each tile has a "contents"
property that indicates what object is at that coordinate. This can be
a mobile or immobile. To determine how far a talk has propagated, each
tile in the three tile radius needs to be queried. You can either use
an equation to get xy coordinates for matching tiles, then build a
list of each tile, or use a recursive technique to explore each
adjacent tile with a decrementing radius count and a shared list of
all tiles visited. Either works. When the list of tiles to notify is
built. it is iterated across and each tile is examined to determine if
the object contained by the tile accepts the talk event. The talk
event is then dispatched to those talk event listeners and the event
is complete. (Yes, there are other ways of doing this.)

In a coordinate-based, sparse map system with cartesian coordinates
(not tiled, but smooth), an event is given an origin, and boundary
conditions are assigned. Only those objects that possess coordinates
within that boundary are checked, and only those that accept the talk
event receive the event notification. Assuming an optimized lookup of
coordinates, this system is less CPU intensive, and certainly less
expensive in memory requirements.

This means that a significant portion of the libraries used by the
rules engine in my design for a MUD are composed of map management
(movement and collision detection, event propagation, map composition,
and communication of modification to the client), This places a burden
on the database interface (registry) to provide speedy, memory
efficient map coordinate lookup (R-tree anyone?).

R-tree references
• Definition
• Optimized lookups using R+ trees bibliography
• Presentation of R* trees
• Graphical representation of R-tree
• R* tree compared
• Analysis of R*-tree indexing methods homework
• R* tree nearest neighbor searches
• Another R-Tree presentation
• and her grad project,
• fast k nearest neighbor search
• A Cost Model for Similarity Queries in Metric Space presentation
• R-tree based indexing of new-relative bitemporal data (PDF) Deals specifically with data in databases that has expiration periods...I'm more interested in R-tree representations that allow for dynamic movement in the dataspace for all elements. Even BSP trees aren't optimized around this kind of motion.
• Target Jr vision research platform (but check out the really cool api!
• Quad and R-Tree presentation
• Surfvey of spatial access methods presentation
• Region quadtrees and R* trees lecture presentation
• Spatial Index demos requires Java in browser

Terrain Generation

Database representation of objects, methods, and fields

The database has a number of tables representing objects, classes and class heirarchies, class methods, class fields, instance field values, etc. The object registry is responsible for keeping track of which objects are currently in memory and which objects are not in memory. Updates to not-in memory object field values can take place by updating the database field (typically, this would occur over a network message). Updates to in-memory objects should occur in memory and are serialized when the object is removed from memory or checkpointed.

Changes to class definitions should propagate through in-memory and not-in memory objects on an asynchronous basis. This can make compiled, working code fail as fields change names or are removed, as well as remove methods that are allowed. These will throw an appropriate exception.

Note that object pointers kept by the registry (in-memory references) are different from object ids used to look up objects. Undecided yet is how the registry will allow aliased objects (literal strings that return object ids or references). Additionally, a synthetic object id is generated for unique objects in a network space (typically, ip or hostname concatenated to an object id).

Types are defined in the database with a table. Types are defined by a name which is hard coded into the engine (so types can be referenced independant of numeric identity field and databases can be moved safely).

The scripts used to create this database are available. They are intended for use with the MySQL database but should be able to be easily converted to another database. Note that no behaviors or constraints are defined beyond references to foreign keys, uniqueness, and null/not-null.

Data Dictionary

+--------------------+
| Tables_in_Scripted |
+--------------------+
| t_access           |
| t_class            |
| t_field            |
| t_field_instance   |
| t_method           |
| t_method_arg       |
| t_object           |
| t_type             |
+--------------------+

describe t_access;
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| Field     | Type        | Null | Key | Default | Extra          | Privileges                      |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| access_id | tinyint(4)  |      | PRI | NULL    | auto_increment | select,insert,update,references |
| access    | varchar(11) |      | UNI |         |                | select,insert,update,references |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+

t_access

access_id

access

describe t_class;
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| Field     | Type        | Null | Key | Default | Extra          | Privileges                      |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| class_id  | int(11)     |      | PRI | NULL    | auto_increment | select,insert,update,references |
| parent_id | int(11)     | YES  | MUL | NULL    |                | select,insert,update,references |
| class     | varchar(64) |      | UNI |         |                | select,insert,update,references |
| fertile   | char(1)     |      |     |         |                | select,insert,update,references |
| final     | char(1)     |      |     |         |                | select,insert,update,references |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+

t_class

class_id

parent_id

class

fertile

final

describe t_field;
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| Field     | Type        | Null | Key | Default | Extra          | Privileges                      |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| field_id  | bigint(20)  |      | PRI | NULL    | auto_increment | select,insert,update,references |
| class_id  | int(11)     |      | MUL | 0       |                | select,insert,update,references |
| type_id   | tinyint(4)  |      |     | 0       |                | select,insert,update,references |
| access_id | tinyint(4)  |      |     | 0       |                | select,insert,update,references |
| name      | varchar(64) |      |     |         |                | select,insert,update,references |
| value     | text        | YES  |     | NULL    |                | select,insert,update,references |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+

t_field

field_id

class_id

type_id

access_id

name

value

describe t_field_instance;
+-----------+------------+------+-----+---------+-------+---------------------------------+
| Field     | Type       | Null | Key | Default | Extra | Privileges                      |
+-----------+------------+------+-----+---------+-------+---------------------------------+
| field_id  | bigint(20) |      | MUL | 0       |       | select,insert,update,references |
| object_id | int(11)    |      | MUL | 0       |       | select,insert,update,references |
| value     | text       | YES  |     | NULL    |       | select,insert,update,references |
+-----------+------------+------+-----+---------+-------+---------------------------------+
t_field
Stores data for instances of a field.
field_id
The field_id from the t_field table.
object_id
The object_id from the t_object table.
value
The value of this instance of a field.

describe t_method;
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| Field     | Type        | Null | Key | Default | Extra          | Privileges                      |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| method_id | int(11)     |      | PRI | NULL    | auto_increment | select,insert,update,references |
| class_id  | int(11)     |      | MUL | 0       |                | select,insert,update,references |
| type_id   | tinyint(4)  |      |     | 0       |                | select,insert,update,references |
| access_id | tinyint(4)  |      |     | 0       |                | select,insert,update,references |
| name      | varchar(64) |      |     |         |                | select,insert,update,references |
| code      | text        | YES  |     | NULL    |                | select,insert,update,references |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
t_method
Describes a method defined on a class.
method_id
The method's identification field.
class_id
The class_id from the t_class table. The class on which the method is defined.
type_id
The type returned by the method.
access_id
The access type allowed by the method as defined in the t_access table.
name
The name of the method.
code
The actual method source code to be interpreted.

describe t_method_arg;
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| Field     | Type        | Null | Key | Default | Extra          | Privileges                      |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| arg_id    | bigint(20)  |      | PRI | NULL    | auto_increment | select,insert,update,references |
| method_id | int(11)     |      | MUL | 0       |                | select,insert,update,references |
| type_id   | tinyint(4)  |      |     | 0       |                | select,insert,update,references |
| name      | varchar(64) |      |     |         |                | select,insert,update,references |
| idx       | tinyint(4)  |      |     | 0       |                | select,insert,update,references |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
t_method_arg
The method argument definitions for a method.
arg_id
The identifier for the argument.
method_id
The method associated with this argument.
type_id
The argument type.
name
The argument name (variable name passed into the method).
idx
The argument order or index in the method call. Should not be duplicated for each method_id.

describe t_object;
+-----------+---------+------+-----+---------+----------------+---------------------------------+
| Field     | Type    | Null | Key | Default | Extra          | Privileges                      |
+-----------+---------+------+-----+---------+----------------+---------------------------------+
| object_id | int(11) |      | PRI | NULL    | auto_increment | select,insert,update,references |
| class_id  | int(11) |      | MUL | 0       |                | select,insert,update,references |
+-----------+---------+------+-----+---------+----------------+---------------------------------+
t_object
An instance of a class.
object_id
The unique object id (persistent id).
class_id
The class of the object.

describe t_object_alias;
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| Field     | Type        | Null | Key | Default | Extra          | Privileges                      |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
| alias_id  | int(11)     |      | PRI | NULL    | auto_increment | select,insert,update,references |
| object_id | int(11)     |      | MUL | 0       |                | select,insert,update,references |
| alias     | varchar(64) |      | UNI |         |                | select,insert,update,references |
+-----------+-------------+------+-----+---------+----------------+---------------------------------+
t_object_alias
Links object alias names ($object) to object ids.
alias_id
The alias id.
object_id
The associated object.
alias
The alias of the object.

describe t_type;
+---------+------------+------+-----+---------+----------------+---------------------------------+
| Field   | Type       | Null | Key | Default | Extra          | Privileges                      |
+---------+------------+------+-----+---------+----------------+---------------------------------+
| type_id | tinyint(4) |      | PRI | NULL    | auto_increment | select,insert,update,references |
| type    | varchar(9) |      | UNI |         |                | select,insert,update,references |
+---------+------------+------+-----+---------+----------------+---------------------------------+
t_type
The types in the language.
type
The type name (token).

Lists are stored in a serialized form: {val, val, val}. Lists are recrusively serialized and deserialized.

Schema

Also available as a JPEG in case you can't read PNG

Example of database queries

1. Get all the methods defined on a given object id:
   SELECT T_METHOD.method_name, T_METHOD.method_id FROM T_OBJECT, T_CLASS, T_METHOD
   WHERE T_METHOD.method_id in (SELECT T_METHOD.class_id in (
   SELECT T_CLASS.class_id FROM T_CLASS, T_OBJECT
   WHERE T_CLASS.class_id = T_OBJECT.class_id AND T_OBJECT.object_id = '1101'
   )
   )
   
   rebuild this as a proper join!!!

select method_name, method_id, class_id
  from t_method
  where class_id in
    (select parent_id
      from t_class
      where class_id = parent_id or
        class_id = 
          (select class_id
            from t_object where object_id=1)
    )