JAVA - 围棋游戏算法

Question

我正在尝试实现一种算法来清除围棋游戏中的死子。

我听说 floodfill 是实现此目标的最佳选择，因为递归使用它最有效且更容易实现。

我在我的代码中使用它时遇到问题，想知道我应该如何实现它。

这是我的一门类(class)，它非常不言自明。

import java.io.*;

public class GoGame implements Serializable {

    int size;
    char[][] pos; // This is the array that stores whether a Black (B) or White (W) piece is stored, otherwise its an empty character.

    public GoGame(int s){
        size = s;
    }

    public void init() {
        pos = new char[size][size];
        for (int i=0;i<size;i++) {
            for (int j=0;j<size;j++) {
                pos[i][j] = ' ';
            }
        }
    }

    public void ClearAll() {
        for (int i=0;i<size;i++) {
            for (int j=0;j<size;j++) {
                pos[i][j] = ' ';
            }
        }
    }

    public void clear(int x, int y) {
        pos[x][y]=' ';
    }

    public void putB(int x, int y) { //places a black stone on the board+array
        pos[x][y]='B';
        floodfill(x,y,'B','W');

    }

    public void putW(int x, int y) { //places a white stone on the board+array
        pos[x][y]='W';
        floodfill(x,y,'W','B');

    }

    public char get(int x, int y) {
        return pos[x][y];
    }

    public void floodfill(int x, int y, char placed, char liberty){


        floodfill(x-1, y, placed, liberty);
        floodfill(x+1, y, placed, liberty);
        floodfill(x, y-1, placed, liberty);
        floodfill(x, y+1, placed, liberty);

    }

}

x 和y 是正方形的坐标，placed 是石头放下的字符，liberty 是另一个字符

任何帮助都会很棒!

Answer 1

虽然其他答案在技术上是正确的，但您还缺少更多与 go 相关的逻辑。我认为你需要做的是(在 B 步):

for each W neighbour of the move:
   check that W group to see if it has any liberties (spaces)
       remove it if not

洪水填充对于查找一组石头的范围很有用，但您的例程需要的远不止于此(我在这里进行了简化，并且还试图猜测该例程的用途-请参阅此答案下方的评论).

鉴于上述情况，识别一组中所有石头的洪水填充将是这样的(请注意，它使用第二个数组进行填充，因为您不想更改 pos只是为了找到一个组):

public void findGroup(int x, int y, char colour, char[][] mask) {
    // if this square is the colour expected and has not been visited before
    if (pos[x][y] == colour && mask[x][y] == ' ') {
        // save this group member
        mask[x][y] = pos[x][y];
        // look at the neighbours
        findGroup(x+1, y, colour, mask);
        findGroup(x-1, y, colour, mask);
        findGroup(x, y+1, colour, mask);
        findGroup(x, y-1, colour, mask);
    }
}

您可以调用它来识别单个组(并将其复制到掩码中)，因此它将帮助您识别与 B Action 相邻的 W 组成员(例如)，但这只是一小部分您需要的全部逻辑。

最后，请注意，如果您想对一组中的每颗 gem 做某事，您有两种选择。你可以像上面那样调用一个例程，然后循环 mask 来找到组，或者你可以把你想做的 Action 直接放在例程中(在这种情况下你仍然使用 mask 控制泛洪的程度填写测试 && mask[x][y] == ' ' 但你不使用它作为结果 - 所有的工作在例程返回时完成)。

(按照所有规则编写程序以正确处理 go，实际上非常复杂 - 您还有很多工作要做...:o)