1 개요
2 동작
2.1 기본적인 트레이싱
2.2 문제점
2.3 개선안
3 샘플
아직 여러 가지로 모자란 소스지만, 개념 잡는 정도에는 도움이 되지 않을까나.
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;
}
4 링크
SeriousMoin v1 (koMoinMoin 1.0a4 Modified)
![[WWW]](/img/moin-www.gif){kind=small}
Smart Moves: Intelligent Path-Finding에 언급된 Robust Tracing을 구현해 보자.