더 빠른 길찾기

고전적인 길찾기 방법, ASTAR

그래프 형태의 구조에서 목적지로의 경로를 찾는 방법에는 다익스트라, 벨만-포드 알고리즘 등이 존재합니다. 하지만 이러한 그래프 구조는 실제 MMORPG 게임서버 맵에서 적용하기 쉽지 않기에, 타일 구조로 맵을 변환시켜 길찾기를 시도하고는 합니다.

타일 구조에서의 길찾기 방식 중 가장 대표적이고, 유명하며 간단한 방식이 A-Star 길찾기입니다.
출발지로부터 연결된 모든 인접 노드를 통해 목적지로 탐색해나가며, 탐색하는 노드마다 가중치를 부여해 목적지로 가는 최단 경로를 찾아내는 방식입니다.

ASTAR 구현

ASTAR 구현을 위해서는, 각 타일에 대한 ‘탐색한 정보’를 담을 노드 구조체와, 탐색했던 노드와 탐색할 노드를 담을 컨테이너 자료형 두 개가 필요합니다.

struct TileNodeBase
{
    TileNodeBase()
    {
        parent = nullptr;
        posX = posY = -1;
        h = g = 0;
    }
    TileNodeBase *parent;
    int posX, posY;
    int h;
    int g;
    int f(int multiplierG, int multiplierH) const
    {
        return h * multiplierH + g * multiplierG;
    }

    int GetHeuristicManhatan(int targetX, int targetY)
    {
        return (abs(targetX - posX) + abs(targetY - posY)) * MOVE_COST_DIRECT;
    }
};

위 자료형은 ASTAR 길찾기 시 최단경로 탐색에 사용되는 파라미터인 h, g 와, 이로부터 파생되어 얻어지는 f 값을 포함하고 있습니다.

목적지까지 남은 거리를 h, 출발지로부터의 이동 거리를 g로 계산하고, 이를 기반으로 h와 g에 가중치를 부여하여 f값을 계산한 뒤, 다음에 탐색할 노드는 이 f값이 가장 작은 노드가 됩니다.

ASTAR 시각화

윈도우 GDI API를 사용하여 그리드 방식의 맵 상에서 직접 장애물과 출발지 목적지를 그린 이후, 탐색되어지는 과정을 눈으로 볼 수 있도록 시각화한다면 개발시에도 디버깅에 도움이 되고, 로직의 검증에도 도움이 됩니다.

위와 같은 식으로 장애물을 그린 이후, G와 H가중치를 조절한 이후 탐색 과정을 확인합니다.

이 때, 각 노드마다 G, H, F값을 확인할 수 있도록 한다면 더욱 확실한 검증이 가능합니다.

ASTAR 방식의 한계점

하지만 이러한 ASTAR 길찾기는, 위 예시 이미지에서도 얼핏 확인할 수 있을 정도로, 생성되는 노드 개수가 굉장히 많아질 수밖에 없습니다. 이는 거리가 늘어남에 따라, 더 많은 장애물을 만나게 될 때마다 점점 더 비효율적인 탐색이 되어가는 것을 의미합니다.

따라서 만일 실제 MMORPG 맵 상에서, 이를 타일화 하여 ASTAR로 길찾기를 수행한다면, 제한된 가까운 거리에서는 효율적인 경로가 탐색이 가능하겠지만, 맵의 복잡도에 따라 조금만 멀리 길찾기를 하려고 하면 체감될 정도로 연산 속도가 오래 소요될 것입니다.

효율적인 길찾기 방법, JPS

생성되는 노드 개수가 너무나도 많은 ASTAR 길찾기의 단점을 해결하려면, 노드 개수를 정말 필요한 만큼만 생성해야 합니다. 그렇다면 노드는 ‘흥미로운 위치’에만 생성이 되야 하는 것이고, 이 ‘흥미로운 노드’는 곧 경로의 방향이 틀어질 수 있는 코너를 의미합니다.

이를 한번 더 생각하자면, 방향이 틀어질 수 있는 위치는 가던 방향의 좌우가 장애물로 막혀 있다가 뚫리게 된 위치를 의미합니다. 따라서, 시작하는 위치에서부터 주변 8방향으로 경로에 ‘흥미로운 노드’가 있는지 탐색해 나가는 과정이 필요합니다.

JPS 구현

JPS를 구현하기 위해서는, 노드가 방향성을 띄고 있어야 합니다.
이를 위해서는 부모로부터 자신의 방향을 계산하고, 주변 장애물을 통해 방향성을 읽어낼 수도 있지만, 해당 노드를 만들 때부터 탐색할 노드 방향이 계산될 수 있으므로 그 때 같이 지정해 주는 방식을 택했습니다.

static constexpr UCHAR WAY_NONE = 0x00;
static constexpr UCHAR WAY_ALL = 0xFF;
static constexpr UCHAR WAY_UU = 0x01;
static constexpr UCHAR WAY_UR = 0x02;
static constexpr UCHAR WAY_RR = 0x04;
static constexpr UCHAR WAY_DR = 0x08;
static constexpr UCHAR WAY_DD = 0x10;
static constexpr UCHAR WAY_DL = 0x20;
static constexpr UCHAR WAY_LL = 0x40;
static constexpr UCHAR WAY_UL = 0x80;

struct TileNodeJ : TileNodeBase
{
    TileNodeJ() : TileNodeBase()
    {
        findingWay = WAY_NONE;
        checkingColor = RGB(255, 255, 255);
    }
    UCHAR findingWay;
    DWORD checkingColor;
};

비트단위로 방향성을 구분할 수 있게끔 한다면 1바이트만으로도 이를 관리할 수 있으며, 연산 수행 속도에서도 이점을 가져올 수 있습니다.

bool PathMakeNodeJPS(int x, int y, TileNodeJ *parent, int moveCost, UCHAR findingWay, TileNodeJ **outCreated = nullptr);
bool PathWayCheckUU(int x, int y, TileNodeJ *parent, TileNodeJ **outCreated = nullptr, int moveCostStart = 0, bool justCheckMode = false);
bool PathWayCheckUR(int x, int y, TileNodeJ *parent);
bool PathWayCheckRR(int x, int y, TileNodeJ *parent, TileNodeJ **outCreated = nullptr, int moveCostStart = 0, bool justCheckMode = false);
bool PathWayCheckDR(int x, int y, TileNodeJ *parent);
bool PathWayCheckDD(int x, int y, TileNodeJ *parent, TileNodeJ **outCreated = nullptr, int moveCostStart = 0, bool justCheckMode = false);
bool PathWayCheckDL(int x, int y, TileNodeJ *parent);
bool PathWayCheckLL(int x, int y, TileNodeJ *parent, TileNodeJ **outCreated = nullptr, int moveCostStart = 0, bool justCheckMode = false);
bool PathWayCheckUL(int x, int y, TileNodeJ *parent);

위처럼 8방향별로 장애물 탐색의 위치가 다르고, 타일 인덱스 참조 시 경계값 체크 방식 또한 다르므로 8종류의 함수로 구분하여 호출하도록 개발하였습니다.

JPS 시각화

이 또한 ASTAR 시각화와 동일하게, Windows GDI API를 사용하여 시각화하였습니다.
다만, ASTAR와는 달리 노드별로 방향성에 맞게 ‘흥미로운 노드’를 찾아나가기 위해 벽까지 탐색해나가는 과정이 존재하므로, 탐색이 된 타일은 색을 부여하여 확인할 수 있게 하였습니다.

JPS에서도 ASTAR와 마찬가지로 F값이 가장 작은 노드를 우선적으로 탐색해나가기에, 노드별로 G, H, F값을 확인할 수 있도록 한다면 더욱 완성도 높은 검증 프로그램을 개발할 수 있습니다.

경로의 최적화 : 브레즌햄 직선

타일 시작점으로부터 떨어진 다른 타일까지의 경로를 계산할 때, 이를 직선으로 나타낼 수 있는 방법에는 lerp를 사용하는 방법이 가장 일반적으로 사용되는 간편한 방식이지만, 예전 소수 단위의 계산이 정수 계산보다 확연히 부하가 클 때 주로 사용되던 방법이 한 가지 있습니다.

브레즌햄 직선 로직은, 소수 계산이 없이 그저 덧셈과 뺄셈 만으로 직선의 기울기 방정식을 통해 타일 상에서 직선으로 표시될 수 있는 타일의 경로를 그려줄 수 있는 방법론입니다.

이를 이용하면 다음과 같은 직선 타일 경로를 얻어낼 수 있습니다.

이를 이용한다면, ASTAR는 물론 JPS도 마찬가지로, 타일맵에서 나타나는, 출발지로부터 목적지까지 노드를 그저 잇기만 했을 때 일어나는 8방향 고정 증상을 해결할 수 있습니다.

노란선 : 도착지로부터 parent로 얻어내는 기존 경로 / 빨간선 : 브레즌햄 직선으로 최적화한 경로

JPS vs ASTAR

ASTAR와 JPS를 비교할 때, 그저 JPS가 ‘생성하는 노드가 더 적으므로 효율적이다’ 라고 말하기에는 몇 가지 짚어보아야 할 점이 있기에, 올바른 결론은 아니라고 할 수 있습니다.

우선, JPS는 생성하는 노드는 적을 지 몰라도, 방향의 끝까지 흥미로운 노드를 위해 탐색해나가는 과정이 필요합니다. 이는 물론 노드를 생성하는 것보다 비용은 훨씬 적을 수 있겠지만, 만일 타일맵의 크기가 방대하여 방향의 끝이 매우 멀다면 오히려 독으로 작용할 수 있습니다.

단순히 10칸이 좌우로 떨어진, 장애물 없는 두 위치 사이의 탐색은 10개의 노드를 만드는 ASTAR가, 모든 방향의 맵을 탐색할 지도 모르는 JPS보다 더욱 효율적일 것임을 예측해볼 수 있습니다.

두 번째로, JPS가 ‘흥미로운 노드’로 생성하는 노드의 개수는, 맵의 장애물의 복잡도에 전적으로 달려있습니다. 따라서, 만일 맵의 장애물이 매우 복잡하고 많다면, JPS는 그 장애물을 만날 때마다 흥미로운 노드로서 굉장히 많은 노드를 생성해내게 됩니다. 이 정도가 심해질 수록, ASTAR보다 성능 상 좋다고 말할 수 있는 ‘생성 노드가 적다’라는 장점은 퇴색되게 됩니다.

따라서 길찾기 또한 길을 얼마나 멀리까지 찾게 할 것인지, 맵 구조와 복잡도는 어떻게 되는지에 따라 고민해보아야 할 문제이지만, 일반적으로 JPS가 ASTAR보다 로직 수행 기대 소요시간이 적기 때문에, JPS가 더욱 선호되어 사용될 수 있습니다.

MMORPG의 경우에는, 이러한 길찾기가 필요하다면 JPS로 직접 클라이언트에서 길을 찾도록 할 수도 있겠지만, 웨이포인트들을 배치하여 이 웨이포인트간의 이동으로 구현하면 더욱 효과적이고 안정적인 길찾기를 구현할 수 있기에, 퀘스트 간 자동이동에는 대부분 ‘웨이포인트’ 방식이 사용되는 것을 다양한 게임에서 확인할 수 있습니다.

코드 모음

ASTAR 길찾기 코드

bool TileMap::PathFindAstarNextFrame()
{
    if (openPathsAstar.empty())
    {
        return false;
    }

    // 가장 f 값이 작은 노드를 가져온다
    TileNodeA *currentNode = openPathsAstar.begin()->second;
    openPathsAstar.erase(openPathsAstar.begin());
    // 해당 노드는 closed 리스트에 추가
    closePathsAstar.insert(pair<int, TileNodeA *>(currentNode->f(multiplierG, multiplierH), currentNode));

    if (currentNode->posX == pathEndPoint.x && currentNode->posY == pathEndPoint.y)
    {
        tileNodeEnd = currentNode;
        PathFindOptimize();
        return true;
    }

    // 상단부터 시계방향 자식생성
    // 상단
    if (currentNode->posY > 0 && GetTileStatus(currentNode->posX, currentNode->posY - 1) != -1)
    {
        PathMakeNodeAstar(currentNode->posX, currentNode->posY - 1, currentNode, MOVE_COST_DIRECT);
    }
    // 우상단
    if (currentNode->posX < mapSizeX && currentNode->posY > 0 && GetTileStatus(currentNode->posX + 1, currentNode->posY - 1) != -1)
    {
        PathMakeNodeAstar(currentNode->posX + 1, currentNode->posY - 1, currentNode, MOVE_COST_DIAGONAL);
    }
    // 우측
    if (currentNode->posX < mapSizeX && GetTileStatus(currentNode->posX + 1, currentNode->posY) != -1)
    {
        PathMakeNodeAstar(currentNode->posX + 1, currentNode->posY, currentNode, MOVE_COST_DIRECT);
    }
    // 우하단
    if (currentNode->posX < mapSizeX && currentNode->posY < mapSizeY && GetTileStatus(currentNode->posX + 1, currentNode->posY + 1) != -1)
    {
        PathMakeNodeAstar(currentNode->posX + 1, currentNode->posY + 1, currentNode, MOVE_COST_DIAGONAL);
    }
    // 하단
    if (currentNode->posY < mapSizeY && GetTileStatus(currentNode->posX, currentNode->posY + 1) != -1)
    {
        PathMakeNodeAstar(currentNode->posX, currentNode->posY + 1, currentNode, MOVE_COST_DIRECT);
    }
    // 좌하단
    if (currentNode->posX > 0 && currentNode->posY < mapSizeY && GetTileStatus(currentNode->posX - 1, currentNode->posY + 1) != -1)
    {
        PathMakeNodeAstar(currentNode->posX - 1, currentNode->posY + 1, currentNode, MOVE_COST_DIAGONAL);
    }
    // 좌측
    if (currentNode->posX > 0 && GetTileStatus(currentNode->posX - 1, currentNode->posY) != -1)
    {
        PathMakeNodeAstar(currentNode->posX - 1, currentNode->posY, currentNode, MOVE_COST_DIRECT);
    }
    // 좌상단
    if (currentNode->posX > 0 && currentNode->posY > 0 && GetTileStatus(currentNode->posX - 1, currentNode->posY - 1) != -1)
    {
        PathMakeNodeAstar(currentNode->posX - 1, currentNode->posY - 1, currentNode, MOVE_COST_DIAGONAL);
    }

    return false;
}

JPS 길찾기 코드

bool TileMap::PathFindJPSNextFrame()
{
    if (openPathsJPS.empty())
    {
        return false;
    }

    // 가장 f 값이 작은 노드를 가져온다
    TileNodeJ *currentNode = openPathsJPS.begin()->second;
    openPathsJPS.erase(openPathsJPS.begin());
    // 해당 노드는 closed 리스트에 추가
    closePathsJPS.insert(pair<int, TileNodeJ *>(currentNode->f(multiplierG, multiplierH), currentNode));

    if (currentNode->posX == pathEndPoint.x && currentNode->posY == pathEndPoint.y)
    {
        tileNodeEnd = currentNode;
        PathFindOptimize();
        return true;
    }

    if (currentNode->findingWay & WAY_UU)
    {
        PathWayCheckUU(currentNode->posX, currentNode->posY, currentNode);
    }
    if (currentNode->findingWay & WAY_UR)
    {
        PathWayCheckUR(currentNode->posX, currentNode->posY, currentNode);
    }
    if (currentNode->findingWay & WAY_RR)
    {
        PathWayCheckRR(currentNode->posX, currentNode->posY, currentNode);
    }
    if (currentNode->findingWay & WAY_DR)
    {
        PathWayCheckDR(currentNode->posX, currentNode->posY, currentNode);
    }
    if (currentNode->findingWay & WAY_DD)
    {
        PathWayCheckDD(currentNode->posX, currentNode->posY, currentNode);
    }
    if (currentNode->findingWay & WAY_DL)
    {
        PathWayCheckDL(currentNode->posX, currentNode->posY, currentNode);
    }
    if (currentNode->findingWay & WAY_LL)
    {
        PathWayCheckLL(currentNode->posX, currentNode->posY, currentNode);
    }
    if (currentNode->findingWay & WAY_UL)
    {
        PathWayCheckUL(currentNode->posX, currentNode->posY, currentNode);
    }

    return false;
}

JPS 길찾기 코드 - 노드의 방향성이 위쪽 방향일 경우

// 위쪽으로 가는 체크
bool TileMap::PathWayCheckUU(int x, int y, TileNodeJ *parent, TileNodeJ **outCreated, int moveCostStart, bool justCheckMode)
{
    int checkPosX = x;
    int checkPosY = y - 1;
    int moveCost = moveCostStart + MOVE_COST_DIRECT;
    while (true)
    {
        // 맵밖이라면 끝
        if (checkPosY < 0) {
            break;
        }
        // 장애물이라면 끝
        if (GetTileStatus(checkPosX, checkPosY) == -1) {
            break;
        }
        // 목적지라면 노드생성
        if (pathEndPoint.x == checkPosX && pathEndPoint.y == checkPosY)
        {
            if (justCheckMode) return true;
            return PathMakeNodeJPS(checkPosX, checkPosY, parent, moveCost, WAY_NONE, outCreated);
            // return true;
        }

        // 위쪽을 검색 가능하다면
        if (checkPosY - 1 >= 0)
        {
            /*
             * O.O
             * X@X
             * ...
             */
            UCHAR checkNeedWay = WAY_UU;
            if (checkPosX - 1 > 0 && GetTileStatus(checkPosX - 1, checkPosY) == -1 && GetTileStatus(checkPosX - 1, checkPosY - 1) != -1)
            {
                // 왼쪽위도 검사해 주세요
                checkNeedWay = checkNeedWay | WAY_UL;
            }
            if (checkPosX + 1 < mapSizeX && GetTileStatus(checkPosX + 1, checkPosY) == -1 && GetTileStatus(checkPosX + 1, checkPosY - 1) != -1)
            {
                // 오른쪽위도 검사해 주세요
                checkNeedWay = checkNeedWay | WAY_UR;
            }
            // 노드 생성이 필요한 지점
            if (checkNeedWay != WAY_UU)
            {
                if (justCheckMode) return true;
                return PathMakeNodeJPS(checkPosX, checkPosY, parent, moveCost, checkNeedWay, outCreated);
                // return true;
            }
        }

        // 특이사항 없는 지점이었다
        tileColorMap[checkPosY * mapSizeX + checkPosX] = parent->checkingColor;
        checkPosY--;
        moveCost += MOVE_COST_DIRECT;
    }
    return false;
}

브레즌햄 직선 그리기 코드

void BresenhamLine::CalculatePoints()
{

    int dX = pointEnd_.x - pointStart_.x;
    int dY = pointEnd_.y - pointStart_.y;
    int vX = dX > 0 ? 1 : -1;
    if (dX == 0) vX = 0;
    int vY = dY > 0 ? 1 : -1;
    if (dY == 0) vY = 0;
    dX = abs(dX);
    dY = abs(dY);

    POINT currentPoint;
    points_.clear();

    int x = pointStart_.x;
    int y = pointStart_.y;

    int error = 0;

    if (dX > dY)
    {
        // X축 변위가 더 크다
        for (int count = 1; count <= dX; count ++)
        {
            error += 2*dY;
            if (error > dX)
            {
                error -= 2*dX;
                y += vY;
            }
            x += vX;

            currentPoint.x = x;
            currentPoint.y = y;
            points_.push_back(currentPoint);
        }
    } else
    {
        // Y축 변위가 더 크다
        for (int count = 1; count <= dY; count ++)
        {
            error += 2*dX;
            if (error > dY)
            {
                error -= 2*dY;
                x += vX;
            }
            y += vY;

            currentPoint.x = x;
            currentPoint.y = y;
            points_.push_back(currentPoint);
        }
    }
}