Sắp xếp, quét và cắt tỉa: Thuật toán phát hiện va chạm (2023)

 (leanrada.com)
3 điểm bởi GN⁺ 2024-08-15 | 1 bình luận | Chia sẻ qua WhatsApp

Thuật toán phát hiện va chạm

Phát hiện va chạm

  • Trong lập trình trò chơi điện tử, phát hiện va chạm là một vấn đề rất phổ biến
  • Đây là yếu tố thiết yếu để ngăn các nhân vật đi xuyên qua nhau hoặc để triển khai physics engine

Cách tiếp cận đơn giản 🐥

  • Phương pháp kiểm tra mọi cặp đối tượng để xác định có va chạm hay không
  • Ví dụ mã: 
    for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}
  • Cách này có độ phức tạp thời gian O(n^2)

Vấn đề hiệu năng

  • Khi số lượng đối tượng tăng lên, các vấn đề hiệu năng sẽ xuất hiện
  • Ví dụ, khi n = 20 thì cần kiểm tra 190 cặp

Cải thiện giải pháp

  • Điều quan trọng là giảm các tác vụ không cần thiết
  • Tối ưu hàm intersects(): 
    function intersects(object1, object2) {
  return object1.left < object2.right &&
         object1.right > object2.left &&
         object1.top < object2.bottom &&
         object1.bottom > object2.top;
}

Tối ưu hóa bằng sắp xếp

  • Nếu sắp xếp các đối tượng theo tọa độ x, có thể giảm các phép kiểm tra không cần thiết
  • Ví dụ mã: 
    sortByLeft(balls);
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (ball2.left > ball1.right) break;
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

Phân tích hiệu năng

  • Sắp xếp: O(n log n)
  • Vòng lặp bên trong: trung bình O(n + m) (m là tổng số lần chồng lấp trên trục x)
  • Độ phức tạp thời gian cuối cùng: O(n log n + m)

So sánh trực quan

  • So sánh giữa việc kiểm tra mọi cặp trên toàn cục và kiểm tra các cặp sau khi đã sắp xếp
  • Việc kiểm tra các cặp đã sắp xếp thực hiện ít phép kiểm tra hơn rất nhiều

Tóm tắt của GN⁺

  • Bài viết này nói về cách tối ưu thuật toán phát hiện va chạm trong phát triển game
  • Bắt đầu từ thuật toán O(n^2) đơn giản và cải thiện hiệu năng đáng kể thông qua sắp xếp
  • Đây là thông tin rất hữu ích cho nhà phát triển game hoặc kỹ sư phần mềm
  • Các dự án khác có chức năng tương tự gồm Box2D, Bullet Physics, v.v.

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-08-15
Ý kiến trên Hacker News

  • Tác giả đề xuất dùng các thuật toán sắp xếp “nhanh” như mergesort hoặc quicksort để đạt hiệu năng tối ưu

    • Tuy nhiên trên thực tế, các thuật toán sắp xếp “kém hơn” như insertion sort có thể cho hiệu năng tốt hơn
    • Các đối tượng trong hệ thống phát hiện va chạm di chuyển theo các bước tương đối nhỏ giữa các frame, nên có thể duy trì danh sách gần như đã được sắp xếp từ frame trước
    • Khi sắp xếp những danh sách gần như đã được sắp xếp này, insertion sort gần với O(n), còn Quicksort gần với O(n^2)

  • Trước đây tôi từng làm công việc tương tự, nhưng thay vì sắp xếp thì giữ các danh sách chỉ mục cho từng hướng

    • Ví dụ có 4 danh sách như objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge
    • Khi một đối tượng di chuyển theo chiều ngang, nó cập nhật chỉ mục của mình trong các mảng leftEdge và rightEdge
    • Trong lúc di chuyển, tối đa chỉ cần hoán đổi 1–2 chỉ mục

  • Bài này được hệ thống hóa rất tốt

    • Tôi làm game từ cuối những năm 90, nhưng phần lớn công việc đều đã được engine trừu tượng hóa
    • Đây là kiến thức thiết yếu để hiểu các mô phỏng hệ thống phức tạp
    • Cảm ơn tác giả vì đã viết một bài rất dễ tiếp cận

  • Tôi luôn thích đọc tài liệu về continuous collision detection

  • Cách dùng minh họa rất tốt

    • Đôi khi những bài như thế này tạo cảm giác chỉ là cái cớ để gom các demo hào nhoáng, nhưng bài này không bị minh họa lấn át nội dung chính

  • Phần 2: https://leanrada.com/notes/sweep-and-prune-2/

  • Có người đặt câu hỏi về nhận định: “Thuật toán đơn giản này chạy trong thời gian O(n^2) theo cách nói của Big O”

    • Vòng lặp ngoài (i) đếm đến n - 1, còn vòng lặp trong (j) bắt đầu từ i + 1 nên số lần lặp giảm dần
    • Tôi không học chuyên ngành CS, nhưng tò mò không biết với n lớn thì nó có thực sự gần tương đương O(n^2) hay là ít hơn

  • Có người thắc mắc liệu cách này có giống việc dùng quadtree để giảm số va chạm tiềm năng hay không

  • Có người tự hỏi liệu đã từng có ai đề xuất phương pháp linear programming chưa

  • Trang web này khiến tôi xao nhãng theo hướng tích cực

    • Rất vui và truyền cảm hứng