สอนการใช้งาน A* Algorithm ด้วยภาษา Java

A* Algorithm คืออะไร

A (A-Star) Algorithm เป็นอัลกอริธึมที่ใช้สำหรับการค้นหาเส้นทางที่มีประสิทธิภาพที่สุดระหว่างสองจุดในกราฟ โดยพิจารณาทั้งค่า g(n) (ค่าเส้นทางจากจุดเริ่มต้นถึงจุดปัจจุบัน) และ h(n) (ค่าประมาณระยะทางจากจุดปัจจุบันถึงจุดปลายทาง) ซึ่งค่าทั้งสองจะรวมกันเป็น *f(n) = g(n) + h(n)

ขั้นตอนของ A* Algorithm

1. เริ่มต้นจากจุดเริ่มต้น (Start Node) และเพิ่มเข้าไปใน Open List
2. เลือก Node ที่มีค่าฟังก์ชัน f(n) ต่ำที่สุดใน Open List 
3. ย้าย Node ดังกล่าวไปยัง Closed List
4. ตรวจสอบเพื่อนบ้าน (Neighbor Nodes) ของ Node ที่เลือก 
   • หาก Node เพื่อนบ้านยังไม่เคยอยู่ใน Open หรือ Closed List ให้เพิ่มเข้า Open List และคำนวณค่า g(n), h(n) และ f(n)
   • หาก Node เพื่อนบ้านเคยอยู่ใน Open List แต่เส้นทางใหม่ดีกว่า ให้ปรับปรุงค่า g(n), h(n), และ f(n)
5. ทำซ้ำจนกว่าจะถึงเป้าหมาย (Goal Node) หรือ Open List ว่าง 

---

การเขียนโค้ด A* Algorithm ด้วย Java

ตัวอย่างนี้เป็นการหาเส้นทางในกราฟ 2 มิติ (Grid) 

import java.util.*;

class Node implements Comparable<Node> {
    int x, y; 
    int g, h, f; 
    Node parent;

    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public void calculateCosts(Node goal, int gCost) {
        this.g = gCost;
        this.h = Math.abs(goal.x - this.x) + Math.abs(goal.y - this.y); // Manhattan Distance
        this.f = this.g + this.h;
    }

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

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Node) {
            Node other = (Node) obj;
            return this.x == other.x && this.y == other.y;
        }
        return false;
    }
}

public class AStar {
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static List<Node> findPath(int[][] grid, Node start, Node goal) {
        PriorityQueue<Node> openList = new PriorityQueue<>();
        Set<Node> closedList = new HashSet<>();

        start.calculateCosts(goal, 0);
        openList.add(start);

        while (!openList.isEmpty()) {
            Node current = openList.poll();
            if (current.equals(goal)) {
                return reconstructPath(current);
            }

            closedList.add(current);

            for (int[] direction : DIRECTIONS) {
                int newX = current.x + direction[0];
                int newY = current.y + direction[1];

                if (isValid(grid, newX, newY, closedList)) {
                    Node neighbor = new Node(newX, newY);
                    int newG = current.g + 1;

                    if (!openList.contains(neighbor) || newG < neighbor.g) {
                        neighbor.calculateCosts(goal, newG);
                        neighbor.parent = current;

                        if (!openList.contains(neighbor)) {
                            openList.add(neighbor);
                        }
                    }
                }
            }
        }
        return null; // ไม่มีเส้นทางที่หาได้
    }

    private static boolean isValid(int[][] grid, int x, int y, Set<Node> closedList) {
        return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length 
                && grid[x][y] == 0 && closedList.stream().noneMatch(node -> node.x == x && node.y == y);
    }

    private static List<Node> reconstructPath(Node current) {
        List<Node> path = new ArrayList<>();
        while (current != null) {
            path.add(current);
            current = current.parent;
        }
        Collections.reverse(path);
        return path;
    }

    public static void main(String[] args) {
        int[][] grid = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {0, 1, 1, 1, 0},
            {0, 0, 0, 0, 0}
        };

        Node start = new Node(0, 0);
        Node goal = new Node(4, 4);

        List<Node> path = findPath(grid, start, goal);

        if (path != null) {
            for (Node node : path) {
                System.out.printf("(%d, %d) -> ", node.x, node.y);
            }
            System.out.println("Goal");
        } else {
            System.out.println("ไม่พบเส้นทาง");
        }
    }
}

---

คำอธิบายโค้ด

1. Node Class
   ใช้เก็บตำแหน่ง (x, y), ค่า g, h, f และ Node ต้นทาง (parent) 

2. Manhattan Distance
   ใช้เป็น Heuristic Function ในตัวอย่างนี้ 

3. Open List และ Closed List

   • Open List: เก็บ Node ที่กำลังพิจารณา 
   • Closed List: เก็บ Node ที่พิจารณาไปแล้ว 

4. การหาทางเดิน (Pathfinding)

   • ใช้ PriorityQueue เพื่อจัดลำดับ Node ที่มีค่าฟังก์ชัน f(n) ต่ำที่สุด 

5. การสร้างเส้นทาง
   เมื่อพบเป้าหมาย จะสร้างเส้นทางย้อนกลับจาก Node เป้าหมายไปยัง Node เริ่มต้น 

---

ตัวอย่างผลลัพธ์

สำหรับ Grid ด้านบน จุดเริ่มต้น (0, 0) และจุดเป้าหมาย (4, 4)
ผลลัพธ์: 

(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2) -> (3, 2) -> (4, 2) -> (4, 3) -> (4, 4) -> Goal

ปรับแต่งโค้ดเพิ่มเติมเพื่อรองรับกรณีอื่นๆ ได้ตามต้องการ!