Planar Geometric Pattern Matching

Help
1

image
image1319×896 70.5 KB

Fig. 1 - Visual representation of a “complete pattern” as seen from the perspective of viewing the board

Fig. 2 - A valid game pattern orientation outside the “complete pattern”*

Fig. 3 - Representation of how the board is stored in memory as a 2d Arraylist*

For the game I’m making, I need to match certain patterns to identify where a player can convert placed resources into a building. I originally did this by taking a base pattern and rotating 90 degrees to make a “complete pattern”. However, I identified this is not complete because it does not make it possible to match reflections of that pattern. if the base pattern is: Brick(2,2) Glass(3,2) Wheat(3,3) It is impossible to match the pattern in figure 2 without reflecting and translating the center piece back to the same point. This got me thinking maybe I’m doing this wrong.

Should I implement the reflection piece and add to the “complete pattern” or is there a better way to do pattern matching that is suitable for this situation?

Note: patterns are stored similarly in 1 dimensional slices of resources or a two dimensional slice for the “complete pattern” used by placing on center point and then checking if any pattern is fulfilled.*

2

Hey! Sounds like an interesting problem!
Can you share some code?

3

Essentially you seem to have a pattern that can be placed on a 2D grid, and any reflection or rotation by 90 degrees of it is also a valid placement. For arbitrary 2D shapes, this makes for 8 different rotation/reflection options, given that you fix one of the squares and rotate around it. I.e. for the three square piece in shape of an L you have:
oox
oxx
ooo
But also the shape:
ooo
oxo
xxo

is valid.

On the grid, each square has resources, which much match the resources of the pattern.

I think the ‘trick’ you have where you check against a fixed 2D pattern works in some cases but fails in other cases for more complicated shapes.
For example, suppose you have a shape like:
xxx
oxo
ooo

Where the top left and top right corner require different resources. There is no way to make a fixed pattern in such a case if you also allow for reflections.

I would guess it is probably easiest if you either construct the 8 different patterns once up front and iterate through them, either explicitly or implicitly. Alternatively, if you only have to check one specific pattern at a time, you could make an algorithm that takes the specific reflection and/or rotations that are applied to the shape as input, and then iterate over the squares of the shape to check if the resources match. This last solution seems the easiest to me.

4

Which approach is best is completely dependent on the answers to questions such as “how large/complex do I expect patterns to get?” and “how many patterns will there be?” and “how easy should it be for developers/modders to define patterns?”.

Your example pattern has certain useful symmetries and could therefore be quite trivially matched against using an algorithm like

if (tile(x, y) == .glass) {
    if (tile(x + 1, y) == .brick or tile(x - 1, y) == .brick) {
        return tile(x, y + 1) == .wheat or tile(x, y - 1) == .wheat;
    }
    if (tile(x, y + 1) == .brick or tile(x, y - 1) == .brick) {
        return tile(x + 1, y) == .wheat or tile(x - 1, y) == .wheat;
    }
}
return false;

but defining patterns in this manner will obviously be a pain in the ass to maintain if you have more than a handful of simple patterns.

I’d probably define patterns like

const pattern: []const Entry = &.{
    .{ .x = 0, .y = 0, .resource = .brick },
    .{ .x = 1, .y = 0, .resource = .glass },
    .{ .x = 1, .y = 1, .resource = .wheat },
};

and use transformation matrices to easily check all eight rotations/reflections:

const matrices: []const [4]i32 = &.{
    .{  1,  0,  0,  1 }, // rotate   0 deg
    .{  1,  0,  0, -1 }, // rotate   0 deg, reflect
    .{  0, -1,  1,  0 }, // rotate  90 deg
    .{  0,  1,  1,  0 }, // rotate  90 deg, reflect
    .{ -1,  0,  0, -1 }, // rotate 180 deg
    .{ -1,  0,  0,  1 }, // rotate 180 deg, reflect
    .{  0,  1, -1,  0 }, // rotate 270 deg
    .{  0, -1, -1,  0 }, // rotate 270 deg, reflect
};

fn test(grid: Grid, grid_x: i32, grid_y: i32, pattern: []const Entry) bool {
    next_matrix: for (matrices) |m| {
        for (pattern) |p| {
            const x = grid_x + p.x * m[0] + p.y * m[1];
            const y = grid_y + p.x * m[2] + p.y * m[3];
            if (grid.getResource(x, y) != p.resource) {
                continue :next_matrix;
            }
        }
        return true;
    }
    return false;
}

This approach is simple to reason about and maintain as you define more complicated patterns. It can also be easily adapted to more complicated rules like “the neighboring tile must belong to category .mineral and have a quality value > 5”. The algorithm will perform some redundant tests for entries where X = 0 or Y = 0, but I doubt this will matter in practice.