• 카테고리

    질문 & 답변
  • 세부 분야

    게임 프로그래밍

  • 해결 여부

    미해결

A* 알고리즘 질문입니다

21.04.07 15:39 작성 조회수 218

0

안녕하세요 강사님

강의를 여러번 돌려보다보니 이해가 안되고 넘어갔었던 부분들도 조금씩 이해가 가고 있는 중입니다

A* 강의를 모두 듣고 궁금한점이 생겨서 질문드립니다

최단 거리가 아니라 방문했었던 모든 길들을 표시해보고싶어서

List<Pos> visitedPoint = new List<Pos>(); 로 리스트를 만들고

마지막에 pq.Push() 부분에서 visitedPoint.Add(new Pos(nextY, nextX)); 로 방문한 자점들을 모두 등록한 후에

플레이어 위치 업데이트 부분에서 visitedPoint 에 있는 좌표를 하나씩 표시하도록 하였는데

처음 예상에는 일단 길이 있는 부분으로 간뒤에 막히면 다시 왔던 길로 돌아간 뒤에 방문하지 않은 쪽으로 이동할 줄 알았는데

미리 예약된(?) 좌표인건지 플레이어의 위치가 이리저리 워프가 되는데 pq노드 안에 등록되었던 예약된 좌표 중에 g+h가 더 적은 위치로 이동이 되는건가요?

그리고 하나더 궁금한게 closed를 이용해서 한번 방문한 지점은 더이상 방문하지 않도록 하였는데

방문했었던 지점도 더 효율적으로 재방문 할수 있을것 같은데 한번만 방문할수 있도록 만들어져있는데 이건 현재 타일맵이라서 작성된 부분일까요?

답변 2

·

답변을 작성해보세요.

0

astrape님의 프로필

astrape

질문자

2021.04.07

답변 감사드립니다!!

0

처음 예상에는 일단 길이 있는 부분으로 간뒤에 막히면 다시 왔던 길로 돌아간 뒤에 방문하지 않은 쪽으로 이동할 줄 알았는데

-> 아닙니다!

미리 예약된(?) 좌표인건지 플레이어의 위치가 이리저리 워프가 되는데 pq노드 안에 등록되었던 예약된 좌표 중에 g+h가 더 적은 위치로 이동이 되는건가요?

-> 이게 맞습니다!

그리고 하나더 궁금한게 closed를 이용해서 한번 방문한 지점은 더이상 방문하지 않도록 하였는데
방문했었던 지점도 더 효율적으로 재방문 할수 있을것 같은데 한번만 방문할수 있도록 만들어져있는데 이건 현재 타일맵이라서 작성된 부분일까요?

-> 타일맵과는 무관하고 알고리즘 자체가 그렇습니다.
이미 방문한 지점을, 뒤늦게 더 효율적으로 재방문할 수 있는 경로를 찾을 수 없다는 것은
수학적 귀납법으로 증명할 수 있습니다.
(예약만 하고 방문은 아직 안 한 시점에서, 뒤늦게 더 효율적인 경로를 찾을 수는 있습니다)
closed를 사용하지 않으면 이미 방문이 끝난 점을
또 다시 pq에 넣고~ 하면서 로직이 꼬이기 때문에 꼭 넣어줘야 합니다.