Archived

This topic is now archived and is closed to further replies.

opciz

mmorpg, spatial data structures & algorithms

Recommended Posts

What kind of data structure and algorithms are best suited for spatially organizing scene data in a typical 3d mmorpg?

Share this post


Link to post
Share on other sites
Probably quadtrees as a huge world will probably be mainly 2-dimensional.
This can be dynamic, by splitting the whole world until each cell is manageable, or by design, by dividing the land into cells.
Each cell could then contain other data structures, eg. a large castle or dungeon could have a BSP for the inside.
Look at the world map for Second Life, it''s easy to see that they zoned the world in advance, as all parts are square and about the same size.

Share this post


Link to post
Share on other sites
Splitting the whole world into manageable cells was something that i originally had in mind. Frustum culling would be fast and easy to implement. I also had an idea on how to implement a LOD system. The range to the viewer determines how deep down the quadtree the renderer should traverse (shorter range = deeper = higher detail). The scene data must therefor exist on every level in the quadtree where they are detailed enough to be rendered. A neat way I thought of not having to traverse hundreds of detailed scene data that gets culled anyway.

However, my main concern about using this approach is that the quadtree quickly gets too large and unmanageable as the world grows. Is this going to be a problem? Is there any good alternatives to quadtrees?

Share this post


Link to post
Share on other sites