Game Development

Jump Point Search(JPS)를 이용하여 최단 거리를 찾아 봅시다. 실제로 큰 맵을 가진 게임에서 사용되는 JPS 알고리즘에 대해서 알아보도록 하겠습니다. [ 참고 ] 해당 포스팅에는 JPS 알고리즘을 C#으로 구현한것이 제공됩니다. JPS알고리즘 말고, JSP(b) 알고리즘, JPS(+) 알고리즘에 대해서도 조금이나마 내용이 나옵니다. JPS 알고리즘 이란 A* 알고리즘을 기반으로 한 알고리즘 중 하나인 JPS 알고리즘 입니다. JPS 알고리즘은 A*의 문제점인 갈 수 있는 노드들의 휴리스틱 값을 구한후 리스트에 넣어 연산하는 과정에 많은 오버헤드가 발생하여 속도가 느린 것을 보안한 알고리즘입니다. 이름 그대로 Jump Point Search 즉 내가 어디로 점프 해야할 지를 구하여 해당 노..