Im making a game in which users via a flash frontend controll a character in a huge world.
The client connects to a server written in Java, running at my home via sockets. This is not what i have a problem with
As users join a new class (userInfo) is created for them this class contains methods for getting the values; xloc(), yloc(), rotation(), movementSpeed(), rotationSpeed(). These values are being updated just fine by the server and this isent where i have a problem either..
The users are all in a big world, there are no zones. Users are server side kept in a huge hashtable with their socket values as keys and induvidual classes as values (above). Now as i want to keep the users updated on whats happening (otherwise this game wouldent be much fun) i send them the data for the entire world every 100ms and interpolate actions inbetween. This is touching on the problem =P
As more users join, say we have 100 users connected, i need to send 100 complete sets of data for the entire world. This is bad. Uses excessive server power and uneccesarry bandwidth. This is the problem
So what im trying to get help with is a way of figuring out which clients need data about what other clients, i drew a pretty little picture to help explain.
(the picture text is not completly correct anymore, whats in the post is true)
From the picture you can see that we have 6 users connected. but only the nodes (node = user) 4, 5, 6 need to know about eachother. nodes 4, 5, 6 do not need to see what nodes 1, 2, 3 are doing and the nodes 1, 2, 3 dont need to know anything about anyone but themselves.
the reason i drew in r ( radius ) in the picture is that each user has a given screen size and only need to get data about what they can see on their screen ( 2D game ), r is the same for all users and a little bigger than the clients visible area to provide a buffer.
So.. in what ways could one figure out which users need data about what other users without iterating through all the users and comparing their distance to all other users. This would be bad b/c it would provide a algorithm running time of O(n^n) and basically become a big *** bottleneck
Hope i made the problem clear and that you all understood.
Any help would be grand!