[1.8.9] Search around block for pattern

[LogicTechCorp]

I am in the process of implementing multi-block structures into my mod. While looking for tutorials on multi-block structures I stumbled upon the Shad Multicore System by Jezzadabomb338. It is 1.7 only at the moment and I decided to port it to 1.8.9. In the 1.7 version the "master" block searches for the pattern from -Z and -X to +Z and +X and would require multiple patterns for each (NESW) direction if the pattern was not symmetrical. I want to make it so that the "master" block can search for the pattern within a set diameter no matter the orientation of the pattern. Which is the best way you recommend of doing so?

 

 

https://gist.github.com/LogicTechCorp/612cbbace222a3b41223

[jabelar]

A similar question was asked recently on the forum, although the guy was only wanting to detect symmetry rather than specific patterns. The short answer is that the number of possibilities for pattern positions expands exponentially as the search area grows, especially if asymmetric patterns need to be considered. Think about it -- if you had a 5 x 5 asymmetrical pattern that you wanted to search in a 10 x 10 area, then there would be 25 possible translations times 4 rotations = 100 possibilities. If you increase the search area to 15 x 15 then there are 100 possible translations times 4 rotations = 400 possibilities. If you increase the search area further to 20 x 20 then there are 225 tranlations times 4 roations = 900 possibilities.

 

Now that isn't too bad, since a computer is still extremely fast but there are 25 blocks in a 5 x 5 pattern so you'd have to check up to (average would be half of this) 22, 500 blocks!

 

Then, it depends on how many patterns you want to look for and multiply that up.

 

Anyway, you get my point -- don't get too ambitious about making the search area big.

 

Okay, back to your main question about best approach. Well, in the end you simply have to check all the possibilities. However, you can stop searching as soon as you find the pattern, so sometimes it will happen at the beginning of the search, sometimes at the end. In terms of checking the possibilities it is all just using arrays -- you can store the pattern in an array (could be an array of blocks, or block names, or some coded int value) and then have the code create the rotated arrays. Then you use a loop to go through an array of locations, just like you mentioned from -x, -z to +x, +z looking for each of the rotations. And escape from the loop as soon as you find the pattern to avoid wasting processing power.

 

Note that it is possible to simply use math to figure out the rotations on the fly, but I think it would be much easier to get right if you simply create the rotations and check for each.

[Zethariel]

First off, you don't want to do pattern recognition that has variants (such as rotation) on too big structures. As mentioned above, it would probably kill the server/client/whoever was doing the lifting.

 

Secondly, you could always shove pattern recognition into a separate thread that you launch and have an event thrown back in the main thread to keep the world running smoothly

 

Thirdly, when recognising patterns, break the search loop as soon as you encounter a discrepancy. To check rotations, use math to figure out the coordinate changes instead of creating 4 separate schematics (look into vector rotations, there are consice equations that you can run on each loop iteration, so that you don't have to start a for loop 4 times and just do it once)

 

If you're putting those structures as objects into a map, I'd store the Master block position and facing into a field. That'd lessen the load by a lot.