World Persistence: One In A Series of Queries

For me, the holy grail question about MMOG design centers on the vesting of persistence in the world itself rather than in the characters. Almost everything I find unsatisfying, both as player and as scholar of MMOGs, has to do with the almost complete lack of dynamism in synthetic worlds themselves, that the only thing which changes, grows, reflects persistence, is the character.

When I've ventured out before on this topic, I've found a reasonable degree of consensus on this point among scholars, developers and players, that dynamic, changing, responsive synthetic worlds are what we need. I've also heard on many occasions that they simply are not technically possible at the present time.

My basic problem is that I like to think about synthetic world design but lack the technical background to go past thinking fairly abstractly about what is and is not possible. So I want to start a series of fairly focused posts on applied world-persistence where I ask the technically adept among our readership just how difficult a particular fairly precise design would be to implement, especially in comparison to existing designs.

I want to approach this problem strictly as a problem in technical feasibility from the programming and server architecture side, not about whether or not this would pose difficult problems in management of the player base.

Applied design problem #1, then.

Let's say a design document calls for the following. I want to simplify this down to the basic essence of the problem, so wherever you might balk at graphical requirements, etc., imagine that the graphics and so on are highly rudimentary.

Let's project the space in which this problem takes place onto a hex map.

A series of ten interlinked caverns, roughly speaking running in two parallel lines from a common entrance that goes to two entry caverns.

In the caverns are one hundred orcs, initially spread evenly over each distinct cavern-room and remaining within the cavern to which they are initially designed. Each cavern-room is roughly circular, ten hexes in diameter.

An orc's hearing range extends for two hexes around the hex it occupies. An orc's visual range extends for five hexes around the hex it occupies.

An orc can move a maximum of two hexes per time step.

Each orc is an autonomous agent with the following rules governing its behavior.

a) If catches sight of non-orcs, each orc-agent has a variable weighted probability (e.g, at creation, each individual orc has slightly different weightings on each of these actions) of doing the following:
     1) running in a random direction and making no noise until non-orcs are no longer visible
     2) running towards the nearest orc and making an alarm noise
     3) moving directly towards non-orc at maximum speed and attacking once they are in range
     4) begin to build a defensive fortification.When finished with fortification in one hex, continue to build in random direction unless non-orc sighted. If non-orc  still sighted when fortification finished, attack with ranged weaponry from fortification; fortification offers major defensive bonuses to ranged attacker. Fortifying orcs will not respond to alarm noise orcs.
     5) move directly towards one of the two connecting caverns. Once in this cavern, build traps in each hex, moving in random direction when completed. Continue to build traps until non-orc sighted or alarm noise-making orc interrupts trap building.

b) If an orc hears an alarm noise, it moves towards orc making alarm and then makes alarm noise, unless already engaged in combat with non-orcs or building fortifications.
c) If alarm-noise making orcs are in hexes proximate to each other, they will move in same direction from that time step on.
d) If more than 5 alarm-noise orcs are proximate to each other, they will move directly towards visible non-orcs and attack once in range. If non-orcs are not visible, they will move towards nearest visible orcs and continue making alarm noise. In neither are visible, they will move in a random direction.

Fortifications prevent movement of non-orcs until they are destroyed, but orcs can move through them with no penalty.

Each trap space can be traversed with no penalty by orcs; non-orcs take damage unless they first detect and demolish the trap.

Ok, up to this point, this has no major dynamic world-persistent aspect to it--it's just a really simple AI routine with some obvious design problems. The next part, however, is this:

a) When non-orcs (e.g., players), leave the caverns altogether, record the number of remaining orcs. If more than 65% of the total cavern population remains, all orcs in caverns will move towards one of the two entry caverns and remain there. They will now have only one ruleset: attack all visible non-orcs.

b) If less than 65% but more than 45% of the total cavern population remains when non-orcs leave the area, the entire remaining population will move to (or remain within) the entry caverns and construct fortifications continuously. When the entry caverns are completely full of fortifications, each orc will occupy a single fortified hex and attack non-orcs from range if they enter the caverns. Any orcs which do not fit in the two entry caverns will move to adjacent caverns and revert to the "standard" ruleset.

c) If less than 45% of the total population remains, the orcs will construct traps continuously in the entry caverns and then retreat to the most distant interior caverns once the entry caverns are full of traps. Once they have retreated, they will stay tightly clustered and if they sight non-orcs, all will attack at 150% effectiveness.

d) Once all the orcs are dead, the caverns will remain empty save for whatever traps and fortifications were not destroyed by the players.

-----------

Here's my basic technical question. Compare this design with a static world design where each of those caves have 10 orcs who respawn at a set rate and who never change their basic AI routine in response to changing circumstances.

How much harder and more expensive in technical terms and in terms of burdens on underlying infrastructure is it to design and maintain the dynamic design than the static one? Twice as hard? Ten times as hard? One hundred times as hard? Like I said, for the moment, don't worry about what happens when the players run out of orc-filled caves to attack, or similarly large-scale problems of dynamic world design. I'm interested in just the narrow scenarios and how they compare.

Comments

[Alistair Riddoch]

The first thing that strikes me is obvious, and in your question. You now have to persist much more than in the simple static case, and this new persistant state is part of the world, not tied to the player. This means entire new systems are required to track and persist changes in the behavoir of the orc community in the overall location, and to persist what are effectively changes to the map caused when the orcs build fortifications and traps. These changes in the map are going to have to be communicated to the client software of any players approaching the vicinity, and depending on the details of your design, the collision detection code will need to deal with the new obstructions.

My feeling is that the complexity of the code has increased significantly, but probably not by as much as a factor of ten. The network load of the game has been increased, but probably not much, and almost certainly not as much as a factor of two. Server storage throughput will also have increased, but I am far from sure by how much.

All this should be qualified with the fact that I am an amateur backend programmer for an as yet incomplete MMO.

[Mike Rozak]

I don't think the problem is technical at all. Your solution doesn't sound technically difficult to me, assuming that you don't worry about what happens when all the orcs are gone (which is a design issue, rather than technical).

The problem is that players want two contradictory things: To be able to change the world, and to not have anyone else change their own world. Some more detailed thoughts on http://www.mxac.com.au/drt/FracturedReality.htm

[bllius]

When do the orcs say to themselves "forget this, we're getting slaughtered", and proceed to go on a pilgrimage to some place safer.

I've always wondered what a game world would be with absolutely zero NPCs, just player characters?

[Chip Hinshaw]

Alistair's comment makes me think about what happens to Timothy's "scenario" when spread over multiple shards/realms/etc. Seems to me that such dynamism(?) suddenly results in fairly vast discontinuity between shards. Players on different shards are no longer playing the same game. And if the results of the dynamics you've introduced are perceived as negative on one shard and different results are perceived as positive on another shard you then at least have the potential for some very dissatisfied customers.

[Andrew Krausnick]

re: Bllius -
Second Life? Either that, or I've always thought there would be some market for a cooperative puzzle/Myst style game in a persistent world.

In response to the original post:

I'll admit that my own experience with coding client/server applications like this is casual, however by all indications what you propose doesn't seem like a significantly difficult problem, at least from a software design point of view.

The main problem that I notice is scalability. With the 'spawn 10 orcs' design, it's easy to make little changes in the design that your players can easily comprehend and still approach as a challenge. For example, maybe your 10 spawning orcs have bows, or are on fire, or throw exploding chickens. In any of these cases the players can apply what they learned as newbies (orcs are mean, orcs generally respawn) and apply additional information in a way that isn't frustrating, but rather inspires fun game play in the form of a new and exciting orcy challenge.

As a consequence there needs to be a compelling design reason behind the change. If you will, take the current batch of MMO's, which are largely derivative in nature; consisting mostly of 'powering up' an avatar. Balance suddenly becomes very important, your players are going to choose the easiest (probably the dumbest) orcs to take on, and that's all they're going to do.

So what do you do, make there be better rewards for the smarter orcs. Well, now you have to fulfill that second objective, fun. If your orcs are just too good at winning, there's no fun in it for your players. You can always design something that can win out over your players or something that can easily be beaten. The challenge is designing something that is, well, a challenge.

As the complexity of your AI increases, so does the complexity of balance, and when major MMO's are being pushed out the door incomplete and with limited AI these days, it's going to be a long time before you see this sort of thing develop in any of the mainstream derivative games.

So what it comes down to is developing a type of MMO that is designed around this type of interactivity, and will most likely be a basic part of the design. I imagine you're probably heading in that direction anyway with this series of queries (good title by the way). In fact, my thesis work is on sustainable virtual societies of autonomous agents (basically communities of agents that can withstand outside forces and have predictable output), which I started work on so I could get a chance to work first hand on this sort of problem. I look forward to seeing what direction this goes in and your further thoughts on the matter not to mention that I’d love to hear some ideas for this sort of design that has compelling game play in mind.

[Duncan]

The problem with persistence is that you now have to hold the whole world in your head (assuming that you are the server). Even when there are no players in the area. You can't just save the data and forget it to make room for other data. It has to be kept active and there are tens to hundreds (to thousands) of operations in a single area that would have to happen even when there is no benefit to a single player.

The reason that the shard/instance solution is used so often is because it closely resembles the much more common area/level scheme used in most games. You have a set of data. The server loads it up, as is, and after the players defeat the Large Boss holding All The Cool Stuff, it can unload it.

There are only a few common areas that are always loaded, and they have very little that needs to be "managed" by the server because they are occupied primarily by PCs.

Persistence is hard to do because the demands are not so much in the design as in keeping the world persistent. In small cases, this is doable, but when the world gets large, it requires far more resources, and far more time. Oh... and writing an AI that could exist without interaction in any sort of form would be the next challenge.

I think that persistent worlds may start to show up in the next few years, but they will be heavily sharded and small to begin with.

[Michael Chui]

I'm not really qualified to answer the question head-on, but at a guess, it really is extremely basic.

What you'd need that is atypical is:
(1) extra stored procedures for things like construction or flee for other-orc,
(2) orc-initiated triggers (for alarms),
(3) tracking new fortification locations and current health (probably the biggest server load, though it's possible to simply regard them as another creature type: one with no attack and no movement and a special "You will not pass!" flag),

In other words, none of the persistence-inspired stuff is actually new.

Re: the persistence stuff.
a) Simple to implement, if you already have a trigger range on each orc. You attach a path-finding function, turn it on, and flag its target as the first PC that triggers.
b) A little more complex to actually DO, but a decent code monkey should find it a piece of cake, once they've understood the particulars. I.e., it's a communicate-to-coder issue, not a can-you-do-it issue.
c) More complex than (b), but same thing. Not hard to actually implement.
d) Simple. Honest. But it does mean that it's (probably) space that will remain unused for a while, so it's taking up database room that could be used somewhere else.

World persistence is do-able. It always has been. But (most of) all MMORPGs don't do it.

Can you honestly say the above scenario is impossible to implement, on your own, in Second Life? I think not: I think I could do it, with incentive, time, and sufficient land. And an artist.

[Timothy Burke]

Everybody's jumping to the next problem--scalability across many servers, scalability across a single synthetic world--and I can't blame them. Trust me, I'm going to get there. I'm just curious about whether, if you push scalability off the horizon for a moment, a single basic programming problem built around world-persistence rather than character-persistence is instrinsically or significantly more technically demanding or resource-heavy.

[randolfe_]

Assuming that the system follows a standard object-oriented, event driven architecture (to scale such a theoretical system, it almost certainly would need to be); and assuming that we are ignoring the derivative load increases caused by the world-physics and netcode layers:

Your scenario would be certainly implementable; many non-graphical implementations of similar experiments exist in various genetic algorithm models and AI agent subsystems.

The problem is, as mentioned by Duncan, the system must now manage, execute, and continually persist a much increased magnitude of objects, all of which must handle a much increased magnitude of events regardless of client (player) interaction/observability. This could be implemented without concern for the constrained scenario you describe, but would grow roughly in load as a geometric progression when you attempt to scale. And that's ignoring the physics and netcode layers, which would also grow in load as a factor.

A more reasonable solution would be to only execute the real-time sequenced scenario when a client can observe the world area. When clients leave the area, instead forward compute a series of future states (these can be based on probabilities emmited from the unique objects). When clients re-enter the area, activate the closest computed time-state, and respond to events in real-time.

This granularity could then become a tuning dimension to allow for more granularity as the infrastructure is scaled (and processing power/throughput is increased).

[mjh]

The obvious answer is: no! So long as you don't get into some kind of n-squared scenario where every orc needs to know about every other orc in the world, of course. The processing costs of handling orc motion and orc combat when a pc is around will dwarf the higher-level orc ai. Particulary if, as you describe it, you're basically switching between several low-level orc behaviors based on the orc headcount; counting orcs is cheap, as is swapping behaviors.

Games are all about cheesing it anyway; you could keep the fortifications in the exact same place each time so players say, "See! It's the same! The cave's permanent!" when everything but is regenerated from the headcount.

There's the problem that a lot of simulated stuff has: when you're doing stuff under the hood that's poorly communicated to the players, it appears random or worse than random; witness the crop of unsatisfying a-life games 5-10 years back.

[Michael Chui]

I'm just curious about whether, if you push scalability off the horizon for a moment, a single basic programming problem built around world-persistence rather than character-persistence is instrinsically or significantly more technically demanding or resource-heavy.

The key part is "resource-heavy": that's dependent on scale, unfortunately. The general rule is that, the more you track, the more resources are required, and thus the more resource-heavy it is. What you ask for is, quite literally, more than there currently is. Therefore, it's more resource-heavy. How much? Well, what's the scale?

But the gist of the answer is simply that you haven't asked for anything special in terms of resources. You've asked for a bit of code complexity, as other posters have mentioned, but to say it's impossible is to call the programmer incompetent. You've already done the majority of the legwork; the programmer merely needs to implement the AI. And all the tools already exist. (If they don't, then either they're genius-like insane crazy ninja coders doing things beyond my ken, or they're still incompetent. =)

[RedKnight]

The one thing I thought of when reading about the various responses of the overall orc horde that depended on the number of orcs left alive was, "but how would they know that's how many of them were left?" Somehow, that knowledge would have to be communicated between the orcs and if that means of communication isn't apparent to the player then you have an interesting phenoma. The orcs are metagamming.

Organizing in game events through out of game channels is inevetiable for any game. But do you reall want mobs takeing part in an activity that's often considered a questionable practice?

[Auz]

"I've always thought there would be some market for a cooperative puzzle/Myst style game in a persistent world."

Seems to have been a small market though...

http://en.wikipedia.org/wiki/Uru:_Ages_Beyond_Myst#Uru_Live

[Daniel Speed]

It seems to me that the question about world persistence is being confused with one about world persistence and dynamic behaviour.

Persistence comes in many shades, down from just about nothing (WoW?) to something like Eve where there's deployable structures and claimed territory, and right up to SL.

Absolute answers aren't always the best ones anyway if you're trying to just achieve a specific effect, so I'd expect it's almost always going to be better to make specific compromises in order to get the effect of persistance in all the ways that it matters to players.

[Artheos]

Redknight, whose to say that they aren't in a guild/raid/group?

Timothy Burk, The actual scripted response to incursion in a specific zone based on an individual orc seems fairly straight forward (I'm not specifically a game developer thought)

It would increase storage and processing power on the server side, but the client would still recieve the object at location moving in direction executing action message they do now (in other words the scripting and persistence would be only server side impact). In most recent games, there are this large number of objects being communcated already to the client (in my thoughts).

This next thing though, kind of has me scratching my head.

Andrew Krausnick > "With the 'spawn 10 orcs' design, it's easy to make little changes in the design that your players can easily comprehend and still approach as a challenge. For example, maybe your 10 spawning orcs have bows, or are on fire, or throw exploding chickens. In any of these cases the players can apply what they learned as newbies (orcs are mean, orcs generally respawn) and apply additional information in a way that isn't frustrating, but rather inspires fun game play in the form of a new and exciting orcy challenge."

This is exactly what I don't find exciting about MMORPGs. Orcs that act like the orcs I fought at level 10 when I'm at level 60 are uninspiring and boring. Attaching a new skin/weapon or armor model doesn't help in the least other than superficially.

World change and persistence is one huge problem in MMORPGs, and another is that even in new areas, against new opponents. you're facing the same challenge over and over again.

I suspect as long as the overall physics model is consistent, the behaviour model has more room to change than is hinted at there.

[Ken Fox]

Michael Chui has really nailed the answer to this post.

Spawning orcs and "spawning" traps is equivalent -- they're both NPCs to the software. You can have different implementations for different types of NPCs though. For example, traps won't have drops or move, so the persistence mechanism can be relaxed. If the server crashes, nobody cares if some traps disappear (the orcs must have rebuilt their city while the server was down...) Nobody will try to dup a trap either. ;)

Changes to terrain are harder to handle without cheating because you have to give the client more than the player can see. If you don't care about cheaters being able to see where the fortifications are, you can have the server send geometry updates and treat the dynamic world exactly like a static world in all the downstream logic.

Scalability (with parallel agent servers, i.e. trusted clients) for these advanced NPCs seems fairly simple, but I'd worry about the server cost -- you're going to need more CPUs to handle the more complex agents, so more power, more heat, more A/C. What's the monthly charge going to be?

[alan]

bllius>>"I've always wondered what a game world would be with absolutely zero NPCs, just player characters?"

I think something like this would make for a very intriguing design.There is nothing interesting or challenging about camping a respawn of creatures that will respond the same way every time. I would, however like to see a twist on the idea of all player characters, by giving the player the ability to "order" NPC characters. If you could leave a group of NPC's with a set of instructions to perform actions such as patrolling an area or guarding a keep, it would really add a level of excitement that is missing. These NPC's actions would be unknown to the attacker because they depended on the "programming" of a player.

[Ken Fox]

I forgot to answer the original question though. :)

10% harder to build. 50% more expensive to run.

alan> I would, however like to see a twist on the idea of all player characters, by giving the player the ability to "order" NPC characters.

I had high hopes for Dungeon and Dragons Online because of the rumor I heard that everything was instanced and designed for groups. It seemed like the perfect design for player-run (an online GM!) content. I guess the game didn't turn out that way, but I haven't played it so I don't know if the idea is feasible for an expansion.

[Timothy Burke]

This is very, very useful, and to me, the technical simpleton, very illuminating.

I especially find one of Randolfe's suggestions useful as a technical strategy for producing a similar result. Rather than requiring the system to recall exact placement of fortifications, traps, orc-positions at the time that players leave the caverns, and then requiring it to carry out each-time step of an agent's actions during player absences, just have the following:

Interval between player exit and next player entry
and
Number of orcs remaining

and use that to construct a "future state" that is predefined (e.g., if players have been gone for 4 hours, build X number of fortifications and Y number of traps and place orcs in appropriate defensive or offensive postures with appropriate new rulesets).

--------

You could extend that idea further to try and find a non-computational way to "simulate" dynamic persistence even in a narrow scenario like this, but I'm less satisfied with that, because I think players see through such strategies fairly readily. The first time you see NPC mobs interacting where it appears they have a dynamism, it's enthralling, but pretty quickly you'll realize that it's just a repeating loop of some kind or some other fixed routine. If on the other hand, there is a genuinely (and partially randomized) dynamic routine involved, even if you come to understand how it's done, or the patterns underlying it, it's still going to feel somewhat life-like and dynamic.

[Hellinar]

As the Irishman is reputed to have said, if you want to get to a persistent world, I don’t think I would start from here. In a sense, a war torn world is the very opposite of persistent. All that was built up and made orderly is being torn down and reduced to chaos. If you are want a persistent world, I think you need to focus first on NPCs that build stuff. The fighting over it is the final stage in the game. I can’t see your Orcs having anything like natural behavior unless they have some lives going on that gives them reason to defend their caverns.

We already have worlds where player characters build stuff. A Tale in the Desert and Second Life come to mind. The next step, in my view, is a persistent world where NPCs build stuff and carry on productive lives. Finally, when NPC interests clash due to the steady growth of their civilizations, you can have a realistic war. But I don’t think tinkering with the current model will do much to make MMORPG believably persistent. A world in which all people do is blow stuff up is quite unnatural. The need to re-spawn stuff at five minute intervals flows from that. Persistence doesn’t really fit with a world in which most NPCs are fighters.

[Charles]

Thus far, to me, this scenario seems entirely feasible and not overly taxing on the systems involved. However, as many peope have mentioned, looking at this absent scaling is sort of meaningless from any kind of practical perspective. If you abstract out scaling, you're abstracting something that can't be safely abstracted out in this case: its an integral part of the design. There's a fair chance you come to the comclusion that X is possible, but later find out that X isn't even what you were looking for. Of course, I'm not currently involved in development of any sort of online game, so others may be far more qualified to answer this question than I.

As far as making worlds persistent, there have been some attempts in various MMO's. First in my mind was an area in one of the many expansions to the original Everquest that (I believe) was non-instanced. It featured 3 NPC villages that were at war, and the player could help any 1 village gain dominance over the others. Of course, after a while the villages would be reset, and the entire process would start again.

However, this also faces the problem Timothy brought up just above, that players will almost immediately exhaust any illusion of real change in the world. Timothy seemed to be referring to small loops of interaction, but I think that the same principle can be applied even to longer more complex recurrences. The players _will_ figure out how to repeat the most beneficial interactions in time unless a real emergent system is used in the world, which is certainly beyond our current technical limitations.

[Franek]

To answer the resource question we might first tease the elements of the design apart.

In the naive design you can classify actors into two categories: driven and directed. Though Ken Fox rightly points out that both mobs and objects are actors to the underlying engine the distinction is still useful. Driven can be those actors that change state only when some outside agent (like the physics system) changes them. Otherwise, they perform scripted actions. Some current NPCs fall into this category. Directed actors can be those, like player characters’ toons, that change behavior through some conceptually external agent.

In Timothy Burke’s target system we could make the Orcs directed and have software implement (as both Timothy and Andrew Krausnick suggest in their posts) appropriate agency.

So now we have three design decisions each with some implementation and operational cost:
1) To what extent can a directed actor change the world?
2) How complex do we want the behavior of directed actor agents to be?
3) How many directed actors do we want active at the same time?

These are familiar problems.

Should actors be able to blow up bridges or build walls? Should rocks roll down hill when pushed? Should bullet holes in walls stay there forever?

Should directed actor agents learn over time? Should they take into account the strategies of their opponents?

Do we want to support a handful of actors, dozens or hundreds in a single coordinated environment?

And there is an existing arsenal of optimizations / design decisions for dealing with them.

Limit the number of active objects in the environment. Allow construction of only simple objects that are animated by the physics engine. Do not retain transient changes like bullet holes.

…

In Timothy’s orc example the baseline (the “static world design”) isn’t completely specified – so incremental costs may be hard to describe. But we could ask questions like “How much harder is it to implement a smart orc than it is to implement a dumb orc?” (Ken suggests 10%) How much more expensive is it to instance and activate a smart orc than a dumb orc?” (Take into account the computing resources, storage, etc – Ken suggests 50% - I would suggest 2X PC cost at a minimum).

As to the world, we have to allow for construction of barricades and traps rather than just having them statically placed. They already exist, so it is the incremental cost of dynamic placement that needs to be estimated. Also, there are about 3500 hexes in the dungeon. Assuming that orcs could fill up 50% of them with barricades or traps, what would the cost be of managing another 1750 driven actors?

So we are sitting on 100 smart orcs, 1750 additional driven actors, and some undefined number of active players all interacting in this dungeon. Worst case situation, 100 orcs and 250 players each occupying one hex in a single room.

This may not be the best analysis of the problem. But some similar analysis is needed to answer the questions of “how much harder”, “what will it take?” and “can we even do it?”

Folks with experience in the various engines / environments / development systems can flesh out the range of values for these variables as they have experienced them. And they can take into account common optimizations like limiting computation and communication on the basis of room boundaries. But it may be that level of detail is inappropriate to the forum.

[Nathan Mishler]

One of the biggest problems with this sort of senerio is that players metagame a lot. As soon as they come up upon this cave, some of them are going to figure out the exact numbers needed to cause each of those senerios. They will spread the world and pretty soon a good number of players will know exactly how the cave works.

That isn't a bad thing, but it will have a tendency to make your more interesting cases not happen that often. That's the big problem with npcs that can act in very interesting ways: people will discover that very interesting things happen and that at least in this case interesting = harder.

Most players in the know will kill all the orcs so they have to deal with traps or fortifications as little as possible. Other players will figure out how to cause the fortification / trap thing to happen and will trigger it just to make it harder for other people.

The problem isn't just a technical one, but a design one, the "We just spent a month on this cave and no one sees the cool edge cases because they just roll right through it" problem. Or the "No one goes to that cave because it's always full of traps so they just go to the easy cave instead" problem.

[Matthias]

How heavy your proposed design is on the resources, depends very much on how serious you take the persistence (from your last post i get the impression that you are ok with "faking" persistence to quite some degree).

I think that a good point of view for the degree of persistence is a server-restart.

Lets assume that there was a raid on the caves and 80 orcs are left, also they have set 10 traps and built 7 fortifications.

If you want the exact state of the caves back after the restart, you need to save each orcs state (could be they suffered some permanent damages, at least they are exhausted or lost some health or projectiles or whatever).
You also need to save the positions/dimensions of the trap-spaces and fortifications of course. And as some have mentioned already that traps/fort. are partly to be handled like npcs, you might also need to save some state on them.
An example might be for traps: dangerous to humans,elves,dwarves,... not dangerous to: orcs. Of course this list can be extended seemingly endlessly (what about other orc-factions for example). Also you need to save/restore the type of trap (poison, fire, ice, whatever) and their strength/damage-dealing-capacity (which will probably have been generated randomly or depending on some stats of the orcs who created/set it.

The easy solution is, what randolfe said. For the restart it would mean that you load up a state of the caves (80 orcs, 10 traps, 7 fort. and randomly generate "new" ones.

It should be obvious that those two are totally different beasts.

There is no single factor you can "put" on these scenarios imo.
I would split it up into categories and even then it depends very much on your implementation. For example there could be a standard fort. that orcs build then you only need to save position/orientation. The more variable they get, the more state you need to save and you could even go so far to save the changed height at each point in the cave).

So for the exact persistence, using simplified state for fort.) id guess:

Bandwidth: a factor of 1.2-1.5 (each trap and each fortification has to be sent to each pc that enters the region/caves and im just assuming that theres up to half as many of them combined than there are orcs). Of course this would be probably much higher if players were also allowed to "litter" the surface of your world with traps and such.

Database: since you now need to save all existing npcs additionally to your pcs id say 2x the space you need for your pcs. The traps and fort. prolly are lower in numbers and have much less state that needs to be saved. so add another 0.5 times pc-space for them.
Of course this also means twice as many database-transactions so the database-server load will also go up and since this usually doesnt scale linearly id say a factor of 3-5 for that.

Server-load due to AI: i dont have enough experience to take an educated guess. i see it much higher than what was written in the comments until now, though, because imo by having to make the orcs aware of the state of their fellow orcs and not only in their cave but in all caves and the need for them to constantly monitor that state id think its quite some extra load.

[Ken Fox]

Timothy Burke> use that to construct a "future state" that is predefined

Yeah, I liked that too -- it's a great idea. I'm not sure it's better than real-time all the time.

First, you're going to frustrate your scenario designers by forcing them to build two behavior models (agent-based real-time vs community-based statistical) and keep those two behavior models consistent enough to fool the players. That seems really hard.

Secondly, if you have enough hardware resources to run the real-time model with players, you've already scaled for peak activity and should have the hardware to run it all the time. It's easy to reduce the computational demands for non-combat agents by switching algorithms based on the presence of players. Of course, this depends on your player-to-NPC ratio -- if you have a huge world with a couple players then the statistical model becomes very attractive. You're already out of business if that happens though, right?

Charles> The players _will_ figure out how to repeat the most beneficial interactions in time unless a real emergent system is used in the world, which is certainly beyond our current technical limitations.

If players couldn't do that, it wouldn't be fun! :)

I disagree with your opinion on emergent systems. Very simple systems (cellular automata in Conway's Game of Life for example) have emergent behavior. The rules for orcs given above are very simple and rigid -- they will probably never surprise the scenario designer. However, the scenario designer could define individual agent goals that elicite the desired scenario, but also combine in surprising ways. Simple change: instead of the 65% threshold, nudge an orc towards agressive defense if he sees another orc kill or chase off an attacker, or if another orc nearby displays an active defense.

[Chris Lloyd]

Charles has already mentioned 'Hollowshade Moor' in Everquest. Three competing factions in three different camps that normally sit in equilibrium, but can be temporarily unbalanced by the players. When a player aids one of the factions to dominance, the faction in question will take over a fourth camp, normally containing friendly traders, with noticably higher level monsters. When this camp is cleared again the entire zone resets.

Given this was, as far as I remember, a unique set-up in Everquest I wonder what problems it had that caused it never to be repeated. Were they technical or political? As an example though I think it goes to show that what you're asking is clearly technically possible.

One of the problems it is going to cause, that may be viewed as a technical one, is how much extra content has to be designed and added to this style of encounter. How much cheaper in terms of level-designer time would it have been to say 'Here we will have ten linked caverns containing 100 orcs on six-minute timers, and over here we will have...' How many extra content developers would you need to populate a world of the same size? Given that you are trying to add a number of extra persistant states to the world, each of which is mutually exclusive, who is going to want to pay for the development for all those states that are not currently visible to the players?

bllius>>"I've always wondered what a game world would be with absolutely zero NPCs, just player characters?"

Face of Mankind?

[Chip Hinshaw]

I don't know ... I hate to keep jumping ahead, but I think that the case Timothy is presenting points eventually (perhaps inevitably) towards an AI layer the complexity of which scales up significantly and I find it hard to ignore (but that's my problem :) ). What you suggest requires an awareness for every one of your agents that must continually be monitored and updated. Butterfly effect potentially ... and I think that's what would become particularly resource-heavy. I have to look for interview I did with one of the geniuses at CCP before the launch of Eve. He had some very interesting comments on just this sort of thing. Now that I think about it maybe it was one of the Origin guys. I'll see if I can find it.

[randolfe_]

Further thoughts on the computation of future states. It occurred to me after thinking about this a bit more that we must assume that the only perturbing actors are player-driven. We are ruling out other AI-driven actors from disturbing the "orc state". If that is the case, then we also are assuming the "orc system" is mean reverting, towards some sort of probabilistic equilibrium. (This equilibrium could decay over time, also, but this is less of a design concern, which I'll attempt to demonstrate).

The approach of precomputing future states isn't really "faking" persistence anyomre than basic quantum principles. To the observer, it is dynamic and occurred in real-time. (Is the cat is alive or dead until we observe it?) Again, since the system reverts towards a mean equilibrium, we only need to forward compute future states as a weighted moving average decreasing with time.

The elements contributing to the computation of the future states would be emmited from the present objects themselves. That is, depending upon who the player-actors were, how many of them were present, and what their persistent stats/characteristics were while present, and dependent upon the mobs left alive (perhaps even those killed as an influence on those left alive...'they killed our leader!' kind of effects) the system agent will compute dynamic future states upon player-actor exit from the "zone".

The problems, as correctly pointed out in many responses, is that players will be able to recognize the patterns and meta-game the system. Never forget that the human brain is a neural-net capable of extraordinary pattern recognition. Creating a system capable of fooling a human into perceiving dynamicism will require a fairly complex computational state processor. I fear that the load will grow geometrically as the number of mutatable variables grows.

I can conceive of a dynamic persistent system, even given your constrained scenario, and even assuming "future state caching", that would require overwhelming (unreasonable) resources. Simply trying to implement "orc emotion" on any realistic level would add an order of magnitude to the complexity.

[Matthias]

randolfe, im sorry for wrongly calling it faking (it was mainly because of the lack of a better term).
The "problem" with computing future state the way youre proposing is that you dont have a clearly defined state at each and every moment.
So instead of only making the state of the existing objects persistent you would have to make the basis/variables of your computation persistent additionally to the current state i.e. you have to save "80 orcs, 10 traps, x fort." and "last player visit at 07:00 server time (and maybe further needed information for the calculations)" to be able to make the correct computation after a server restart.
You could, instead, do all the computations at the time of saving - but that would not work with "unexpected server downtimes" (crashes).

Oh and i found a better term now: "compromising" :)

I think its actually a very good compromise (just to make sure this post isnt misunderstood)

[randolfe_]

Matthias,

Thanks for the clarification. Yes, I was assuming computation and persistence at the time of last-visit-exit. *Unexpected* system aborts, whether software or hardware, would be tough to handle because you could only roll back to the most appropriate time-sequence stored, which in the worst case would be the long-run equilibrium from the most recently stored player visit. This could have the effect of "turning back time" to a point before a player/group had visited the areaa.

I'm not an expert when it comes to the hardware side of this equation, but even assuming a massively over engineered hardware platform that "never goes down", there would still be significant problems with software level errors causing such time-blips.

[Tom H.]

Most of the techincal discussion above ("feasible, maybe not scalable, designer-intensive") makes sense to me (PhD in networked VR). Two minor points:

If I recall correctly, Neverwinter Nights, running single-player games with worlds smaller than many MMOs, had to do serious "level of detail" on AI which came down to not running AI code in zones with no players. Not directly applicable, since I assume they were spending most of the CPU on graphics and UI.

Didn't Ultima Online early on experiment with a persistent ecology, which crashed? Google shows reviews and Origin's ad copy from 1997 touting persistence and a virtual ecology. If we have anybody from that crew around they ought to have lots of insight. (That was before I was in work-avoidance mode in my dissertation.)

[Raph]

You don't get to push scalability off. Otherwise, what you've made is a nice single-player game encounter, not a virtual world.

UO's ecology didn't crash in a technical sense, it crashed in a design sense -- there were bad feedback loops in our design.

That said, it was also too resource-intensive. The reason AI is dumb in these games is because we can't run too many smart ones.

And the reason encounters are simple is because we can't handcraft too many cool ones.

Absent scale, you're not actually addressing the design problem.

FWIW, the single biggest problem with real persistence right now is that the DB gets huge and nobody outside of Linden seems to want to pay to run it. :)

[Chip Hinshaw]

I found some of my notes: Rick Hall had said to me (re: the difficulty of implementing "smart" AI in these MMOs) that you eventually have thousands of these agents throughout the gamespace carrying out their various activities and that quickly bogs down resources (as Raph mentions above).

On the other hand, Kjarten Emilsson of CCP had suggested to me that "large-scale coherent patterns emerge from lower-scale simple processes ... Natural Stupidity rather than Artificial Intelligence." So maybe there's some simple schema that results in the type of behavior you're looking for, but again I still think it ends up costing you alot across the server. If we're talking persistence then changes become permanent (at least to the extent that we don't likely return to the initial state). And (sorry) paste this across multiple shards and your customers are not playing your game in the same space. One shard becomes very appealing based on a persistent state that has arisen due to behavior of AI on one shard, whereas an unappealing (or at least dull) situation persists on another shard because those same events did NOT take place on that shard.

[randolfe_]

Raph wrote:
FWIW, the single biggest problem with real persistence right now is that the DB gets huge and nobody outside of Linden seems to want to pay to run it. :)

This point is very important. Persistence costs grow very quickly with scale; moreso than most (unfortunately) designers and architects usually plan for. A complex system like this isn't a simple, procedural DB storage question, but a problem of persisting complex object graphs. The cost of serializing deep graphs is expensive in terms of processor, memory and throughput. Rehydrating these graphs quickly is of even greater expense. There is a derivative problem of either garbage collection or debug-cycles of reference counting and memory management. Anyone's whos ever implemented a deep-graph object system and found they ran into significant persistence scaling problem knows what I'm getting at. Unfortunately, the answer is usually to revert to non-object approaches which, while fast and efficient resource-wise, yield far less flexible designs that result in systems that are prohibitively expensive to maintain and enhance.

[Daniel Speed]

Chip - Eve's NPCs are highly simplistic and not persisted. On the other hand, Eve persists a huge amount of data about player states.

Mattias - Exactly what I was suggesting earlier. What you generally want is the minimum data, computation and effort to achieve the effect that you want. When you're trying to get a sense of orcs that build up defences and grow, you dont *need* to persist every single orc and simulate them individually to achieve this effect. Persist what's important, and you can get 95% of the effect at 5% of the cost. Store the number of orcs, an indication of the level of the defences, and use formulas or a simple algorithm to simulate how that changes over time. The derivative of the formula for the number of defences will even give you a guide to what they're all doing at any one time. You could then create the entire cavern scenario by putting together a number of authored archetypes to achieve the balance of numbers and activity that you want, and you've done it for the cost of a few templates, some quick calculations and a very minimal DB footprint.

It's critically important in MMOGs to work out what you want, and find an elegantly simple method of getting that, not the 100% accurate simulation.

[randolfe_]

FWIW, the single biggest problem with real persistence right now is that the DB gets huge and nobody outside of Linden seems to want to pay to run it. :)

Not to detract at all from LL's accomplishment. Are there any complex non-player directed AI in SL aside from what people have implemented in LSL, which is initialized-volatile except for data that has been exported outside of the grid?

[Hellinar]

Daniel Speed> It's critically important in MMOGs to work out what you want, and find an elegantly simple method of getting that, not the 100% accurate simulation. <

The problem with the Orc example is that it implies a kill, loot and level game. Which implies that all encounters be challenging, and all shards equally interesting to play on. Otherwise players will focus only on the easy encounters, and play only on the interesting shards. That seems like an enormously difficult result to achieve with a simple method. In a Diku type game, I think players are looking for dynamic quests, that spawn well balanced encounters with a sense of evolving backstory. A bunch of AI NPCs following their own agendas will likely lead to encounters that are badly out of balance for risk/reward.

We already have persistent, dynamic worlds in Second Life and A Tale in the Desert, to name a couple. In ATiTD at least, the database problem is made tractable by the persistent objects being buildings, which don’t run around and interact with each other. Perhaps the next step up from that is NPCs who build stuff, with some way for Players to select for NPCs who build interesting stuff rather than boring stuff. Isn’t that something like Spore is aiming to do?

[Michael Chui]

You could then create the entire cavern scenario by putting together a number of authored archetypes to achieve the balance of numbers and activity that you want, and you've done it for the cost of a few templates, some quick calculations and a very minimal DB footprint.

This is a bit of a tangent, but that made me think of Christopher Alexander's "Pattern Languages", the idea of being able to make things from scratch from a few basic ideas. He's in the field of architecture, but it's a reapplicable idea.

Also, it might be worthwhile to point out John Arras' genmud.

[Samantha LeCraft]

Chip Henshaw said, ...paste this across multiple shards and your customers are not playing your game in the same space. One shard becomes very appealing based on a persistent state that has arisen due to behavior of AI on one shard, whereas an unappealing (or at least dull) situation persists on another shard because those same events did NOT take place on that shard.

Why is it a problem if the different game servers are not carbon copies of each other? We've been working under the assumption that they should be, pretty much from the beginning, but IMO, that sort of thinking has limited what we're willing to try. Players aren't playing in the same space anyway -- what you do on Server A does not affect my game on Server B -- but we like to pretend that it's all one large game. Why do that?

Each server could have a different starting state, and the state of each server could diverge wildly from there. If players had the ability to affect the state of the world in a meaningful and lasting way, would it be so wrong for Server A to be different from Server B? Don't like the state of things on Server B? Well then, start effecting change in the world. I truly doubt that players would jump from Server B to Server A just because Server A's state is seen as "better" somehow. Players hate leaving their developed characters and their stuff behind, so if they were given the option of changing their own server, I think they would do that before jumping ship altogether.

Beyond the added work for the dev team of keeping up with the different situations on each server, why would this be a bad thing?

[Franek]

We seem to have centered on the implementation of orc behavior as the activity most important to evaluating complexity. Raph and others suggest that throwing computational resources at the problem is not economical. Similarly, dynamic designs drive statefull instancing, that drives database size and that leads to economic tradeoffs.

By way of optimizations to reduce cost we have been having the pure vs optimized discussion for both cellular automata and object oriented storage.

Do we really mean our limitations are economic rather than conceptual? Are we saying that if we could justify the computing power and storage we could make fully interactive persistent worlds given the knowledge we have now? Or are there some problems we can’t solve even if our resources were unlimited?

Casting Timothy’s question in light of economic feasibility changes the scale question we’ve been kicking around. Does the computational complexity of persistence justify the cost of supporting it? Perhaps that can only be answered if we know the population to which we are designing. If that is so we will have to discuss not only our ability to optimize our costs and ride the curve of computing cost reduction but also reopen discussion of our how much people will pay for persistence.

Taking these two questions together and twisting them a bit, are there some things we don’t know how to do now, like communicate compelling interactive story arcs in an MMO context, that would be enhanced by dynamic persistent environments and justify their greater cost?

[Charles]

Hellinar> Which implies that all encounters be challenging, and all shards equally interesting to play on. Otherwise players will focus only on the easy encounters, and play only on the interesting shards.

I don't think this is necessarily true. I think that for the majority of players there is a great deal of identification with the shard and resulting community that inhabits that shard. Having different states in each shard might increase that sense of identification. People might have pride in their server's unique accomplishments, others might like the idea of a realtively untouched land that they can develop. As long as you can ensure that the servers will be different enough to identify, but not so wildly different as to be an entirely different game experience, there should be little danger of people abandoning "uninteresting" servers.

[Mike Sellers]

Very interesting discussion.

Timothy, despite what's been said above about technical issues and scaling, I think the primary reason the kind of thing you describe above hasn't been implemented is due to design rather than technical considerations.

First, current and past MMO designers tend to think individually ("what is the player doing" or "what are the quests and encounters"), a throwback perhaps to pen-and-paper RPGs. The alternative is designing systemically, which is what's required for the sort of scenario you outline. Consider that you could run WoW today with a text interface and it would almost indistinguishable from a MUD made twenty years ago. That's not a knock against current MMOs, just a statement of where we are in terms of what's been done. The gameplay tropes have changed very little.

Second, to a large degree we have this design stultification because it's what the vocal player base have gravitated towards (the rest is that evolution in the designers and publishers of MMOs has been glacially slow). Persistence and systemic design haven't been rewarded in the marketplace by hardcore gamers. They more often want predictability of outcome instead of a smart opponent or a dynamic world.

This isn't to say that the scaling issues in particular aren't real. They're just not the critical bottleneck in preventing this sort of design from being implemented and deployed.

The AI question is also at the crux of this issue, I think. What we want is not just persistence, but the feeling that the world really is going on while we're looking elsewhere. This requires something beyond static respawns, and definitely requires something beyond what we currently have as game AI (it's telling that most game-AI discussions quickly divert from anything goal-oriented and focus on low-level behaviors like path-finding).

Raph said, The reason AI is dumb in these games is because we can't run too many smart ones.

Only partly. Mostly I think to date MMOs have been focused on old-MUD-style individual play and so haven't invested in robust, goal-oriented AI that contributes to gameplay. Creating robust AI that doesn't eat CPUs is a very difficult problem, no doubt about it, but also one that can contribute hugely to moving MMOs off of their flagging style of gameplay and onward to something more dynamic, persistent, and rewarding to (more) players. Doing so sets up (and requires) a different kind of design ethic, and for example requires that you be comfortable with tuning emergent systems rather than proscribing mechanistic ones.

In terms of scalability, in addition to novel AI architectures, there are a variety of "LODAI" (level of detail AI) techniques that can be applied -- variable time-slicing, forward computation, representative computation (i.e., maybe you don't need to calculate the state of every single orc), etc. But as I said, these are a secondary issue -- a form of optimization more than huge innovation.

Overall the point is that creating a persistent, dynamic, textured world is possible, but not if you stick with the current MMO design methods and goals. It's going to require something different, especially in the area of more believable AI (which is ultimately at the heart of your example, Tim). Moving to a more satisfying degree of persistence requires and creates new kinds of gameplay -- and of course entails certain risks until we know the terrain better.

[Chip Hinshaw]

Semantha>Absolutely valid and good points. Truthfully, I don't know that it would necessarily be a bad thing. I certainly agree that it could lead to some very interesting possibilities (namely that chunks of the subscriber base are playing vastly different games in potentially vastly different worlds "ruled" by the same mythos).

I guess I'm focusing too much on the potential for imbalance, and I suppose that could be mitigated to an extent. If you go back 10 million years in time, one little mistake could completely undo the future of the world. Whereas if you go back 10 minutes in time ... your actions aren't likely to have much effect outside the very local. So, you could certainly control the extent to which AI behavior would have a deep or lasting effect on the overall world. But, then it's down to perception. And if a good portion of your subscribers feel that other players are getting more for their money on another server (perhaps one that they cannot join due to population) then you've probably got a not insignificant service issue on your hands.

I agree with you, though, that it would make for some very interesting alternative worlds.

[Michael Chui]

Do we really mean our limitations are economic rather than conceptual? Are we saying that if we could justify the computing power and storage we could make fully interactive persistent worlds given the knowledge we have now? Or are there some problems we can’t solve even if our resources were unlimited?

That's exactly what I'm saying, certainly; and not presuming to speak for the others, the gist of what I hear is much the same.

The thing is: persistence has been DONE. It has been achieved. The problem is that none of the game-like worlds USE it to the degree suggested (and that's a very small degree). The belief Tim presents in the OP is that persistence is the necessary key; this, I also agree with.

The problem has never really been technical. Sure, it's more work, technically, and you need better coders and better designers... but these people exist, and these people are willing. No one's made the choice to do it. Would it take more money? Yes. It'd take more servers, better networking, etc., etc. All of that. And the bigger you scale, the more you need. Fine. But is it possible? Hell yeah. Like Raph mentioned: Linden is doing it. Now. Like I said in my first post, you can achieve all of the above features by spending some time in Second Life. You can theoretically program the next MMORPG in Second Life. Of course, you'd also probably crash their servers... =P

[randolfe_]

Like Raph mentioned: Linden is doing it. Now. Like I said in my first post, you can achieve all of the above features by spending some time in Second Life.

I don't think there is any level of AI implemented in SL by the VW itself (correct me if I'm wrong). If the suggestion is that you could use LSL and code your own persistent MMO, then you have to get around some serious limitations.

From the LSL wiki:

In LSL, each script runs in its own seperate 16k memory "sandbox", meaning there is 16k of space to store your program and all it takes to run it.

Of course you could use linkage and non-linked mechansims to expand upon this (essentially having lots of 16K processes interoperating), but this will reduce to an effort of optimization overriding design in short order.

Secondly, how exactly do you persist? LSL and many object attribtes are volitile from initialization state, so you'd have to export data out of grid then reimport it for reinitializations.

Lastly, even though LSL is an event-driven paradigm, it does not allow you to efficiently implement dynamic event handling. This will make creating an autonomous agent pretty tough.

[Mike Sellers]

Michael: Would it take more money? Yes. It'd take more servers, better networking, etc., etc. All of that.

Hardware costs aren't a determinate factor in the scheme of things. One question in terms of cost is, would it cost more to create a dynamic persistent world with autonomous agents, and from which gameplay emerges, or to have an army of scripters creating reams of quests and instances? We know something about the spiraling costs in the latter case, and how quickly people rip through static content. The methods and costs of creating a dynamic persistent world part are a lot less well-known. But to me this looks like the way to move beyond our current first-generation MMOGs.

[Hellinar]

Charles> I think that for the majority of players there is a great deal of identification with the shard and resulting community that inhabits that shard. Having different states in each shard might increase that sense of identification.<

Good point. Perhaps you could run each shard with just an NPC civilization for a hundred years before the player characters get there, then players have some chance to see how things are going in each shard. I still don’t see the model fitting well with the kind of character power curves we have in current games. If character development was more about the journey than power gained, then balancing the encounters would be much less of a challenge. And the diverging histories more of a benefit.

[Timothy Burke]

Mike completely groks my ulterior motive here, as he has learned to from long experience with looking past my smokescreens.

In a nutshell, I'm trying to figure out with this and some subsequent entries I'm cooking up whether the problem with world persistence is:

1) technical in the sense of programming
2) technical in the sense of server loads or other hardware considerations
3) economic in the sense of, "We already know how to do it, but it's too expensive"
4) conceptual in terms of "We just don't think that way because the path-dependent nature of MMOG design so we really don't know how to think through this"
5) philosophical in terms of "It's a shitty idea"
6) managerial in terms of "it places huge burdens on live development teams and players will dope it out and exploit the hell out of it"
7) marketing in terms of "players say they want it, but they don't really".

I'm going to keep at this, so we'll see. I readily grok that I don't get to evade scalability; I'm just curious about the relative granularity of the "technical" or "conceptual" problems, about where it is that those questions really start to get ugly.

[function]

Plenty of MMO players are already hopping between multiple characters, server, and even games that they play in parallel. In search of variety, or rather in search of respite from burnout from the eternal treadmills of their immutable (dare I say... "persistent"?) worlds. In that context, orcs who vary their reactions to attackers based on population are neat, but aren't shards that evolve to differ wildly from one to the next even neater?

[RedKnight]

>>>I've always wondered what a game world would be with absolutely zero NPCs, just player characters?

If you want to see what a world with no NPCs is like, go check out Urban Dead (www.urbandead.com) a browser based zombies vs humans MMOG. Very fun.