In-depth: Concurrent World Editing, On The Cheap

[In this reprinted #altdevblogaday-opinion piece, Braid and The Witness developer Jonathan Blow shares how his team created a low-tech system for concurrent world editing of its open-world 3D game.] A small team with limited manpower, we wanted a low-effort way to use our existing version control system (svn) to facilitate concurrent world editing for our open-world 3D game (i.e. we desire that multiple users can edit the world at the same time and merge their changes).   We developed a system wherein the data for each entity is stored as an individual text file. This sounds crazy, but it works well: the use of individual files gives us robustness in the face of merge conflicts, and despite the large number of files, the game starts up quickly. Entities are identified using integer serial numbers. We have a scheme for allocating ranges of these numbers to individual users so there is no overlap (though this scheme could certainly be better). The system seems now to be robust enough to last us through shipping the game, with seven people and one automated build process concurrently editing the world across 18 different computers. We don't know whether this method would work for AAA-sized teams, though it seems that it might with some straightforward extensions. But for us the method works surprisingly well, given how low-tech it is. About the Game We have been developing a 3D open-world game called The Witness since late 2008. For much of that time, development happened in a preproduction kind of way, where not many people were working on the game. Recently, though, we went into more of a shipping mode, so the number of developers has grown: we're up to about 10 or 11 people now (pretty big for a non-high-budget, independent game). Not all of these people directly touch the game data, but about 7 do now, and this number will rise to 9 in the near future. The design of the game requires the world to be spatially compact, relative to other open-world games, so it is far from Skyrim-esque in terms of area or number of entities. At the time of this writing, there are 10,422 entities in the game world. I expect this number to grow before the game is done, but probably not by more than 2x or 3x the current amount. Because the world is not too big, and some game-level events require entities to coordinate across the length of the world, it makes sense to keep all the entities in one space, that is to say, there is no zoning of the world or partitioning of it into separate sets of data. This makes the engine simpler, and it reduces the number of implementation details that we need to think about when editing the world. It also introduces a bit of a challenge, because it requires us to support concurrent editing of the world without an explicit control structure governing who can edit what. One such control structure might be: if you imagine the world were divided into a 10×10 grid; so there are 100 different zones; and where anyone editing the world must lock whatever zones they want to edit, make their changes, check them in, then unlock those zones; this would provide a very clear method of ordering world edits. (Because of the locking mechanism, two people would not be able to change the same world entity at the same time, so there doesn't have to be any resolution process to decide whose changes are authoritative). However, the straightforward implementation of such a control scheme would make for inconvenient workflow, as it is tedious to lock and unlock things. Even with further implementation work and a well-streamlined UI, there would still be big inconveniences. (I really want to finish building a particular puzzle right now, but a corner of that puzzle just borders on some region that a different user has locked, and he is sick this week so he probably won't finish his work and unlock it until next week. Or, if my network connection is flaky then I may not be able to edit; if I am off the net then I definitely could not edit.) Thus, rather than implementing some kind of manual locking, I found it preferable to envision a system that Just Magically Works. Since we already used the Subversion source-control system to manage source code and binary source assets such as texture maps and meshes, it didn't seem like too big of a stretch for Subversion to handle entity data as well. The World Editor and Entity Data Our world editor is built into the game; you press a key to open it at any time. Here's what it looks like:

The editor view is rendered in exactly the same way as the gameplay view, but you fly the camera around and select entities (I have selected the red metal door at the center of the scene, so it is surrounded by a violet wireframe). In the upper right, I have a panel where I can edit all the relevant properties of this Door; the properties are organized into four tabs and here you can see only one, the "Common" properties. These properties, which you can edit by typing into the fields of this Entity panel, are all that the game needs to instantiate and render this particular entity (apart from heavier-weight shared assets like meshes and texture maps). If you serialize all these fields, then you can unserialize them and generate a duplicate of this Door. That's how the editor saves the world state: serialize every entity, and for each entity, serialize all fields. Originally, the game saved all entities into one file in a binary format. This is most efficient, CPU-performance-wise, and the natural thing that most performance-minded programmers would do first. Unfortunately, though, svn can't make sense of such a file, so if two people make edits, even to disjoint parts of the world, svn is likely to produce a conflict; once that happens, it's basically impossible to resolve the situation without throwing away someone's changes or taking drastic data recovery steps. Our natural first step was to change this file from binary into a textual format. Originally I had worries about the load-time performance of parsing a textual file, but this turned out not to be an issue. I decided to use a custom file format, because the demands in this case are very simple, and we have maximum control over the format and can modify it to suit our tastes. Many modern programmers seem to have some kind of knee-jerk inclination to use XML whenever a textual format is desired, but I think XML is one of the worst file formats ever created, and I have no idea why anyone uses it for anything at all, except that perhaps they drank the XML Kool-Aid or have XML Stockholm Syndrome. Yes, there are XML-specific tools out there in the world, and whatever, but I didn't see how any such tool would be of practical use to us. One of our primary concerns is human-readability, so that people can make intelligent decisions when attempting to resolve revision control conflicts. XML is not particularly readable, but we can modify our own format to be as readable as it needs to be in response to whatever real-world problems arise. You'll see a snippet below of the format we use. Evolution of the Textual Format The first version of our textual format was a straightforward adaptation of our binary format. The gameplay-level code that saves and loads entities is the same for either format; the only difference is just a boolean parameter, choosing textual or binary, which is passed to the lower-level buffering code. After the buffer is done being packed, it's written to a file. In our engine, entities are generally referenced using integer serial numbers (that act as handles). These numbers are the same when serialized as they are at runtime. Originally, in the binary file, the order in which the entities were written didn't matter. But if we want to handle concurrent edits, we want to make merging as easy as possible for the source control system, so we sort entities by serial number, writing them into the file in increasing order. Thus we didn't generate any spurious file changes due to haphazardly-changing serialization order. In theory, Subversion could now handle simultaneous world edits and just merge them, the same way it does with our source code. Unsurprisingly, though, this initial attempt was not sufficient. Though the file was now textual, it contained a bare minimum of annotations and concessions to readability. Though I knew I would eventually want to add more annotations, I didn't want to go overboard if it wasn't necessary, because these inflate the file size and the time required to parse the files (though I never measured by how much, so it's likely the increases are negligible performance-wise and I was engaging in classic premature optimization). As it happens, the kind of redundant information that increases human-readability also helps the source control system understand file changes unambiguously, so as we made the format more-readable, the number of conflicts fell. Here's what our file format currently looks like, for entity #6555 (the Door we had selected in the editor screenshot).

Door
72
6555
; position
    46.103531 : 42386a04
    108.079681 : 42d828cc
    8.694907 : 410b1e57
; orientation
    0.000000 : 0
    0.000000 : 0
    -0.069125 : bd8d9184
    0.997608 : 3f7f633d
; entity_flags
    160
; entity_name
    !
; group_id
    4059
; mount_parent_id
    6554
; mount_position
    0.035274 : 3d107ba5
    0.006069 : 3bc6e19c
    0.000038 : 381ffffc
; mount_orientation
    0.000000 : 0
    0.000000 : 0
    0.000027 : 37e5f004
    1.000000 : 3f800000

(The first line, "Door", is the type name; 72 is the entity data version, which is used to load older versions of entities as their properties change over time; 6555 is the entity's ID. root_z and cluster_id (seen in the screenshot) are not saved into the file, because these properties have metadata that say they are only saved or loaded under certain conditions which are not true here. For the sake of making the listing short, I've shown only the properties listed on that first tab in the screenshot.) You'll note that the floating-point numbers are written out a bit oddly, as in this first line under 'position':

    46.103531 : 42386a04

This is how we preserve the exact values of floating-point numbers despite saving and loading them in a text file. If you do not take some kind of precaution, and use naive string formatting and parsing, your floating-point values are likely to change by an LSB or two, which can be troublesome. The number on the left is a straightforward decimal representation of the value, written with a reasonable number of digits. The : tells us that we have another representation to look at; the number on the right, which the : introduces, is the hexadecimal representation of the same number. The IEEE 754 floating-point standard defines this representation very specifically, so we can use this hexadecimal representation to reproduce the number exactly, even across different hardware platforms. The decimal representation is mostly just here to aid readability. However, if we decide we want to hand-edit the file, we can just delete the : and everything after it, changing that first number to a 47.5 or something; seeing no :, the game will parse the decimal representation and use that instead. There are other ways to solve this floating-point exactness problem; for example, you can implement an algorithm that reads and writes the decimal representation in a manner that carefully preserves the values. This is complicated, but if you're interested in that kind of thing, here's what Chris Hecker says:

(Twitchy, and look at how much code that is! What we did is a couple of lines.) In a document on his web site, Charles Bloom discusses a scheme that was in use at Oddworld Inhabitants, similar to what we're doing in The Witness but involving a comparison between the two representations:

Subversion Confusion After switching to this format, conflicts still happened. I categorize conflicts into two types: "legitimate", where two people edit the same entity in contradictory ways and the source control system doesn't know who to believe; and "illegitimate", where Subversion was just getting confused. We did have a number of legitimate conflicts for a while, yet which were not the users' fault, because our world editor tended to do things that are bad in a concurrent-editing environment. (See the Logistics section at the end of this article for some examples). But even after we ironed these out, we still found that Subversion was still getting confused. Here's an example of a common problem: suppose we start with a world containing data on entities A, B, and D, so our file contains: ABD. You edit the file and delete entity B. I edit the file and also delete entity B, but add another entity C. (That we both deleted B may be a very common use-case, especially if this is due to some automatic editor function). So, you want to check in a file that just says: ABD – B = AD, so the new result is AD. I want to check in a file that says: ABD – B + C = ACD (the C goes in the middle, because remember, the entities are sorted!) In theory this is an easy merge: the correct result is just ACD. But Subversion would get confused in cases like this, requiring the user to hand-merge the file. This is a disaster, because even with a visual merge tool such as the one that comes with TortoiseSVN, you don't want non-engine-programmers trying to merge your entity data file. Even if that file is extremely readable, at some point someone will make a mistake; the file will fail to parse, and then you have a data recovery problem that requires the attention of an engine programmer. When this happens it kills the productivity of two people (the engine guy, because he has to merge the data, and also the guy who generated the conflict, because until it gets resolved his game is in an un-runnable state, and anyway, the engine guy has probably commandeered the other guy's computer to fix this). After we had this problem a few times too many, Ignacio suggested moving to a more-structured file format like JSON, which, in theory, source-control systems would handle more solidly. But I thought that this would only reduce the frequency of the problem, but not solve anything fundamental; even if we achieved a situation of only generating legitimate conflicts, each conflict would still be a potential game-crippling disaster. Splitting the File It occurred to me, finally, that it could hardly get cleaner than to store each entity in its own file. This initial thought might cause a performance-oriented programmer to recoil in horror; we have 10,422 entities right now, and it must be very slow to parse and load 10,000 text files every time the game starts up! But I knew that we already had over 4,000 individual files laying around for assets like meshes and texture maps, currently loaded individually, the idea being that at ship time we would combine these into one package so as to avoid extra disk seeks and the like. But on our development machines, these files still loaded quickly. I figured that if we can already load 4,000 big files, why not try loading an extra 10,000 small files? If loading all these files turned out to be slow, we could resort to this only when entity data has changed via a source control update; after loading all the text files, we can save out a single binary file containing all the entity data, which would be much faster to load, just like we used to do before we supported concurrent editing. I tried this and it worked great. So, now we have a data folder called 'entities', which holds one file per serialized entity. The Door selected in the editor screenshot is stored in a file named after its entity ID, "6555.entity_text", which contains the text you see in the listing above. As mentioned, there are currently 10422 entity files; the text files take up about 8MB of space, whereas the binary file is 1.4MB. We're not making any effort to compress either of these formats; they are very small compared to the rest of our data.

Benefits of Using Individual Files Storing each entity in a separate file solved our problems with merging: both the illegitimate source control confusions as well as the problems due to hand-guided file merging. The illegitimate conflicts go away because transactions become very clear. If I delete an entity, and you delete an entity, then we both just issue a file delete command, and it's very easy for the source control system to see that we agree on the action. Furthermore, if we both delete B but I add C, because the change to C is happening in a completely separate file, there is no way for the system to get confused about what happened. Legitimate conflicts do still happen, as multiple people edit the same entities, but these cases are much easier to handle than they were before. The usual response is to either revert one whole entity or stomp it with your own. Because we usually want to treat individual entities atomically — using either one person's version of that entity or the other's — individual files are a great match, because now the usual actions we want to perform are top-level source control commands (usually from the TortoiseSVN pulldown menu). Before, this wasn't true, and merging a single entity in an atomic way required careful use of the merge tool. If an entity ever gets corrupted somehow, for whatever reason, we can just revert that one file, knowing the damage is very limited in scope; before we've reverted it, the worst that can happen is that that single entity will not load; it won't prevent the rest of the entities in the world from loading. It would be difficult to overemphasize the robustness gained. I feel that these sentences do not quite convey the subtle magic; it feels a little like the state change when a material transitions from a liquid to a solid. Sometimes, someone will update their game data in a non-vigilant way; not noticing that a conflict happened, so they won't resolve it; and then they will run the game. Before, this would have been a disaster; Subversion inserts annotations into text files to try to help humans manually resolve conflicts (this is an unfortunate throwback to programs like SCCS), which would have caused much of the world to fail to parse. Now, though, the damage from these annotations is constrained to indivi