Hiện Thực Quadtree Và Ứng Dụng trong Lập Trình Game

Để đảm bảo độ chính xác của game, phải kiểm tra từng đôi một các đối tượng với nhau. Làm một phép thử, nếu game có 100 thực thể riêng biệt, sẽ mất một lượng chi phí không nhỏ cho C2100 là 4950 lần kiểm tra.

Con số này sẽ càng lớn khi số lượng thực thể trong game tăng dần lên. Cần 1 giải thuật có thể giúp giảm thiểu chi phí cho việc xét va chạm giữa các thực thể trong không gian, trong đó Quadtree là 1 giải thuật hữu dụng.

Quadtree là gì?

Quadtree là một cấu trúc dữ liệu phân nhánh dạng cây, được sử dụng để phân hoạch vùng không gian hai chiều hiện tại thành các vùng nhỏ và dễ quản lý hơn. Khác với cây nhị phân, mỗi lần phân hoạch, Quadtree chia vùng hiện tại thành 4 vùng. Do đó mỗi node trong Quadtree có 4 node dẫn xuất hoặc không có node dẫn xuất nào, không có ngoại lệ.

Việc sử dụng Quadtree giúp quản lý các đối tượng trong không gian một cách hiệu quả, bằng cách phân chia vùng cần xử lý các đối tượng thành những vùng con, các đối tượng sẽ được đưa vào các vùng tương ứng và được quản lý riêng biệt. Quá trình phân chia cứ thế tiếp diễn cho đến khi mỗi vùng chỉ chứa một số lượng đối tượng nhất định hoặc mức độ phân chia đạt mức chấp nhận được.

2 vùng được đánh dấu bằng mũi tên không có khả năng tương tác với nhau (tương tự đối với các vùng khác). Do đó, sẽ tiết kiệm được một lượng chi phí không nhỏ khi số lượng đối tượng trong không gian càng nhiều.

Ứng dụng của Quadtree trong game

Quadtree thường được ứng dụng vào việc xét va chạm giữa các đối tượng, update và render các đối tượng.

Chi phí cho việc khởi tạo Quadtree nhỏ hơn rất nhiều so với việc update, render, xử lý va chạm, ... các đối tượng không cần thiết. Ví dụ một đối tượng nằm ngoài vùng nhìn thấy của camera trong game thì không nhất thiết phải render.

Khi sử dụng Quadtree, các đối tượng thuộc 2 node cách biệt nhau không có khả năng va chạm với nhau. Chi phí giảm đồng nghĩa với việc thời gian của một vòng lặp game được rút ngắn, FPS của game được cải thiện.

Hiện thực Quadtree

Lớp Quadtree

Một Quadtree sẽ lưu trữ một số thông tin cần thiết như:

• Phạm vi của Quadtree.
• Danh sách các đối tượng.
• Danh sách các node dẫn xuất.
• Level.

Khai báo class Quadtree như sau:

class Quadtree
{
private:
    int            m_level;
    Rect*          m_region;
    list*          m_objects_list;
    Quadtree**     m_nodes;

    bool           IsContain(Entity* entity);
    void           Split();
public:
    Quadtree();
    Quadtree(int level, Rect* region);
    ~Quadtree();
    
    void           Clear();
    void           Insert(Entity* entity);
    list*          Retrieve(list* return_objects_list, Entity* entity);
};

Để giới hạn số lượng đối tượng tối đa trong một node và giới hạn mức độ phân chia, sử dụng 2 giới hạn sau:

#define MAX_LEVEL                5
#define MAX_OBJECT_IN_REGION     4

Do Quadtree có cấu trúc phân cấp nên hiện thực bằng phương pháp đệ quy sẽ đơn giản và dễ hiểu hơn.

Phương thức Clear

void Quadtree::Clear()
{
    // Clear all nodes
    if(m_nodes)    
    {
        for(int i = 0; i < 4; i++)
        {
            m_nodes[i]->Clear();
            delete m_nodes[i];
        }
        delete[] m_nodes;
    }
    
    // Clear current Quadtree
    m_objects_list->clear();

    delete m_objects_list;
    delete m_region;
}

Clear giải phóng các vùng nhớ được cấp phát cho m_region, m_objects_list, m_nodes. Vì mỗi node cũng là một Quadtree nên Clear sẽ thực hiện đệ quy, giải phóng từng node dẫn xuất trước khi giải phóng node gốc.

Phương thức IsContain

bool Quadtree::IsContain(Entity* entity)
{
    Rect* bound = entity->GetBoundingBox();

    return !(bound->x + bound->width < m_region->x ||
             bound->y + bound->height < m_region->y ||
             bound->x > m_region->x + m_region->width ||
             bound->y > m_region->y + m_region->height);
}

Mục tiêu của IsContain là xác định phạm vi của đối tượng được truyền vào. Nếu đối tượng thuộc phạm vi của vùng hiện tại, IsContain sẽ trả về giá trị true, ngược lại là false.

Phương thức Split

void Quadtree::Split()
{
    m_nodes = new Quadtree*[4];

    m_nodes[0] = new Quadtree(m_level + 1,
                              new Rect(m_region->x, m_region->y, m_region->width/2, m_region->height/2));
    m_nodes[1] = new Quadtree(m_level + 1,
                              new Rect(m_region->x + m_region->width/2, m_region->y, m_region->width/2, m_region->height/2));
    m_nodes[2] = new Quadtree(m_level + 1,
                              new Rect(m_region->x, m_region->y + m_region->height/2, m_region->width/2, m_region->height/2));
    m_nodes[3] = new Quadtree(m_level + 1,
                              new Rect(m_region->x + m_region->width/2,
                              m_region->y + m_region->height/2, m_region->width/2, m_region->height/2));
}

Mục đích của Split là khởi tạo 4 node dẫn xuất cho node hiện tại. Mỗi node dẫn xuất cũng là một Quadtree nên cũng có khả năng gọi Split khi thoả điều kiện.

Phương thức Insert

void Quadtree::Insert(Entity* entity)
{
    // Insert entity into corresponding nodes
    if(m_nodes)
    {
        if(m_nodes[0]->IsContain(entity))
            m_nodes[0]->Insert(entity);
        if(m_nodes[1]->IsContain(entity))
            m_nodes[1]->Insert(entity);
        if(m_nodes[2]->IsContain(entity))
            m_nodes[2]->Insert(entity);
        if(m_nodes[3]->IsContain(entity))
            m_nodes[3]->Insert(entity);

        return; // Return here to ignore rest.
    }
    
    // Insert entity into current quadtree
    if(this->IsContain(entity))
        m_objects_list->push_back(entity);

    // Split and move all objects in list into it’s corresponding nodes
    if(m_objects_list->size() > MAX_OBJECT_IN_REGION && m_level < MAX_LEVEL)
    {
        Split();

        while(!m_objects_list->empty())
        {
            if(m_nodes[0]->IsContain(m_objects_list->back()))
                m_nodes[0]->Insert(m_objects_list->back());
            if(m_nodes[1]->IsContain(m_objects_list->back()))
                m_nodes[1]->Insert(m_objects_list->back());
            if(m_nodes[2]->IsContain(m_objects_list->back()))
                m_nodes[2]->Insert(m_objects_list->back());
            if(m_nodes[3]->IsContain(m_objects_list->back()))
                m_nodes[3]->Insert(m_objects_list->back());

            m_objects_list->pop_back();
        }
    }
}

Insert là sự tương tác trực tiếp giữa Quadtree và game. entity được truyền vào sẽ được thêm vào đúng vị trí thích hợp trong Quadtree. Sau khi thêm vào, nếu số lượng đối tượng trong danh sách vượt quá mức quy định, Split sẽ được gọi, các entity trong danh sách sẽ được di chuyển vào các node thích hợp. Đồng nghĩa với việc danh sách đối tượng ở node hiện tại sẽ không còn chứa đối tượng nào cả.

Nếu một đối tượng nằm hoàn toàn trên một vùng, thêm đối tượng đó vào danh sách đối tượng của vùng đó. Tuy nhiên, tồn tại một số trường hợp mà một đối tượng nằm trên hai, ba hoặc cả bốn node thì làm thế nào? Khi đó, đối tượng này có khả năng va chạm với các đối tượng thuộc nhiều vùng khác nhau. Để đơn giản và đạt độ chính xác, thêm một đối tượng vào bất cứ vùng nào có chứa một phần của nó.

Phương thức Retrieve

void Quadtree::Retrieve(list* return_objects_list, Entity* entity)
{
    if(m_nodes)
    {
        if(m_nodes[0]->IsContain(entity))
            m_nodes[0]->Retrieve(return_objects_list, entity);
        if(m_nodes[1]->IsContain(entity))
            m_nodes[1]->Retrieve(return_objects_list, entity);
        if(m_nodes[2]->IsContain(entity))
            m_nodes[2]->Retrieve(return_objects_list, entity);
        if(m_nodes[3]->IsContain(entity))
            m_nodes[3]->Retrieve(return_objects_list, entity);

        return; // Return here to ignore rest.
    }

    // Add all entities in current region into return_objects_list
    if(this->IsContain(entity))
    {
        for(auto i = m_objects_list->begin(); i != m_objects_list->end(); i++)
        {
            if(entity != *i)
                return_objects_list->push_back(*i);
        }
    }
}

Phương thức Retrieve có chức năng trả về danh sách tất cả các đối tượng có khả năng xảy ra va chạm với entity đang xét. Bằng cách xét vị trí của entity trong Quadtree, lấy ra được tất cả các đối tượng thuộc cùng một vùng với entity đang xét, từ đó thêm toàn bộ các đối tượng trong vùng đó vào return_objects_list.

Sử dụng Quadtree xét va chạm giữa các đối tượng

void DetectCollision()
{
    Quadtree* quadtree = CreateQuadTree();

    list* return_objects_list = new list();
    list* entity_list = EntityManager::GetInstance()->GetEntityList();

    for(list::iterator i = entity_list->begin(); i != entity_list->end(); i++)
    {
        //Get all objects that can collide with current entity
        quadtree->Retrieve(return_objects_list, *i);

        for(auto x = return_objects_list->begin(); x != return_objects_list->end(); x++)
        {
            if(IsCollide(*i, *x))  // Your algorithm about Collision Detection
            {
                // Do something here
            }
        }

        return_objects_list->clear();
    }

    quadtree->Release();

    delete return_objects_list;
    delete quadtree;
}

Hiện thực phương thức CreateQuadTree được sử dụng trong hàm trên:

Quadtree* CreateQuadTree()
{
    // Init base game region for detecting collision
    Quadtree* quadtree = new Quadtree(1, new Rect(0, 0, 800, 600));
    
    list* entity_list = EntityManager::GetInstance()->GetEntityList();
    for(auto i = entity_list->begin(); i != entity_list->end(); i++)
        quadtree->Insert(*i);

    return quadtree;
}

Màn hình game có kích thước là 800x600. Tuy nhiên, các thông số truyền vào là kích thước màn hình cần xét va chạm chứ không phải là màn hình game. Giả sử game có một cột hiển thị các thông tin như level, scores, lives, ... thì cần tuỳ chỉnh lại các thông số này cho phù hợp.

Giải thuật xét va chạm giữa các đối tượng nằm ngoài phạm vi của bài viết nên không được hiện thực chi tiết phương thức IsCollide.