• Create Account

### #15razialx  Members   -  Reputation: 122

Like
0Likes
Like

Posted 10 November 2006 - 05: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

### #16NotAYakk  Members   -  Reputation: 876

Like
0Likes
Like

Posted 10 November 2006 - 07:56 AM

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.

### #17Jack9  Members   -  Reputation: 102

Like
0Likes
Like

Posted 10 November 2006 - 09:52 AM

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]

### #18Carandiru  Members   -  Reputation: 212

Like
0Likes
Like

Posted 10 November 2006 - 11:42 PM

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/

### #19NotAYakk  Members   -  Reputation: 876

Like
0Likes
Like

Posted 11 November 2006 - 02: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.

### #20Bob Janova  Members   -  Reputation: 769

Like
0Likes
Like

Posted 11 November 2006 - 08:59 AM

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.

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS