2024-12-27

내일배움캠프 Node.js 트랙 44일차

몬스터 경로 생성하기

타워 디펜스 게임에서 매 라운드마다 몬스터의 공격로를 랜덤하게 생성하고 싶다면 어떻게 코드를 작성해야 할까?어쩌면 미리 맵을 생성하는 방식이 있을 것이고, 좌표로 위아래로 랜덤하게 이동하게 만드는 방식도 있을 것이다.

그런데 만약 게임을 그리드로 나누어서 영역에 따라 경로가 이어져야한다면 어떻게 생성하는 게 가장 효율적일까? 꼬불꼬불한 공격로를 생성하면서도 중복되지 않고 일정 길이를 가지길 바란다면?

 

위와 같은 고민을 하던 중, 같은 트랙을 듣던 어느 재야의 고수로부터 랜덤 워크 이론으로 작성된 코드를 전수 받게 되었다.

랜덤 워크 이론이란?

랜덤 워크 이론이란 주어진 공간에서 매 순간 랜덤으로, 즉 확률적으로 이동하는 모습을 수학적으로 표현한 것이다. 이걸 코드로 나타내보자면 아래와 같다.

function generatePath(start, end) {
    const path = [];
    const visited = new Set(); // 방문한 좌표를 저장하는 Set
    let currentX = start.x;
    let currentY = start.y;

    // 시작점 추가
    path.push({ x: currentX, y: currentY });
    visited.add(`${currentX},${currentY}`); // 방문한 좌표 추가

    // 이동 가능한 방향 (상하좌우)
    const directions = [
        { x: 1, y: 0 },   // 오른쪽
        { x: -1, y: 0 },  // 왼쪽
        { x: 0, y: 1 },   // 위쪽
        { x: 0, y: -1 }   // 아래쪽
    ];

    // 경로 생성
    while (currentX !== end.x || currentY !== end.y) {
        const possibleMoves = directions
            .map(dir => ({
                x: currentX + dir.x,
                y: currentY + dir.y
            }))
            .filter(move =>
                !visited.has(`${move.x},${move.y}`) && // 방문하지 않은 좌표
                move.x >= Math.min(start.x, end.x) && move.x <= Math.max(start.x, end.x) && // x 범위 체크
                move.y >= Math.min(start.y, end.y) && move.y <= Math.max(start.y, end.y) // y 범위 체크
            );

        if (possibleMoves.length === 0) {
            // 더 이상 이동할 수 없으면 종료
            break;
        }

        // 무작위로 가능한 이동 중 선택
        const nextMove = possibleMoves[Math.floor(Math.random() * possibleMoves.length)];
        currentX = nextMove.x;
        currentY = nextMove.y;

        // 경로에 추가
        path.push({ x: currentX, y: currentY });
        visited.add(`${currentX},${currentY}`); // 방문한 좌표 추가
    }

    return path;
}

function drawPathInConsole(start, end, path) {
    const gridWidth = Math.max(start.x, end.x) + 1; // 그리드의 너비
    const gridHeight = Math.max(start.y, end.y) + 1; // 그리드의 높이
    const grid = Array.from({ length: gridHeight }, () => Array(gridWidth).fill('■')); // 'ㄱ'으로 채운 2D 배열 생성

    // 경로를 그리드에 표시
    path.forEach(point => {
        grid[point.y][point.x] = '□'; // 경로를 'ㅇ'으로 표시
    });

    // 그리드를 콘솔에 출력
    grid.forEach(row => {
        console.log(row.join(' ')); // 각 행을 출력
    });
}

// 사용 예시
const startPoint = { x: 0, y: 0 };
const endPoint = { x: 5, y: 5 };

const generatedPath = generatePath(startPoint, endPoint);
console.log("Generated Path:", generatedPath);
drawPathInConsole(startPoint, endPoint, generatedPath);

차근차근 로직을 살펴보면서 이 코드를 어떻게 타워디펜스에 적용할 수 있을지 설명해보도록 하겠다.

(1) 기본적인 변수 선언

const path = [];
const visited = new Set(); // 방문한 좌표를 저장하는 Set
let currentX = start.x;
let currentY = start.y;

// 시작점 추가
path.push({ x: currentX, y: currentY });
visited.add(`${currentX},${currentY}`); // 방문한 좌표 추가

// 이동 가능한 방향 (상하좌우)
const directions = [
        { x: 1, y: 0 },   // 오른쪽
        { x: -1, y: 0 },  // 왼쪽
        { x: 0, y: 1 },   // 위쪽
        { x: 0, y: -1 }   // 아래쪽
];

• 먼저 몬스터의 공격로를 좌표로 변환하여 배열에 담기 위해 path 변수를 선언해주었다.
• 그리고 이미 지나간 좌표를 또 지나가는 걸 막기 위해 Set 또한 선언했다.
• 시작점을 함수의 인자로 받아와서 첫 좌표로 path 배열에 push해준 뒤, visited Set에도 추가해주었다.
• 그럼 이제 시작점에서 어디로 갈지 결정할 차례다. 그리드 형식이므로 게임을 구현할 계획이므로 상하좌우로만 이동할 수 있게끔 directions를 정의했다.(필요에 따라서 대각선 이동도 추가할 수 있을 것이다.)

(2) 랜덤한 경로 생성

    // 경로 생성
    while (currentX !== end.x || currentY !== end.y) {
        const possibleMoves = directions
            .map(dir => ({
                x: currentX + dir.x,
                y: currentY + dir.y
            }))
            .filter(move =>
                !visited.has(`${move.x},${move.y}`) && // 방문하지 않은 좌표
                move.x >= Math.min(start.x, end.x) && move.x <= Math.max(start.x, end.x) && // x 범위 체크
                move.y >= Math.min(start.y, end.y) && move.y <= Math.max(start.y, end.y) // y 범위 체크
            );

        if (possibleMoves.length === 0) {
            // 더 이상 이동할 수 없으면 종료
            break;
        }

        // 무작위로 가능한 이동 중 선택
        const nextMove = possibleMoves[Math.floor(Math.random() * possibleMoves.length)];
        currentX = nextMove.x;
        currentY = nextMove.y;

        // 경로에 추가
        path.push({ x: currentX, y: currentY });
        visited.add(`${currentX},${currentY}`); // 방문한 좌표 추가
    }

    return path;
}

이제 이동 가능한 경로를 탐색하면서 path를 만든다.(중복 방문 불가, 범위 내에서 이동이 조건) return하는 경우는 딱 두 가지인데, 하나는 endpoint에 도달하는 것이고 다른 하나는 더 이상 이동할 수 있는 경로가 없을 때다.
이제 drawPathInConsole()을 이용해서 생성한 경로를 콘솔에 그려보면 아래와 같이 나온다. (물론 실행할 때마다 결과는 달라진다.)

 

이것만으로도 충분히 게임에 쓸 순 있겠지만 타워 디펜스라는 장르적 관점에서 보면 다소 아쉽다. 공격로가 꺾이는 지점에 공격 타워를 세울 수 있다면 훨씬 타워 디펜스다운 맵이 생성될 테니 말이다.

로직 입맛대로 변경하기

그래서 아래와 같은 방식으로 로직에 변형을 추가했다.

// 경로 생성
while (path.length < minlength) {
    const possibleMoves = directions
        .map((dir) => ({
            dir,
            mid: { x: currentX + dir.x, y: currentY + dir.y }, // 중간 좌표
            final: { x: currentX + dir.x * 2, y: currentY + dir.y * 2 }, // 최종 좌표
        }))
        .filter(
            (move) =>
                !visited.has(`${move.mid.x},${move.mid.y}`) && // 중간 좌표 미방문
                !visited.has(`${move.final.x},${move.final.y}`) && // 최종 좌표 미방문
                move.final.x >= Math.min(start.x, end.x) &&
                move.final.x <= Math.max(start.x, end.x) && // x 범위 체크
                move.final.y >= Math.min(start.y, end.y) &&
                move.final.y <= Math.max(start.y, end.y), // y 범위 체크
        );
        if (possibleMoves.length === 0) {
    // 더 이상 이동할 수 없는 경우 경로를 재생성
    return generatePath(start, end, minlength);
}

아이디어는 간단했다. 방향을 한 번 정하면 반드시 두 칸을 움직여야 한다는 것. 목표 좌표를 mid와 final로 구분해서 두 좌표 모두 중복되지 않도록 조건식을 작성하였다.
또 while문(path.length < minlength)과 재귀문(return generatePath(start, end, minlength);)을 추가해서 특정 길이 이상의 경로만을 return하도록 설정했다.

 

결과물