A* 길 찾기 알고리즘은 유니티로 2D 게임을 만들 때도 자주 사용되는 알고리즘이고 포폴에서도 사용했었다.
구글링해서 C# 코드는 금방 찾을 수 있지만 JavaScript 코드는 찾기가 어려웠다.
그래서 단순히 코드 복붙해서 날먹하려는 시도보다는 A* 알고리즘의 원리에 집중해서 새롭게 코드를 작성했다.
1. 우선순위 큐 (Priority Queue)
A* 길찾기 알고리즘에서는 탐색할 다음 노드를 선택할 때, 현재 노드와 연결돼 있는 다음 노드들 중에
비용이 가장 적은 노드를 뽑는 과정을 반복해야한다.
이때마다 노드들을 새로 정렬하거나 가장 적은 노드를 찾는 행위를 다시 한다면
길 찾기 알고리즘의 퍼포먼스가 떨어질 수 있다. 물론 전체 노드의 개수(Grid)가 적다면 큰 차이는 없겠지만.
그래서 대부분 A* 길찾기 알고리즘에서는 오름차순 우선순위 큐를 사용하는데
현재 프로젝트에서 사용하는 EselJS 라이브러리에서는 우선순위 큐를 제공하지 않아서 직접 구현해야 했다.
function PriorityQueue() {
this.items = [];
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
this.enqueue = function(element, priority) {
let queueElement = new QueueElement(element, priority);
if (this.isEmpty()) {
// 큐가 비어있다면 그냥 원소를 push
this.items.push(queueElement);
} else {
// 큐가 비어있지 않다면 기존의 원소와 우선순위를 비교
let added = false;
for (let i = 0; i < this.items.length; i++) {
// 새 원소보다 우선순위가 높은 원소가 있다면, 한 칸 앞에 새 원소를 추가
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}
// 기존 원소들보다 우선순위 낮으면 그냥 push
if (!added) {
this.items.push(queueElement);
}
}
};
// 큐에서 우선순위가 가장 높은 원소 반환
this.dequeue = function() {
return this.items.shift().element;
};
// 큐에서 원소가 존재하는지 확인
this.includes = function(element) {
for (let i = 0; i < this.items.length; ++i) {
if(this.items[i].element === element) return true;
}
return false;
}
// 큐가 비어있는지 확인
this.isEmpty = function() {
return this.items.length === 0;
};
// 큐의 길이 확인
this.size = function() {
return this.items.length;
};
}
당장은 A* 길 찾기 알고리즘에서만 사용할 것이기에 필요한 기능들만 구현했다.
큐에 원소를 넣을 때 우선순위(priority)와 짝지어서 넣어준다.
그리고 원소를 삽입할 때 기존에 들어있던 원소들과 우선순위를 비교해서 넣을 위치를 결정하는 간단한 방식이다.
2. A* 길찾기 알고리즘
function AStarNode(x, y) {
this.x = x;
this.y = y;
this.cost = 0;
this.isWall = true;
this.parentNode = null;
this.neighborNodes = [];
}
function AStarPathFinder() {
this.equal = function(a, b) {
return (a.x === b.x && a.y === b.y);
}
this.heuristic = function(a, b) {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
this.getPath = function(startNode, destNode) {
let openList = new PriorityQueue();
let closeList = [];
// openList에 시작 노드 추가
openList.enqueue(startNode, startNode.cost);
while (openList.size() > 0) {
let currentNode = openList.dequeue();
// 목적지 도착했는지 확인
if (this.equal(currentNode, destNode)) {
let path = [];
path.push(currentNode);
let temp = currentNode;
while (temp.parentNode != null && !path.includes(temp.parentNode)) {
path.push(temp.parentNode);
temp = temp.parentNode;
}
path.reverse();
path.shift(); // 시작 노드는 빼기
return path;
}
// closeList에 현재 노드 추가
closeList.push(currentNode);
// 연결된 노드 방문
let neighborNodes = currentNode.neighborNodes;
for (let i = 0; i < neighborNodes.length; ++i) {
if (closeList.includes(neighborNodes[i]) || neighborNodes[i].isWall) continue;
let cost = currentNode.cost + this.heuristic(currentNode, neighborNodes[i]);
if (cost < neighborNodes[i].cost || !openList.includes(neighborNodes[i])) {
neighborNodes[i].parentNode = currentNode;
neighborNodes[i].cost = cost;
if (!openList.includes(neighborNodes[i])) openList.enqueue(neighborNodes[i]);
}
}
}
return [];
}
}
구현한 실제 코드는 위와 같다.
구글링해서 찾은 C#으로 작성된 코드를 참조해서 JavaScript 문법으로 만든 것이기 때문에
다른 사람과 많이 다르게 구현하지는 않았다.
'JavaScript 게임 활용' 카테고리의 다른 글
CreateJS (0) | 2024.01.25 |
---|---|
숫자 세 자리마다 콤마 찍기 (0) | 2023.04.05 |
아주 심플한 가중치 랜덤 뽑기 (0) | 2022.07.19 |