• 카테고리

    질문 & 답변
  • 세부 분야

    게임 프로그래밍

  • 해결 여부

    해결됨

Astar open 배열에 관하여 질문있습니다.

21.12.28 18:04 작성 조회수 184

0

항상 좋은 강의 잘 듣고 있습니다.

다름이 아니라 Astar 알고리즘에 대해서 복습하던 중 궁금한 점이 생겨 질문드리게 되었습니다.

 

Astar 알고리즘에서 open 배열과 우선순위 큐를 사용하셨는데, 우선순위 큐를 사용하면 open 배열 없이도 구현할 수 있지 않나요?

 

조금 코드를 변형시켜 open 배열 없이

다음과 같이 구현해 보았습니다.

open배열을 사용하는것에 대한 장점이 따로 있을까요?

 

        void AStar() 
        {
            // U L D R UL DL DR UR
            int[] deltaY = new int[] { -1, 0, 1, 0, -1, 1, 1, -1 };
            int[] deltaX = new int[] { 0, -1, 0, 1, -1, -1, 1, 1 };
            int[] cost = new int[] { 10, 10, 10, 10, 14, 14, 14, 14 };
           
            bool[,] closed = new bool[_board.Size,_board.Size]; 

            // 삭제
            //int[,] open = new int[_board.Size, _board.Size]; // OpenList
            //for (int y = 0; y < _board.Size; y++)
            //    for (int x = 0; x < _board.Size; x++)
            //       open[y, x] = Int32.MaxValue;

            Pos[,] parent = new Pos[_board.Size, _board.Size];

            PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();
            
            //open[PosY, PosX] = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX));

            //PQNode에 parent 추가
            pq.Push(new PQNode() { F = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX)), G = 0, Y = PosY, X = PosX, parent= new Pos(PosY, PosX)});


            while (pq.Count > 0)
            {

                PQNode node = pq.Pop();
                if (closed[node.Y, node.X])
                    continue;

                closed[node.Y, node.X] = true;
                //추가
                parent[node.Y, node.X] = node.parent;

                if (node.Y == _board.DestY && node.X == _board.DestX)
                    break;
                for (int i = 0; i < deltaY.Length; i++)
                {
                    int nextY = node.Y + deltaY[i];
                    int nextX = node.X + deltaX[i];

                    if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
                        continue;

                    if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
                        continue;

                    if (closed[nextY, nextX])
                        continue;

                    int g = node.G + cost[i];
                    int h = 10 * (Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX));

                    //삭제
                    //if (open[nextY, nextX] < g + h)
                    //    continue;

                    //삭제
                    //open[nextY, nextX] = g + h; 
                    pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX, parent = new Pos(node.Y, node.X) }); //parent 추가
                    
                }
            }
            CalcPathFromParent(parent);
        }

읽어주셔서 감사합니다.

답변 1

답변을 작성해보세요.

1

네 예리하게 분석하셨는데 PriorityQueue가 openList를 겸하게 할 수도 있습니다.
로직이 미세하게 달라지는데 결과적으로는 어차피
closed 배열을 확인하니 중복해서 같은 점을 2번 체크하진 않긴 합니다.
경우에 따라 PQ에 넣기 전에 open 배열을 먼저
체크해서 걸러주는 것이 성능에 유리할 수도 있긴 합니다.