I'm in the process of coding something that will let me build on a grid, and I've run into problem. Let me show a quickly sketched picture that will help describe what I mean:
At first I thought I'm gonna build with uniform sized blocks - these blocks would be the green block on my picture. Then I decided that I need blocks that will be half as thick and appear in two width variants: 1x1 and 1x2. Mind that each size mean a block that can't be divided - a separate 3D model that will connect to other (allowed) block seamlessly.
Problem is with storing information about these blocks. If I create a grid consisting of smallest elements, biggest block on the example which is 2x2 will occupy 4 cells. How should I handle storing this information so I can query the grid for the smallest cell and still get information about the big one if part of it occupies the queried cell. Following the picture:
grid = GREEN_BLOCK_1*; grid = GREEN_BLOCK_1*; grid = GREEN_BLOCK_1*; grid = GREEN_BLOCK_1*;
* GREEN_BLOCK is just representation of some data structure describing that particular block, depending on building block it may store different information
How should I keep information that this GREEN_BLOCK is actually one and the same object? Should I keep some register on top of grid, and grid should keep index into this register? Like:
grid = 0; grid = 0; grid = 0; grid = 0; grid = 1; register = GREEN_BLOCK_1*; register = RED_BLOCK_1*;
This problem is probably quite common because there were many games that had non-uniform building blocks on some isometric maps, I just can't figure how to store that information in a way that will allow querying by smallest neighbouring blocks, but also supporting blocks that span over more than 1 cell.
I was even considering quadtrees (octrees actually, because whole thing is 3D but I describe 2D to simplify the case) that I don't really like because they don't allow as fast neighbour querying as simple grid and are generally cumbersome. But then, the problem will be blocks that are not 1x1, 2x2, 3x3 like the one thats 2x1 - quadtree can't subdivide in such way, so the 2x1 block would have to consist of 2 smaller blocks and we're back to problem we have on grid, but this time we're also using quadtrees:
If anyone can point me in the right direction here, I'd be very grateful. There is probably some nice and clean solution, I just can't figure it out. Thanks!
Edited by noizex, 25 October 2012 - 04:35 PM.