Coding Feature.

SFML로 DFS 시뮬레이션 해보기 in C++ 본문

Game Development/SFML

SFML로 DFS 시뮬레이션 해보기 in C++

codingfeature 2023. 9. 2. 20:55

멀티미디어 라이브러리인 SFML을 좀 더 잘 다루어보고자 학습차원에서 DFS 알고리즘을 SFML를 가지고 시뮬레이션 해보았다.

 

DFS(Depth-First Search) 란 그래프 탐색 알고리즘 중 하나이다.

 

SFML를 Visual Studio에 환경 구축하는 법은 아래 링크를 참고하면 좋다.

https://codingfeature.tistory.com/59

 

SFML 게임 제작 공부 #2. SFML 라이브러리 개발 환경 구축하기.

Reference. 우선 SFML을 다운로드 하기 위해 아래 링크에 접속해본다. https://www.sfml-dev.org/download.php Download (SFML) www.sfml-dev.org 왼쪽 상단에 가장 최근 SFML(현재는 2.6.0) 버전을 클릭한다. 위와 같은 창에

codingfeature.tistory.com

 

소스 코드.

#include <SFML/Graphics.hpp>

// 미로의 크기(배열의 크기)
#define MAZE_SIZE_X 10
#define MAZE_SIZE_Y 10

// 미로가 탐색을 시작하는 위치
#define MAZE_START_X 1
#define MAZE_START_Y 1

// 미로의 각 칸의 크기.
#define RECT_SIZE 30.f

// 미로의 가장 왼쪽 위 꼭짓점의 위치.
#define RECT_START_X 20
#define RECT_START_Y 20

// 처음 미로의 형태, -1은 벽, 0은 빈 공간.
int maze[MAZE_SIZE_Y][MAZE_SIZE_X] = {
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
    {-1, 0, 0, 0, 0, 0, 0, 0, 0, -1},
    {-1, 0, -1, -1, -1, -1, -1, -1, 0, -1},
    {-1, 0, -1, 0, 0, 0, 0, 0 ,0 ,-1},
    {-1 ,0 ,-1 ,0 ,-1 ,-1 ,-1 ,-1 ,-1 ,-1},
    {-1 ,0 ,-1 ,0 ,-1 ,0 ,0 ,0 ,0 ,-1},
    {-1 ,0 ,-1 ,0 ,-1,0,-1,-1 ,0 ,-1},
    {-1 ,0 ,-1 ,0 ,0 ,0 ,0 ,-1 ,0 ,-1},
    {-1 ,0 ,-1,-1,-1,-1,-1,-1 ,0 ,-1},
    {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
};

// 탐색 확인용 배열.
int visited[MAZE_SIZE_Y][MAZE_SIZE_X] = {0, };

sf::RectangleShape rec[MAZE_SIZE_Y][MAZE_SIZE_X];
sf::RenderWindow window(sf::VideoMode(800, 600), "Maze!!");

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

// 미로 정보를 토대로 각 칸의 색상, 위치, 크기를 설정.
void SetMaze() {
    int i, j;
    for (i = 0; i < MAZE_SIZE_Y; i++) {
        for (j = 0; j < MAZE_SIZE_X; j++) {
            rec[i][j].setSize(sf::Vector2f(RECT_SIZE, RECT_SIZE));
            rec[i][j].setPosition(RECT_START_Y + j * RECT_SIZE, RECT_START_X + i * RECT_SIZE);
            if (maze[i][j] == -1) {     // 벽
                rec[i][j].setFillColor(sf::Color::Black);
            }
            else if (maze[i][j] == 0)   // 빈 공간
                rec[i][j].setFillColor(sf::Color::Green);

            if (visited[i][j])          // 탐색한 공간.
                rec[i][j].setFillColor(sf::Color::Red);
        }
    }
}

// 창에 미로를 그림.
void DrawMaze(sf::RenderWindow& window) {
    int i, j;
    for (i = 0; i < MAZE_SIZE_Y; i++) {
        for (j = 0; j < MAZE_SIZE_X; j++) {
            window.draw(rec[i][j]);
        }
    }
}

// DFS 알고리즘을 통해 탐색.
void DFS(int x, int y) {
    int i;
    sf::Event event;
    while (window.pollEvent(event)) {
        if (event.type == sf::Event::Closed)
            window.close();
    }

    visited[y][x] = 1;

    window.clear(sf::Color::White);
    SetMaze();
    DrawMaze(window);
    window.display();

    for (i = 0; i < 4; i++) {
        int new_x = x + dx[i];
        int new_y = y + dy[i];

        // 미로 밖 공간으로 이탈 시 예외 처리.
        if (new_x < 0 || new_x >= MAZE_SIZE_X || new_y < 0 || new_y >= MAZE_SIZE_Y)
            continue;

        // 벽이 있거나, 이미 방문했다면 예외 처리.
        if (maze[new_y][new_x] == -1 || visited[new_y][new_x])
            continue;

        visited[new_y][new_x] = visited[y][x] + 1;
        DFS(new_x, new_y);
    }
}

int main() {
    window.setFramerateLimit(5);
    sf::Clock clock;
    while (window.isOpen()) {
        sf::Event event;
        while (window.pollEvent(event)) {
            if (event.type == sf::Event::Closed)
                window.close();
        }
        window.clear(sf::Color::White);
        SetMaze();
        DrawMaze(window);
        window.display();

        if(clock.getElapsedTime().asSeconds() > 0.5) // 0.5 초 뒤 DFS 시작.
            DFS(MAZE_START_X, MAZE_START_Y);
    }

	return 0;
}

 

결과 창.

(1, 1) 좌표에서 시작한 결과.
(3, 3) 좌표에서 시작한 결과.

 

추가로 사용자가 마우스로 직접 미로를 그려서 (0, 0) 좌표부터 탐색하는 코드를 구현해보았다.

#include <SFML/Graphics.hpp>
#include <iostream>

// 미로의 크기(배열의 크기)
#define MAZE_SIZE_X 20
#define MAZE_SIZE_Y 20

// 미로가 탐색을 시작하는 위치
#define MAZE_START_X 0
#define MAZE_START_Y 0

// 미로의 각 칸의 크기.
#define RECT_SIZE 30.f

// 미로의 가장 왼쪽 위 꼭짓점의 위치.
#define RECT_START_X 20
#define RECT_START_Y 20

// 처음 미로의 형태, -1은 벽, 0은 빈 공간.
int maze[MAZE_SIZE_Y][MAZE_SIZE_X] = {0, };

// 탐색 확인용 배열.
int visited[MAZE_SIZE_Y][MAZE_SIZE_X] = {0, };

sf::RectangleShape rec[MAZE_SIZE_Y][MAZE_SIZE_X];
sf::RenderWindow window(sf::VideoMode(MAZE_SIZE_X * RECT_SIZE + RECT_START_X * 2, MAZE_SIZE_Y* RECT_SIZE + RECT_START_Y * 2), "Maze!!");

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

// 미로 정보를 토대로 각 칸의 색상, 위치, 크기를 설정.
void SetMaze() {
    int i, j;
    for (i = 0; i < MAZE_SIZE_Y; i++) {
        for (j = 0; j < MAZE_SIZE_X; j++) {
            rec[i][j].setSize(sf::Vector2f(RECT_SIZE, RECT_SIZE));
            rec[i][j].setPosition(RECT_START_Y + j * RECT_SIZE, RECT_START_X + i * RECT_SIZE);

            rec[i][j].setOutlineThickness(1.f);
            rec[i][j].setOutlineColor(sf::Color::Black);

            if (maze[i][j] == -1) {     // 벽
                rec[i][j].setFillColor(sf::Color::Black);
            }
            else if (maze[i][j] == 0)   // 빈 공간
                rec[i][j].setFillColor(sf::Color::Green);

            if (visited[i][j])          // 탐색한 공간.
                rec[i][j].setFillColor(sf::Color::Red);
        }
    }
}

// 창에 미로를 그림.
void DrawMaze(sf::RenderWindow& window) {
    int i, j;
    for (i = 0; i < MAZE_SIZE_Y; i++) {
        for (j = 0; j < MAZE_SIZE_X; j++) {
            window.draw(rec[i][j]);
        }
    }
}

// DFS 알고리즘을 통해 탐색.
void DFS(int x, int y) {
    int i;
    sf::Event event;
    while (window.pollEvent(event)) {
        if (event.type == sf::Event::Closed)
            window.close();
    }

    visited[y][x] = 1;

    window.clear(sf::Color::White);
    SetMaze();
    DrawMaze(window);
    window.display();

    for (i = 0; i < 4; i++) {
        int new_x = x + dx[i];
        int new_y = y + dy[i];

        // 미로 밖 공간으로 이탈 시 예외 처리.
        if (new_x < 0 || new_x >= MAZE_SIZE_X || new_y < 0 || new_y >= MAZE_SIZE_Y)
            continue;

        // 벽이 있거나, 이미 방문했다면 예외 처리.
        if (maze[new_y][new_x] == -1 || visited[new_y][new_x])
            continue;

        visited[new_y][new_x] = visited[y][x] + 1;
        DFS(new_x, new_y);
    }
}

int main() {
    window.setFramerateLimit(60);
    sf::Clock clock;
    int mouse_position_x = 0, mouse_position_y = 0, i, j;
    bool is_mouse_pressed = false;
    while (window.isOpen()) {
        sf::Event event;
        while (window.pollEvent(event)) {
            if (event.type == sf::Event::Closed)
                window.close();

            // 마우스 이동 이벤트 확인.
            if (event.type == sf::Event::MouseMoved) {
                mouse_position_x = event.mouseMove.x;
                mouse_position_y = event.mouseMove.y;
                std::cout << "x : " << event.mouseMove.x << " y : " << event.mouseMove.y << '\n';
            }
        }

        // 마우스 왼쪽 버튼 클릭.
        if (sf::Mouse::isButtonPressed(sf::Mouse::Left)) {
            std::cout << "Mouse Left Pressed!\n";
            is_mouse_pressed = true;
        }

        for (i = 0; i < MAZE_SIZE_Y; i++) {
            for (j = 0; j < MAZE_SIZE_X; j++) {
                // 마우스 왼쪽 클릭 시 그 위치에 있는 사각형에 벽 (-1) 값 입력.
                if (rec[i][j].getGlobalBounds().contains(sf::Vector2f(mouse_position_x, mouse_position_y)) && is_mouse_pressed) {
                    maze[i][j] = -1;
                    is_mouse_pressed = false;
                }
            }
        }
        window.clear(sf::Color::White);
        SetMaze();
        DrawMaze(window);
        window.display();

        // 마우스 오른쪽 클릭 시 DFS 시작.
        if (sf::Mouse::isButtonPressed(sf::Mouse::Right)) 
            DFS(MAZE_START_X, MAZE_START_Y);

    }

	return 0;
}

 

결과창.

 

다음은 Sorting 알고리즘을 가지고 성능을 테스트 해보는 프로그램을 만들어보고자 한다.

'Game Development > SFML' 카테고리의 다른 글

SFML) 모래와 물이 떨어지는 시뮬레이션 구현하기 in C++  (0) 2023.09.03
SFML) 정렬 알고리즘 그래픽으로 구현하기.  (0) 2023.09.03
'Game Development/SFML' Related Articles more