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.*

Edit adding link to code

code

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.

1 Like
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.

4 Likes
5

I edited post to link to code

6

Thank you for the links. I watched a few vids on matrix transformations. I did not take linear algebra so its this kind of information that is really helpful! I’ll implement the matrix method and test.

I am representing patterns like:

pub const PatternPoint = struct {
    x: i8,
    y: i8,
    material: game.MaterialType,
    pub fn new(x: i8, y: i8, m: game.MaterialType) PatternPoint {
        return PatternPoint{ .x = x, .y = y, .material = m };
    }
};

rotations are done:

 pub fn pattern_rotations(allocator: std.mem.Allocator, pattern: []card.PatternPoint) ![4][]card.PatternPoint {
        var full_rotations = [_][]card.PatternPoint{&.{}} ** 4;
        const rotation_point = board.Point.new(pattern[0].x, pattern[0].y);
        var position = pattern;

        //Reflections

        //Rotations
        for (0..4) |i| {
            if (i == 0) {
                full_rotations[i] = pattern;
                continue;
            }
            position = try rotatePattern(allocator, position, rotation_point, 90);
            full_rotations[i] = position;
        }
        // log.debug("{any}", .{full_rotations});
        return full_rotations;
    }
pub fn rotatePattern(allocator: std.mem.Allocator, pattern: []const card.PatternPoint, center: board.Point, degrees: f16) ![]card.PatternPoint {
        // var rotated = [_]card.PatternPoint{.{ .material = .Brick, .x = -50, .y = -50 }} ** 10;

        var rotated = try std.ArrayList(card.PatternPoint).initCapacity(allocator, pattern.len);
        defer rotated.deinit(allocator);
        // for (0..pattern.len) |_| {
        //     try pattern_arraylist.append(allocator, .{ .material = .Brick, .x = 0, .y = 0 });
        // }
        // const copied_pattern = try pattern_arraylist.toOwnedSlice(allocator);

        const radians = std.math.degreesToRadians(degrees);
        for (pattern, 0..pattern.len) |point, _| {
            // const material_symbol = board.board.board.PieceType.str(board.board.board.PieceType{ .material = point.material });
            // if (point.x == center.x and point.y == center.y) {
            //     print("Skipping center block of pattern\n", .{});
            //     continue;
            // }
            const point_minus_center_x = (@as(f16, point.x) - center.x);
            const point_minus_center_y = (@as(f16, point.y) - center.y);
            // print("Center: {},{}\n", .{ point_minus_center_x, point_minus_center_y });

            // log.debug("Point: {d},{d}", .{ point.x, point.y });
            // x' = cₓ + cosθ(x−cₓ) − sinθ(y−c_y)
            const rotatedX: f16 = center.x + @cos(radians) * point_minus_center_x - @sin(radians) * point_minus_center_y;

            // y' = c_y + sinθ(x−cₓ) + cosθ(y−c_y)
            const rotatedY: f16 = center.y + @sin(radians) * point_minus_center_x - @cos(radians) * point_minus_center_y;

            // log.debug("Rotated Point: {d},{d}", .{ @round(rotatedX), @round(rotatedY) });
            // log.debug("Rotated Point(float): {d},{d}  {s}", .{ rotatedX, rotatedY, material_symbol });

            const rotatedPoint: card.PatternPoint = .{ .material = point.material, .x = @round(rotatedX), .y = @round(rotatedY) };
            try rotated.append(allocator, rotatedPoint);
        }

        // return try allocator.dupe(card.PatternPoint, rotated[0..pattern.len]);
        return rotated.toOwnedSlice(allocator);
        // return rotated;
    }
7

I didn’t either :slight_smile: I thought linear algebra and matrices were overly complex esoteric math nonsense until I started teaching myself 3D programming and had it explained to me that it’s just a clever way to multiply and add numbers, and that 0s and 1s can be used to turn multiplications/additions into no-ops. This webgl2fundamentals.org article was quite enlightening for me.

In this case because we’re only working with rotations and reflections and the matrices all follow a set pattern you don’t even really need to think of it as any kind of advanced math, it’s just different permutations of the following:

xx = x * m[0] + y * m[1];  yy = x * m[2] + y * m[3];

// the 1, 0, 0, 1 pattern cancels out the middle two multiplications,
// (preserving x and y)
xx = x * m[0] + y * m[1];  yy = x * m[2] + y * m[3];
xx = x * 1 + y * 0;        yy = x * 0 + y * 1;
xx = x + 0;                yy = 0 + y;
xx = x;                    yy = y;

// the 0, 1, 1, 0 pattern cancels out the outermost two multiplications,
// (swapping x and y)
xx = x * m[0] + y * m[1];  yy = x * m[2] + y * m[3];
xx = x * 0 + y * 1;        yy = x * 1 + y * 0;
xx = 0 + y;                yy = x + 0;
xx = y;                    yy = x;
1 Like