Sign in to follow this  

How important is space partitioning?

This topic is 4859 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on an RPG rendering engine that will be used for an MMO. The majority of the game will be in the open fields, with some hills. There'll be some trees, bushes, etc. And then the characters. Is there a need for detailed space partitioning? I understand why they would be needed for older games, but are they still needed today? In my past games, I've just used a linked list, or possibly a 2d array of linked lists to store game objects. Thanks. -Nick

Share this post


Link to post
Share on other sites
Quote:
Original post by nickwinters
Is there a need for detailed space partitioning? I understand why they would be needed for older games, but are they still needed today? In my past games, I've just used a linked list, or possibly a 2d array of linked lists to store game objects.

Thanks.

-Nick


yes absolutely they're still needed. the amount of geometry present in any large world even if it's just a field is pretty huge. you can cut rendering costs down dramatically if you do some simple culling via quad-trees/bsp-trees/whatnot. further, for a MMO you need to cut down dramatically on network traffic since it's one of the major bottle-necks. you'd use your same spatial partitioning technique to manage the network messages that are broadcast out to each client. i.e. a character on the far end of the world doesn't need to know anything about the movements of a character on the other end.

-me

Share this post


Link to post
Share on other sites
If I try to render several thousand billboarded trees in one of my applications on current hardware, my frame-rate drops significantly. Space partitioning alleviates a good deal of that, and they're only billboards (2 triangles per billboard). Imagine how much worse it will be with several thousand detailed player models all on the same server.

Also imagine collision detection, which is typically an n*n problem without something like space partitioning. 10,000 players times 10,000 players would be 100,000,000 collision tests per frame (and that doesn't count collision with NPC's or other game objects). If you use space partitioning, you can limit collision tests to be between objects within the same partition (and sometimes in neighboring partitions), greatly reducing the number of combinations that need to be checked.

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
yes absolutely they're still needed. the amount of geometry present in any large world even if it's just a field is pretty huge. you can cut rendering costs down dramatically if you do some simple culling via quad-trees/bsp-trees/whatnot. further, for a MMO you need to cut down dramatically on network traffic since it's one of the major bottle-necks. you'd use your same spatial partitioning technique to manage the network messages that are broadcast out to each client. i.e. a character on the far end of the world doesn't need to know anything about the movements of a character on the other end.
-me


That's a great point about the network traffic. Another point that brings to mind is that if you want seamless transitions between zones (or servers), you will need to implement another space partitioning scheme on the servers. This is to determine each server's areas of responsibilty, to handle what happens when players move from one server to another, and to help handle fail-over scenarios when a server crashes.

I'm not sure how important that last one is to most MMORPG providers. SWG had a scheduled a reboot of all servers every morning, so reliable continuous up-time was high on their list of concerns. ;-)

Share this post


Link to post
Share on other sites
Quote:
Original post by s_p_oneil
I'm not sure how important that last one is to most MMORPG providers. SWG had a scheduled a reboot of all servers every morning, so reliable continuous up-time was high on their list of concerns. ;-)


<offtopic>
usually they do those kinds of things to mask memory leaks or other subtle bugs that just creep into the system after X hours of uptime. it's also a way to ensure that IT has time to patch the servers so they don't get virused or haxored. granted it's a bit annoying when the servers go down, but an MMO is one of the more complicated pieces of software one can write. also failover is tres expensive. :)
</offtopic>

-me

Share this post


Link to post
Share on other sites
I should clarify my original question. I do plan to have, at the very minimum, a 2d array of linked lists which stores the world, so for collision detection, objects just need to deal with the cell they're in, and if on the edge, the cells next to them. At the most, the cells would contain a couple hundred characters at peak times.

Beyond this, what would be the most useful? A BSP tree? A Quad tree?

Share this post


Link to post
Share on other sites
Quote:
Original post by nickwinters
I should clarify my original question. I do plan to have, at the very minimum, a 2d array of linked lists which stores the world, so for collision detection, objects just need to deal with the cell they're in, and if on the edge, the cells next to them. At the most, the cells would contain a couple hundred characters at peak times.

Beyond this, what would be the most useful? A BSP tree? A Quad tree?

If its outside a quadtree or octree is most likely to be used. BSP trees are for indoors

Share this post


Link to post
Share on other sites
Quote:
Original post by nickwinters
I should clarify my original question. I do plan to have, at the very minimum, a 2d array of linked lists which stores the world, so for collision detection, objects just need to deal with the cell they're in, and if on the edge, the cells next to them. At the most, the cells would contain a couple hundred characters at peak times.

Beyond this, what would be the most useful? A BSP tree? A Quad tree?


Well, that is space partitioning, isn't it? I'm sure you also won't render cells that aren't visible to the current camera. Whether you need more space partitioning thant that really depends on how big the cells are and how many game objects can be in it.

Share this post


Link to post
Share on other sites
Of course if they used dynamic clustering software and made their server side stuff useable with it then there wouldnt be any need for any kind of reboot to patch the servers, they could take them down one at a time seamlessly. Of course that dosnt fix the shitty coding that may have introduced memory leaks into the game server software ;).

Share this post


Link to post
Share on other sites
You could write your engine to handle real life scenes and then see if you're too slow or fast enough. Pvs is just an optimization technique and it might very well be that your bottlenecks could be somewhere else. Also, what is your target computer system? Keep those things in mind.

Share this post


Link to post
Share on other sites

This topic is 4859 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this