2
\$\begingroup\$

I have a 6x6 grid where every cell have a color property (simply integer value).

Player can change one cell at a time to form rectangles of the same color inside of the grid. New rectangles can only be 2x2, 3x2, 2x3 and 3x3 in size.

Is there a cleaner way to find those rectangles rather than having to manually search for [i][j], [i+1][j], [i][j+1] and [i+1][j+1] (et cetera) color matches?

\$\endgroup\$
  • \$\begingroup\$ Have a look at this as it may help en.m.wikipedia.org/wiki/Flood_fill \$\endgroup\$ – Savlon Apr 29 '14 at 6:37
  • \$\begingroup\$ @Savlon A recursive search radiating out from the clicked point is exactly how I would solve this. Flood fill is a great example of a very similar algorithm. \$\endgroup\$ – Dan May 12 '14 at 17:50
1
\$\begingroup\$

If your shapes never get bigger than 3x3, your described approach should be sufficiently fast. A 3x3 maximum square means that whenever a player changes a tile's color, you only need to search two tiles in all directions (that is, a 5x5 search space). That's a total of 24 checks in the worst case (you don't need to check the center), which is not that taxing. Especially since the overall size of your grid means you will short-circuit out of many of those checks anyway (since they'd be out of bounds).

A potential optimization is to track the state of "partially assembled" squares as they are built. This reduces the number of checks you generally need to make to approximately 8 (the eight surrounding tiles of the clicked tile) to see if the clicked tile should be added to an existing potential solution, and whatever checks you need to see if a potential solution has just become valid (probably two or three more ifs, to check it horizontal and vertical bounds).

However, this approach not only requires more memory but also requires a way for you to tell if a given tile is part of an existing potential solution, which is generally efficiently done with some kind of spatial partitioning technique. It is thus much more complex for what is a questionable performance gain at the scale you are working at.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.