Find if exists diagonally, horizontally, or vertically in 2D - values one after another

Question

So I'm making a boardgame that's 19 by 19. It is basically connect 5, called Gomoku.

I want to make an efficient algorithm to find if there are 'n' pieces in a row. The data is stored as a 2D array of 19x19. But for question's sake, let's say it's 6x6.

0 0 0 1 0 0      0 0 0 0 0 0
0 0 0 1 0 0      0 1 0 0 0 0
0 0 0 1 0 0      0 0 1 0 0 0
0 0 0 1 0 0      0 0 0 1 0 0 
0 0 0 1 0 0      0 0 0 0 1 0
0 0 0 0 0 0      0 0 0 0 0 1

These are two examples of '5' of 1's in a row. How can i test for HORIZONTAL, VERTICAL, and both DIAGONALS?

Here's my inefficient code:

 private boolean firstDiagonalCheck(int x, int y, int num) {
    int count = 1;
    int check = 0;
    boolean rflag = true;
    boolean lflag = true;
    int pos = 1;

    check = turnHuman + 1;

    while (rflag) {
        if (x + pos >= 19 || y + pos >= 19) {
            rflag = false;
            break;
        }
        if (gb.getBoard()[x + pos][y + pos] == check) {
            count++;
            pos++;
        } else {
            rflag = false;
        }
    }

    pos = 1;

    while (lflag) {
        if (x - pos < 0 || y - pos < 0) {
            lflag = false;
            break;
        }
        if (gb.getBoard()[x - pos][y - pos] == check) {
            count++;
            pos++;
        } else {
            lflag = false;
        }
    }

    if (count == num) {
        return true;
    }
    return false;
}

This is only one method for the first Diagonal. There are 3 more.

How can I make it more efficient and check all 4 directions?

EDIT ##################

What my code does is: - Get's the position of the piece (x,y) - Check both sides (up and down if vertical) and count how many in a row there are - If the number of count matches desired, ("num"), then return true, otherwise return false.

WOULD it be more efficient if I checked the WHOLE board every time to see if there are pieces in a row?

Well, it should check all 4 conditions. It doesn't matter if it checks one at a time, but there must be a better way! — Michael Halper, Sep 19 '14 at 19:14
If you're eventually going to check the whole board, then it would be more efficient to just scan each row, column, and diagonal. But if you're only looking to see if the most recent piece create 5 in a row (and you can assume that if 5 in a row elsewhere on the board would have already been identified), then just checking around that one point will be more efficient, since you can eliminate most of the search space. — Tim, Sep 19 '14 at 19:21
If you are willing to change the representation of your board, you might consider bitboards for faster performance: http://stackoverflow.com/questions/7044670/how-to-determine-game-end-in-tic-tac-toe/7046415#7046415. — emsworth, Sep 19 '14 at 19:27
@emsworth Okay! I'll definitely check out bitboards before I move onto anything else. I wanted to use 2D array for simplicity's sake. Are there any other data structures that might be more efficient? — Michael Halper, Sep 19 '14 at 19:31
If you mean efficient with regard to time, I don't know (I don't think so); a lot of chess engines use the bitboard representation. You can pre-cache a lot of bitboards for various lookups, but it is less space-efficient. But you're right, it's not as simple to intuitively understand as a 2D array. — emsworth, Sep 19 '14 at 19:35

Ankit · Answer 1 · 2014-09-19T21:43:40.817

int count=0;
boolean Check(int x,int y)
{  
  int p1;
  int p2;
 if(elementat[x+1][y+1]==1)
  {p1=1; p2=1;}
else   if(elementat[x+1][y]==1)
  {p1=1; p2=0;}
else.  if(elementat[x+1][y-1]==1)
   {p1=1; p2=-1;}
else.  if(elementat[x][y-1]==1)
   {p1=0;p2=-1;}
else.  if(elementat[x-1][y-1]==1)
   {p1=-1; p2=-1;}
else.  if(elementat[x-1][y]==1)
   {p1=-1; p2=0;}
else.  if(elementat[x-1][y+1]==1)
   {p1=-1; p2=1;}
else.  if(elementat[x][y+1]==1)
  {p1=0; p2=1;}

Checknext(x,y);
Checknextinv(x,y);
If(count==5) // 5 means no. of elements to form line
{return true}
else 
   {return false;}
}


Checknext(x,y)  //19 represents the 19x19 matrix
{ if((x+p1)<=19 && (x+p1)>=0 && (y+p2)<=19 && (y+p2)>=0)
      {     if(element[x+p1][y+p2]==1)
             {  count++;
               checknext[x+p1][y+p2];
      }
}
Checknextinv(x,y)
{ if( (x+(-1*p1))<=19 && (x+(-1*p1))>=0 && (y+(-1*p2))<=19 && (y+(-1*p2))>=0))
    {
      if(element[x+(-1*p1)][y+(-1*p2)]==1 )
         {
               count++;
                checknextinv[x+(-1*p1)][y+(-1*p2)];
        }
 }

Find if exists diagonally, horizontally, or vertically in 2D - values one after another

1 Answers1