联机围棋的简单实现

    两个月没更新文章了，暂且水一篇（）。本次的主题是——联机围棋。

    使用的语言是JAVA，技术细节为Socket套接字、Thread多线程、Swing图形界面，以及IO流读写。

目标

    1.可以在任何地方访问，不局限于局域网连接通信。

    2.符合基础的围棋下棋规则，黑方先下，轮替下棋。

    3.符合基础的围棋逻辑，自动提子，标记最新下的棋子（方便识别）。

    4.处理速度尽可能的快速，提高效率。

基本实现流程

棋盘定义

    首先是交叉点Cross，定义为枚举类型，一共有五种状态：

public enum Cross {
    NONE, BLACK, WHITE,
    BLACK_CUR, WHITE_CUR
}

    NONE 表示空位，即没有任何棋子在该交叉点上；BLACK 表示黑棋子；WHITE 表示白棋子。BLACK_CUR 和 WHITE_CUR 是服务器返回棋盘数据时才需要区分的标识，表示的含义是最新的下棋棋子。

    对于棋盘，采用的是Cross类型的二维数组组成的，起先，数据内容全部填充 Cross.NONE。

下棋判定

    对于每下的一步棋子，都需要进行一次全盘扫描，以检测当前棋子是否会造成棋盘局势变更（围棋下到后期相对来说错综复杂，暂且没想到是否有更加高效的扫描方式）。

    判定的基本流程如下图所示：

    即先进行边界判定（是否超边界），然后对下的目标位置进行判定（是否已有棋子在交叉点），然后设置目标交叉点并且结算该步的结果（如果该步导致了对方出现死子，将死子全部去除棋盘）。

死子检测

    这一步骤是最重要的步骤之一。

    我的基本逻辑是，取对方色棋子 ObsColor，从（0，0）开始扫描每个棋盘每个位置，如果该位置是 ObsColor，则进行死子判断，判断该棋子连接的ObsColor区域是否有活气（即是否存在Cross.NONE与该片区域相连），如果存在则说明是暂且活棋（并非真正的活棋，围棋的规则是必须存在两个真眼才算活棋），保留该区域棋子。

    采用的算法逻辑是BFS广搜+记忆化搜索。BFS用在查询目标色片区的边界是否为Cross.NONE，存在则可能是活棋或者暂且苟延残喘着活着。如果暂且活着，则将这次BFS搜索的片区在活子确认数组中标记，在下次查询某个棋子所在片区是否活棋的时候，先从活子确认中先查看是否确认活子，确认活子，则跳过本次BFS。下面贴上代码。

public static boolean draw(Cross cross, int row, int col, Cross[][] map) {
    int width = map.length;
    if (row > width || row < 1 || col > width || col < 1 || (map[row - 1][col - 1] != Cross.NONE && cross != Cross.NONE)) return false;
    map[row - 1][col - 1] = cross;
    if (cross != Cross.NONE) check(cross, map);
    return true;
}

/**
 * clear dead : BFS
 * @param cross cur
 * @param map map
 */
private static void check (Cross cross, Cross[][] map) {
    int width = map.length - 1;
    // 遍历 黑色，出现黑色时，查找边缘，只要存在存在空白则安全。bfs查找

    Cross obc = cross == Cross.BLACK ? Cross.WHITE : Cross.BLACK;

    boolean[][] aliveConfirmed = new boolean[map.length][map.length]; // 已被确认为活棋的区域

    for (int i = 0; i < map.length; i++) {
        for (int j = 0; j < map.length; j++) {
            // 为目标色，并且该位置未确认活棋
            if (map[i][j] == obc && !aliveConfirmed[i][j]) {
                // BFS 查找是否存在 NONE 边界
                int len = 0;
                List<KVPair> queue = new ArrayList<>();
                queue.add(new KVPair(i, j));
                List<KVPair> colored = new ArrayList<>();
                colored.add(new KVPair(i, j));

                boolean isDead = true;
                while (len < queue.size()) {
                    // 获取当前的四周，插入到queue
                    KVPair kvPair = queue.get(len);
                    int row = kvPair.k;
                    int col = kvPair.v;

                    // 上
                    if (kvPair.k != 0 && isAliveOrAdd(colored, map, row - 1, col, obc, queue)) {
                        isDead = false;
                        break;
                    }

                    // 下
                    if (kvPair.k != width && isAliveOrAdd(colored, map, row + 1, col, obc, queue)) {
                        isDead = false;
                        break;
                    }

                    // 左
                    if (kvPair.v != 0 && isAliveOrAdd(colored, map, row, col - 1, obc, queue)) {
                        isDead = false;
                        break;
                    }

                    // 右
                    if (kvPair.v != width && isAliveOrAdd(colored, map, row, col + 1, obc, queue)) {
                        isDead = false;
                        break;
                    }

                    len++;
                }

                if (isDead) {
                    // 去除操作
                    colored.forEach(item -> draw(Cross.NONE, item.k + 1, item.v + 1, map));
                } else {
                    // 确认活棋
                    colored.forEach(item -> aliveConfirmed[item.k][item.v] = true);
                }
            }
        }
    }

}

private static boolean isAliveOrAdd(List<KVPair> colored, Cross[][] map, int row, int col, Cross obc, List<KVPair> queue){
    if (isColored(colored, row, col)) return false;

    // 活的，则退出整个大循环
    if (map[row][col] == Cross.NONE) {
        return true;
    }

    // 为己方的，则加入队列，否则对方不进行操作
    if (map[row][col] == obc) {
        queue.add(new KVPair(row, col));
        colored.add(new KVPair(row, col));
    }
    return false;
}

private static boolean isColored(List<KVPair> colored, int row, int col) {
    for (KVPair tmp:colored) {
        if (tmp.k == row && tmp.v == col) return true;
    }
    return false;
}

    实现了这一步，基本核心功能就完成了。如果想要立马测试效果，还可以在控制台绘制一个可视化效果。

public static void printMap(Cross[][] map, Cross now){
    System.out.println();
    int width = map.length - 1;
    System.out.println("O A B C D E F G H I");
    for (int i = 0; i < map.length; i++) {
        System.out.print(i + 1 + " ");
        for (int j = 0; j < map.length; j++) {
            if (map[i][j] == Cross.NONE){
                String tmp = "┼-";
                if (i == 0) tmp = "┬-";
                if (i == width) tmp = "┴-";
                if (j == 0) tmp = "├-";
                if (j == width) tmp = "┤ ";

                if (i == 0 && j == 0) tmp = "┌-";
                if (i == 0 && j == width) tmp = "┐";
                if (i == width && j == 0) tmp = "└-";
                if (i == width && j == width) tmp = "┘";

                System.out.print(tmp);
            } else if (map[i][j] == Cross.BLACK){
                System.out.print("● ");
            } else {
                System.out.print("○ ");
            }
        }
        System.out.println();
    }
    System.out.print((now == Cross.BLACK ? " [ ● ] " : " [ ○ ] ") + " : ");
}

    实例效果图如下（好像还怪不错的）：

GUI界面绘制

    界面绘制用的Java-Swing，相对绘制的比较简单。

    先绘制纵横线条（BASE_HEIGHT为标题栏占用列高，JFrame默认为26像素高度标题栏，BASE_FROM为距离左上角距离）：

g.setColor(Color.lightGray);
for (int i = 1; i <= 9; i++) {
    drawLine(g, BASE_FROM, BASE_FROM * i, BASE_FROM * 9, BASE_FROM * i);
    drawLine(g, BASE_FROM * i, BASE_FROM, BASE_FROM * i, BASE_FROM * 9);
}
g.setColor(Color.black);

private void drawLine(Graphics g, int x1, int y1, int x2, int y2) {
     g.drawLine(x1, BASE_HEIGHT + y1, x2, BASE_HEIGHT + y2);
}

    比较关键的一个处理是当我们点击棋盘落子的逻辑，交叉点附近的半径内规整获取落子映射行列。

addMouseListener(new MouseAdapter() {
    @Override
    public void mouseReleased(MouseEvent e) {
        int x = e.getX() - BASE_FROM;
        int y = e.getY() - BASE_FROM - BASE_HEIGHT;

        int col = (x%BASE_FROM < BASE_FROM / 2) ? (x / BASE_FROM) : (x / BASE_FROM + 1);
        int row = (y%BASE_FROM < BASE_FROM / 2) ? (y / BASE_FROM) : (y / BASE_FROM + 1);
        System.out.printf("[click] row: %d; col: %d;\n", row, col);

        NewClick newClick = NewClick.newInstance(now, row + 1, col + 1);

        Client.sendMsg(os, newClick);

        repaint();
    }
});

网络连接

    上面已经可以实现单机的下棋操作，但是我们是想要有联机的功能的，这样就可以和小伙伴一起愉快的玩耍了。分server和client两个模块开发。client主要的功能是绘制服务器传来的数据内容，有GUI。server端只要进行数据的传递与处理，无需GUI。

    在实际处理过程，为了方便开发，将读写流抽离出一个函数，如果要发送数据直接sendMsg，接收直接recMsg。

    public static void main(String[] args) {
        try {
            Socket socket = new Socket("127.0.0.1", 1919);

            ObjectInputStream oi = new ObjectInputStream(socket.getInputStream());
            ObjectOutputStream os = new ObjectOutputStream(socket.getOutputStream());

            new MainFrame(oi, os);

        } catch (IOException e) {
            e.printStackTrace();
        }

    }

    public static void sendMsg(ObjectOutputStream os, Object obj) {
        try {
            os.writeObject(obj);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static Object recMsg(ObjectInputStream oi){
        try {
            return oi.readObject();
        } catch (ClassNotFoundException | IOException e) {
            e.printStackTrace();
            return null;
        }
    }

    数据的接收可以单独拿出一个线程来获取。

    new Thread(() -> {
            while (true) {
                try {
                    String o = (String) Client.recMsg(oi);
                    map = DataUtil.rawData(o);
                    repaint();
                } catch (Exception e){
                    e.printStackTrace();
                    System.out.println("连接断开");
                    break;
                }
            }
        }).start();

    至此，一个简单的联机围棋就实现啦！

    话说现在网上好像还没有看到联机围棋的实现博文，我这个可以说是首个吗？

    当然了，对于我这个算法还有一点点的缺陷，就是没有判定禁着和反复提子的违规操作，后续如果可能也会做出相应的实现。然后当前还没有最终结算处理，后续也需要来实现结算清点。