230211 AStar 알고리즘

그래프 검색 문제에 사용되는 효율적인 알고리즘

• 목적지까지의 예상 거리(heuristic cost)를 고려하여 경로를 탐색
• 경로 탐색 과정에서 각 노드의 총 비용(total cost)을 계산하여, 목적지에 도달할 때까지 가장 낮은 비용을 갖는 노드를 선택

  예상 거리 - 현재 위치에서 목적지까지의 거리를 추정한 값
  총 비용 - 현재 노드에서 출발하여 목적지까지의 실제 거리(cost so far)와 예상 거리를 합산한 값

어떤 지점 A에서 B까지 가는 경우

우선 A에 인접한 지역들을 OpenList(조사해야하는 지점)에 추가

이후 A에 인접한 OpenList의 항목들 중에 가장 예상거리가 작은 지점을 가져와서 다시 그곳의 인접한 지역을 OpenList에 추가하는 과정을 목적지에 도달할 때까지 반복

예시

class AData {

    int x;
    int y;
    int pIndex;
    int g; // 시작지점으로부터 온 거리
    int h; // 목적지까지의 거리
    int f; // 기대 거리

    public AData(int x, int y, int pIndex, int g, int h) { // OpenList에 추가할 때 사용할 값

        this.x = x;
        this.y = y;
        this.pIndex = pIndex;
        this.g = g;
        this.h = h;
        this.f = g + h; // F값은 G+H 이므로 따로 입력하지 않도록 했다.

    }

}

public class AStar {

    static ArrayList<AData> openList = new ArrayList<>();

    static ArrayList<AData> closeList = new ArrayList<>();

    static ArrayList<int[]> path = new ArrayList<>(); // 마지막에 경로를 저장할 곳이다.

    private static void aStarFind(int startx, int starty, int endx, int endy, int nowIndex) {
        closeList.add(new AData(startx, starty, -1, 0, 0)); // 시작지점을 바로 탐색할 수 있도록 CloseList에 미리 넣어준다.

        while (closeList.get(nowIndex).x != endx || closeList.get(nowIndex).y != endy) { // 목적지에 도착할때까지 반복한다.
            for (int way = 0; way < 4; way++) { // 상하좌우 순서
                int nowx = closeList.get(nowIndex).x;
                int nowy = closeList.get(nowIndex).y;

                boolean flag = false; // 해당 위치가 열린, 닫힌리스트중에 있는가 확인할때 쓴다.

                if (way == 0)
                    nowy++;
                else if (way == 1)
                    nowy--;
                else if (way == 2)
                    nowx--;
                else if (way == 3)
                    nowx++;

                flag = flag(nowx, nowy, flag);
                flag = findShorterRoute(nowIndex, nowx, nowy, flag);

                if (!flag) { // 열린, 닫힌리스트에 없다면 열린리스트에 새로 추가해줌
                    openList.add(new AData(nowx, nowy, nowIndex, closeList.get(nowIndex).g + 1,
                            Math.abs(endx - nowx) + Math.abs(endy - nowy)));
                }

            }
            if (openList.isEmpty())
                break;
            nowIndex = findNext(nowIndex);
        }
        printRoute(nowIndex);
    }

    private static boolean flag(int nowx, int nowy, boolean flag) {
        for (int i = 0; i < closeList.size(); i++) {
            if (closeList.get(i).x == nowx && closeList.get(i).y == nowy) {
                flag = true;
            }
        }
        return flag;
    }

    private static int findNext(int nowIndex) {
        int fTemp = openList.get(0).f;
        int index = 0;

        for (int i = 0; i < openList.size(); i++) {
            if (openList.get(i).f < fTemp) {
                fTemp = openList.get(i).f;
                index = i;

            } else if (openList.get(i).f == fTemp) { // F값이 동일하다면 H값이 작은것을 택한다.
                if (openList.get(i).h < openList.get(index).h) {
                    index = i;
                }
            }

        }

        closeList.add(openList.get(index));

        openList.remove(index); // CloseList에 탐색할 위치를 넣어주고 OpenList에서 지운다.

        nowIndex++;
        return nowIndex;
    }

    private static void printRoute(int nowIndex) {
        while (nowIndex != -1) { // 도착지점부터 역순으로 되짚어간다
            int[] pathtemp = { closeList.get(nowIndex).x, closeList.get(nowIndex).y };
            path.add(pathtemp);// + " " + CloseList.get(nowIndex).y);
            nowIndex = closeList.get(nowIndex).pIndex;
        }

        while (!path.isEmpty()) { // 되짚어간 경로를 다시 원래대로 출력한다.
            System.out.println(path.get(path.size() - 1)[0] + " " + path.get(path.size() - 1)[1]);
            path.remove(path.size() - 1);
        }
    }

    private static boolean findShorterRoute(int nowIndex, int nowx, int nowy, boolean flag) {
        for (int i = 0; i < openList.size(); i++) {
            if (openList.get(i).x == nowx && openList.get(i).y == nowy) {
                flag = true;
                if (openList.get(i).g > closeList.get(nowIndex).g + 1) {
                    openList.set(i, new AData(nowx, nowy, nowIndex, closeList.get(nowIndex).g + 1, openList.get(i).h));
                }
            }
        }
        return flag;
    }
}