Well, I'm looking at implementing a coordinate based MUD server, and was wondering what would be the best way to partition a potentially huge world.
So far it seems like the wisest approach would be to use quadtrees, although representing a huge world will take up a ton of space.
I was thinking each coordinate would represent a 2 foot by 2 foot square - and each coordinate could hold at most one player, one or more items (based on their size), etc. Even still, one square mile, 5280 feet by 5280 feet = 2640 x 2640 coordinates. Assuming that each leaf coordinate had a "pointer" to it's parent on the quadtree, and a tlist containing any and all objects it contains, as well as a few bytes set aside for terrain info and such, I'm estimating the smallest I could get each coordinate would be approximately 12 bytes. Non-leaf coordinates would have a pointer to their parent, and 4 more pointers, one to each quadrant, and would also store some information about it's children. For instance, if the nodes 4 children (each leaf nodes) had no players in them, it would store this information itself so that the 4 children wouldn't need to be checked. This is also why I'd implement 'pointers' to the parents so that information could propagate upward - if a node 3 levels from the bottom of the tree was representing 256 leaf nodes, and none of those leaf nodes had any players - any algorithm that was searching for players in that area would not need to search any farther than that node - saving 256 + 3 search calls.
Problem is, one square mile is 2640*2640 coordinates, or 6,969,600 coordinates. At a minimum of 12 bytes, that's 84 megs per square mile in the game - and that's just the data for the leaf nodes. If the rest of the tree were to be fully assembled, that number would jump tremendously (with all of the duplication of data at various tree levels, all of the extra pointers for each layer of the tree, etc.) I'm guessing with the rest of the tree would at least quadruple the number (and probably be more like 10x the #).
Granted, I plan on using a lazy loading technique and only loading portions of the map that are near players (and unloading them after they've been empty for a while). This will allow me to only store the actual leaf nodes in the database and construct the tree from the ground up - and only the necessary portions of the tree will be constructed to conserve RAM.
Even so, the tree will take up huge amounts of RAM if a lot of players are logged in and all in different areas (thus requiring much more of the map to be loaded.) Is there a better and more space efficient approach to doing this?
A few points to keep in mind: I don't want to dynamically generate the world, so using something like a Perlin noise algorithm to construct the world based off of a static seed is a no go. Also, each coordinate needs to store information about the underlying terrain, soil type, etc - and these variable can change due to player or game impact (i.e. acid rain may change the soil type), so as far as I can tell sparse arrays aren't really going to be an option since I can't group a large homogenous landmass into a zone and then just give the attributes to the zone.
Hmm, any thoughts/ideas/recommendations are welcome.
So far it seems like the wisest approach would be to use quadtrees, although representing a huge world will take up a ton of space.
I was thinking each coordinate would represent a 2 foot by 2 foot square - and each coordinate could hold at most one player, one or more items (based on their size), etc. Even still, one square mile, 5280 feet by 5280 feet = 2640 x 2640 coordinates. Assuming that each leaf coordinate had a "pointer" to it's parent on the quadtree, and a tlist containing any and all objects it contains, as well as a few bytes set aside for terrain info and such, I'm estimating the smallest I could get each coordinate would be approximately 12 bytes. Non-leaf coordinates would have a pointer to their parent, and 4 more pointers, one to each quadrant, and would also store some information about it's children. For instance, if the nodes 4 children (each leaf nodes) had no players in them, it would store this information itself so that the 4 children wouldn't need to be checked. This is also why I'd implement 'pointers' to the parents so that information could propagate upward - if a node 3 levels from the bottom of the tree was representing 256 leaf nodes, and none of those leaf nodes had any players - any algorithm that was searching for players in that area would not need to search any farther than that node - saving 256 + 3 search calls.
Problem is, one square mile is 2640*2640 coordinates, or 6,969,600 coordinates. At a minimum of 12 bytes, that's 84 megs per square mile in the game - and that's just the data for the leaf nodes. If the rest of the tree were to be fully assembled, that number would jump tremendously (with all of the duplication of data at various tree levels, all of the extra pointers for each layer of the tree, etc.) I'm guessing with the rest of the tree would at least quadruple the number (and probably be more like 10x the #).
Granted, I plan on using a lazy loading technique and only loading portions of the map that are near players (and unloading them after they've been empty for a while). This will allow me to only store the actual leaf nodes in the database and construct the tree from the ground up - and only the necessary portions of the tree will be constructed to conserve RAM.
Even so, the tree will take up huge amounts of RAM if a lot of players are logged in and all in different areas (thus requiring much more of the map to be loaded.) Is there a better and more space efficient approach to doing this?
A few points to keep in mind: I don't want to dynamically generate the world, so using something like a Perlin noise algorithm to construct the world based off of a static seed is a no go. Also, each coordinate needs to store information about the underlying terrain, soil type, etc - and these variable can change due to player or game impact (i.e. acid rain may change the soil type), so as far as I can tell sparse arrays aren't really going to be an option since I can't group a large homogenous landmass into a zone and then just give the attributes to the zone.
Hmm, any thoughts/ideas/recommendations are welcome.