java检查2D数组中4个连续相同的对角线元素（连接4个游戏）

Question

我正在Java上实现connect 4游戏。我几乎完成了模拟游戏的程序

我使用2D字符数组char [][] board = new char[6][7];来表示游戏的网格

我已经实现了checkHorizontal方法来查找是否有4个连续的相同水平元素来检查win条件。我还实现了checkVertical方法，以查找是否有4个连续的相同垂直元素来检查win条件

在编写checkDiagonal方法的算法时，我有点困惑，该算法检查2D数组中4个连续相同对角线元素的所有可能性

下面是游戏中对角赢的两个例子

案例1：

 * * * * * * *
 * * * * * * *
 Y * * * * * *
 R Y * * Y * *
 Y R Y R Y R R
 R Y R Y R Y R

案例2：

 * * * * * * *
 * * * * * * *
 * * * * * R *
 * * * * R Y *
 * * * R Y R *
 Y Y R Y R Y R

我如何检查rows和columns来解决这些问题

Answer 1

检查对角线类似于检查水平线，增加了阵列偏移的复杂性。其中一种方法是在阵列中进行蛮力行走

你用行大调或列大调走路。在你前进的过程中增加你的位置。下面的Ie显示了一排主要的步行路线

第一次检查

* * * X * * *
* * X * * * *
* X * * * * *
X * * * * * *
* * * * * * *
* * * * * * *

下一步：

* * * * X * *
* * * X * * *
* * X * * * *
* X * * * * *
* * * * * * *
* * * * * * *

等等。 到达第一行末尾后，增加该行并重复。 下一行的第一次迭代是

* * * * * * *
* * * X * * *
* * X * * * *
* X * * * * *
X * * * * * *
* * * * * * *

对所有行重复上述步骤，你已经覆盖了该方向的所有对角线。现在对对角线重复相反的方向

在数组方面，因为您知道从位置4（索引3）开始，您可以简单地使用直接偏移。Ie

if( board[row][column] == board[row+1][column-1] == board[row+2][column-2] == board[row+3][column-3] ){
  /* You have a match */
}

Answer 2

你只需要检查一个新的type类型被放置在哪里，因为游戏场的其余部分保持不变。在这里，你可以这样做：

/** 
 * Counts pieces of the given type, starting at (y, x), 
 * in the direction denoted by (dy, dx).
 * Stops at field boundaries or when a different field type is encountered. 
 */
int count(char type, int x, int y, int dx, int dy) {
  int count = 0;
  x += dx;  // Skip the piece at (y, x) to avoid counting it twice
  y += dy;  // when looking in both directions on a line.
  while (x >= 0 && x < 7 && y >= 0 && y < 6 && board[x][y] == type) {
    count++;
    x += dx;  // Move in the direction denoted by (dy, dx)
    y += dy;
  }
  return count;
} 

/**
 * Main entry point after a new piece of type `type` was added at (y, x). 
 * Returns true if this connects 4 or more in any direction.
 */
boolean check(char type, int x, int y) {
  return count(type, x, y, -1, 0) + 1 + count(type, x, y, 1, 0) >= 4  // horizontal
      || count(type, x, y, 0, -1) + 1 + count(type, x, y, 0, 1) >= 4  // vertical
      || count(type, x, y, -1, -1) + 1 + count(type, x, y, 1, 1) >= 4  // diagonal
      || count(type, x, y, -1, 1) + 1 + count(type, x, y, 1, -1) >= 4);
}  

dx和dy check参数用于向不同方向移动，而无需为每个方向使用单独的方法

在水平检查代码中，您可能通过在循环中将1添加到x（保持y恒定，即将0添加到y）来移动到下一个片段。在垂直检查代码中，通过将1添加到y（0添加到x）来移动到下一块。要沿对角线移动，需要在x和y坐标上都加1

为了能够用一个方法检查所有方向，check（）使用运动方向的参数：dx=1和dy=0在每个步骤中为x添加1，为y添加0，因此可以进行水平检查。当dx=0，dy=1时，进行垂直检查

编辑：取消了检查助手，因为它只在一个地方真正需要

Answer 3

另一种效率较低但可能更容易推理的解决方案是将行按1移位到另一个数组中，并重用垂直win代码

例如，将从左到右对角线的左数组移到一个更大的数组中，如下所示：

* * * * * * *    * * * * * * *
* * * * * * *      * * * * * * *
* * * * * R *        * * * * * R *
* * * * R Y *          * * * * R Y *
* * * R Y R *            * * * R Y R *
Y Y R Y R Y R              Y Y R Y R Y R

对于从右到左的对角线：

* * * * * * *                * * * * * * *
* * * * * * *              * * * * * * *
Y * * * * * *            Y * * * * * *
R Y * * Y * *          R Y * * Y * *
Y R Y R Y R R        Y R Y R Y R R
R Y R Y R Y R      R Y R Y R Y R

现在你可以重复使用你的垂直赢码来赢对角线

Answer 4

我喜欢用一个概念来解决很多基于网格的问题，这个概念叫做dx/dy。基本的想法是你有两个数字数组，一个代表delta x，一个代表delta y，指定在这个方向上走多远。例如：这里有一个8方向的dx/dy阵列对

int[] dx = {0, 0, 1, 1, 1,-1,-1,-1}
int[] dy = {1,-1, 0, 1,-1, 0, 1,-1}

以及更小的4方向阵列对：

int[] dx = {0, 0, 1,-1}
int[] dy = {1,-1, 0, 0}

以及用于检查connect 4的简明版本，因为反向方向与我们的目的相同（即左上==右下）：

int[] dx = {1, 0, 1,-1}
int[] dy = {0,-1, 1, 1}

我们可以假设堆叠的数字是x，y对。因此，如果我们需要8个方向的移动，考虑下面的棋盘位置：{{CD2>}，我们当前的位置：

- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - S - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -

如果查看两个数组的i-th索引，您将得到一对dx/dy坐标（这对坐标在上面的数组中垂直对齐）：

dx[4] =  1
dy[4] = -1 

这将给我们x和y的增量（或变化），以到达我们的新位置。因此，现在看看电路板，你可以看到8个dx/dy对中的每一个都会给你带来什么（根据数组的索引编号）：

- - - - - - - -
- - - - - - - -
- - - 6 0 3 - -
- - - 5 S 2 - -
- - - 7 1 4 - -
- - - - - - - -
- - - - - - - -
- - - - - - - -

你可以看到这里的位置4是

( S.x + 1, S.y - 1 )

对应于dx/dy阵列，如下所示：

( S.x + dx[4], S.y + dy[4] )

现在，如果你把它放在一个for循环中，你可以检查x，y位置周围的所有8个正方形

通过简单地构造不同的对，这个概念可以应用于许多不同的方式（例如，国际象棋中骑士的移动）。考虑骑士运动的数组：

int[] dx = {1, 1, 2, 2,-1,-1,-2,-2}
int[] dy = {2,-2, 1,-1, 2,-2, 1,-1}

骑士方格（K）和他所有可能的动作：

- - - - - - - -
- - - - - - - -
- - 4 - 0 - - -
- 7 - - - 2 - -
- - - K - - - -
- 6 - - - 3 - -
- - 5 - 1 - - -
- - - - - - - -

---

有了这些知识，我们可以通过几个步骤解决您的问题

第1步：在网格中的每个x，y坐标上循环：

for(int x = 0; x < width; x++)
    for(int y = 0; y < height; y++)

第2步：现在我们应用dx/dy来检查8个方向上的所有邻居：

for(int x = 0; x < width; x++) {
        for(int y = 0; y < height; y++) {
        for(int i = 0; i < dx.length; i++) {
            int xTemp = x + dx[i];
            int yTemp = y + dy[i];
        }
    }
}

第3步：检查我们是否有颜色相同的邻居：

for(int x = 0; x < width; x++) {
        for(int y = 0; y < height; y++) {

        if( GRID(x, y) == EMPTY) continue;

        for(int i = 0; i < dx.length; i++) {
            int xTemp = x + dx[i];
            int yTemp = y + dy[i];

            if( GRID(x, y).color == GRID(xTemp, yTemp).color)
                checkLine( GRID(x, y), dx[i], dy[i], GRID(x,y).color)  
        }
    }
}

第4步：checkLine(Grid, xOrigin, yOrigin, dx, dy)现在我们只需签入一行，看看是否有4行

boolean checkLine(GRID, x, y, dx, dy, color) {
    for(int i = 0; i < 4; i++) 
        if( GRID(x + dx*i, y + dy*i) != color) return false;

    return true;
}

第5步：最后，我们需要确定胜利者。这只是检查checkLine()的结果

for(int x = 0; x < width; x++) {
        for(int y = 0; y < height; y++) {

        if( GRID(x, y) == EMPTY) continue;

        for(int i = 0; i < dx.length; i++) {
            int xTemp = x + dx[i];
            int yTemp = y + dy[i];

            if( GRID(x, y).color == GRID(xTemp, yTemp).color) {
                if( checkLine( GRID(x, y), dx[i], dy[i], color) ) {
                    winner = color;
                    return;
                }
            }
        }
    }
}

p.S对于所有这些psuedo代码，您需要在网格上处理索引越界。我忽略了这一点，以减少混乱

p.p.S我使用GRID(x, y)来表示网格上的x、y或行、列对。这很容易被2D阵列取代。同样，这只是psuedo代码，所以为了清晰起见，我使用了GRID(x, y)