Please forgive me if I ramble or use weird terms to try and describe what I’m after; I’m a programmer not a mathematician.
The scenario: A large number of players, playing a real-time game in 3d space, must be organized in a way where a server can efficiently update other players of any other players move, based on their range from one another. Players over a certain “distance” from each other don’t need to be updated about each other, and in fact should not be. However, if there are 3000 players, one must run 3000! To find out the ranges between everything.( Google tells me that ends up as a number with over 9000 digits; that’s insane and not worth considering for a near-real-time environment.)
The method that I’m playing with conceptually that makes sense from a server/programming side is to decimate the player populate down into more manageable chunks/clusters/clumps, centered around "hot-spots". Running a calculation of 6[Factorial] for range is better and doable. However 6 clumps doesn’t give near the kind of granularity desired in separating the groups.
The problem I have, is how to logically organize up to 3000 points in space in a way that each one can easily know what’s ‘near’ them, and what’s ‘far’ away from them, in an efficient way, from each individuals point of view.
This question is all about how to sidestep the factorial range calculation issue. If clumping isn’t optimal, I would love to hear about other solutions or ideas.
“Clumps” are a concept that makes sense to me, but certainly have their own issues, and seem to run into the same factorial issue fairly quickly and I'm not sure their truly suitable. If clumping IS the way to go, how would one determine/sort which points go to what clump, and probably more importantly, where to center the clumps?
a thing of note; Planetside 2 (free online mmofps) solves this problem I think; they use something called a "Sphere Tree", but I'm not sure what it is or how its used.
Edit 1: Some have been asking why I say this is a 3000! problem; let me run a quick example. Player 1 wants to know its range to everything, so it asks the server, and the server does 3000 calculations to find the range between player 1 and all the other players on the server. Now player 2 wants to know its range to everything. Well the server just did player one, so it doesnt have to do that, but it still has 2999 calculations to do... and then player 3 needs to know 2998 ranges... and so on.
A possible approach is to subdivide your space into zones, which have connections to all other zones close enough that a move in one needs to be reported to players in the other. When a player enters a zone, they are automatically registered with it, and unregistered with the zone being left. Whenever a player moves, the zone is notified, and in turn notifies its connected zones, who each in turn notify all their registered players. You may want to have the zones overlap a little to avoid having to constantly change registration when the player is moving along the edge.