댓글을 작성하려면 로그인이 필요합니다.
좋은 참고 사이트가 있어서 공유 드립니다! https://qiao.github.io/PathFinding.js/visual/
좋은 정보 감사합니다!! 참고하여 공부하도록 하겠습니다.
A*알고리즘 = Dijkstra + 휴리스틱 정확한 표현입니다. 반대로 표현하자면 Dijkstra 알고리즘은 휴리스틱이 항상 1인 A* 알고리즘이다 라고도 표현합니다. 또한 휴리스틱의 대표적인 3가지 케이스를 소개해주셨지만, 자신의 상황에 따라 휴리스틱의 일부 조정하여 더욱 높은 효율을 구성하는 방법도 고안해볼 수 있습니다.
최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘의 원리를 차용한 것으로 현재 상태의 비용을 g(x), 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 h(x)라고 할 때, 둘을 더한 f(x) = g(x) + h(x)가 최소가 되는 지점을 우선적으로 탐색하는 방법이다.
f(x)가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다.
"NavMesh가 있는데 굳이?" 라고 생각할 수 있다. 하지만 NavMesh는 만능이 아니다.
NavMesh가 어색한 상황들이 분명히 있다. 타일맵 기반의 전략 게임, 절차적으로 생성되는 던전, 2D 격자 이동이 필요한 퍼즐 게임 — 이런 경우엔 NavMesh보다 A*를 직접 구현하는 것이 훨씬 자연스럽다.
커스텀 로직이 필요할 때도 마찬가지다. "적이 불 타일은 피해서 이동", "체력이 낮으면 전투를 우회하는 경로 선택" 같은 조건은 NavMesh의 비용 시스템만으로는 표현하기 어렵다. 원리를 알아야 자유롭게 응용할 수 있다.
디버깅할 때도 원리가 필요하다. NavMesh를 쓰다가 경로가 이상하게 나올 때, 내부 동작을 모르면 원인을 찾기 어렵다. A*의 휴리스틱과 비용 계산 방식을 이해하면 문제를 훨씬 빠르게 파악할 수 있다.
NavMesh는 도구고, A*는 지식이다. 도구는 상황에 따라 바뀌지만, 원리를 알면 어떤 도구든 제대로 쓸 수 있다.
Dijkstra는 "지금까지 비용 g(n)"만 본다.
A*는 "지금까지 비용 g(n) + 목적지까지 예상 비용 h(n)"을 함께 본다.
f(n) = g(n) + h(n)
우선순위 큐에 f(n)을 우선순위로 넣어 "실제로 가까운 + 목적지를 향해 있는" 노드가 먼저 나오게 된다
Admissible(허용 가능): h(n) ≤ 실제 n→goal 비용. 과소평가여야 최적 보장.
격자에서 많이 쓰는 것:
|dx| + |dy| — 상하좌우 이동만 가능한 4방향 격자에 적합. 이 프로젝트가 사용.sqrt(dx² + dy²) — 대각선도 가능할 때.max(|dx|, |dy|) — 8방향 격자.// Dijkstra
pQueue.Enqueue(adjacent, newDistance);
// A*
pQueue.Enqueue(adjacent, newDistance + Heuristic(adjacent, goal));
즉 A는 Dijkstra + 휴리스틱이다.
*Dijkstra는 등고선처럼 사방으로 퍼지고, A**는 목적지를 향해 "길죽하게" 탐색한다.
캐시 미스 횟수 세기
알고리즘 공부는 의외로 문제를 푸는 능력보다 먼저, 계속 풀 수 있게 만드는 환경에서 갈립니다. 처음 알고리즘을 시작하면 보통 이렇게 됩니다. - 오늘은 한 문제 풀었다 - 내일은 못 풀었다 - 일주일 뒤에는 뭘 풀었는지 기억도 안 난다 - 몇 문제를 풀었는지, 어디가 약한지도 감이 안 온다 이때 필요한 건 더 독한 의지가 아니라, 공부가 남는 구조를 먼저
XR을 활용한 게임 개발 3기(유니티) 수강생입니다. 곧 수료 하지만 앞으로 이곳에 가끔 저의 개발 경험이 나 지식 기록할까 합니다. 더 나아가 이 사이트가 제 개인위키의 역할을 할 수 있으면 좋겠습니다. 한국 게임 시장을 흔들겠습니다
