-
카테고리
-
세부 분야
게임 프로그래밍
-
해결 여부
미해결
실수한 부분에서 나온 증상에 대한 이해
21.01.14 05:31 작성 조회수 118
0
제가 parent[nextY, nextX] = new Pos(node.Y, node.X) 대신에 PosY, PosX를 집어 넣으니까
뭔가 맵이 폭포스마냥 계속 업데이트 되는걸로 보이던데
이게 모든 점의 부모점을 시작점으로 해버려서 진행도 못하고 그자리에서 멤돌기 때문에 생기는거죠?
public void Astar()
{
// the delta values when moving towards Up, Left, Down, Right
int[] deltaY = { -1, 0, 1, 0 };
int[] deltaX = { 0, -1, 0, 1 };
int[] cost = { 1, 1, 1, 1 };
// Giving points depending on how close the player is to the destination
// F = G + H
// F = Final Score (the smaller, the better. Varying depending on the route)
// G = the cost to move from the start to the destination (the smaller, the better. Varying depending on the route)
// H = the distance from the current position and the destination, without ignoring any obstacles (the smaller, the better. Fixed)
// the status whether a coordinate has been visited (visited = closed)
bool[,] closed = new bool[_board.Size, _board.Size]; // ClosedList (List can be used as well)
// the status whether a route to (y, x) has been found (Gigving score)
// not found -> Int32.Max
// found -> F = G + H
int[,] open = new int[_board.Size, _board.Size]; // OpenList (which has the scores on each coordinate)
// Initialize OpenList
for (int y = 0; y < _board.Size; y++)
for (int x = 0; x < _board.Size; x++)
open[y, x] = Int32.MaxValue;
// an Array to track the parent nodes
Pos[,] parent = new Pos[_board.Size, _board.Size];
// Use PriorityQueue, which is specialized to pick up the best case
// a tool to pick up the best candidate from OpenList
PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();
// Found Start (Reservation begins) // Log and give the score to the coordinate
open[PosY, PosX] = 0 + Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX); // : G == 0; H = the distance from Start to Destination
pq.Push(new PQNode() { F = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX), G = 0, Y = PosY, X = PosX });
parent[PosY, PosX] = new Pos(PosY, PosX); // parent of Start is itself
while (pq.Count > 0)
{
// Find out the best candidate
PQNode node = pq.Pop();
// Skip if a coordinate has been visited(clsoed) with a faster route, while finding out routes to the same coordinate
if (closed[node.Y, node.X])
continue;
// Visit saying this coordinate won't visited again
closed[node.Y, node.X] = true;
// Quit if reached the destination
if (node.Y == _board.DestY && node.X == _board.DestX)
break;
// Reserve(Open) the coordinates by verifying if they are available to move to
for (int i = 0; i < deltaY.Length; i++)
{
int nextY = node.Y + deltaY[i];
int nextX = node.X + deltaX[i];
// Skip when the coordinate is out of the boundary
if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
continue;
// Skip when the coordinate is Wall
if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
continue;
if (closed[nextY, nextX])
continue
// Evalutate the cost
int g = node.G + cost[i]; // the cost to move to the next coordinate
int h = Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX); // the distance from the current position to the destination
// Skip when a btter route is found
if (open[nextY, nextX] < g + h)
continue;
open[nextY, nextX] = g + h; // Put the calculated score
pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX }); // input the coordinate to the Priority Queue
parent[nextY, nextX] = new Pos(PosY, PosX); // the parent node of the next coordinate is the current node, which is the fastest one (verified by going through the filters above)
}
}
// retrieve the path by follwing the parent nodes inversly
CalculatePathFromParent(parent);
}
답변을 작성해보세요.
0
0
Rookiss
지식공유자2021.01.14
parent 배열이 [내가 어디서 왔는지]를 추적하기 위해 관리하는건데,
데이터가 잘못 들어가는 바람에
시작 좌표 -> 종료 좌표로 바로 이동한 것으로 인식되어서 발생한 문제입니다.
시작/끝으로 순간이동하고 끝나니 바로 맵을 랜덤으로 바꾸기 때문에 그렇게 보이는겁니다.
이런 문제는 사실 CalcFromParent에 브레이크 포인트를 걸고 타고 들어가서
살펴보는게 가장 정확합니다.
답변 2