Finding shapes in 2D Array, then optimising
- by assemblism
I'm new so I can't do an image, but below is a diagram for a game I am working on, moving bricks into patterns, and I currently have my code checking for rotated instances of a "T" shape of any colour. The X and O blocks would be the same colour, and my last batch of code would find the "T" shape where the X's are, but what I wanted was more like the second diagram, with two "T"s
Current result Desired Result
[X][O][O] [1][1][1]
[X][X][_] [2][1][_]
[X][O][_] [2][2][_]
[O][_][_] [2][_][_]
My code loops through x/y, marks blocks as used, rotates the shape, repeats, changes colour, repeats.
I have started trying to fix this checking with great trepidation. The current idea is to:
loop through the grid and make note of all pattern occurrences (NOT marking blocks as used), and putting these to an array
loop through the grid again, this time noting which blocks are occupied by which patterns, and therefore which are occupied by multiple patterns.
looping through the grid again, this time noting which patterns
obstruct which patterns
That much feels right... What do I do now?
I think I would have to
try various combinations of conflicting shapes, starting with those
that obstruct the most other patterns first.How do I approach this one?
use the rational that says I have 3 conflicting shapes occupying 8 blocks, and the shapes are 4 blocks each, therefore I can only have a maximum of two shapes.
(I also intend to incorporate other shapes, and there will probably be score weighting which will need to be considered when going through the conflicting shapes, but that can be another day)
I don't think it's a bin packing problem, but I'm not sure what to look for. Hope that makes sense, thanks for your help