While creating the gameplay for Prim, one of the major hurdles I faced was detecting if a block group had been completed (as a full, filled-in shape) or not. The starting state of a block group in Prim┬áis an incomplete polygon that is rectangular or square in shape. For example, a 3×3 square that the top row is filled in, and one block on each side down the other 2 rows. All starting shapes must follow a couple logical stipulations such as the open spaces of the shape must be able to be filled in from bottom-to-top; in other words, all shapes must be able to be filled in somehow by firing new blocks onto them. The calculation of the block group “completed” flag needed to be done on various occasions:

  1. When a block projectile collided with a group, attached itself, and grouped with this block group
  2. When a block group reached the end of the playfield and a row of blocks fell off the edge
  3. Combo variations and more…

I first explored options that involved complicated flood fill algorithms to check neighboring blocks — which also required more complex data structures. I also thought to convert a 2D array of 0’s and 1’s whether or not there was a block in each array spot. But one thing that I was sure of (that flood fill is generally unaware of) was the shape was always going to have a fixed min/max X, and a possible varying min/max Y (really this is Z). Having a known X, each time the shape grew in the Y, I would have a desired area size, multiplying X times Y. For example, if there was a 3×3 shape, in which the min/max X was 0 to 2, (distance of 3 units) and the current min/max Y was 2 to 4 (also a distance of 3) — multiplying the distances of X and Y, 3 times 3, would result in an area of 9. If this block group had a child count of 9 blocks, this shape would equal the checked area size, and the shape would be recognized as completely filled in. Creating this algorithm was rather simple, as illustrated by this pseudo math equation:

\left( blocks^{cnt} == area \right) ? = \left\{ \begin{array}{cl} |x| = \max\left(\text{vx}\right) - \min\left(\text{vx}\right) ,\\ |y| = \max\left(\text{vy}\right) - \min\left(\text{vy}\right) ,\\[5px] \hline \hline round \left(|x| \cdot |y|\right) \end{array} \right.

This can be illustrated by the small amount of self-documented code that I extracted from Prim:

Having stored all the X and Y coordinates each time a block is added to the block group into separate arrays: vx and vy, the first function setMinMax() sets the min/max values, then the distances are set by taking the absolute value (distance) of the max – min + 1 (to account for the zero-based array), in setDistances(). Finally, the check to see if the area equals the number of blocks stored in this block group in isAreaEqualToCount() will return whether or not this shape is completed. If this returns true, the shape is marked as “completed”, and further operations can be done on it in its new state; otherwise, nothing needs to be done this time around.

Example:

Incomplete Block Group

The start of a block group has 5/9 blocks filled in, thus the shape is not yet completed. 5 \neq 9 = \left\{ \begin{array}{cl} |x| = 4 - 2 ,\\ |y| = 2 - 0 ,\\[5px] \hline \hline round \left(3 \cdot 3\right) \end{array} \right.

Completed Block Group

Two blocks are fired on each side of the missing portion and now 9/9 blocks are filled in, making it complete. 9 \equiv 9 = \left\{ \begin{array}{cl} |x| = 4 - 2 ,\\ |y| = 2 - 0 ,\\[5px] \hline \hline round \left(3 \cdot 3\right) \end{array} \right.

This check ends up being small in size and processing power, rather optimal and self-documenting, and shouldn’t need a more complicated algorithm such as a flood fill to perform properly. When this algorithm was first introduced and worked somewhat properly, some oddities I noticed as a result were mainly based on the performance of the physics and the timing of the algorithm being started in a coroutine. Thus, I ended up refactoring the block groups and blocks in separate states, fully decoupled from each other, that would request that the completed check was called and finished in time for these edge cases to perform well.