Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
When you described your problem, references didn't come to mind? –  Daniel Oct 24 '11 at 22:23
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
Thanks for stating that there is only one line that two boxes share. I didn't come up with that idea. –  pimvdb Apr 28 '11 at 14:09
    
@pimvdb that's the key, I think; after that, it's just like implementing any shared-relationship structure (like a tree/graph). –  ashes999 Apr 28 '11 at 18:57
    
After some trial-and-error, I actually prefer your first idea - that's a little easier to implement I guess. It seems it's not that complicated to create a function that automatically updates the line data of the neighbour box as well. –  pimvdb Apr 28 '11 at 20:02
add comment

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

share|improve this answer
    
I didn't know at all that a complete book has been written about this game. I see it's available at Google Books for free, so that's great. Thanks. –  pimvdb Apr 28 '11 at 20:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.