Finding shapes in 2D Array, then optimising

Posted by assemblism on Game Development See other posts from Game Development or by assemblism
Published on 2012-10-08T15:49:03Z Indexed on 2012/10/08 15:54 UTC
Read the original article Hit count: 267

Filed under:
|
|
|

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

© Game Development or respective owner

Related posts about algorithm

Related posts about grid