Efficient Zoning Code
Author
I'm currently working on a server for a 3rd person multiplayer shooter I've been coding (think Infantry at www.station.com, but less 2d if that makes sense). Anyway, I know for my networking code to be more bandwidth efficient, clients should only be sent info about players and other objects near them. This, of course, could easily be solved by looping through players and checking positions, but isn't this a waste of processing power?
I've been trying to find a way to send players the information they need without the need for an/multiple if statements within a loop of all the players. As the number of players grows, this architecture just seems like it would take too much time. It's really been bugging me because every time I think I might have something it ends up that I'm going to need to loop through players and check a condition anyway.
Anybody have any suggestions?
BTW: Game is designed (right now) to support less than 100 clients, most likely around 40.
My first thoughts on this points to breaking your world up into chunks (2d or 3d depending on how things are layed out) and as players move around the game attach them to the chunk they are in, the its just a matter of either checking chunks instead of players (possibly maintaining a list of chunks with players in and only checking that list).
An Oct or Quad Tree should help with this a great deal, infact given you can subdivde them down as needed you could probably get away with never having to directly check a player at all, just to the closest chunk.
An Oct or Quad Tree should help with this a great deal, infact given you can subdivde them down as needed you could probably get away with never having to directly check a player at all, just to the closest chunk.
I've never use them myself but I believe PVS's are great for this kind of thing (potentially visible set). Basically you create a list of every discrete location/room in the level, then find everywhere you can see from that location. You can do this by hand or there are algorithms to do it as well I think. Anyway once you have that you only need to update a player with info from any room/region thats with the PVS of his current location.
If your going for a big outdoor terrain this might not work though as you can see everywhere ... in that case its probably just to break your work up into a big grid as phantom said.
If your going for a big outdoor terrain this might not work though as you can see everywhere ... in that case its probably just to break your work up into a big grid as phantom said.
The problem is you need one PVS per player, containing all the other players. This turns into a (N^2 log N) thing very quickly.
The easiest thing to do would probably be to stick all the players in an octree or quadtree, and then set a maximum visible distance. Run a sphere (or circle) query centered on the player over your tree, and consider only the other players that are within the results of this query.
Another thing, which is more appropriate for MMOGs, is to keep an entity update queue for each player (this uses N^2 storage), and sort it by something like (k * time_last_update_sent + l * distance_to_player). Then, each step, for each player, you send data about the closest N players, and then re-insert them in the queue (they should have moved back, because you sent data and thus updated time_last_update_sent and probably distance_to_player). Every step, you also re-visit the queue of ONE player, and update the "distance to player" metric, so that distant players who move closer to the player will be discovered sooner.
Or, for 40 players, you can put their player Id (or pointer) and position in an array of structs, and just iterate over the entire array for each player -- it'll cache very well (16 bytes per player times 40 players is 640 bytes, which is 1/12th of the L1 cache in a Pentium IV). Chances are, in reality, this will be at least as fast as any fancier implementation, and it'll be a doddle to implement and test, too :-)
The easiest thing to do would probably be to stick all the players in an octree or quadtree, and then set a maximum visible distance. Run a sphere (or circle) query centered on the player over your tree, and consider only the other players that are within the results of this query.
Another thing, which is more appropriate for MMOGs, is to keep an entity update queue for each player (this uses N^2 storage), and sort it by something like (k * time_last_update_sent + l * distance_to_player). Then, each step, for each player, you send data about the closest N players, and then re-insert them in the queue (they should have moved back, because you sent data and thus updated time_last_update_sent and probably distance_to_player). Every step, you also re-visit the queue of ONE player, and update the "distance to player" metric, so that distant players who move closer to the player will be discovered sooner.
Or, for 40 players, you can put their player Id (or pointer) and position in an array of structs, and just iterate over the entire array for each player -- it'll cache very well (16 bytes per player times 40 players is 640 bytes, which is 1/12th of the L1 cache in a Pentium IV). Chances are, in reality, this will be at least as fast as any fancier implementation, and it'll be a doddle to implement and test, too :-)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
