인프런 커뮤니티 질문&답변

제가 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);
        }