are you refering to lazy loading?
Part of the robotics software I create involves the creation of a world built from sensor data (from cameras, lidar, whatever) as in:
(Not a screenshot of what I make)
This world is built up and then we apply planning routines to allow a mobile robot to navigate through the environment.
Currently we have a small world (50x50 meters, for example) and we only have information for the system in that 50x50meter world. I've been tasked with breaking up that world into smaller cells and allowing for an undefined number of these cells to exist. This would allow us to keep information outside our immediate area without drastically increasing the amount of memory or processing we need.
This is a solved problem in games and I'm wondering, does anyone have any resources out there for how it's typically done?
are you refering to lazy loading?
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.
Sorry for being vague, it's not intentional.
IF you guys know Elder Scrolls games you know it's a huge world divided into cells. As the player moves around the world the cells around him are loaded if he gets close to them or unloaded if he gets too far from them. I need to do something like that and am just looking for some research material on ways the problem has been solved.
An tree based system could work, I'll think about it.
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
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 in this spatial hashing paper for 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 into Minecraft's Chunks to 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 an R*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.
Last edited by LennyLenard; 11-01-2013 at 03:07 PM. Reason: Grammar?
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.
Last edited by Celestein; 11-07-2013 at 04:45 PM.
There are currently 1 users browsing this thread. (0 members and 1 guests)