우선순위 큐

A* 길 찾기 알고리즘

A* 길 찾기 알고리즘은 유니티로 2D 게임을 만들 때도 자주 사용되는 알고리즘이고 포폴에서도 사용했었다. 구글링해서 C# 코드는 금방 찾을 수 있지만 JavaScript 코드는 찾기가 어려웠다. 그래서 단순히 코드 복붙해서 날먹하려는 시도보다는 A* 알고리즘의 원리에 집중해서 새롭게 코드를 작성했다. 1. 우선순위 큐 (Priority Queue) A* 길찾기 알고리즘에서는 탐색할 다음 노드를 선택할 때, 현재 노드와 연결돼 있는 다음 노드들 중에 비용이 가장 적은 노드를 뽑는 과정을 반복해야한다. 이때마다 노드들을 새로 정렬하거나 가장 적은 노드를 찾는 행위를 다시 한다면 길 찾기 알고리즘의 퍼포먼스가 떨어질 수 있다. 물론 전체 노드의 개수(Grid)가 적다면 큰 차이는 없겠지만. 그래서 대부분 A..