Efficient Zoning Code

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.

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.

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 :-)

Thanks guys. I'll test some of this out and check the performance.