每日算法 — 使用java实现连连看：A*搜索与转弯次数优化路径查找

可莉爸爸 AI算法

引言

连连看是考验观察力与路径规划的经典消除游戏。传统人工玩法依赖视觉扫描寻找可通过不超过两次转弯连通的对子，而AI实现则需要系统化的路径搜索算法。本文采用A*搜索求解最优消除路径，核心创新在于将”转弯次数”作为关键成本因子融入启发函数，使搜索优先找到转折少、路径直观的连通方案，更符合人类玩家的视觉习惯。

问题建模

连连看的路径连通规则要求：两个相同图案的格子之间，可以用一条不超过两次转弯的折线连接，且折线只能经过空白格子（已消除的格子视为空白）。

状态空间

  • 地图状态：二维网格，每个格子为图案编号或空白（0）
  • 路径状态：从起点出发，经过一系列直线段到达终点，每段直线沿单一方向延伸，方向改变即构成一次转弯

A*搜索设计

标准A*的代价函数为f = g + h，其中g为已付出代价，h为启发估计。连连看的特殊性在于：

  • g成本：路径长度（经过格子数）+ 转弯次数惩罚（每次转弯额外+5，优先直线路径）
  • h启发：曼哈顿距离 / 直线能力 + 最少转弯估计

通过给转弯赋予高惩罚权重，A*会优先探索直线延伸的路径，仅在必要时才转向。

核心算法设计

转弯感知的A*节点

每个搜索节点不仅记录位置坐标，还记录进入该格子的方向。方向变化时触发转弯计数：

class Node {
    int row, col;      // 位置
    int dir;           // 进入方向 0=上 1=下 2=左 3=右
    int turns;         // 已转弯次数
    int g;             // 实际成本
    int f;             // f = g + h
}

扩展策略：射线式延伸

从当前节点出发，沿当前方向直线延伸直到遇到边界或障碍，每遇到一个可落脚点就生成一个新节点。若延伸方向与进入方向不同，则转弯次数+1。这种”射线式扩展”大幅减少A*的扩展节点数，因为同一直线上的中间点不会被单独加入Open表。

可解性预判断

在启动A之前，先检查起点和终点是否在同一行或同一列且中间无障碍（0转弯解），或是否存在一个中转空白格使两段均为直线（1转弯解）。这些简单情况可在O(n)时间内解决，避免A搜索开销。

Java完整实现

import java.util.*;

/**
 * 基于A*搜索的连连看AI
 * 使用转弯次数优化启发函数，实现最优路径查找
 */
public class AStarLinkLink {

    // 方向定义：上、下、左、右
    private final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private final String[] dirNames = {"UP", "DOWN", "LEFT", "RIGHT"};

    // 地图
    private int[][] board;
    private int rows, cols;

    // 转弯惩罚权重
    private final int TURN_PENALTY = 5;
    private final int MAX_TURNS = 2;

    public AStarLinkLink(int[][] board) {
        this.board = board;
        this.rows = board.length;
        this.cols = board[0].length;
    }

    /**
     * A*搜索节点
     */
    static class Node implements Comparable<Node> {
        int row, col;
        int dir;        // 进入方向，-1表示起点
        int turns;      // 已转弯次数
        int g;          // 实际成本（步数 + 转弯惩罚）
        int h;          // 启发估计
        int f;          // 总评估值
        Node parent;

        Node(int r, int c, int dir, int turns, int g, int h, Node parent) {
            this.row = r; this.col = c; this.dir = dir;
            this.turns = turns; this.g = g; this.h = h;
            this.f = g + h;
            this.parent = parent;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.f, o.f);
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Node)) return false;
            Node n = (Node) o;
            return row == n.row && col == n.col && dir == n.dir && turns == n.turns;
        }

        @Override
        public int hashCode() {
            return Objects.hash(row, col, dir, turns);
        }
    }

    /**
     * 启发函数：曼哈顿距离 + 最少转弯估计
     */
    private int heuristic(int r, int c, int dir, int tr, int tc) {
        int manhattan = Math.abs(r - tr) + Math.abs(c - tc);

        // 如果当前方向已经指向目标，最少0次额外转弯
        // 否则至少1次
        int minExtraTurns = 0;
        if (dir >= 0) {
            boolean aligned = (dir <= 1 && r == tr) || (dir >= 2 && c == tc);
            if (!aligned) minExtraTurns = 1;
        }

        return manhattan + minExtraTurns * TURN_PENALTY;
    }

    /**
     * 判断位置是否在地图内且可通行
     */
    private boolean isPassable(int r, int c, int targetR, int targetC) {
        if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
        // 空白格或目标格可通行
        return board[r][c] == 0 || (r == targetR && c == targetC);
    }

    /**
     * 快速预判断：0转弯或1转弯直连
     */
    private List<int[]> fastCheck(int sr, int sc, int tr, int tc) {
        // 0转弯：同行或同列且中间无阻碍
        if (sr == tr) {
            int min = Math.min(sc, tc), max = Math.max(sc, tc);
            boolean clear = true;
            for (int c = min + 1; c < max; c++) {
                if (board[sr][c] != 0) { clear = false; break; }
            }
            if (clear) {
                List<int[]> path = new ArrayList<>();
                path.add(new int[]{sr, sc});
                for (int c = min + 1; c <= max; c++) path.add(new int[]{sr, c});
                if (sc > tc) Collections.reverse(path);
                return path;
            }
        }
        if (sc == tc) {
            int min = Math.min(sr, tr), max = Math.max(sr, tr);
            boolean clear = true;
            for (int r = min + 1; r < max; r++) {
                if (board[r][sc] != 0) { clear = false; break; }
            }
            if (clear) {
                List<int[]> path = new ArrayList<>();
                path.add(new int[]{sr, sc});
                for (int r = min + 1; r <= max; r++) path.add(new int[]{r, sc});
                if (sr > tr) Collections.reverse(path);
                return path;
            }
        }

        // 1转弯：寻找一个中转空白格
        // 尝试 (sr, tc) 和 (tr, sc)
        int[][] candidates = {{sr, tc}, {tr, sc}};
        for (int[] cand : candidates) {
            int cr = cand[0], cc = cand[1];
            if (board[cr][cc] != 0 && !(cr == sr && cc == sc) && !(cr == tr && cc == tc)) continue;

            // 检查两段是否都畅通
            boolean seg1clear = true, seg2clear = true;

            // 段1: (sr,sc) -> (cr,cc)
            if (sr == cr) {
                for (int c = Math.min(sc, cc) + 1; c < Math.max(sc, cc); c++) {
                    if (board[sr][c] != 0) { seg1clear = false; break; }
                }
            } else if (sc == cc) {
                for (int r = Math.min(sr, cr) + 1; r < Math.max(sr, cr); r++) {
                    if (board[r][sc] != 0) { seg1clear = false; break; }
                }
            } else {
                seg1clear = false;
            }

            // 段2: (cr,cc) -> (tr,tc)
            if (cr == tr) {
                for (int c = Math.min(cc, tc) + 1; c < Math.max(cc, tc); c++) {
                    if (board[cr][c] != 0) { seg2clear = false; break; }
                }
            } else if (cc == tc) {
                for (int r = Math.min(cr, tr) + 1; r < Math.max(cr, tr); r++) {
                    if (board[r][cc] != 0) { seg2clear = false; break; }
                }
            } else {
                seg2clear = false;
            }

            if (seg1clear && seg2clear) {
                List<int[]> path = new ArrayList<>();
                // 构建段1
                if (sr == cr) {
                    int min = Math.min(sc, cc), max = Math.max(sc, cc);
                    for (int c = min; c <= max; c++) path.add(new int[]{sr, c});
                } else {
                    int min = Math.min(sr, cr), max = Math.max(sr, cr);
                    for (int r = min; r <= max; r++) path.add(new int[]{r, sc});
                }
                // 构建段2（避免重复中转点）
                if (cr == tr) {
                    int min = Math.min(cc, tc), max = Math.max(cc, tc);
                    int start = (cc == min) ? min + 1 : max - 1;
                    int end = (cc == min) ? max : min;
                    int step = (cc == min) ? 1 : -1;
                    for (int c = start; step > 0 ? c <= end : c >= end; c += step) {
                        path.add(new int[]{cr, c});
                    }
                } else {
                    int min = Math.min(cr, tr), max = Math.max(cr, tr);
                    int start = (cr == min) ? min + 1 : max - 1;
                    int end = (cr == min) ? max : min;
                    int step = (cr == min) ? 1 : -1;
                    for (int r = start; step > 0 ? r <= end : r >= end; r += step) {
                        path.add(new int[]{r, cc});
                    }
                }
                return path;
            }
        }

        return null;
    }

    /**
     * A*搜索主函数：查找从起点到终点的最优路径
     */
    public List<int[]> findPath(int sr, int sc, int tr, int tc) {
        // 预判断快速路径
        List<int[]> fast = fastCheck(sr, sc, tr, tc);
        if (fast != null) return fast;

        // A*搜索
        PriorityQueue<Node> open = new PriorityQueue<>();
        Set<String> closed = new HashSet<>();

        Node start = new Node(sr, sc, -1, 0, 0, heuristic(sr, sc, -1, tr, tc), null);
        open.add(start);

        while (!open.isEmpty()) {
            Node cur = open.poll();
            String key = cur.row + "," + cur.col + "," + cur.dir + "," + cur.turns;
            if (closed.contains(key)) continue;
            closed.add(key);

            // 到达目标
            if (cur.row == tr && cur.col == tc) {
                return reconstructPath(cur);
            }

            // 射线式扩展：沿每个方向直线延伸
            for (int d = 0; d < 4; d++) {
                int extraTurn = (cur.dir == -1 || cur.dir == d) ? 0 : 1;
                int newTurns = cur.turns + extraTurn;
                if (newTurns > MAX_TURNS) continue;

                int nr = cur.row + dirs[d][0];
                int nc = cur.col + dirs[d][1];

                // 沿方向d直线延伸
                while (isPassable(nr, nc, tr, tc)) {
                    int stepCost = 1 + extraTurn * TURN_PENALTY;
                    int newG = cur.g + stepCost;
                    int newH = heuristic(nr, nc, d, tr, tc);
                    Node next = new Node(nr, nc, d, newTurns, newG, newH, cur);

                    String nKey = nr + "," + nc + "," + d + "," + newTurns;
                    if (!closed.contains(nKey)) {
                        open.add(next);
                    }

                    // 到达终点则停止沿此方向延伸
                    if (nr == tr && nc == tc) break;

                    nr += dirs[d][0];
                    nc += dirs[d][1];
                }
            }
        }

        return null; // 无路径
    }

    private List<int[]> reconstructPath(Node node) {
        List<int[]> path = new ArrayList<>();
        while (node != null) {
            path.add(new int[]{node.row, node.col});
            node = node.parent;
        }
        Collections.reverse(path);
        return path;
    }

    /**
     * 查找地图上所有可消除的相同图案对子
     */
    public List<int[]> findAllPairs() {
        List<int[]> pairs = new ArrayList<>();

        for (int r1 = 0; r1 < rows; r1++) {
            for (int c1 = 0; c1 < cols; c1++) {
                if (board[r1][c1] == 0) continue;
                for (int r2 = r1; r2 < rows; r2++) {
                    for (int c2 = 0; c2 < cols; c2++) {
                        if (r1 == r2 && c2 <= c1) continue;
                        if (board[r1][c1] != board[r2][c2]) continue;

                        if (findPath(r1, c1, r2, c2) != null) {
                            pairs.add(new int[]{r1, c1, r2, c2});
                        }
                    }
                }
            }
        }
        return pairs;
    }

    /**
     * 执行消除
     */
    public boolean eliminate(int r1, int c1, int r2, int c2) {
        if (board[r1][c1] == 0 || board[r1][c1] != board[r2][c2]) return false;

        List<int[]> path = findPath(r1, c1, r2, c2);
        if (path == null) return false;

        System.out.println("Eliminating (" + r1 + "," + c1 + ") and (" + r2 + "," + c2 + ")");
        System.out.print("Path: ");
        for (int[] p : path) {
            System.out.print("(" + p[0] + "," + p[1] + ") ");
        }
        System.out.println("(turns: " + countTurns(path) + ")");

        board[r1][c1] = 0;
        board[r2][c2] = 0;
        return true;
    }

    private int countTurns(List<int[]> path) {
        if (path.size() < 3) return 0;
        int turns = 0;
        int prevDir = -1;
        for (int i = 1; i < path.size(); i++) {
            int dr = path.get(i)[0] - path.get(i-1)[0];
            int dc = path.get(i)[1] - path.get(i-1)[1];
            int dir = (dr == -1) ? 0 : (dr == 1) ? 1 : (dc == -1) ? 2 : 3;
            if (prevDir != -1 && prevDir != dir) turns++;
            prevDir = dir;
        }
        return turns;
    }

    /**
     * 打印地图
     */
    public void printBoard() {
        System.out.println("  0 1 2 3 4 5 6 7");
        for (int i = 0; i < rows; i++) {
            System.out.print(i + " ");
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 0) System.out.print(". ");
                else System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * AI自动求解：贪心策略，每次消除找到的第一对
     */
    public void solve() {
        int steps = 0;
        while (true) {
            List<int[]> pairs = findAllPairs();
            if (pairs.isEmpty()) break;

            int[] p = pairs.get(0);
            eliminate(p[0], p[1], p[2], p[3]);
            steps++;
            printBoard();
        }
        System.out.println("Solved in " + steps + " steps.");
    }

    public static void main(String[] args) {
        // 8x8测试地图，数字表示图案类型
        int[][] map = {
            {1, 2, 3, 0, 0, 4, 5, 6},
            {0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 0, 0, 0, 0, 5, 0},
            {0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0},
            {0, 3, 0, 0, 0, 0, 2, 0},
            {0, 0, 0, 0, 0, 0, 0, 0},
            {4, 0, 6, 0, 0, 0, 0, 0}
        };

        AStarLinkLink game = new AStarLinkLink(map);
        System.out.println("Initial board:");
        game.printBoard();
        game.solve();
    }
}

算法复杂度分析

模块 时间复杂度 空间复杂度
快速预判断（0/1转弯） O(rows + cols) O(path)
A*搜索单路径 O(nodes × directions × maxLen) O(nodes)
全图配对检测 O(patterns² × pathSearch) O(pairs)
单次消除决策 O(pathSearch) O(path)

关键设计要点

  1. 射线式扩展：相比逐格扩展，沿方向直线延伸直至障碍，Open表节点数减少为O(turning_points)级别
  2. 转弯成本建模：将人类”喜欢直线路径”的直觉量化为A*成本函数，搜索结果更符合视觉预期
  3. 快速预判断层：优先检查0转弯和1转弯的简单情况，避免对简单路径启动完整的A*搜索
  4. 方向状态编码：节点包含进入方向信息，使转弯次数的计算精确且高效

总结

本文设计的转弯感知A*算法将连连看的路径搜索问题转化为带约束的最短路径问题。通过射线式扩展和转弯惩罚机制，在保证最优性的同时显著降低了搜索空间。读者可以进一步探索将”路径美观度”（如避免贴边、优先对称路径）融入启发函数，使AI的消除路径更接近人类高手的选择习惯。

Tagged with: