woutr_be - 3 years ago 237
C Question

# Four in a row logic

I'm currently working on a basic four in a row game for myself, but I'm rather stuck at the logic behind it.

Currently I have this multi-dimensional array that represents the board

``````[
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]
]
``````

`0`
would represent an empty slot, while
`1`
and
`2`
represent a player.
So let's say after a while you get this array:

``````[
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 0, 0],
[0, 0, 0, 1, 1, 0, 0],
[0, 0, 1, 2, 2, 2, 0],
[0, 1, 2, 2, 1, 2, 0]
]
``````

How can I write the logic to check if there are four in a row?
Calculating it for horizontal and vertical ones seem rather easy (although still figuring out the best way), but how would I do this for diagonal lines?

Best bet is to probably divide the search space into four:

• vertical;
• horizontal;
• right and down;
• right and up.

then limit your starting and ending coordinates based on the direction.

For example, let's say your array is `board[row=0-5][col=0-6]` with `board[0][0]` at the top left.

First vertical (loops are inclusive at both ends in this pseudo-code):

``````for row = 0 to 2:
for col = 0 to 6:
if board[row][col] != 0 and
board[row][col] == board[row+1][col] and
board[row][col] == board[row+2][col] and
board[row][col] == board[row+3][col]:
return board[row][col]
``````

This limits the possibilities to only those that don't extend off the edge of the board, a problem most solutions have when they simplistically start by checking each cell and going out in all directions from there. By that, I mean there's no point checking a start row of 3, simply because that would involve rows 3, 4, 5 and 6 (the latter which does not exist).

Similarly, for horizontal:

``````for row = 0 to 5:
for col = 0 to 3:
if board[row][col] != 0 and
board[row][col] == board[row][col+1] and
board[row][col] == board[row][col+2] and
board[row][col] == board[row][col+3]:
return board[row][col]
``````

For right and down, followed by right and up:

``````for row = 0 to 2:
for col = 0 to 3:
if board[row][col] != 0 and
board[row][col] == board[row+1][col+1] and
board[row][col] == board[row+2][col+2] and
board[row][col] == board[row+3][col+3]:
return board[row][col]

for row = 3 to 5:
for col = 0 to 3:
if board[row][col] != 0 and
board[row][col] == board[row-1][col+1] and
board[row][col] == board[row-2][col+2] and
board[row][col] == board[row-3][col+3]:
return board[row][col]
``````

Now, you could actually combine those two by making `for col = 0 to 3` the outer loop and only doing it once rather than twice but I actually prefer to keep them separate (with suitable comments) so that it's easier to understand. However, if you're addicted to performance, you can try:

``````for col = 0 to 3:
for row = 0 to 2:
if board[row][col] != 0 and
board[row][col] == board[row+1][col+1] and
board[row][col] == board[row+2][col+2] and
board[row][col] == board[row+3][col+3]:
return board[row][col]
for row = 3 to 5:
if board[row][col] != 0 and
board[row][col] == board[row-1][col+1] and
board[row][col] == board[row-2][col+2] and
board[row][col] == board[row-3][col+3]:
return board[row][col]
``````

Then, if no wins were found in the four possible directions, simply return `0` instead of the winner `1` or `2`.

So, for example, your sample board:

``````row
0   [0, 0, 0, 0, 0, 0, 0]
1   [0, 0, 0, 0, 0, 0, 0]
2   [0, 0, 0, 1, 1, 0, 0]
3   [0, 0, 0, 1, 1, 0, 0]
4   [0, 0, 1, 2, 2, 2, 0]
5 > [0, 1, 2, 2, 1, 2, 0]
^
0  1  2  3  4  5  6 <- col
``````

would detect a winner in the right and up loop where the starting cell was `{5,1}` because `{5,1}`, `{4,2}`, `{3,3}` and `{2,4}` are all set to `1`.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download