더 복잡한 맵에서의 JPS 구현 테스트 in C++

Sia Lim·2024년 11월 19일

C++Path Searching cpp jps 게임

Path Searching for Game

목록 보기

9/10

이전 글에서 C++에서 구현한 JPS 알고리즘을 시각화했다.

이번에는 좀더 나아가서, 더 복잡한 맵상에서 JPS알고리즘의 동작을 확인해보고자 한다.

더 복잡한 맵 적용

목표

다양한 크기의 맵과 장애물 배치를 테스트.
알고리즘 성능(경로 길이, 시간) 비교.

방법 구상

맵 크기 조절

GRID_ROWS와 GRID_COLS를 동적으로 설정하여 다양한 맵 크기 생성.

랜덤 장애물 배치

장애물을 무작위로 배치하는 함수를 작성.

맵 저장 및 출력

생성된 맵을 파일로 저장하여 재현성을 확보.

랜덤 맵을 동적으로 생성하는 함수

// 랜덤 맵 생성 함수
vector<vector<int>> generateRandomMap(int rows, int cols, int obstacleCount) {
    vector<vector<int>> grid(rows, vector<int>(cols, 0)); // 이동 가능한 빈 맵 초기화
    srand(time(0)); // 랜덤 시드 설정

    while (obstacleCount > 0) {
        int r = rand() % rows;
        int c = rand() % cols;

        if (grid[r][c] == 0) { // 이미 장애물이 없는 곳만 선택
            grid[r][c] = 1; // 장애물 배치
            --obstacleCount;
        }
    }
    return grid;
}

테스트

테스트해보니, 대각선으로 장애물이 가로막고 있는데 이걸 뚫고 지나가버린다.

JPS 알고리즘은 기본적으로 대각선 이동을 허용한다. 하지만, 대각선 이동 시 대각선 양쪽 경로(수평 및 수직)가 모두 장애물로 막혀 있으면 이동이 불가능해야 한다.
점프 함수에서 대각선 이동 시 수평 및 수직 경로의 유효성 검사를 추가해야할 것 같다. JPS가 충돌 검사를 제대로 수행하지 않으면, NPC는 대각선 이동이 불가능한 상황에서도 이렇게 이동해버린다.

JPS jump 알고리즘 수정

JPS.cpp의 jump함수에서 지금은 이런 식으로 대각선 이동을 처리하도록 되어있다.

if (dx != 0 && dy != 0) { // 대각선 이동
    auto next_jump_x = jump(grid, {x, y}, {dx, 0}, goal);
    auto next_jump_y = jump(grid, {x, y}, {0, dy}, goal);

    if (next_jump_x.first != -1 || next_jump_y.first != -1) {
        return {x, y};
    }
}

이 부분을 다음과 같이 수정해보았다.

if (dx != 0 && dy != 0) { // 대각선 이동
    // 수평 및 수직 경로가 모두 유효한지 검사
    if (grid[x - dx][y] == 1 && grid[x][y - dy] == 1) {
        return {-1, -1}; // 대각선 이동 불가
    }

    // 수평 또는 수직 방향의 점프 포인트 확인
    auto next_jump_x = jump(grid, {x, y}, {dx, 0}, goal);
    auto next_jump_y = jump(grid, {x, y}, {0, dy}, goal);

    if (next_jump_x.first != -1 || next_jump_y.first != -1) {
        return {x, y}; // 강제 점프 포인트 발견
    }
}