• Create Account

We're offering banner ads on our site from just \$5!

Storing non-uniform size building blocks on the grid

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

#1noizex  Members   -  Reputation: 879

Like
0Likes
Like

Posted 25 October 2012 - 02:45 PM

Hi,
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[0][0] = GREEN_BLOCK_1*;
grid[0][1] = GREEN_BLOCK_1*;
grid[1][0] = GREEN_BLOCK_1*;
grid[1][1] = 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][0] = 0;
grid[0][1] = 0;
grid[1][0] = 0;
grid[1][1] = 0;

grid[2][0] = 1;

register[0] = GREEN_BLOCK_1*;
register[1] = 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.

#2frob  Moderators   -  Reputation: 22293

Like
0Likes
Like

Posted 25 October 2012 - 02:50 PM

Looks like the perfect application for a loose quadtree.

The fast neighbor query is not as bad in practice as you make it sound ... unless you are developing on a phone or other device that you didn't specify.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.

#3noizex  Members   -  Reputation: 879

Like
0Likes
Like

Posted 25 October 2012 - 03:03 PM

Looks like the perfect application for a loose quadtree.

The fast neighbor query is not as bad in practice as you make it sound ... unless you are developing on a phone or other device that you didn't specify.

I will look into them, I remember reading about them for spatial partitioning. Not sure if they're not too "loose" though - I still need the objects to be constrained to some fixed sizes / coords, not be placed freely. Not sure how it would work with loose quadtree which can adjust to basically anything - won't this be too much freedom? Also remember I need precise neighbour information, like querying something at position [x-1, y] or [x+2, y-1] from current block and having enough information to decide if I can place a block there or it will collide with anything.

And no, its not phone or mobile, its normal game for PC.

Edited by noizex, 25 October 2012 - 03:05 PM.

#4frob  Moderators   -  Reputation: 22293

Like
0Likes
Like

Posted 25 October 2012 - 03:25 PM

None of those constraints look like a problem. We've used loose quadtrees on many games, and had those constraints and more.

There can potentially be a slight performance issue when certain objects are added to the spatial tree when it requires serious subdivision, but those situations are fairly rare in the typical case once the world becomes populated.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS