Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have an online game where players get to shape the world in some way - eg. Ultima Online's housing, where you get to build your houses directly onto certain parts of the world map. These are changes that should persist over time as part of the persistent world.

At the same time, the design team are adding new content and amending old content to improve and extend the game for new players. They will do this on a development server first during testing and then later have to merge their work in with the players' "work" on the live server.

Assuming we fix the game design issues - eg. players can only build in designated areas, so they never clash geographically with designer edits - what are good ways to handle the data or arrange the data structures so as to avoid conflicts when new designer data is merged in with new player data?

Example 1: a player crafts a new type of item, and the game assigns the ID 123456 to it. Instances of that item all refer back to 123456. Now imagine the game designers have a similar system, and a designer creates a new item also numbered 123456. How can this be avoided?

Example 2: someone makes a popular mod that gives all your dragons a French accent. It includes a script with a new object called assignFrenchAccent which they use to assign the new voice assets to each dragon object. But you are about to deploy your "Napoleon vs Smaug" DLC which has an object of the same name - how can you do this without a lot of customer service problems?

I've thought of the following strategies:

  • You can use 2 separate files/directories/databases, but then your read operations are significantly complicated. "Show All Items" has to perform one read on the designer DB and one read on the player DB (and still has to distinguish between the 2, somehow.)
  • You can use 2 different namespaces within one store, eg. using strings as the primary key and prefixing them with "DESIGN:" or "PLAYER:", but creating those namespaces may be non-trivial and dependencies aren't clear. (eg. In an RDBMS you may not be able to efficiently use strings as primary keys. You could use integers and allocate all the primary keys below a certain number, eg 1 million, to be designer data, and everything above that point to be player data. But that info is invisible to the RDBMS and foreign key links will cross the 'divide', meaning all tooling and scripts need to explicitly work around it.)
  • You can always work on the same shared database in real-time, but performance may be poor and the risk of damage to player data may be enhanced. It also doesn't extend to games that run on more than 1 server with different world data.
  • ...any other ideas?

It occurs to me that although this is primarily an issue for online games, the concepts may apply to modding too, where the community creates mods at the same time that the developers patch their game. Are any strategies used here to reduce the chance of mod breaking when new patches come out?

I've also tagged this as "version control" because on one level that's what this is - 2 branches of data development that need merging. Perhaps some insights might come from that direction.

EDIT - some examples added above to help clarify the problem. I am starting to think the issue is really one of namespacing, which could be implemented in a store via composite keys. That simplifies the merge strategy, at least. But there may be alternatives I'm not seeing.

share|improve this question
1  
I imagine the answer to this could depend at least in part on what type of data the designers are adding and what the players are adding. –  lathomas64 Feb 13 '12 at 14:07
    
It could, but I'm more interested in generic solutions to 2 parties both contributing to a single data store. –  Kylotan Feb 13 '12 at 14:15
1  
A lot of people are missing the point of this question - it's not players' changes that are conflicting: rather content updates etc. breaking existing layouts. @Kylotan am I right? –  Jonathan Dickinson Feb 15 '12 at 17:16
    
It's where developer content updates potentially clash with player content updates. I'm not really interested in game design workarounds (eg. only let players build in certain places) but in data structure workarounds (eg. only let players create things with IDs greater than 1 million). –  Kylotan Feb 15 '12 at 17:36
2  
You didn't specify, are you expecting to do real-time updates to a live world? A side note: 2 parties contributing to a single data store IS a database, that's what databases do, you can't get around that fact and it would be folly to ignore decades of knowledge about how to avoid problems with shared data. –  Patrick Hughes Feb 15 '12 at 18:04
show 6 more comments

7 Answers

up vote 2 down vote accepted
+250

I think the answers proposing DB solutions are jumping to a specific implementation without understanding the problem. Databases don't make merges easy, they just give you a framework in which to store your data. A conflict is still a conflict even if it's in an DB. And checking out is a poor man's solution to the problem - it will work, but at a crippling cost to your usability.

What you are talking here falls into the distributed development model of problem. The first step I believe is not to think of players and designers as being separate types of content creators. That removes an artificial dimension to your problem that doesn't affect the solution.

Effectively you have your mainline - the canonical, developer approved version. You may (probably) also have other branches - live servers were people are actively developing and sharing mods. Content may be added on any branch. Crucially, your designers are nothing special here - they're just content creators that happen to live in-house (and you can go find them and hit them when they screw up).

Then accepting user generated content is a standard merge problem. You have to either pull their changes back onto the mainline, merge, then push out again, or pull the mainline changes onto their branch and merge (leaving the mainline 'clean' of user generated stuff). As usual, pulling to your branch and fixing there is more friendly than asking other people to pull your changes and then trying to fix it remotely on their end.

Once you're working with that sort of a model, all the normal processes about avoiding merge conflicts apply. Some of the more obvious:

  • Encourage liberal use of name-spaces to ring-fence content from a particular author / mod / team.
  • Where content needs to interact, establish clear calling / usage conventions, naming conventions, and other loose 'rules' that guide development so that it is easy to merge back. Provide tools that allow content creators to know if they're following those rules, ideally integrated into the content creation itself.
  • Provide reporting / analysis tools to spot likely merge failures before they happen. Fixing it post merge is probably very painful. Make it so that a particular bit of content can be checked and given the all clear as merge-ready, so that the merge is painless
  • Make your merging / integration robust. Allow easy rollbacks. Do rigorous testing of merged content: if it fails testing, don't merge it! Iterate either their content or yours until the merge will go ahead cleanly.
  • Avoid using incremental integer IDs for anything (you don't have a reliable way of doling them out to creators). That only works in a DB because the DB itself is a canonical provider of IDs so you never get duplicates; however it also introduces a single point of failure / load in your system.
  • Instead use GUIDs - they cost more to store, but are machine specific and so will not cause collisions. Alternatively use string identifiers, this is much easier to debug / resolve, but more expensive for storage and comparison.
share|improve this answer
    
Sadly some of this is not helpful to my problem (eg. having players follow certain rules, as this all has to be done automatically server-side) and I don't think it will be practical to support the degree of merge management and transactional semantics you mention, but the general approach of allocating guaranteed unique IDs, maybe GUIDs, is probably closest to what I'll go with. –  Kylotan Feb 17 '12 at 0:45
    
Ah, I see. Well since you control their building tools, at least enforcing those merge-friendly approaches (namespaces, etc.) is something you can do without the players having to agree. –  MrCranky Feb 17 '12 at 11:40
    
What do you do if two players create duplicate content? Or are separate instances of your gameworld treated as unique? In which case perhaps it's a helpful approach to automatically check every unique instance that you know of against your core/mainline branch for conflicts that will happen when you push out those changes to the instances. If you can't control the players, you can at least warn your internal team that the work they're doing conflicts with instance X of the world, early on in development. –  MrCranky Feb 17 '12 at 11:41
    
The concept of namespaces is not so much the problem - picking adequate namespaces from the namespace of all possible namespaces is! :) And duplicate content for me is not a problem - it's just 2 instances of something which are equivalent. The important thing is that no damaging merges or overwrites occur. As for automatic collision checks, that stops the damage done in the write, but doesn't solve the original naming problem. (Renaming things to avoid a collision may be non-trivial, due to cross-referencing.) –  Kylotan Feb 17 '12 at 13:02
    
Ah yes, I see now, it's not the namespaces themselves so much as the choice of name. In that case, GUIDs are probably the answer again - have content effectively kept in its own little area. A decorative name can be given, but the game would use the GUID. –  MrCranky Feb 17 '12 at 15:06
show 2 more comments

If the files for the data are text as opposed to binary and the designers and players are modifying different areas you could try an SVN merge.

share|improve this answer
add comment

I think a database/filesystem replicated across environments with a 'check-out' procedure would be best.

So, whenever a designer wants to make some modification to the world, he would check-out/lock all assets he wants to create/modify on all copies of the database (development and production), so no other player or designer could modify it. He would then work on the development database until the new design is finished, and at that time the changes would be merged with the production database and those assets would be checked-in/unlocked in all environments.

Player edits would work in much the same way, except the database/filesystem roles would be reversed - they work on the production database, and all updates are uploaded to dev when finished.

The asset locking can be limited to the properties where you want to guarantee no conflicts: in Example 1, you'd lock ID 123456 as soon as the player starts crafting it, so the developers will not be assigned that ID. In Example 2 your developers would have locked the script name assignFrenchAccent during development, so the player would have to chose a different name when developing his modification (that small nuisance can be reduced by namespacing, but that by itself will not avoid conflicts unless you give each user/developer a specific namespace, and then you'll have the same issue with managing the namespaces). This does mean that all development would have to read from a single on-line database, but all you require from that database in these examples are the object names, so performance should not be a problem.

In terms of implementation, having a single table with all keys and asset state (available, locked from dev, locked from prod) synchronized/accessible in real-time across environments should be enough. A more complex solution would implement a complete Version Control system - you can use an existing system like CVS or SVN if your assets are all in a filesystem.

share|improve this answer
    
Usually it's not practical to lock any data globally - players may be editing the world just through normal play, and you wouldn't want that play to stop designers from being able to work. If you allow global locks, then a merge operation is basically an overwrite operation, which is easy - but if you don't have global locks, what then? –  Kylotan Feb 15 '12 at 15:25
    
As lathomas64 mentioned, the answer would depend on what kind of data you are talking about. Without global locks I would think you would have to have a versioning system and a set of rules to resolve any conflicts - these rules would depend on the data and gameplay requirements. Once you have those, I guess every merge reduces to a simple overwrite operation. –  SkimFlux Feb 15 '12 at 15:58
add comment

Store everything as an attribute (or decorator) - with mount points. Let's take a house the player has designed as an example:

o House: { Type = 105 } // Simple square cottage.
 o Mount point: South Wall:
  o Doodad: Chair { Displacement = 10cm }
   o Mount point: Seat:
    o Doodad: Pot Plant { Displacement = 0cm, Flower = Posies } // Work with me here :)
 o Mount point: North Wall:
  o Doodad: Table { Displacement = 1m }
    o Mount point: Left Edge:
     o Doodad: Food Bowl { Displacement = 20cm, Food = Meatballs}

So each entity can have one or more mount points - each mount point can accept zero or more other components. This data would be stored with the version that it was saved at, along with the any relevant properties (such as Displacement etc. in my example) - NoSQL would likely make a really nice fit here (Key = Entity ID, Value = Serialized Binary Data).

Each component would then need to be able to 'upgrade' old data from a previous version (never remove fields from serialized data - just 'null' them) - this upgrade happens the minute it is loaded (it would then be immediately stored back in the latest version available). Let's say that our house has had it's dimensions changed. The upgrade code would relatively work out the distance between the north and south walls and proportionally alter the displacements of all the contained entities. As another example our meat bowl might have the 'Food' field removed, and instead get a 'Variety' (Meat) and 'Recipe' (Balls). The upgrade script would turn 'Meat Balls' into 'Meat', 'Balls'. Each component should also know how to deal with changes to mount points - e.g. if one is removed you will need a mechanism in place to figure out the position relative to another mount point that is still available.

This all leaves exactly one issue open: what happens if two objects clash with each-other (not their container - mount points protect you from that)? After an upgrade you should check for collisions and attempt to resolve them (by moving things apart, a bit like SAT). If you can't figure out how to resolve the collision remove one of the objects and place it in a stash - where they can buy these removed items (for free) or sell them (at full price); and obviously notify the player that the upgrade broke some of their layout - possibly with a 'zoom into' feature so that they can see the problem.

Ultimately you should leave complex changes in the players' hands (fail fast) as no algorithm can account for aesthetic - you should merely be able to give the player context as to where the item used to be (so that they can remember, not just land up with all these items in their stash and not know where they were).

share|improve this answer
    
This is focused a little too narrowly on object positioning, which isn't really the key problem I'm trying to solve. It's more about having unique identifiers in concurrent data sets and needing to be able to merge those without any possible risk of conflict. I added 2 examples to my post the other day to try and explain a bit further. –  Kylotan Feb 16 '12 at 19:15
add comment

I think the point here is to cleanly accept your responsibility. 1) The server says what is currently acceptable, and the API to access with. The database is being modified, according to certain rules. 2) Creators are allowed to create content, but it must be playable after updates. This is purely your responsibility: any update must be able to parse old data structures preferably as clean and easy as possible.

Mount point idea has merits if you are interested in keeping track of unique items and positions inside a malleable structure, especially if we accept that the whole 'home' structure of a player is going to undergo a dramatic change, and you want to keep that little deco stuff in their respective lockers.

It's a massively complicated issue, good luck! There probably does not exist any one answer.

share|improve this answer
add comment

I don't think this has big of a problem as you are making it.

I would just overwrite user created mods, with a warning noting that "Mod X may not work correctly with this version", leave it to the mod creators to change their work. I don't think this is an unrealistic expectation that updates might disable certain mods.

Same for user created content, just make a backup, and overwrite.

I have no actual experience in this, just making suggestions.

share|improve this answer
    
I think if it was purely for user-supplied mods, then you would be right. But some games are explicitly about the user created content, and so you can't just destroy it. –  Kylotan Feb 16 '12 at 21:40
    
Then just leave room in the system for content you might add later. If you are using ID numbers, reserve 1-1000. Or if users can name their assets, don't let users start the name with "FINAL-" or something (reserve it for your own assets). EDIT: or better yet, do it in reverse, forcing user content into a range or a prefix –  Woody Zantzinger Feb 16 '12 at 21:50
add comment

I'm trying to associate this with something that I understand, so I'm thinking in terms of Minecraft right now. I'm picturing a live server with players making changes in real-time while the developers are running on a test server fixing/creating new content.

Your question almost seems like 2 unique questions:

  1. How to insure that object IDs are unique
  2. How to insure that script namespaces do not collide

I would try solving #1 through a temporary referencing system. For instance, when a new object is created by someone, it could be marked as volatile or temporary. I would imagine that all new content created on the test server would be marked volatile (although it may also reference non-volatile content).

When you're ready to bring new content to the live server, your import process would find the volatile objects and assign them live-server object IDs that are set in stone. This is different than a straight-up import/merge because you need to be able to reference existing non-volatile objects should you need to fix or update them.

For #2, it seems you really need to have some level of intermediate script transmutation that can hash the function name to a unique namespace. i.e.

assignFrenchAccent

Becomes

_Z11assignFrenchAccent
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.