• 15
• 15
• 11
• 9
• 10

# Continuous visibility sets

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

## Recommended Posts

This probably belongs in one of the other forums, but I couldn't figure out which - feel free to move.

I have a 2D multiplayer game, played from a top-down perspective. Each player has a single avatar, with a limited range of vision, which move continuously (i.e. no teleporting). Obviously, I only want to send each player updates for the other avatars which are within the player's radius of vision.

Now, I could just use a kd-tree (or similar), and perform visibility queries for each each player, at every update. However, this seems a little expensive, especially since the set of visible avatars is likely to be very similar (or even the same) in consecutive frames.

Is there some method/data-structure that would let me take advantage of the temporal continuity between consecutive frames?

##### Share on other sites
What about a simple quadtree? You could use the query function and that will return all avatars in the specified view range (via a bounding sphere).

For instance, here is a quick mock-up example:

//--Are there any avatars in tange of us?List<Avatar> selectedAvatars = quadTree.Query(new BoundingSphere(playerPosition, viewRange));if (selectedAvatars.Count > 0){    //--We found some, loop through the found avatars and send them an update to let them know about us    foreach (Avatar player in selectedAvatars)    {        //--Send update (source player, destination player)        SendUpdate(this, player);    }}

If there are 2000 players in the area your query may only return 5 in your view range in a matter of milliseconds, which is fast and effective for what you need.

Just an idea. Best of luck and happy holidays.

##### Share on other sites
Quote:
 Original post by UltimaXWhat about a simple quadtree? You could use the query function and that will return all avatars in the specified view range (via a bounding sphere).
Right, this is the basic approach I mentioned: throw everything into some sort of spatial partition (quadtree/kd-tree/spatial-hash/whatever), and then run view queries every update.

It is quite likely that this will perform fairly well, and given that I am not designing for an insane amount of players, my be sufficient. But it feels a bit inelegant, and I am trying to come up with some way to take advantage of the temporal continuity of my setup...

##### Share on other sites
That may be true, but it's still going to beat the n^2 brute force. I am not really sure of any other methods for dynamic data. If it was static you could compute a PVS, but even that would require checks every frame against a large data set.

You could do the simple player->avatar distance check, but that is going to kill your performance. You're right that spatial partitioning "seems a little expensive", but if you consider the performance boost they provide then it's well worth the alternatives. Also, spatial partitioning is mostly done at loading time and after that it's just checking quadrants, cells, whatever the case may be. You will just have to weigh the costs and see which one works best for your situation. Like I said, I am not sure what other alternatives there are so sorry I can't be of more help.

##### Share on other sites
Quote:
 Original post by UltimaXThat may be true, but it's still going to beat the n^2 brute force.
Ah, ok, I see the confusion. I didn't word my original post very well - brute force was never considered an option. The baseline approach I am looking at is maintaining a spatial partition, and running queries for each object at each update tick.

Going with a spatial hash for simplicity, you can keep the spatial hash updated in linear time, and the query for each object is roughly constant time, for a per-tick cost of O(n). The constant factors may be fairly high in places, but it is far and away ahead of an O(n^2) brute force.

What I am looking for is an adaptation of a spatial partitioning method, such that it can take the continuity of object motion into account when updating the spatial tree. I don't know if such a thing exists, but if it does, I would assume it has applicability to the N-body problem, etc.

##### Share on other sites
I was just using brute force as an example. Also, the reason I suggested quadtree was because you mentioned top-down and the players would/could be in constant motion. I recently implemented a quadtree because, I too, was researching some spatial partitioning algorithms and that just happened to fit my need.

The test application I made has 100 "players" all moving around in a top-down perspective. All of these players are checking and doing collisions against each other. On top of that you can click on the screen and "pick" one of them and it will do a query and tell you how many objects it queried and if you successfully picked that object. Out of 100 objects it usually returns around 3-15 objects it queried. Also, with all of these collisions, checks, etc. it still runs at 2000 FPS.

So the quadtree I made will handle objects in motion with no problem.

I used this one as a starting point.

##### Share on other sites
Fair enough, and thanks for the reality check on the performance front - looks like I may be over-analysing things. I don't expect to have more than a hundred players, and a few thousand objects in game at any one time.

##### Share on other sites
I believe Sweep and Prune does what you're talking about (taking advantage of continuity over time). But I'm not sure how well it will work in a "visibility" scenario. I think it's more for collision detection.