Persistence and Perseverance

You may have been wondering where I've been for the last month or so. You may not have been wondering, and that's the more likely case, and that's fine. I've been working on a single, large change. I'm using the term "single" here somewhat loosely, in the nature of a revisioning system. That is, I've made only one checkin in the last month or so.This particular change is one that's been the bane of my existence for much longer than that.

I will describe the nature of the problem the same way I described it to my friend Odie the other day. This was actually the catalyst that helped me finally get around to figuring it out and finishing it. The problem has to do with loading various parts of world data from persisted storage. Characters, mobs, dealies (objects), and rooms all live in data files rather than being hard-coded into the code. I've unofficially described an XML format that the area files are created in. Builders will be able to modify the files by hand, using some special tools, and probably through an On-Line Creation system (OLC) like most MUDs have. I chose XML because I prefer how it looks to YAML, which was also in the running, and because it represents most of the relationships between pieces of data in the MUD pretty concisely--but that's a discussion for another day.

There are several types of dealie that will be loaded from disk, but the most complicated at this stage is a container (bag, box, etc.), which can contain other dealies (including other containers). So I need a way to get container dealies out of files and into the MUD. Let me state the premises for this problem.

The Problem

1. For ease of building, every dealie has a prototype defined in the data file. The prototype describes the default attributes for that dealie, like a template. Nevertheless, it's kind of an abstract thing. You can't find a dealie prototype in the actual game world.

   Here is a sample dealie prototype:

   <dealie_prototype order="1">
       <kind>food_proto</kind>
       <lid area_name='main' local_id='10'/>
       <keywords>
           <keyword order="0">barn</keyword>
           <keyword order="1">cover</keyword>
           <keyword order="2">roof</keyword>
       </keywords>
       <short_description>the cover for a barn</short_description>
       <long_description>The spare roof of a barn is here.</long_description>
       <nourishment>10</nourishment>
   </dealie_prototype>

   Note the LID (local ID) given above. This uniquely idenfies this kind of XML-readable thing througout the MUD. There cannot be another prototype with LID main.10 in the world or else it's an error in the area file.

2. Anywhere a dealie is needed, it references its dealie prototype, and then overrides any properties it wants to change for that instance.

   Here is a dealie that does not override any properties of the prototype:

   <item order="1">
       <kind>food_dealie</kind>
       <proto_lid area_name="main" local_id="10"/>
   </item>

   Here is a dealie that does override some properties:

   <item order="2">
       <kind>food_dealie</kind>
       <proto_lid area_name="main" local_id="10"/>
       <keywords>
           <keyword order="0">surprise</keyword>
           <keyword order="1">super</keyword>
       </keywords>
       <short_description>a surprise!!!</short_description>
       <long_description>a surprise lies here</long_description>
   </item>

   Note the proto_lid element, which points to main.10. Anything not overridden in this place will fall back to its value from the prototype. It's a convenient way to make minor modifications to dealies. Allowing individual dealies to be customized locally allows for things like restrings, which are nice to have.

3. A prototype must have values for all of the properties of its type explicitly in the XML. That is, if a dealie does not override some property explicitly, it must be able to find a value for it in its prototype.

4. There is a kind of dealie called a container dealie. It's not really a special kind, but it is a specific kind. It is able to contain other dealies inside it. Since a container dealie itself is a kind of dealie, container dealies can contain other container dealies.

5. A container prototype can be defined with a set of default contents. Think, "a bag full of cheese." Here is a container prototype definition.

   <dealie_prototype order="5">
       <kind>container_proto</kind>
       <lid area_name='main' local_id='6'/>
       <keywords>
           <keyword order="0">pathological</keyword>
           <keyword order="1">sack</keyword>
       </keywords>
       <short_description>a pathological sack</short_description>
       <long_description>This sack is full of junk, and is the
           bane of all existence.</long_description>
       <max_num_dealies>5</max_num_dealies>
       <max_weight>10</max_weight>
   
       <default_contents>
           <kind>dealie_bag</kind>
   
           <item order="0">
               <kind>food_dealie</kind>
               <proto_lid area_name="main" local_id="1"/>
           </item>
           <item order="1">
               <kind>food_dealie</kind>
               <proto_lid area_name="main" local_id="10"/>
               <current_nourishment>1</current_nourishment>
           </item>
       </default_contents>
   </dealie_prototype>

   The default contents of this prototype are two food dealies. If this sack is referenced somewhere, it will by default have two food dealies inside.

6. Since you can override attributes when instantiating dealies, you can likewise override the contents of a container when you instantiate a container dealie. Here is a container dealie that is overriding the prototype's default contents.

   <item order="0">
       <kind>container_dealie</kind>
       <proto_lid area_name="main" local_id="6"/>
       <contents_bag>
           <kind>dealie_bag</kind>
   
           <item order="0">
               <kind>food_dealie</kind>
               <proto_lid area_name="main" local_id="3"/>
           </item>
       </contents_bag>
   </item>

7. In the previous point I made a container dealie that overrode its prototype to instead contain a single food dealie. But the following works (or should work) too:

   <dealie_prototype order="4">
       <kind>container_proto</kind>
       <lid area_name='main' local_id='7'/>
       <keywords>
           <keyword order="0">junky</keyword>
           <keyword order="1">sack</keyword>
       </keywords>
       <short_description>a junky sack</short_description>
       <long_description>This sack is full of tons of junk.</long_description>
       <max_num_dealies>5</max_num_dealies>
       <max_weight>10</max_weight>
   
       <default_contents>
           <kind>dealie_bag</kind>
   
           <item order="0">
               <kind>container_dealie</kind>
               <proto_lid area_name="main" local_id="7"/>
               <contents_bag>
                   <kind>dealie_bag</kind>
   
                   <item order="0">
                       <kind>food_dealie</kind>
                       <proto_lid area_name="main" local_id="3"/>
                   </item>
               </contents_bag>
           </item>
       </default_contents>
   </dealie_prototype>

   In this little gem, the prototype contains an instance of itself (albeit with an overridden contents). This scenario is the essence of the difficulty of what I've been working on. There's a cyclic nature to loading this data, coupled with ability to define things at different levels that puts the devil into the details. What solution would you use to tackle this?

8. I should state formally that even though this is a somewhat cyclic problem, we're dealing with "real" items, so the cycle has to be terminated at some point. In the case above, finally the inner bag is overridden so that the container simply doesn't contain itself. That is illegal.

The Solution

Now I'll try to describe the solution I implemented to this problem (thank god it seems to be working now).

Each thing that needs to be loaded from persisted storage has attributed to it 0 or more properties.

Each property is a collection of several values of interest: the XML element name used to locate it within its parent node; a pointer/reference to where the actual data will be stored; the datatype of the property; and a pointer to a "fallback" location.

The fallback pointer is used for a dealie when it's NOT overriding a value. The fallback pointer in that case points to the corresponding value in its dealie prototype. The way to read it is: when setting this value, if the value is not defined explicitly in the XML, it is instead stored in the prototype.

1. We start by loading up the full XML of all the areas defined. We go to every top-level prototype element in the XML and try to load the prototype (elaboration to follow). The attempt to load the prototype reports as to whether the prototype is fully loaded. When all prototypes are fully loaded, we're done loading prototypes.

2. To load a single prototype, we first create a "skeleton" instance of it. Hereafter, we will fill in its properties as we can load them. So we iterate through its properties. The property has a pointer to where it should be loaded, so we can check whether the property has been set yet (null or non-null). If it hasn't been set, we try to load it.

3. Properties are defined with the XML to locate it within the parent node, so we have enough information to figure out if the property is defined in the XML. If the element is not defined, we check the fallback. If the fallback is not defined either, we skip loading this property for now and come back to it in a later pass.

4. If the property has been located, we can instantiate a new "skeleton" object for the property. Depending on what kind of datatype it is, we may be able to fully create it on the spot (numbers, strings, and other simple types).

5. At this point, if we've been able to create an object for the property, we can use the property's pointer to the actual location to set it.

6. Again depending on the data type, the object we just set may be fully created (simple types) or may have sub-properties that need to be loaded. In the latter case, we recursively call loadProperties for each of the object's sub properties.

7. It's kind of handled as a special case, but after the first pass through, we expect to have all "simple" properties of the top-level prototypes loaded. At this point, we register them all in a global lookup by LID. Thereafter, when a dealie needs to find its prototype, it looks up the LID to find the (possibly only partially defined) prototype object.

8. Since there has to be a termination to container cycles, we are guaranteed to make some progress every pass through. After some number of passes, eventually all the properties of all the objects will be loaded.

It's not efficient in the slightest, but it gets the job done. I may optimize it eventually, but since this loading phase happens before the network socket is even opened up, it doesn't affect anyone if it takes a performance hit. I'm worried, however, that with hundreds or thousands of items it may take on the order of minutes to start up the MUD. That's not really acceptable.

Some of you Ruby-savvy folks may have noticed my use of the word "pointer" above and wondered what I was talking about, since Ruby doesn't have pointers. Okay, you caught me. I didn't really use pointers. Conceptually what I needed was for an object to be able to store the location in another object that I could read from and write to. The way I implemented it is with a getter and setter method. Each property stores a proc that references something like @value to get the value, and another one that sets @value to something.

It's actually incredibly clunky to code with, and I really want to streamline it, since each property I create has to have up to three such methods defined (getter, setter, and fallback). Take a look:

procGetShortDescription = lambda {
    self.shortDescription
}
procSetShortDescription = lambda { |val|
    self.shortDescription = val
}
procFallShortDescription = lambda {
    self.proto() && self.proto().shortDescription()
}

@props << PersistedProperty.new(
              'short_description',
              procGetShortDescription,
              procSetShortDescription,
              String,
              procFallShortDescription)

Yuck! I really wish I had pointers right now. At one point I actually created a pointer type class. I've yet to decide if I'll actually use it. It's quite small. Here's its implementation.

def ref(sym)
    return Ref.new(lambda { |*val|
        if val.length > 0
            eval("#{sym.id2name} = val[0]")
        else
            eval(sym.id2name)
        end
    })  
end
        
class Ref
    def initialize(block)
        @block = block
    end
    
    def r()
        @block.call()
    end # function r

    def r=(val)
        @block.call(val)
    end # function r =
end

Other Miscellanea

Everything I talked about in here had to do with dealies, but mobs are equally important. I similarly added properties and such to mobs so that they can fit into the same algorithm. I probably won't be running into a cyclical problem with mobs anytime soon, though...

I have a lot of cleaning up to do with the code. There are a few things not represented using properties that really should be. For instance, room exits (connections between rooms) are currently handled separately, but ought to be able to be represented by properties easily enough.

I haven't done the work to allow for saving much to disk. The basic code is in place to save characters, but not inventories and other things that you'd want to save. I've toyed with the idea of a persistent world that never returns to some weird default state like most MUDs do. There are a lot of potential pitfalls there, so I'll need to consider the implications more before going off and typing some words.

Mostly, I'm just glad I finally got this basically solved. I had it solved badly for months and really wanted to get it out of the way so I could work on more interesting things... like mobprogs.