좀비 이동 알고리즘 구현

A* Pathfinding은 3개의 값을 가지고 최적의 경로를 도출해낸다.

 

G = 시작점으로부터 이동한 거리

H = 도착지점까지의 휴리스틱 거리

F = G + H

 

여기서, 자연스러운 이동을 위해 dx, dy도 고려한다.

 

dx = 도착지점까지의 x차

dy = 도착지점까지의 y차

 

Grid 맵이므로 대각선 이동은 연산하지 않는다.

 

휴리스틱 거리는 맨하튼 계산을 사용했다.

int Heuristic(Node node, Node dist) {
	return Math.abs(node.x - dist.x) + Math.abs(node.y - dist.y);
}

 

 

이동경로의 우선순위는 아래와 같이 산출한다.

 

1. F값이 제일 작은 노드

2. F값이 같다면 H값이 더 작은 노드

3. F, H값이 같다면 부모 노드의 dx, dy 중 더 거리가 먼 축에 대해 가까워지는 노드가 우선순위

 

이 때, 칸잡을 방지하려면 아래의 조건도 추가하여야 한다.

 

만약 도착 노드로부터 현재 노드의 dx, dy가 동일하게 1이고, 타겟이 이동중일 때

 

1. 타겟이 X축 방향으로 이동하고 있고, 현재 노드의 y값이 더 작을 때는 x축에 대해 우선 이동

2. 타겟이 Y축 마이너스 방향으로 이동하고 있을 때는 y축에 대해 우선 이동