STDIO
Tìm kiếm gần đây

    Nội dung

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

    31/07/2015
    20/05/2016
    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.

    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ài viết liên quan

    Áp Dụng Kĩ Thuật OOP Trong Quá Trình Xây Dựng Framework Dựa Trên Thư Viện SDL

    Trong quá trình xây dựng Engine của bản thân mình, thông qua bài viết Khởi Tạo Môi Trường Lập Trình Game Sử Dụng Thư Viện SDL (Simple DirectMedia Layer) của Nghĩa Nguyễn ...

    Hoàng Thái09/09/2015

    Lập Trình Multithreading Trong Ngôn Ngữ Lập Trình Java

    Trong chương trình của chúng ta đôi khi ta cần thực thi nhiều tác vụ cùng một lúc như thao tác với network, đọc ghi file... Theo cách lập trình thông thường thì ta chỉ ...

    Nguyễn Nghĩa19/11/2015

    Sử Dụng CSDL Hướng Đối Tượng DB4O Với Android - Phần 2 Thực Hiện App Đơn Giản - Chương Trình Trắc Nghiệm

    Tiếp theo bài viết 'Sử dụng hệ quản trị cơ sở dữ liệu DB4O trên Android', bài viết này sẽ hướng dẫn xây dựng một chương trình trắc nghiệm đơn giản và tập trung vào các ...

    Nguyễn Hồng Sơn15/03/2016

    Ứng Dụng Của StartCoroutine Trong Unity

    Khi tiếp nhận và xử lý các sự kiện thu được, có những lúc chúng ta cần một khoảng thời gian chờ giữa việc nhận được sự kiện và xử lý sự kiện. Có khá nhiều những trường ...

    Rye Nguyen08/08/2015

    Lập Trình Hiệu Ứng Trong Cocos2d-x 3.x.x

    Bài viết nằm trong loạt bài viết của chương trình Tự Học Cocos2d-x 3.x.x. Trong bài viết sẽ giới thiệu khái niệm về lập trình hiệu ứng, thuộc tính, và ví dụ về sử dụng ...

    Trương Xuân Đạt23/01/2015

    Hiện Thực Game Zero Với Unity - Phần 1 - Nhận Sự Kiện Button

    Tôi tiếp tục chuỗi bài viết giúp bạn đọc xây dựng một game đơn giản thực tế: Hướng Dẫn Hiện Thực Game Zero Với Unity. Qua chuỗi bài viết, hi vọng bạn đọc sẽ dễ dàng hơn ...

    Rye Nguyen09/08/2015

    Tổng Quan Về Ngôn Ngữ Lập Trình Java

    Java là một trong những ngôn ngữ lập trình mạnh và được sử dụng đông đảo trong phát triển phần mềm, các trang web, game hay ứng dụng trên các thiết bị di động, ngôn ngữ ...

    Lê Minh Trung20/05/2015

    Hiện Thực Game Zero Với Unity - Phần 3 - Điểm Số Và Progress Timer

    Tiếp tục chuỗi bài viết Hướng Dẫn Hiện Thực Game Zero Với Unity, ở phần trước, tôi đã giới thiệu và hướng dẫn các bạn cách hiện thực gameplay của game Zero. Trong phần 3 ...

    Rye Nguyen10/08/2015

    Lập Trình Game Với DirectX - Phần 2: Khởi Tạo Cửa Sổ

    Ở bài viết cũ của mình, tôi có đề cập đến Game thực chất là 1 đối tượng trong chương trình. Đối tượng đó trải qua 3 giai đoạn chính gồm: Khởi Tạo (init), Chạy (run) và ...

    Trần Hữu Danh21/01/2015

    Lập Trình Windows Phone 8.1 - Phần 1: Thiết Lập Môi Trường Và Cài Đặt Công Cụ

    Trong lĩnh vực lập trình, thiết lập môi trường cũng như cài đặt công cụ là bước quan trọng và căn bản đầu tiên mà các lập trình viên phải biết. Với lập trình Windows ...

    Nguyễn Nghĩa23/09/2015

    STDIO
    Trang chính
    Công ty TNHH STDIO

    30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
    +84 28.36205514 - +84 942.111912
    [email protected]

    383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
    Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012

    ©STDIO, 2013 - 2020