A* 알고리즘 질문입니다

Question

안녕하세요 강사님 강의를 여러번 돌려보다보니 이해가 안되고 넘어갔었던 부분들도 조금씩 이해가 가고 있는 중입니다 A* 강의를 모두 듣고 궁금한점이 생겨서 질문드립니다 최단 거리가 아니라 방문했었던 모든 길들을 표시해보고싶어서 List visitedPoint = new List(); 로 리스트를 만들고 마지막에 pq.Push() 부분에서 visitedPoint.Add(new Pos(nextY, nextX)); 로 방문한 자점들을 모두 등록한 후에 플레이어 위치 업데이트 부분에서 visitedPoint 에 있는 좌표를 하나씩 표시하도록 하였는데 처음 예상에는 일단 길이 있는 부분으로 간뒤에 막히면 다시 왔던 길로 돌아간 뒤에 방문하지 않은 쪽으로 이동할 줄 알았는데 미리 예약된(?) 좌표인건지 플레이어의 위치가 이리저리 워프가 되는데 pq노드 안에 등록되었던 예약된 좌표 중에 g+h가 더 적은 위치로 이동이 되는건가요? 그리고 하나더 궁금한게 closed를 이용해서 한번 방문한 지점은 더이상 방문하지 않도록 하였는데 방문했었던 지점도 더 효율적으로 재방문 할수 있을것 같은데 한번만 방문할수 있도록 만들어져있는데 이건 현재 타일맵이라서 작성된 부분일까요?

astrape · Answer

답변 감사드립니다!!

Rookiss · Answer

처음 예상에는 일단 길이 있는 부분으로 간뒤에 막히면 다시 왔던 길로 돌아간 뒤에 방문하지 않은 쪽으로 이동할 줄 알았는데 -> 아닙니다! 미리 예약된(?) 좌표인건지 플레이어의 위치가 이리저리 워프가 되는데 pq노드 안에 등록되었던 예약된 좌표 중에 g+h가 더 적은 위치로 이동이 되는건가요? -> 이게 맞습니다! 그리고 하나더 궁금한게 closed를 이용해서 한번 방문한 지점은 더이상 방문하지 않도록 하였는데 방문했었던 지점도 더 효율적으로 재방문 할수 있을것 같은데 한번만 방문할수 있도록 만들어져있는데 이건 현재 타일맵이라서 작성된 부분일까요? -> 타일맵과는 무관하고 알고리즘 자체가 그렇습니다. 이미 방문한 지점을, 뒤늦게 더 효율적으로 재방문할 수 있는 경로를 찾을 수 없다는 것은 수학적 귀납법으로 증명할 수 있습니다. (예약만 하고 방문은 아직 안 한 시점에서, 뒤늦게 더 효율적인 경로를 찾을 수는 있습니다) closed를 사용하지 않으면 이미 방문이 끝난 점을 또 다시 pq에 넣고~ 하면서 로직이 꼬이기 때문에 꼭 넣어줘야 합니다.