사용자 도구

사이트 도구


kb:robusttracingalgorithm

Robust Tracing Algorithm

Smart Moves: Intelligent Path-Finding에 언급된 Robust Tracing을 구현해 보자.

동작

샘플

아직 여러 가지로 모자란 소스지만, 개념 잡는 정도에는 도움이 되지 않을까나.

pathfinder.h

//////////////////////////////////////////////////////////////////////////////
/// \file PathFinder.h
/// \author excel96
/// \date 2004.11.30
//////////////////////////////////////////////////////////////////////////////
 
#ifndef __PATHFINDER_H__
#define __PATHFINDER_H__
 
#include <list>
 
//////////////////////////////////////////////////////////////////////////////
/// \class MapProxy
/// \brief PathFinder 클래스와 맵 관련 클래스 간의 의존성을 줄이기 위해
/// 만든 프락시 클래스.
//////////////////////////////////////////////////////////////////////////////
 
class MapProxy
{
public:
    /// \brief 해당 좌표가 막혀있는지의 여부를 반환한다.
    /// \param x X 좌표
    /// \param y Y 좌표
    /// \return bool 막혀있는 경우 true, 뚫려있다면 false를 반환한다.
    virtual bool isBlocked(int x, int y) const = 0;
};
 
 
//////////////////////////////////////////////////////////////////////////////
/// \class PathFinder
/// \brief Bresenham 알고리즘과 Contour Tracing (Theo Pavlidis) 알고리즘을 
/// 적당히 섞은 길찾기 객체.
///
/// A* 알고리즘과는 달리, 가장 짧은 길을 선택하지도 않고, 반드시 도착하는
/// 것도 보장하지 않는다. 한마디로 무책임!
//////////////////////////////////////////////////////////////////////////////
 
class PathFinder
{
private:
    class Utility;
    friend class Utility;
 
    /// 검색을 위한 방향 선언
    enum Direction
    {
        DIR_LEFT = 0,       ///< 9시 방향
        DIR_LEFTDOWN,       ///< 7시 반 방향
        DIR_DOWN,           ///< 6시 방향
        DIR_RIGHTDOWN,      ///< 4시 반 방향
        DIR_RIGHT,          ///< 3시 방향
        DIR_RIGHTUP,        ///< 1시 반 방향
        DIR_UP,             ///< 12시 방향
        DIR_LEFTUP,         ///< 10시 반 방향
        DIR_MAX             ///< 배열을 위한 맥스값
    };
 
    /// 길찾기 객체의 동작 모드
    enum MoveMode
    {
        MOVE_MODE_NORMAL = 0, ///< 일반 모드. 직선으로 움직인다.
        MOVE_MODE_TRACE       ///< 장애물 가장자리 따라가기 모드.
    };
 
    /// \struct POINT
    /// \brief 2D 좌표 객체
    typedef struct POINT
    {
        int x;
        int y;
        POINT(int _X=0, int _Y=0) : x(_X), y(_Y) {}
        bool operator == (const POINT& rhs) const { return x == rhs.x && y == rhs.y; }
        bool operator != (const POINT& rhs) const { return x != rhs.x || y != rhs.y; }
    } POINT;
 
    typedef std::list<POINT> PATH;
 
    POINT     m_Goal;        ///< 목표 위치
    POINT     m_Current;     ///< 현재 위치
    MoveMode  m_MoveMode;    ///< 현재 동작 모드
    int       m_TraceDir;    ///< 이전 턴에서 따라간 방향
    PATH      m_DirectPath;  ///< 현재 위치에서 목표 위치까지의 일직선 패스
 
 
public:
    /// \brief 생성자
    PathFinder();
 
    /// \brief 소멸자
    ~PathFinder();
 
 
public:
    /// \brief 길찾기를 초기화한다.
    /// \param sx 시작 지점 X 좌표
    /// \param sy 시작 지점 Y 좌표
    /// \param gx 목표 지점 X 좌표
    /// \param gy 목표 지점 Y 좌표
    void init(int sx, int sy, int gx, int gy);
 
    /// \brief 목표 지점에 도달하기 위해 가야하는 다음 좌표를 반환한다.
    /// \param x 다음 X 좌표를 집어넣을 변수
    /// \param y 다음 Y 좌표를 집어넣을 변수
    /// \param map 맵 정보를 알려줄 프락시 객체
    /// \return bool 다음 좌표를 찾았다면 true를 반환하고, 찾지 못했다면
    /// false를 반환한다.
    bool next(int& x, int& y, const MapProxy& map);
 
 
private:
    /// 복사 생성자는 사용 금지
    PathFinder(const PathFinder&) {}
 
    /// 대입 연산자는 사용 금지
    const PathFinder& operator = (const PathFinder&) { return *this; }
};
 
#endif

pathfinder.cpp

//////////////////////////////////////////////////////////////////////////////
/// \file PathFinder.cpp
/// \author excel96
/// \date 2004.11.30
//////////////////////////////////////////////////////////////////////////////
 
#include "PCH.h"
#pragma hdrstop
 
#include "PathFinder.h"
#include <assert.h>
 
//////////////////////////////////////////////////////////////////////////////
/// \class PathFinder
//////////////////////////////////////////////////////////////////////////////
 
class PathFinder::Utility
{
public:
    /// \brief 선분이 주어진 좌표를 포함하는지의 여부를 반환한다.
    /// \param path 선분
    /// \param pt 좌표
    /// \return bool 좌표를 포함하는 경우 true
    static bool ptInPath(
        const PATH& path, const POINT& pt)
    {
        return std::find(path.begin(), path.end(), pt) != path.end();
    }
 
    /// \brief 선분 안에 포함되는 좌표들을 리스트로 반환한다.
    /// \param x1 시작 지점 X 좌표
    /// \param y1 시작 지점 Y 좌표
    /// \param x2 목표 지점 X 좌표
    /// \param y2 목표 지점 Y 좌표
    /// \param path 좌표를 집어넣을 리스트 객체
    static void bresenham(int x1, int y1, int x2, int y2, PATH& path)
    {
        static const int OFFSET = 0x8000;
        static const int SHIFT = 16;
 
        bool yLonger = false;
        int shortLen = y2 - y1;
        int longLen = x2 - x1;
 
        if (abs(shortLen) > abs(longLen))
        {
            std::swap(shortLen, longLen);
            yLonger = true;
        }
 
        int decInc = longLen == 0 ? 0 : (shortLen << SHIFT) / longLen;
 
        if (yLonger)
        {
            if (longLen > 0)
            {
                longLen += y1;
                for (int j=OFFSET+(x1<<SHIFT); y1 <= longLen; ++y1)
                {
                    path.push_back(POINT(j >> SHIFT, y1));
                    j += decInc;
                }
            }
            else
            {
                longLen += y1;
                for (int j=OFFSET+(x1<<SHIFT); y1 >= longLen; --y1)
                {
                    path.push_back(POINT(j >> SHIFT, y1));
                    j -= decInc;
                }
            }
        }
        else
        {
            if (longLen > 0)
            {
                longLen += x1;
                for (int j=OFFSET+(y1<<SHIFT); x1 <= longLen; ++x1)
                {
                    path.push_back(POINT(x1, j >> SHIFT));
                    j += decInc;
                }
            }
            else
            {
                longLen += x1;
                for (int j=OFFSET+(y1<<SHIFT); x1 >= longLen; --x1)
                {
                    path.push_back(POINT(x1, j >> SHIFT));
                    j -= decInc;
                }
            }
        }
    }
 
    /// \brief 시작 지점에서 목표 지점으로 직선 경로로 움직이기 위해 다음에
    /// 가야하는 지점의 좌표를 반환한다.
    /// \param from 시작 지점
    /// \param to 목표 지점
    /// \param path 좌표를 집어넣을 리스트 객체
    static void bresenham(const POINT& from, const POINT& to, PATH& path)
    {
        bresenham(from.x, from.y, to.x, to.y, path);
    }
 
    /// \brief 시작 지점에서 목표 지점으로 직선 경로로 움직이기 위해 다음에
    /// 가야하는 지점의 좌표를 반환한다.
    /// \param from 시작 지점
    /// \param to 목표 지점
    /// \return POINT 다음 지점의 좌표
    static POINT getNextBresenhamPoint(const POINT& from, const POINT& to)
    {
        assert(from != to);
 
        PATH path;
        bresenham(from, to, path);
        assert(!path.empty());
 
        PATH::const_iterator b = path.begin();
        PATH::const_reverse_iterator e = path.rbegin();
 
        return *b == from ? *(++b) : *(++e);
    }
 
    /// \brief 해당 좌표에서 주어진 방향으로 움직였을 경우에 도착하는 좌표를
    /// 반환한다.
    /// \param from 기준이 되는 좌표
    /// \param dir 방향
    /// \return POINT 움직인 후의 좌표
    static POINT getNextPoint(const POINT& from, int dir)
    {
        static const POINT DirMoveMask[DIR_MAX] =
        {
            POINT(-1,  0), // DIR_LEFT
            POINT(-1,  1), // DIR_LEFTDOWN
            POINT( 0,  1), // DIR_DOWN
            POINT( 1,  1), // DIR_RIGHTDOWN
            POINT( 1,  0), // DIR_RIGHT
            POINT( 1, -1), // DIR_RIGHTUP
            POINT( 0, -1), // DIR_UP
            POINT(-1, -1)  // DIR_LEFTUP
        };
 
        return POINT(from.x + DirMoveMask[dir].x, from.y + DirMoveMask[dir].y);
    }
 
    /// \brief 주어진 방향을 해당 옵셋만큼 튼 다음, 오버플로우 및
    /// 언더플로우를 보정한 방향을 반환한다.
    /// \param dir 기준이 되는 방향
    /// \param offset 틀 방향. 예를 들어 1 이라면 시계 반대 방향으로 한 스텝,
    /// 0 이라면 원래 방향, -1 이라면 시계 방향으로 한 스텝이다.
    /// \return int 보정한 방향
    static int adjust(int dir, int offset)
    {
        dir += offset;
        if (dir < 0) dir += DIR_MAX;
        else if (dir >= DIR_MAX) dir -= DIR_MAX;
        return dir;
    }
 
    /// \brief 두 좌표 간의 상대적인 방향을 구한다.
    /// \param from 기준이 되는 좌표
    /// \param to 방향을 잴 좌표
    /// \return int 방향 (DIR_LEFT ~ DIR_LEFTUP)
    static int getRelativeDir(const POINT& from, const POINT& to)
    {
        if (from.x < to.x)
        {
            if (from.y < to.y)      return DIR_RIGHTDOWN;
            else if (from.y > to.y) return DIR_RIGHTUP;
            else                    return DIR_RIGHT;
        }
 
        if (from.x > to.x)
        {
            if (from.y < to.y)      return DIR_LEFTDOWN;
            else if (from.y > to.y) return DIR_LEFTUP;
            else                    return DIR_LEFT;
        }
 
        if (from.y < to.y)      return DIR_DOWN;
        else if (from.y > to.y) return DIR_UP;
 
        return DIR_MAX;
    }
};
 
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 생성자
//////////////////////////////////////////////////////////////////////////////
PathFinder::PathFinder()
: m_MoveMode(MOVE_MODE_NORMAL), m_TraceDir(DIR_MAX)
{
}
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 소멸자
//////////////////////////////////////////////////////////////////////////////
PathFinder::~PathFinder()
{
}
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 길찾기를 초기화한다.
/// \param sx 시작 지점 X 좌표
/// \param sy 시작 지점 Y 좌표
/// \param gx 목표 지점 X 좌표
/// \param gy 목표 지점 Y 좌표
//////////////////////////////////////////////////////////////////////////////
void PathFinder::init(int sx, int sy, int gx, int gy)
{
    m_Goal.x    = gx;
    m_Goal.y    = gy;
    m_Current.x = sx;
    m_Current.y = sy;
    m_MoveMode  = MOVE_MODE_NORMAL;
 
    // 시작 지점과 목표 지점을 잇는 직선 좌표들을 구해둔다.
    m_DirectPath.clear();
    Utility::bresenham(sx, sy, gx, gy, m_DirectPath);
}
 
//////////////////////////////////////////////////////////////////////////////
/// \brief 목표 지점에 도달하기 위해 가야하는 다음 좌표를 반환한다.
/// \param x 다음 X 좌표를 집어넣을 변수
/// \param y 다음 Y 좌표를 집어넣을 변수
/// \param map 맵 정보를 알려줄 프락시 객체
/// \return bool 다음 좌표를 찾았다면 true를 반환하고, 찾지 못했다면
/// false를 반환한다.
//////////////////////////////////////////////////////////////////////////////
bool PathFinder::next(int& x, int& y, const MapProxy& map)
{
    static const int SearchSequences[DIR_MAX][DIR_MAX] =
    {
        { DIR_LEFT, DIR_LEFTDOWN, DIR_LEFTUP, DIR_DOWN, DIR_UP, DIR_RIGHTDOWN, DIR_RIGHTUP, DIR_RIGHT, }, // DIR_LEFT
        { DIR_LEFTDOWN, DIR_DOWN, DIR_LEFT, DIR_RIGHTDOWN, DIR_LEFTUP, DIR_RIGHT, DIR_UP, DIR_RIGHTUP, }, // DIR_LEFTDOWN
        { DIR_DOWN, DIR_RIGHTDOWN, DIR_LEFTDOWN, DIR_RIGHT, DIR_LEFT, DIR_RIGHTUP, DIR_LEFTUP, DIR_UP, }, // DIR_DOWN
        { DIR_RIGHTDOWN, DIR_RIGHT, DIR_DOWN, DIR_RIGHTUP, DIR_LEFTDOWN, DIR_UP, DIR_LEFT, DIR_LEFTUP, }, // DIR_RIGHTDOWN
        { DIR_RIGHT, DIR_RIGHTUP, DIR_RIGHTDOWN, DIR_UP, DIR_DOWN, DIR_LEFTUP, DIR_LEFTDOWN, DIR_LEFT, }, // DIR_RIGHT
        { DIR_RIGHTUP, DIR_UP, DIR_RIGHT, DIR_LEFTUP, DIR_RIGHTDOWN, DIR_LEFT, DIR_DOWN, DIR_LEFTDOWN, }, // DIR_RIGHTUP
        { DIR_UP, DIR_LEFTUP, DIR_RIGHTUP, DIR_LEFT, DIR_RIGHT, DIR_LEFTDOWN, DIR_RIGHTDOWN, DIR_DOWN, }, // DIR_UP
        { DIR_LEFTUP, DIR_LEFT, DIR_UP, DIR_LEFTDOWN, DIR_RIGHTUP, DIR_DOWN, DIR_RIGHT, DIR_RIGHTDOWN, }  // DIR_LEFTUP
    };
 
    // 이미 목표 지점에 도착한 상태라면 그냥 리턴
    if (m_Current == m_Goal)
        return false;
 
    POINT NextPt;
 
    //------------------------------------------------------------------------
    // 일반 모드. 
    // 목표 지점까지 브레센헴 알고리즘을 이용해 직선을 그어서 다음 좌표를 
    // 구한 다음, 움직인다.
    //------------------------------------------------------------------------
    if (m_MoveMode == MOVE_MODE_NORMAL)
    {
        NextPt = Utility::getNextBresenhamPoint(m_Current, m_Goal);
 
        if (!map.isBlocked(NextPt.x, NextPt.y))
        {
            m_Current = NextPt;
            x = m_Current.x;
            y = m_Current.y;
            return true;
        }
        else
        {
            // 직선으로 갈 수 없다. 즉 장애물과 충돌했다.
            // 그러므로 장애물 가장자리 따라가기 모드로 들어가야 한다.
 
            // 직선으로 갈 수 없다면, 어느 방향으로 가야할지를 정해야 한다.
            // 문제는 어느 방향으로 가야하는지 결정하기가 애매하다는 것이다.
            // 최선의 방향으로 가는 게 좋다고 생각할 수도 있지만, 이럴 경우
            // 한번 못가는 길은 영원히 못 간다. 그에 반해 랜덤을 이용하면
            // 좀 돌아가는 경향이 있기는 하나, 어쨌든 목표 지점까지는 
            // 도착할 확률이 높다.
            //int OriginalDir = getRelativeDir(m_Current, NextPt);
            int OriginalDir = rand() % DIR_MAX;
 
            for (int i=1; i<DIR_MAX; i++)
            {
                int dir = SearchSequences[OriginalDir][i];
                NextPt = Utility::getNextPoint(m_Current, dir);
 
                if (!map.isBlocked(NextPt.x, NextPt.y))
                {
                    m_MoveMode = MOVE_MODE_TRACE;
                    m_TraceDir = dir;
                    m_Current = NextPt;
                    x = m_Current.x;
                    y = m_Current.y;
                    return true;
                }
            }
        }
    }
    //------------------------------------------------------------------------
    // 장애물 가장자리 따라가기 모드.
    // 장애물 가장자리를 따라가다가, 목표 지점까지 일직선 상으로 갈 수 
    // 있다면, 따라가기 모드를 탈출한다.
    //------------------------------------------------------------------------
    else
    {
        // 목표 지점까지의 직선 경로 좌표들을 구한다.
        PATH path;
        Utility::bresenham(m_Current, m_Goal, path);
        assert(!path.empty());
 
        // 모든 좌표가 비어있는지 조사한다.
        bool bPathClear = true;
        for (PATH::const_iterator itr(path.begin());
            itr != path.end(); ++itr)
        {
            const POINT& pt = *itr;
            if (map.isBlocked(pt.x, pt.y))
            {
                bPathClear = false;
                break;
            }
        }
 
        if (bPathClear)
        {
            // 길이 뚫려있다. 직선으로 가면 된다.
 
            PATH::const_iterator b = path.begin();
            PATH::const_reverse_iterator e = path.rbegin();
 
            // 브레센헴 알고리즘의 특성상,
            // 좌표가 앞쪽에 있을 수도 뒤쪽에 있을 수도 있다.
            if (*b == m_Current)
            {
                m_Current = *(++b);
                x = m_Current.x;
                y = m_Current.y;
            }
            else if (*e == m_Current)
            {
                m_Current = *(++e);
                x = m_Current.x;
                y = m_Current.y;
            }
 
            // 일반 모드로 돌아간다.
            m_MoveMode = MOVE_MODE_NORMAL;
            return true;
        }
        else
        {
            // 따라가기 모드!
            for (int i=0; i<DIR_MAX; i++)
            {
                int NextDir = Utility::adjust(m_TraceDir, i - 2);
                NextPt = Utility::getNextPoint(m_Current, NextDir);
 
                if (!map.isBlocked(NextPt.x, NextPt.y))
                {
                    // 가장자리를 따라 움직이다가, 시작 지점과 목표 지점을
                    // 잇는 직선 상에 올라갔다면, 다시 일반 모드로 돌아간다.
                    // 이를 통해 한 장애물의 가장자리를 계속 도는 일을
                    // 어느 정도 방지할 수 있다.
                    if (Utility::ptInPath(m_DirectPath, NextPt))
                        m_MoveMode = MOVE_MODE_NORMAL;
 
                    m_TraceDir = NextDir;
                    m_Current = NextPt;
                    x = m_Current.x;
                    y = m_Current.y;
                    return true;
                }
            }
        }
    }
 
    return false;
}

링크

kb/robusttracingalgorithm.txt · 마지막으로 수정됨: 2014/11/11 14:57 저자 excel96