//
// 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;
}
| 