Game Dev - Cấu Trúc Dữ Liệu Quad Tree Trong Kiểm Tra Va chạm
Disclaimer: Mình là một người thích lập trình và đồ họa máy tính, bài viết mang tính chia sẻ quá trình học của mình nhằm lan tỏa và củng cố kiến thức, nếu có gì sai xin mọi người góp ý nhe.
Chào mọi người, trước đây mình có hay xem các video coding challenge trên kênh The Coding Train của chú Danial Shiffman. Các video rất hay và truyền cảm hứng cho mình, coding lúc này như là một nghệ thuật. Tuy nhiên, lúc đó mình quá lười để học làm theo nên hôm nay mình sẽ vừa học vừa viết bài để duy trì động lực.
Không dài dòng nữa, nay mình sẽ tìm hiểu về cấu trúc dữ liệu Quad Tree, vốn được sử dụng rất nhiều trong lập trình game và đồ họa máy tính.
I. Bài Toán Kiểm Tra Va Chạm
Hãy tưởng tượng, bạn đang chơi tựa game Vampire Survival, có cả trăm con quái đang vây bắt bạn, bạn thì liên tục bắn ra các vũ khí để tiêu diệt chúng. Mỗi con quái bị tiêu diệt lại rơi ra kinh nghiệm và bạn cố gắng nhặt những khối kinh nghiệm đó. Bây giờ câu hỏi đặt ra là:
- Làm sao biết được vũ khí bắn ra có chạm vào con quái nào hay không.
- Làm sao biết được mình có đang chạm vào khối kinh nghiệm nào để nhặt hay không.
II. Phương Pháp
Để đơn giản hóa, mình sẽ mô phỏng va chạm bằng các hình tròn nhỏ liên tục di chuyển trong không gian 2D.
1. Bruteforce
Để trả lời cho câu hỏi ở mục I, ta nghĩ ngay tới việc kiểm tra 1 hình tròn này với tất cả các hình tròn khác trong game, mình sẽ gọi phương pháp này là brute force.
for (int i = 0; i < circles.size(); i++) {
Circle* circle = circles[i];
for (int j = 0; j < circles.size(); j++) {
if (i == j) continue;
Circle* other = circles[j];
if (circle.collide(other)) {
// Xử lí va chạm.
}
}
}
Đối với số lượng đối tượng ít thì chương trình chạy mượt 60fps. Tuy nhiên, khi số lượng các đối tượng tăng lên hơn 2000, hạn chế chí mạng của này lộ rõ do có độ phức tạp quá lớn: O(N^2).
Bất cập không chỉ nằm ở độ phức tạp, mà còn về logic: tại sao chúng lại cần phải kiểm tra va chạm giữa 1 đối tượng ở góc dưới bên trái với 1 đối tượng ở góc trên bên phải?
2. Quad Tree - Giải pháp thú vị
Xuất phát từ câu hỏi tại sao chúng lại cần phải kiểm tra va chạm giữa 1 đối tượng ở góc dưới bên trái với 1 đối tượng ở góc trên bên phải? Vậy làm sao chúng ta có thể xác định các đối tượng gần một hình tròn để kiểm tra va chạm.
Quad tree thừa kế ý tưởng chia để trị, cụ thể là ta sẽ xem màn hình game như là một chiếc hộp lớn:
- Ta sẽ lưu các hình tròn vào chiếc hộp lớn.
- Nếu như chiếc hộp cha vượt ngưỡng phần tử cần chứa, ta thêm vào hộp lớn 4 hộp con.
- Áp dụng logic đó cho các hộp con và tiếp tục cho đến khi tất cả các hình còn được fill vào cây.
Khi này, nếu hình tròn cần kiểm tra va chạm nằm ở góc trên bên trái, ta chỉ cần kiểm tra nó với các hình tròn khác nằm trong các hộp xung quanh nó.
3. Cài đặt
a. Vẽ hình tròn
Trong dự án này mình sẽ sử dụng c++ và raylib để visualize cấu trúc Quad Tree.
Đầu tiên ta xây dựng class Circle:
class Circle {
Vector2 position;
Vector2 velocity;
float radius;
float speed;
}
Để vẽ hình tròn ta sử dụng hàm DrawCircle()
void show() {
DrawCircle(position.x, position.y, radius, Color{0, 0, 0, 255});
}
b. Di chuyển hình tròn
Mình sẽ làm hình tròn di chuyển theo cách đơn giản nhất là thay đổi vị trí của nó theo vận tốc. Bên cạnh đó cũng phải ngăn các hình tròn của chúng ta chạy khỏi màn hình.
void move() {
if (x <= 0 || x >= WINDOW_WIDTH) vx *= -1;
if (y <= 0 || y >= WINDOW_HEIGHT) vy *= -1;
float dt = GetFrameTime();
x += vx * dt;
y += vy * dt;
}
c. Kiểm tra va chạm
Mình sẽ dùng brute force trước:
void check_circles_collision() {
for (int i = 0; i < circles.size(); i++) {
Circle* circle = circles[i];
for (int j = 0; j < circles.size(); j++) {
if (i == j) continue;
Circle* other = circles[j];
if (circle->get_position().x == other->get_position().x &&
circle->get_position().y == other->get_position().y) continue;
float total_radius = circle->get_radius() + other->get_radius();
if (circle->get_distance(other) < total_radius) {
resolve_circle_collision(circle, other);
}
}
}
}
Khi kiểm tra va chạm mình có thể biết được liệu có 2 hình tròn nào xếp chồng lên nhau không bằng cách tính khoảng cách d giữa 2 hình tròn, sau đó so sánh nó với tổng bán kính r1 + r2 của 2 hình tròn đó:
- Nếu
d < r1 + r1=> 2 hình tròn đè lên nhau
Để xử lí tình huống 2 hình đề lên nhau, mình sẽ làm đơn giản bằng cách tách nó ra theo hướng va chạm.
void resolve_circle_collision(Circle* circle1, Circle* circle2) {
float r1 = circle1->get_radius();
float r2 = circle2->get_radius();
float d = circle1->get_distance(circle2);
float amount = (r1 + r2 - d) / 2.0f;
Vector2 c1_center = circle1->get_position();
Vector2 c2_center = circle2->get_position();
Vector2 new_direction = Vector2Normalize(Vector2Subtract(c1_center, c2_center));
float new_c1_x = c1_center.x + amount * new_direction.x;
float new_c1_y = c1_center.y + amount * new_direction.y;
float new_c2_x = c2_center.x - amount * new_direction.x;
float new_c2_y = c2_center.y - amount * new_direction.y;
circle1->set_position({ new_c1_x, new_c1_y });
circle2->set_position({ new_c2_x, new_c2_y });
Vector2 new_c1_vel = Vector2Scale(new_direction, circle1->get_speed());
Vector2 new_c2_vel = Vector2Scale(Vector2Scale(new_direction, -1), circle2->get_speed());
circle1->set_velocity({ new_c1_vel.x, new_c1_vel.y });
circle2->set_velocity({new_c2_vel.x, new_c2_vel.y});
}
c. Quad Tree
Các thuộc tính cần có của Quad Tree gồm:
class QuadTree {
BBox box;
std::vector<Circle*> list;
int threshold = 5;
std::shared_ptr<QuadTree2D> topleft;
std::shared_ptr<QuadTree2D> topright;
std::shared_ptr<QuadTree2D> bottomleft;
std::shared_ptr<QuadTree2D> bottomright;
}
- box: bounding box của quadtree, gồm các thuộc tính để xác định vị trí và kích thước của hộp (position và size).
- list: danh sách chứa tất cả các hình tròn trong game.
- threshold: ngưỡng chứa của 1 danh sách.
- topleft, topright, bottomleft,bottomright: các quadtree con sẽ được tạo khi mà size của list đạt ngưỡng threshold.
Bây giờ mình sẽ đi qua các phương thức cần có để quad tree này hoạt động. Mình sẽ có 2 phương thức chính: insert và query.
Phương thức insert sẽ thêm các hình tròn vào cấu trúc quad tree để quản lý và xử lí.
- Nếu size của list chưa đạt ngưỡng, thì thêm hình tròn vào
- Nếu size của list đã đạt ngưỡng:
- Ta sẽ tạo các quad tree con.
- Kiểm tra xem hình tròn đang xét đang nằm ở trong vùng quad tree con nào, và thực hiện gọi hàm insert của quad tree con đó (có thể dùng đệ quy hoặc stack) để thêm hình tròn đó vào.
void insert(Circle* circle) {
if (list.size() < threshold) {
list.push_back(circle);
return;
}
if (!is_divided) {
// Tạo quad tree con (topleft, bottomleft, topright, bottomright)
divide();
is_divided = true;
}
// Kiểm tra hình tròn đang xét đang nằm ở trong vùng quad tree con nào
if (topleft->box.contains(circle)) {
topleft->insert(circle);
}
else if (topright->box.contains(circle)) {
topright->insert(circle);
}
else if (bottomleft->box.contains(circle)) {
bottomleft->insert(circle);
}
else {
bottomright->insert(circle);
}
}
Khi này ta đã tạo ra được một cấu trúc quad tree. Bây giờ, khi xét một hình tròn bất kì ta cần phải lấy ra được các hình tròn gần xung quanh nó, mình sẽ xem vùng tìm kiếm range này như là một bounding box.
Ta biết rằng các quad tree như các hộp chứa được xác định bởi bouding box của nó. Vậy thì khi này ta cần kiểm tra xem bounding của quad tree nào cắt với vùng cần tìm kiếm thì ta trả về các hình tròn trong list của quad tree đó.
Vì các bounding box này là các hình chữ nhật nên ta sẽ sử dụng thuật toán AABB để kiểm tra xem các bounding box có cắt nhau hay không.
void query(BBox range, std::vector<Circle*>& found) {
std::stack<std::shared_ptr<QuadTree2D>> stack;
stack.push(shared_from_this());
while (!stack.empty()) {
std::shared_ptr<QuadTree2D> current = stack.top();
stack.pop();
if (current->box.intersects(range)) {
for (int i = 0; i < current->list.size(); i++) {
if (range.contains(current->list[i])) {
found.push_back(current->list[i]);
}
}
if (current->is_divided) {
stack.push(current->topleft);
stack.push(current->topright);
stack.push(current->bottomleft);
stack.push(current->bottomright);
}
}
}
}
Và như vậy với 6000 đối tượng, bằng cách sử dụng quadtree, fps đã tăng từ 9 lên 23.
Tìm hiểu thêm trong repo của mình: https://github.com/gnol-aig/quadtree2d/tree/main
References
Coding Challenge #98.1: Quadtree - Part 1
All rights reserved
