Back to General and Gameplay Programming

Abstract World Management, is it trivial?

General and Gameplay Programming Programming

Started by Carandiru November 07, 2006 08:21 PM

18 comments, last by Bob Janova 17 years, 5 months ago

1,070

November 09, 2006 06:24 AM

Quote:Original post by Jack9
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!

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?

Kylotan

10,510

November 09, 2006 09:47 AM

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.

NotAYakk

876

November 09, 2006 10:37 AM

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.

wodinoneeye

1,691

November 09, 2006 09:25 PM

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.

--------------------------------------------[size="1"]Ratings are Opinion, not Fact

razialx

122

November 10, 2006 11:36 AM

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

NotAYakk

876

November 10, 2006 01:56 PM

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.

Jack9

102

November 10, 2006 03:52 PM

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]

Carandiru

212

Author

November 11, 2006 05:42 AM

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/

NotAYakk

876

November 11, 2006 08:20 AM

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.

Bob Janova

769

November 11, 2006 02:59 PM

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.

Abstract World Management, is it trivial?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Abstract World Management, is it trivial?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines