Game Development

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

A*를 이용하여 길을 찾아 보자 게임에서 사용되되는 알고리즘 중 기초적인 알고리즘 중 하나인 A*를 알아보도록 하겠습니다. [ 참고 ] 이번 포스팅에서는 A*를 구현하는 방식에 대해서 알려드립니다. 전체적인 소스코드는 따로 주어지지 않습니다. 직접 스크립트를 작성해보며 실력을 기르시기 바랍니다. A* 알고리즘 이란 그래서 A*가 어떤 알고리즘 이냐면 현재의 위치에서 목적지 까지의 최단 경로를 구하는 알고리즘 입니다. A*에서는 크게 3가지로 구성 되어 있다고 보시면 됩니다. 1. 현재 노드까지 오는데 필요했던 비용 ( g Cost ) 2. 현재 노드에서 목적지 까지 가는데 필요한 비용 ( h Cost ) 3. 현재 노드에까지 온 비용과 목적지 까지 비용을 합친 비용 ( f Cost ) 위에 있는 3가지의..