Jump Point Search 알고리즘 ( C# 소스코드 )

---

Jump Point Search(JPS)를 이용하여 최단 거리를 찾아 봅시다.

실제로 큰 맵을 가진 게임에서 사용되는 JPS 알고리즘에 대해서 알아보도록 하겠습니다.

[ 참고 ]

해당 포스팅에는 JPS 알고리즘을 C#으로 구현한것이 제공됩니다.

JPS알고리즘 말고, JSP(b) 알고리즘, JPS(+) 알고리즘에 대해서도 조금이나마 내용이 나옵니다.

---

JPS 알고리즘 이란

A* 알고리즘을 기반으로 한 알고리즘 중 하나인 JPS 알고리즘 입니다.

JPS 알고리즘은 A*의 문제점인 갈 수 있는 노드들의 휴리스틱 값을 구한후 리스트에 넣어 연산하는 과정에 많은 오버헤드가 발생하여 속도가 느린 것을 보안한 알고리즘입니다.

이름 그대로 Jump Point Search 즉 내가 어디로 점프 해야할 지를 구하여 해당 노드에서만 연산한다는 점으로 A* 알고리즘의 문제점을 해결할 수 있게 되었습니다.

 

Jump Point를 생성하는 규칙은 코너의 여부입니다.

코너의 규칙은 2가지로 직직할 떄와, 대각선으로 이동할때로 나뉩니다.

 

1. 직진 일때 코너를 구하는 방식 ( Ex 오른쪽 방향 )

  1. 현재 방향으로 쭉 직진합니다.

  2. 현재 위치에서 아래가 막혀있고 오른쪽 아래가 막혀있지 않은 경우.

  3. 현재 위치에서 위가 막혀있고 오른쪽 위가 막혀있지 않은 경우.

 

2. 대각선 일때 코너를 구하는 방식 (Ex 오른쪽 위)

  1. 현재 방향으로 쭉 직진합니다.

  2. 현재 위치에서 아래가 막혀있고 오른쪽 아래가 막혀있지 않은 경우.

  3. 현재 위치에서 왼쪽이 막혀있고 왼쪽 위가 막혀있지 않은 경우.

  4. 현재 위치에서 오른쪽 방향과 위쪽 방향을 1번 규칙으로 검사 후 코너가 나왔을 경우 해당 위치에 코너를 생성하지       않고 해당 작업을 진행한 위치에서 노드를 생성.

 

 

4. 현재 위치에서 오른쪽 방향과 위쪽 방향을 1번 규칙으로 검사 후 코너가 나왔을 경우 해당 위치에 코너를 생성하지       않고 해당 작업을 진행한 위치에서 노드를 생성.

 

해당 규칙의 말을 그림으로 설명하자면 아래의 그림입니다. 각 각 대각선을 이동하면서 오른쪽과 위쪽으로 검사를 한번씩 더 해줍니다. 그리고 노드를 발견할 시 해당 노드에서 생성이 아닌 부모노드에서 생성합니다.

 

---

휴리스틱은 무엇을 사용했을까?

JPS에서 사용하는 휴리스틱은 A*에서 사용된 휴리스틱과 동일합니다.

private int Heuristic(Vector2Int _currPosition, Vector2Int _endPosition)
{
    int x = Mathf.Abs(_currPosition.x - _endPosition.x);
    int y = Mathf.Abs(_currPosition.y - _endPosition.y);
    int reming = Mathf.Abs(x - y);

    return MOVE_DIAGONAL_COST * Mathf.Min(x, y) + MOVE_STRAIGHT_COST * reming;
}

---

전체적인 소스코드

소스코드의 길이가 1000줄이 넘어 깃 허브를 통하여 A*와 JPS가 구현되어있는 프로젝트를 올리도록 하겠습니다.

Dev-Owen-Git/Unity_AStar_JPS_Algorithm