탄금 프로젝트에 AStar알고리즘을 적용 시킬려면 어떤게 필요할까?
AStar알고리즘-탄금컨버팅.zip1. SRPG라는 장르적 특성 상 기존 알고리즘의 이동형태를 바꿀 필요가 있다.
: 자신 타일을 기준으로 상하좌우 대각선을 포함해 8방향에 대한 적합성 검사를 한다. 이를 수정하여 상하좌우 즉 4방향에 대한 검사를 수행하도록 해야한다.
: 캐릭터가 이동 할 수 있는 영역은 자신의 이동거리를 나타내는 타일을 넘어갈 수 없으므로 이를 제한해야 한다. 최대 이동 거리를 제한 할 수 있는 방식에는 2가지가 있다. 길찾기가 완료된 GetBestNode()매서드를 통해서 최적화된 노드의 리스트를 얻어오는데. 얻어온 후 이동 시에 자신의 최대 이동거리와 비교하여 break; 시키는것과 노드 검색 시에 검색 범위를 최대 이동거리로 제한을 두는 것이다. 2번째 방법이 효율성 측면에서는 우수하나 AStar알고리즘의 특성 상 현재 찾고 있는 길의 적합도(f)값은 길찾기가 완료되지 않은 시점에서는 추측에 불과하기 때문에 무리가 있다.
2. 1번 문제가 해결됐다면 2번 문제를 들어가야 된다. 현재 검색하고자 하는 타일을 구성하는 작업이 필요하다.
: 타일의 사이즈를 구성하는데에는 3개의 define문이 사용되었다.
#define ASE_GRIDSIZE 8 // 타일 간격
#define ASE_BOARDX 100 // 검색하고자 하는 타일의 세로축
#define ASE_BOARDY 100 // 검색하고자 하는 타일의 가로축
.
.
UCHAR m_cBoard[ASE_BOARDX][ASE_BOARDY];
UCHAR m_cDataBoard[ASE_BOARDX][ASE_BOARDY];
위의 코드처럼 검색할 보드가 셋팅된다.
시각적인 보드로 판단되니 코드 분석을 더 합시다.
실마리를 풀었다. aseView.cpp의 MouseToPoint()매서드를 살펴보자.
이 매서드는 유저가 툴바에서 선택한 브러쉬로 해당 포인트를 설정하는 루틴이 들어있다.
1) 마우스의 포인터와 보드 정보를 얻어온다
int px = point.x/ASE_GRIDSIZE; // 마우스 좌표를 얻어온다.
int py = point.y/ASE_GRIDSIZE; // 마우스 좌표를 얻어온다.
UCHAR *board = GetDocument()->GetBoard(); // GetBoard()함수로 포인터를 얻어온다.
2) Start-End값을 셋팅한다.
else if (brush == 256)
{
temp.x = m_cStart.x * ASE_GRIDSIZE;
temp.y = m_cStart.y * ASE_GRIDSIZE;
UCHAR *board = GetDocument()->GetBoard();
if (board[ci(px,py)] == 0 || pDoc->AseMessage(ASE_VALID, px, py) == ASE_POSINVALID) return;
m_cStart.x = px;
m_cStart.y = py;
}
if (brush == 257)
{
temp.x = m_cEnd.x * ASE_GRIDSIZE;
temp.y = m_cEnd.y * ASE_GRIDSIZE;
UCHAR *board = GetDocument()->GetBoard();
if (board[ci(px,py)] == 0 || pDoc->AseMessage(ASE_VALID, px, py) == ASE_POSINVALID) return;
m_cEnd.x = px;
m_cEnd.y = py;
}
: 브러시 256은 start 257은 end를 나타내며 탄금 프로젝트 에서 start에는 캐릭터 자신의 위치를 넣고 end에는 공격할 대상의 위치를 넣으면 되겠다.
3) 장애물 값을 셋팅 한다. 장애물과 관련된 변수와 함수를 살펴보자.
var
m_iBreakData - int
m_cBreakpoint - CPoint
m_iBreakData - int
m_pcBreakNode - _asNode*
func
CPoint GetBreakpoint() { return m_cBreakpoint; }
void SetBreakpoint(CPoint bp) { m_cBreakpoint = bp; m_iBreakData = -1; }
void CAseDoc::NodeAdded(_asNode *node, int data)
{
if (m_cBreakpoint.x == -1 && m_iBreakData == -1) return;
if (node->x == m_cBreakpoint.x && node->y == m_cBreakpoint.y) {
m_bBreakpointHit = true;
m_pcBreakNode = node;
}
if (data == m_iBreakData) {
m_bBreakpointHit = true;
m_pcBreakNode = node;
}
}
위의 함수는 BreakPoint메뉴를 위해 존재하는 것이다.
다시 찾아보면 이동이 불가능한 타일은 ID_WEIGHTIMPASSABLE이라 명명되어 있고 m_uBrushType은 0으로 설정되어 있다.
결국 MouseToPoint매서드가 호출될 때 board의 특정 인덱스에 장애물을 나타내는 brush값인 0을 집어 넣음으로써 맵데이터가 채워지는 것이다.
// 뭐야 별거 아니잖아. 이것 때문에 4시간 동안 삽질 했다.
실질적으로 필요한 것만 간추리면 정말 간소한 AStar알고리즘이 완성되겠다.
//------------------------------------------------------------------------------
Q1-m_cDataBoard라는 멤버변수가 어디에 사용되는지는 이해가 않감.
A1-
Q2-캐릭터-캐릭터매니저-AI-FSM-AStar클래스간의 설계.
A2-
Q3-고정 장애물 말고 캐릭터를 장애물로 놓고 생각했을 시의 길찾기
A3-캐릭터 캐릭터 이동 턴이 종료된 시점에 해당 타일 정보 업데이트 시켜줌.
2007년 10월 24일 추가 작성
자료구조와 알고리즘 교수님께서 우리팀은 A*알고리즘을 프로젝트에 적용 시켰다고 이에 대한 발표준비를 하라고 하셨다. 그래서 샤샤삭 만들어 봤다. 실행파일과 스크린 샷 등을 포함 시켰다.
이올린에 북마크하기
이올린에 추천하기'직업에 관한 관심' 카테고리의 다른 글
| 첫 회사, 첫 작업물.. (0) | 2007/11/29 |
|---|---|
| "사내 정치를 잘하려면..." (0) | 2007/10/25 |
| AStar알고리즘을 분석해봅니다. (3) | 2007/10/24 |
| 엔도어즈 면접 보러 갑니다. (0) | 2007/10/22 |
| 프로그래머형 인간 - 기획자형 인간 (0) | 2007/09/30 |
| 엔트리브 입사지원서 작성 완료. (0) | 2007/09/30 |
