[Solved] - Detecting asymmetrical multiblock pattern

[xilef11]

Hello

 

I am looking for an efficient way to detect asymmetrical multi-block structures in the world, while keeping them orientation-independent.

 

For instance, take the following structure defined as a 2d array of blocks (where X is a specific block):

x

x

x

x

x

I want the structure to be detected with the "top" X in any of the 4 directions.

 

One could think of a "brute-force" algorithm as follows:

(note that this is inside the block class X, but it could be in an Item)

onBlockActivated(BlockPos pos){
  Block[][] pattern = findPatternAroundBlock(pos);
  for(Block[][] multi : allPatternsInMyMod){
    if(patternsMatch(pattern,multi){
      foundPattern=multi;
      break;
    }else{
      //rotate pattern 90 degrees and check again. do this for all directions
    }
  }
  activateStructure(foundPattern,pos,pattern);
}

This implementation has a few problems:

• it is necessary to iterate through all defined patterns (this could probably be reduced to a  subset based on the number of blocks)
  
• we have to check if the pattern is matched 4 times before we know we don't have the right one
  
• rotating a large array 90 degrees could be slow/complicated
  

Is there a more efficient algorithm (or way to store the patterns) for this task?

 

Also, is there a way other than a double for loop for patternsMatch()? (I doubt it)

I am also unsure of a good implementation for findPatternAroundBlock(BlockPos).

 

Thanks

[xilef11]

Is there no better way of doing this?

[jabelar]

There are a lot of further clarifications you need to give about what you are trying to achieve:

- What do you consider symmetrical? I would consider the diagram you drew in your post as being symmetrical (since it is mirrored across). Do you mean symmetrical in both x and y together? So a circle would be symmetrical but a triangle would not? (Just pointing out that the mathematical definition of symmetry means that there only has to be one axis of symmetry to declare something symmetrical...)

- Are you also looking for specific patterns? Or just looking for symmetry in any arbitrary pattern?

- Is the pattern expected to be in a specific location or do you have to detect the symmetrical structure anywhere in the world?

- Is there a size limit to the structure (performance will be greatly impacted if you're trying to check for arbitrary structures more than a few blocks per side)? What if structures overlap or are next to each other, how do you define where one begins and next one ends?

- Do you consider a single block symmetrical?

 

I think the first performance tip you should consider is you should only check for the pattern / symmetry when a block is placed, rather than always searching for it. So I would do this in detection code in an event handler for block placement.

 

I think the big challenge is not the actual symmetry part (I'll explain how to do that more efficiently) but figuring out where the structure is. For example, if your maximum size of the structure was 5 x 5, let me show you the problem if you had only a couple blocks in the structure. Here is some block placement:

 

----------

----------

-X--X-----

----------

-X--X-----

----------

----------

----------

-------X--

----------

 

Is the pattern above a symmetrical 4 x 4 pattern with some other block that isn't counted, or is it an asymmetrical pattern? Do you understand my point? It is hard to define exactly what area you should be looking for symmetry on, because you can find symmetry in the smaller area.

 

Anyway, once you have figured out the area to check, I think there are more efficient ways to determine symmetry. The first thing you need to figure out is the axis of symmetry: I would do it by checking "across" the area for symmetries. Like if you found a block at position 3 , 1 in a 5 x 5 area, then you should check if there is a block at position 3 , 4 and if not then there cannot be symmetry around the x-axis, and you would also check if there is a block 2, 1 and if not then there cannot be symmetry around the y-axis. If you find there is no symmetry around either axis, then you're done -- just checking for symmetry on that one block proved there is no symmetry. If you find there is symmetry around one or both axes, you continue but now adhere to the axis of symmetry: find another block (if there is one) and check across the known axes of symmetry. If there is not matching block across, then you know there is no symmetry for that axis.

 

I believe this would be very efficient. In most cases just checking two block positions would prove there is no symmetry and you're done. The worst case is you have to check all the blocks across the axis of symmetry, but that still isn't that much and wouldn't happen too often.

 

Did you understand what I'm suggesting?

 

Now if you wanted to get fancy and also consider symmetry around diagonal axes, you would just extend the concept.

 

Hope that helps. I greatly suggest that you only look for symmetry in pre-defined areas that are relatively small. Otherwise, you will have to do all the above multiple times around any block because you won't know where the possible axes are. Think of this: if you don't know the size of the area, how can you know where to check for symmetry? You can't because symmetry has to be across the half-way, and you don't know where half-way is without knowing the size and boundaries of the area you're checking.

[xilef11]

I think you misunderstood the question... I'm not trying to detect if an arbitrary structure is symmetrical. I need to detect when a specific pattern of blocks (out of many predefined ones) is created (think railcraft tank).

 

The problem is mostly around the fact that this pattern will not be symmetrical, i.e. the top left corner is not the same block as the top right corner, but I need to detect it if the "top" edge is in any orientation (NESW).

 

As I described in my earlier post, my current algorithm would be the following:

 

For each possible pattern, check if it matches with what's in the world. If it dosen't match, rotate it 90° and check again. When all 4 possible rotations have been checked, try the next pattern.

 

Of course, if there are many defined patterns, this could take a while even if it's fail-fast. Also, the code for "rotate 90°" and check again could be a hassle.

 

Since many mods already have multiblock structures/"machines", I was wondering if there was a known "good" implementation for this.

[Ernio]

There is no well-defined algorithm to do such thing.

 

Although note that this issue could be adressed with D&C approach ( https://en.wikipedia.org/wiki/Divide_and_conquer_algorithms ), to gain maximum performance.

 

jablelar answer was good, just saying. For example, structure like this:

OXO

XOXX

OXO

Could be defined as:

OXO

XOX  +  X in some direction from center+1

OXO

[jabelar]

I think you misunderstood the question... I'm not trying to detect if an arbitrary structure is symmetrical. I need to detect when a specific pattern of blocks (out of many predefined ones) is created (think railcraft tank).

 

The problem is mostly around the fact that this pattern will not be symmetrical, i.e. the top left corner is not the same block as the top right corner, but I need to detect it if the "top" edge is in any orientation (NESW).

 

As I described in my earlier post, my current algorithm would be the following:

 

For each possible pattern, check if it matches with what's in the world. If it dosen't match, rotate it 90° and check again. When all 4 possible rotations have been checked, try the next pattern.

 

Of course, if there are many defined patterns, this could take a while even if it's fail-fast. Also, the code for "rotate 90°" and check again could be a hassle.

 

Since many mods already have multiblock structures/"machines", I was wondering if there was a known "good" implementation for this.

 

You still have the issue of defining the "search area". Like if you find one block of the type for the pattern, how would you know if that block was from the corner, and edge, or somewhere in the middle of the pattern? So your problem isn't just rotation, but also matter of shifting in each direction.

 

Anyway, assuming you don't have pre-defined area where the structure might be built, then logically there is no more efficient way than checking for every pattern in every shift and rotation. If you think about the logic, the only way to prove that any of the patterns exists is to check for them all.

 

Again though, in terms of performance, you can keep things a bit more reasonable by only checking for patterns when a block is added to the world, rather than every tick. And furthermore, you can spread the checking out over several ticks after that event.

 

Lastly, the logic should be that you assume the pattern is there and then escape the check as soon as you determine the pattern isn't there. For most patterns you'll only have to check two positions per shift-rotation combination because most of the time there won't be a pattern.

 

But my main point is that you can't get away from the logic that you have to check for presence of every pattern shift and rotation.

[xilef11]

you can keep things a bit more reasonable by only checking for patterns when a block is added to the world, rather than every tick.

I planned to check that on right-click with an Item, so that shouldn't be a concern

 

You still have the issue of defining the "search area". Like if you find one block of the type for the pattern, how would you know if that block was from the corner, and edge, or somewhere in the middle of the pattern? So your problem isn't just rotation, but also matter of shifting in each direction.

Since all the blocks in the patterns will be specific blocks from my mod, I was thinking I could define the patterns in a way that all blocks in it need to be "connected", and using some sort of search algorithm (breadth-first seems logical?) around the clicked block. Not sure how well taht would work though.

 

Anyway, assuming you don't have pre-defined area where the structure might be built, then logically there is no more efficient way than checking for every pattern in every shift and rotation. If you think about the logic, the only way to prove that any of the patterns exists is to check for them all.

 

I guess I'll have to do it that way then  hoped there was a better way

 

Do you think storing the patterns as a 2d array would work or is there a nicer way?

 

Also, my "blocks" are technically ItemStacks in a TileEntity, but I think the logic should be the same (contents of the TE can be returned as a 2D array of ItemStacks), I just have to "flatten" the array in some way, i.e go from a 2D array of 2D arrays of ItemStacks to a 2D array of ItemStacks.

[jabelar]

You still have the issue of defining the "search area". Like if you find one block of the type for the pattern, how would you know if that block was from the corner, and edge, or somewhere in the middle of the pattern? So your problem isn't just rotation, but also matter of shifting in each direction.

Since all the blocks in the patterns will be specific blocks from my mod, I was thinking I could define the patterns in a way that all blocks in it need to be "connected", and using some sort of search algorithm (breadth-first seems logical?) around the clicked block. Not sure how well taht would work though.

 

Yes, if there is some additional "rules" about the patterns besides simple matching, then yes there may be opportunities for more efficient searching. Like if the pattern has to be connected, then you start by just finding the connected parts and that would help define the area of the full pattern. That would be a big efficiency because you wouldn't have to check every shift of the pattern.

 

Note however you still have the possible issue of two connected patterns right next to each other that look connected. That would be extremely hard to figure out logically which part is the pattern area.

 

A 2D array is certainly a good way to represent the pattern, and the pattern to be matched. If you create a couple functions to rotate the array and check symmetry or check pattern, then you could have some very clean code. For this sort of problem, the simpler and more understandable your code is the more likely you are to not introduce bugs. Doing this in a convoluted way could be extremely buggy...

 

So I would define 2d array fields for all the patterns you want to detect. I would make a method for rotating by 90 degrees (you could use that multiple times to rotate more. I would create a method to detect the pattern area (which would be much easier if all patterns were connected, as discussed above) and then create a method for detecting the pattern that simply loops through the patterns you want to detect with all rotations (and for good performance escapes from the loop as soon as it finds a pattern).

[xilef11]

Got it!

 

I just find the largest connected pattern around the block clicked, convert it to an array and compare that to the stored patterns.

 

The finding and comparing code is indeed surprisingly clean, although I might have to switch my recursive function to a loop if patterns get too large, and it would have been easier if ItemStack had a useful equals() implementation (because Arrays.deepequals could have worked).

 

The conversion to a flat array is much less nice looking (4 nested for loops ), but I guess I'll live with it.

 

Here is my code if anyone finds this useful in the future

 

Pattern finding

pattern matching