기존 에이스타
: fgh를 이용해 4방면을 확인하는 방식으로 진행함.
코드
bool TileMap::astar(vector<POINT>& way, int StartX, int StartY, int EndX, int EndY, int RangeX, int RangeY)
{
if (StartX == EndX && StartY == EndY || m_Tiles[EndX][EndY].State == TILE_STATE::TILE_WALL)
{
way.clear();
way.shrink_to_fit();
return false;
}
int MinIndexX;
int MaxIndexX;
int MinIndexY;
int MaxIndexY;
//
if (StartX < EndX)
{
MinIndexX = StartX - RangeX;
MaxIndexX = EndX + RangeX;
}
else
{
MinIndexX = EndX - RangeX;
MaxIndexX = StartX + RangeX;
}
if (StartY < EndY)
{
MinIndexY = StartY - RangeY;
MaxIndexY = EndY + RangeY;
}
else
{
MinIndexY = EndY - RangeY;
MaxIndexY = StartY + RangeY;
}
MinIndexX = max(0, MinIndexX);
MinIndexY = max(0, MinIndexY);
MaxIndexX = min(m_TileDesc.TileMaxX - 1, MaxIndexX);
MaxIndexY = min(m_TileDesc.TileMaxY - 1, MaxIndexY);
//타일 비용, 길 전부 초기화
way.clear();
way.shrink_to_fit();
for (int i = 0; i < m_TileDesc.TileMaxX; i++)
{
for (int j = 0; j < m_TileDesc.TileMaxY; j++)
{
//INT32_MAX 최대값 사용하여 초기화 하기
//__int64
//__int32
m_TileCost[i][j].F = INT32_MAX;
m_TileCost[i][j].G = INT32_MAX;
m_TileCost[i][j].H = FindH(i, j, EndX, EndY);
m_TileCost[i][j].prevX = INT32_MAX;
m_TileCost[i][j].prevY = INT32_MAX;
m_TileCost[i][j].isCheck = false;
}
}
//처음 시작 타일은 g 비용값이 0이다
m_TileCost[StartX][StartY].G = 0;
int count = 0;
//반복문
while (1)
{
//다 찾아봐도 반복문이 끝나지 않는다면
if (count == (MaxIndexX- MinIndexX)*(MaxIndexY - MinIndexY))
{
way.clear();
way.shrink_to_fit();
return false;
}
count++;
//타일의 g값이 갱신된 상황이라면 F값 만들어 주기
for (int i = MinIndexX; i < MaxIndexX + 1; i++)
{
for (int j = MinIndexY; j < MaxIndexY + 1; j++)
{
if (m_TileCost[i][j].G != INT32_MAX)
m_TileCost[i][j].F = m_TileCost[i][j].H + m_TileCost[i][j].G;
}
}
//f의 최소값을 구한다
POINT MinIndex;
MinIndex.x = INT32_MAX;
MinIndex.y = INT32_MAX;
int minF = INT32_MAX;
for (int i = MinIndexX; i < MaxIndexX + 1; i++)
{
for (int j = MinIndexY; j < MaxIndexY + 1; j++)
{
if (m_Tiles[i][j].State != TILE_STATE::TILE_WALL && !m_TileCost[i][j].isCheck)
{
if (m_TileCost[i][j].F != INT32_MAX && m_TileCost[i][j].F < minF)
{
MinIndex.x = i; MinIndex.y = j;
minF = m_TileCost[i][j].F;
}
}
}
}
//탐색했을때 최소값F가 도착지점이였다면 반복문 종료
if (MinIndex.x == EndX && MinIndex.y == EndY)break;
//최소값이 없는경우
if (minF == INT32_MAX)
{
way.clear();
way.shrink_to_fit();
return false;
}
//최소값F 주변에 g값 갱신
//타일 왼쪽
if (MinIndex.x != 0)
{
//벽은 g값이 갱신되도 최소F탐색때 제외됨
if (m_TileCost[MinIndex.x - 1][MinIndex.y].G >
10 + m_TileCost[MinIndex.x][MinIndex.y].G)
{
m_TileCost[MinIndex.x - 1][MinIndex.y].G =
10 + m_TileCost[MinIndex.x][MinIndex.y].G;
m_TileCost[MinIndex.x - 1][MinIndex.y].prevX = MinIndex.x;
m_TileCost[MinIndex.x - 1][MinIndex.y].prevY = MinIndex.y;
}
}
//타일 오른쪽
if (MinIndex.x < m_TileDesc.TileMaxX - 1)
{
//벽은 g값이 갱신되도 최소F탐색때 제외됨
if (m_TileCost[MinIndex.x + 1][MinIndex.y].G >
10 + m_TileCost[MinIndex.x][MinIndex.y].G)
{
m_TileCost[MinIndex.x + 1][MinIndex.y].G =
10 + m_TileCost[MinIndex.x][MinIndex.y].G;
m_TileCost[MinIndex.x + 1][MinIndex.y].prevX = MinIndex.x;
m_TileCost[MinIndex.x + 1][MinIndex.y].prevY = MinIndex.y;
}
}
//타일 아래쪽
if (MinIndex.y != 0)
{
//벽은 g값이 갱신되도 최소F탐색때 제외됨
if (m_TileCost[MinIndex.x][MinIndex.y - 1].G >
10 + m_TileCost[MinIndex.x][MinIndex.y].G)
{
m_TileCost[MinIndex.x][MinIndex.y - 1].G =
10 + m_TileCost[MinIndex.x][MinIndex.y].G;
m_TileCost[MinIndex.x][MinIndex.y - 1].prevX = MinIndex.x;
m_TileCost[MinIndex.x][MinIndex.y - 1].prevY = MinIndex.y;
}
}
//타일 위쪽
if (MinIndex.y < m_TileDesc.TileMaxY - 1)
{
//벽은 g값이 갱신되도 최소F탐색때 제외됨
if (m_TileCost[MinIndex.x][MinIndex.y + 1].G >
10 + m_TileCost[MinIndex.x][MinIndex.y].G)
{
m_TileCost[MinIndex.x][MinIndex.y + 1].G =
10 + m_TileCost[MinIndex.x][MinIndex.y].G;
m_TileCost[MinIndex.x][MinIndex.y + 1].prevX = MinIndex.x;
m_TileCost[MinIndex.x][MinIndex.y + 1].prevY = MinIndex.y;
}
}
//대각선 스킵
m_TileCost[MinIndex.x][MinIndex.y].isCheck = true;
}
//길 도착지점부터 추가해주기 (시작지점까지)
POINT temp;
temp.x = EndX;
temp.y = EndY;
way.emplace_back(temp);
while (1)
{
POINT temp2;
temp2.x = m_TileCost[temp.x][temp.y].prevX;
temp2.y = m_TileCost[temp.x][temp.y].prevY;
if (temp2.x == StartX && temp2.y == StartY)
{
break;
}
way.emplace_back(temp2);
temp.x = temp2.x;
temp.y = temp2.y;
}
return true;
}-> 그렇다.. 복잡했다.
=> 공부 후, bfs로 개선함.
bfs로 개선하자.
//10.07 에이스타 폴더를 참고하세용~
-
map을 이용해 현재 pos(x,y) 가 어디에서 왔는지 알아야 한다.
map의 경우 pair값을 key값으로 받기 위해서는 class를 따로 만들어 준 상태에서 진행해야 한다. -
상하좌우를 확인하기 위해서 4개 배열을 구성함.
주의할점
1) 이미 한번 통과했음을 알리는 불변수가 필요하다.
2) 조상좌표를 알기위해서 map을 이용해 좌표 두개를 넣어줌
3) 도착지점에 왔다면 반드시 종료처리를 해야한다.
4) 4방면을 확인하기 위한 다음좌표 이동가능 여부 체크하기
bfs 소스코드
//210806 코드 개선
void TileMap::bfs(vector<Pos>& way, int StartX, int StartY, int EndX, int EndY)
{
Pos pos;
pos.x = StartX;
pos.y = StartY;
Pos nextPos[4] = { {0,-1}, {0,1}, {1,0}, {-1,0} };
queue<Pos>q;
q.push({ pos });
//조상이 있어야 하고,
//한번 거친것을 못거치게 인터락 있어야 한다 .
vector<vector<bool>>checked(100, vector <bool>(100, false));
checked[StartX][StartY] = true;
map<Pos, Pos>parent;
parent[pos] = pos;
while (!q.empty())
{
Pos prePos = q.front();
q.pop();
//종료 처리를 반드시 해야한다.
if (prePos.x == EndX && prePos.y == EndY)
break;
for (int i = 0; i < 4; i++)
{
int cmpX = prePos.x + nextPos[i].x;
int cmpY = prePos.y + nextPos[i].y;
//한번 거친 부분 예외처리
if (CanGo(cmpX, cmpY) == false)
continue;
if (checked[cmpX][cmpY] == true)
continue;
//갱신 및 한번 거쳤음을 나타내는 불체크 처리
//조상 값도 추가해야한다.
pos.setPos(cmpX, cmpY);
q.push(pos);
parent[pos] = prePos;
checked[cmpX][cmpY] = true;
}
}
way.clear();
pos.x = EndX;
pos.y = EndY;
while (true)
{
way.emplace_back(pos);
// 시작점은 자신이 곧 부모이다
if (pos == parent[pos])
break;
pos = parent[pos];
}
}
Pos 구조체 코드 부분
여기서 operator < 연산자에서 key값 x값이 같을 경우에는
y값을 이용해 반환하고, 다를 경우에는 x값으로 반환하는 부분이 중요하다.
반대로 작성한다면 원하는 결과가 나온지 않는다.
반환 부분에서 부등호 변경은 상관없다.
struct Pos
{
int x;
int y;
bool operator <(const Pos& other) const
{
//이 부분 중요하다! 여기를 복붙 한거랑 똑같이 하면
//잘못된다.
//키값 동일한지 다른지 여부로 나눈다음
//다를 경우를 처리해야 한다.
//등호로 하면 원하는 결과가 안나온다.
if (other.x != this->x)
return x > other.x;
//키값이 같다면 키값말고 다른 값으로 분류를 하겠다는 뜻이다.
return y > other.y;
}
void setPos(const int &inX, const int &inY)
{
x = inX;
y = inY;
}
bool operator==(Pos& other)
{
return y == other.y && x == other.x;
}
};
https://blog.naver.com/rk9034/221245693559
우선순위 큐를 이용한 aStar 개선
🔥🔥🔥
0개의 댓글
