A* 尋路算法 Java 完整實現：從核心邏輯到可視化測試

A* (A-Star) 是啟發式圖搜索算法，結合 Dijkstra 保證最短路徑與貪心策略加速收斂，廣泛用於遊戲寻路、機器人規劃、網絡路由。本文提供生產級 Java 實現，含八方向移動、代價模型、開閉集合優化、路徑回溯與可視化測試。

核心數據結構

class Node {
    int x, y;           // 坐標
    Node parent;        // 父節點（回溯用）
    int g;              // 起點到當前實際代價
    int h;              // 當前到終點估算代價（曼哈頓/歐幾里得/切比雪夫）
    int f;              // f = g + h，優先級依據
}

代價模型（八方向）

• 直角移動（上下左右）：COST_STRAIGHT = 10
• 斜向移動：COST_DIAGONAL = 14（≈10×√2）

算法流程

1. 起點入開啟列表（Open List，優先隊列按 f 排序）。
2. 循環取出 f 最小節點：
   • 若為終點 → 回溯構建路徑，成功返回。
   • 生成 8 鄰居節點，跳過不可通行/關閉列表已有者。
   • 若鄰居在開啟列表：比較新 g 值，更小則更新 g/f/parent。
   • 否則計算 g/h/f，設置 parent，加入開啟列表。
3. 當前節點移入關閉列表。
4. 開啟列表為空仍未找到終點 → 無路徑。

關鍵代碼片段

// 核心搜索
private List<Node> search(Node start, Node end) {
    List<Node> path = new ArrayList<>();
    openList.add(start);
    while (!openList.isEmpty()) {
        Node cur = openList.get(0); // 已按 f 排序
        if (cur.x == end.x && cur.y == end.y) {
            buildPath(path, cur);
            return path;
        }
        for (Direction dir : Direction.values()) {
            Node next = cur.neighbor(dir);
            if (!isValid(next) || inCloseList(next)) continue;
            int newG = cur.g + dir.cost;
            int idx = indexInOpenList(next);
            if (idx >= 0) {
                if (newG < openList.get(idx).g) updateNode(openList.get(idx), cur, newG);
            } else {
                openList.add(new Node(next.x, next.y, cur, newG, heuristic(next, end)));
            }
        }
        closeList.add(openList.remove(0));
        Collections.sort(openList, Comparator.comparingInt(n -> n.f));
    }
    return path; // 空 = 失敗
}

啟發式函數選擇

本實現採用曼哈頓距離（忽略障礙物），保證最優路徑。

優化方向

• 開啟列表用 PriorityQueue 替代 List+sort（O(log n) vs O(n log n)）。
• 關閉列表用 boolean[][] 或 HashSet<Long>（x<<32|y）O(1) 查找。
• 跳點搜索 (JPS) 在均勻網格上大幅減少展開節點。
• 雙向 A* 同時從起終點搜索，相遇即停止。

完整可測試 Demo

public class Test {
    public static void main(String[] args) {
        int[][] map = {
            {1,1,1,1,1,1,1,1,1,1},
            {1,1,1,1,0,1,1,1,1,1},
            {1,1,1,1,0,1,1,1,1,1},
            {1,1,1,1,0,1,1,1,1,1},
            {1,1,1,1,0,1,1,1,1,1},
            {1,1,1,1,0,1,1,1,1,1}
        };
        AStar astar = new AStar(map, 6, 10);
        int ret = astar.search(4, 0, 3, 8); // (行,列)
        if (ret == 1) {
            for (int[] row : map) {
                for (int v : row) {
                    System.out.print(v == 1 ? "  " : v == 0 ? "██" : "※");
                }
                System.out.println();
            }
        }
    }
}

輸出將以 ※ 標記最短路徑，██ 為障礙物。

1. 上一篇文章： NIO 進階概念全景：選擇器、文件鎖、內存映射與虛擬內存原理
2. 下一篇文章： Java 數值截斷與四捨五入：類型轉換 vs Math.round 陷阱

Java 相關知識

WTP 1.0 開發 Web Service 實戰：從 Java Class 到 SOAP 服務

五分鐘打造溫度轉換 Web Service — Eclips

結合 XForms 與 Ruby on Rails 開發小型門診管理系統（第 4 部分）：醫生與患者搜尋表單

本系列最終回，完成醫生病患資料編輯表單與患者姓氏搜尋表單，實

MyBatis 查詢部分字段返回 NULL 問題根因分析與解決方案

問題現象 使用 MyBatis 執行 SQL 查詢時，返回對

Java IO 數據流：DataInputStream 基本型別二進制讀取完整指南

核心定位：機器無關的基本型別二進制讀取 DataInputS