일단 기본알고리즘 구조는 이전의 글에서 설명된 것처럼 굉장히 심플하다.
왜 그렇게 되는지 이해하는 문제는 물론 별개의 문제이지만.
1. A* 알고리즘이란?
A* 알고리즘은 초기노드(시작지점)에서 목표 노드(목표지점)까지의 경로를 찾는 그래프 탐색 알고리즘이다. 다른 그래프 탐색 알고리즘과 다른 점은 목표에 얼마나 근접한 것인지를 평가하는데 휴리스틱 함수를 사용한다는 것이다.
2. 알고리즘 순서
(1) 시작지점을 열린목록(Openlist)에 넣는다.
(2) 열린목록에 있는 노드 중 1개를 빼서 여덟 방향 주변노드를 탐색한다.
( 평가함수 F= G+H 를 계산 & 부모노드를 명시, 장애물과 닫힌목록은 제외한다.)
F= G+H 설명
G : 시작노드N0에서 현재노드N까지의 최단경로의 값. (수직,수평 +1, 대각선일 경우 +1.41)
H : 현재노드N에서 목표노드까지의 (조건없는)최단경로의 값. (휴리스틱요소)
F : 시작노드N0에서 목표노드까지 현재노드N을 통해 갈 수 있는 모든 가능한 경로 중 최단경로의 값이 된다.
(3) 2단계에서 뺀 노드를 닫힌목록(Closelist)에 삽입한다
(4) 2단계에서 탐색한 노드들을 열린 목록(우선순위 queue)에 삽입한다
(우선순위 큐는 가장 작은 값부터 순서대로 자동정렬되는 특성을 가지기 때문에 가장 낮은 F비용을 가진 노드를 찾을 수 있다.)
(5) 열린 목록 중 가장 앞 노드를 빼고 그 노드를 닫힌 목록에 추가한다.
(6) 5단계에서 뺀 노드의 여덟방향 주요 노드를 탐색한다.
(장애물과 닫힌목록제외, 목표노드가 있는지 조사)
(끝내는 경우: 1. 만일 목표노드가 있다면 부모노드를 추적하여 역순으로 스택에 삽입 2. 열린목록이 비어있게 될 경우 목표노드를 찾는데 실패한 것, 길이 없음.)
(7) 열린목록에 존재하지 않는 노드는 열린목록에 추가하고
중복되는 노드는 G값을 서로비교하여 더 작은 값을 열린 목록으로 교체한다.
(8) 5단계부터 반복
c#언어를 사용해서 구현해보도록 하겠다.
일단 위의 순서부분에 나와 있는 것들을 하나씩 구현해보고 실제 동작을 하는지 확인해본다.
위에 그림은 실제 A*알고리즘을 구현해본 프로그램의 스크린샷이다.
파란색 네모는 고양이를 녹색 네모는 쥐들을 나타내고, 빨간색 영역은 갈수 없는 곳을 노란색 영역은 갈 수 있는곳을 나타낸다.
기본적으로 쥐들은 고양이가 가까이 오게되면 화면의 임의의 위치를 정해서 도망을 가도록 되어 있다.
마우스 왼버튼 클릭으로 고양이의 위치를 지정하게 되면 구현된 A*알고리즘에 따라서 해당 위치의 경로를 탐색하게 되고
경로가 찾아진 경우에는 해당 위치로 이동하게 된다. 만일 고양이의 이동경로에 취들이 있다면 취들은 혼비백산해서 맵의 임의의
위치로 역시 A*알고리즘을 사용해서 경로 탐색을 한다음에 이동하게 될것이다.
먼저 위에 있는 A*알고리즘의 작동순서에 따라서 구현하기 위해서 필요한 것들이 있다.
열린노드, 닫힌노드, 그리고 실제 길을 구성하는 맵데이터가 그것이다.
열린노드와 닫힌 노드는 단일 연결리스트로 구현한다.
다음과 같은 구조로 선언했다.
public class CNaviNode
{
public int x, y; //위치, 2D맵으로 표현하기 위한 위치
public int dist; //목표점까지의 거리
public int depth;
public CNaviNode pParent = null;
//현재 노드를 주어진 노드의 내용물로 복사
public void Copy(CNaviNode pNode)
{
x = pNode.x;
y = pNode.y;
dist = pNode.dist;
depth = pNode.depth;
pParent = pNode.pParent;
}
//위치가 같은지 확인 public bool IsSamePos(CNaviNode pNode) { if (x != pNode.x || y != pNode.y) return false; return true; }
//내용물을 그대로 복사 public CNaviNode Clone() { CNaviNode pNode = new CNaviNode(); pNode.x = x; pNode.y = y; pNode.dist = dist; pNode.depth = depth; pNode.pParent = null; return pNode; }
//노드의 위치를 sx, sy로 설정하고, 목표점 dx, dy까지의 거리를 구해서 초기화 한다. , dep는 탐색깊이 public static CNaviNode Create(int sx, int sy, int dx, int dy, int dep) { CNaviNode pNode = new CNaviNode(); pNode.x = sx; pNode.y = sy; int deltx = dx - sx; int delty = dy - sy; pNode.dist = (deltx * deltx) + (delty * delty); pNode.depth = dep; return pNode; }
//단순히 시작점 sx, sy로 해서 노드를 생성한다 public static CNaviNode Create(int sx, int sy) { CNaviNode pNode = new CNaviNode(); pNode.x = sx; pNode.y = sy; return pNode; }
//주어진 목표점 까지의 거리를 구하고 탐색깊이를 설정한다. public void CalcDist(CNaviNode pDest, int cdepth) { int deltx = pDest.x - x; int delty = pDest.y - y; dist = (deltx * deltx) + (delty * delty); depth = cdepth; } public void SetParent(CNaviNode p) { pParent = p; } public CNaviNode GetParent() { return pParent; } }
길을 구성하는 맵데이터는 단순히 바이트 배열로 선언하고, 갈수 없는부분은 0으로
갈수 있는곳은 1로 마킹하여 텍스트 파일로 저장했다.
아래가 실제 맵데이터이며, 맵의 폭과 높이에 대한 정보와 실제 맵에서 갈 수 있는곳과 없는곳을 표현한
데이터이다.
width 40
height 40
mapstart
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1
1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1
1 1 1 0 1 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1
1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1
1 1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1
1 1 1 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1
1 1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1
1 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
실제 길찾기 수행하기
class CAStarPathFinding
{
private List<CNaviNode> m_vecOpenNode = null; //열린노드
private List<CNaviNode> m_vecCloseNode = null; //닫힌노드
public void Delete()
{
m_vecOpenNode = null;
m_vecCloseNode = null;
m_vecOpenNode = new List<CNaviNode>();
m_vecCloseNode = new List<CNaviNode>();
}
//시작 위치 PStart에서 목표위치 pEnd까지의 경로를 구한다. 경로가 구해진경우 true그렇지 않은경우 fale
//vecPath : 구해진경로
//pNavi : 지형데이터를 제공한다, 위의 맵데이터를 읽어서 맵에 대한 컨트롤 정보를 제공한다
public bool FindPath(CNaviNode pStart, CNaviNode pEnd, ref List<CNaviNode> vecPath, CNavigationData pNavi)
{
Delete(); //열린노드 및 닫힌노드 정보를 클리어하고 초기화
CNaviNode pNode = pStart.Clone();
/*
* insert start position to open node, 시작점을 열린노드에 삽입한다.
* */
m_vecOpenNode.Add(pNode);
int iDepth = 0;
pNode.depth = iDepth;
List<CNaviNode> vecChilds;
vecChilds = new List<CNaviNode>();
while(true)
{
if (m_vecOpenNode.Count == 0)
{//if opennode has not contents, it's meaning that path not found. 만일 열린노드에 더이상 데이터가 없다면 길이 존재하지 않는것이다.
break;
}
pNode = m_vecOpenNode[0]; //get first content, 열린노드의 가장처음항목을 하나 가져온다
m_vecOpenNode.RemoveAt(0); //delete content from open node, 가져온것은 열린노드에서 제거한다
if (pEnd.IsSamePos(pNode)) //if that node is end position, we found path, 만일 가져온 노드가 목표점이라면 해당 노드를 패스목록에 추가하고 길탐색을 종료한다
{
while(pNode != null) //tracking it's parent node for it's parent is null
{
vecPath.Add(pNode); //add node to path list
pNode = pNode.GetParent(); //get current node's parent
}
return true;
}
pNode = InsertCloseNode(pNode); //insert current node to close list, 목표점이 아니면 해당 노드를 닫힌노드에 삽입한다.
++iDepth; //탐색깊이를 하나 증가 시킨다
vecChilds.Clear();
pNavi.GetNeighbor(pNode, ref vecChilds); //해당노드의 인접한 노드들을 모두 가져와서
for (int i = 0;i < vecChilds.Count; ++i)
{
if (FindFromCloseNode(vecChilds[i])) //만일 닫힌노드에 있는것이면 무시하고
{
continue;
}
//닫힌노드에 없는것이라면, 거리를 구한다음에 열린노드에 삽입한다.
vecChilds[i].CalcDist(pEnd, iDepth);
vecChilds[i].SetParent(pNode);
InsertOpenNode(vecChilds[i]);
}
//열린노드를 비용에 따라서 정렬한다
SortOpenNode();
}
Delete();
return false;
}
//노드 p1이 노드 p2보다 저비용이라면(거리가 더가까우며, 탐색깊이가 더 작은지) true
private bool NodeCompare(CNaviNode p1, CNaviNode p2)
{
if (p1.dist < p2.dist) return true;
if (p1.dist > p2.dist) return false;
if (p1.depth <= p2.depth) return true;
return false;
}
//열린노드에 노드 삽입, 중복된 노드가 삽입되지 않도록 처리한다
private void InsertOpenNode(CNaviNode pNode)
{
for (int i = 0;i < m_vecOpenNode.Count; ++i)
{
if (m_vecOpenNode[i].IsSamePos(pNode))
{
InsertCloseNode(m_vecOpenNode[i]);
m_vecOpenNode[i] = pNode;
return;
}
}
m_vecOpenNode.Add(pNode);
}
//닫힌노드에 삽입
private CNaviNode InsertCloseNode(CNaviNode pNode)
{
m_vecCloseNode.Add(pNode);
return pNode;
}
//열린 노드를 비용에 따라서 정렬한다, 심플하게 버블정렬을 하고 있다.
private void SortOpenNode()
{
if (m_vecOpenNode.Count < 2) return;
CNaviNode pNode;
bool bContinue = true;
while(bContinue)
{
bContinue = false;
for (int i = 0;i < m_vecOpenNode.Count - 1; ++i)
{
if (!NodeCompare(m_vecOpenNode[i], m_vecOpenNode[i+1]))
{
pNode = m_vecOpenNode[i];
m_vecOpenNode[i] = m_vecOpenNode[i+1];
m_vecOpenNode[i+1] = pNode;
bContinue = true;
}
}
}
}
//열린노드에 해당 노드가 있는지 확인한다
private bool FindFromOpenNode(CNaviNode pNode)
{
for (int i = 0;i < m_vecOpenNode.Count; ++i)
{
if (m_vecOpenNode[i].IsSamePos(pNode)) return true;
}
return false;
}
//닫힌노드에 해당 노드가 있는지 확인한다
private bool FindFromCloseNode(CNaviNode pNode)
{
for (int i = 0;i < m_vecCloseNode.Count; ++i)
{
if (m_vecCloseNode[i].IsSamePos(pNode)) return true;
}
return false;
}
}
전체 프로젝트 소스코드는 첨부파일에서 다운로드 가능하다.
pathtest2.zip'알고리즘' 카테고리의 다른 글
| 쿼터니언 (0) | 2014.05.02 |
|---|---|
| A* 알고리즘이란? (0) | 2014.05.02 |
