A* 알고리즘 (A star) - 최단 거리 알고리즘

A* 알고리즘 (최단 거리 알고리즘)

: 그래프 탐색과 최단 경로 찾기를 위한 알고리즘으로, 다익스트라 알고리즘과 휴리스틱(Heuristic) 탐색을 결합한 방식

 

각 경로의 비용을 평가하는 F 값을 기반으로 탐색을 수행

---

• 열린 목록: 내가 앞으로 갈 수 있는 노드들
• 닫힌 목록: 내가 이미 갔던 노드들
• 노드: 각 좌표
• 부모 노드: 이동할 때 현재 노드의 이전 노드
• F: G + H
• G: 출발지에서 얼마나 떨어져 있나 (상, 하, 좌, 우 = 10, 대각선 = 14)
  
• H: 목적지까지 얼마나 이동해야 하나(대각선 이동과 장애물은 고려하지 않는다.)

시작점을 열린 목록에 넣는다.
    열린 목록이 비어있지 않으면 반복
        열린 목록에서 F값이 가장 적은 하나를 가져온다. (가져온 노드는 목록에서 삭제)
        가져온 노드는 닫힌 목록에 넣어준다.
        만약 가져온 노드가 최종 목적지면 최종 경로 출력
        그렇지 않으면
            가져온 노드의 인접 노드 중 갈 수 있는 노드를 열린 목록에 넣는다.
            F, G, H 계산
            인접 노드의 부모 노드를 현재 노드로 지정
            만약 인접 노드가 열린 목록에 있다면 F가 더 작은 걸 넣기

 

---

예제

시작 지점 : (2, 3)

도착 지점 : (6, 3)

벽 : (4, 1), (4, 2), (4, 3),  (4, 4),  (4, 5) 

 

 

 

1. 시작 지점 (2, 3)을 열린 목록에 넣는다.

---

 

2. 현재 열린 목록에서 F 값이 가장 적은 노드를 꺼낸 후 열린 목록에서 삭제하고, 닫힌 목록에 넣는다.

 

현재 열린 목록에는 (2, 3) 밖에 없기 때문에 (2, 3)을 꺼내서 닫힌 목록에 넣어준다. 

---

 

3. (2, 3)의 인접한 노드 중 갈 수 있는 노드를 열린 목록에 넣는다.

 

(2, 3)을 기준으로 인접한 노드들은 (1, 2), (2, 2), (3, 2), (1, 3), (3, 3), (1, 4), (2, 4), (3, 4) 

인접한 노드을 열린 목록에 넣어주고 F, G, H 값을 계산해준다.

 

---

 

4. 현재 열린 목록 중에서 F 값이 가장 적은 노드(3, 3)를 꺼낸 후 열린 목록에서 삭제하고, 닫힌 목록에 넣는다.

 

현재 열린 목록에서 F 값이 가장 적은 건 (3, 3) 이기 때문에 (3, 3)을 꺼내서 닫힌 목록에 넣어준다.

닫힌 목록은 노란색으로 칠해준다.

---

 

5. (3, 3)의 인접한 노드 중 갈 수 있는 노드를 열린 목록에 넣는다.

 

(3, 3)을 기준으로 인접한 노드들 중 갈 수 있는 노드는 (2, 2), (3, 2), (2, 4), (3, 4) 

나머지 노드들은 F, G, H 값을 계산해주고, 모든 노드들이 이미 열린 목록에 있기 때문에 F값을 비교해준다.

모든 노드가 이전의 F값이 더 작기 때문에 업데이트하지 않고 그대로 놔둔다.

 

4번과 동일

---

 

6. 현재 열린 목록 중에서 F 값이 가장 적은 노드를 꺼낸 후 열린 목록에서 삭제하고, 닫힌 목록에 넣는다.

(3, 2)와 (3, 4)가 54로 제일 적은 F 값을 가진다.

리스트 안에 있는 순서대로 (3, 2)를 가져온다.

 

---

 

7. (3, 2)의 인접한 노드 중 갈 수 있는 노드를 열린 목록에 넣는다.

 

(3, 2)을 기준으로 인접한 노드들 중 갈 수 있는 노드는 (2, 1), (3, 1), (2, 2)

(2, 1)과 (3, 1)은 F, G, H 값을 계산해준다.

 

(2, 2)는 이미 열린 목록에 있기 때문에 F 값을 비교해준다.

이전의 F값이 더 작기 때문에 업데이트하지 않고 그대로 놔둔다.

---

 

 

위와 같은 작업을 반복하면 된다.

 

8. F 값 가장 적은 노드(3, 4)를 꺼낸 후 닫힌 목록에 넣고, 인접 노드 계산 후 열린 목록에 넣기

 

---

 

9. F 값 가장 적은 노드(2, 2)를 꺼낸 후 닫힌 목록에 넣고, 인접 노드 계산 후 열린 목록에 넣기

 

여기서 (2, 1)의 F 값이 원래 88이었는데, (2, 2)를 기준으로 계산하면 G 값이 20으로 줄어들어서 80이 된다.

(2, 1)은 원래 열린 목록에 들어가있기 때문에 F 값을 다시 계산하고 부모를 바꿔서 다시 열린 목록에 넣어준다.

 

---

 

 

 

열심히 반복 중

 

 

 

 

10. 현재 열린 목록 중에 F 값이 가장 적은 노드를 꺼내고, 해당 노드가 도착 지점이면 반복을 종료한다.

 

위의 과정을 반복해서 채우면 이렇게 된다.

닫힌 목록에 도착 지점이 들어왔으니 해당 반복을 종료한다.

---

 

 

11. 닫힌 목록의 제일 마지막 노드(도착 지점)부터 부모 노드를 따라가면서 경로를 출력한다.

 

(6, 3)의 부모 노드는 (6, 2)이고, (6, 2)의 부모는 (5, 1)이고, (5, 1)의 부모는 (4, 0)이다.

이런 식으로 부모 노드를 따라가면서 출력하고, null이 나오면 출력을 종료한다.

 

 

 

최종 경로는

(2, 3), (3, 2), (3, 1), (4, 0), (5, 1), (6, 2), (6, 3)

 

=> 열린 목록에서 F값이 가장 적은 노드가 여러 개 있을 때, 어떤 걸 선택하느냐에 따라서 최단 경로가 달라질 수 있다.

 

---

1. Node 클래스

노드 객체들을 저장하는 클래스

public class Node {
    private int x;
    private int y;
    private int f;
    private int g;
    private int h;
    private Node parent;

    // 생성자
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
        this.f = 0;
        this.g = 0;
        this.h = 0;
        this.parent = null;
    }

    public Node(int x, int y, int f, int g, int h, Node parent) {
        this.x = x;
        this.y = y;
        this.f = f;
        this.g = g;
        this.h = h;
        this.parent = parent;
    }

    // getter, setter 생략
}

 

 

---

2. Astar 클래스

DEFAULT_COST : 상, 하, 좌, 우 비용

DEFAULT_DIAGONAL_COST : 대각선 비용

 

 

생성자 메소드

map을 매개변수로 받아서 맵과 맵의 사이즈를 저장한다.

시작 지점과 도착 지점을 저장하고, 열린 목록과 닫힌 목록을 초기화시켜준다.

public Astar(int[][] map) {
    this.map = map;
    this.rowSize = map.length;
    this.colSize = map[0].length;

    for (int i = 0; i < rowSize; i++) {
        for (int j = 0; j < colSize; j++) {
            if (map[i][j] == 1) {
                this.start = new Node(i, j);
            }
            if (map[i][j] == 2) {
                this.goal = new Node(i, j);
            }
        }
    }

    openList = new ArrayList<>();
    closeList = new ArrayList<>();
}

 

 

findPath 메소드

최단 경로를 찾는 메소드

 

열린 목록이 비어있지 않으면 반복한다.

열린 목록에서 F값이 가장 적은 노드를 가져온 후 가져온 노드는 열린 목록에서 삭제하고, 닫힌 목록에 넣어준다. 

 

만약 가져온 노드가 최종 목적지면 최종 경로를 출력한다.

그렇지 않으면 가져온 노드의 인접 노드 중 갈 수 있는 노드를 열린 목록에 넣는다.

인접 노드를 현재 노드로 지정하고, F, G, H를 계산한다. 

G : 부모 G + 가중치(가로세로면 10, 대각선이면 14)
H : (abs(목적지 x -  노드 x) + abs(목적지 y - 노드 y)) * 가중치(10)
F : G + H

 

만약 가져온 노드의 인접 노드 중 갈 수 있는 노드가 열린 목록에 있다면 F가 더 작은 걸 넣는다.

 

public void findPath() {
    openList.add(start);
    while (!openList.isEmpty()) {
        // F값 기준으로 오름차순 정렬
        Collections.sort(openList, (a, b) -> a.getF() - b.getF());
        // 열린 목록에서 F값이 가장 적은 하나를 가져온다.
        Node current = openList.get(0);
        // 가져온 노드는 목록에서 삭제
        openList.remove(0);
        // 가져온 노드는 닫힌 목록에 넣어준다.
        closeList.add(current);

        // 만약 가져온 노드가 최종 목적지면
        if (current.getX() == goal.getX() && current.getY() == goal.getY()) {
            // 최종 경로 출력
            printPath(current);
            return;
        }
        // 가져온 노드의 인접 노드 중 갈 수 있는 노드를 열린 목록에 넣는다.
        else {
            int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};
            int[] dy = {0, 0, -1, 1, -1, -1, 1, 1};

            for (int i = 0; i < 8; i++) {
                int nx = current.getX() + dx[i];
                int ny = current.getY() + dy[i];
                // map을 벗어나지 않고 장애물이 아니라면
                if (nx >= 0 && nx < rowSize && ny >= 0 && ny < colSize && map[nx][ny] != 3) {
                    // F, G, H 계산
                    int g = current.getG() + (i < 4 ? DEFAULT_COST : DEFAULT_DIAGONAL_COST);
                    int h = (Math.abs(nx - goal.getX()) + Math.abs(ny - goal.getY())) * DEFAULT_COST;
                    int f = g + h;

                    // 노드 객체 생성
                    Node newNode = new Node(nx, ny, f, g, h, current);

                    // 닫힌 목록에 있으면 작업 X
                    if(closeList.contains(newNode)) {
                        continue;
                    }
                    // 열린 목록에 있으면 F값을 비교해서 F, G, Parent 초기화
                    boolean check = false;
                    for (Node n : openList) {
                        if (n.getX() == nx && n.getY() == ny) {
                            if (n.getF() > f) {
                                n.setF(f);
                                n.setG(g);
                                n.setParent(current);
                            }
                            check = true;
                            break;
                        }
                    }
                    // 어디에도 없으면 열린 목록에 추가
                    if (!check) {
                        openList.add(newNode);
                    }
                }
            }

        }

    }
}

 

 

printPath 메소드

최단 경로를 출력한다. 

 

매개변수로 현재 지점(도착 지점)을 넘겨 받는다.

리스트에 string으로 담고, 도착 지점부터 출발해서 시작 지점 방향으로 탐색한다.

인덱스 0번째에 넣어주면서 경로 노드를 앞쪽에 넣어준다. (이러면  reverse 정렬을 안 해도 된다.)

 

만약 시작 지점이면 s, 도착 지점이면 g, 벽이면 ■, 경로면 *, 아무것도 아니면 □를 출력한다.

private void printPath(Node current) {
    List<String> path = new ArrayList<>();
    while (current != null) {
        String str = "[" + current.getX() + ", " + current.getY() + "]";
        path.add(0, str);
        current = current.getParent();
    }
    System.out.println(path);

    for (int i = 0; i < rowSize; i++) {
        System.out.print(" ");
        for (int j = 0; j < colSize; j++) {
            if (map[i][j] == 1) {
                System.out.print("s");
            } else if (map[i][j] == 2) {
                System.out.print("g");
            } else if (map[i][j] == 3) {
                System.out.print("■");
            } else if (path.contains("[" + i + ", " + j + "]")) {
                System.out.print("*");
            } else {
                System.out.print("□");
            }
            System.out.print(" ");
        }
        System.out.println();
    }
}

 

 

 

전체 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Astar {
    final int DEFAULT_COST = 10;
    final int DEFAULT_DIAGONAL_COST = 14;

    int[][] map;

    int rowSize;
    int colSize;

    Node start;
    Node goal;

    List<Node> openList;
    List<Node> closeList;

    public Astar(int[][] map) {
        this.map = map;
        this.rowSize = map.length;
        this.colSize = map[0].length;

        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                if (map[i][j] == 1) {
                    this.start = new Node(i, j);
                }
                if (map[i][j] == 2) {
                    this.goal = new Node(i, j);
                }
            }
        }

        openList = new ArrayList<>();
        closeList = new ArrayList<>();
    }

    public void findPath() {
        openList.add(start);
        while (!openList.isEmpty()) {
            Collections.sort(openList, (a, b) -> a.getF() - b.getF());
            // 열린 목록에서 F값이 가장 적은 하나를 가져온다.
            Node current = openList.get(0);
            // 가져온 노드는 목록에서 삭제
            openList.remove(0);
            // 가져온 노드는 닫힌 목록에 넣어준다.
            closeList.add(current);

            // 만약 가져온 노드가 최종 목적지면
            if (current.getX() == goal.getX() && current.getY() == goal.getY()) {
                // 최종 경로 출력
                printPath(current);
                return;
            }
            // 가져온 노드의 인접 노드 중 갈 수 있는 노드를 열린 목록에 넣는다.
            else {
                int[] dx = {-1, 1, 0, 0, -1, 1, -1, 1};
                int[] dy = {0, 0, -1, 1, -1, -1, 1, 1};

                for (int i = 0; i < 8; i++) {
                    int nx = current.getX() + dx[i];
                    int ny = current.getY() + dy[i];
                    // map을 벗어나지 않고 장애물이 아니라면
                    if (nx >= 0 && nx < rowSize && ny >= 0 && ny < colSize && map[nx][ny] != 3) {
                        // F, G, H 계산
                        int g = current.getG() + (i < 4 ? DEFAULT_COST : DEFAULT_DIAGONAL_COST);
                        int h = (Math.abs(nx - goal.getX()) + Math.abs(ny - goal.getY())) * DEFAULT_COST;
                        int f = g + h;

                        // 노드 객체 생성
                        Node newNode = new Node(nx, ny, f, g, h, current);

                        // 닫힌 목록에 있으면 작업 X
                        if(closeList.contains(newNode)) {
                            continue;
                        }
                        // 열린 목록에 있으면 F값을 비교해서 F, G, Parent 초기화
                        boolean check = false;
                        for (Node n : openList) {
                            if (n.getX() == nx && n.getY() == ny) {
                                if (n.getF() > f) {
                                    n.setF(f);
                                    n.setG(g);
                                    n.setParent(current);
                                }
                                check = true;
                                break;
                            }
                        }
                        // 어디에도 없으면 열린 목록에 추가
                        if (!check) {
                            openList.add(newNode);
                        }
                    }
                }

            }

        }
    }


    private void printPath(Node current) {
        List<String> path = new ArrayList<>();
        while (current != null) {
            String str = "[" + current.getX() + ", " + current.getY() + "]";
            path.add(0, str);
            current = current.getParent();
        }
        System.out.println(path);

        for (int i = 0; i < rowSize; i++) {
            System.out.print(" ");
            for (int j = 0; j < colSize; j++) {
                if (map[i][j] == 1) {
                    System.out.print("s");
                } else if (map[i][j] == 2) {
                    System.out.print("g");
                } else if (map[i][j] == 3) {
                    System.out.print("■");
                } else if (path.contains("[" + i + ", " + j + "]")) {
                    System.out.print("*");
                } else {
                    System.out.print("□");
                }
                System.out.print(" ");
            }
            System.out.println();
        }
    }
}

 

---

3. Main 클래스 (출력 결과)

 

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        // 1은 출발지, 2는 도착지, 3은 장애물
        int[][] map = {
                {0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 3, 0, 0, 0},
                {0, 0, 0, 0, 3, 0, 0, 0},
                {0, 0, 1, 0, 3, 2, 0, 0},
                {0, 0, 0, 0, 3, 0, 0, 0},
                {0, 0, 0, 0, 3, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0}
        };

        Astar astar = new Astar(map);
        astar.findPath();
    }
}