2021-01-13

에이스타(A*)

에이스타(A*)는 다익스트라처럼 우선순위 큐를 이용한 방법으로 구현한다. 차이점이라면 최단 거리 대신에 가중치를 쓴다는 점이다.
written by

Introduction

앞서 미로의 출발 지점부터 도착 지점까지 가는 방법으로 DFS와 BFS를 알아봤다. DFS, BFS는 미로를 탐색하는 좋은 방법이지만 단순한 탐색 방법이다. 하지만 미로의 출발 지점과 도착 지점이 주어진다면 그 정보를 적극적으로 활용하여 탐색을 할 수 있다.

먼저 다익스트라(Dijkstra) 알고리즘을 생각해 보자. 이 방식으로 출발 지점으로부터 현재까지의 최단 거리를 알 수 있고, 도착 지점이 주어졌으므로 현재 지점에서 도착 지점까지의 거리를 더 이용할 수 있다. 이 둘을 적절히 섞는다면 대략적으로 도착 지점에 가까운 방향으로 탐색을 진행할 수 있다. 이것이 에이스타(A*)의 원리이다.

Algorithm

에이스타(A*)는 다익스트라처럼 우선순위 큐를 이용한 방법으로 구현한다. 차이점이라면 최단 거리 대신에 가중치를 쓴다는 점이다. 먼저, 가중치의 개념은 다음과 같다. 일반적으로 설명할 때 많이 쓰는 가중치 개념이다.

  • 이동한 경로에 대한 가중치: 이동한 경로를 각각에 대해서 유클리디안 거리로 계산.
  • 남은 거리에 대한 가중치: 남은 경로에 대해서 맨해튼 거리로 계산.

이제 가중치를 기준으로 하는 우선순위 큐를 이용하여 다음의 순서대로 진행한다. 출발 지점은 남은 거리에 대한 가중치만 기록한다. 나머지 지점은 무한대를 나타내는 임의의 가중치를 기록한 후에 우선순위 큐에 출발 지점을 넣는다.

  • 우선순위 큐의 헤드에 있는 지점에서 방문이 가능한 지점들을 방문한다.
  • 해당 지점에 기록된 가중치가 없으면 해당 지점까지의 가중치를 기록한다.
  • 해당 지점에 기록된 가중치가 있으면 가중치가 작을 경우만 가중치를 기록한다.
  • 가중치가 갱신된 경우에만 해당 지점과 해당 지점에 기록된 가중치를 우선순위 큐에 넣는다.
  • 큐에서 헤드를 제거한다.
  • 큐가 빌 때까지 위의 과정을 반복한다.

결국 다익스트라의 확장이라고 생각하면 편할 거 같다.

Kotlin Scratch Code

import java.util.*
import kotlin.math.abs

// 0이면 통로, 1이면 벽으로 간주하는 이차원 배열이다.
// 가로는 열(col), 세로는 행(row), maze[row][col]로 위치를 표시한다.
val maze = listOf(
    listOf(0, 1, 0, 0, 1, 0),
    listOf(0, 0, 0, 1, 0, 1),
    listOf(0, 1, 0, 0, 0, 0),
    listOf(1, 0, 0, 1, 0, 1),
    listOf(1, 0, 0, 1, 0, 0),
)

// 해당 maze[row][col] 지점의 방문 여부를 의미한다.
val visit = listOf(
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
    booleanArrayOf(false, false, false, false, false, false),
)

// row 좌표는 -1은 북쪽, +1은 남쪽, col 좌표는 -1은 서쪽, +1은 동쪽을 의미한다.
// 세 번째 값은 현재 지점으로부터의 가중치이다.
// 수직과 수평은 10, 대각선에 대해서는 14의 가중치를 적용하도록 하였다.
val directions = listOf(
    Triple(-1, 0, 10),
    Triple(-1, 1, 14),
    Triple(0, 1, 10),
    Triple(1, 1, 14),
    Triple(1, 0, 10),
    Triple(1, -1, 14),
    Triple(0, -1, 10),
    Triple(-1, -1, 14),
)

// 방문한 것으로 표시한 시작 지점과 도착 지점을 배열에 저장한다.
val location = intArrayOf(0, 0).also { visit[it[0]][it[1]] = true }
val goal = intArrayOf(4, 5)

// 각 지점에 대한 가중치를 저장하는 이차원 배열.
// 출발 지점으로부터 경로에 해당하는 directions 가중치를 모두 더해서 첫 번째 값에 저장한다.
// 해당 지점에서 도착 지점까지의 수직과 수평 거리의 10배를 곱해서 두 번째 값에 저장한다.
// 출발 지점의 directions 가중치는 없으므로 0을 저장해서 초기화한다.
val heuristic = List(maze.size) { i ->
    List(maze[i].size) { j -> intArrayOf(Int.MAX_VALUE - 1000, abs(goal[0] - i) * 10 + abs(goal[1] - j) * 10) }
}.apply { this[location[0]][location[1]][0] = 0 }

// 시작 지점을 삽입하여 Maze 탐색 큐를 초기화한다.
val mazeQueue = PriorityQueue<Triple<Int, Int, Int>>(compareBy { it.third }).apply {
    add(
        Triple(
            location[0],
            location[1],
            heuristic[location[0]][location[1]][0] + heuristic[location[0]][location[1]][1]
        )
    )
}

// 큐가 다 비어도 도착 지점을 찾지 못하면 경로가 없다.
while (mazeQueue.isNotEmpty()) {

    // 큐에서 탐색 중인 위치를 현재 위치로 저장하고 큐에서 제거한다.
    location[0] = mazeQueue.element().first
    location[1] = mazeQueue.element().second
    mazeQueue.poll()

    // 맵을 출력한다.
    printMaze(maze, location)

    // 현재 위치가 목적 지점이라면 탐색을 종료한다.
    if (location.contentEquals(goal)) {
        break
    }

    // 시계 방향으로 방문이 가능한지 판별한다.
    directions.forEach { direction ->

        // 방문할 지점이 맵을 벗어나지 않는지 확인한다.
        if (location[0] + direction.first >= 0 && location[0] + direction.first < maze.size && location[1] + direction.second >= 0 && location[1] + direction.second < maze[0].size) {

            // 방문할 지점이 벽이 아니고, 방문한 적이 없는 경우에만 큐에 삽입하도록 한다.
            if (maze[location[0] + direction.first][location[1] + direction.second] == 0 && !visit[location[0] + direction.first][location[1] + direction.second]) {

                // 도착 지점까지의 가중치는 항상 일정하므로 비교하지 않고, 출발 지점으로부터의 가중치만 Dijkstra 알고리즘처럼 비교한다.
                if (heuristic[location[0] + direction.first][location[1] + direction.second][0] > heuristic[location[0]][location[1]][0] + direction.third) {

                    // 가중치가 작아졌으므로 가중치를 갱신한다.
                    heuristic[location[0] + direction.first][location[1] + direction.second][0] =
                        heuristic[location[0]][location[1]][0] + direction.third

                    // 출발 지점으로부터의 가중치와 도착 지점까지의 가중치를 합산해서 이것으로 우선순위를 따지도록 하여 큐에 삽입하고 방문하였다고 표시한다.
                    mazeQueue.add(
                        Triple(
                            location[0] + direction.first,
                            location[1] + direction.second,
                            heuristic[location[0] + direction.first][location[1] + direction.second][0] + heuristic[location[0] + direction.first][location[1] + direction.second][1]
                        )
                    )
                    visit[location[0]][location[1]] = true
                }
            }
        }
    }
}

// 벽은 X, 통로는 빈 문자, 현재 위치는 *로 표시하여 미로를 출력하는 함수.
fun printMaze(maze: List<List<Int>>, location: IntArray) {
    Array(maze.size) { i ->
        Array(maze[i].size) { j ->
            when {
                maze[i][j] == 0 -> "[ ]"
                else -> "[X]"
            }
        }
    }.apply {
        this[location[0]][location[1]] = "[*]"
    }.run {
        println("------------------")
        forEach { row ->
            row.forEach { cell ->
                print(cell)
            }.run { println("") }
        }
        println("------------------")
    }
}

Result

------------------
[*][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
------------------
------------------
[ ][X][ ][ ][X][ ]
[ ][*][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
------------------
------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][*][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
------------------
------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][*][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][ ]
------------------
------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][*][X]
[X][ ][ ][X][ ][ ]
------------------
------------------
[ ][X][ ][ ][X][ ]
[ ][ ][ ][X][ ][X]
[ ][X][ ][ ][ ][ ]
[X][ ][ ][X][ ][X]
[X][ ][ ][X][ ][*]
------------------
2021 © Cinntiq's Studio