How to store 'dots and boxes' data?

Question

I'm trying to explore a little as to how I could make a simple 'dots and boxes' game.

The problem I'm facing is in what way to store which lines are allocated by who. The problem lies in the fact that all inner lines are shared by neighbour boxes. So I can't just have four variables on each box because the right line of upper left-hand box is actually the same as the left line of box next to it. So I'd need them to be stored in one variable.

What technique of saving this data would be practical in this case?

Answer 1

It's not actually a problem. What you need to do is make sure that lines are shared references, not simply variables.

So if you have two boxes, A and B, sharing a line:

.  .   .
 A | B
.  .   .

Then a.RightLine and b.LeftLine both point to the same reference. Or, if it's a boolean, when the user clicks on the line, make sure you update both A and B to keep track of that fact.

Another solution might be to keep a hash-map of lines, where the key is the indicies of both boxes plus the line side.

So the above example would be something like:

lines["A, B"] = solid

Because you can uniquely identify a line with two boxes, since every pair of boxes only have one shared side.

Answer 2

The way I've traditionally handled it is as two arrays of lines: one n-by-(n+1) array of vertical lines (one for each row and one for each column-plus-one - there's the one to the left of each column and then the last set of vertical lines on the right), and likewise, one (n+1)-by-n array of horizontal lines, one for each row-plus-one and one for each column. This requires a very little special-casing (the two boxes you'll have to check for matches when a line's drawn are different for horizontal vs. vertical), but it also allows for easy indexing of the lines corresponding to a given box (the edges of Box[a,b] are HLine[a,b], HLine[a+1,b], VLine[a,b], and VLine[a,b+1]).

And if you ever decide to make the game more sophisticated (especially on an AI front), then you'll probably want a more abstract representation for strategic purposes: you may want to look into Nimstring and Berlekamp's dots-and-boxes book - a lot of positions that look completely different on the board are actually identical from a mathematical perspective (for instance, 'chains' of boxes with two walls closed off and two open to the next-and-previous box).