Implement a rolling grid

[Moopli]

Create a multidimensional array-like thing that can constantly add rows and columns on one side while losing them at the opposite -- a rectangle/prism of active indices moving around in space, as it were. The grid will be generally centred on the player, and new data to fill the incoming edges is generated on the fly.

[jjonj]

Labeled programming and easy. I imagine we would represent this grid with a class, what kind of interface would it require?

[Moopli]

The basic idea of a grid like this is that from when a cell (a region in space) enters the grid's bounds to when it next leaves, it should stay in the same memory location. And any particular cell is always indexed with the same indices.

That's what sets it apart from a regular grid-centred-on-player, since on that kind of grid, objects are indexed by position relative to player, which means moving the player leads to lots of memory copying.

move(dr, dc) -- moves the grid dr rows down and dc columns right operator () (r, c) -- get data at certain index OR operator () (x, y) -- get data at certain location (index is just position >> by lg(grid size))

I don't think it'll have to support resizing, but I may be wrong and it shouldn't kill perf to support resizing anyway.

What else? I could get started on it.

Come to think of it, it occurs to me that we could use a VDB with a sliding mask -- it should support what we need, and then we wouldn't have to optimize it ourselves. It just means we add a new dependency.

[ghost]

What you describe above sounds like a very good solution for fluid dynamics, and for keeping track of compound gradients on a large scale. While I agree that keeping each grid cell in the same memory location is probably ideal, it'll need a little though on exactly how we allocate storage, as simply instantiating new cells as they're needed, or using a memory pool, will lead to pretty severe memory fragmentation over time. A simple solution will work for now, but its worth discussing this in more detail for a later upgrade (which means we need to nail down the public interface soon) - this might be a good topic for our new technical discussion forum.

Another scenario is the compound cloud deposited by a dying microbe (or one of many other sources) - this can be represented either as a layer (one per compound?) in a pseudo-infinite grid as above, but that leads to wasted memory (for all the grid cells where the concentration is negligible), and possibly wasted CPU cycles updating those cells (or detecting that they don't need updating). I would suggest we therefore at least design a 'free floating' grid, which is spawned as and when needed, expands only to accommodate non-negligible concentrations, and is removed as soon as all its cell's concentrations become negligible.

Also - whats a VBD, and are we planning on using any array libraries (boost/armadillo), or just the STL?

[Moopli]

I was thinking of using a shallow tree (probably just root and leaves) for the rolling grid, where a leaf (about 64x64?) only exists when it contains non-negligible values. The root can then default to 0 for any missing leaves. The leaves in this case would represent your free-floating grids, but at a standard size. We could then keep the leaves in a memory pool, and activate new leaves behind the scenes whenever a non-negligible value is written to an inactive area of the rolling grid. This implementation, however, starts to look more and more like a poor man's VDB. The VDB is pretty much an optimized, more fully-featured version of that -- a datastructure designed for storing sparse, functionally infinite volume data (which works, even more efficiently, in 2D too). The paper explains it better than I could.

So I'm thinking, if we go with the VDB, we could just make the rolling grid wrap a VDB and automatically inactivate anything that leaves the bounds.

Oh, and a note: I've already suggested somewhere on the forums that we could use VDBs for things like asteroids and spaceships in space stage and caves and cliffs and other complicated terrain features in everything from aware forward. So if you guys approve, it'll be worthwhile to get OpenVDB working.

[ghost]

Ok, that seems to incorporate most of what I was going to suggest, and more, so I'd be in favor of using OpenVDB, though I haven't read all the details. I'm not sure it'd be an ideal solution for the free-floating grids, unless the leaves can be spaced irregularly?

[Moopli]

I don't think leaves can be spaced irregularly, and indeed, I don't think it's too great an idea; as the increased memory and processing time footprint you'd need to spend on irregularly placed leaves in most cases would negate their benefit. Irregular leaf placement breaks the simplicity of the space partitioning, which in the case of the VDB, breaks many of its optimizations.

[ghost]

That's what I suspected, what I was hoping to avoid was having a compound source on the edge/corner of a leaf, causing 2-4 leaves to become active.

[Moopli]

Yeah, so leaves should be medium-small, so we could reasonably expect any interesting phenomenon to cover several leaves; meaning compound sources on edges and corners don't particularly matter.

[jjonj]

I added Moopli to developers and assigned to this issue for now!

[Moopli]

I've been too busy studying and working and being sick to do anything with this for a while — obviously this won't be part of the new release coming up, but I'm thinking, to get it in a usable state at all (which can be improved after, obviously), we'll have to cut corners and make it a simple 1-layer grid with wraparound.

[jjonj]

Sounds reasonable

[Moopli]

Something to keep in mind for later optimization: http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx

[Moopli]

The simple one-layer rolling grid now works! It just needs some code review and then we should be good to go with compound clouds and stuff.

Optimization idea for far future: If we stick with 1-layer arrays with wraparound logic, we won't have to redesign the datastructure at all if we port it to texture memory. Offloading the grid onto the GPU makes sense if we ever want to do lots of heavy but parallel calculations; like, say, diffusion.

[jjonj]

Sounds great! I'll put this reviewing this top of my thrive todo!

[jjonj]

Fixed with #193