Lesson 08 — Broad-phase & Quadtree

Vì sao so mọi cặp ($n^2$) là không chịu nổi, và làm sao grid / quadtree cắt số cặp xuống. Ba module: (1) quadtree động — vật bay, ô tự chia/gộp theo mật độ; (2) spatial grid — tô ô có vật + cặp cùng ô; (3) đồ thị số phép so sánh theo N.

1. Quadtree động — vật bay, ô tự chia theo mật độ

N vật bay tự do (nảy tường). Mỗi frame quadtree dựng lại: node chứa quá capacity vật thì chia làm 4. Đường kẻ mảnh = biên ô quadtree. Bên dưới đếm số cặp phải test với broad-phase (chỉ cặp cùng lá + lá kề) so với không (mọi cặp $n^2$).

2. Spatial grid — tô ô có vật, đếm cặp cùng ô + ô kề

Lưới ô đều. Ô tô đậm theo số vật trong ô (càng đông càng đậm). Kéo cell size để thấy: ô to → ít ô đông → nhiều cặp; ô nhỏ → nhiều ô thưa → ít cặp (tới khi quá nhỏ thì vật trải nhiều ô). Cặp ứng viên = mọi cặp trong cùng ô và giữa ô kề.

3. Đồ thị: số phép so sánh theo N — $n^2$ vs broad-phase

Trục ngang = số vật N; trục dọc = số cặp phải test. Đường đỏ = so mọi cặp $C(N,2)\approx N^2/2$ (parabol). Đường xanh = broad-phase $\approx$ tuyến tính ($\sim c\cdot N$). Bảng dưới đối chiếu vài mốc N.