在2Darrays中检查4个连续相同的对角元素（连接4游戏）
我正在努力在Java上实现connect 4 Game。 我差不多完成了模拟游戏的程序。
我使用2D字符数组char [][] board = new char[6][7]; 代表游戏的网格。
我已经实现了checkHorizontal方法来查找是否有4个连续的相同水平元素来检查win条件。 我还实现了checkVertical方法来查找是否有4个连续相同的垂直元素来检查win条件。
我在编写checkDiagonal方法的算法时有点困惑， checkDiagonal方法检查2Darrays中4个连续相同对角线元素的所有可能性。
以下是游戏中对角线胜利案例的2个例子
情况1：
* * * * * * * * * * * * * * Y * * * * * * RY * * Y * * YRYRYRR RYRYRYR
案例2：
* * * * * * * * * * * * * * * * * * * R * * * * * RY * * * * RYR * YYRYRYR
如何检查rows和columns以解决这些情况？
您只需要检查新类型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 dy, 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[y][x] == 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检查参数用于在不同方向上移动，而无需为每个方向分别设置方法。
在你的水平检查代码中，你可能通过在循环中将x添加1来移动到下一个部分（保持y不变，即将0添加到y）。 在垂直检查代码中，通过向y（和0到x）添加1来移动到下一个部分。 要沿对角线移动，您需要在x和y坐标上添加1。
为了能够使用单一方法检查所有方向，check（）使用移动方向的参数：dx = 1和dy = 0在每个步骤中将1添加到x和0到y，因此您要进行水平检查。 如果dx = 0且dy = 1，则进行垂直检查。
编辑 ：摆脱了检查助手，因为它只在一个地方真正需要
另一种解决方案，效率较低但可能更容易推理，是将行换1到另一个数组并重用您的垂直赢代码。
例如，将左数组从左到右对角线移动到更大的数组中，如下所示：
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * R * * * * * * R * * * * * RY * * * * * RY * * * * RYR * * * * RYR * YYRYRYRYYRYRYR
对于从右到左的对角线：
* * * * * * * * * * * * * * * * * * * * * * * * * * * * Y * * * * * * Y * * * * * * RY * * Y * * RY * * Y * * YRYRYRRYRYRYRR RYRYRYRRYRYRYR
现在，您可以重复使用垂直获胜代码进行对角线获胜。
检查对角线类似于检查水平，增加arrays偏移的复杂性。 你能做到的一种方法是对arrays进行蛮力行走。
你走的是主要专业或专业专业。 随时随地增加你的位置。 即下面显示了一行主要步行。
首先检查
* * * X * * * * * X * * * * * X * * * * * X * * * * * * * * * * * * * * * * * * * *
下一个：
* * * * X * * * * * X * * * * * X * * * * * X * * * * * * * * * * * * * * * * * * *
等等。 一旦到达第一行的末尾，就会增加行并重复。 即下一行的第一次迭代将是。
* * * * * * * * * * X * * * * * X * * * * * X * * * * * X * * * * * * * * * * * * *
重复所有行，你已经覆盖了那个方向的所有对角线。 现在重复对角线的相反方向。
因为你知道你从位置4（索引3）开始，所以你可以简单地使用直接偏移。 即
if( board[row][column] == board[row+1][column-1] == board[row+2][column-2] == board[row+3][column-3] ){ /* You have a match */ }
我喜欢用于许多基于网格的问题的概念称为dx/dy 。 基本思路是你有2个数字数组，一个用于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方向arrays对：
int[] dx = {0, 0, 1,-1} int[] dy = {1,-1, 0, 0}
并且用于检查连接4的简洁版本，因为反向方向对于我们的目的是相同的（即，向上 – 左= =向右 – ）：
int[] dx = {1, 0, 1,-1} int[] dy = {0,-1, 1, 1}
打破这一点，我们看到可以看到假装堆叠的数字是x，y对。 因此，如果我们想要8个运动方向，请考虑下面的板，其中S = (x, y)我们当前的位置：
- - - - - - - - - - - - - - - - - - - - - - - - - - - - S - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
如果你看两个数组i-th索引，你将得到一对dx / dy坐标（这些对在上面的数组中垂直对齐）：
dx[4] = 1 dy[4] = -1
这将为我们提供x和y的delta（或变化）以达到我们的新位置。 现在看一下这个板，你可以看到8个dx / dy对中的每个对你带来的位置（根据数组的索引编号）：
- - - - - - - - - - - - - - - - - - - 6 0 3 - - - - - 5 S 2 - - - - - 7 1 4 - - - - - - - - - - - - - - - - - - - - - - - - - -
所以你可以在这里看到第4个位置
( Sx + 1, Sy - 1 )
对应于dx / dy数组
( Sx + dx[4], Sy + dy[4] )
现在，如果您将其置于for循环中，则可以检查ax，y位置周围的所有8个方格。
通过简单地构造不同的对，可以以许多不同的方式（例如，骑士在国际象棋中的运动）应用该概念。 考虑骑士运动的arrays：
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; }
第五步：最后我们需要设置胜利者。 这只是检查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; } } } } }
PS对于所有这些伪代码，您需要处理网格上的索引越界。 我把它留下来以减少混乱。
PPS我使用GRID(x, y)来表示网格上的x，y或行，列对。 这可以很容易地用2Darrays代替。 同样这只是伪代码，所以为了清楚起见我使用了GRID(x, y) 。