Breaking Game World into Cells

I've done this in a text adventure game but I feel the scope is exponentially smaller than what you wish. This thread sounds cool and I'm interested though.

I'm not entirely sure what problem you're trying to fix by breaking the world into smaller cells.
One thing comes to mind would be the octree (or a quadtree for its 2D counterpart) as a datastructure of your world. As you insert new objects into your world, the octree can recalibrate itself into smaller chunks when a maximum amount of elements is reached at the parent node. The same thing can happen when you delete objects and need to delete these smaller chunks that are no longer necessary.

I use BSP trees to break up my world, and then use the node faces for navigation, stripping out anything too vertical. Stairs need some special hacks but you sort of find grid points within a navmesh poly if you are needing a grid (like if you are doing xcom style movement) or just connect the navmesh polys themselves.

For connecting, I find shared edges and do box or sphere raycasts to see if anything is blocked. If the two connected polys are not coplanar you have to use the shared edge and do the raycast in 3 stages.

In addition to bsps you could go with the aforementioned quad and octtrees, or kdtrees which are used a lot by games these days. I don't know anything about them though.

Here's some connection data:


And the same point of view with the navmesh draw turned off

I for one welcome our new robotic overlords.

From everything I've read (I searched for "chunking" instead of cells) it is a very complex issue that is generally delegated onto the engine. I didn't see any example of someone online doing this from the ground up.

There's tons of open source game tools out there. Lots of .map file builders and such. It is heavy reading though.

A lot of places make the artists do the work, marking a set of walkable faces in the art program. It saves a ton of work as auto generating pathing data from geometry is very tricky. Lots of funny cases to handle.

Artist-done games are typically those that have annoying invisible walls and little spots where it looks like you should be able to go but can't. But shouldn't be a problem for what you are doing.

I used the stuff inthis spatial hashing paperfor my game. Basically shows how to break up world into a grid, easily determine which grid cell any object is in, and use that to optimize collision detection, AI, picking, sound effects, etc.

It is a short paper with lots of diagrams and isn't too hard to follow. Even if you don't use the exact methods the diagrams should give you some ideas.

Without knowing more about the application, I'd even propose a simple 2D or 3D grid of a fixed size, say 2x2x2m. Assuming (going to be doing a lot of that here) you're only accessing a cell and its adjacent cells, it should be easy to navigate to neighbors, allow for fairly controllable max constraints (9 cells if you include diagonals with a certain discernible data density), and should scale alright as you add in more at the edges or update existing cells. Especially since you're, in theory, going to be using this with a real world, it could be mapped against a map (it'd probably break down on a globe level). Each cell's overhead could be as little as a global X,Y,Z coordinate, and perhaps a "local X,Y,Z" relative to your agent.

Again, with the assumptions, if you're looking at consistently dense data (as in, you have a vertex every 10cm for instance), you can get away with something like this since using a more dynamic system loses its benefits as an Oct/Quadtree will look the same.

You can look intoMinecraft's Chunksto see how they partition their game worlds in consistent pieces, since each terrain atom is a 1x1x1m cube. It scales up quite well, just requiring more storage space as more chunks are added/generated, but the amount in memory is pretty fixed.

Now, speaking from my personal experience, in my game Space Impossible (can see more about it in the other thread), I use anR*Tree. It works because data density isn't consistent, much of the game world is empty, and what is being partitioned consists of area bound 2D objects.

From a very early test, with unrealistically tightly packed data, from Oct 2012.


But it really really depends on what you're storing in those cells.

Not entirely relevant, but could offer some clues:Gamasutra: Matt Klingensmith's Blog - Overview of Motion Planning

Celestein_sl said:

I program mostly in functional languages/styles(including in games), the way I've done this in the past in through simple lazy evaluation.

The entire "world"(or an infinite sequence for procedural content) is one data-structure(of whatever type) and each section is simply evaluated on an as-needed basis. It makes this "problem" really trivial in my experience.

The only downside is it tends to be computationally more expensive.

You way that you actually implement it can be pretty wildly different though, you could still break it up by "cells", or you could simply have buildings, objects, creatures, whatever, be points of data that you apply transforms to get the 3d world based on their properties.

Click to expand...

It sounds to me that Tuco is more memory constrained than anything. I don't think he needs a lazy loading scheme but more of a memory management scheme. I would consider some type of intelligent cache maybe... You ask the cache to fetch objects (buildings etc) for you. This guy keeps track of what's loaded and other state (what direction your walking) and it can selectively "unload" objects. You can develop some type of scoring algo to determine what to unload when to do it. You could even put it back to disk in some type of access format that's faster than the first load...in case you need it again.