[💬] a* 알고리즘 글올린 게이 보셈..

A*는 f cost(시작점부터 현재 노드까지의 비용 + 현재 노드부터 목적지까지 예상비용)가 가장 낮은 노드들을 열고 닫으면서 최적 거리를 찾는 알고리즘임. 이를 위해서 현재노드, open set, close set이 필요함. 현재 노드는 처음에는 start node이고 이후 루프를 돌면서 open set 중에서 가장 f cost가 낮은 노드로 결정되야 함.

(참고로 현재 노드가 되는 순간 open set에서 close set으로 넣어야 함) 그리고 모든 현재 노드의 인접 노드에 대해(이동할 수 있는 노드.. 이 스크립트에서는 상하 좌우로 움직이는 듯 하니 상하 좌우에 해당하는 노드들) 해당 인접 노드의 f cost를 계산하는데 f cost는 현재노드의 출발점으로부터의 비용 + 인접노드의 목적까지의 비용으로 계산함

그리고 인접 노드들을 open set에 추가함. 그리고 open set 중에서 가장 f cost가 가장 낮은 노드를 다시 현재 노드로 설정하면서 경로 저장을 위해 자신 이전의 현재노드를 저장함(길찾기를 하기 위함) 이 과정을 계속 반복하면 최단경로를 계산할 수 있다는 이론임..

open set은 계속 열리고 그 중에서 가장 f cost가 낮은걸 다음으로 설정하면서 open set을 또 열고.. 하다보면 기존에 open set에 속한 애들 중에서도 f cost를 재계산 하면서 f cost가 낮아지는 노드들도 있음

올려놓은 문제의 코드에서 뭐가 문제인지는 직접 굴려보면서 해보지 않으면 완벽히 알 수는 없겠지만 일단 goal까지의 비용은 직선거리를 구할려고 했던 거면 제곱근을 취해야했고, 상하좌우로밖에 못움직이니까 아마 Math.pow를 쓰면 안되고 abs로 절대값을 구해서 x y를 더하는게 맞을듯.

(글고 처음 노드를 오픈셋에 넣어놨기떔에 calc() 호출 전에AddProximityNode(startNode)는 필요없음.. )

우선순위 큐말고 리스트로 open set을 관리하고 그 중에서 f cost가 가장 낮은 노드를 다음 현재 노드로 설정하는 부분이 스크립트에 없네..

글고 인접 노드들의 f cost를 결정하고 open set에 추가할 때, 이미 닫힌 close set에 속하는 노드를 제외하는 부분이 스크립트에 없다. 이러면 닫아 놓은 노드에 대해서도 재연산을 하기 때문에 무한루프에 빠져버린건 이 부분이 문제일거임..

요약하면

1.목적지까지의 거리 비용이 x차이의 제곱 + y차이의 제곱으로 잡혀있어서 문제가 발생할 가능성.

2. queue를 이용해 들어간 순서대로 pop하여 a*의 최단경로 계산 알고리즘의 중요한 개념이 유실됨. queue를 이용하면 a*가 아니라 휴러스틱 알고리즘에 가까운 결과가 나올 것임.. a*를 원한다면 queue 말고 list로 open set을 관리하고 다음 현재노드를 결정할 때 open set에 속한 노드 중 f cost(시작점으로부터의 거리+도착점 까지의 거리)가 가장 낮은 노드를 다음 현재 노드로 결정해야 함.. foreach를 이용해서 openset에 속한 모든 노드중 가장 fcost가 낮은 노드를 쉽게 얻을 수 있음..

3. open set에서 뽑아낸(그리고 close set에 추가한) 현재 노드의 인접 노드에 대해 f cost를 설정해준 뒤 그 인접 노드들이 이동가능한 노드인지 확인하고 open set에 추가하는데, 이후에 다시 현재 노드의 인접 노드들에 대해서 연산할 때 close set에 속한 인접노드들을 다시 한번 계산 대상에 넣고 있음. 이를 제외하지 않으면 이미 close한 노드에 대해서도 연산을 반복하기 때문에 계속 같은 자리를 맴돌게 되며 무한루프는 여기서 발생하는 듯..

일단 말한 부분 수정 해보고 계속 문제가 생기면 다시 말해주셈..

[💬] a* 알고리즘 글올린 게이 보셈..

댓글 2

다른 게시글