좀비 이동 알고리즘 [2]

좀비고의 이동 알고리즘은 꽤 특이하다.

 

다음과 같은 맵에서 S -> E로 경로를 찾아간다고 가정하겠다.

 

보통의 A* 알고리즘을 사용한다면 경로는 이렇게 된다.

 

( 사진1 )

하지만 좀비고에서는 이렇게 이동하지 않는다.

 

best next path 우선순위 설정에 따라 달라질수도 있지만, 원하는 좀비 이동 로직은 나오지 않는다.

 

( 사진2 )

좀비고에서는 아마 이렇게 이동할 것이다.

 

일반적인 A* 알고리즘으로는 재현이 안되는 이유는, 좀비고의 로직은 거리의 dx, dy값을 알고리즘에 반영해서 이동하기 때문이다.

 

사진1 과 사진2 는 이동에 드는 cost가 동일하다.

 

어느 경로를 택하더라도 이동에 걸리는 시간은 동일하므로, 사진2 의 경로가 선택되지 않는다.

 

동일한 cost가 드는 next nodes중에서 dx, dy 중 더 높은 수치에 대해 최적의 값을 추가적으로 계산해준다면 좀비고의 이동 알고리즘과 동일하게 이동한다.