Jump to content
  • Advertisement
Sign in to follow this  
Carandiru

Abstract World Management, is it trivial?

This topic is 4270 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


Link to post
Share on other sites
Advertisement
Quote:
Original post by Carandiru
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.

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


Link to 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


Link to 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


Link to 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


Link to 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


Link to 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


Link to post
Share on other sites
Quote:
Original post by RPG_Programmer
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)


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


Link to post
Share on other sites
Guest Anonymous Poster
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


Link to 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


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!