Data structure for game Dots and Boxes

Question

What would be a good data structure to represent the status of the game Dots and Boxes?

I came up with using 2 matrices of boolean, for horizontal and vertical lines, but maybe there's a more elegant way of doing this (and the operations: add line, check line, check square).

Answer 1

Using a pair of two-dimensional arrays of booleans called linesX and linesY makes sense to me. Each array would have one more row/column than the total number of squares on the board in that given X/Y direction. Here's a code sample of check square with that solution:

bool isSquareComplete(int x, int y) {
    return linesX[x][y] && linesX[x + 1][y] && linesY[x][y] && linesY[x][y + 1];
}

Answer 2

I recently did this and used a map of box objects. The map was a tuple and the box object. This allows for very fast access and is simpler to implement the edge algorithms. It is a lot easier to check unsuccessfully for <-1,0> rather than special case the left edge. To avoid the data duplication, there was an array representing the edges and the box objects knew how to access it.

One advantage of using box objects rather than just an array is that it makes strategy algorithms easier. You often want to keep track of lists of boxes that are close to full, etc. This can't be done easily in an array.

Answer 3

I would use a single two-dimensional array that corresponds to the play area size. Each element in the array can then store either an object (or structure, depending on language used) that contains 4 bools, one for each side. Checking to see if a box is complete becomes as simple as returning the logical ands of the object at the given co-ordinates.

The single two-dimensional array makes maintenance and troubleshooting errors much easier.

Answer 4

My playable game, with adjustable W, H, and numPlayers, is here: http://pconstrictor.github.io/cellsurround/

(Source code is there too. Still needs to be refactored into ES6 module syntax, and hopefully rewritten using FP. So if there's a simpler model design, I'd love to know.)

For the data model, I used a single 2D array of size w by h. Each cell has a list of sides (four in the case of this square grid) and becomes 'filled' when all sides are 'filled'. Note that the user then gets an extra turn. Also, sometimes a single action results in two cells become filled simultaneously.

// MODEL
exports.SquareGrid = function(width, height, players) {

    // reset (also serves as init)
    this.reset = function(w, h, players) {
        this.players = players;
        this.player = players.firstPlayer();
        var m = [];
        this.matrix = m; // will be a 2D array (well, array of arrays)
        this.height = h;
        this.width = w;

        // fill matrix
        var toLeft = null, above = null; // these will be used for cells
                                            // sharing sides
        for (var row = 0; row < h; row++) {
            m[row] = [];
            for (var col = 0; col < w; col++) {
                toLeft = col ? m[row][col - 1] : null;
                above = row ? m[row - 1][col] : null;
                m[row][col] = exports.createSquareCell(above, toLeft);
            }
        }
    }

...
}

For actually displaying the UI, I used a single 2D array (of size 2w+1 by 2h+1) as the view model, in which dots, edges, and cells are all simply represented as either filled or empty. (Dots start out filled and always remain so.) This translates nicely into, say, an HTML table that can be easily rendered with two loops and no extra logic. Here is the 7 by 9 array that corresponds to a 3x4 model. Note that these pseudo columns and rows should ideally display in alternating sizes, just for visual reasons.

(w = 3, h = 4) so (ww = 7, hh = 9)
. ___ . ___ . ___ .
|     |     |     |
|     |  p1 | p1  |
.     . ___ . ___ .
|     |     |     |
|     |  p1 |  p2 |
.     . ___ . ___ .
|     |           |
|     |           |
.     . ___ .     .
|                 |
|                 |
. ___ . ___ . ___ .

Here's the actual view model.

// VIEW MODEL

exports.SquareGridView = function(gameModel, appId, resetFuncString) {

// prepare to render the latest of whatever is in the model
this.refresh = function() {
    var h = this.gridModel.height;
    var w = this.gridModel.width;

    // Initialize the UI table, whose dimensions are bigger than the
    // model's.
    var viewPm = [];
    var hh = viewCoord(h);
    var ww = viewCoord(w);
    for (var i = 0; i < hh; i++) {
        viewPm[i] = [];
    }

    // But loop over the model when actually filling it in. (Shared
    // cells cause double writes to viewPm, but oh well.)
    for (var row = 0; row < h; row++) {
        for (var col = 0; col < w; col++) {
            var cell = this.gridModel.matrix[row][col];
            var i = viewCoord(row), j = viewCoord(col);
            viewPm[i][j] = cell.owner;
            viewPm[i - 1][j] = cell.sides['top'];
            viewPm[i + 1][j] = cell.sides['bottom'];
            viewPm[i][j - 1] = cell.sides['left'];
            viewPm[i][j + 1] = cell.sides['right'];
            // Note: vertices can be either filled or left undefined here (and hard-coded as filled in the HTML).
        }
    }
...

And here's the actual render-as-html step:

var t = []; // the html text
// TODO: split the HTML bits out into a template file? Use React or Elm?
...

t.push('<table class="squaregrid">\n');
var tdClass, tdId; // 'vertex', '0.0';
for (var i = 0; i < hh; i++) {
    t.push("  <tr> \n");
    for (var j = 0; j < ww; j++) {
        t.push(this.tdHtml(viewPm, i, j));
    }
    t.push(" </tr>\n");
}
t.push("</table>\n");

...

The tdHtml() function is omitted--it generates a TD with correct ID and classes.