I got lots of headaches in the last days thinking about the known-list problem. Please help me... Assume you have 10.000 Mobiles in the World. Should i store a KnownList for each Mobile (in the mobile?). I think not, its to slow. I need a fast algorithm for the known list. Right now i have done this with region, but i am not so satisfied with this solution. Should a player/mobile update its known list by it self, or should there be some masterprocess which iterates through all mobiles and updates there known list. If you have such a large number of Mobiles, recalculating their knownlist could be really timeconsuming. I need a fast algorithm for this. please help... i cannot think anymore about this issue... :D

If all 10k objects were in the same area, each having a referrence to the other 10k objects, that'd require about 400mb of RAM.

I don't think I any PC is capable of updating 10,000 entities in real time even without known-lists, assuming that you're talking about a standard style FPS game and requiring a large amount of them to be rendered in 3D.

If you're talking about some kind of simulation where those entities are not drawn, then you might be ok, depending on what you're trying to achieve.

Given we're in the network forum, I'd guess that you're trying to write a server to handle that situation, and I have no experience there whatsoever. Try it and see!

Quote:Original post by HeftiSchlumpf

Should i store a KnownList for each Mobile (in the mobile?). I think not, its to slow.

That's a matter of storage requirements, not speed by itself.

Quote:Should a player/mobile update its known list by it self, or should there be some masterprocess which iterates through all mobiles and updates there known list.

That depends on architecture and type of processing you need.

Quote:If you have such a large number of Mobiles, recalculating their knownlist could be really timeconsuming.

It can be. But there's not much to do about it.

When an entity moves, you do something like this:
1) Remove entities which are max_distance away
2) Scan the world around entity's location and find all other entities less than max_distance away
3) Perform union operation on this new and old KnownList

The rest is about implementation. Each of the steps can be quite expensive.

For 1), you can keep the list ordered, and scan from start/end until distance <? max_distance criteria is met. Depending on number of entities changed, keeping the list sorted can be quite fast.

In addition, when you remove an certain entity, you also remove self from entity's KnownList.

2) can be reasonably fast with some space partitioning structure. Quad tree is one of more trivial ones, R trees can work quite well if interest regions vary in size (you see an elephant further away than you do a mouse). Using cells can help as well, some factor in motion to determine the range.

3) This one is tricky since if you always compare full lists, set union is expensive. A good way is to have 2) return as little as possible. So rather than having 2) return all entities, it's preferable to limit the scan range.

If you imagine area of interest as a sphere/circle around individual entity, then you can approximate the search range either approximately or exactly as difference between old and new AOI. If you can limit your search only to this new area, then merging the two can be performed in constant or linear time (depending on representation of KnownList). With quad tree, this test can be used on quads themselves for coarse grained test.

If the above is done synchronously on same machine, then you need to perform the update once per entity move, with O(1)..O(logn) per entity membership changed.

But ultimately, the process *is* time consuming, so for many applications you can limit the number of updates. So rather than keeping state perfectly culled, you update both, in turns, and at lesser update rate, if your model allows for that. For example, updating once per second at most will limit the cost. In most cases, this will not be a problem after factoring in the time to propagate new entity data across network.

If your AOI range is 500m (for example), and mobiles are humanoids, then they can move up to 50kmph, or 13 meters per second, so they can cover 3% of AOI in this time.

You can, obviously factor the speed into AOI calculation as well. You can keep multiple world lists for differently sized objects. So a jet pilot would only receive entities larger than 3m, but up to 5km away, whereas a pedestrian would receive entities larger than 0.1m, but only up to 100m away, and ant all entities, but only up to 1m away.

Quote:If all 10k objects were in the same area, each having a referrence to the other 10k objects, that'd require about 400mb of RAM.

The reason for AOI approach is just in practical experience that most entities will not be in range of others. If they are, then there's no need for such extra complication, and you just update all on all clients, in which case 10k is a lot.

Quote:I don't think I any PC is capable of updating 10,000 entities in real time even without known-lists, assuming that you're talking about a standard style FPS game and requiring a large amount of them to be rendered in 3D.

Depends on type of updates. For most online games, on each tick, a subset of world entities will be touched on each update. Doing full physics for every entity on every step however is trickier.

Lock step however is capable of reaching such numbers, as Age of Empires and others have proven. It just depends on the simulation model used.

Thx so much guys, you made my day.

When there was no reply at this topic at first, i thought about 3 hours about a fast algorithm to keep the known-lists up to date.

My idea was a sorted-list for each dimension (x,y) .
So that the actual entity stores a left and right link to the next entities.
Each link has a value, so its like a graph with weight.

Nice idea, good tests on paper, and really fast, because i made it work with quicksort inside each entity, and not the whole list over and over again.

So far so good, but after a friend who works with me on this project came on, i told him how this algorithm works.
Later on, we found a bad mistake.


the problem is, that there is only one distance on one dimension, without any relation to the other dimension, which would make it possible to have an entity in a rage of 50m near on X-Dimension, but 1000000m far on Y.

This sucks.


Later on we worked a bit with scriblink.com together to find a nice solution, had a look ad quadtrees and octree stuff. I already knew them but they dont make sense for me. - How do one entity in an octree knows the other entities around it?

->
So our old solution, already implemented it but modified it again:

A uniform grid, including a linked-list which we made thread safe with enumerators. So we only need to lock the a few entities in that regions if we plan to update (regions -> uniform grid).

Its really fast and good not so time-consuming algorithm. While updating the regions of the entities, the client can raise callbacks an work on these list (shared for all) without locking.

I think i will post the code here later, when it is stable.
I need to do some fixes i missed yet, but i had to go to a friends house-party..

Just again, thx alot for your great tips.
The one with the mice and the elephant is really cool, i just need to add something like an object-height and with this i can just determine which needs to be updated.
Great!

Quote:Original post by HeftiSchlumpf

but they dont make sense for me. - How do one entity in an octree knows the other entities around it?

It doesn't. It allows for quick queries. You say: find all entities within r from point (x,y).

The reason for de-coupling of area of interest from spatial locality lies in that there might not be any spatial relation between entities.

Consider multi-zoned, clustered server. A player in group goes to another zone. It's now off-the-map (a whole different physical computer, on a different world), so there can't be spatial relation to it. Yet it remains subscribed to group members, as well as its own locality. In addition, it's temporarily subscribed to any relevant data it needs to know (for example, person attacking party members, or party chat, or some local events) and every one of them is still subscribed to global events (system and GM notifications, deus-ex-machina GM events, weather, time, who knows what).

Such cases may be rare (or not), but they do happen, and can be quite annoying.

For example, in a group, one person is away, and a new person joins. The new person won't be able to find out who the missing party member is, since they're not close.

With generic subscription model that's no problem. Even if solved for special cases, it quickly becomes annoying with portals (rooms, caves, houses). You either send too much information (standing on top of a sky scraper) or not enough.

As far as spatial queries go, GIS domain has researched them into oblivion, so it's a waste to not first look at those applications, since they solve the common case of spatial locality.

I'd be very very interested in your theory. Currently, what I have now is pretty simple. When an entity moved into a region, all entites are updated with that link to the player. Instead of each player know who he knows about, I have a list of each entity that knows of me. So when I want to broadcast a packet (which we do a lot), we know everyone we should send to. What do you have?

Quote:Original post by Antheus

Quote:Original post by HeftiSchlumpf

but they dont make sense for me. - How do one entity in an octree knows the other entities around it?

It doesn't. It allows for quick queries. You say: find all entities within r from point (x,y).

Can you explain it a bit further and give an example ?

Quote:Original post by HeftiSchlumpf

Can you explain it a bit further and give an example ?

Entity::onMove(Point newLocation){  if (distance(lastUpdate, newLocation) > movement_dead_zone) {    // find entities no longer in range    for_each(e : known_list) {      if (distance(oldLocation) > aoi_max_radius) {        unsubscribe(e);        e.unsubscribe(this);      }    }    // define the area we are interested in    Query q(Circle(newLocation, aoi_min_radius));    // returns a list of all entities that are within the new AOI    // log(n)    Set<entity> candidates = quadtree.find(q);    // current known list might already contain new entities    // find out which candidates are not yet in existing known list    // size(candidates) * log(size(known_list))    Set<entity> new_entities = set_difference(candidates, known_list);    // what I know about knows about me    // O(size(new_entities)),     // usually *log(n) for each player,     // *1 for everything else    for_each(e : new_entities) {      subscribe(e);      e.subscribe(this);    }    last_update = new_position;  }}

The above is quick and dirty approach for subscription model.

aoi_min_radius < aoi_max_radius, so once subscribed, an entity is known for a while longer to prevent too frequent updates when one is just skimming the range.

If no dead_zone is used, and subscription is tested each time an entity moves, then instead of testing for entire range, one can only test for difference I mentioned above. There, the candidates list will be much shorter (empty most of the time), but at expense of more frequent quad tree queries.

Subscribe operations perform several things:
- if element is already in known_list, they do nothing
- if new element is added, and known_list belongs to a player, the current state of the entity added is sent as baseline
- unsubscribe does reverse, if element is removed, notification is sent to player to forget about the object

Reasoning is that, if I know about X, then X knows about me. Hence, what I subscribe to, becomes subscribed to me. Static entities, and most non-player entities can ignore this. A rock will usually not care who is near it.

Last, most entities won't move enough to warrant AOI update. If movement_dead_zone is 50-100m, then in most cases, they will trigger infrequently, perhaps once per entity life-time. An NPC that just does some tiny patrol around a house will never trigger it, players walking around it will.

Perhaps the most problematic case above is "herds". When a group of something moves, it will consistently trigger updates. For NPC movement, this can be solved by performing AOI test on group, rather than individual entities. A group of players traveling together however will still trigger frequent updates.

Furthermore, known_list can contain flags about why an entity was added. This way, it becomes possible to keep entities around even when they fall out of range, or they never were in spatial proximity. Player's inventory, or group members for example are both this type of subscription.

If portals are used, then forced subscription without range check can be used. When player enters such a zone, it is made aware of all entities in new zone, regardless of range or visibility.

I won't go into implementation of quad tree, since that's an elementary structure and there's plenty of implementations found in just about any relevant text book.

Lastly - much of this assumes typical MMORPG-ish behavior (fairly static world, mostly dumb or trivial NPCs, few players, physics is mostly basic collision detection).

Quote:
Quote:
Original post by CIJollySo, would using quadtrees give me a significant enough performance boost to warrant the extra effort?

Unlikely, but it really depends on the types of objects you have (are they all the same size vs. largely differing sizes) and what type of collision queries you hope to perform on them.

Due to its inherent simplicity, a (uniform) grid tends to have much better cache performance than tree-based structures. The uniform grid breaks down a bit when you have objects of greatly varying sizes, but in those cases you can use a hierarchical grid to address that problem. A hierarchical grid typically always outperforms a quadtree/octree for collision detection purposes.

Source: http://www.gamedev.net/community/forums/topic.asp?topic_id=414915


Thx for your great example and nice explaination.

I will present my solution in tomorrow evening, right now it is 2:08am here.

So far, its made with a uniform grid, multithreaded.