cocos2d-x용으로 만들었으며, 다음의 블로그의 내용을 참조하였다.
http://blog.daum.net/jty71/15645104
http://blog.daum.net/jty71/15645104
위 두 블로그 다 같은소스가 첨부파일로 올라가있었는데, 내공과 영어실력이 부족하기도 하고,
4방향으로 Cocos2d 타
가급적 객체지향으로 만들어보았는데, 사실 제대로 짠거인지도 잘 모르겠다.
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
|
//
// DK_PathFindNode.h
// Marionette
//
// Created by choi on 2014. 6. 26..
//
//
#ifndef __Marionette__DK_PathFindNode__
#define __Marionette__DK_PathFindNode__
#include "cocos2d.h"
#define _ASTAR_3_G_DIAGONAL 20
#define _ASTAR_3_G_DIRECT 10
class DK_PathFindNode : public cocos2d::Ref
{
public:
static DK_PathFindNode* create();
//-------------------------------------------------
// 나의 포지션(타일 좌표)
//-------------------------------------------------
CC_PROPERTY(cocos2d::Point, _targetPos, TileCnt);
//-------------------------------------------------
// 출발점에서의 거리.
//-------------------------------------------------
CC_PROPERTY(int, _g, G);
//-------------------------------------------------
// 도착점에서의 거리.
//-------------------------------------------------
CC_PROPERTY(int, _h, H);
//-------------------------------------------------
// 경로 선택 비교값.
//-------------------------------------------------
int getF();
//-------------------------------------------------
// 부모 타일 정보. 탐색이후 경로추적용.
//-------------------------------------------------
CC_PROPERTY(DK_PathFindNode*, _parent, Parent);
//-------------------------------------------------
// 노드정보 초기화(권장)
// @parent. 부모노드.
// @currentTileCnt. 이 노드의 타일좌표.
// @destiTileCnt. 도착지점.
//-------------------------------------------------
void setAll(DK_PathFindNode* parent,
const cocos2d::Point& currentTileCnt,
const cocos2d::Point& destiTileCnt);
};
#endif /* defined(__Marionette__DK_PathFindNode__) */
|
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
|
//
// DK_PathFindNode.cpp
// Marionette
//
// Created by choi on 2014. 6. 26..
//
//
#include "DK_PathFindNode.h"
USING_NS_CC;
DK_PathFindNode* DK_PathFindNode::create()
{
auto ret = new DK_PathFindNode();
ret->autorelease();
return ret;
}
void DK_PathFindNode::setTileCnt(cocos2d::Point var)
{
_targetPos = var;
}
cocos2d::Point DK_PathFindNode::getTileCnt()
{
return _targetPos;
}
void DK_PathFindNode::setG(int g)
{
_g = g;
}
int DK_PathFindNode::getG()
{
return _g;
}
void DK_PathFindNode::setH(int h)
{
_h = h;
}
int DK_PathFindNode::getH()
{
return _h;
}
int DK_PathFindNode::getF()
{
return _g + _h;
}
void DK_PathFindNode::setParent(DK_PathFindNode *var){
_parent= var;
}
DK_PathFindNode* DK_PathFindNode::getParent(){
return _parent;
}
void DK_PathFindNode::setAll(DK_PathFindNode* parent,
const cocos2d::Point& currentTileCnt,
const cocos2d::Point& destiTileCnt)
{
//현재 포지션.
DK_PathFindNode::setTileCnt(currentTileCnt);
//부모
setParent(parent);
//출발점에서의 거리. G
Point parentTileCnt = getParent()->getTileCnt();
//좌상
if(parentTileCnt.x - 1 == currentTileCnt.x &&
parentTileCnt.y - 1 == currentTileCnt.y)
{
setG(parent->getG()+_ASTAR_3_G_DIAGONAL);
}
//상
else if(parentTileCnt.x - 0 == currentTileCnt.x &&
parentTileCnt.y - 1 == currentTileCnt.y)
{
setG(parent->getG()+_ASTAR_3_G_DIRECT);
}
//우상
else if(parentTileCnt.x + 1 == currentTileCnt.x &&
parentTileCnt.y - 1 == currentTileCnt.y)
{
setG(parent->getG()+_ASTAR_3_G_DIAGONAL);
}
//우
else if(parentTileCnt.x + 1 == currentTileCnt.x &&
parentTileCnt.y - 0 == currentTileCnt.y)
{
setG(parent->getG()+_ASTAR_3_G_DIRECT);
}
//우하
else if(parentTileCnt.x + 1 == currentTileCnt.x &&
parentTileCnt.y + 1 == currentTileCnt.y)
{
setG(parent->getG()+_ASTAR_3_G_DIAGONAL);
}
//하
else if(parentTileCnt.x + 0 == currentTileCnt.x &&
parentTileCnt.y + 1 == currentTileCnt.y)
{
setG(parent->getG()+_ASTAR_3_G_DIRECT);
}
//좌하
else if(parentTileCnt.x - 1 == currentTileCnt.x &&
parentTileCnt.y + 1 == currentTileCnt.y)
{
setG(parent->getG()+_ASTAR_3_G_DIAGONAL);
}
//좌
else if(parentTileCnt.x - 1 == currentTileCnt.x &&
parentTileCnt.y - 0 == currentTileCnt.y)
{
setG(parent->getG()+_ASTAR_3_G_DIRECT);
}
//동일
else {
setG(0);
}
//도착점에서의 거리. H
const int START_2_DESTI_DISTANCE_X = destiTileCnt.x - getTileCnt().x;
const int START_2_DESTI_DISTANCE_Y = destiTileCnt.y - getTileCnt().y;
const int START_2_DESTI_DISTANCE =
abs(START_2_DESTI_DISTANCE_X) + abs(START_2_DESTI_DISTANCE_Y);
setH(START_2_DESTI_DISTANCE * _ASTAR_3_G_DIRECT);
}
|
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
|
//
// DK_PathFinder.h
// Marionette
//
// Created by choi on 2014. 6. 27..
//
//
/*
4방향 탐색 알고리즘.
*/
#ifndef __Marionette__DK_PathFinder__
#define __Marionette__DK_PathFinder__
#include "cocos2d.h"
#include "DK_PathFindNode.h"
class DK_PathFinder
{
public:
//--------------------------
// 생성자.
// @startTileCnt : 경로 탐색을 시작할 시작지점의 타일좌표.
// @destiTileCnt : 경로 탐색을 마칠 도착지점의 타일좌표.
// @onCheckBlock : 타일좌표를 받으면 해당 좌표가 장애물인지, 비 장애물인지 알려줄 콜백함수.
// @maxLoopCnt : 무한 반복을 막기위한 반복 카운트 (기본값 100)
//--------------------------
DK_PathFinder(cocos2d::Point startTileCnt,
cocos2d::Point destiTileCnt,
std::function<bool(const cocos2d::Point&)> onCheckBlock,
int maxLoopCnt = 100);
//--------------------------
// 시작지점에서 도착지점까지의 경로를 탐색하여 리턴한다.
//--------------------------
std::vector<cocos2d::Point> getPath();
private:
int _maxLoopCnt = 0; //무한반복을 막기위한 반복 카운트
cocos2d::Point _startPos; //경로 탐색 시작좌표.
cocos2d::Point _destiPos; //경로 탐색 종료좌표.
cocos2d::Vector<DK_PathFindNode*> _openList; //경로 탐색에 쓰일 열린 노드.
cocos2d::Vector<DK_PathFindNode*> _closeList; //이미 관계설정을 마친 닫힌 노드.
std::function<bool(const cocos2d::Point&)> _onCheckBlock; //장애물여부 콜백.
};
#endif /* defined(__Marionette__DK_PathFinder__) */
|
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
164
165
166
167
168
169
170
171
172
173
174
175
|
//
// DK_PathFinder.cpp
// Marionette
//
// Created by choi on 2014. 6. 27..
//
//
#include "DK_PathFinder.h"
USING_NS_CC;
DK_PathFinder::DK_PathFinder(cocos2d::Point startTileCnt,
cocos2d::Point destiTileCnt,
std::function<bool(const cocos2d::Point&)> onCheckBlock,
int maxLoopCnt)
{
_startPos = startTileCnt;
_destiPos = destiTileCnt;
_onCheckBlock = onCheckBlock;
_maxLoopCnt = maxLoopCnt;
}
std::vector<cocos2d::Point> DK_PathFinder::getPath()
{
//현재 노드 만들기
auto currentNode = DK_PathFindNode::create();
currentNode->setAll(currentNode, _startPos, _destiPos);
//최초 노드 열기
_openList.pushBack(currentNode);
//반복
int loopCnt = 0;
//--------------------------
// 현재 노드의 타일이 도착지점 타일이거나,(탐색 성공)
// 더이상 열린 노드가 없거나, (탐색 실패)
// 반복횟수가 최대 수치인 경우. (탐색 실패)
// 탐색을 종료한다.
//--------------------------
while (currentNode->getTileCnt() != _destiPos &&
loopCnt < _maxLoopCnt)
{
CCLOG("%d. 현재 노드 f, x, y : %d, %.0f, %.0f", loopCnt,
currentNode->getF(), currentNode->getTileCnt().x, currentNode->getTileCnt().y);
//현재 노드 닫기
_openList.eraseObject(currentNode);
_closeList.pushBack(currentNode);
//현재 노드의 주변 노드 열기
cocos2d::Vector<DK_PathFindNode*> neighborNodes;
for(int i = 0; i < 4; i++){
//주변 타일 탐색.
auto currentPos = currentNode->getTileCnt();
cocos2d::Point neighborPos;
switch (i) {
case 0:
neighborPos = Point(currentPos.x, currentPos.y+1);
break;
case 1:
neighborPos = Point(currentPos.x, currentPos.y-1);
break;
case 2:
neighborPos = Point(currentPos.x-1, currentPos.y);
break;
case 3:
neighborPos = Point(currentPos.x+1, currentPos.y);
break;
}
//막힘 체크.
if(_onCheckBlock(neighborPos)){
continue; //다음 주변 타일 체크.
}
//닫힘 체크.
bool isClosed = false;
for(auto elementNode : _closeList){
if(elementNode->getTileCnt() == neighborPos){
isClosed = true;
}
}
if(isClosed){
continue; //다음 주변 타일 체크.
}
//--------------------------
// 탐색된 주변타일이 이미 열린 노드 목록에 있는 경우.
// 탐색된 주변 타일 : A, 이미 열린 노드 B.
// A가 B보다 출발 지점에서 가까우면(g값이 작으면),
// 열린 목록에서 B를 제거하고, A를 열린 목록에 추가한다.
// B가 A보다 출발 지점에서 가까우면(g값이 작으면),
// A를 열린 목록에 추가하지 않는다.
//--------------------------
bool isDontOpen = false;
for(auto openedNode : _openList){
if(openedNode->getTileCnt() == neighborPos){
DK_PathFindNode* containNode = DK_PathFindNode::create();
containNode->setAll(currentNode, neighborPos, _destiPos);
//이미 열린 노드가 더 출발지점에서 가까움.
if(openedNode->getG() < containNode->getG()){
isDontOpen = true;
}
//새로 발견된 노드가 출발지점에서 더 가깝거나 동일.
else {
_openList.eraseObject(openedNode);
}
}
}
//새로 발견된 타일을 열지 않음.
if(isDontOpen){
continue; //다음 주변 타일 체크.
}
DK_PathFindNode* neighborNode = DK_PathFindNode::create();
neighborNode->setAll(currentNode, neighborPos, _destiPos);
CCLOG("노드 열림 g, x, y : %d, %.0f, %.0f",
neighborNode->getG(), neighborNode->getTileCnt().x, neighborNode->getTileCnt().y);
neighborNodes.pushBack(neighborNode);
}
_openList.pushBack(neighborNodes);
//열린 노드 없음. 탐색 실패(종료)
if(_openList.size() < 1){
break;
}
//열린 노드에서 가장 작은 F비용을 현재 노드로 선택.
DK_PathFindNode* lowestF_node = nullptr;;
for(auto openElement : _openList){
if (lowestF_node == nullptr) {
lowestF_node = openElement;
}
if (lowestF_node->getF() >= openElement->getF()){
lowestF_node = openElement;
}
}
CCLOG("선택된 노드 f, x, y : %d, %.0f, %.0f", lowestF_node->getF(), lowestF_node->getTileCnt().x, lowestF_node->getTileCnt().y);
currentNode = lowestF_node;
loopCnt++;
}
std::vector<Point> rstVector;
//마지막으로 선택된 노드가 종착노드인가?
if(currentNode->getTileCnt() != _destiPos){
CCLOG("갈 수 없음.");
return rstVector;
}
//마지막에 선택된 노드로부터 부모노드 추적.
std::vector<Point> tempVector;
auto node = currentNode;
CCLOG("탐색된 경로{");
for (int k = 0;
currentNode->getParent()->getTileCnt() != currentNode->getTileCnt();
k++) {
CCLOG("%d - F : %d / pos : %.0f, %.0f",
k, node->getF(), node->getTileCnt().x, node->getTileCnt().y);
tempVector.push_back(node->getTileCnt());
auto parentNode = node->getParent();
if(parentNode->getTileCnt() == node->getTileCnt()){
break;
}
node = parentNode;
}
CCLOG("}탐색된 경로");
//완성된 배열을 거꾸로 저장.
for (int k = 0; k < tempVector.size(); k++)
{
auto item = tempVector.at(tempVector.size()-k-1);
rstVector.push_back(item);
}
return rstVector;
}
|
END.
댓글 없음:
댓글 쓰기