에이스타에 대한 자세한 설명은
http://egloos.zum.com/cozycoz/v/9748811
위 블로그에 자세히 잘 나와있으니 참고하기 바라고, 여기서는 내 소스코드나 올리고 그냥 조금의 설명이나 하려고한다. 구동 가능하고 쉬운 에이스타 코드를 찾는 많은 이들을 위하여..
■ 에이스타
void Astar(const Position & start, const Position & end,
const int & tileCX, const int & tileCY, TILE * map)
{
list<Node*> openList;
list<Node*> closeList;
Node* startNode = CreateNode(start, 0, 0, nullptr);
openList.push_back(startNode);
Node* endNode = nullptr;
while (!endNode)
{
// 오픈리스트가 비었다면 더이상 찾을 길이없다 판단하고 종료한다
if (openList.empty())
break;
Node* parentNode = nullptr;
// 부모노드가 될 최소 비용 노드를 찾는다.
openList.sort([&](Node* node1, Node* node2)
{
int F1 = node1->G + node1->H;
int F2 = node2->G + node2->H;
if (F1 < F2)
{
return true;
}
return false;
});
parentNode = openList.front();
openList.pop_front();
closeList.push_back(parentNode);
for (int y = parentNode->pos.y - 1; y < parentNode->pos.y + 2; ++y)
{
for (int x = parentNode->pos.x - 1; x < parentNode->pos.x + 2; ++x)
{
int idx = GetIdx(Position(x, y), tileCX, tileCY);
// 범위밖, 못가는 길, 닫힌 목록에 있을때의 예외처리
if (idx == -1)
continue;
if (map[idx] == OP_OBSTACLE)
continue;
if (FindNodeByPos(Position(x, y), closeList))
continue;
// 목표지점에 도달했다면 기록하고 종료한다.
if (x == end.x && y == end.y)
{
endNode = CreateNode(Position(x, y), 0, 0, parentNode);
break;
}
Node* openNode = FindNodeByPos(Position(x, y), openList);
// 현재 위치가 열린목록에 있다면 g값을 갱신시키고 더 작은지 검사한다.
if (openNode)
{
int G = GetG(parentNode->G, parentNode->pos, Position(x, y));
if (G < openNode->G)
{
openNode->G = G;
openNode->parent = parentNode;
}
}
// 아니라면 노드를 생성해 비용들을 산출하고 열린목록에 넣는다
else
{
int G = GetG(parentNode->G, parentNode->pos, Position(x, y));
int H = GetH(Position(x, y), end);
Node* node = CreateNode(Position(x, y), G, H, parentNode);
openList.push_back(node);
}
}
}
}
// 엔드노드가 존재한다면 길을 찾은것으로 판단하고 기록한다
Node* node = endNode;
while (node)
{
Position pos = node->pos;
int idx = GetIdx(pos, tileCX, tileCY);
if (map[idx] != OP_START && map[idx] != OP_END)
{
map[idx] = OP_PATH;
}
node = node->parent;
}
ReleaseList(&openList);
ReleaseList(&closeList);
}
|
에이스타를 처리하는 코드는 이게 전부다. 순서는 대략 이러하다.
1. 열린목록에서 최소 F 비용을 가진 노드를 찾아 부모노드로 설정하고 닫힌목록에 넣는다.
2. 1에서 설정된 부모노드의 주변을 탐색한다. 범위 밖이거나, 못가는 길이거나, 닫힌 목록에있는 노드는 제외한다.
3. 2 과정에서 찾은 타겟 노드가 만약 열린목록에 존재한다면 G값을 현재 부모노드로 부터 산출해보고 만약 새로 산출한 G값이 더 저렴하다면, 타겟 노드의 G값과 부모노드를 새로 산출한 G와 현재 부모로 대체한다
4. 만약 열린목록에 존재하지 않는다면, 새로운 노드를 생성해 비용들을 산출하고 열린목록에 집어넣는다.
5. 위 과정중에 열린 목록에 존재하지 않는다면 경로가 존재하지 않는것으로 판단하고 종료하고, 목표지점에 도달했다면 경로가 존재하는 것으로 판단하고 기록한다.
소스코드도 길지않고 과정도 어렵지않아 매우 쉽게 이해 가능할것이다. 자세한건 아래 프로젝트 파일을 참고하기 바란다.
■ 소스코드
댓글 없음:
댓글 쓰기