[1.12.2] MultiBlock Structure Pattern Recognition Best Practices

[TH3Doctor_11th]

Hi all. I have some TEs ready, with blocks and everything set, and I would like to figure out how to efficiently recognize a multiblock structure with those TEs. As regards mechanics, Master-Slave is just right. But are there any best practices about finding out if a multiblock structure is valid or not? I am currently trying with the for loops for each axis, since I don't think recursion would be much better (It's not a Fluid Tank, so the TEs composing the structure could be different. I could implement recursion, but at the moment I am focusing on solving the structure recognition first). The problem is, the structure controller is not at the perfect center of the Multiblock, and as a result I have to check where the TE block is facing. I don't think this is an efficient solution, and I was hoping someone could lead me in the right direction to figure out a good way to solve this. Thanks in advance!

[Cadiboo]

If you efficiently get all the positions to check and then fail fast if one of the positions is wrong (and also don’t run the code more than is necessary), there shouldn’t be any problems at all

[jabelar]

The key is to use loops with escapes (break and continue keywords in Java)-- your loops should give up as soon as they "know" there isn't a match. Secondly it is good to find the lack of match as early in the loop as possible, so if you can find unique parts (least likely to spawn naturally and/or uncommon to build) of the structure to check first that is helpful. 

[TH3Doctor_11th]

Thanks for the answers @Cadiboo @jabelar  So, since I wanted to use an energy containment / transfer block (I am working on a Technical Mod) in conjuction with the controller, I could start by checking if and where it is located relative to the controller itself. So, I have to do 4 conditional checks for the x and z axis, both negative and positive, and if I am planning on adding a transfer and a battery with different costs in crafting terms, i need to check separately for both. Is it correct? (I am using Structure classes, Singletons, to hold off 3D Matrixes that contain the correct order of blocks). Just another thing, would it be better to have the structure made of TEs so wherever I click I can open the future GUI of the controller following the Master-Slave principle, or should I make players click just on the controller (which will have a different texture of course) keeping the other blocks of the structure without TEs? (except the transferer / battery, which will have their own GUIs). Thanks again for both your answers!

[TH3Doctor_11th]

After some trials, I found out a possible solution that I would like to share and get some feedback from both  As you said, I have to recognize the unique pieces of the multiblock first. If any of them is missing, I just say "nope, no correct structure". Then, through BlockPos.getAllInBox() or something like that, I get the positions in the N x N x N, and I iterate through them (ignoring the positions of the special ones, that I asserted to be there at this stage) and check if the blocks at the corresponding locations are, for example, casings. Again, if anything is not at its place, then it's not a valid structure. Else, everything is in its place, and the structure is ready  let me know

[Cadiboo]

  On 10/1/2018 at 9:57 PM, TH3Doctor_11th said:

After some trials, I found out a possible solution that I would like to share and get some feedback from both  As you said, I have to recognize the unique pieces of the multiblock first. If any of them is missing, I just say "nope, no correct structure". Then, through BlockPos.getAllInBox() or something like that, I get the positions in the N x N x N, and I iterate through them (ignoring the positions of the special ones, that I asserted to be there at this stage) and check if the blocks at the corresponding locations are, for example, casings. Again, if anything is not at its place, then it's not a valid structure. Else, everything is in its place, and the structure is ready  let me know

Expand  

That sounds perfect. Then you just have to store a reference (BlockPos?) to the Master somewhere & when the blocks are right clicked return master.rightClicked.

You will also want to return the capabilities of the master when your outside blocks are queried too.

[jabelar]

Yep, that is how its done.

 

One other point, depending on the symmetry of your structure you might want to take different approaches regarding whether the rotations are handled "algorithmically" or "brute force". If you have a structure that is symmetric in both X and Z then obviously you have to only scan once since the shape is same in any rotation. If you have a structure otherwise you need to decide the best way to handle the rotation. The brute force way is to pre-compute the structure in each rotation (really four different structures) and check each with same logic as you outlined above. I generally recommend that way. But if the symmetry is simple you could choose to handle the rotation within the loop -- like when you detect the unique elements they would indicate the rotation and then you apply it.

 

I've seen a lot of people work hard at getting rotation to work, and in the end I recommend just considering each rotation a separate structure and then have very simple checking.

 

Not sure which situation applies to your structure.

[TH3Doctor_11th]

  On 10/2/2018 at 2:10 AM, Cadiboo said:

That sounds perfect. Then you just have to store a reference (BlockPos?) to the Master somewhere & when the blocks are right clicked return master.rightClicked.

You will also want to return the capabilities of the master when your outside blocks are queried too.

Expand  

Ok! ?

  On 10/2/2018 at 3:20 AM, jabelar said:

Yep, that is how its done.

 

One other point, depending on the symmetry of your structure you might want to take different approaches regarding whether the rotations are handled "algorithmically" or "brute force". If you have a structure that is symmetric in both X and Z then obviously you have to only scan once since the shape is same in any rotation. If you have a structure otherwise you need to decide the best way to handle the rotation. The brute force way is to pre-compute the structure in each rotation (really four different structures) and check each with same logic as you outlined above. I generally recommend that way. But if the symmetry is simple you could choose to handle the rotation within the loop -- like when you detect the unique elements they would indicate the rotation and then you apply it.

 

I've seen a lot of people work hard at getting rotation to work, and in the end I recommend just considering each rotation a separate structure and then have very simple checking.

 

Not sure which situation applies to your structure.

Expand  

So if I store the correct blocks in a matrix (static and final) for every configuration, would it be ok? Or is it too much? This structure in particular is a 3x3x3 ?

[Cadiboo]

  On 10/2/2018 at 7:37 AM, TH3Doctor_11th said:

Ok! ?

So if I store the correct blocks in a matrix (static and final) for every configuration, would it be ok? Or is it too much? This structure in particular is a 3x3x3 ?

Expand  

I suggest querying your master block for a list of BlockPoss to check for your structure and have your master return an itterable of MutableBlockPos. That’s a horrible explanation, here’s some example code of the concept

for(MutableBlockPos pos : getMaster().getAllPositionsInStructure()){

if(!isPositionCorrect(pos)) return FAIL;

}

return SUCCESS;

 

I’ve got a 3x2x3 multiblock structure in my mod that I use this method for, so I’m a bit biased.

Edited October 2, 2018 by Cadiboo

[jabelar]

  On 10/2/2018 at 7:37 AM, TH3Doctor_11th said:

Ok! ?

So if I store the correct blocks in a matrix (static and final) for every configuration, would it be ok? Or is it too much? This structure in particular is a 3x3x3 ?

Expand  

Yeah, I would do it that way. Have a matrix (or whatever format you have for your template) for each possible orientation and just check them all (efficiently like we discussed above). Otherwise you'll do a lot of coding (and probably bang your head over bugs) trying to perform the math to rotate inside the loops.

[Draco18s]

  On 10/2/2018 at 3:29 PM, jabelar said:

Otherwise you'll do a lot of coding (and probably bang your head over bugs) trying to perform the math to rotate inside the loops.

Expand  

Not really. If you do all your offsets based on a Facing (and Facing has a getOffset method) you don't even need to think about it.

 

"This block is 1 forward" -> pos.offsetX(Facing.getX()).offsetZ(Facing.getZ())

"This block should be one to the right" -> pos.offsetZ(Facing.getX()).offsetX(Facing.getZ())

 

Then you just loop over the horizontal facing values.

Edited October 2, 2018 by Draco18s

[jabelar]

  On 10/2/2018 at 5:30 PM, Draco18s said:

Not really. If you do all your offsets based on a Facing (and Facing has a getOffset method) you don't even need to think about it.

 

"This block is 1 forward" -> pos.offsetX(Facing.getX()).offsetZ(Facing.getZ())

"This block should be one to the right" -> pos.offsetZ(Facing.getX()).offsetX(Facing.getZ())

 

Then you just loop over the horizontal facing values.

Expand  

 

The logic for rotation isn't that simple, as the movement needed for each block is dependent on the size of the overall structure and distance of each block from the center. You also have to do different math for structures that have odd number of blocks on each side (in which case there is a center block) versus even number of blocks on each side. And if your structure isn't same size on each side you have to add logic to "pad" out the short side during the rotation.

 

But even if you consider the rotation logic simple (and for you Draco18s I'm certain it is relatively simple), that is already too much thinking. Furthermore it is also a performance hit. Having the structure pre-rotated with simple looping is less lines of code and can be super efficient.

 

The other problem with clever algorithms is that they are much more prone to bugs and harder to debug. It would be pretty hard to screw up looping through a pre-set matrix.

 

 

Edited October 2, 2018 by jabelar

[Draco18s]

  On 10/2/2018 at 7:36 PM, jabelar said:

The logic for rotation isn't that simple, as the movement needed for each block is dependent on the size of the overall structure and distance of each block from the center.

Expand  

No its not. Two blocks to the right? pos.offsetZ(Facing.getX() * 2).offsetX(Facing.getZ() * 2)

Three blocks left and one up? pos.offsetZ(Facing.getX() * -3).offsetX(Facing.getZ() * -3).offset(Facing.UP)

 

There's always a point from which you can perform all of these calculations and there is no rotation that this doesn't support (unless you want your machines to be constructed on their *sides* too, but even THAT functions if you do it right). It doesn't support mirroring very well, but you CAN do it. The whole even/odd things it moot too. If its an even number of blocks your "center" is just offset to the side a bit, one side extends 1 block away from "center" and the other side extends 2.

 

I dare you to construct something that when rotated does not appear identical to a reference frame rotated the by same amount.

[jabelar]

  On 10/2/2018 at 8:23 PM, Draco18s said:

No its not. Two blocks to the right? pos.offsetZ(Facing.getX() * 2).offsetX(Facing.getZ() * 2)

Three blocks left and one up? pos.offsetZ(Facing.getX() * -3).offsetX(Facing.getZ() * -3).offset(Facing.UP)

 

There's always a point from which you can perform all of these calculations and there is no rotation that this doesn't support (unless you want your machines to be constructed on their *sides* too, but even THAT functions if you do it right). It doesn't support mirroring very well, but you CAN do it. The whole even/odd things it moot too. If its an even number of blocks your "center" is just offset to the side a bit, one side extends 1 block away from "center" and the other side extends 2.

 

I dare you to construct something that when rotated does not appear identical to a reference frame rotated the by same amount.

Expand  

 

The concept is obviously simple, but the implementation really isn't so much. I entirely know how to code it, but why bother?

 

You're glossing over the fact that every block needs to move a different amount. If you have a 4 x 4 structure, each corner has to move 3 blocks in a straight line, but one edge block on each side needs to move 3 blocks plus 1 block over, and one edge block on each side needs to move 3 block plus 2 blocks over. Then the blocks on the inside each just move 1 block. So every block has to move differently. It is conceptually simple, but it is a pain. And because these are blocks which are discrete, the movements are different for odd versus even.

 

And anyway, calculating new positions at all is more processing than needs to be done with a pre-rotated structure -- which needs none. So performance-wise an algorithmic rotation is always going to suffer a relative performance hit.

 

I agree it is totally possible to do it your way, but fail to see any advantage in doing it algorithmically, especially if you want to generalize it for arbitrary size. My way is literally 10 lines of code or less, less likely to have a bug, and performs faster.

Edited October 2, 2018 by jabelar

[Draco18s]

  On 10/2/2018 at 9:25 PM, jabelar said:

You're glossing over the fact that every block needs to move a different amount.

Expand  

I swear, you're either misrepresenting the argument on purpose in order to create strawman or you're actually not understanding it.

 

Lets take this layout:

The left side is just a mirror of the right, so I'm not bothering to draw its offsets.

 

If we want to rotate it, we get this:

 

Notice how two of the positions (besides the center) remain filled, even though they are different parts of the whole layout:

 

This is because of how rotations work: they swap the X and Z values (and sometimes flip their sign).

https://math.stackexchange.com/questions/1330161/how-to-rotate-points-through-90-degree

 

In order to make what we want to happen, we treat things as relative. Instead of +2X we call it +2R.

if Facing.Forward.Z is our Forward offset (moves up under no rotation) and Facing.Forward.X is our Right offset (moves right under no rotation)
 

We'll do this process by focusing only on this blue block:

 

In this orientation it's +1F,+2R. Lets animate that.

 

Now lets rotate it 90 degrees.

 

HOLY SHIT IT WORKS

Edited October 2, 2018 by Draco18s

[jabelar]

I totally understand the mirroring method of Cartesian rotation. And it isn't that hard but the problem with the swapping method is that there are a couple details in calculating the center with potential for causing some confusion. Maybe not confusing for you, or me, but for the average modder probably. 

 

Imagine your matrix is a 5 x 4 matrix:

A B C D E

F G H I J

K L M N O

P Q R S T

 

And you're rotating clockwise by 90 degrees to get:

P K F A

Q L G B

R M H C

S N I D

T O J E 

 

So I believe, correct me if there is simpler way, the steps for your algorithm are:

1. find center block of the base matrix. Easy right -- just divide the dimensions in half so it must be 2.5, 2. But wait if I look at the array the center is really at the 3rd position across and 2.5 down, so isn't the center then actually 3, 2.5? Okay, but wait in computing we start counting at 0 so the center is really at the array index 2, 1.5. 
2. Now we can start swapping. We'll create an empty new array and populate it. The dimensions should be a 4 x 5 array now.
3. For rotation we want to implement it by transforming (x, z) to (-z, x). The first element in the base is at index 0, 0 but we need to convert that to a relative coordinates from the center so let's say the first element is at relative position -2, -1.5. We swap that so it is now 1.5, -2. Also the swap results are now relative to the new array center at index 1.5, 2 so we add them and get index of 3, 0. Yay, it worked!

Now I admit that isn't that hard, but you have to imagine the "average" modder on this forum implementing this without the hints I gave above. Wouldn't you bet that we'd be getting questions where it wasn't working because people screwed up by not figuring out the center properly?

 

By the way, the point of my recommendation was to "pre-rotate" the structures. I'm not at all against using this algorithm for doing it in advance. I just think people will muck it up combining the rotation into the loop that does the actual checking.

 

P.S. Thanks for taking the time to make the animated pictures!

Edited October 3, 2018 by jabelar

[Draco18s]

You missed the fact that my example layout was 6x5 didn't you?