[주저리] 사천성 게임의 경로탐색

넷마블 사천성!

사천성(Shishen-sho)

한번쯤은 즐겨본 적이 있을 "사천성" 이라는 게임이다.

이 게임에서 가장 주된 기능이라고 하면 단연코 "경로탐색" 알고리즘일 것이다.

처음 문제에 접근할 땐 단순히 "두번이상 꺾이지 않는 경로만 탐색하면 되겠지!" 라고 생각했었는데,

이게 점차 갈수록 최적경로가 아닌 문제와 더불어 소거되는 경로를 표시하려면 좌표를 저장해야 하는데 그러한 사소한 문제부터 걸리기 시작한다.

일단 문제를 해결하기 위해서 접근가능한 방법은 아래와 같다.

1. DFS

2. BFS

3. Heuristic Path Finding

1. DFS(깊이-우선 탐색)

가장 간단하고 직관적이다. 스택 혹은 재귀를 이용하여 다음 탐색할 대상을 찾고 거의 한쪽방향의 끝이 나올떄까지 주변을 탐색하다가, 해가 없을 경우

다시 다른 방향으로 찾아가서 결국 해를 찾아낸다.

장점 : 메모리 사용량이 적고, 코드가 직관적이라 이해하기 쉽다.

단점 : 해를 찾긴 하는데, 그 해가 최적이라고 보장할 수 없다.

2. BFS(너비-우선 탐색)

깊이우선 탐색과 유사한 듯 하지만, 전혀 다른 방법으로 탐색한다. Queue를 이용하여 구현하고, Queue의 앞부분에 있는 노드를 탐색하고, 새로 확장되는 노드들을

뒤에 추가함으로써, 돌을 호수에 던질 때 물결이 생기는 것 처럼 넓게 탐색해 나간다.

장점 : 최적의 해를 찾을 수 있다. 경로가 최적이라고 보장이 됨.

단점 : 메모리 사용량이 깊이-우선 탐색에 비해 많음.

익히 알고있는 내용이긴 한데, 실제로 사천성 게임에서 이러한 알고리즘간의 차이는 "거의 없다" 라고 봐도 무방하다.

가장 많은 블록이 배열되는 40x40 이라고 쳐도 160개의 Vertex로 구성이 되기 때문에 메모리 사용량이나 속도가 사실 큰 차이가 날 수 없다.

그렇다면 최적의 경로를 찾을 수 있는 너비우선 탐색을 사용하는것이 더 현명한 선택일 수 있다.

다만, 그대로 사용하면 알 수 없는 함정에 빠지게 된다(2번 이내로 꺾임을 어떻게 판단할 것인가?)

3. Heuristic Path Finding

간단하게 설명하자면, Heuristic이란 일종의 "가중치" 라고 생각하면 된다. 예를 들어 한 노드가 확장될 때 상/하/좌/우 4개의 노드가 새로 추가가 된다면,

이 노드들의 가중치를 비교해서 가장 적은 비용을 선택하는 기준을 만들기 위한 방법이라고 생각하면 된다.

가장 많이 사용되는 가중치 측정 방법은 L1 Distance(맨하탄 거리) 이다.

경로탐색은 시작점(x1,y1) 과 도착점(x2, y2)가 있는데, 시작점에서부터의 거리(G)와, 도착점까지 남은 거리(H) 를 합산한 결과를 토대로

F(Fitness) = G + H

의 식으로 판단한다. G값과 H값은 동일한 공식인 |x1-x2| + |y1-y2| 로 구할 수 있다.

이런식으로 목표지점까지 최단비용을 지닌 노드들을 따라서 경로탐색을 하는 알고리즘이다.

장점 : 최단경로가 보장됨. 같은 최적의 해를 찾는 너비우선 탐색에 비해 비교횟수 및 탐색횟수가 현저히 적다.

단점 : 구현하기 까다로움. 휴리스틱을 이해하고 구현해야함.

---

그래서 사천성에서 사용하는 경로탐색을 구현하기 위해서는 일반적인 경로탐색 알고리즘을 사용해서는 바로 해결할 수 없다.

적어도 몇가지 조건을 걸어서 알고리즘을 구현해야 한다.

1. DFS를 사용할 경우

꺾임 횟수를 측정하며 탐색해야 한다. 초기 꺾임(Turning) 값을 가지고 탐색을 시작하며, 꺾임이 판단되었을 때(기존 방향과 다를 경우) Turning값을 증가시킨다.

이 값이 3 이상일 경우에 탐색을 종료하고 다시 Backtracking을 시도한다(3이상인 경우 그 경로는 버린다는 소리)

2. BFS를 사용할 경우

일반적인 Queue를 사용해서는 원하는 값을 얻을 수 없다. Priority-Queue를 사용한다.

우선순위 큐를 구성하고, 이전 노드의 방향을 기억해두고 같은 방향인 경우를 우선적으로 탐색하고, 방향이 꺾이는 노드의 경우 가중치를 높게 주어

나중에 탐색될 수 있도록 한다. 사실 BFS로 구현해본 적은 없지만 일반 Queue를 사용했을 때 방향 판단기준이 잡히지 않아서 실패했던 기억이 있다.

왜냐면 각 노드가 일정한 방향으로 탐색되는 것이 아니라 중구난방으로 퍼져나가기 때문이다.

만약 Priority Queue를 사용한다면 괜찮은 결과를 얻을 수 있지 않을까 생각해본다(다만 이렇게 구현하면 DFS와 다를바가 없지 않을까 생각되기도 한다)

3. Heuristic Path Finding

주로 A* 알고리즘을 이용해서 구현을 한다. 다른 휴리스틱 알고리즘들이 많긴 하지만 구현도 매우 까다로운 편이고 사천성에서 그 짧은 경로를 찾기위해서

너무 오버헤드가 큰 기분도 든다. 하지만 Astar 특성상 다른 path finding 알고리즘보단 최적화된 알고리즘인만큼 오히려 더 빠르게 탐색이 가능할 수 있다.

A star의 경우 "depends on the heuristic" 이라고 되어있는만큼 휴리스틱 알고리즘(어떤걸 adjacent list에 넣을거고 말거고.. 하는 로직) 에 큰 영향이 있다는걸 알 수 있다.

그 외 익히 알고있는.. Dijkstra 나 Floyd 같은 경우는 거의 n^2, n^3 에 가까운 속도를 보인다.

A* 알고리즘을 사용한다면, 노드를 확장하고 F값을 기준으로 다음 노드를 선택하게 되는데 이 때 T값이라는 기준을 추가하여 선택하게 해야 한다.

현재 방향과 다른 방향으로 확장하고자 한다면 큰 비용값을 매기고, 같은 방향이라면 적은 비용을 매겨서 탐색을 진행한다.

한 예로 https://github.com/phishman3579/java-algorithms-implementation 에서 구현한 알고리즘을 살펴보자.

public List<Node> findPath() {
    openList.add(initialNode);
    while (!isEmpty(openList)) {
        Node currentNode = openList.poll();
        closedSet.add(currentNode);
        if (isFinalNode(currentNode)) {
            return getPath(currentNode);
        } else {
            addAdjacentNodes(currentNode);
        }
    }
    return new ArrayList<Node>();
}

private void addAdjacentLowerRow(Node currentNode) {
    int row = currentNode.getRow();
    int col = currentNode.getCol();
    int lowerRow = row + 1;
    if (lowerRow < getSearchArea().length) {
        checkNode(currentNode, col, lowerRow, getHvCost());
    }
}

private void checkNode(Node currentNode, int col, int row, int cost) {
    Node adjacentNode = getSearchArea()[row][col];
    if (!adjacentNode.isBlock() && !getClosedSet().contains(adjacentNode)) {
        if (!getOpenList().contains(adjacentNode)) {
            adjacentNode.setNodeData(currentNode, cost);
            getOpenList().add(adjacentNode);
        } else {
            boolean changed = adjacentNode.checkBetterPath(currentNode, cost);
            if (changed) {
                // Remove and Add the changed node, so that the PriorityQueue can sort again its
                // contents with the modified "finalCost" value of the modified node
                getOpenList().remove(adjacentNode);
                getOpenList().add(adjacentNode);
            }
        }
    }
}

결국 여기에서 중요한건 addAdjacentRow 와 checkNode의 역할이다.

Node의 cost를 측정하고, 그 cost를 기반으로 구성된 Priority Queue에서 어떤 노드를 먼저 탐색할지를 결정한다.

근데, 사천성에서는 이 값이 고정된 값을 사용하게되면 꺾임을 찾을 수가 없을 것이다.

꺾임을 측정하려면 어떻게 해야할까?

간단하다. 노드 3개만 있으면 꺾임의 여부를 알 수 있다.

2개로는 꺾임을 판단할 수 없다.

가로로 2개

ㅁㅁ 

세로로 2개

ㅁ

ㅁ

가 있다고 한들 이게 꺾여서 꺾인건지, 원래 저런건지 알 수 없지만 3개가 존재한다면 얘기는 틀려진다.

가로로 2개 + 세로로 1개

ㅁㅁ

  ㅁ

세로로 2개 + 가로로 1개

ㅁ

ㅁㅁ

즉, 3개의 ROW 좌표가 같거나 COL좌표가 같은때는 "꺾임이 없다."

하지만 ROW 혹은 COL 좌표가 1개라도 틀린 경우는 "꺾임이 발생한다." 라는 뜻이 된다.

이는 adjacentNode를 추가하는 부분에 적용할 수 있다.

아래는 간단하게 현재 node와 추가할 next 노드를 받아서 방향전환이 일어났는지를 확인하는 로직이다.

private boolean isTurned(Node current, Node next) {
    if (current.getParent() != null) {
        Node prev = current.getParent();
        return (!((prev.getCol() == current.getCol()) && (current.getCol() == next.getCol()) || (prev.getRow() == current.getRow()) && (current.getRow() == next.getRow())));
    } else {
        return false;
    }
}

이를 checkNode시에 적용하게 되면

private void checkNode(Node currentNode, int col, int row, int cost) {
    Node adjacentNode = getSearchArea()[row][col];
    if (!adjacentNode.isBlock() && !getClosedSet().contains(adjacentNode)) {
        if (!getOpenList().contains(adjacentNode)) {
            // turn 체크(cost 측정위함)
            if (currentNode.getParent() != null) {
                if (isTurned(currentNode, adjacentNode)) {
                    cost += getTurnCost();
                }
            }
            adjacentNode.setNodeData(currentNode, cost);
            getOpenList().add(adjacentNode);
        } else {
            boolean changed = adjacentNode.checkBetterPath(currentNode, cost);
            if (changed) {
                // Remove and Add the changed node, so that the PriorityQueue can sort again its
                // contents with the modified "finalCost" value of the modified node
                getOpenList().remove(adjacentNode);
                getOpenList().add(adjacentNode);
            }
        }
    }
}

대략적으로 위와 같은 모습이 된다.

원래라면 hvCost만 가져가는 반면에, 사천성을 목적으로 작성한 탐색기법엔 위와같이 isTurned(방향전환 여부)를 체크한 뒤 node data를 세팅해준다.

저렇게되면 기존 로직과는 다르게 방향전환이 될법한 예정(adjacent) 노드들은 cost가 올라가게 되어 Queue의 맨 뒤로 밀리게 된다.

그렇다면 기존 로직과 차이점을 한번 확인해보자.

이전(위 github의 로직 그대로) 탐색 로직을 그대로 써본 것이다.

위는 node map의 상태

S : 시작점

E : 목표점

- : 빈 공간

| : 장애물(block)

위 상태로 탐색을 하게되면 최단거리를 찾기위해 벽을 따라서 계단현상(stair)이 나타나는 경로를 찾게된다.

당연히 이런 경우는 꺾임이 많게되어 실제로 사용할 수 없는 경로가 된다.

그럼 이제 앞서 작성한 위 코드를 적용해서 확인해보자.

보다시피 아주 이상적인 경로대로 찾게 된다.

꺾임이 발생하는 경우는 최악의 수로 보고, 왠만하면 가던 경로대로 탐색하려 하기 때문에 위에 나타났던 계단현상이 없어진 것이다.

여러 케이스를 확인해봤는데 생각했던대로 잘 동작하는 것을 확인할 수 있었다.

AStar를 적용하려면 방향전환의 여부를 확인하는 것과 그때의 가중치를 어떻게 주는지에 따라 길찾기의 성패가 갈리게 될 것 같다.

(이래서 depends on heuristic 이다 ㅎㅎ;)

---

사천성게임의 알고리즘을 검색해도 마땅한 정보를 찾을 수 없을 것이다.

(소스가 있어도 수정이 꼭 필요한 정도..)

사실 알고리즘을 통째로 올릴까 했지만, 사천성 알고리즘을 고민하면서 꽤 논리적인 생각을 하기에 좋았다는 경험이어서 올리지 않으려 한다.

참고할 블로그를 링크하는 것이 더 나을 것 같다.

블로그는 참고하되, 본인이 직접 구현해보는 것이 실력향상에 더 좋을 것 같다.

- 참고할 블로그들 -

거의 80%의 소스가 존재하는 블로그

소스가 100% 있지만 C언어로 구현이 되어있고 일반적인 사천성에 적용하려면 수정을 많이해야할 블로그(콘솔에서 구현한 사천성이라)

마찬가지로 소스가 100% 있지만, 본인이 사용할 부분을 추려내야할 블로그