[알고리즘] 최단 거리 | A-Star 알고리즘 (A* algorithm) 구

📍A* 알고리즘이란?

 

 

A* 알고리즘은 최단 거리 알고리즘 중 하나로, 출발 노드에서부터 목표 노드까지 가는 최단 경로를 찾아낸다. 

 

최단 경로 알고리즘 Visualization

https://qiao.github.io/PathFinding.js/visual/

 

---

📍코드 

Node.js

package astar;

public class Node {
    Integer x;
    Integer y;
    Integer startd;
    Integer destd;
    Integer total;

    Node parents;

    public Node(Integer x, Integer y) {
        this.x = x;
        this.y = y;
        parents = null;
    }


}

 

Astar.java

package astar;

import java.util.*;

public class Astar {
    final Integer DEFAULT_COST = 10;
    final Integer DEFAULT_DIAGONAL = 14;

    //상하좌우, 대각선 상좌 상우 하좌 하우
    final Integer XPOS[] = {0, 0, -1, 1, -1, 1, -1, 1 };
    final Integer YPOS[] = {-1, 1, 0, 0, -1, -1, 1, 1 };

    //맵의 크기를 저장하는 변수
    Integer mapX;
    Integer mapY;

    //열린, 닫힌 목록 저장할 변수
    List<Node> open;
    List<Node> close;
    List<Node> block;

    //초기화 할 때 맵 정보를 전달 받아서 출발지와 목적지의 좌표를 변수에 저장
    Integer[][] map;
    Node start;
    Node goal;

    public Astar(Integer[][] map) {
        this.map = map;
        mapX = map[0].length;
        mapY = map.length;

        //열린 목록, 닫힌 목록 초기화
        open = new ArrayList<>();
        close = new ArrayList<>();
        block = new ArrayList<>();

        //출발점, 도착점, 장애물 초기화
        init();
        start.startd = 0;
        start.destd = Math.abs(goal.x - start.x) *10 + Math.abs(goal.y - start.y) *10;
        start.total = start.startd + start.destd;
    }

    void init(){
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if(map[i][j] == 1){
                    System.out.printf("출발점: (%d, %d)", j, i);
                    start = new Node(j, i);
                }

                else if(map[i][j] == 2){
                    System.out.printf("도착점: (%d, %d)", j, i);
                    goal = new Node(j, i);
                }
                else if(map[i][j] == 3){
//                    System.out.printf("장애물: (%d, %d)", j, i);
                    block.add(new Node(j, i));
                }
            }
        }
    }

    public void findPath() {
        // 시작점를 '열린 목록'에 넣는다.
        open.add(start);

        // 열린 목록이 비어 있지 않으면 반복, 리스트가 비어있는지 아닌지 확인은 리스트변수.isEmpty()
        while(!open.isEmpty()) {
            //열린 목록에서 F값이 가장 적은 하나를 가져온다(가져온 노드는 목록에서 삭제)
            open.sort(new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    return o1.total<o2.total ? o1.total:o2.total;
                }
            });

            Node node = open.get(0);
            System.out.printf("\n열린 목록에서 [%d, %d], Total = %d 를 꺼내왔습니다.\n",
                    node.x, node.y, node.total);
            open.remove(0);
            //가져온 노드는 닫힌 목록에 넣어준다.
            close.add(node);

            //만약 가져온 노드가 최종 목적지면, 최종 경로 출력!
            if(goal.x==node.x && goal.y==node.y) {
                printPath(node);
                break;
            }

            else {
                // 가져온 노드의 인접 노드 중 갈 수 있는 노드의 객체를 생성
                // 생성한 노드의 부모 노드를 현재 노드로 지정
                // 생선한 노드의 FGH 계산
                // 생성한 노드를 열린 목록에 넣는다(중복된 노드는 추가 X).
                for (int i = 0; i < 8; i++) {
                    int nx = node.x + XPOS[i];
                    int ny = node.y + YPOS[i];

                    if(nx < 0 || ny <0 || nx > mapX || ny > mapY) continue;
                    if(ifContains(block, nx, ny)) continue;
                    if(ifContains(open, nx, ny) || ifContains(close, nx, ny)) continue;

                    Node newNode = new Node(nx, ny);
                    newNode.parents = node;
                    if(i <= 4) {
                        newNode.startd = node.startd + DEFAULT_COST;
                    }
                    else {
                        newNode.startd = node.startd + DEFAULT_DIAGONAL;
                    }
                    newNode.destd = Math.abs(goal.x - nx)*10 + Math.abs(goal.y - ny)*10;
                    newNode.total = newNode.startd + newNode.destd;

                    addAdjacentNodes(newNode);

                }
            }
        }
    }

    private void printPath(Node node){
        // 특정 노드를 하나 전달 받아서
        // 부모 부모 부모 찾아가서 출발지가 나오면
        // 출발지 부터 출력
        if(node.x == start.x && node.y==start.y){
            for (int i = 0; i < mapX; i++) {
                for (int j = 0; j < mapY; j++) {
                    System.out.print(map[i][j]+ " ");
                }
                System.out.println();
            }
            return;
        }
//        System.out.printf("%d, %d \n", node.x, node.y);
        if(node.x == goal.x && node.y == goal.y);
        else map[node.y][node.x] = 8;
        printPath(node.parents);
    }

    private void addAdjacentNodes(Node node) {
        // 인접노드를 열린 목록에 추가하는데 중복 안되게
        open.add(node);
//        System.out.printf("인접 노드[%d, %d], Total = %d 가 추가되었습니다.\n", node.x, node.y, node.total );
    }

    private boolean ifContains(List<Node> list, Integer x, Integer y){
        for (int i = 0; i < list.size() ; i++) {
            if(list.get(i).x == x && list.get(i).y == y ) return true;
        }
        return false;
    }
}

 

Test.java

package astar;

public class Test {
    public static void main(String[] args) {
    
    //출발점: 1
    //도착점: 2
    //장애물: 3
        Integer[][] map = {
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,3,0,0,0,0},
                {0,0,0,0,0,3,0,0,0,0},
                {0,0,0,0,0,3,0,2,0,0},
                {0,0,0,0,1,3,0,0,0,0},
                {0,0,0,3,3,3,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,0,0,0,0}
        };

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

    }
}

---

실행 결과

 

---

📍참고

https://recall.tistory.com/40