일단 기본알고리즘 구조는 이전의 글에서 설명된 것처럼 굉장히 심플하다.
왜 그렇게 되는지 이해하는 문제는 물론 별개의 문제이지만.
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을 통해 갈 수 있는 모든 가능한 경로 중 최단경로의 값이 된다.
( 평가함수 F= G+H 를 계산 & 부모노드를 명시, 장애물과 닫힌목록은 제외한다.)
F= G+H 설명
G : 시작노드N0에서 현재노드N까지의 최단경로의 값. (수직,수평 +1, 대각선일 경우 +1.41)
H : 현재노드N에서 목표노드까지의 (조건없는)최단경로의 값. (휴리스틱요소)
F : 시작노드N0에서 목표노드까지 현재노드N을 통해 갈 수 있는 모든 가능한 경로 중 최단경로의 값이 된다.
(3) 2단계에서 뺀 노드를 닫힌목록(Closelist)에 삽입한다
(4) 2단계에서 탐색한 노드들을 열린 목록(우선순위 queue)에 삽입한다
(우선순위 큐는 가장 작은 값부터 순서대로 자동정렬되는 특성을 가지기 때문에 가장 낮은 F비용을 가진 노드를 찾을 수 있다.)
(우선순위 큐는 가장 작은 값부터 순서대로 자동정렬되는 특성을 가지기 때문에 가장 낮은 F비용을 가진 노드를 찾을 수 있다.)
(5) 열린 목록 중 가장 앞 노드를 빼고 그 노드를 닫힌 목록에 추가한다.
(6) 5단계에서 뺀 노드의 여덟방향 주요 노드를 탐색한다.
(장애물과 닫힌목록제외, 목표노드가 있는지 조사)
(끝내는 경우: 1. 만일 목표노드가 있다면 부모노드를 추적하여 역순으로 스택에 삽입 2. 열린목록이 비어있게 될 경우 목표노드를 찾는데 실패한 것, 길이 없음.)
(장애물과 닫힌목록제외, 목표노드가 있는지 조사)
(끝내는 경우: 1. 만일 목표노드가 있다면 부모노드를 추적하여 역순으로 스택에 삽입 2. 열린목록이 비어있게 될 경우 목표노드를 찾는데 실패한 것, 길이 없음.)
(7) 열린목록에 존재하지 않는 노드는 열린목록에 추가하고
중복되는 노드는 G값을 서로비교하여 더 작은 값을 열린 목록으로 교체한다.
중복되는 노드는 G값을 서로비교하여 더 작은 값을 열린 목록으로 교체한다.
(8) 5단계부터 반복
c#언어를 사용해서 구현해보도록 하겠다.
일단 위의 순서부분에 나와 있는 것들을 하나씩 구현해보고 실제 동작을 하는지 확인해본다.
위에 그림은 실제 A*알고리즘을 구현해본 프로그램의 스크린샷이다.
파란색 네모는 고양이를 녹색 네모는 쥐들을 나타내고, 빨간색 영역은 갈수 없는 곳을 노란색 영역은 갈 수 있는곳을 나타낸다.
기본적으로 쥐들은 고양이가 가까이 오게되면 화면의 임의의 위치를 정해서 도망을 가도록 되어 있다.
마우스 왼버튼 클릭으로 고양이의 위치를 지정하게 되면 구현된 A*알고리즘에 따라서 해당 위치의 경로를 탐색하게 되고
경로가 찾아진 경우에는 해당 위치로 이동하게 된다. 만일 고양이의 이동경로에 취들이 있다면 취들은 혼비백산해서 맵의 임의의
위치로 역시 A*알고리즘을 사용해서 경로 탐색을 한다음에 이동하게 될것이다.
먼저 위에 있는 A*알고리즘의 작동순서에 따라서 구현하기 위해서 필요한 것들이 있다.
열린노드, 닫힌노드, 그리고 실제 길을 구성하는 맵데이터가 그것이다.
열린노드와 닫힌 노드는 단일 연결리스트로 구현한다.
다음과 같은 구조로 선언했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
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; }
}
| cs |
길을 구성하는 맵데이터는 단순히 바이트 배열로 선언하고, 갈수 없는부분은 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
실제 길찾기 수행하기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
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;
}
}
| cs |
전체 프로젝트 소스코드는 첨부파일에서 다운로드 가능하다.
또는 git 을통해서 소스코드를 받아 보실 수 있습니다.
https://github.com/choi98772/pathtest
많이 배우고 갑니다~
답글삭제소스를 다운 받을 수 있으면 더 쉽게 이해 됬을 것 같은데 예제에 나오지 않는 네비 함수가 포함되어 있어서 끝 부분에서 너무 헷갈리네요 ㅠㅠ
답글삭제소스코드 링크가 깨져있었네요. 링크주소 수정했으니 전체 소스파일다운로드 받아 보시면됩니다.
삭제ㄷㄷ; 오래된 글이신데 덧글을 봐주실 줄은 몰랐네요 감사합니다 ㅠㅠ
삭제감사합니다 올려주신 소스로 공부가 되었고 실제 원하는 기능을 구현 할 수 있었습니다 정말 감사합니다 ㅜ
삭제작성자가 댓글을 삭제했습니다.
삭제소스코드가 다시 깨진 것 같습니다. ㅜㅜ 죄송하지만 링크를 다시한번 확인해 주실 수 있으신지요?
답글삭제링크가 깨진지 모르겠는데 다시 공유설정해두었습니다.
삭제깃에도 소스를 올려두었습니다.
https://github.com/choi98772/pathtest
안녕하세요. 지도 데이터를 바꾸어서 상황을 구현해보고 싶은데요. 지도데이터는 어디서 어떻게 바꿀수 있나요 또한 바꿀 때 맵사이즈를 변경하고 싶은거 반드시 고려해야할 사항은 무엇이 있을까요?
답글삭제깃에서 소스를 받으시면 bin/Debug 폴더안에 실행파일이 있습니다. 그리고 맵파일도 같이 있는데 이름이 map.txt입니다. 맵은 n * n개의 셀로 구성되어 있는데 맵파일을 열어서보시면 width 가 셀의 가로개수 height가 셀의 세로 개수입니다. mapstart아래 있는 내용이 실제 맵인데 1이 이동가능한부분 0이 이동불가능한 부분입니다. 맵의 크기나 내용을 수정하시려면 이걸 수정해주시면되겠지요.
삭제프로그램에서 맵을 그릴때는 (각셀의 픽셀크기 * 셀의 개수)의 크기에 해당하는 비트맵을 만들어서 그려주게 됩니다. 해당 내용은 Form1.cs파일에 있는데 기존소스의 경우에는 40 * 40셀 크기를 기준으로 그리게 해두어서 크기를 더크게 변경하면 제대로 작동하지 않는 문제가 있었습니다. 소스를 조금 수정해서 맵파일의 크기에 맞게 제대로 그리도록 해서 깃에 올려두었습니다.
위 성실한 답변 감사드립니다. 수정까지 해주시다니 정말 감사합니다. // 질문 몇 개 더 드리고 싶습니다. 오픈된 곳과 막힌곳의 구분은 이진법으로 0,1로 표현할 수 밖에 없나요? 예를 들어 저희가 구상하고 있는 것은 0(막힌 곳)과 1(열린 곳)로 구현된 맵에서 제 3의 변수(숫자 : 2)를 추가하여 길을 막아볼 생각이거든요. 3의 변수는 화재로 가정하고 일정시간을 두고 규칙성을 갖고 퍼지게할 생각입니다. 그 퍼지게 보이는 것을 0으로만 지정해야하는 것인지 아니면 2와 같은 수로 표현 가능한지 여쭙고 싶습니다. 제 3의 수로 표현하고 싶은 이유는 0과 2를 색을 다르게 함으로서 구분하고 싶어서요. 제 3의 변수를 지정할 때 고려해야할 상황이 있는지 알고 싶습니다. /
삭제저 초록 쥐 부분으로 추정되는 부분을 싹 다 지워봤는데 구현이 안되더라구요. 이것은 무엇이 문제일까요? 쥐로 표현된 부분이 꼭 전체 식에 영향을 주나요?
맵데이터를 꼭 0, 1로 표현할 필요는 없습니다. CNavigationData.cs 파일을 열어보시면 IsValidPos함수가 있는데 주어진 위치가 갈수 있는곳인지 아닌지 리턴하는 함수입니다. 해당 함수를 적절히 수정해주시면되겠지요. 그리고 맵을 그리는 부분이 Form1.cs의 DrawMap()함수인데 안의 내용을 보시고 적절히 수정해주시면되겠습니다. 그리고 유닛들이 있는데 파란색 박스로 그려지는 유닛은 유저가 컨트롤 할 수 있는 유닛이고, 녹색 박스로 그려지는 유닛은 자체적인 알고리즘(간단히 파란색 박스가 일정이상 접근하면 임의의 위치를 선택해서 이동하는)으로 작동하는 유닛입니다. 예제를 위한 것이기 때문에 목적에 맞지 않을 수 있으니 해당 부분도 수정이 필요할 수 있습니다.
삭제작성자가 댓글을 삭제했습니다.
삭제첫번째 질문 : Form.cs Draw map에서 else if로 추가하여 새로운 변수 2에 대해서 길을 막는 현상을 구현하려고 하였습니다. 2도 막히는 것이라는 정보를 어디서 지정할 수 있을까요? IsVaildPos 함수에서
삭제virtual public bool IsValidPos(int x, int y)
{
if (x < 0 || x >= m_iWidth) return false;
if (y < 0 || y >= m_iHeight) return false;
if (m_MapData[(y * m_iWidth) + x] == 0) return false;
return true;
}
//해당 지점이 이동가능한 지점인가 확인한다
virtual public bool IsValidPos(CNaviNode pos)
{
if (pos.x < 0 || pos.x >= m_iWidth) return false;
if (pos.y < 0 || pos.y >= m_iHeight) return false;
if (m_MapData[(pos.y * m_iWidth) + pos.x] == 0) return false;
return true;
}
어떤 흐름인지 이해를 못하였습니다.
0보다 작거나 넓이보다 작으면 실행하지 안는다가 제가 이해한 것입니다. 이부분을 건들어서 제 3의 변수 2로 길을 막는 것이 어떻게 표현되는건가요? 제가 아예 생기초라 지식이 부족한점 죄송합니다.
-------------------------------------------------------------------------------------------
두번째 질문 : 점의 경우 인접한 모든 노드에 이동 가능한 것으로 설정되어 있는데, 대각선을 제외하고 상하좌우 (+ 형태)로 움직임을 제한하기 위해선 어느 부분을 어떻게 건들면 좋을까요? 대각선으로 이동이 가능ㅎ니 벽을 뚫어 버리는 경우(울타리를 표현하였으나 그지점을 넘어가버림)가 생겨 버리네요.
virtual public int GetNeighbor(CNaviNode pos, ref List vecList)
{
int[] distx = new int[3] { -1, 0, 1 };
int[] disty = new int[3] { -1, 0, 1 };
for (int y = 0; y < 3; ++y)
{
for (int x = 0; x < 3; ++x)
{
int cx = distx[x] + pos.x;
int cy = disty[y] + pos.y;
if (cx == pos.x && cy == pos.y) continue;
if (!IsValidPos(cx, cy)) continue;
vecList.Add(CNaviNode.Create(cx, cy));
}
}
return vecList.Count;
}
제가 보기엔 이 부분을 건들어서 방향성을 지정하는 것이라고 생각하고 있습니다. -1,0 1이 세가지가 의미하는 것이 무었인가요? 특히 '-1' 이요.
1번의 경우
삭제if (m_MapData[(pos.y * m_iWidth) + pos.x] == 0) return false; 부분을 보시면 해당위치가 0이면 길이 아니다 라는 부분입니다.
if (m_MapData[(pos.y * m_iWidth) + pos.x] == 0 || m_MapData[(pos.y * m_iWidth) + pos.x] == 2)
return false;
씩으로 바꿔주시면되겠지요.
2번째의 경우 주어진 위치를 기준으로 8방향의 노드를 구해서 길인부분만 목록에 추가하는코드입니다. 그러니 상,하, 좌, 우 지점만 노드로 추가하는 형태로 변경하시면됩니다.
virtual public int GetNeighbor(CNaviNode pos, ref List vecList)
{
//x, y변위값의 쌍으로 각각 좌, 상, 우, 하
int []pos = new int[8]
{-1, 0, //좌
0, -1, //상
1, 0, //우
0, 1}; //하
for (int i = 0;i < 8; i += 2)
{
int cx = pos[i] + pos.x;
int cy = pos[i + 1] + pos.y;
//주어진 노드와 같은 노드면 통과
if (cx == pos.x && cy == pos.y) continue;
//이동불가능한 지점이면 통과
if (!IsValidPos(cx, cy)) continue;
vecList.Add(CNaviNode.Create(cx, cy));
}
return vecList.Count;
}
//변수 pos가 겹치네요.
삭제virtual public int GetNeighbor(CNaviNode pos, ref List vecList)
{
//x, y변위값의 쌍으로 각각 좌, 상, 우, 하
int []posDelta = new int[8]
{-1, 0, //좌
0, -1, //상
1, 0, //우
0, 1}; //하
for (int i = 0;i < 8; i += 2)
{
int cx = posDelta[i] + pos.x;
int cy = posDelta[i + 1] + pos.y;
//주어진 노드와 같은 노드면 통과
if (cx == pos.x && cy == pos.y) continue;
//이동불가능한 지점이면 통과
if (!IsValidPos(cx, cy)) continue;
vecList.Add(CNaviNode.Create(cx, cy));
}
return vecList.Count;
}
그리고 -1의 의미를 물으셨는데
삭제수정된 posDelta 배열의 경우 x, y변위를 저장하고 있는 배열입니다.
만일 i가 0 이고, pos.x는 1, pos.y는 1이라고 가정할때
int cx = posDelta[i] + pos.x;
int cy = posDelta[i + 1] + pos.y; 의 결과는
cx = -1 + 1
cy = 0 + 1
이니 0, 1이 될겁니다.
결과적으로 pos의 좌측 지점의 좌표입니다.
나머지도 동일합니다.
제가 감사 표현이 늦었네요. 정말로 감사드립니다.
삭제두번째에 질문에 대한 답변 감사합니다.
답글삭제안녕하세요 전에 질문 드렸던 사람입니다. 혀재 맵 데이터에 새로운 난수로 방해요소를 설정하는데까지 성공하였습니다.
답글삭제맵에 시간이 지남에 따라 새로운 인덱스 변수 2로 생기게 구현하였습니다.
새로운 2가 발생함에 따라 주변 초록색 점을 쫓아 내고 싶습니다.
파란점(추격자) 이외의 새로운 점 2로부터 초록색 점들이 도망가는 현상을 구현하고자 할 때 어느 부분을 건들면 좋을지 조언 받고 싶습니다.
CUnit.cs 소스를 보시면 유닛은 추적모드(사용자컨트롤, 파란색점) 회피모드가 있습니다.
삭제회피모드는(녹색점) 추적유닛과 자신과의 거리를 검사해서 일정거리 이하면 맵의 임의의 지점을 선택하고 해당 위치가 이동가능한 위치인경우 목표점으로 설정하고 이동하는 형태로 작동합니다.
아래 코드가 Update함수의 내부 코드중 회피모드를 작동시키는 코드인데
추적자의 거리와 자신의 거리가 4cell 이하이고, 현재 이동중이지 않으면 임의의 위치를 선택해서 해당 위치까지 패스를 구한다음 이동하는 코드입니다.
아래 코드를 좀 수정해주시면될것 같습니다.
예를들어
각 유닛은 현재 자신의 위치를 기준으로 맵의 상/하/좌/우를 검사해서 2번인덱스가 나타나는 경우 맵의 임의의 위치를 선택하고 경로를 구한다음 이동하는 형태와 같이 수정가능할거 같습니다.
else
{//타겟을 회피하는 모드다
//추적자와의 거리가 4cell이하이고 현재 이동중이지 않으면
if (Math.Abs(dx) < 4 && Math.Abs(dy) < 4 && !m_bMove)
{
while (true)
{
//맵의 임의의 위치를 선택하고
int cx = m_RND.Next(ND.GetWidth());
int cy = m_RND.Next(ND.GetHeight());
//해당 위치가 이동가능한 위치면
if (ND.IsValidPos(cx, cy))
{
m_vecPath = new List();
CNaviNode pStart = CNaviNode.Create(m_iPos[0], m_iPos[1]);
CNaviNode pEnd = CNaviNode.Create(cx, cy);
//목표점까지의 경로룰 구하고
if (!FF.FindPath(pStart, pEnd, ref m_vecPath, ND))
{
//경로가 구해지지 않으면, while 루프를 다시 반복
continue;
}
else
{
//유닛을 이동중으로 설정하고 while 루프를 종료한다.
m_bMove = true;
break;
}
}
}
}
}
답변 정말 감사드립니다.
삭제작성자가 댓글을 삭제했습니다.
답글삭제안녕하세요. 전에 질문 드린 송인우 라고 합니다. 덕분에 맵 변경과 새로운 장애물로부터 다른점들이 반응하는 것까지 구현하였습니다. 다만 프로그램 구동상 의문이 생겨 질문하나 더 드리고자 합니다. 공유하신 프로그램은 A* 알고리즘을 기반으로 최단 경로를 찾아 파란점이 이동하는 것으로 알고 있습니다. 하지만 프로그램을 구현하다 보면 파란점이 최단경로를 찾는 과정에서 주변 구석이나 오목하게 들어간 지점(凸凸)을 경유하여 이동하는 현상을 보입니다.
답글삭제□□□□□□□□□□□
-------> ----------> ( 원하는 예상경로)
凸凸凸凸凸凸凸凸凸凸□
□□□□□□□□□□□
(현재 상황경로)
凸凸凸凸凸凸凸凸凸凸凸 (경우에 따라 저 오목하게 들어간 지점을 다 지나쳐 이동함)
이러한 이유는 무엇이며, 이러한 점들을 지나지 않고 도착점과 시작점 사이에 최단 경로만을 지나 이동할 수 있는지 알고 싶습니다.
예제에서 구현된 a star 알고리즘은 현재 노드의 주변노드를 평가해서 최적의 노드를 지속적으로 찾는 방식으로 최종경로를 구하게 되어 있습니다. 이렇다 보니 위와 같은 현상이 발생하게 되는데 이경우 a star 알고리즘만으로는 해결이 안될듯하네요. 최종적으로 구해진 노드를 정리해서 쓸때없는 경로를 수정하는 방식으로 개선해야 할듯합니다.
삭제예를 들면 구해진 경로가 a, b, c, d 라 가정하고 이때 노드 a와 한칸 건너뛴 노드 c가 같은 위치라면 노드 b, c를 제거하고 a, d를 바로 연결할 수 있을 겁니다. 이와 같은 행태로 최종경로를 한번정리 해주시면 좀더 나은 결과를 얻을 수 있을듯합니다.
삭제한 노드로 부터 주변 노드를 평가하고 지나과는 과정에서, 우회하는 현상이 계속 발생됨에도 불구하고, 큰 틀로 보아 해당하는 경로가 최단 경로임을 어떻게 입증하는 편이 좋을까요? 이것에 대해 어떤 견해를 갖고 계신지 궁금합니다.
답글삭제알고 있는 내용 :A* 알고리즘은 초기노드(시작지점)에서 목표 노드(목표지점)까지의 경로를 찾는 그래프 탐색 알고리즘으로 알고 있습니다. 다른 그래프 탐색 알고리즘과 다른 점은 목표에 얼마나 근접한 것인지를 평가하는데 휴리스틱 함수를 사용한다는 것이다.
-> 위의 처음 질문으로 제시된 상황이 어쩔 수 없는 한계인건가요? 혹시 위같은 우회하는 상황을 대처하거나 위 상황을 고려할 필요 없는 알고리즘이 있는지 질문 드리고 싶습니다 ㅎ
일단 결론적으로 위의 상황에서 astar알고리즘 만으로 최적의 경로를 구하기는 사실상 힘듭니다.
삭제최선의 패스를 찾자면 노드에 대해서 정확한 평가가 이루어져야 하는데, 이 평가 자체가 몇가지 정보만으로 정확하게 이루어질수는 없기 때문입니다. 위의 예제에서는 단순히 목표점과의 거리와 탐색깊이만을 노드평가에 반영하는데, 평가에 반영할 추가적인 요소를 구성하는 형태로 평가함수를 개선하지 않는 이상은 더나은 결과를 얻기는 힘들것같네요. 그리고 최종적으로 구해진 패스를 다시한번 최적화 하는 작업을 수행해줘야 할듯합니다. 저도 astar알고리즘을 거의 20여년전에 공부한 이후로 다른 알고리즘에 대해서는 알아본게 없다보니 더나은 패스파인딩 알고리즘이 있는지는 잘모르겠습니다. 그리고 말씀하신 노드우회하는 경우와 경로가 최적이 아닌경우 같은 현상은 20여년 전에도 문제가 되는 부분이었는데, 결론은 astar알고리즘을 패스파인딩의 기본으로 하고 구해진 경로를 좀더 최적화 하는 형태밖에는 딱히 다른 대안은 없는듯하네요.
답변 감사합니다.
삭제