• Advertisement

# Abstract World Management, is it trivial?

This topic is 4119 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## Recommended Posts

To start off, lets say you have a 200km squared world. Various details, a vast landscape, and about a dozen cities and villages inbetween you and your destination. So I already have basic scene management in terms of visibility. An octree that manages all static and dynamic objects that can been seen within the user's viewing frustum. This system manages it in a absolutely beautiful manner, I'm really proud of its outcome. As for my terrain, I can basically define any arbitrary size of Terrain, and each patch will be "streamed in" for when it is visible to leverage a huge vast world, with a reasonable impact to memory usage. So keep in mind this is a seamless world design. So the question of management for visibility has been answered. The question I now have how to manage the updating for n objects in my world. If I base these updates (npc walking around, monsters wandering, etc) on just what the player is able to see, the world beyond what is not visible will be on standby. This is simply not acceptable, yet a nice optimization if it could be leveraged in some manner. I was thinking of defining a sphere of influence that projects around the users character, and interecting sphere's of influence that contain objects would then be updated. So the problem I face now is how to manage all the game objects that need an abritrary update whether they are visible, or not visible. The world is seamless, and REALLY big. How does one accomplish this management and maintain performance? while ( n < nGameObjects, where nGameObjects = 5,000,000,000 ) nGameObjects.update() This doesn't seem practical Or am I overcomplicating the problem, is it more trivial than I think? Anyone with personal experience with this type of problem, or anyone with some insight to a possible solution, I would greatly appreciatte your feedback!! Thank you! -Carandiru http://www.uamp.ca/

#### Share this post

##### Share on other sites
Advertisement
Quote:
 Original post by CarandiruIf I base these updates (npc walking around, monsters wandering, etc) on just what the player is able to see, the world beyond what is not visible will be on standby. This is simply not acceptable, yet a nice optimization if it could be leveraged in some manner.

Are you sure it is not acceptable? If you can't see some NPC on the other side of the world, then why should you need to animate it? The key is to give your simulation levels of detail. You might have to keep track of the fact that an NPC exists in an area, but if the player is not in the area, that's really all you need to keep track of. When the player is in the area (or close to it), then you need to keep track of the NPCs movement. When the player can see the NPC, then you need to animate it. When the player can interact with the NPC, then you need to run its AI.

#### Share this post

##### Share on other sites
My understanding of oblivion and how they did it was that each npc had a timeframe of what they were doing through out the day, which was essentialy what they "Should be doing", a macro simulation... as the world was streamed in, this timeframe would be refrenced to decide who and what to show. WHile the npc was within "range", a micro simulation was ran that actually showed the npc doing things, One of the ranges was "while in view", so to speak.

I suppose you could run some type of octree method to decide what level of range the npc is at.

Optimumly, an npc on the other side of the world should have very little caclulations, the closer they were, the more is done.

A lot of this would be intefaced with some other micro/macro simulation, for things like economy and faction feuding, and such. Stuff happening in the micro would affect the macro, and vice versa.

#### Share this post

##### Share on other sites
Don't push a rope.

Objects that know they will need update should place themselves in the "to be updated" queue.

Objects that cause other objects to need updating should put them in the "to be updated" queue.

So, instead of asking every single object if it needs to be updated, the objects that need to be updated ask to be updated.

The "I need to be updated" logic might be more complex than just "I need to be updated at 10:00 pm". It could be:
"I need to be updated when I'm in view".
"I need to be updated whenever locations A-D are in view".
"I need to be updated once per game hour if the player is far away, once per minute if the player is nearby, and once per frame if I'm in view".

The idea of "pulling the rope" is that you start with "the player is looking at locations A, B and Z -- now update what I'm looking at, and other things that things I'm looking at depend on, etc.", instead of "do you need updating if the player is looking at locations A, B and Z?"

You are pulling data from the world, instead of pushing an update query to each object.

#### Share this post

##### Share on other sites
Most objects will be completely uninteresting to update when they
are far away (eg npc's doing their daily cycle).

I would make some sector-based system (eg 200x200 m areas) where
you just enter/exit (and with that spawn / destroy) 'uninteresting
npc's - no need to keep 5mio objects in memory)
In the spawning routine, you can make sure these npc's are at the
position they should be according to (for example) the time of day
(so npc's are spawned in their houses when it's night and you
enter their sector).

If it's _really_ needed, tag the really important npc's with a flag
and update them every x seconds (or minutes) - let's say this list
is a few 100 objects, that would still be possible.
And with update I don't mean animations but rather 'logic state and
position')

#### Share this post

##### Share on other sites
Thank you for all your feedback.

Just attempting to conceptualize from a first fore thought of world control/managment is very complex.

Specifically Im interested in "don't push the rope"

This is an interesting methodogoly of "pulling data out of the world, rather than pushing an update query on each object" I can see a huge benefit (performance wise) from this logic.

On question still remains, if I were to use this type of system, since it is based of in your reply on "the player is looking at locations A, B and Z -- now update what I'm looking at, and other things that things I'm looking at depend on, etc."

What about all other objects that are not visible, how do you pull the rope? As applying to "I need to be updated once per game hour if the player is far away, once per minute if the player is nearby, and once per frame if I'm in view".

Very cool replies, and some great ideas.

I understand the LOD way of doing all of this, if in view animate (skinning for example), if not in view update my position every n minutes, etc. Its just the shear NUMBER of dynamic objects that could possibly exist in the world, and how to manage them all. Are there any good books on this subject btw?
I'm looking into some AI books, but I'm not sure which one to get, any recommendations?

Thanks again,

Carandiru
http://www.uamp.ca/

#### Share this post

##### Share on other sites
Multithreading is the answer.

Run a thread for each area that has objects that need updating.

Do not store the 'area data' itself in memory, just the objects on the landscape. When that area is about to be entered, then load the area data into memory.

Thread synchronization will be important if you go that route.

Proper design can yield a result in which objects can update themselves regardless of where they are in the world. (On scene, or not)

#### Share this post

##### Share on other sites
Quote:
 Original post by RPG_ProgrammerThread synchronization will be important if you go that route.Proper design can yield a result in which objects can update themselves regardless of where they are in the world. (On scene, or not)

Are you proposing a separate thread that continuously cycles through each entity and determines the need to update? That would still waste as many cpu cycles as "pushing the rope" in a single thread.

This is going to introduce a lot of non-trivial (from a debugging point of view) bugs. On a single pc, there won't be any performance improvements either. I think the problem has a viable single-threaded solution.

#### Share this post

##### Share on other sites
I'd setup a very accurate timer and dispatch AI tasks every x ms to a different, distant NPC. I'd update closer ones first and more often fading off to something like x * x for ones very distant. I'd also make large "jumps" instead of doing day to day things like "Get up, Go to work" instead of "Get up, Get Dressed, Eat Breakfast, Pack lunch, Go to work, ..." like I would for ones in the same or neighboring sectors. You can also dispatch more "jobs" if you implement a multithreaded system when there is idle time (we do this). We have a work queue and if it gets empty it polls the "make work" part where AI can dump quick stuff when we have an idle CPU.

#### Share this post

##### Share on other sites
I have a very similar problem, but I'm using Hard Zones (no overlap or seamless) so it's a bit easier for me, I guess. If I was going seamless, I'd still break the world up into Zones for faster iterations.

How to deal with this problem is not trivial for me. In fact, my whole server design is based on solving the problem "how to keep everything running around and still be able to transmit gamestate information to players in a timely manner.

To say there is a single threaded solution that meets those requirements for ANY set of 1000+ dynamic entities is pretty silly, IMO. Even iterating through 1000 elements of a linked list to rearrange them, creates ungodly overhead. I'm really posting to try to explain how I do it with multiple players!

Note: Everything with the name 'Server' or 'Node' is an independent process. The messages described are not what I actually use, but try to convey the content.

First of all, I have 6 processes
(some of which I originally called servers)...they all start up about the same time and the login server blocks until they are all ready.

1. Login Server - Holds the connection open. It's responsible for authentication and spawns a UserNode on auth. UserNodes register with PC Server.

2. PC Server - Keeps track of UserNodes.

3. Zone Server - Keeps track of ZoneNodes. Spawns a ZoneNode for every Zone in DB, passing it the Zone data from DB. As a ZoneNode starts, it spawns 2 managers.
4. PCNodeManager which holds the data about PCs that are in the zone and processes their requests.
5. NPCNodeManager which starts up all the NPCs (NPCNodes) and keeps track of them.

6. World Server - My Console of sorts. I send it messages from my console directly, to manipulate elements of the game.

---

GameState is hard on the system. It's the most tasking thing by far.

UserNode gets the message "gamestart, MyCharacter" from a network read, looks up the position of the User from when they logged out...which is in the DB as MyZone,X,Y.

UserNode asks for the ZoneNode, from the Zone Server... "lookup, MyZone"

UserNode tells the correct ZoneNode "pc, join, MyCharacter, X, Y, MyUserNode"

Now the ZoneNode knows about all the NPCs and PCs in the Zone since the NPCs were loaded and respawn at the Zone NPCManager's whim and all the PCs send join/leave messages keeping the Zone PCManager up-to-date.

ZoneNode appends to the message, "pc, join, MyCharacter, X, Y, MyUserNode"+","+NPCManager(getNPCList())

Then ZoneNode passes the message to the PCManager(join,MyCharacter,X,Y,MyUserNode,PCList,NPCList)

PCManager has lots of things it's doing, so it doesn't want to be bogged down by this kind of work and creates a temporary process called
PCManagerDispatch(join,MyCharacter,X,Y,MyUserNode,PCList,NPCList)
AND adds MyCharacter,X,Y,MyUserNode to the PCManager PCList after afterwards.

This PCManagerDispatch process has filters that tell it what to do based on what it's passed.
'join' :
foreach PC in PCList
if(distance(PC.getLocation(),makeLocation(X,Y)) < radarRadius+10)
sendPC(PC, join, MyCharacter, X, Y, MyUserNode)
foreach NPC in NPCList
if(distance(NPC.getLocation(),makeLocation(X,Y)) < radarRadius+10)
sendPC(PC, join, MyCharacter, X, Y, MyUserNode)
then this Dispatch dies...

Each PC and NPC will perform their behaviors based on what it means to them for the PC to have joined at that location, which will include...
A concerned NPC sending a message to the ZoneNode "pc, moved, NPCNode, X, Y, NPC" meaning 'tell PCs that an NPC process NPCNode exists at X,Y' or maybe a "pc, moved, NPCNode, X, Y, NPC, aggro, 10, MyCharacter" which you can figure out.

The UserNode starts getting messages and can maintain it's own gamestate now.

In the case of misses (NPC's or PCs that enter into a character's view but dont get notified because of process time), all gamestates are really calculated every time something "moves", which includes leaving or joining the zone, so it will simply be updated correctly the next cycle!

Yes, all the PCNodes within radarRadius+10 get this message of "NPC Exists here" from ZoneNode even if they already knew that just because some yahoo joined the game....but this is ok serverside and will actually prevent misses in some cases. NPCs serverside consist of an ID, which is actually translated to an NPCname embedded within the zone map, clientside.

#### Share this post

##### Share on other sites
Quote:
 Original post by Jack9To say there is a single threaded solution that meets those requirements for ANY set of 1000+ dynamic entities is pretty silly, IMO. Even iterating through 1000 elements of a linked list to rearrange them, creates ungodly overhead. I'm really posting to try to explain how I do it with multiple players!

But wouldn't we be doing it for a small subset only? Also, we aren't exactly sorting them, and iterating over a list is an O(n) operation. It's not so silly if you assume a single-player, single-cpu environment :)

Very interesting post, but you approach it from the multiplayer angle, where going multi-threaded certainly does make sense - especially when you can split up the threads or even a number of processes between different physical servers to help lighten the workload.

Based on your description, it seems that the multi-threaded architecture is used largely for managing PC joining. You didn't go into a lot of details about the actual NPC updates. In particular, I'm not quite clear about how you propose to update NPC's - does the NPCNodeManager check for player proximity and prioritize the AI for the NPC's that are closer?

#### Share this post

##### Share on other sites
There is absolutely no reason why single-threaded can't perform equally well or even better than multi-threaded here.

1) As already stated, don't poll all the objects, just have an update queue, sorted by next update time. Objects that can do with less frequent updates get scheduled further down the time line than those that need rapid updates. Stagger the updates too, either with a random factor, or a hashed value, to ensure you're performing a roughly equal number of updates each time.

2) Split up the update routine according to purpose and importance. eg. Animation and physics are essentially cosmetic, and can be ignored if a player isn't nearby. Pathfinding may be unimportant for a distant peasant the player doesn't care about, but very important for a monster the player deliberately trapped behind a rock, so do pathfinding before moving it. With this sort of thing in mind, you can pass these parameters to the update function and let the object decide what is appropriate.

3) Create abstract updates. Moving from A to B should require low-level pathfinding for a nearby creature, but can probably be adequately handled by simple line interpolation for a distant one. Scheduling systems are great here: if an NPC is marked as being in the Inn at 9-11pm each day, and you're nowhere near that NPC, there's no need to worry about how it gets to the Inn. Just teleport it there whenever its Update function is called between 9 and 11.

Quote:
 What about all other objects that are not visible, how do you pull the rope? As applying to "I need to be updated once per game hour if the player is far away, once per minute if the player is nearby, and once per frame if I'm in view".

Upon updating a given object, the game should know how long it is likely to be before another update is needed, so it can push the object back onto the queue with a given time in mind. The only thing you then have to worry about is promoting objects in importance when you approach them, so ensure you have a way to pull them to the front of the queue. One simple implementation method: make sure that the object has a reference to its position in the queue, so than an 'emergency update' can pull it out of that structure quickly. You can obviously get a list of local objects from your octtree.

I don't think you'll need a book on this to be honest - just make sure your object updates are parameterised and staggered according to their need, and that you can handle infrequent abstract updates as well as fine-grained concrete ones.

#### Share this post

##### Share on other sites
In an area X units on a side, there are X^2 square units.

Suppose an area X units away costs 1/2^X in support costs. (LOD approximation if your world is a bin/quad/oct tree)

Define F(X) = (2X)^2 / 2^X

This is an upper bound of the overhead cost of every piece of terrain between distance X and distance 2X.

Then the sum,
sum(I from 0 to K) F(2^I)
is an upper bound to the cost of a world of radius 2^K.

= sum(N from 0 to K) 4 * 2^2N / (2^(N))
= sum(N from 0 to K) 16
= 16 K

So a world of radius N = 2^K has an overhead cost of roughly 16K.

In other words, the overhead of a quad-tree for a world of radius N is logorithmic in N.

...

So, a solution:

Build a quad-tree. Have each object that needs to be updated if objects are within 2^X distance enter itself into the Xth height quad-tree as "must be updated".

When you want to do an update, search from the top node in the quad tree down to where the player is and/or where the player is looking, and update each object registered with those nodes.

...

Another solution: (which may work well in concert with the above)

Keep a sorted list of "things to be updated in the future" with timestamps. Something to be updated once/hour simply reenters itself on the list at present_time + 1 hour.

...

Another solution. Add a temporal dimension to the above quad tree of updating -- your updates are located both in time and space.

...

Note that multi-threading doesn't solve resource problems. Each thread actually creates (by default) a meg of overhead (stack space), and in theory you could usually reimplement it with manual state maintenance.

Threading is a way of reducing the amount of state you (the programmer) have to keep track of, and of dealing with the CPU-resource in a less manual way. It doesn't reduce the amount of computation required to solve a problem.

#### Share this post

##### Share on other sites
Game objects will belong to one of several levels:

Furniture - mostly static/passive, are usually acted upon, but may have very slow behaviors like plant growth (or a hole that slowly fills itself in). This type of object usually doesnt move. Often individual objects arent as important as groupings (they can be generated from random seeds to match locational factors -- and discarded later when the player is long gone). Specific changes made by a player (like burning down a tree) would need to be saved in details as a 'mod' so that it could be reconstituted. These are most likely the most numerous objects (and have low behavior processing requirements). Out of sight little needs to be done for them.

Semi-Intelligent - things like animals that can move from area to area but have fairly simple behaviors (hunting/eating/managing a territory). Out of sight of a player they can be abstracted quite a bit (cellular automata type mechanism can be used and generalizations of groups could easily be done). Ecosystems can be built up over their simple behavior patterns. Realizing their details (from the abstract) when the player comes near might be done via generation templates (only a few parameters need be saved and many might be almost completely random ). Usually these dont require complex coordinated detail to be composed for them (how many different variety attributes do you need for a Wolf ???) Games already do this with 'spawns', but usually much more static. Simple NPCs might be of this type.

Significant - Objects that are capable of strategy and complex interactions with the players and the world (much heavier AI). These drive the plot interactions. They can be abstracted when out of sight to some extent, but their interactions
and effects on the world are significant and preferably should have some continuity (and would be harder to 'generate' realizization from abstract quickly when a player comes close). Even if they dont execute their AI constantly, the processing load is large (think some kind of goal oriented/planning AI ). A 'significant' object might not even have a physical presence, but act as a controller (a village as an abstract organization on a world map which coordinates the behaviors of all the local inhabitants...)
Depending on the complexity of the scenario there may only be a dozen 'significant' objects (or hundreds - every town/village as its own political entity as well as the free-agent plot driving personalities/factions).

Lackeys - Objects which are linked to a 'significant' which would be controlled as a group (Boss & Lackeys). They can be abstracted easier because the Boss's AI drives them and their own can be simpler reactive/command driven. They can be template generated when realized from abstraction. The 'Boss' moves around
on the abstract world map actively with a set of lackeys which can be fleshed out when needed. Lackeys could be used as pawns - moving them around as resources to represent/implement the 'boss's influence'. Lackeys likely would have more complex behaviors than the 'Semi-Intelligent' objects (more plot theme oriented). Able to do simple goal oriented directives (along with the typical reactive behaviors). NPCs in a town take their 'mood' from the town (sig) itself. They would alter their behavior from a normal schedule (coordinted from above). They still can have alot of role specific behavior, but the 'heavy lifting' of doing the higher AI would be done for them (saving alot of duplication of processing).

My project is similar to the OP except that I am doing a seamless world (ugliness of cross area interactions.... worse - cross zone servers).
The AI load is large enough to require more than one seperate AI server for the 'significant' objects -- with several tiers of hierarchies of local social entities/alliances/factions and fields of influence. Economies and ecologies are simulated at the abstract level to present appropriate situations
to the player (who sees the 'realized' details).

It will be interesting when online games actually start doing things like this in more than feeble rudimentary ways. CPU power only recently have begun to reach adequacy for reasonable AI -- example: I played UO for several years before they got around to (or able to) use pathfinding for the monsters (before that they only traveled in straight lines towards a target, making it very easy to force them to get stuck on scenery features.)

As I've mentioned in other postings, the game companies may be able to save alot of \$ by using such simulation mechanisms to drive their plots (and quest systems) versus the chore of handcrafting them in increasing volumes and complexities.

#### Share this post

##### Share on other sites
The first thing I thought of is, as it turns out, how Oblivion does it.

Develop a schedule for entities that can be referenced based on time, so that when an entity enters a certain range of the player (Sphere, or AABB) the entities can be set to _roughly_ where they should be doing what they should be doing. Then micromanagement can take over.

I guess an easy (overly simplified) view would be
Entity TIM has Schedule:
T:0 Get Up
T:100 Go Downstairs
T:300 Leave House
T:400 Get In Car
...
T:168300 Arrive Home
T:168400 Go to bed

So, for that entity, when it goes out of range of the player, we store the time that it became no longer active (given that these are relative times, interactions will take entities off their course and you can't expect them to follow this when under micromanagement).
So, when Entity TIM becomes active again, we take the difference in time to find where the entity should be. This is extremely simple, of course, and you could expand on it by doing perhaps a cursory evaluation of a tree of interactions to determine where things would be. This would be a computation hit when entities become active, but it would allow entities that are not active to have no affect on your CPU load.

So, a tree could involve decisions that you evaluate based on heuristics or just randomness, so things would not be as predictable. Of course, I don't know the nature of your entities. If this was a RTS type game involving flight for example, you could have decision trees for what they would have built in your absence.

If I am way off here, please let me know. I just ramble off the top of my head at times.

Good luck!
Tim

#### Share this post

##### Share on other sites
The problem with the "scedule" system is that it can easily result in "impossible" situations.

For example, the player blows up a doorway -- and so long as the player isn't near, NPCs can teleport through the door's rubble. But if the player stays near, the NPCs can't path past the rubble.

Unless you are really careful, the game can easily break down to "you have to go away from this location (at least 1 km), then start walking back at 1 pm, arrive at 3 pm, and the game will be in a special state" kind of features.

Or, "camp out for 1 minute" in order to teleport an NPC kind of features.

I suppose that isn't always game breaking.

#### Share this post

##### Share on other sites
Quote:
 Based on your description, it seems that the multi-threaded architecture is used largely for managing PC joining. You didn't go into a lot of details about the actual NPC updates. In particular, I'm not quite clear about how you propose to update NPC's - does the NPCNodeManager check for player proximity and prioritize the AI for the NPC's that are closer?

NPCNodeManager is just for message passing and Time-expensive calculations.
In general, the NPCs are just actor processes. They respond to messages.

The two ways I can deal with NPC AI are:

Wide...
Parallel AI process that monitors and reacts to predefined behaviors for changes in the NPC (process) along with an idle decision tree (the tree that starts with, I'm alive and healthy and at my starting location).

Narrow...
Set up an NPCAINode under the NPCNodeManager for each AI type in the Zone. Have it manage the AI for all the NPCs in the zone, reacting to predefined behaviors for changes in the NPC (processes) along with an idle decision tree (the tree that starts with, I'm alive and healthy and at my starting location), per type.

Given how much load is on the Zone Server and the ability to spawn Parallel AI from templates, there's no real good reason to go narrow IMO, other than it's harder to administrate on an individual NPC basis. I go wide.

There's no priority other than NPC AI in PC populated Zones, which should have priority, but that's not something I'm interested in enforcing and have not.

[Edited by - Jack9 on November 10, 2006 4:52:42 PM]

#### Share this post

##### Share on other sites
It seems to me like this is a very large topic, which doesn't seem to have many articles.

I really apprieciatte all of your insight, and have come up with an initial design for the update lod solution.

Basically, there with be the WorldZoneSphere, which is like a quadtree manager, with the ZoneSphereNodes. All These nodes will contain lists of the Abstract Object. With a Virtual Function, the actual object can then define itself LOD based on the the parameters given to it. The ZoneSphereNode maintains updates ("the function")

The Octree maintains visibility ("the form"), and pivots around the player instance. A super frustum, aka Abyss, is basically the communication protocol that associates objects ("the function") with instances ("the form"). Based on an intersection of the Abyss with the ZoneSphereNodes, you can reduce the working set of tests needed, and maintain a multithreaded solution for streaming new objects in when needed.

Thats a basic overview of my initial theory, implementation will work out all the little details overlooked.

My engine is already multithreaded, with the Scene and Render thread's running in parallel, so leveraging this structure is to my benefit.

Thanks again!

Carandiru
http://www.uamp.ca/

#### Share this post

##### Share on other sites
If you place every object in the leaves of your quad tree, then you won't be able to do "far-away updates" using the quad tree.

On the other hand, if objects can promote themselves to higher nodes in your quad tree, you can efficiently have "far away" things that get queried for updates.

Query your node, and adjacent nodes, if they want to be updated. Do it not only at the most fine-grained level, but at each level.

This results in you querying 9 nodes per level. There are a logorithmic number of levels -- so you have to query a logorithmic number of nodes.

The trick is only the objects that can respond to far-away queries can be in the "larger-level" nodes. So you'll only have to do O(lg(width of word) + # of items you have to query) work in the update phase.

The "visit everything" pattern falls apart when doing sparse visitation. When you are doing sparse visitation, you want to only visit a subset of the objects that corelate strongly with the objects that will actually do something when visited.

#### Share this post

##### Share on other sites
I like the 'add me and anyone I care about to the update queue' idea. How about splitting the world up into smallish sectors, and any object 'in range' (in the player's current sector or any adjacent sector) is automatically updated every update cycle. Those objects can add other objects to the update queue if they wish.

In addition, each object should have a maximum wait time. When an update has just been run for the object, it adds itself to the queue again for a time that far in the future. Then you can have 'always realtime' objects that have a wait time of one cycle.

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement
• ### Popular Tags

• Advertisement
• ### Popular Now

• 10
• 10
• 10
• 10
• 12
• Advertisement