길찾기 A* 알고리즘...

 

길찾기 알고리즘 공부삼아 만들어봄.

 

https://www.redblobgames.com/pathfinding/a-star/introduction.html

https://qiao.github.io/PathFinding.js/visual/

http://itmining.tistory.com/66

http://blog.naver.com/PostView.nhn?blogId=denoil&logNo=221014139704 ( G값 계산에 대한 설명 )

 

여러 사이트 검색하다가 위 세개를 보고 몇일 파악하고 만듬.

 

 

동작은 잘되는 것은 봤는데...

 

세번째 링크 블로그에 탐색관련 설명중에...

 

3. 인접한 사각형이 이미 '열린 목록'에 있다면 해당 사각형의 비용이 더 좋은지 확인합니다. 즉,선택한 사각형과 비교하여 G점수가 어떤 것이 더 낮은지 확인 합니다. 그렇지 않으면 아무것도 하지 않습니다. 하지만 해당 사각형의 G 비용이 더 낮은 경우 인접 사각형들의 부모를 새로운 사각형으로 바꿉니다. 마지막으로, 그 사각형의 F와 G를 다시 계산합니다. 어렵다면 아래의 실제 작업 과정을 봐주세요.

출처: http://itmining.tistory.com/66 [IT 마이닝]

 

이게 뭔말인지 도저히 모르겠다. 만든걸 스탭별로 확인해봐도 ... 이전노드  대상을 가리키는 화살표라든가 재 계산된 G값이 달라 ...?

 

소스가 잘 못 만들어졌는지 테스트를 해보곤 있는데... 잘되는것 같은뎅..

 

쭉 다시 읽어보고 작업했는데 더 이상해... ( 아무리 해봐도 블로그에 있는 것처럼 안되네... )

 

 

 단, 대각선 <-- 을 지나가게 되어 있어서...

 

 

 

 

 

이렇게 대각선도 찾아간다... 흠...

 

두번째 링크에꺼로 해보면

 

요렇게 비해서 검색을 하네??

 

 

 

일단 이거 수정하고 나면 Flood Fill Path Find 라는 방법으로 해보려고 한다.

음 더 간단해보여서..?

 

소스(숨겨짐)

 

###################################################################################

드디어 고쳤다.

 

 인접한 셀(B)이 검색대상에 이미 있는 거면

현재중심셀(A)을 이용하여 인접한셀(B)의 G값을 임시로 계산해서

인접한 셀(B)의 원래 G값과 임시로 계산한 G값과 비교해서 

임시로 계산한 G값이 작으면 인접한 셀(B)의 이전노드셀을 현재중심셀(A)로 지정한다.