Day 10 Game 10: 30 games in 30 days using Grids
This is what Grids did for us today. What can Grids do for you?
To win game 10, you have to block all the ant paths by placing dominos in their way. This game is played on a rectangular grid, and involves both the faces, and the edges of the grid. It’s based on a “classical” polyomino problem: pack a rectangle with dominoes so that there are no “faults”, where a fault is a straight line between blocks not blocked by any domino. (In our version of the game, you don’t have to fill the entire grid – it makes it slightly easier.. but not much 🙂 This problem cannot be transferred to any grids; for example, hex grids are always fault-free.
There are several ways to deal with edges when it comes to grids:
- You can store edge information in your grid cells (in this case, you would only need to store two edges per cell, and you would need a slightly bigger grid).
- You can use an edge grid (this is similar to the concept of a vertex dual grid, but it’s not a dual).
- You can use a compound grid that represents both edges and faces. For hex grids, this solution can be very elegant; for square grids, it’s not bad but it is not the best.
- Or you can use a dictionary with two indices (one for each face); the entry represents the edge between the two faces (if it exists).
For this game, we used an approach similar to the last, but we simplified it a bit so that edge-paths are easily represented, and we simply maintain whether paths are blocked or not.