JPS in C++ 시각화

Sia Lim·2024년 11월 18일
CPath Searchingcppjps게임경로 탐색
0

Path Searching for Game

목록 보기
8/10
post-thumbnail

JPS 알고리즘을 C++로 구현하기에서 이어서, 이 JPS 알고리즘을 통해 간단한 2D 맵에서 NPC가 경로를 따라 이동하는 것을 시각적으로 구현해보고자 한다.

C++에서 2D 맵 시각화를 구현하는 방법은, 주로 SFML (Simple and Fast Multimedia Library) 또는 SDL (Simple DirectMedia Layer) 같은 멀티미디어 라이브러리를 사용하여 그래픽을 표시함으로써 해볼 수 있을 것 같다. 이 포스팅에서 일단은 SFML을 사용하여 2D 시각화를 시도해보고자 한다.

Mac OS에서 SFML 설치 및 사용은 이 깃허브 링크를 참고했다.

C++와 SFML을 활용한 2D 맵 시각화

목표

  • SFML 창에서 2D 맵 표시
  • NPC가 경로를 따라 이동하며, 장애물과 이동 가능한 공간을 구분

1. JPS 알고리즘의 결과를 SFML 시각화 코드에 통합하기

이 과정을 위해 먼저 JPS.h 라는 사용자 헤더 파일을 만들었다.

#ifndef JPS_H
#define JPS_H

#include <vector>
#include <utility> // for std::pair

using namespace std;

// === JPS 알고리즘 함수 선언 ===
vector<pair<int, int>> jps(const vector<vector<int>>& grid, pair<int, int> start, pair<int, int> goal);

#endif // JPS_H

JPS.h 파일 설명

  1. 헤더 가드

    • #ifndef JPS_H, #define JPS_H, #endif는 헤더 파일이 여러 번 포함되더라도 중복 정의되지 않도록 방지한다.

  2. 필요한 라이브러리 포함

    • #include <vector> : 2D 맵과 경로를 저장하기 위해 사용.
    • #include <utility> : std::pair 사용.

  3. jps 함수 선언

    • jps 함수는 JPS 알고리즘의 메인 함수로, 구현부는 JPS.cpp에 작성되며 헤더 파일에서는 선언만 포함한다.

  4. 네임스페이스

    • using namespace std

2. JPS.cpp 파일 수정

기존 JPS.cpp에 다음과 같이 사용자 정의 헤더파일 JPS.h를 추가한다.

#include "JPS.h"
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <algorithm>

...

(+) 그리고 JPS.cpp 안의 main 함수는 주석 처리해야 충돌이 생기지 않는다

3. main.cpp 생성

프로젝트 구조

Project/
├── JPS.h       // JPS 헤더 파일
├── JPS.cpp     // JPS 알고리즘 구현
├── main.cpp    // SFML 시각화 및 프로그램 실행

main.cpp 전체 코드

#include "JPS.h"
#include <SFML/Graphics.hpp>
#include <vector>
#include <thread>
#include <chrono>


using namespace std;

const int CELL_SIZE = 50;
const int GRID_ROWS = 5;
const int GRID_COLS = 5;

// 맵 데이터
vector<vector<int>> grid = {
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 0, 0},
    {0, 0, 0, 0, 0}
};

pair<int, int> start = {0, 0};
pair<int, int> goal = {4, 4};

void drawGrid(sf::RenderWindow& window) {
    for (int row = 0; row < GRID_ROWS; ++row) {
        for (int col = 0; col < GRID_COLS; ++col) {
            sf::RectangleShape cell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
            cell.setPosition(col * CELL_SIZE, row * CELL_SIZE);

            if (grid[row][col] == 1) {
                cell.setFillColor(sf::Color::Black);
            } else {
                cell.setFillColor(sf::Color::White);
            }

            cell.setOutlineThickness(1);
            cell.setOutlineColor(sf::Color(200, 200, 200));
            window.draw(cell);
        }
    }
}

void animatePath(sf::RenderWindow& window, const vector<pair<int, int>>& path) {
    for (auto pos : path) {
        int row = pos.first;
        int col = pos.second;

        // 화면 초기화 및 맵 재그리기
        window.clear(sf::Color::White); // 화면 초기화
        drawGrid(window);              // 맵 다시 그리기

        // 시작점과 목표점 다시 그리기
        sf::RectangleShape startCell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        startCell.setPosition(start.second * CELL_SIZE, start.first * CELL_SIZE);
        startCell.setFillColor(sf::Color::Blue);
        window.draw(startCell);

        sf::RectangleShape goalCell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        goalCell.setPosition(goal.second * CELL_SIZE, goal.first * CELL_SIZE);
        goalCell.setFillColor(sf::Color::Red);
        window.draw(goalCell);

        // NPC 경로 표시
        sf::RectangleShape cell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        cell.setPosition(col * CELL_SIZE, row * CELL_SIZE);
        cell.setFillColor(sf::Color::Green);
        cell.setOutlineThickness(1);
        cell.setOutlineColor(sf::Color(200, 200, 200));
        window.draw(cell);

        // 화면 업데이트
        window.display();

        // 이동 속도 조절
        this_thread::sleep_for(chrono::milliseconds(500));
    }
}


int main() {
    sf::RenderWindow window(sf::VideoMode(GRID_COLS * CELL_SIZE, GRID_ROWS * CELL_SIZE), "JPS Visualization");

    while (window.isOpen()) {
        sf::Event event;
        while (window.pollEvent(event)) {
            if (event.type == sf::Event::Closed) {
                window.close();
            }
        }

        // 맵 그리기
        window.clear(sf::Color::White);
        drawGrid(window);

        // 시작점과 목표점 표시
        sf::RectangleShape startCell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        startCell.setPosition(start.second * CELL_SIZE, start.first * CELL_SIZE);
        startCell.setFillColor(sf::Color::Blue);
        window.draw(startCell);

        sf::RectangleShape goalCell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        goalCell.setPosition(goal.second * CELL_SIZE, goal.first * CELL_SIZE);
        goalCell.setFillColor(sf::Color::Red);
        window.draw(goalCell);

        // JPS 알고리즘 실행 및 경로 시각화
        vector<pair<int, int>> path = jps(grid, start, goal);
        animatePath(window, path);

        window.display();
        break; // 애니메이션 후 종료
    }

    return 0;
}

main.cpp 코드 상세 설명

(1) 라이브러리

#include <SFML/Graphics.hpp>
#include <vector>
#include <thread>
#include <chrono>
#include "JPS.h" // JPS 알고리즘 헤더 파일 포함
  • #include <SFML/Graphics.hpp>
    • SFML의 그래픽 관련 기능을 사용하기 위해 포함.
    • 창 생성, 도형 그리기, 화면 업데이트 등의 기능 제공.
  • #include <vector>
    • C++ STL의 벡터 자료구조를 사용하기 위해 포함. 2D 맵, 경로 등을 저장.
  • #include <thread>와 #include <chrono>
    • 스레드와 시간 지연 기능을 사용하여 NPC가 이동할 때 애니메이션 속도를 조절.
  • #include "JPS.h"
    • 위에서 구현한 JPS 알고리즘 헤더 파일. 이 파일에서 JPS 함수를 선언하고 사용.

(2) 상수 및 변수 정의

const int CELL_SIZE = 50;
const int GRID_ROWS = 5;
const int GRID_COLS = 5;

vector<vector<int>> grid = {
    {0, 0, 0, 0, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0},
    {0, 1, 0, 0, 0},
    {0, 0, 0, 0, 0}
};

pair<int, int> start = {0, 0};
pair<int, int> goal = {4, 4};
  • CELL_SIZE
    • 각 셀의 크기(픽셀 단위)를 정의. 여기서는 50x50 픽셀로 설정.
  • GRID_ROWS와 GRID_COLS
    • 맵의 행과 열 개수를 정의. 현재 5x5 크기의 맵.
  • grid
    • 2D 벡터로 맵을 정의.
    • 0: 이동 가능한 공간.
    • 1: 장애물.
  • start와 goal
    • NPC의 시작점과 목표점을 나타내는 좌표 (행, 열).
    • pair<int, int>은 두 개의 정수를 하나의 쌍으로 묶어 저장하는 자료구조.

(3) 맵 그리기 함수

void drawGrid(sf::RenderWindow& window) {
    for (int row = 0; row < GRID_ROWS; ++row) {
        for (int col = 0; col < GRID_COLS; ++col) {
            sf::RectangleShape cell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
            cell.setPosition(col * CELL_SIZE, row * CELL_SIZE);

            if (grid[row][col] == 1) {
                cell.setFillColor(sf::Color::Black);
            } else {
                cell.setFillColor(sf::Color::White);
            }

            cell.setOutlineThickness(1);
            cell.setOutlineColor(sf::Color(200, 200, 200));
            window.draw(cell);
        }
    }
}
  • drawGrid
    • grid 배열을 사용해 맵을 창에 그립니다.
  • sf::RectangleShape
    • 사각형(각 셀)을 표현하는 SFML 클래스.
    • sf::Vector2f(CELL_SIZE, CELL_SIZE)로 셀 크기 지정.
  • setPosition
    • 셀의 위치를 설정.
    • 열(col)과 행(row)에 따라 위치를 계산.
  • 셀 색상
    • 장애물(grid[row][col] == 1): 검은색.
    • 이동 가능한 셀(grid[row][col] == 0): 흰색.
  • 셀 테두리
    • setOutlineThickness(1)으로 테두리 두께 설정.
    • setOutlineColor로 테두리 색상 지정.

(4) 애니메이션 함수

void animatePath(sf::RenderWindow& window, const vector<pair<int, int>>& path) {
    for (auto pos : path) {
        int row = pos.first;
        int col = pos.second;

        // 화면 초기화 및 맵 재그리기
        window.clear(sf::Color::White); // 화면 초기화
        drawGrid(window);              // 맵 다시 그리기

        // 시작점과 목표점 다시 그리기
        sf::RectangleShape startCell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        startCell.setPosition(start.second * CELL_SIZE, start.first * CELL_SIZE);
        startCell.setFillColor(sf::Color::Blue);
        window.draw(startCell);

        sf::RectangleShape goalCell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        goalCell.setPosition(goal.second * CELL_SIZE, goal.first * CELL_SIZE);
        goalCell.setFillColor(sf::Color::Red);
        window.draw(goalCell);

        // NPC 경로 표시
        sf::RectangleShape cell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        cell.setPosition(col * CELL_SIZE, row * CELL_SIZE);
        cell.setFillColor(sf::Color::Green);
        cell.setOutlineThickness(1);
        cell.setOutlineColor(sf::Color(200, 200, 200));
        window.draw(cell);

        // 화면 업데이트
        window.display();

        // 이동 속도 조절
        this_thread::sleep_for(chrono::milliseconds(500));
    }
}
  • animatePath
    • path에 저장된 좌표를 따라 NPC를 이동.
    • 각 이동 후 창을 업데이트(window.display).
  • 화면 초기화
    • window.clear로 이전 화면 제거.
    • drawGrid로 맵과 장애물 다시 그림.
  • 현재 위치 표시
    • cell.setFillColor(sf::Color::Green)으로 NPC의 현재 위치를 녹색으로 표시.
  • 속도 조절
    • this_thread::sleep_for(chrono::milliseconds(500))로 이동 속도 조절.

(5) 메인 함수

int main() {
    sf::RenderWindow window(sf::VideoMode(GRID_COLS * CELL_SIZE, GRID_ROWS * CELL_SIZE), "JPS Visualization");

    while (window.isOpen()) {
        sf::Event event;
        while (window.pollEvent(event)) {
            if (event.type == sf::Event::Closed) {
                window.close();
            }
        }

        // 맵 그리기
        window.clear(sf::Color::White);
        drawGrid(window);

        // 시작점과 목표점 표시
        sf::RectangleShape startCell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        startCell.setPosition(start.second * CELL_SIZE, start.first * CELL_SIZE);
        startCell.setFillColor(sf::Color::Blue);
        window.draw(startCell);

        sf::RectangleShape goalCell(sf::Vector2f(CELL_SIZE, CELL_SIZE));
        goalCell.setPosition(goal.second * CELL_SIZE, goal.first * CELL_SIZE);
        goalCell.setFillColor(sf::Color::Red);
        window.draw(goalCell);

        // JPS 알고리즘 실행 및 경로 시각화
        vector<pair<int, int>> path = jps(grid, start, goal);
        animatePath(window, path);

        window.display();
        break; // 애니메이션 후 종료
    }

    return 0;
}
  • sf::RenderWindow
    • SFML 창 생성.
    • 크기: GRID_COLS * CELL_SIZE x GRID_ROWS * CELL_SIZE
  • 이벤트 처리
    • pollEvent로 창 닫기 이벤트(sf::Event::Closed)를 처리.
  • 맵 및 경로 표시
    • 시작점, 목표점, 장애물 등을 그린 후 animatePath로 경로 애니메이션.
  • 한 번 실행 후 종료
    • break로 루프를 빠져나가 프로그램 종료.

4. 실행

명령어

터미널에 명령어 입력

g++ -std=c++17 main.cpp JPS.cpp -o PathFinding -lsfml-graphics -lsfml-window -lsfml-system

C++에서 여러 파일로 구성된 프로젝트를 컴파일하려면, 각 파일을 컴파일한 뒤 연결(linking)하는 과정이 필요하다.

명령어 설명

  • g++ : GNU C++ 컴파일러를 사용.
  • -std=c++17 : C++17 표준을 사용.
  • main.cpp JPS.cpp : 두 개의 소스 파일을 컴파일하여 연결.
  • -o PathFinding: 출력 실행 파일의 이름을 PathFinding으로 지정.
  • -lsfml-graphics -lsfml-window -lsfml-system : SFML의 그래픽, 창, 시스템 라이브러리를 링크.

컴파일이 성공하면 PathFinding이라는 실행 파일이 생성된다.

실행 파일

다음의 명령어로 실행한다.

./PathFinding

실행 결과

profile
Sia Lim
이전 포스트

JPS 알고리즘 in C++

다음 포스트

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

0개의 댓글