해당 게시글은 제가 구현한 A* 알고리즘 JS 코드에 대한 글입니다.
A* 알고리즘이 무엇인지 궁금하신 분은 다음 게시글을 참고 바랍니다.
A* 알고리즘을 사용한 이유
프로젝트 진행 중 시작 지점과 목표 지점의 좌표가 있고 그 사이에 장애물 좌표가
있는 경우 목표 지점에 도달할 수 있는 최단 경로를 구하는 알고리즘이 필요했습니다.
최단 경로를 찾는 알고리즘으로는 대표적으로 다익스트라와 A* 알고리즘이 있지만
다익스트라 알고리즘은 메모리 사용량과 소요 시간이 커지기 때문에 휴리스틱 함수를 사용해
효율적으로 최적의 경로를 찾을 수 있는 A* 알고리즘을 선택했습니다.
A*알고리즘 만들기
1. 그리드 생성
A* 알고리즘을 만들며 테스트해보기 위해 그때그때 크기를 조절하고
장애물을 생성할 수 있는 그리드를 먼저 만들었습니다.
css
.grid {
display: grid;
grid-template-columns: repeat(10, 30px);
}
.node {
width: 30px;
height: 30px;
border: 1px solid #ccc;
}
.node.start {
background-color: green;
}
.node.end {
background-color: red;
}
.node.obstacle {
background-color: black;
}
.node.visited {
background-color: yellow;
}
html
<h1>A* 알고리즘</h1>
<div class="grid" id="grid"></div>
<button onclick="startAlgorithm()">테스트</button>
js
const ROWS = 10;
const COLS = 10;
const grid = document.getElementById('grid');
const startNode = [0, 0];
const endNode = [ROWS - 1, COLS - 1];
function createGrid() {
for (let i = 0; i < ROWS; i++) {
for (let j = 0; j < COLS; j++) {
const node = document.createElement('div');
node.classList.add('node');
node.dataset.row = i;
node.dataset.col = j;
node.addEventListener('click', toggleObstacle);
grid.appendChild(node);
}
}
document.querySelector(`.node[data-row='${startNode[0]}'][data-col='${startNode[1]}']`).classList.add('start');
document.querySelector(`.node[data-row='${endNode[0]}'][data-col='${endNode[1]}']`).classList.add('end');
}
function toggleObstacle() {
const row = parseInt(this.dataset.row);
const col = parseInt(this.dataset.col);
if (!isEqual([row, col], startNode) && !isEqual([row, col], endNode)) {
this.classList.toggle('obstacle');
}
}
function isEqual(node1, node2) {
return node1[0] === node2[0] && node1[1] === node2[1];
}
function startAlgorithm() {
console.log("테스트 시작")
}
-실행화면-
2. 이웃 노드 찾기와 거리 계산
최단거리 알고리즘의 가장 기본적인 원리는 한 칸 한 칸 이동할 때 비용을 지불한다고 생각하고
내가 시작 지점에서 끝 지점까지 갔을 때 최소 비용으로 가는 방법을 알아내는 것입니다.
그렇기 위해선 내가 움직일 수 있는 이웃 노드를 찾고 해당 노드까지 가는 데에 들어가는
비용을 미리 세팅해줘야 합니다.
isObstacle(row, col)
: 해당 좌표에 장애물이 있는지 확인하는 함수입니다.
function isObstacle(row, col) {
const node = document.querySelector(`.node[data-row='${row}'][data-col='${col}']`);
return node.classList.contains('obstacle');
}
getNeighbors(node)
: 나의 이웃 노드를 찾는 함수입니다.
상하좌우의 노드를 찾으며 나의 그리드를 벗어났는지 장애물이 있는지를 확인합니다.
function getNeighbors(node) {
const neighbors = [];
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dx, dy] of directions) {
const newRow = node[0] + dx;
const newCol = node[1] + dy;
if (newRow >= 0 && newRow < ROWS && newCol >= 0 && newCol < COLS && !isObstacle(newRow, newCol)) {
neighbors.push([newRow, newCol]);
}
}
return neighbors;
}
heuristic(node, endNode)
: 가장 중요한 거리 계산 함수입니다.
저는 간단하게 맨해튼 거리 계산을 사용해 이웃노드와 목표노드의 차이를
절댓값으로 계산해 값이 0에 가까워지면 목표에 가까워진다고 생각했습니다.
function heuristic(node, endNode) {
return Math.abs(node[0] - endNode[0]) + Math.abs(node[1] - endNode[1]);
}
3. 최단 경로 찾기
이제 모든 함수가 준비 됐습니다.
최단 경로를 찾는 aStarAlgorithm 함수는 다음과 같습니다.
변수
openList : 아직 평가하지 않은 노드의 배열 ( 방문하지 않은 노드 )
closedList : 이미 평가된 노드의 배열 ( 방문했거나 비효율적인 노드 )
cameFrom : 경로 추적을 위한 이전 노드를 저장하는 맵
gScore : 시작 노드부터 각 노드까지의 최단 경로로 이동하는 데 걸리는 비용을 나타내는 맵
fScore : 시작 노드를 통해 현재 노드를 거쳐 목표 노드까지 이동하는 예상 비용을 나타내는 맵
알고리즘 프로세스
- 변수 초기화
- gScore 초기화 (모든 노드 무한대 설정 후 시작노드 0 설정)
- fScore 초기화 (모든 노드 무한대 설정 후 시작노드 heuristic 함숫값으로 계산)
- openList에 시작 노드 추가
- 현재 노드의 이웃 노드 탐색
- closeList에 해당 노드가 있는지 (있다면 무시)
- 새로운 gScore를 계산하고 이전 값보다 나은경우 openList에 추가
- 해당 이웃 노드를 최적 경로로 업데이트
- openList를 fScore에 따라 재정렬
- 목표 노드에 도달할 수 없거나 openList가 비어있을 때까지 반복
- 만약 최적의 경로를 찾았을 경우 역추적( reconstructPath )해 경로 얻기
aStarAlgorithm 코드
function aStarAlgorithm() {
const openList = [];
const closedList = new Set();
const cameFrom = {};
const gScore = {};
for (let row = 0; row < ROWS; row++) {
for (let col = 0; col < COLS; col++) {
gScore[`${row},${col}`] = Infinity;
}
}
gScore[startNode.toString()] = 0;
const fScore = {};
for (let row = 0; row < ROWS; row++) {
for (let col = 0; col < COLS; col++) {
fScore[`${row},${col}`] = Infinity;
}
}
fScore[startNode.toString()] = heuristic(startNode, endNode);
openList.push([startNode, fScore[startNode.toString()]]);
while (openList.length > 0) {
const currentNode = openList.shift()[0];
if (currentNode.toString() === endNode.toString()) {
return reconstructPath(cameFrom, endNode);
}
closedList.add(currentNode.toString());
const neighbors = getNeighbors(currentNode);
for (const neighbor of neighbors) {
if (closedList.has(neighbor.toString())) {
continue;
}
const tentativeGScore = gScore[currentNode.toString()] + 1;
if (!openList.some(([node, _]) => node.toString() === neighbor.toString())) {
openList.push([neighbor, tentativeGScore + heuristic(neighbor, endNode)]);
} else if (tentativeGScore >= gScore[neighbor.toString()]) {
continue;
}
cameFrom[neighbor.toString()] = currentNode;
gScore[neighbor.toString()] = tentativeGScore;
fScore[neighbor.toString()] = gScore[neighbor.toString()] + heuristic(neighbor, endNode);
openList.sort((a, b) => fScore[a[0].toString()] - fScore[b[0].toString()]);
}
}
return [];
}
3. 찾은 경로 역추적
위의 방법으로 찾은 노드들의 경로를 역추적해 최단 거리 노드의 배열을 구합니다.
reconstructPath 코드
function reconstructPath(cameFrom, endNode) {
const path = [endNode];
let currentNode = endNode;
while (cameFrom[currentNode.toString()]) {
currentNode = cameFrom[currentNode.toString()];
path.unshift(currentNode);
}
return path;
}
-실행화면-
트러블 슈팅
생각해 보니 가장 중요한 대각선 경로를 생각하지 않았다.
이웃노드에 대각선 경로를 추가하고 휴리스틱 함수로 루트 2 만큼의 비용을 책정했다
다음과 같이 huristic 함수와 getNeighbors 함수를 수정해 주자
function heuristic(node, endNode) {
const dx = Math.abs(node[0] - endNode[0]);
const dy = Math.abs(node[1] - endNode[1]);
return Math.max(dx, dy) + (Math.sqrt(2) - 1) * Math.min(dx, dy);
}
function getNeighbors(node) {
const neighbors = [];
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]];
for (const [dx, dy] of directions) {
const newRow = node[0] + dx;
const newCol = node[1] + dy;
if (newRow >= 0 && newRow < ROWS && newCol >= 0 && newCol < COLS && !isObstacle(newRow, newCol)) {
neighbors.push([newRow, newCol]);
}
}
return neighbors;
}
A*알고리즘 완성
-실행화면-
전체 코드
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>A* Algorithm</title>
<style>
body {
font-family: Arial, sans-serif;
}
.grid {
display: grid;
grid-template-columns: repeat(10, 30px);
}
.node {
width: 30px;
height: 30px;
border: 1px solid #ccc;
}
.node.start {
background-color: green;
}
.node.end {
background-color: red;
}
.node.obstacle {
background-color: black;
}
.node.visited {
background-color: yellow;
}
/* .node.path {
background-color: blue;
} */
</style>
</head>
<body>
<h1>A* 알고리즘</h1>
<div class="grid" id="grid"></div>
<button onclick="startAlgorithm()">테스트</button>
<script>
const ROWS = 10;
const COLS = 10;
const grid = document.getElementById('grid');
const startNode = [0, 0];
const endNode = [ROWS - 1, COLS - 1];
function createGrid() {
for (let i = 0; i < ROWS; i++) {
for (let j = 0; j < COLS; j++) {
const node = document.createElement('div');
node.classList.add('node');
node.dataset.row = i;
node.dataset.col = j;
node.addEventListener('click', toggleObstacle);
grid.appendChild(node);
}
}
document.querySelector(`.node[data-row='${startNode[0]}'][data-col='${startNode[1]}']`).classList.add('start');
document.querySelector(`.node[data-row='${endNode[0]}'][data-col='${endNode[1]}']`).classList.add('end');
}
function toggleObstacle() {
const row = parseInt(this.dataset.row);
const col = parseInt(this.dataset.col);
if (!isEqual([row, col], startNode) && !isEqual([row, col], endNode)) {
this.classList.toggle('obstacle');
}
}
function isEqual(node1, node2) {
return node1[0] === node2[0] && node1[1] === node2[1];
}
function startAlgorithm() {
const visitedNodesInOrder = aStarAlgorithm();
console.log(visitedNodesInOrder);
animateAlgorithm(visitedNodesInOrder);
}
function aStarAlgorithm() {
const openList = [];
const closedList = new Set();
const cameFrom = {};
// 각 노드의 g_score 초기화
const gScore = {};
for (let row = 0; row < ROWS; row++) {
for (let col = 0; col < COLS; col++) {
gScore[`${row},${col}`] = Infinity;
}
}
gScore[startNode.toString()] = 0;
// 각 노드의 f_score 초기화
const fScore = {};
for (let row = 0; row < ROWS; row++) {
for (let col = 0; col < COLS; col++) {
fScore[`${row},${col}`] = Infinity;
}
}
fScore[startNode.toString()] = heuristic(startNode, endNode);
// 시작 노드를 openList에 추가
openList.push([startNode, fScore[startNode.toString()]]);
while (openList.length > 0) {
// openList에서 f_score가 가장 작은 노드를 가져옴
const currentNode = openList.shift()[0];
// 목표 노드에 도달한 경우, 최단 경로를 반환
if (currentNode.toString() === endNode.toString()) {
return reconstructPath(cameFrom, endNode);
}
closedList.add(currentNode.toString());
// 이웃 노드 탐색
const neighbors = getNeighbors(currentNode);
for (const neighbor of neighbors) {
if (closedList.has(neighbor.toString())) {
continue;
}
const tentativeGScore = gScore[currentNode.toString()] + 1;
if (!openList.some(([node, _]) => node.toString() === neighbor.toString())) {
openList.push([neighbor, tentativeGScore + heuristic(neighbor, endNode)]);
} else if (tentativeGScore >= gScore[neighbor.toString()]) {
continue;
}
// 이웃 노드의 최적 경로를 찾은 경우, 경로를 업데이트
cameFrom[neighbor.toString()] = currentNode;
gScore[neighbor.toString()] = tentativeGScore;
fScore[neighbor.toString()] = gScore[neighbor.toString()] + heuristic(neighbor, endNode);
// openList를 f_score로 재정렬
openList.sort((a, b) => fScore[a[0].toString()] - fScore[b[0].toString()]);
}
}
// 목표 노드까지의 경로가 없는 경우
return [];
}
// 휴리스틱 함수: 대각선 이동 고려하여 루트 2의 비용 책정
function heuristic(node, endNode) {
const dx = Math.abs(node[0] - endNode[0]);
const dy = Math.abs(node[1] - endNode[1]);
return Math.max(dx, dy) + (Math.sqrt(2) - 1) * Math.min(dx, dy);
}
// 이웃 노드 찾기
function getNeighbors(node) {
const neighbors = [];
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]];
for (const [dx, dy] of directions) {
const newRow = node[0] + dx;
const newCol = node[1] + dy;
if (newRow >= 0 && newRow < ROWS && newCol >= 0 && newCol < COLS && !isObstacle(newRow, newCol)) {
neighbors.push([newRow, newCol]);
}
}
return neighbors;
}
function isObstacle(row, col) {
const node = document.querySelector(`.node[data-row='${row}'][data-col='${col}']`);
return node.classList.contains('obstacle');
}
// 역추적하여 최단 경로 찾기
function reconstructPath(cameFrom, endNode) {
const path = [endNode];
let currentNode = endNode;
while (cameFrom[currentNode.toString()]) {
currentNode = cameFrom[currentNode.toString()];
path.unshift(currentNode);
}
return path;
}
function animateAlgorithm(visitedNodesInOrder) {
for (let i = 0; i <= visitedNodesInOrder.length; i++) {
if (i === visitedNodesInOrder.length) {
setTimeout(() => {
animatePath();
}, 10 * i);
return;
}
setTimeout(() => {
const node = visitedNodesInOrder[i];
const element = document.querySelector(`.node[data-row='${node[0]}'][data-col='${node[1]}']`);
element.classList.add('visited');
}, 10 * i);
}
}
function animatePath() {
// Animate the shortest path
}
createGrid();
</script>
</body>
</html>
프로젝트에 적용한 모습
728x90
'Programming > JavaScript' 카테고리의 다른 글
| [JavaScript] 원시 타입 VS 객체 타입 ( Primitive VS Object ) (0) | 2024.08.07 |
|---|---|
| [Node] NVM 설치와 사용 (Windows) (1) | 2024.07.22 |
| [JavaScript] 브라우저 밖 알림 기능 (0) | 2024.04.29 |
| [JavaScript] forEach와 map의 차이점 (0) | 2024.04.23 |
| [JavaScript] 한글 파일(.hwp) 양식에 맞춰 출력하기 (0) | 2024.04.19 |
