Yesterday, Jay and I discussed how to represent the world on the server side. We came to the conclusion that a tree-based scene graph would be appropriate for this task.
Basically, the idea is this. Each area server (the world is split between multiple server processes, each handling one region/area) receives a rectangular region for which it is responsible. Upon receiving the coordinates, width, and height of the region, the area server builds a single-node BSP tree out of it. This first node (called the root) then branches off into two more nodes (called children) as more objects are added to the world. When even more objects are added, they both branch off into two nodes (leaving us with 7 nodes in total), and so on.
So, what's the point of this? Well, first of all, it reduces the CPU time needed for collision detection. To check if an object is colliding with another, the server only has to cycle through the object belonging to the same node, as opposed to all objects in the entire world. Further, it simplifies load balancing. If an area server gets busy, it can simply hand over a node to another area server, and forget all about it. Neat, huh?
I wanted to visualize this, so I spent an hour this afternoon writing a Windows application that places 100 objects (blue pixels) in random positions, and subdivides the world (a 320x320 pixel region) into smaller and smaller ones, until no region contains more than four objects. The red lines represent subdivisions. Take a look at the screen shot!
