Best approach for space partitioning?
BlitzMax Forums/BlitzMax Programming/Best approach for space partitioning?
| ||
| 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. |
| ||
| Can your players really explore 6,969,600 coordinates? Maybe you could cheat a bit and have different resolution for open expanses of terrain as for areas near roads and indoors? |
| ||
| What stuff do you need apart from the terrain data? If you just need to store the specific type of soil for each tile, you should be able to keep that to less than 8bits per tile. With 8bits you would need about 6.6Mb for the terrain, which shouldn't be a problem. Just store it as an array. If you have only 16 different types of landscape tiles, you can keep it to a 4bit array and then you only need 3.3Mb. For the terrain data itself nothing beats an array. If you have extra stuff, which I assume you do, you should decouple that from the terrain, as it is likely to be much more sparsely distributed. A quad tree is no bad solution, or you could use regular clusters that span X*X number of terrain tiles and contain a clean list of what goes where. Again that is easy to index and easy to predict preloading/swapping of if nescessary. I don't understand why you want to use a tree for the regular terrain, but maybe I have misunderstood something. |
   |