# Spatial partitioning for continuous map?

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

## Recommended Posts

Hello, I'm trying to figure out a good way to do spatial partitioning for a continuous map... sort of like RuneScape, where the map is divided into large squares and each square loads as you approach it. I was thinking about octrees for each block of the map, but how should I handle cases where objects are between two squares? And how do I determine the height of the octree? I guess I could figure this out for static geometry, but what about dynamic objects that move around? What if an object moves higher than the top of the octree? I don't know that much about spatial partitioning, so does anyone have any suggestions about what might work for this situation?

##### Share on other sites
Hello Gumgo-

I think your general approach (partition into large squares, and then work on partitioning each square) is good.

Octrees for each block: yes, sounds reasonable. I also have had good luck with kd-trees. But almost any space partitioning would work.

How should I handle cases where objects are between two squares? There shouldn't be any space between squares. Are you saying the object spans two squares? That is, its bounding box intersects multiple large squares? You are probably fine. You can still use the object's center to determine which square it is "in", and that will work fine for front-to-back rendering and other calculations so long as your objects are (reasonably) convex. I assume that if square A and square B are adjacent, you'll render (parts of) square B even if the viewer is in square A.

How do I determine the height of the octree? Make it the highest legitimate height available to players! Every bit of accessible space needs to be contained in your squares.

What about dynamic objects? Use your static environment to set up space partitioning. You'll end up with the 3D volume partitioned pretty well. Then, each frame, you can remove all dynamic objects and re-add them at their new location. You can get cleverer than that if you'd like, but complete removal and re-addition isn't a bad start.

What if an object moves higher than the top of the octree? Every bit of accessible space needs to be contained in your squares. So that shouldn't happen.

Suggestions for what might work? I'd take a look at octrees and kd-trees. BSP trees are also good but may be more complex than you need.

-Thomas

##### Share on other sites
If your world is mostly planar, consider using a quad-tree rather than an octree. Simpler to implement, and no issues of height...

##### Share on other sites
Thanks for the replies!
I'm thinking perhaps I'll go with the quadtree approach because yes, my scene is fairly planar for the most part. I think perhaps what I will do is have three quadtrees per map square, one for terrain, one for static geometry, and one for dynamic objects. That way, I can get a tight fit for the min/max z values of the nodes of the terrain and static geometry, and I can handle the dynamic objects differently (since they're dynamic I'll have to handle the min/max points differently).

##### Share on other sites
A coarse grid and a fine grid in each coarse grid cell is a simple solution as well.

Quote:
 Original post by Gumgobut how should I handle cases where objects are between two squares?

For objects that straddle a boundary between partitions, you will have to place a reference to them in multiple partitions, otherwise you will get extremely wonky collision between objects near the partition lines.

I've addressed this issue in an RTS-type game by the following manner, we used a grid not a tree, but it is the same concept:

- after objects move and are being placed in partitions before collision, check where the min and max point of the object's collision hull are, and place a reference to the object in multiple partitions if necessary

1. 1
2. 2
Rutin
30
3. 3
4. 4
5. 5
khawk
14

• 11
• 11
• 23
• 10
• 9
• ### Forum Statistics

• Total Topics
633647
• Total Posts
3013108
×