[게임 프레임워크 개발 일지] #11 충돌 시스템 개선하기 - Broad Phase

2D 충돌 알고리즘에 대해서는 이전 포스팅에서 다뤄본 적이 있습니다.

실제로 사용하려면, 각 Entity마다 Collider를 할당하고, pair에 대해서 충돌하는지 검사해주면 됩니다.

 

그런데 막상 사용하려고 코드를 짜보니 이중 for 문에 O(N^2)이 나오더군요.

무식하게 pair를 만들고 다 비교하려고 해서 그렇습니다.

Brute Force는 대충 다음처럼 돌아갑니다.

for (int i = 0; i < colliders.size(); i++)
{
    for (int j = i + 1; j < colliders.size(); j++)
    {
        if (Collide(colliders[i], colliders[j]))
        {
            //collide
        }
    }
}

 

Collider를 만들 때 QuadTree를 사용해서 최적화를 해볼 생각이었는데, 이상하게도 별 효과가 없었습니다.

지금 생각하면 Entity를 움직이면서 tree update 빈도가 꽤 높아진 때문이 아닐까 싶네요.

 

아무튼, 이번 포스팅에서는 이러한 충돌 감지를 최적화하는 알고리즘을 정리해보겠습니다.

 

Reference

 - Broad Phase (Grid) : http://buildnewgames.com/broad-phase-collision-detection/

Broad Phase Collision Detection Using Spatial Partitioning - Build New Games

- Sweep And Prune : https://github.com/YulyaLesheva/Sweep-And-Prune-algorithm

GitHub - YulyaLesheva/Sweep-And-Prune-algorithm: Sweep And Prune algorithm for game engines based on Matthew Leibowitz article,

- Dynamic AABB Tree : 

https://box2d.org/files/ErinCatto_DynamicBVH_GDC2019.pdf

https://allenchou.net/2014/02/game-physics-broadphase-dynamic-aabb-tree/

Game Physics: Broadphase – Dynamic AABB Tree | Ming-Lun "Allen" Chou | 周明倫

---

Brute Force의 문제점은 두 Entity 간의 거리가 너무 멀어서 충돌이 발생했을 리가 없는 pair에 대해서도 검사한다는 점입니다. 그래서 최적화 알고리즘은 주로 이러한 충돌했을 가능성이 적은 pair를 솎아내는 과정에 초점을 맞춥니다.

 

이렇게 충돌했을 가능성이 낮은 pair를 골라내는 과정을 Broad Phase라고 하며, 충돌했는지 여부만을 간단하게 검사합니다. 충돌했을 가능성이 있는 pair에 대해서 충돌 정보를 자세히 구하는 과정은 Narrow Phase라고 합니다.

collider가 복잡한 경우에는 narrow phase 이전에 mid phase를 한 번 거쳐서 걸러내기도 합니다.

 

충돌했을법한 pair를 골라내는 것이기 때문에 collider를 감싸는 AABB를 생성해줄 필요가 있습니다.

Broad Phase 알고리즘에는 Sweep And Prune (SAP), Space Partitioning 등이 있습니다.

순서대로 시작해봅시다.

 

들어가기에 앞서 사용하기에 좋게 미리 정의해둔 struct가 있습니다.

AABB를 비교해서 판단하기 때문에 원래 collider shape가 뭐였는지 알 수가 없습니다.

따라서 원래 collider를 알아낼 수 있게 하기 위해서 struct에 해당 collider의 index를 id로 넣어줬습니다.

struct Shape
{
    SP2C::SPC_Shape* collider;
    size_t id;
};

 

제가 구현한 collider에서 SPC_Shape는 모든 collider의 base class이기 때문에 ComputeAABB를 virtual 함수로 넣을 수가 없었습니다. 따라서 전역 함수로 따로 생성해줘야 했습니다. 이 포스팅을 올리는 시점에서는 라이브러리에도 따로 추가해줬습니다.

SP2C::SPC_AABB ComputeAABB(SP2C::SPC_Shape* shape)
{
	switch (shape->type)
	{
	case SP2C::SPC_Shape::AABB:
		return reinterpret_cast<SP2C::SPC_AABB*>(shape)->ComputeAABB();

	case SP2C::SPC_Shape::Circle:
		return reinterpret_cast<SP2C::SPC_Circle*>(shape)->ComputeAABB();

	case SP2C::SPC_Shape::Polygon:
		return reinterpret_cast<SP2C::SPC_Polygon*>(shape)->ComputeAABB();

	default:
		return SP2C::SPC_AABB();
	}
}

 

1. Sweep And Prune

충돌 가능성이 높은 pair를 구하는, 가장 쉽게 생각할 수 있는 방법은 정렬하는 겁니다.

x축이든 y축이든 한 방향으로 정렬해서 각각을 비교해보는 겁니다.

비교할 collider를 하나 먼저 지정하고, 다른 collider들을 가져와서 충돌을 검사해보면서 충돌했으면 pair를 만들어 넣어주면 됩니다.

collider를 AABB의 min.x를 기준으로 오름차순 정렬했다고 가정합시다.

만약 가져온 collider AABB의 max.x가 기준 collider AABB의 min.x보다 크다면

이 이후의 모든 collider는 충돌할 가능성이 없으므로 여기서 멈춰주고 다음으로 넘어가주면 됩니다.

 

namespace SAP
{
    bool CompareMinX(Shape& a, Shape& b)
    {
        return a.aabb.min.x < b.aabb.min.x;
    }

    std::vector<std::pair<Shape, Shape>> broadphase(std::vector<Shape> colliders)
    {
        std::sort(colliders.begin(), colliders.end(), CompareMinX);
        std::vector<Shape> currentList;
        std::vector<std::pair<Shape, Shape>> pairs;

        for (size_t i = 0; i < colliders.size(); i++)
        {
            for (size_t j = 0; j < currentList.size(); j++)
            {
                auto A = colliders[i].aabb, B = currentList[j].aabb;
                if (A.min.x > B.max.x)
                {
                    currentList.erase(currentList.begin() + j);
                    j--;
                }
                else
                    pairs.emplace_back(colliders[i], currentList[j]);
            }

            currentList.push_back(colliders[i]);
        }

        return pairs;
    }
}

 

충돌 함수는 다음 같은 방식으로 짰습니다.

void collide_SAP()
{
    std::vector<Shape> list;

    for (size_t i = 0; i < entities.size(); i++)
    {
        Shape shape;
        shape.aabb = ComputeAABB(entities[i].collider);
        shape.id = i;

        list.push_back(shape);
    }

    auto pairs = SAP::broadphase(list);

    for (const auto& p : pairs)
    {
        SP2C::SPC_Manifold m;
        m.A = entities[p.first.id].collider;
        m.B = entities[p.second.id].collider;

        if (SP2C::Collision::Collide(&m))
            collided[p.first.id] = collided[p.second.id] = 1;
    }
}

 

이렇게 놓고 보니, 매번 Shape list를 만들고 객체를 복사하는 게 비용이 좀 클 것 같아서

initialization 과정을 따로 분리해줬습니다. 그리고 object를 pointer로 바꿨습니다.

 

2022-10-08 추가)

이후에 추가로 좀 돌려보니까, 어차피 외부에서 list로 관리할 것이라면 pointer 보다 object로 관리하는 게 더 빠릅니다.

굳이 pointer로 바꿀 필요는 없었는데, 여기서는 list를 copy해올 때도 생성하는 비용이 클 거라고 생각해서 그랬나봅니다.

 

namespace SAP
{
    bool CompareMin(Shape*& a, Shape*& b)
    {
        return a->aabb.min.x < b->aabb.min.x;
    }

    std::vector<std::pair<Shape*, Shape*>> broadphase(std::vector<Shape*> colliders)
    {
        std::sort(colliders.begin(), colliders.end(), CompareMin);
        std::vector<Shape*> currentList;
        std::vector<std::pair<Shape*, Shape*>> pairs;

        for (size_t i = 0; i < colliders.size(); i++)
        {
            for (size_t j = 0; j < currentList.size(); j++)
            {
                auto A = colliders[i]->aabb, B = currentList[j]->aabb;
                if (A.min.x > B.max.x)
                {
                    currentList.erase(currentList.begin() + j);
                    j--;
                }
                else if (SP2C::Collision::AABB_to_AABB(colliders[i]->aabb, currentList[j]->aabb))
                    pairs.emplace_back(colliders[i], currentList[j]);
            }

            currentList.push_back(colliders[i]);
        }

        return pairs;
    }
}

또 하나, else 문에 AABB to AABB 검사가 추가한 것을 볼 수 있습니다.

 

x좌표의 인접 여부만을 판단해서도 상당수의 pair를 걸러낼 수 있기 때문에 AABB_to_AABB 없이 그냥 pair를 넣어줘도 작동은 잘 합니다.

다만 AABB to AABB 검사를 하지 않는 경우에는 worst scenario가 있는데, x좌표는 거의 동일하지만 y좌표가 크게 다른 물체가 많은 경우입니다. 이 상황에서는 x좌표 비교만으로는 가능성이 낮은 pair를 걸러낼 수 없어서 성능이 많이 떨어집니다.

	random over entire screen, 50% moving	same x axis, random over entire y, 50% moving
check AABB to AABB, Release Build	0.0006s	0.0043s
no check, Release build	0.0017s	0.027s

화면 전체에 무작위로 뿌리는 건 no check가 빠르지만, y축 상으로만 무작위로 뿌리는 건 그보다 훨씬 느려집니다.

bool sap_init = false;
std::vector<Shape*> list_sap;

void collide_SAP()
{
    if (!sap_init)
    {
        sap_init = true;

        for (auto& shape : list_sap)
            delete shape;

        list_sap.clear();

        for (size_t i = 0; i < entities.size(); i++)
        {
            Shape* shape = new Shape();
            shape->aabb = ComputeAABB(entities[i].collider);
            shape->id = i;

            list_sap.push_back(shape);
        }
    }
    else
    {
        for (size_t i = 0; i < entities.size(); i++)
            list_sap[i]->aabb = ComputeAABB(entities[i].collider);
    }

    auto pairs = SAP::broadphase(list_sap);

    for (const auto& p : pairs)
    {
        SP2C::SPC_Manifold m;
        m.A = entities[p.first->id].collider;
        m.B = entities[p.second->id].collider;

        if (SP2C::Collision::Collide(&m))
            collided[p.first->id] = collided[p.second->id] = 1;
    }
}

수정한 충돌 검사 코드입니다.

 

수정을 (Shape 객체, no AABB check) -> (Shape 포인터, no AABB check) -> (Shape 포인터, AABB check)

순서대로 했는데, 성능 테스트가 Release build 기준 0.006초 - 0.002초 - 0.0006초로 나왔습니다.

...이거 제대로 돌아간 거 맞나?

 

아무튼, 여기서 다룰 알고리즘 모두 이런 방식으로 테스트했습니다. 아래부터는 별다른 설명은 하지 않겠습니다.

각 알고리즘에 대한 평가도 모두 모아서 성능 비교를 하면서 하겠습니다.

---

2. Grid

Spatial Partitioning은 충돌 판정을 편하게 하기 위해서 collider를 그룹으로 묶어놓는 것입니다.

여기서는 공간을 grid로 나누고 collider를 각 cell에 그룹에 배정해놓습니다.

같은 cell에 있는 collider는 충돌 가능성이 높은 것으로 판단하고 pair를 만들어주면 되겠죠.

 

source from: https://levelup.gitconnected.com/2d-collision-detection-8e50b6b8b5c0

collider의 크기에 따라 여러 cell에 배정되어 있을 수 있습니다.

그냥 같은 cell에 collider가 존재하는지만 판단하면 되니까요.

 

먼저 공간 크기에 따라, 그리고 cell 크기에 따라 grid를 만들어 줄 필요가 있습니다.

struct Grid
{
    std::vector<std::vector<std::vector<Shape*>>> cells;
    unsigned int gridSize;
} grid;

void init(unsigned int width, unsigned int height, unsigned int gridSize)
{
    grid.cells.clear();
    grid.cells.resize(height / gridSize);

    for (auto& v : grid.cells)
        v.resize(width / gridSize);
    grid.gridSize = gridSize;
}

 

다음으로 collider를 cell에 배정해줘야 됩니다.

얘가 움직일 때마다 다시 새로 갈아엎어줘야되나 고민을 해봤는데

뭐 크게 효율적인 다른 방법이 있는 것 같지는 않아서 그냥 매번 다시 배정하게 했습니다.

//clear
for (auto& v : grid.cells)
    for (auto& cell : v)
        cell.clear();

for (size_t i = 0; i < colliders.size(); i++)
{
    auto& aabb = colliders[i].aabb;

    int x1 = std::max((int)(aabb.min.x / grid.gridSize), 0), x2 = std::min((int)(aabb.max.x / grid.gridSize), width);
    int y1 = std::max((int)(aabb.min.y / grid.gridSize), 0), y2 = std::min((int)(aabb.max.y / grid.gridSize), height);

    for (int y = y1; y <= y2; y++)
        for (int x = x1; x <= x2; x++)
            grid.cells[y][x].push_back(colliders[i]);
}

collider가 cell boundary 바깥으로 나갈 가능성이 있기 때문에, 그런 경우에는 clamp를 해줘야 합니다.

 

이제 각 cell 마다 루프를 돌면서 pair를 추가해주면 됩니다.

여기서 문제점이 있는데, 중복된 pair가 나올 수 있다는 점입니다.

collider A가 {2,3,4,5}, collider B가 {4,5,7,8}번 cell에 포함되어 있다면

A와 B는 4번, 5번 cell에서 pair가 생성될 수 있으므로 중복이 발생하게 됩니다.

 

따라서 collider pair를 key로 해서 체크해줘야 합니다.

그런데 C++에는 pair에 대한 hash가 없네요?

 

아니 왜 이런 걸 지원 안 하지? C++은 정말 최악의 언어임이 분명하다.

그렇다고 때려치고 당장 다른 언어를 배울 수는 없는 노릇이니, 대충 제 역할을 해줄 key를 만들어줍시다.

 

처음에는 pair에 대한 hasher struct를 만들어줬는데 얘가 작동을 안 합니다.

사실 여기에서 pair는 (A, B) 또는 (B, A) 둘 다 나타날 수 있기 때문에 둘을 같은 hash로 인식할 수 있는 hasher가 필요합니다.

그래서 first와 second를 뒤집어도 같게끔 코드를 작성해줬는데도 얘가 자꾸 다른 녀석으로 인식하지 뭡니까?

 

이 hasher에는 암흑버그귀신이 붙어있는 게 분명하니 얼른 폐기하고 그냥 string으로 생성했습니다.

근데 진짜 왜 이럴까요? 원본 값에 대해서 해쉬 충돌 보정을 해주는 거라도 내장이 되어있나.

 

하여튼 min, max 값으로 순서를 고정한 뒤에 string으로 연결해줬습니다.

std::unordered_map<std::string, bool> checked;

std::vector<std::pair<Shape*, Shape*>> pairs;

for (auto& v : grid.cells)
    for (auto& cell : v)
    {
        for (size_t i = 0; i < cell.size(); i++)
            for (size_t j = i + 1; j < cell.size(); j++)
            {
                std::string hash = std::to_string(std::min(cell[i].id, cell[j].id)) + "," +
                                   std::to_string(std::max(cell[i].id, cell[j].id));

                if (checked[hash]) continue;

                if (SP2C::Collision::AABB_to_AABB(cell[i]->aabb, cell[j]->aabb))
                    pairs.emplace_back(cell[i], cell[j]);

                checked[hash] = 1;
            }
    }

return pairs;

 

이러고 비교를 해봤더니, hash 생성이 성능에 영향을 너무 끼친다는 것을 발견했습니다.

그래서 모두 추가한 뒤에 unique로 지워주는 방법으로 바꿔봤습니다.

 

std::vector<std::pair<Shape*, Shape*>> pairs;

for (auto& v : grid.cells)
    for (auto& cell : v)
    {
        for (size_t i = 0; i < cell.size(); i++)
            for (size_t j = i + 1; j < cell.size(); j++)
                if (SP2C::Collision::AABB_to_AABB(cell[i]->aabb, cell[j]->aabb))
                    pairs.emplace_back(cell[i], cell[j]);
    }

pairs.erase(std::unique(pairs.begin(), pairs.end()), pairs.end());
return pairs;

 

이 상황에서 성능을 비교해봤습니다.

Release Build	random over entire screen, 50% moving	same position, no moving
no hash	0.00057s	0.023s
string hash	0.0048s	0.18s
unique erase	0.00059s	0.022s

string hash가 확실히 느리긴 하고, no hash와 unique erase의 성능이 사실상 동일하게 나타났습니다.

 

그러면 개수를 올려서 실험해봐야겠네요.

Release	1024 entities, random, 50% moving	1024 entities, same, no moving	8192 entities, random, 50% moving	8192 entitis, same, no moving
no hash	0.00057s	0.023s	0.0428s	1.7s
unique erase	0.00059s	0.022s	0.044s	1.78s

 

?

hash가 없어도 되나 싶어서 넘어갔다가 나중에 되서야 생각난 게 있습니다.

cell 크기가 pair 중복에 영향을 끼친다는 점입니다. 자세한 얘기는 성능 비교 때하고, cell size에 따라서만 비교해봅시다.

Release	5x5 px	20x20 px	40x40 px
no hash	0.0105s	0.00268s	0.00182s
unique erase	0.0096s	0.00261s	0.00191s

cell size가 작을 수록 pair가 중복될 가능성이 높습니다.

반면 cell size가 클 수록 한 cell에 포함되는 collider 개수가 많아지니, 비교할 pair의 종류가 많아집니다.

 

collider pair를 구하는 입장에서는 중복이 존재하면 안되니, 최종 성능 비교에서는 unique erase를 사용하겠습니다.

중복 여부가 상관 없다면 중복 제거 없이 써도 문제는 없어 보입니다.

---

3. Dynamic AABB Tree

Spatial Partitioning의 연장선으로, 이러한 충돌 판정을 최적화하기 위해 사용하는 자료 구조가 있습니다.

서두에서 언급한 QuadTree나 kd-Tree 그리고 여기서 이야기할 Dynamic AABB Tree가 해당됩니다.

 

source from: https://allenchou.net/2014/02/game-physics-broadphase-dynamic-aabb-tree/

Dynamic AABB Tree는 부모 노드의 AABB가 자식 노드의 AABB를 합친 union 객체입니다.

여기서 구현할 Tree는 Full Binary Tree (모든 노드의 자식이 0개 또는 2개)입니다.

자식이 1개인 경우에는 그 부모 노드와 자식 노드가 사실상 동일한 노드라는 이야기이므로, 비효율적입니다.

 

Tree이기 때문에 Node struct를 정의해줘야 합니다.

그런데 이전에는 동일한 id에 Shape와 Collider (또는 Entity)가 대응됐지만, node는 index로 찾을 수 있는 구조가 아닙니다.

그래서 node 삭제 같은 작업을 할 때 Shape에서 Node를 찾아갈 link가 필요합니다. (top-down으로 찾을 수야 있겠지만, 매번 contain 비교를 해줘야 하니까요)

이를 위해서 따로 Shape struct를 만들어줬습니다.

기존 Shape에다, Node pointer가 저장될 수 있도록 userData를 void pointer를 추가했습니다.

struct AABBShape
{
    SP2C::SPC_Shape* shape;
    size_t id;
    void* userData;
};

이것 때문에 이전 알고리즘들과는 차이가 조금 생기긴 하는데, 뭐 겨우 이정도로 영향을 받을까요 설마.

 

이제 Node를 만들어봅시다.

struct AABBNode
{
    AABBNode* parent;
    AABBNode* children[2];

    bool crossed; //to check pair duplicates
    SP2C::SPC_AABB aabb;
    AABBShape* data;

    AABBNode() : parent(nullptr), data(nullptr), crossed(false)
    {
        children[0] = nullptr;
        children[1] = nullptr;
    }

    bool isLeaf() const
    {
        return children[0] == nullptr;
    }

    void setBranch(AABBNode* a, AABBNode* b)
    {
        a->parent = this;
        b->parent = this;

        children[0] = a;
        children[1] = b;
    }

    void setLeaf(AABBShape* data)
    {
        this->data = data;
        data->userdata = this;

        children[0] = nullptr;
        children[1] = nullptr;
    }

    void updateAABB(float margin)
    {
        if (isLeaf())
        {
            //fat aabb
            const SP2C::Vec2 marginVec(margin, margin);
            const SP2C::SPC_AABB shape = data->shape;

            aabb.min = shape.min - marginVec;
            aabb.max = shape.max + marginVec;
        }
        else
            aabb = uniteAABB(children[0]->aabb, children[1]->aabb);
    }

    AABBNode* getSibling() const
    {
        return this == parent->children[0] ? parent->children[1] : parent->children[0];
    }
};

Reference를 그대로 옮겨와서 적용했습니다.

crossed는 AABB Tree에서 중복 검사를 방지하기 위해 사용한다고 합니다.

 

그외에 isLeaf, setBranch, setLeaf, getSibling는 Node의 부모 자식 관계에 관련된 함수이고,

updateAABB는 연결한 data의 AABB를 가져오는 함수입니다.

 

여기서 사용하는 AABB는 fat AABB인데, AABB가 바뀔 때마다 tree를 update하면 비용이 너무 커지니

원본보다 margin 만큼 큰 AABB를 저장하고, 이를 기준으로 업데이트하고 충돌을 계산합니다.

만약 해당 node가 branch라면 자식 node의 AABB를 합쳐서 저장해야 합니다.

SP2C::SPC_AABB uniteAABB(const SP2C::SPC_AABB& a, const SP2C::SPC_AABB& b)
{
    return SP2C::SPC_AABB(SP2C::Vec2(std::min(a.min.x, b.min.x), std::min(a.min.y, b.min.y)),
                          SP2C::Vec2(std::max(a.max.x, b.max.x), std::max(a.max.y, b.max.y)));
}

여기서 사용하는 AABB 관련 함수들도 라이브러리에 업데이트했습니다. 안 하고는 못 배길 정도더군요.

 

이제 AABBTree의 차례입니다.

함수가 많으니 필요한 것만 간단하게 다뤄봅시다.

먼저 Tree에 필요한 멤버 변수들입니다.

AABBNode* root;
float margin;
std::vector<AABBNode*> invalidNodes;

root는 말그대로 root node이고, margin은 AABBTree에서 fat AABB를 만들기 위해 사용할 margin 값입니다.

invalidNodes는 AABB가 업데이트되면서 수정해야할 AABB Node들을 모아놓는 리스트입니다.

 

그러면 이제 node를 추가하고 삭제할 수 있어야겠죠.

void add(AABBShape* shape)
{
    if (root)
    {
        AABBNode* node = new AABBNode();
        node->setLeaf(shape);
        node->updateAABB(margin);
        insert(node, &root);
    }
    else
    {
        root = new AABBNode();
        root->setLeaf(shape);
        root->updateAABB(margin);
    }
}

void remove(AABBShape* shape)
{
    AABBNode* node = static_cast<AABBNode*>(shape->userData);

    node->data = nullptr;
    shape->userData = nullptr;

    removeNode(node);
}

remove에서 AABBShape으로 node를 찾을 방법이 딱히 없어서 userData를 추가했었죠.

insert는 재귀를 위해 따로 정의한 함수입니다. Tree가 다 그렇죠 뭐

 

void insert(AABBNode* node, AABBNode** parent)
{
    AABBNode* p = *parent;
    if (p->isLeaf())
    {
        AABBNode* newParent = new AABBNode();
        newParent->parent = p->parent;
        newParent->setBranch(node, p);
        *parent = newParent;
    }
    else
    {
        //* find least increasing difference
        const SP2C::SPC_AABB a = p->children[0]->aabb;
        const SP2C::SPC_AABB b = p->children[1]->aabb;

        const float diffA = getArea(uniteAABB(a, node->aabb)) - getArea(a);
        const float diffB = getArea(uniteAABB(b, node->aabb)) - getArea(b);

        if (diffA < diffB)
            insert(node, &p->children[0]);
        else
            insert(node, &p->children[1]);
        //*

        //update parent
        (*parent)->updateAABB(margin);
    }
}

void removeNode(AABBNode* node)
{
    AABBNode* parent = node->parent;
    if (parent)
    {
        AABBNode* sibling = node->getSibling();
        if (parent->parent)
        {
            //move sibling to parent
            sibling->parent = parent->parent;
            (parent == parent->parent->children[0] ? parent->parent->children[0] : parent->parent->children[1]) = sibling;
        }
        else
        {
            //move sibling to root
            root = sibling;
            sibling->parent = nullptr;
        }

        delete node;
        delete parent;
    }
    else //root to be deleted
    {
        root = nullptr;
        delete node;
    }
}

 

node를 삽입하는 기준은 volume의 증가량입니다. volume이 가장 적게 증가하는 leaf를 찾아서 그 곳에

새로운 branch node를 만들고, 기존 leaf와 새로운 node를 삽입합니다.

처음에도 말했듯이, 각각의 leaf가 원본 collider의 AABB를 의미하고 branch는 그 collider들을 합친 AABB를 의미합니다.

 

여기서 논리적으로 이상하다고 느낀 것이 있었는데, 추후에 설명하겠습니다.

 

3차원 이상에서는 volume이 될 수도 있고, surface area가 될 수도 있겠지만 여긴 2D이니 그냥 넓이를 구해주겠습니다.

float getArea(const SP2C::SPC_AABB& aabb)
{
    return (aabb.max.x - aabb.min.x) * (aabb.max.y - aabb.min.y);
}

 

volume 증가량이 아닌 다른 걸 기준으로도 판단할 수 있습니다.

Reference에서는 AABB centroid, 다시 말해 가장 가까운 무게중심을 갖는 AABB가 있는 node 쪽에 추가하는 방법도 있다고 이야기하고 있습니다.

다른 것도 찾아봤는데... 이건 번외에서 이야기하겠습니다.

removeNode에서는 node를 지우기 위해서 필요한 작업을 수행합니다.

먼저, 지우는 node는 어떤 collider 개체이기 때문에 반드시 leaf node일겁니다.

AABB Tree에서 node의 자식은 0개 또는 2개이기 때문에, leaf node의 sibling이 존재하지 않는 경우는 root node인 경우 뿐입니다.

따라서 node를 지우고 난 뒤에는 sibling node 하나만 남게 되므로, node의 parent 역시 필요하지 않게 됩니다.

그러니 node와 parent를 모두 지우고, parent 위치에는 sibling을 옮겨둬야겠죠.

그 후에는 parent의 parent에서도 sibling과 연결시켜줘야합니다.

 

이제 추가한 collider들을 업데이트해봅시다.

void update()
{
    if (root)
    {
        if (root->isLeaf())
            root->updateAABB(margin);
        else
        {
            invalidNodes.clear();
            checkInvalidNodes(root, invalidNodes);

            for (AABBNode* node : invalidNodes)
            {
                AABBNode* parent = node->parent;
                AABBNode* sibling = node->getSibling();
                AABBNode** parent_place = parent->parent ? (parent == parent->parent->children[0] ? &parent->parent->children[0] : &parent->parent->children[1]) : &root;

                //move sibling to parent
                sibling->parent = parent->parent ? parent->parent : nullptr;
                *parent_place = sibling;
                delete parent;

                //update the node and re-insert it
                node->updateAABB(margin);
                insert(node, &root);
            }

            invalidNodes.clear();
        }
    }
}

void checkInvalidNodes(AABBNode* node, std::vector<AABBNode*>& list)
{
    if (node->isLeaf())
    {
        //get the shape if it is not completely inside the fat aabb
        if (!contains(node->aabb, node->data->shape))
            list.push_back(node);
    }
    else
    {
        checkInvalidNodes(node->children[0], list);
        checkInvalidNodes(node->children[1], list);
    }
}

먼저 AABB의 포함 관계를 다시 계산해줄 필요가 있는 node들을 골라낼 필요가 있습니다.

checkInvalidNodes에서 각 leaf node의 fat aabb가 원본 aabb를 포함하는지 판단해줍니다.

bool contains(const SP2C::SPC_AABB& a, const SP2C::SPC_AABB& b)
{
    return (a.min.x <= b.min.x && b.max.x <= a.max.x) &&
           (a.min.y <= b.min.y && b.max.y <= a.max.y);
}

수정이 필요한 node들에 대해서는 삭제한 후에 다시 삽입해줍니다.

node 자체는 삭제하면 안된다는 것을 빼면 remove와 동일합니다.

 

 

이제 pair만 구하면 되겠네요.

std::vector<std::pair<AABBShape*, AABBShape*>> broadphase()
{
    std::vector<std::pair<AABBShape*, AABBShape*>> pairs;
    if (!root || root->isLeaf())
        return pairs;

    clearCrossedFlags(root);

    computePairs(pairs, root->children[0], root->children[1]);
    return pairs;
}

void computePairs(std::vector<std::pair<AABBShape*, AABBShape*>>& list, AABBNode* a, AABBNode* b)
{
    if (a->isLeaf())
    {
        if (b->isLeaf()) //both are leaves
        {
            if (SP2C::Collision::AABB_to_AABB(a->data->shape, b->data->shape))
                list.emplace_back(a->data, b->data);
        }
        else //one leaf and one branch
        {
            crossChildren(list, b); //check the flag
            computePairs(list, a, b->children[0]);
            computePairs(list, a, b->children[1]);
        }
    }
    else
    {
        if (b->isLeaf()) //one branch and one leaf
        {
            crossChildren(list, a); //check the flag
            computePairs(list, b, a->children[0]);
            computePairs(list, b, a->children[1]);
        }
        else //two branches
        {
            crossChildren(list, a); //check the flags
            crossChildren(list, b);

            computePairs(list, a->children[0], b->children[0]);
            computePairs(list, a->children[0], b->children[1]);
            computePairs(list, a->children[1], b->children[0]);
            computePairs(list, a->children[1], b->children[1]);
        }
    }
}

 

AABBNode에서 crossed 라는 변수를 만들어뒀습니다.

해당 node를 검사했는지를 판단하는 값이므로, flag를 지워주는 함수가 필요하겠군요.

void clearCrossedFlags(AABBNode* node)
{
    node->crossed = false;
    if (!node->isLeaf())
    {
        clearCrossedFlags(node->children[0]);
        clearCrossedFlags(node->children[1]);
    }
}

flag를 지워준 후에는

두 자식 노드는 branch/leaf 중 어느 것이냐에 따라 세 가지 경우가 나올 수 있습니다.

2 branches / 1 branch and 1 leaf / 2 leaves 입니다.

branch node에 대해서는 그 node의 자식들에 대해서도 충돌 여부를 판단해줘야 합니다.

 

이때 이 branch node 하위에 존재하는 child nodes들에 대해서는 모두 검사한 게 되므로, branch node의 crossed를 true로 만들어줍니다. 이 역할을 해줄 함수가 crossChildren입니다.

void crossChildren(std::vector<std::pair<AABBShape*, AABBShape*>>& list, AABBNode* node)
{
    if (!node->crossed)
    {
        computePairs(list, node->children[0], node->children[1]);
        node->crossed = true;
    }
}

다시 돌아와서 세 가지 경우에 대해서 생각해봅시다.

 

2개가 모두 leaf node인 경우에는, 두 collider가 충돌할 가능성이 있는 pair라는 의미이므로 list에 추가해줍니다.

1개가 branch node인 경우에는, 아까도 말했듯이 branch node의 하위 자식들에 대해서 먼저 검사를 해준 뒤에

그 자식 node들과 나머지 하나의 leaf node에 대해서도 충돌 여부를 검사해줍니다.

2개가 branch node인 경우에는 각각의 자식들에 대해서 검사한 뒤에 서로의 자식들과 충돌 여부를 검사해줍니다.

 

여기서 생각해봤습니다. 서로 다른 branch의 자식끼리 충돌할 가능성이 있다면

두 branch의 AABB (원본 collider가 없으니 fat AABB의 union AABB가 됩니다) 또한 충돌할 것입니다.

그럼 미리 검사해서 이걸 걸러내면 되지 않을까? 해서 구현해봤더니 뭔가 코드가 이상하게 돌아가더군요.

 

여기서 아까 논리적으로 이상하다고 느낀 것을 발견했는데,

update에서 새로운 parent는 AABB를 갱신해줬는데, 그 상위 node들도 갱신해야하지 않느냐는 것입니다.

마찬가지로, remove에서는 sibling 상위 node들을 갱신해줘야 합니다.

 

정작 지금 코드에서 돌렸을 때는 별다른 문제점을 찾지 못했는데, 사실상 모든 pair에 대해서 검사를 하기 때문인 것 같습니다.

그런 이유로 수정한 update 및 remove 코드는 다음과 같습니다.

void update()
{
    if (root)
    {
        if (root->isLeaf())
            root->updateAABB(margin);
        else
        {
            invalidNodes.clear();
            checkInvalidNodes(root, invalidNodes);

            for (AABBNode* node : invalidNodes)
            {
                AABBNode* parent = node->parent;
                AABBNode* sibling = node->getSibling();
                AABBNode** parent_place = parent->parent ? (parent == parent->parent->children[0] ? &parent->parent->children[0] : &parent->parent->children[1]) : &root;

                //move sibling to parent
                sibling->parent = parent->parent ? parent->parent : nullptr;
                *parent_place = sibling;
                delete parent;
                updateNode(sibling->parent); //here!!!

                //update the node and re-insert it
                node->updateAABB(margin);
                insert(node, &root);
            }

            invalidNodes.clear();
        }
    }
}

void updateNode(AABBNode* node)
{
    if (!node) return;

    node->updateAABB(margin);
    updateNode(node->parent);
}

updateNode를 통해 상위 노드를 모두 갱신해줬습니다.

remove에서도 마찬가지로 수정해줬습니다.

 

void removeNode(AABBNode* node)
{
    AABBNode* parent = node->parent;
    if (parent)
    {
        AABBNode* sibling = node->getSibling();
        if (parent->parent)
        {
            //move sibling to parent
            sibling->parent = parent->parent;
            (parent == parent->parent->children[0] ? parent->parent->children[0] : parent->parent->children[1]) = sibling;
        }
        else
        {
            //move sibling to root
            root = sibling;
            sibling->parent = nullptr;
        }

        delete node;
        delete parent;

        updateNode(sibling->parent); //here!!!
    }
    else //root to be deleted
    {
        root = nullptr;
        delete node;
    }
}

이제 pair check를 수정해봅시다.

void computePairs(std::vector<std::pair<AABBShape*, AABBShape*>>& list, AABBNode* a, AABBNode* b)
{
    if (a->isLeaf())
    {
        if (b->isLeaf()) //both are leaves
        {
            if (SP2C::Collision::AABB_to_AABB(a->data->shape, b->data->shape))
                list.emplace_back(a->data, b->data);
        }
        else //one leaf and one branch
        {
            crossChildren(list, b); //check the flag

            if (!SP2C::Collision::AABB_to_AABB(a->aabb, b->aabb))
                return;

            computePairs(list, a, b->children[0]);
            computePairs(list, a, b->children[1]);
        }
    }
    else
    {
        if (b->isLeaf()) //one branch and one leaf
        {
            crossChildren(list, a); //check the flag

            if (!SP2C::Collision::AABB_to_AABB(a->aabb, b->aabb))
                return;

            computePairs(list, b, a->children[0]);
            computePairs(list, b, a->children[1]);
        }
        else //two branches
        {
            crossChildren(list, a); //check the flags
            crossChildren(list, b);

            if (!SP2C::Collision::AABB_to_AABB(a->aabb, b->aabb))
                return;

            computePairs(list, a->children[0], b->children[0]);
            computePairs(list, a->children[0], b->children[1]);
            computePairs(list, a->children[1], b->children[0]);
            computePairs(list, a->children[1], b->children[1]);
        }
    }
}

Collider의 AABB를 빨간색, union의 fat AABB를 녹색으로 그리면 다음처럼 나타납니다. margin은 20px입니다.

AABB Tree

성능도 0.005초에서 0.001초 정도로 상승했습니다. 아마도요?

---

4. 비교 및 고찰

포스팅을 쓰면서 알고리즘을 빈번하게 수정했습니다.

이제 코드를 정리하고 각 상황에서의 성능을 비교해보도록 합시다.

 

여러 자잘한 부분을 수정했습니다만, 가장 크게 달라진 점은 Collider 생성 파트입니다.

무작위로 추가/삭제를 하려니 vector index가 저장해놓은 id와 달라지는 문제가 있어서 map으로 바꿨습니다.

그리고 시간 측정은 사실 대충 돌리고 적당한 중앙값을 선정한 것이기 때문에, 그렇게 믿을만한 지표는 아닙니다.

 

1024 objects (box and circle)

collider는 1024개 생성했고, 사각형과 원만을 생성했습니다. 화면 크기는 600x400 px입니다.

경우에 따라 배치하는 위치의 무작위성/움직임 등의 여부를 나누어 비교했습니다.

grid의 cell 크기는 40x40 px이고, collider의 크기는 5 ~ 30px 사이로 설정했습니다.

 

	Debug, 50% moving	Release, 50% moving
Brute Force	0.0956	0.0137
Sweep And Prune	0.0156	0.00142
Grid	0.0202	0.00185
Dynamic AABB Tree	0.0144	0.00188

Brute Force에 비해 다른 알고리즘들이 10배 정도 빠르네요.

 

	random pos no move	random pos 50% moving	random pos 100% moving	random x, same y, no move	same x, random y, no move	same pos, no move	random insert, random delete random moving	two pos, no move
SAP	0.00138	0.00142	0.00138	0.0064	0.0118	0.0632	0.00173	0.0307
Grid	0.00192	0.00185	0.00187	0.00875	0.0127	0.0664	0.00188	0.0445
DAT	0.00184	0.00188	0.00178	0.00744	0.0107	0.0544	0.00204	0.0285

 

x좌표는 0 ~ 600, y좌표는 0 ~ 400에 분포하도록 설정했기 때문에 성능에 영향이 좀 있습니다.

예를 들어 x좌표를 동일하게 한 경우와 y좌표를 동일하게 한 경우를 보면, x좌표를 동일하게 한 경우가 전체적으로 성능이 좀 더 느립니다. y좌표 상으로 무작위 분포하는 것이 collider가 겹치는 경우가 더 많기 때문인 것으로 보입니다.

 

random insert/delete의 경우에는 초기 생성한 collider는 움직이지 않도록 하고, 새로 생성하는 collider는 50%의 확률로 움직이게끔 했습니다.

two pos 같은 경우에는 두 좌표를 선입력하고, collider를 생성할 때 두 좌표중 하나에 배치하게끔 했습니다.

 

사실 대부분 상황에서는 각 알고리즘이 그렇게 유의미한 성능 차이를 보이고 있진 않습니다.

다만 각 알고리즘이 특히 성능이 저하될 것으로 보이는 경우가 있는 것 같네요.

 

SAP는 현재 x좌표를 기준으로 collider를 정렬합니다. 그래서 x좌표가 같은 상황에서는 성능이 내려갈 가능성이 높습니다.

표에서도 나오듯이, y좌표가 같은 상황에서는 SAP가 가장 빠르게 나오지만, x좌표가 같은 상황에서는 DAT보다 느립니다.

 

Grid는 사실 사용할 상황부터가 조건을 타는데, 한정된 공간을 grid로 만들어야 사용할 수 있다는 점입니다.

여기서는 화면 크기 600x400으로 한정했고, 그 밖에 나가는 것은 clamp를 하도록 설계했지만 다시 말하면 가변 크기인 공간에서는 사용하기 힘들고, clamp하는 collider가 많을 수록 가장자리 cell에 몰리는 것 또한 많아질 겁니다.

 

마찬가지로, 특정 cell에 collider가 몰려있으면 성능이 내려가기 쉽습니다. 좌표 범위를 한정짓는 조건들 (x좌표 고정, y좌표 고정, 둘 다 고정하는 경우 등)에서는 성능이 가장 나쁩니다.

여기서는 고려하지 않았지만 collider의 크기와 cell의 크기 또한 영향을 끼칩니다.

grid의 cell 크기가 collider 대비 너무 큰 경우에는 한 cell에 여러 개의 collider가 들어갈 수 있게 됩니다.

collider를 적당히 걸러내지 못하고 모든 pair에 대해서 검사하게 되겠죠.

cell 크기가 너무 작은 경우에는 여러 개의 cell에 같은 collider가 들어가게 됩니다.

이 경우에는 같은 pair가 중복해서 발생하게 될 가능성이 높아집니다.

 

그래서 적당한 cell 크기를 찾는 것이 중요합니다. collider 크기가 비교적 일정하면 그 크기에 맞춰서 정해주면 되겠지만,

너무 편차가 크다면 정하기가 어려워집니다.

 

DAT는 전체적으로 무난합니다. 가장 빠르지는 않지만, 그렇다고 가장 느리지도 않습니다.

collider를 update할 때마다 메모리를 쓰고 지우고 상위 노드에 전파시켜야한다는 점이 영향을 끼치지 않았나 싶습니다.

DAT가 다른 알고리즘 대비 성능이 좋은 경우가 뭐가 있을지 생각해본 결과가 two position입니다.

two position

DAT에서 parent의 fat AABB끼리 서로 충돌하지 않는다면, child node끼리도 충돌하지 않을 것이므로 거기서 멈추고 하위 노드를 모두 스킵할 수 있습니다.

모든 collider가 만나지 않게 멀리 배치하는 건 공간도 부족하고, 코드 작성하기도 복잡하기 때문에

두 그룹에 collider를 배치해서 그룹 내에서는 충돌하지만 그룹끼리는 충돌하지 않게끔 했습니다.

 

그리고 테스트하는 도중에 가끔씩 collider가 충돌 판정이 나지 않는 오류가 발생하더군요.

세 알고리즘을 동시에 돌려서 충돌 판정이 난 횟수를 세어봤는데 1~2번만 판정이 난 경우가 가끔씩 발생합니다.

알고리즘 상의 문제인가 싶어서 살펴봤는데 논리적인 오류는 없는 것 같고, 매번 돌릴 때마다 발생하는 경우가 달라서 오차의 문제라고 결론내렸습니다.

random 함수는 정해진 seed를 사용하고 있고, collider 크기가 꽤 작은 편이니까요.

 

음... 그래서 제 프로젝트에는 뭘 쓰는 게 좋을지는 결정하기가 힘드네요.

일단 세 방법 모두 구현해놓긴 할 생각인데, 게임이란게 상황이 여러 가지가 나올 수 있으니까요.

---

번외) Surface Area Heuristic

box2D 등에서는 Surface Area Heuristic (이하 SAH)를 사용하고 있길래, 이걸 구현해보려고 했었습니다.

음 그랬었는데

 

이론을 이해하기도 힘들고, 구현도 지금까지 했던 broad phase와는 좀 다른 느낌인 것 같고 그래서

써먹어보기가 힘들더군요. 기껏 어렵게 코드 분석해보고 따라 만들어봤더니 결국에는 제대로 작동하지가 않았습니다.

 

그래서 그나마 이해한 것에 대해서만 짧게 적어보고자 합니다.

 

Reference (였던 것):

 - https://medium.com/@bromanz/how-to-create-awesome-accelerators-the-surface-area-heuristic-e14b5dec6160

How to create awesome accelerators: The Surface Area Heuristic

 - https://github.com/lohedges/aabbcc/blob/master/src/AABB.cc

GitHub - lohedges/aabbcc: Dynamic AABB trees in C++ with support for periodic systems.

 

 - https://box2d.org/files/ErinCatto_DynamicBVH_Full.pdf

 - https://www.slideshare.net/hnam7/gdc13-vanden-bergenginophysicstut

Physics for Game Programmers: Spatial Data Structures

 

Reference에 대해서 이야기하자면,

1번 reference는 무슨 소리인지 아직 잘 이해가 안 됩니다. SAH를 검색하면 가장 먼저 나오는 글이

이 포스팅과 이 포스팅을 한글로 번역한 글인데, 번역 글은 이해가 더 어렵습니다.

왜 그 전공 과목에서는 항상 그렇지 않습니까. 한글이 영어보다 알아듣기 더 어려운 거

그런 탓에 어색해서 이해하기가 어려웠습니다. 뭐, 이런 글을 의역한다는 것부터가 보통 일이 아니긴 하겠네요.

 

아무튼, 요약하자면 검사할 물체들을 더 빡빡하게 담도록 node를 분할하자는 겁니다.

SAH는 그렇게 만들어 줄 최적의 지점이 될 확률이 높은 곳을 찾습니다.

 

1번 reference의 그림 설명에서는 3번이 최적의 지점입니다.

1번 방법은 나쁘진 않지만, 무작정 중간 지점을 기준으로 나누고 있고 이 다음부터는 높은 확률로 삼각형 그룹을 뚫고 지나가는 상황이 발생하게 됩니다.

2번 방법은... 그냥 대놓고 뚫고 지나갑니다. worst case가 되겠죠.

3번 방법이 의도한 최적의 지점이 됩니다. 삼각형이 많은 그룹이 있는 노드는 넓이가 더 작게 되도록 했고, 그만큼 왼쪽 노드의 검사는 훨씬 널널해질 겁니다.

 

대충 이렇게 놓고 보니, 뭔가 제가 생각하던 게 아닌 것 같았습니다.

난 충돌할 가능성이 높은 두 물체를 찾는 것이지, ray cast를 할 생각이 아닌데 말이죠.

3D라서 그런걸까? 그래서 box2D의 Dynamic AABB Tree 코드로 넘어갔습니다.

 

2번 reference는 box2D의 b2DynamicTree를 써먹기 좋게 옮겨온 github이고,

3번 reference는 box2D에서의 Dynamic AABB Tree에 관해 설명하는 pdf 자료입니다.

4번 reference는 collision에 쓰는 data structure에 관한 설명입니다. 후반부에 SAH에 관한 설명이 있습니다.

 

읽어봤더니, 위에서 구현한 Dynamic AABB Tree와 비슷했습니다.

Surface Area, 즉 겉넓이가 최소가 되도록 AABB를 추가하는 거였는데

2D에서는 surface area가 volume이죠.

다만 차이점은 있었는데, 위에서는 반드시 leaf - leaf 간에 merge를 한 node를 생성해서 추가했다면

여기서는 branch - leaf 간에도 merge를 하더군요.

그래서 branch와 merge하는 것이 이득인지, children으로 넘어가는 게 이득인지를 판단해줄 필요가 있습니다.

 

3번 reference에서는 branch and bound 알고리즘으로 설명하고 있습니다.

현재 node $N$과 추가하려는 leaf $L$을 합치는 비용 $C_N$은 $N$과 $L$을 합친 AABB를 가지는 새로운 parent node를 그 자리에 추가해야 합니다. 그 후에 상위에 있는 ancestor node들을 업데이트해줘야 됩니다.

따라서 $C_N$은 surface area의 증가량인 (parent node의 surface area = $N \cup L$의 surface area + $\Delta$ ancestor의 surface area)가 됩니다.

$\Delta$ ancestor의 surface area = 새로운 ancestor의 surface area - 기존 ancestor의 surface area

= (ancestor의 AABB에 $L$의 AABB를 union한 AABB의 surface area) - 기존 surface area 입니다.

 

반면 children으로 넘어갔을 때의 비용은,

child node가 leaf node인 경우 child와 leaf를 합친 새로운 node의 surface area + ancestor의 surface area 변화량이고

leaf node가 아닌 경우에는 최소 child와 leaf를 합친 surface area - child의 기존 surface area + ancestor의 surface area 변화량입니다.

 

라고 적긴 했는데, 이게 뭔 소리지?

child node도 branch인 경우에는 child node에 합칠지, child의 child에 합칠지에 따라 비용이 또 달라집니다만

일단 여기서는 최소가 되는 경우 (child에서도 children으로 전파하는 경우)의 값을 계산한 것 같습니다.

(child + leaf의 surface area - child의 surface area)는 그 경우에 child node의 surface area 변화량이거든요.

 

뭐 아무튼 그렇다치고 넘어가려는데 코드를 보면 2를 곱합니다.

double combinedSurfaceArea = combinedAABB.getSurfaceArea();

// Cost of creating a new parent for this node and the new leaf.
double cost = 2.0 * combinedSurfaceArea;

// Minimum cost of pushing the leaf further down the tree.
double inheritanceCost = 2.0 * (combinedSurfaceArea - surfaceArea);

 

(source from: https://github.com/lohedges/aabbcc/blob/master/src/AABB.cc row 708 ~ 714)

 

왜 2를 곱하는지 모르겠어서 찾아봤는데 box2d github에 있던 issue의 답변은 이렇습니다.

"두 개의 child node를 방문해야 되서 그런 것 같다"

 

여전히 이해를 못하겠습니다. 그거랑 이 비용이 무슨 상관이지?

그래서 2를 곱하지 않고 돌려봤더니 작동이 안 됩니다.

진짜 2를 곱해야되나? 근데 2를 곱해도 똑같습니다. 안 돌아가요. ㅋㅋ;

 

결국 폐기했습니다. 구현이 뭔가 잘못됐나봐요.

사실 reference의 code에는 collider pair를 구하는 함수가 없습니다.

위에서 구현한 AABB Tree를 갖다가 좀 변형해서 썼는데, 그게 뒤섞이면서 이렇게 된 걸까요.

 

대신에 query 함수가 있는데, 이건 주어진 AABB 객체와 충돌하는 object lsit를 구할 수 있습니다.

그럼 이건 잘 돌아갔느냐? 나름 돌아가긴 했는데, 인식이 안 되는 collider가 한 두개씩 보이더군요.

이게 알고리즘 상의 문제인지 오차 상의 문제인지는 잘 모르겠습니다. 다른 알고리즘들도 다 그런 증상이 있었으니까요.

 

그러면 글은 여기까지 쓰겠습니다.

사실 이 파트를 지금 2번이나 날려먹고 다시 쓰고 있습니다.

아니 저장했다면서 왜 다시 불러오면 끝부분을 자꾸 날려먹는 거나고