A Sandbox to Play In

The current “accepted best definition” of a game universe for persistent worlds is “sandbox.” This means a malleable environment with lots of toys which players can then use to make whatever they want to out of the environment–as much as the game allows, at any rate. The ideal of the designer, then, is to provide a wide array of toys that suit the sort of environment that they intend. There are however many ways to do this, and they all have to do with how the virtual world in question handles data storage. While all virtual worlds must offer a modicum of persistence, there are lots of different levels of persistence to consider, and they all have radically different impact on the overall design.

For the purposes of discussion, one can break persistence into three levels: persistence of the world proper, persistence of avatars and their possessions, and lastly, persistence of items that are not avatars. Properly ordered, the world encompasses the objects that encompass the characters. The very earliest muds had persistence of the world, but lacked persistence of the other two. AberMUDs, for example, were originally scavenger style games wherein the entire world “reset” periodically. There was, therefore, no real way to make a mark on the world within the game’s context. Many of the player-vs-player combat muds do not offer character persistence either: avatars are persisted only in the sense that some of their career statistics for kills might be saved, but essential elements of the avatar such as acquired skills have to be relearned at the start of each match.

The key thread here is that these are session-based games. All that is required for a game to cease being session-based and become a true persistent world is persistence of characters. Note that persistence of the “second layer” (objects that are not characters) is not in fact required; in fact, few games do this, and those that do are termed muds that save world state. World state muds are generally limited to those that allow users to build in the world while the game is running.

In the diagram, you can see that even though there are three layers defined, what we really have is a spectrum, and one on multiple axes at that. It is easy to find examples of muds that make player’s corpses persistent, whilst leaving other types of objects as ephemeral; this because of player outcry when the mud crashes before they have recovered their items from the corpse. You can find many examples of muds wherein the code simply does not offer high degrees of user modifiability of the world, obviating the need for persistence of many elements; and examples of muds where user-created content is commonplace, requiring a high degree of persistence. Likewise, it is easy to find examples of muds which offer the technology sufficient for persisting absolutely everything in the virtual world, but which choose not to do so in order to simplify either database maintenance or the process of approving changes to the world as being fitting with the world’s theme. Some mud codebases, such as LP, rank high on both scales even though in practice they are most often used in a manner consistent with muds of the Diku codebase which is low on the scale. Early LPs did not properly persist characters, in fact!¹

The Tiers of Data Storage

As this quickly gets tangled, the easy way to think of it is the three tiers of storage: world, objects, and avatars. It is then easy to trace the evolution of mud codebases as they gradually move from persisting only the world, to persisting the world and also avatars, then also persisting some objects, and lastly, saving what we term world state, which is all data in the virtual environment.

The first thing worth noting here is that some of the earliest muds did not provide persistence of the avatars. Today this is taken for granted, but some of the earliest muds were in fact often little more than session-based scavenger hunts. You can see the remnants of this style of design in the requirement that you bring treasure in an AberMUD to the “well” at the center of the map. This design was likely inspired by the original Zork, wherein you scored points by placing found treasures in the trophy case in the little white house. The world itself is drawn from a static database, and therefore could technically be said to not persist at all, but merely be recreated anew at every time the server boots. In other words, the world data is instantiated from a template.

As avatar persistence became more important, we came to muds like the (extremely large) family of DikuMUDs.² In these muds, avatar advancement and development is the sole point of the activity—they are goal-oriented experiences based around achieving arbitrary levels and slaying monsters. This also requires the storage of specific other items, those carried by avatars as they go about their business: the part of the profile termed “equipment.” The world is still drawn from a static template database, as are in fact the monsters and swords and other items, but now text flat files are maintained of characters (the avatar’s tangible attributes and profile). The profile eventually expanded, in some muds, to cover objects that were not actually part of the avatar in any way, such as the avatar’s corpse, or specific objects located in special rooms termed lockers, or rooms tied to the avatar (instances of what we’d call player housing). Given time, dynamic elements would be added to Diku-derived muds in that online map building tools, commonly termed OLC, would be added to the stock code distributions. However, Dikus had already been leapfrogged by that time by two other codebases: LP and MUSH.

In LP and MUSH systems, the world is no longer a static database. Instead, it is a dynamic entity; rooms in these systems are actually code objects and can be modified on the fly; this can be termed an aggregated world as opposed to a template-driven world. For various reasons, MUSHes tend to be used as social spaces whereas the commonest use of an LP is to attempt to emulate the play mechanics on a Diku. However, in both cases the ability to build is generally restricted: even though the code architecture allows free creation of objects, new object classes, and new rooms on the fly, only certain players are given permission to do so. Hence, they offer a less dynamic environment than more evolved codebases.

Said more evolved codebase is called MOO, for “mud, object-oriented.” MOOs allow any user whatsoever to write code objects, and there code objects make up the map, the objects, and yes, even the avatars in the space—on a MOO, any user can actually write a new player class that redefines the nature of the tangible attributes of an avatar.³ Absolutely everything is persisted to the database.

This is obviously the sine qua non of virtual spaces: complete freedom to rewrite the digital space at any time, with every action persisting until changed. But it also reveals the key problems of world-state muds: database bloat and content approval. With the ongoing additions of new objects that all must be persisted, the amount of data persisted continues to increase⁴ — and worse, all the code there means that likely every object must be covered by an update loop in order to keep cycling through the code that it may be executing. This leads to lag, which is the slang term for slowdowns in the virtual space. On many MOOs, you are greeted by a message giving you the current loop time for the mud! Flexibility comes at a price, and many muds back away from full world-state simply to minimize lag and save hard drive space and memory footprint.

The other problem is whether all that content is worth it at all. If you are running an environment that you hope to make themed or fictionally consistent, allowing free content creation by any user is disastrous. The cost of vetting every piece of user building quickly grows prohibitive. Hence many muds back away from user building in order to maintain creative control; Ultima Online opted to allow building only with fairly large and complex pieces so that the designers could be ensured of a somewhat reasonable aesthetic in the world. It did, however, persist every single rabbit and sword left on the ground and scrap of cloth forgotten at the bottom of some chest—arguably, for no good reason at all.

Muds which have this high degree of persistence actually permit the rules of the environment to be rewritten on the fly; the only codebase to make this clear is LPMuds, where there is a division by convention between the mudlib or core game rules (which are dynamic) and the game objects (which are also dynamic).

Overall Mud Architecture

It should be clear now that for any instance involving data in mud design, there are basically two paradigms for handling the data. One of them is dynamic, flexible, and powerful; the other is simplistic but much easier to use. In understanding these two systems, it helps to understand how muds tend to be architected generally. And to do that, it helps to have a lot of diagrams!

A mud is essentially a server that responds to input from a client, and then makes changes to a database it is holding in memory. It also saves aspects of this database to disk in order to persist elements that are worth persisting. It may also have another, different, database, wherein templates for objects and rooms and other such materials for the environment are stored. We can term these two databases the persistence database⁵ and the template database.⁶ Calling these databases doesn’t mean to imply that they are actually transactional databases, SQL, Oracle, or anything of the sort. Often they are merely aggregations of text files.

Generally, the server saves data to the persistence database periodically (and maintains a copy in memory for speed, in most cases, though there are some fully disk-based systems). It reads from the persistence database anytime it needs to access data that it does not have in memory—server boot, for example, and perhaps also when individuals log in, items are retrieved from storage, etc. It only reads the template database once, however, at server boot, and uses the information in this database to create objects in the likeness of the templates from then on.

Some mud designs, notably the ones which use aggregated maps and an object-oriented system, conflate the two databases. There is no template database; instead, everything goes into the persistence database. Every object in the game must therefore be a unique creation or be a copy or modified copy of something else in the persistence database. This is, of course, an object-oriented approach—but it’s a memory hog. And even these systems usually have a set of object primitives that you can use basically as templates in the creation of new objects.

For the purposes of discussion, it helps to not conflate these two databases even if your architecture actually does, just so that the relationship between them and other components of your server is clear.

Now, it should be evident that any client-server relationship implies that there’s a part of the server that does nothing but talk to the client. This is often called a packet handler, a nanny, or the network layer. Either way, it’s a very basic component of a mud. So basic, that in fact it’s one of the most similar bits of code from mud to mud. It’s also one of the least understood, generally.

You can think of this network layer as being part of the core engine of a mud. It’s not the only part, however. There’s also a large part of the game code which is similarly generic in that it cares not what the mud visible to the players looks like. It’s the guts of the mud, what handles simple concepts like “here” and “now.” It’s what determines not just the shape of objects, but the fact that there are objects at all. This part of a mud is generally called the driver.

In many muds, the principal role of the driver is to serve as a script execution engine. It isn’t about defining the physics of a given world—rather, it is about defining the rules by which physics can be written. It provides a language and a framework in which the game’s laws of nature can be crafted. Drivers therefore tend to be pretty heavy-duty code, obscure and difficult for most to manage, replete with technical mumbo-jumbo such as compiler theory, interpreted language parsing, memory management, and garbage collection. Few hobbyist programmers mess around with drivers.

Above the driver comes a layer that is far more amenable to modification. This is the portion of the mud that defines the laws of nature: things like what a character is like, what an avatar looks like, what “looking” means. The commonest term for this is mudlib, a term from the LPMud codebase. LPs are the muds with the clearest line between driver and mudlib, and hence make a handy reference point. In the MOO world, LambdaCore is a good example of a mudlib. Writing new mudlibs is hard, and they are few and far between. They provide an interface for the mud designer to craft their own mud on top of the base.

Some mudlibs are written in C++ or C. Some are written in whatever language the driver supports as an embedded scripting language. Drivers themselves are almost never written in the embedded script language for speed and security reasons. What lies above a mudlib can be entirely written in the script language, and indeed may be best done that way. After all, what is above the mudlib is the skin of the mud: the face it presents to the world. And this is the part that you want to be most easily mutable.

The line between driver and mudlib, and the line between mudlib and game-specific code, exist for a very good reason. By replacing a mudlib without having to rewrite the driver, you gain the ability to radically alter the capabilities of a mud with a minimum of fuss. A well-designed mud will allow you to replace niceties such as how time works, what the data structure is for an avatar, and so on, with relative ease. Even Diku muds, which have no formal split, have code files segmented such that making this sort of change is relatively trivial. And of course, the difference between a mudlib and what goes above it is even more critical. Countless muds have been written with a package that supplies essentially a complete driver and mudlib—these many muds are all as different from one another as fingerprints, because ultimately, it’s the data and the custom code above a mudlib that really make it appear different to a user.

All of the above history should make it clear that there are solid reasons to choose not to make what one would expect is a “true” persistent world. Well after the development of MOO, many codebases continue to be created which offer quite a great deal less flexibility. Similarly, Diku-derived muds, with their simplistic template-based system, are more popular for budding builders than the more complex object-oriented systems. One should not be snobbish about these differences in architecture, but instead should evaluate the options based on what one seeks to provide in the space they plan to run. Then design accordingly.

Design Patterns for Persisting Maps

There are basically three choices for architecting map persistence. They range from the static database, which has the most rigid structure, yet also offers the most control to the administrators; to the dynamically generated world, which has virtually no structure, but abdicates all control to the whim of the algorithms that construct the map.

The Static Map Database

The most basic form of map persistence is to draw the map from a static database. Since it is static, by its very nature it does not change and is therefore persistent. Most text mud systems like this are based on the concept of area files, which are text files that act like a flat file database. These files have a rigid structure which forces building the map to be a fill-in-the-blank exercise. This structure usually forces certain compromises: for example, exits to other rooms must be only in the cardinal directions—whatever directions the file format supports. Many muds have added support for directions other than the standard six,⁷ but you’re not going to get exits like “towards the castle” as you would under systems that are not template based. Your only choices are going to be those directions that the original designers of the file format supported. Most area file formats have come to encompass a wide range of options, but it is still a particularly constraining limit to have to work within.

Some advanced area files support the addition of blocks of code (generally in an embedded scripting language) to rooms to detect events and respond to them. Most are not that flexible, however, and require that instead scripted objects of some sort be placed in the room (these are sometimes termed daemons after the Unix terminology).

Most template-based map systems require that the entire game server be restarted in order to load new database entries into the game. Even those servers which can do it on the fly do so by essentially running their startup routine without dropping active connections. Some area files require compilation into binary form before use.

By their very nature, template-based systems demand a high level of centralized control. They preclude expansion of the world by ordinary players, as there is a degree of access to the server and its execution space required in order to add an area. Many muds have added systems for online map creation, usually termed OLC, but all these do is use the mud itself as a medium for creating the static data file and placing it on the server. A template-based system, by its very nature, does not encourage community contribution to the database.

It may seem that template or static database systems are overly restrictive and that there’s no way that a modern mud architecture would make use of them. However, it’s worth considering that the nature of graphical environments is such that they are ideally suited for exactly this sort of system. In fact, most of them rely on exactly this sort of static data file existing on both client and server,⁸ making the task of updating the map even more difficult. In particular, 3d environments often require some form of compilation in order to optimize them.

The central control paradigm required by template-based systems makes them ideal for servers where a degree of thematic consistency is required, since they require an administrator to install them, and they are easily checked since they are wrapped up in a tidy little package. This also means that it is fairly easy to put together a template-based mud by simply obtaining individual area files which one likes, and putting them together in a database. This has led to the much-decried phenomenon of stock muds, which are muds built entirely out of other people’s work, with little to no glimmering of originality. However much we might dislike this phenomenon, it must also be admitted that the easy-to-use nature of template files has opened up mud design and administration to a wider range of people than would have otherwise been able to engage in it.

The Aggregated World

Usually, of course, a template-based mud is built up of the aggregation of many area files. A more sophisticated map system embraces the concept of the aggregated world and allows aggregation in smaller units, down to the room. Mud servers with a more object-oriented design such as MOO, MUSH, and LP, treat rooms as merely being an object. Objects can be added on the fly, resulting in sections of the map that appear to be coherent expressions of a single creator but which are in fact not, and are most likely not contiguous in the database either. The flexibility in such a system is immediately apparent; however, so are the weaknesses. As a result, there are basically two ways in which aggregated worlds are handled, and they are quite independent of the code implementation of the map system; the choice between a pre-designed and carefully managed aggregated world, and a user-contributed space defines the nature of the mud in a more fundamental way than the database implementation.

Most goal-oriented muds are centrally managed. In aggregated map systems, this means that creation of new space must be limited to only those individuals with special permissions granted by the mud administrators—generally, only the administrators themselves. In addition, for true coherency, you have to have some sort of central building authority that controls the quality of what is built. Most MUSHes set in popular fictional settings tightly control this sort of thing in order to make the virtual world emulate the fictional one as closely as possible.

Other systems prefer to let players simply build. This is the pattern of a social MOO, such as TinyTIM or LambdaMOO. However, because it is difficult to separate the wheat from the chaff, what typically happens on such a mud is an incoherent sprawl of database entries. This has led to the creation of central authorities even on free building environments.⁹ Since many aggregated systems tend to store everything in a giant flat file database, the entire world must exist in memory simultaneously, which can result in performance problems.

While it may seem that the aggregated world has much to recommend it, it suffers a great deal when the community that is building does not share from a single coherent vision. Even the most techno-anarchist of users might cringe at the idea of a virtual space that has no spatiality, no sense of scale whatsoever, no thematic coherence, and thus may be un-navigable except by the most diehard and patient of people. It is extremely common to see free-building MOOs declare a theme from the outset (HotelMOO, for example) and request that all subsequent building be done in the context of the world’s theme.

It’s worth noting that in general, aggregated systems are still treated as static. Once the data has been aggregated, it continues to exist. It’s not particularly portable from world to world, and it only goes away if some form of garbage clean-up is done on the database to remove spaces that are rarely used.

Aggregated systems are common in the text world, but not well suited to the graphical environments that are becoming more popular. The only major try at an aggregated graphical system was AlphaWorld. In this system, a gigantic coordinate space was built, and players were offered building tools to construct any buildings they chose on the surface.

The Dynamic World

The most exciting concepts in mud map design have never actually been implemented in publicly available servers. They all have to do with solving the problem of having an aggregated or dynamic space, but without the problems of fictional coherency, memory space bloat, or overly rigid templates. These sorts of systems are for continuous maps, and rely on one or both of the concepts of fixed random seeds and sparse arrays.

The concept of sparse arrays is simple: instead of having a database entry for every location on your grid, only have ones for those locations which have anything of interest. Then nearby locations can be constructed dynamically by looking at what is nearby on the coordinate grid. Sparse arrays lend themselves to environments such as wilderness or other natural areas where the majority of the environment can be assumed to consist of the same thing; then only those elements which are different can be superimposed upon the assumed default. Another way to think of this is that the sparse array serves as a delta, or list of changes, on a base map that does not actually exist but which is assumed to be completely uniform.

By itself, a sparse array serves to massively economize on the data storage required for a map. It also makes the tedious task of assembling a map much easier. But more exciting, perhaps, is the fact that the sparse array also can be far more dynamic than the traditional continuous map model. Since each entry in the database is identified with a key and a set of information defining what the entry involves, it is easy to move elements within the sparse array around on the map. This means that it is easy to make such a map dynamic. As an example, Ultima Online stored objects on the map in a sparse array, by simply keying each object to a location. But since one class of objects was actually buildings, it was possible to denote an entire structure on the map with a single database entry. And it could easily be moved or removed. In the case of a well-constructed textual mud, forests could move, trenches be dug, and other such radical alterations occur in the geography.

In a graphical system, sparse arrays leave something to be desired, since the level of detail required to make a compelling graphical environment is not really suited to a sparse array. You could certainly economize a great deal on your map storage, but you’re not likely to get appealing results unless the default against which the sparse array is placed is complex, rather than simple. And it has to be a complexity that is simply described. This is where we can introduce another concept that complements that of the sparse array.

The other concept is that of the fixed random seed. A good definition by J. C. Lawrence from the MUD-Dev glossary:

Fixed random seeding

Using a fixed value (such as a character’s unique ID, or the character’s position in XYZ space) to seed the random number generator, assuring that the same random number will always be rolled if the circumstances are exactly the same, but requiring no storage. This allows parts of the world or its behaviours to be dynamically generated from the seed value as needed, and yet to have each “new copy” be the same as all the others because the seed value hasn’t changed.¹⁰

To cut through the gobbledygook: the allegedly random numbers generated by a computer are not in fact random. They give predictable output given a seed number. Most computers get around this by rapidly rotating the seed values so that from moment to moment, the random number generator will actually give different results. But at best these are pseudo-random. And if you pass in a fixed seed rather than letting the computer pick a seed, then you can get predictable results for that seed every time. And if you generate your map from a fixed number so that you always get the same output, then you are in effect storing a full map with only one piece of data: the seed.

The basic principle in both sparse arrays and fixed random seeding is that of reproducible results from an algorithm given very little data. An example of the utility of fixed random seeding merged with a sparse array is demonstrated by Privateer Online, which planned to have literally millions of individual rooms, each with a continuous map fractally generated from a seed. Then buildings and alterations to the geometry are stored in a sparse array on top of that, permitting the world to be dynamic within the constraints of what the permissible alterations are. Naturally, a given entry in the sparse array might actually cover a fairly wide area. An element like “a radial circle of standing stones extending across 50 feet” might be represented by a single entry in the sparse array, and the code responsible for placing that element on the map could automatically handle such niceties as smoothing the terrain for the stones to be placed on—without actually having to store each vertex on the map.

The concept of adding detail as the map is examined more closely is of course highly suitable for both sparse arrays and fractal systems based on fixed seeds. Consider the system proposed by Lawrence for gradually populating a sparse array using a seed, based on frequency of usage of the area:

…the game-world and all its details are (generally) a random-seed generated thing with the depth of that simulation (and thus the expense of the modelling) being proportional to player activity there.

The first player sees an endless flat gray plain without distinguishing features, landmarks, interruption, or any other observable entity in existance other than himself.

As that player goes about trying to do things, and as other players join him, the world gradually (or rapidly) forms about them, growing out of the entropic raw chaos into something definite, knowable, and of specific type.

Player built constructs would then assume the same requires-regular-human-refreshing-to-persist models, so that, for instance, the road between a distant village and a local town would likely be a narrow path thru the formless void, with only the path and its immediate surrounds being well defined. The pleasing side-effect being, that should regular traffic between the town and village fall off for some reason, the path would tend to disappear, and the village might well become permanently “lost”.¹¹

Privateer Online was making use of similar effects, by allowing players themselves to expand the map (which really means letting them toss a new seed onto the pile). Cleaning up the database (which is far smaller a database than otherwise required) is then a matter of whether or not seeds are being instantiated into maps regularly—if not, then do not persist the greater detail. It is not a stretch to imagine a forest entry placed in the sparse array; and when you walk to a point in the forest, a fractal routine being used to add more detail, which can then be stored in the sparse array, but tagged as a higher level of detail so that it can be prioritized for recycling into unused memory.

There is little doubt in my mind that the future of online worlds is going to rely on concepts like fixed random seeding and sparse arrays, and others that are not yet developed. As of now, only a few ventures have attempted to make use even of these concepts,¹² so it is likely they will be state-of-the-art for quite some time.

---

1. Early versions of LPMuds saved off all tangible attributes of an avatar, but did not persist all elements of the profile; to be exact, equipment that the player had accumulated did not persist. Modern versions of the codebase do, of course, have this capability. ↩

2. Developed at the University of Copenhagen; the acronym DIKU translates out as a department of the university, in fact. ↩

3. The “Schmoo wars” of LambdaMOO are an example of this. A user on the MOO wrote a new player definition that included various simulations of limbs and appendages in order to better support tinysex. This led to great controversy in the playerbase. ↩

4. LambdaMOO used to measure elapsed time, in a historical sense, by the object numbers created. They actually have an outdated clause in their terms of service which says, in effect, “don’t create items just to run the number up, you’ll mess up the timekeeping.” ↩

5. This is also called the runtime database in some circles. For example, “playerfiles” in a DikuMUD, or the entire collection of objects accumulated in a MOO. ↩

6. At Origin, this is often called the master game database. In a Diku-derivative mud, it would be an area file. In Ultima Online , it’s text files that serve as templates for creating monsters and certain types of items. Its direct equivalent in paper gaming would be the Monster Manual, or whatever other book has the list of critters that can appear and what their statistics should be. ↩

7. Up, down, north, south, east, and west are the standard suite. ↩

8. This is done so that the map data, which in a graphical environment can be quite a lot of data, does not need to be streamed down over the wire. This results in lower costs for the company running the game. As commercial “massively multiplayer” games grow, so do the map sizes required by market pressures—the result is that the next generation of games is likely to exceed the storage capabilities of a CD by far, requiring footprints well above a gigabyte in size. ↩

9. Such as the Architecture Review Board on LambdaMOO. ↩

10. This definition can be found at http://www.kanga.nu/FAQs/MUD-Dev-L/34.html. ↩

11. From the MUD-Dev archives at http://www.kanga.nu/archives/MUD-Dev-L/1999Q4/msg00652.html. ↩

12. Hero’s Journey from Simutronics and Privateer Online, which was cancelled by Origin, both depended on fixed random seeding; the latter also made extensive use of sparse arrays layered on top of the generated map. In the text world, Discworld is a good example. ↩