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

• Trong vật lý game, bài toán phát hiện va chạm lặp đi lặp lại được minh họa bằng mô phỏng các quả bóng, qua đó giải thích luồng tối ưu hóa từ việc kiểm tra mọi cặp sang sweep-and-prune
• Cách đơn giản gọi intersects() cho mọi cặp ứng viên trong n đối tượng, tức khoảng (n*(n-1))/2 lần kiểm tra, nên nhanh chóng tăng thành O(n²)
• Kiểm tra giao nhau AABB gồm nhiều bất đẳng thức và &&; tận dụng đánh giá ngắn mạch và tính bắc cầu của bất đẳng thức có thể loại sớm các ứng viên không thể va chạm
• Sau khi sắp xếp đối tượng theo minimum x là biên trái, tại thời điểm ball2.left > ball1.right có thể break vòng lặp trong để loại luôn các ứng viên phía sau
• Với chi phí sắp xếp O(n log n) cộng thêm chi phí vòng lặp theo số lần chồng lấp trên trục x là m, trung bình đạt mức O(n log n + m) và giảm mạnh các lần gọi intersects() không cần thiết

---

Điểm khởi đầu của phát hiện va chạm trong game

• Phát hiện va chạm là tiền đề cho nhiều hành vi trong lập trình game video
  • Ngăn nhân vật đi xuyên qua nhau
  • Khi Goomba va vào vật thể khác thì đổi hướng
  • Trong agar.io, tế bào lớn ăn tế bào nhỏ khi tiếp xúc
  • Xử lý vật lý game nói chung
• Ví dụ sử dụng mô phỏng quả bóng vật rắn để so sánh nhiều cách tiếp cận phát hiện va chạm
• Phạm vi ở đây đi từ cách đơn giản nhất đến sweep-and-prune, không bao gồm phân hoạch không gian hay tinh chỉnh cây không gian

Cách tiếp cận đơn giản: kiểm tra mọi cặp

• Cách trực tiếp nhất là xem mọi cặp đối tượng đều là ứng viên
  • Vòng lặp ngoài duyệt qua từng quả bóng
  • Vòng lặp trong bắt đầu từ i + 1 để tránh cặp trùng lặp như A-B và B-A
  • Với mỗi cặp ứng viên, gọi intersects(ball1, ball2) và nếu đúng thì chạy bounce(ball1, ball2)
• Việc kiểm tra này lặp lại ở mỗi bước thời gian, nên bóng sẽ được xử lý nảy lại tại thời điểm va chạm
• Khi số đối tượng ít thì hoàn toàn đủ dùng, nhưng khi số lượng tăng thì lượng kiểm tra nhanh chóng trở thành nút thắt hiệu năng

Giới hạn do O(n²) tạo ra

• Thuật toán đơn giản chạy với độ phức tạp O(n²) theo Big O
• Với n quả bóng, số cặp cần kiểm tra xấp xỉ (n*(n-1))/2, tức 0.5n² - 0.5n
  • n = 5 thì có 10 cặp
  • n = 10 thì có 45 cặp
  • n = 15 thì có 105 cặp
  • n = 20 thì có 190 cặp
• Trong trường hợp xấu nhất khi mọi đối tượng chồng lên nhau cùng lúc, hầu như không thuật toán phát hiện va chạm nào tránh được xử lý va chạm ở mức O(n²)
• Trong thực tế, so sánh theo trường hợp trung bình và tốt nhất thường hữu ích hơn trường hợp xấu nhất
• Cách đơn giản luôn vận hành ở mức Θ(n²) bất kể số va chạm thực tế, nên còn nhiều dư địa để cải thiện

Công việc lặp lại bên trong intersects()

• Điểm bắt đầu của tối ưu hóa là hàm intersects() được gọi với mọi cặp ứng viên
• Một phép kiểm tra giao nhau AABB điển hình gồm nhiều kiểm tra bất đẳng thức so sánh biên theo từng hướng

function intersects(object1, object2) {
  // compare objects' bounds to see if they overlap
  return object1.left < object2.right
      && object1.right > object2.left
      && object1.top < object2.bottom
      && object1.bottom > object2.top;
}

• Phép kiểm tra này tách thành bốn điều kiện
  • object1.left < object2.right
  • object1.right > object2.left
  • object1.top < object2.bottom
  • object1.bottom > object2.top
• Nhờ đánh giá ngắn mạch của &&, chỉ cần một điều kiện sai là toàn bộ phép kiểm tra giao nhau lập tức trả về sai
• Nếu khái quát trường hợp “ít nhất một điều kiện sai” qua nhiều phép kiểm tra, ta có thể giảm cả số lần gọi intersects()
• Đây là ý tưởng cùng hướng với định lý trục phân tách: nếu hình chiếu trên một trục không chồng lên nhau thì hai đối tượng không va chạm

Loại bỏ ứng viên bằng tính bắc cầu của bất đẳng thức

• Chỉ cần nhìn vào riêng điều kiện object1.right > object2.left cũng đã có cơ hội tối ưu hóa
• Khi ba đối tượng A, B, C nằm theo thứ tự ngang A-B-C, các phép kiểm tra sau đều có thể là sai

A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false

• Nếu A > B là sai và B > C là sai, thì theo tính bắc cầu của bất đẳng thức, ta biết A > C cũng sai
• Vì vậy, không cần gọi intersects(A, C) vẫn có thể kết luận hai đối tượng không va chạm
• Việc bỏ qua này chỉ áp dụng khi các đối tượng có một thứ tự nhất định, nhưng nhãn của đối tượng là tùy ý, nên có thể chọn đối tượng bên trái là A, ở giữa là B và bên phải là C
• Công việc đặt các đối tượng vào trật tự logic như vậy chính là sắp xếp

Sắp xếp theo giá trị tối thiểu trên trục x

• Danh sách đã sắp xếp cho phép áp dụng tính bắc cầu của bất đẳng thức lên nhiều ứng viên cùng lúc
• Các thuật toán sắp xếp nhanh phổ biến có độ phức tạp O(n log n), thấp hơn O(n²)
• Vì đối tượng không phải là điểm mà chiếm một khoảng trên trục x, nên để sắp xếp theo vị trí x ta dùng minimum x là biên trái
• Từ đoạn mã O(n²) đơn giản, chỉ cần hai thay đổi
  • Trước vòng lặp, gọi sortByLeft(balls) để sắp xếp bóng theo tọa độ x của biên trái
  • Trong vòng lặp trong, nếu ball2.left > ball1.right thì break

// sort by min x
sortByLeft(balls);

// for each ball
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  // check each of the other balls
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];

    // stop when too far away
    if (ball2.left > ball1.right) break;

    // check for collision
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

• Hàm sắp xếp sẽ sắp xếp mảng dựa trên chênh lệch của biên trái

function sortByLeft(balls) {
  balls.sort((a,b) => a.left - b.left);
}

Vì sao break là an toàn

• Khi danh sách đã được sắp xếp, với mọi số nguyên dương bất kỳ c, quan hệ sau luôn đúng

balls[j + c].left >= balls[j].left

• Nếu ứng viên hiện tại thỏa điều kiện sau, thì cặp hiện tại không chồng lên nhau trên trục x

balls[j].left > ball1.right

• Kết hợp hai bất đẳng thức đó, ta được

balls[j + c].left >= balls[j].left > ball1.right

• Theo tính bắc cầu, balls[j + c].left > ball1.right cũng đúng, nên mọi ứng viên phía sau cũng không chồng lên ball1 trên trục x
• Ngay khi ball2 hiện tại không còn chồng lên ball1, có thể dừng toàn bộ phần còn lại của vòng lặp trong mà không cần kiểm tra nữa
• Tối ưu hóa này giới hạn số lần gọi intersects() vào các cặp thật sự chồng lên nhau trên trục x

Độ phức tạp thời gian được cải thiện

• Chi phí sắp xếp thêm vào hạng O(n log n) nếu dùng các thuật toán sắp xếp nhanh như mergesort hay quicksort
• Vòng lặp lồng nhau có dừng sớm này trung bình có thể xem là O(n + m)
  • m là tổng số lần chồng lấp trên trục x
  • Ở trường hợp tốt nhất, nếu không có chồng lấp thì gần như không có xử lý dư thừa, nên gần với O(n)
  • Ở trường hợp xấu nhất, nó vẫn có thể suy biến thành O(n²)
• Trường hợp trung bình giả định các đối tượng được phân bố khá đều và mỗi đối tượng chỉ có vài va chạm
• Gộp cả sắp xếp và vòng lặp, độ phức tạp tổng thể là O(n log n + m)
• Cách này tốt hơn phương pháp đơn giản vì hai lý do
  • n log n nhỏ hơn n²
  • Nó phụ thuộc một phần vào số chồng lấp m, nên không xử lý nhiều hơn mức cần thiết

Gánh nặng triển khai và bước tiếp theo

• Cách làm dựa trên sắp xếp này là điểm cân bằng tốt: thay đổi mã ít nhưng cải thiện đáng kể hiệu năng thời gian chạy
• Trong demo so sánh, việc kiểm tra cặp dựa trên sắp xếp giảm rõ rệt số phép thử intersects() mỗi khung hình so với kiểm tra toàn bộ cặp toàn cục
• Chi phí sắp xếp không được hiển thị trong trực quan hóa so sánh, nhưng giả định rằng phép kiểm tra giao nhau đủ đắt đỏ để đáng tối ưu
• Các cách nâng cao hơn và mã hoàn chỉnh được tiếp nối ở Part 2

[GN⁺]

Các ý kiến trên Hacker News

• Điểm thú vị ở cách này là tác giả đề xuất dùng các thuật toán sắp xếp “nhanh” như merge sort/quicksort để đạt hiệu năng cao nhất
  Nhưng trong thực tế, một thuật toán sắp xếp “tệ” hơn là insertion sort có thể nhanh hơn
  Các đối tượng trong hệ thống phát hiện va chạm thường chỉ di chuyển một chút 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
  Với kiểu danh sách này, insertion sort tiến gần O(n), trong khi quicksort có thể tiến gần O(n^2)

  • Tác giả có nói gần như cùng nội dung trong Phần 2
    Đại ý là: “Bước sắp xếp là điểm nghẽn theo phân tích, nhưng phần lớn thời gian thì việc sắp xếp chẳng làm gì cả. Danh sách hầu như luôn đã được sắp xếp từ frame trước. Ngay cả khi trật tự bị phá vỡ, thường chỉ cần vài lần hoán đổi là sắp xếp lại được. Đây là một ví dụ về cách insertion sort hoạt động”
  • Thay vì sắp xếp ở mỗi bước, cũng có thể làm cấu trúc lập chỉ mục lỏng hơn một chút để bắt các ứng viên va chạm khi đối tượng di chuyển ít hơn epsilon
    Ví dụ, có thể tăng bán kính của hình cầu thêm epsilon
    Trong khi hình cầu chưa di chuyển một khoảng epsilon, không cần tính lại chỉ mục
    Khi cần tính lại, để tránh đỉnh trễ, có thể sắp xếp 10% mỗi frame để tạo một chỉ mục bị trễ
    Sau 10 frame, bạn sẽ có một chỉ mục hợp lệ miễn là nó nằm trong epsilon so với vị trí của 10 frame trước
  • Quicksort trở thành O(n^2) trên danh sách gần như đã sắp xếp chỉ khi chọn pivot thật sự tệ
    Nếu chọn pivot ngẫu nhiên thì sẽ là O(n log n), và nếu danh sách đã gần như được sắp xếp thì cũng có thể chọn phần tử ở giữa danh sách làm pivot
    Tuy vậy, ngay cả với pivot tối ưu, quicksort trong trường hợp tốt nhất vẫn là O(n log n)
    Có những biến thể merge sort đơn giản chạy O(n log k), trong đó k là số run tăng dần/giảm dần trong dữ liệu
    sort mặc định của thư viện chuẩn Haskell dùng thuật toán như vậy, và Python có lẽ cũng thế

• Bố cục bài viết rất tốt
  Tôi đã làm phát triển game dưới hình thức này hay hình thức khác từ cuối thập niên 90, và giờ đây phần lớn những thứ này đã được trừu tượng hóa trong engine, nhưng các nội dung như thế này là thiết yếu để hiểu mô phỏng hệ thống phức tạp hoạt động ra sao
  Cảm ơn tác giả vì đã viết một bài dễ tiếp cận

• Về phát hiện va chạm liên tục, tôi luôn đánh giá cao tài liệu này: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
  Bản thân thư viện cũng rất xuất sắc về hiệu năng
  Tuy nhiên, vì được tối ưu hóa nhiều nên việc tích hợp hơi khó

• Tôi thắc mắc câu “thuật toán ngây thơ này chạy trong thời gian O(n2) theo Big-O” có đúng không
  Vòng lặp ngoài i chạy n - 1 lần, còn vòng lặp trong j bắt đầu từ i + 1, nên chẳng phải nó ngày càng chạy ít hơn n - 1 lần sao
  Tôi không học chuyên ngành này, nên muốn biết khi n lớn thì có thể xem nó xấp xỉ O(n2) hay không, hay thật ra nhỏ hơn như vẻ ngoài

  • Không phải chính xác n^2
    Với phần tử thứ i, ta thực hiện (n - i - 1) phép so sánh, và nếu đánh chỉ mục từ 0 thì tổng số phép so sánh là (n - 1) * n / 2
    Xem https://en.wikipedia.org/wiki/Triangular_number
    Cuối cùng thì trong phân tích Big-O không có khác biệt
    Big-O mô tả hành vi khi n tiến tới vô hạn, và lúc đó hạng tử bậc hai chi phối
  • Việc “tối ưu hóa” cho vòng lặp trong bắt đầu từ j = i + 1 là để tránh kiểm tra mỗi cặp đối tượng hai lần
    Nó cũng giúp không kiểm tra một đối tượng với chính nó
    Vì thuật toán kiểm tra mỗi cặp đúng một lần, nên nó là O(n^2)
  • Big-O chỉ là một phân loại độ phức tạp mô tả số phép toán trừu tượng scale như thế nào theo kích thước đầu vào, tức độ dài danh sách đầu vào
    Nói chung, nếu có thể biểu diễn số phép toán dưới dạng một hàm giải tích của kích thước đầu vào, Big-O chỉ giữ lại hạng tử lớn nhất và bỏ mọi hệ số
    Nó không nhất thiết mô tả hiệu năng thực tế của thuật toán
    20n2^+5n và 2n^2 + 9001n đều là O(n^2)
  • Vì là tổng từ 1 đến n nên thành n(n+1)/2
    Trong ký hiệu Big-O, mọi hệ số và các hạng tử tăng chậm hơn đều bị bỏ qua, nên rút gọn thành độ phức tạp bậc hai
  • Có thể sẽ dễ hiểu hơn nếu xem Big-O giống như tính giới hạn trong giải tích

• Cách dùng minh họa rất hay và có vẻ đúng chỗ
  Đôi khi các bài có minh họa tương tác tạo cảm giác như chỉ là cái cớ để nhét thật nhiều demo hào nhoáng, giống các bài nói TED có phần trang trí nhiều hơn nội dung
  Nhưng trong bài này, minh họa không lấn át nội dung

• Phần 2: https://leanrada.com/notes/sweep-and-prune-2/
  Các bài viết hay khác cũng đáng xem: https://leanrada.com/

• Lâu rồi tôi từng làm thứ tương tự, nhưng thay vì sắp xếp, tôi duy trì danh sách chỉ mục theo từng hướng và để các đối tượng tự được sắp xếp
  Ví dụ có 4 danh sách như objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge
  Khi một đối tượng di chuyển theo phương ngang, nó cập nhật chỉ mục của mình trong mảng leftEdge và rightEdge
  Vì ngay cả khi di chuyển, thường chỉ cần hoán đổi 1–2 chỉ mục là đủ

  • Cách đó có vẻ hữu ích với các cảnh phần lớn là tĩnh
    Càng có nhiều yếu tố động, cách dựng lại đồ thị có vẻ càng tốt hơn

• Đây là cách tôi mới thấy lần đầu, chẳng phải nó tương tự việc dùng thứ như quadtree để giảm số collider tiềm năng sao?

  • Đúng vậy
    Tuy nhiên, trong render offline bạn sẽ thường thấy những thứ như k-d tree hơn so với render thời gian thực

• Tôi tò mò về đoạn “sẽ không bàn đến các cách tiếp cận khác như phân hoạch không gian hay chia nhỏ cây không gian”
  Có ai biết thuật toán trong bài nói chung có nhanh hơn phân hoạch không gian/chia nhỏ cây không gian không?
  Từ rất lâu trước đây tôi từng dùng cách tiếp cận kiểu cây không gian, và nhìn một cách ngây thơ thì nó có vẻ khá tốt, nhưng hồi đó là thập niên 80 trước thời Internet nên tôi chưa từng tìm hiểu hay so sánh các thuật toán người khác dùng

  • Độ phức tạp của việc duy trì phân hoạch không gian hay chia nhỏ cây, đặc biệt khi có cực nhiều đối tượng chuyển động, có thể là gánh nặng lớn
    Quản lý một danh sách entity duy nhất, hoặc một lưới ô 256x256 trong đó mỗi ô chứa danh sách entity, dễ viết, debug và tối ưu hơn nhiều so với một cấu trúc phân hoạch phức tạp phải duy trì mọi bất biến của cây mỗi khi đối tượng di chuyển
    Thời DOOM hay Quake, hiệu năng của các hệ thống nền tảng kiểu này quan trọng hơn bây giờ rất nhiều, nên việc các tác giả engine xây các hệ thống phân hoạch rất phức tạp có lẽ hợp lý hơn
    CPU ngày nay rất mạnh trong việc quét các mảng đã sắp xếp, còn do pipelining, việc lần theo linked list hay cây tương đối kém lợi thế hơn trước
    Thời gian CPU giờ được dành nhiều hơn cho những thứ như AI và render, thay vì quản lý danh sách entity