Các thư viện tiêu chuẩn giữ lại lập trình viên từ việc đổi mới lại cái bánh xe. Steve McConnell
STDIO Xét va chạm (Collision Detection) là một việc quan trọng trong lập trình game. Công việc này đòi hỏi chi phí cao, đặc biệt khi số lượng thực thể (entity) trong game là rất lớn. Quadtree là một giải thuật đơn giản và hiệu quả giúp giảm thiểu chi phí dùng cho việc xét va chạm giữa các đối tượng trong game.
Nội dung bài viết

Giới thiệu

Xét va chạm (Collision Detection) là một việc quan trọng trong lập trình game. Công việc này đòi hỏi chi phí cao, đặc biệt khi số lượng thực thể (entity) trong game là rất lớn. Để đảm bảo độ chính xác của game, ta phải kiểm tra từng đôi một các entity với nhau. Làm một phép thử, nếu game của chúng ta có 100 entity riêng biệt, ta sẽ mất một lượng chi phí không nhỏ cho C2100 lần kiểm tra. Con số này sẽ ngày càng khủng khiếp khi số lượng entity trong game ngày một tăng nhiều. Vậy có một giải thuật nào có thể giúp giảm thiểu chi phí cho việc xét va chạm giữa các entity trong game? Bài viết này sẽ giới thiệu một giải thuật đơn giản nhưng hiệu quả để giải quyết vấn đề này. Đó là giải thuật Quadtree.

Tiền đề bài viết

Trong quá trình làm việc thực tế, tôi đã cảm thấy bế tắc trong việc xét va chạm giữa các entity trong game, bởi số lượng entity ngày một tăng cao khiến chi phí cần cung cấp đã vượt quá mức chấp nhận được. Qua nghiên cứu và tìm hiểu, tôi đã ứng dụng thành công giải thuật Quadtree vào game của mình và đã đạt được hiệu quả bất ngờ. Bài viết này mong muốn chia sẻ kiến thức này đến với mọi người.

Đối tượng hướng đến

Bài viết hướng đên đối tượng là những lập trình viên đang nghiên cứu phát triển game, cần một giải pháp tối ưu để tiết kiệm chi phí trong game.

Ngôn ngữ và các công cụ cần thiết

Để đơn giản và dễ hiểu, trong bài viết tôi sử dụng ngôn ngữ C++ trên môi trường Visual Studio 2013 Professional. Các bạn cũng có thể sử dụng một công cụ khác hay một ngôn ngữ khác để hiện thực, vì giải thuật là giống nhau với hầu hết các ngôn ngữ lập trình thông dụng hiện nay.

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ỏ hơn 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 sẽ chia vùng hiện tại thành 4 vùng. Do đó mỗi node trong quadtree có thể 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 chúng ta quản lý các đối tượng trong game một cách hiệu quả hơn, 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”.

ss_1
 
Trên đây là hình ảnh mô phỏng lại cách hoạt động của quadtree. Qua đó, ta thấy 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 đó, ta sẽ tiết kiệm được một lượng chi phi không nhỏ, nhất là khi số lượng object trong game ngày 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 (vẽ) 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ì ta không nhất thiết phải render nó.

Khi sử dụng Quadtree, ta dễ dàng nhận biết 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. Do đó FPS của game sẽ đượ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 và 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 Object tối đa trong một node và giới hạn mức độ phân chia, ta định nghĩa 2 const sau bằng từ khoá #define:

#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 nhất.

Tôi sẽ giải thích ý nghĩa và hiện thực từng hàm được khai báo ở trên.

Hàm 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;
}

Hàm Clear sẽ giải phóng các vùng nhớ được cấp phát cho các biến m_region, m_objects_list, m_nodes. Vì mỗi node cũng là một Quadtree nên hàm 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.

Hàm 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 hàm là xác định phạm vi của entity được truyền vào hàm. Nếu entity thuộc phạm vi của vùng hiện tại, hàm sẽ trả về giá trị true, ngược lại là false.

Hàm 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 hàm khá đơn giản: 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 hàm này khi thoả điều kiện.

Hàm 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();
        }
    }
}

Đây là hàm quan trọng, 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, hàm 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, ta dễ dà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ì ta sẽ 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, ta sẽ 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ó.

Hàm 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);
        }
    }
}

Hàm 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 được xét. Bằng cách xét vị trí của entity trong quadtree, ta dễ dàng 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

Mục tiêu của chúng ta khi tạo ra quadtree là để giúp quản lý các đối tượng trong game một cách hiệu quả hơn. Dưới đây là cách mà tôi sử dụng để xét va chạm giữa các đối tượng trong game:

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ủa tôi 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ủa bạn có một cột hiển thị các thông tin như level, scores, lives, … thì các bạn 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 tôi sẽ không hiện thực chi tiết hàm IsCollide. Các bạn có thể tự tra cứu, hoặc liên hệ trực tiếp với tôi. Tôi sẽ giải đáp các thắc mắc của các bạn trong thời gian sớm nhất.

Bạn cần hỗ trợ các dự án kết nối không dây?

Quí doanh nghiệp, cá nhân cần hỗ trợ, hợp tác các dự án IoT, kết nối không dây. Vui lòng liên hệ, hoặc gọi trực tiếp 0942.111912.

  • TỪ KHÓA
  • Arduino
  • ESP32
  • ESP8266
  • Wifi
  • Bluetooth
  • Zigbee
  • Raspberry Pi
THẢO LUẬN
ĐÓNG