# Determining if player-created structure matches a template in a 3D block-based game

Disclaimer: this is one of those dreaded Minecraft-style questions, but I feel it's more a data structures and algorithms question

I'm really new to 3D data structures and am wondering what the best way to store and match a 3D block structure.

Right now, the player is able to place blocks in any arbitrary space and when these blocks match a pre-defined structure an event happens. The way I'm doing it currently is when a player places a block the game recursively checks each adjacent block to find the block with the lowest x, y, z coordinate and makes that block the root block. Then it checks the rest of the blocks, based off of the root block, to make sure they match a certain template. The problem is that as the template gets more complicated, so does my (terribly inefficient) code.

I'm thinking the best way to do this is to store some type of matrix that defines the structure and then match against the matrix whenever a player places a block. Are there already data structures/algorithms that would match this type of problem?

-
As an example, are thinking of how to template structures like a Minecraft portal? –  dcousens Sep 28 '11 at 0:21
@Daniel Actually, I guess that would be a good example. Although, my goal would be to have an arbitrarily large/complex structure. The portals are rather simple. –  WillP Sep 28 '11 at 0:26
Not an answer, but just a thought - if the structures become arbitrarily large, and the list of target structures (that you have to search to find a match) becomes incredibly large, this becomes a pattern recognition problem, like recognising text or speech. Then you move away from brute force comparison towards statistical methods like Hidden Markov Models trained on your target structures. That would be so cool. –  Pieter Müller Sep 28 '11 at 7:36
@Harikawashi Oh man, that would be very cool. Even though my goal is not something astronomically large, I may do it anyway just so I can play around with that. Thanks! –  WillP Oct 3 '11 at 20:02

To be honest, I'd take the simple solution.

Make a matrix that defines the structure. Whenever a block is changed, attempt to apply that matrix to all locations that might have created the new structure. That's going to be width*depth*height locations, since the player could have finished any point on the structure, but it shouldn't be too bad because most of these locations are going to early-exit when the first check fails.

Basically, you've got a 3d matrix, and you're comparing it against another 3d matrix, at a bunch of offsets.

From here there's a bunch of totally optional optimizations you could do. For example, if your structure is extremely sparse - i.e. the player is building a tall tower with a sphere at the top, but you don't care if the bottom of the tower is surrounded by trees - you could turn it into a list of blocks instead of a matrix. (I'd generate the list from the matrix - the matrix will be far easier to maintain directly.)

If you wanted to be super-clever, break the structure apart into blocktypes. If you know that the player just changed block 1,2,3, and you know that placing your structure at coordinates 0,0,0 would require block 1,2,3 to be obsidian, and block 1,2,3 is wood, then you don't even need to try block 1,2,3. Generate all possible offsets for the structure given that the player has just placed a specific type of block. Then, when the player places that block, just check the pregenerated possible offsets.

But, seriously, this is all optimization. Just make a matrix, then compare your matrix with the world brute-force style. Assuming you're making something Minecrafty, people really don't place all that many blocks - a few blocks every second at most. Unless you have hundreds of huge structures you'll be able to test that easily.

-
You're right. Brute forcing really shouldn't be a major performance problem. I feel like I've fallen into the trap of premature optimization. Thanks for your insight. –  WillP Sep 28 '11 at 2:08

Well you come up with an interesting problem. I would suggest something like the following: use your blocks as pixels and do a per/pixel collision detection, where all blocks must match to return a true collision.

This would work fine, however make sure you only do this when objects/blocks change. So I'd recommend a simple event system to pass a change to a object checker, that can certainly use your algorithm. Which would then do whatever you want that object to do. Also I'd recommend checking height and width, before running the algorithm, because if it isn't high enough/is too high obviously it won't match.

As far as a data structure, a simple vector would do, or perhaps a custom data structure.

Interesting question.

-