Support for Bitmask Shapes and Polyominoes in Grids 2.3

Polyominoes are used as pieces in many puzzle games, and now Grids has support for them too.

The technology is not very complicated, but it took us a long time to get here.

First, we had to realize that the grid data structure was not just useful for game boards (or game worlds), but also for game pieces (and sections of game worlds). The first example where we used this idea was in this tri-grid game.

Second, we had to realize that the part of the grid that was usually useful in such cases is the grid shape. In Grids 1, shapes were second class citizens – merely used to make grids. The usual way to get a shape was to make an empty grid from it. This is one of the things we changed in Grids 2: shapes can now be used completely independently. (A useful tip: you can declare a ShapeGraph field in a MonoBehaviour and use the node editor to make shapes for your own purposes too).

Third, we had to make it easier to define more complicated shapes. Shapes used for playing fields are usually simple, symmetric shapes. However, shapes used for pieces are often much more complicated. Although you could define polyominoes using a union of a bunch of rectangles, it is awkward to work with. In this version, we introduce “bitmask” shapes: a shape defined by a bunch of bools that says whether a point is inside a shape or not. We provide a few methods to define these shapes. The easiest is to use an array of strings, like this:

var cross = ExplicitShape.BitMaskShape(new [] {"010", "111", "010"});

Which defines a 3×3 cross:

010
111
010

(The other methods allow you to specify a 2D array of int or bool instead of strings – under the hood all these are converted to the same thing).

There are nodes for these shapes too, but when it comes to using shapes for pieces, you are likely to require a whole bunch of shapes, so it’s easier to make a set of pieces in code. The class Polyominoes defines shapes for all polyominoes up to hexominoes. There are also enums, and dictionaries linking the enums to the actual shapes.

We also added an example that shows how to use these shapes in a typical game. The example shows two important techniques: how to define a custom shape data structure with more information to make it easier to write algorithms, and how to define a custom grid data structure to make it easier to deal with pieces that span multiple cells.

TightShape2 is a shape that guarantees that the shape’s bounding box is as tight as it can be. (IExplicitShapes make no such guarantee, even though it is usually the case). If the bounding box is tight, it is much easier to compare shapes and determine whether they are they same. You can use the bounding box dimensions as early bail-out tests, and then move them to canonical positions and compare the shapes point-by-point.

PuzzleGrid is a grid-data structure that keeps track of multi-cell pieces. For example, it has a contains method that can check an entire shape (not just a single point), it can return the shape (appropriately translated) of a piece at any location (if there is a piece), and place a piece at a location. This type of grid should be useful in any type of game where you have multi-cell pieces that cannot occupy the same space, but moreover, shows the type of thinking in designing algorithms for grid games.