OYUN GEOMETRİSİ VE FİZİĞİ · G2
Uzaysal Bölümleme
Izgara, uzaysal hash, dörtlü ağaç, BVH — “yakınımda kim var?” sorusunu herkese sormadan cevaplamak
PRESS ▶ TO START
Bu derste oyunun haritası 🗺️
- Sorun — herkesi herkesle karşılaştırmak: N² neden öldürür? Geniş ve dar aşama
- Düzgün ızgara ve uzaysal hash — hücre formülü, sorgu, hücre boyu hesabı; DOOM’un “blockmap”i, Minecraft’ın parçaları
- Dörtlü ağaç — dolunca dörde böl; budama; Kerbal’ın gezegenleri, harita karoları
- BVH — kutuların kutusu; ışın–kutu testi; Box2D’nin “şişman” kutuları, ışın izleme
- Hangisini seçmeli? — karşılaştırma tablosu; kd-ağacı ve sweep-and-prune ile ilişki
- Her adımda — elle izleme → canlı demo → kod (JavaScript / Python / C#) → oyunlardaki karşılığı
🎮 Bu dersin sonunda…
2.000 mermiyi 500 düşmanla saniyede 60 kez çarpıştırmanın neden mümkün olduğunu hesapla gösterebilecek; bir sahne için ızgara, dörtlü ağaç ve BVH arasında gerekçeli seçim yapabilecek; uzaysal hash ızgarasını 30 satırda yazabileceksiniz.
🤔 ISINMA: 1.000 TOP, SANİYEDE 60 KARE
1.000 top birbirine çarpıyor mu? En basit kod: her topu her topla karşılaştır.
- 1.000 × 999 / 2 ≈ 500.000 çift, kare başına. Saniyede 30 milyon uzaklık testi.
- 10.000 top olursa? 100 kat fazla: saniyede 3 milyar. Oyun durur.
- Ama bir top, ekranın öbür ucundaki topa çarpamaz. Testlerin %99’undan fazlası baştan belli.
- Bu dersin tek fikri: uzayı böl; yalnızca aynı bölgedekileri karşılaştır.
- Aynı soru her yerde: yakınımdaki düşmanlar (Y11), sürü komşuları (Y7), patlamadan etkilenenler, mermi neye çarptı, kamera neyi görüyor.
🎯 Bu konu için bilmeniz gerekenler
Yeşil = gerekli · kesikli = faydalı ama şart değil. Tıklayınca ilgili sunuma gider.
BST’nin Geometrik Uygulamaları (kd-ağacı, sweep and prune)Algoritma Analizi (N² ve N log N)Y7 · Steering (boids komşu arama)
Neden?Hash Tabloları sunumunda “uzaysal hash ızgarası”, Ağaçlar sunumunda dörtlü ağaç, Geometrik BST sunumunda kd-ağacı ve sweep-and-prune birer örnek olarak geçmişti. Bu sunum hepsini aynı probleme karşı yan yana koyuyor, hesabını yapıyor ve eksik olanı (BVH) ekliyor.
🧰 Kodlamadan korkuyorsanızUzaysal hash ızgarası bir sözlük (Map) ve iki bölme işleminden ibaret. Projeniz için çoğu zaman yalnızca o yeter.
Mini sözlük
| spatial partitioning | uzaysal bölümleme | Uzayı bölgelere ayırıp nesneleri bulundukları bölgeye göre saklamak |
| broad phase · narrow phase | geniş aşama · dar aşama | “Kimler çarpışıyor olabilir?” (ucuz eleme) · “Gerçekten çarpışıyorlar mı?” (kesin test, G3) |
| uniform grid · spatial hash | düzgün ızgara · uzaysal hash | Eşit kareler · hücreleri dizide değil sözlükte tutan, sınırsız ızgara |
| quadtree · octree | dörtlü ağaç · sekizli ağaç | Dolunca dörde bölünen kare · 3B’de sekize bölünen küp |
| BVH (bounding volume hierarchy) | sınırlayıcı hacim hiyerarşisi | Nesnelerin kutularını daha büyük kutularda toplayan ağaç |
| AABB · fat AABB | eksen hizalı kutu · şişman kutu | Kenarları eksenlere paralel sınırlayıcı kutu · hareket payı için büyütülmüş kutu |
| pruning | budama | Bir dalın sonuca katkısı olamayacağını görüp hiç açmamak |
| candidate | aday | Bölümlemenin döndürdüğü “belki yakın” nesne; kesin test hâlâ gerekir |
LEVEL 0
Sorun: N²
herkes herkesle
Geniş aşama ve dar aşama
- Dar aşama: “bu iki şekil gerçekten çakışıyor mu?” Kesin ama pahalı olabilir (çokgenler, G3).
- Geniş aşama: “hangi çiftler çakışıyor olabilir?” Ucuz ve kaba; yanlış alarm verebilir, gözden kaçıramaz.
- Bölümleme yapıları geniş aşamadır: aday listesi üretir. Kesin test her zaman en sonda, yalnızca adaylara.
- Her fizik motoru bu iki katmanla çalışır (Box2D, PhysX, Unity, Unreal).
Kaba kuvvetin kodu
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++) // j = i + 1: her çift BİR kez
if (carpisiyor(nesne[i], nesne[j])) …| nesne | kaba kuvvet (çift) | ızgarayla (yaklaşık) |
|---|---|---|
| 100 | 4.950 | ~300 |
| 1.000 | 499.500 | ~3.000 |
| 10.000 | 49.995.000 | ~30.000 |
| 100.000 | ≈ 5 milyar | ~300.000 |
Nesneler aşağı yukarı eşit dağılmış ve hücre başına birkaç nesne düşüyorsa iş N ile doğrusal büyür (hesabını birazdan yapacağız). Hepsi tek hücreye yığılırsa yine N²: yapı sihir değil, dağılıma bağlı.
LEVEL 1
Düzgün ızgara ve uzaysal hash
en basit, çoğu zaman en iyi
Çizimle: her nokta hangi hücrede? (hücre boyu 50)
Dünyayı 50’lik karelere bölüyoruz. Her nokta, koordinatlarını 50’ye bölüp aşağı yuvarlayınca çıkan hücrededir: (130, 75) → (2, 1). Kırmızı çizgi x = 0: solundaki (−10, 20) noktası −1 numaralı sütunda. (49,9, 50) tam sınırda: y = 50 bir alttaki sıraya (1) aittir. Sayılar sonraki slayttaki tablonun aynısı.
Fikir: hücre numarası = aşağı yuvarla(konum / hücre boyu)
- Dünyayı kenarı s olan eşit karelere böl. Bir nesnenin hücresi:
cx = floor(x / s),cy = floor(y / s). - Her hücre, içindeki nesnelerin bir listesini tutar.
- Nesneyi “ekle” = hücresini hesapla, listesine koy. Sabit zaman.
Elle hesap (s = 50):
| nokta | x / 50, y / 50 | hücre (floor) |
|---|---|---|
| (130, 75) | 2,6 · 1,5 | (2, 1) |
| (26, 24) | 0,52 · 0,48 | (0, 0) |
| (49,9, 50) | 0,998 · 1,0 | (0, 1) |
| (−10, 20) | −0,2 · 0,4 | (−1, 0) |
| (199, 399) | 3,98 · 7,98 | (3, 7) |
⚠️ Neden
floor? Üç yaygın hata| yazım | (26, 24) için | (−10, 20) için |
|---|---|---|
Math.floor(x / s) | (0, 0) ✔ | (−1, 0) ✔ |
Math.round(x / s) | (1, 0) ✘ | (0, 0) ✘ |
(x / s) | 0 · int(x / s) | (0, 0) ✔ | (0, 0) ✘ |
x // s (Python) | (0, 0) ✔ | (−1, 0) ✔ |
round hücre sınırlarını yarım hücre kaydırır. | 0 ve int() sıfıra doğru keser: −0,2 → 0; böylece −1 ve 0 hücreleri birleşir ve orijin çevresindeki hücre iki kat genişler. Dünyanız eksi koordinat içermiyorsa fark etmezsiniz; içerdiği gün hata çıkar.
İki saklama biçimiDüzgün ızgara: hücreler dizide; dünya sınırlı; en hızlısı. Uzaysal hash: hücreler sözlükte (
"cx,cy" → liste); dünya sınırsız, boş hücre yer tutmaz.Çizimle: sorgu dairesi hangi hücrelere değiyor?
Kırmızı daire: (120, 80) çevresinde 30 yarıçaplı sorgu. Onu saran kesikli kare 90 … 150 ve 50 … 110; bu kareye değen altı turuncu hücre dışındaki hiçbir hücreye bakmaya gerek yok. Turuncu hücrelerdeki nesneler adaydır; gerçekten dairenin içinde olup olmadıklarına ayrıca bakılır.
Sorgu: “(x, y) çevresinde r yarıçapında kim var?”
- Sorgu dairesini saran kareyi düşün: x − r … x + r ve y − r … y + r.
- Bu karenin değdiği hücreler:
floor((x − r)/s)…floor((x + r)/s)(y için de aynısı). - O hücrelerin listelerindeki herkes adaydır. Aday ≠ sonuç: köşedeki hücrenin uzak ucundaki nesne dairenin dışında olabilir. Kesin uzaklık testi çağıranın işi.
Elle hesap: (120, 80), r = 30, s = 50
x: 90 … 150 → hücre 1 … 3 · y: 50 … 110 → hücre 1 … 2
Bakılacak hücre: 3 × 2 = 6 (bütün dünyadaki yüzlerce hücre yerine).
🎮 Çarpışma için
Her nesne, kendi hücresi + 8 komşu hücredeki nesnelerle test edilir (3 × 3). Bunun yetmesi için: hücre boyu ≥ en büyük nesnenin çapı.
Aynı çifti iki kez test etmemek için: yalnızca j > i olanlara bak (ya da hücre çiftlerinin yarısını gez).
Hareketli nesnelerNesne taşınınca hücresi değişebilir. İki yol: (1) eski hücreden sil, yenisine ekle; (2) her kare hepsini sil, baştan kur. İkincisi N ekleme demek: şaşırtıcı derecede ucuz, hatasız ve çoğu oyunun yaptığı şey.
🧭 DEMOYU OKUMA KILAVUZU (bir sonraki slayt)
- Toplar hareket ediyor; kırmızı olanlar o an bir başkasıyla çakışanlar.
- Mavi kareler ızgara hücreleri; ne kadar koyuysa içinde o kadar çok top var.
- Sol üst: bu karede yapılan çift testi sayısı; altında “kaba kuvvet olsaydı” sayısı ve kaç kat fark ettiği.
- Fare: sarı çerçeve, farenin bulunduğu hücrenin 3×3 komşuluğu; sarı toplar “yakınımda kim var?” sorgusunun adayları.
- Alt satır: dolu hücre sayısı ve en kalabalık hücredeki top sayısı (hücre boyunu ayarlarken bakacağınız sayı).
Canlı: kaba kuvvet mi, ızgara mı? 🧮
- “kaba kuvvet”i seçip top sayısını 300 → 600 → 1200 yapın: test sayısı her seferinde dört katına çıkıyor (44.850 → 179.700 → 719.400).
- “düzgün ızgara”ya geçin: aynı 1200 top için test sayısı kaç? “kat fazla” yazısını okuyun.
- Hücre boyunu 160 yapın: hücreler kalabalıklaşır, test sayısı yükselir. 10 yapın: hücre topun çapı kadar; 3×3 komşuluk sınırda.
- Fareyi kalabalık bir bölgeye götürün: 1200 toptan yalnızca birkaç düzinesi “aday”.
- Bir sonraki slayttaki formülle 300 top ve hücre boyu 40 için test sayısını tahmin edin; sonra demoda okuyun.
- Toplar hareket ediyor; kırmızı olanlar o an bir başkasıyla çakışanlar.
- Mavi kareler ızgara hücreleri; ne kadar koyuysa içinde o kadar çok top var.
- Sol üst: bu karede yapılan çift testi sayısı; altında “kaba kuvvet olsaydı” sayısı ve kaç kat fark ettiği.
- Fare: sarı çerçeve, farenin bulunduğu hücrenin 3×3 komşuluğu; sarı toplar “yakınımda kim var?” sorgusunun adayları.
- Alt satır: dolu hücre sayısı ve en kalabalık hücredeki top sayısı (hücre boyunu ayarlarken bakacağınız sayı).
🔎 DEMODA DENEYİN
- “kaba kuvvet”i seçip top sayısını 300 → 600 → 1200 yapın: test sayısı her seferinde dört katına çıkıyor (44.850 → 179.700 → 719.400).
- “düzgün ızgara”ya geçin: aynı 1200 top için test sayısı kaç? “kat fazla” yazısını okuyun.
- Hücre boyunu 160 yapın: hücreler kalabalıklaşır, test sayısı yükselir. 10 yapın: hücre topun çapı kadar; 3×3 komşuluk sınırda.
- Fareyi kalabalık bir bölgeye götürün: 1200 toptan yalnızca birkaç düzinesi “aday”.
- Bir sonraki slayttaki formülle 300 top ve hücre boyu 40 için test sayısını tahmin edin; sonra demoda okuyun.
🔗 Başka gözle: etkileşimli anlatımlar ve yazılar
Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.
📘 Spatial Partition
Game Programming Patterns (Robert Nystrom)
Izgara, quadtree ve BSP ile “yakınımdaki nesneler” sorusunu hızlandırmak.
🔗 Collision Detection
Jeffrey Thompson
Nokta, daire, dikdörtgen, çizgi ve çokgen çarpışmalarının p5.js ile adım adım anlatımı.
🔴 Hexagonal Grids
Red Blob Games (Amit Patel)
Altıgen ızgarada koordinat, komşu, mesafe ve yol bulma; oyun geliştiricilerin en çok başvurduğu sayfalardan biri.
Hesap: hücre boyu ne olmalı, kaç test eder?
N nesne, alanı A olan bir dünyaya eşit dağılmış; hücre kenarı s.
Hücre başına ortalama nesne: $$k = \frac{N \cdot s^2}{A}$$
Her nesne 9 hücreye bakar ve her çift bir kez sayılır: $$\text{test} \approx \frac{N \cdot 9k}{2}$$
Demodaki sayılarla
N = 300, alan 720 × 340 = 244.800, s = 40:
k = 300 · 1.600 / 244.800 ≈ 1,96
test ≈ 300 · 9 · 1,96 / 2 ≈ 2.650 (demo ≈ 2.400–2.700 gösterir)
Kaba kuvvet: 300 · 299 / 2 = 44.850. Yaklaşık 17 kat.
| hücre boyu s | k (hücre başına) | tahmini test | not |
|---|---|---|---|
| 10 | 0,12 | ~165 | çap = 10: komşuluk sınırda; büyük nesne taşar |
| 20 | 0,49 | ~660 | iyi |
| 40 | 1,96 | ~2.650 | güvenli seçim |
| 80 | 7,8 | ~10.600 | hücreler kalabalık |
| 160 | 31 | ~42.000 | neredeyse kaba kuvvet |
ÖnermeNesne yoğunluğu sınırlıysa (hücre başına ortalama k sabit kalıyorsa) ızgarayla çarpışma taraması N ile doğrusal büyür: kurma N, tarama ≈ 4,5·k·N. En kötü durumda (herkes tek hücrede) yine N².
Pratik kural: s ≈ en büyük nesnenin çapı (ya da en sık sorgu yarıçapı). Daha küçüğü 3×3 komşuluğu bozar; daha büyüğü testi artırır.
Kod: uzaysal hash ızgarası (1/2)
Kod: uzaysal hash ızgarası (2/2)
🎒 Kodu okuyalım
| ifade | ne demek | neden böyle |
|---|---|---|
new Map() · defaultdict(list) · Dictionary<…> | anahtar → değer sözlüğü (hash tablosu) | Yalnızca dolu hücreler yer tutar; dünya sınırsız olabilir (Hash Tabloları sunumu). |
floor(x / s) + ',' + floor(y / s) | "2,1" gibi bir metin anahtar | En basit çakışmasız anahtar. Hız gerekirse iki sayı tek tam sayıya paketlenir (cx * 73856093 ^ cy * 19349663). |
Python: (cx, cy) | demet anahtar | Python’da demetler sözlük anahtarı olabilir; metne çevirmek gerekmez. |
if (!has(k)) set(k, []) | liste yoksa oluştur | defaultdict bunu kendiliğinden yapar. |
for (cx = floor((x − r)/s); cx <= floor((x + r)/s); cx++) | sorgu karesinin değdiği sütunlar | <=: son hücre dahil. Elle hesaptaki 1 … 3. |
Python: yield from | listeyi üretmeden tek tek ver | Büyük sorgularda ara liste kurulmaz. |
C#: l.Clear() (yeni liste yerine) | listeyi boşalt ama bellekte tut | Her kare yeni liste = çöp toplayıcı takılması (Y18). |
🌱 Isınma kodu: hangi hücredeyim?
Bütün uzaysal hash bu satıra dayanır.
Math.round en yakın tam sayıya gider: x = 26, boy = 50 için 0,52 → 1 (yanlış; 26 hâlâ 0. hücrede). Gereken her zaman aşağı yuvarlamak: Math.floor. Eksi koordinatlara dikkat: −10 / 50 = −0,2 → hücre −1. Az önceki tablonun satırları testlerde.🧪 Canlı laboratuvar: ızgarayı sen kur
Başlangıç kodu boş bir nesne döndürür: sağda hiçbir hücre boyanmaz. Üç satır:
const k = Math.floor(x / size) + "," + Math.floor(y / size);, if (!grid[k]) grid[k] = [];, grid[k].push(i);. Doğruysa her hücre, içindeki nokta sayısıyla boyanır ve noktalar hareket ettikçe güncellenir.Oyunlarda: DOOM’un “blockmap”i (1993)
- DOOM’un her haritası 128 × 128 birimlik karelere bölünür: “blockmap”. Bu sunumdaki düzgün ızgaranın ta kendisi.
>>MAPBLOCKSHIFT: 128 = 2⁷ olduğu için bölme yerine 7 bit sağa kaydırma. Tam sayılarda sağa kaydırma her zaman aşağı yuvarlar: bedavafloor.- Her kare iki liste tutar: içinden geçen duvar çizgileri (harita derlenirken önceden hesaplanır) ve o an içinde duran şeyler (canavar, eşya; her hareket ettiklerinde güncellenen bağlı liste).
- Canavar yürürken, mermi giderken, roket patlarken motor yalnızca ilgili birkaç karenin listesine bakar. 1993’ün 33 MHz’lik işlemcisinde onlarca canavarı mümkün kılan şeylerden biri.
- Bir duvar birkaç kareden geçiyorsa aynı duvar iki kez test edilmesin diye her çizgide bir
validcountdamgası tutulur: “bu turda bana bakıldı”. G1’deki mermi de bu ızgarayı kullanır: yol hangi karelerden geçiyorsa yalnızca oralara bakılır.
Oyunlarda: Minecraft’ın parçaları ve “survivor” türü
🧱 Minecraft: dünya bir ızgaradır
- Dünya 16 × 16 blokluk sütunlara, parçalara (chunk) bölünür. Parça = ızgara hücresi; konumdan parçaya:
x >> 4(yine bit kaydırma). - Yalnızca oyuncunun çevresindeki parçalar yüklenir, çizilir ve simüle edilir; uzaktakiler diske yazılır. Bu bir uzaysal hash: sınırsız dünya, yalnızca dolu hücreler bellekte.
- Yaratıklar bulundukları parçaya kayıtlıdır: “yakınımdaki zombiler” sorgusu birkaç parçaya bakar.
- Oyuncular bu ızgarayı keşfetti: çiftlikler “parça sınırına” göre kurulur, uzaktaki makineleri çalışır tutmak için “parça yükleyiciler” yapılır; oyun sonradan sınırları gösteren hata ayıklama görünümü (F3 + G) ekledi.
🧛 Ekranda binlerce düşman
- Vampire Survivors tarzı oyunlarda aynı anda binlerce düşman ve mermi olur. Her mermiyi her düşmanla sınamak imkânsızdır.
- Tipik çözüm tam olarak bu bölümdeki: düşmanları her kare ızgaraya koy, her mermi yalnızca kendi hücresine baksın.
- SimonDev’in “Spatial Hash Grids & Tales from Game Development” videosu aynı yapıyı gerçek bir projede adım adım hızlandırır: sözlükten düz diziye, listelerden önceden ayrılmış belleğe (Kaynaklar).
Ders: büyük, açık dünyalı oyunların çoğu en basit yapıyla, ızgarayla başlar; tür bile bir veri yapısının mümkün kıldığı bir tasarımdır.
Kod: sınırlı dünya için dizi tabanlı ızgara
DOOM’un yaptığı: hücreler tek boyutlu bir dizide, indis = satır · genişlik + sütun. Sözlük araması yok, metin anahtar yok: en hızlısı. Bedeli: dünya sınırlı olmalı ve boş hücreler de yer tutar. Çoğu seviye tabanlı oyun için doğru seçim.
🐍 Laboratuvar: yakınımdaki adaylar
cx için math.floor((x - r) / size) ile math.floor((x + r) / size) arasını (ikisi de dahil) dolaşın; cy için aynısı. Olmayan hücre için grid.get(key, []). Bunlar aday: bazıları dairenin dışında olabilir; kesin uzaklık testi çağıranın işi.Quiz 1 · ızgara
Bir uzay oyununda 2.000 küçük mermi ve tek bir dev boss gemisi (ekranın üçte biri kadar) var. Hücre boyunu mermi çapına göre seçtiniz. Sorun ne olur?
Düzgün ızgara, benzer boyutlu nesnelerde parlar. Boyutlar çok farklıysa seçenekler: büyük nesneyi ayrı bir listede tutup herkesle doğrudan test etmek, iki ayrı ızgara (kaba ve ince) kullanmak ya da boyuta uyum sağlayan bir ağaca (dörtlü ağaç, BVH) geçmek.
🎬 Ara: uzaysal hash ızgarası, bir oyun geliştiricinin gözünden
Spatial Hash Grids & Tales from Game Development
SimonDev · 19 dk 07 sn · YouTube’da aç
Az önceki ızgaranın gerçek bir oyun projesindeki hikâyesi: binlerce birimde “yakınımda kim var?” sorusu, hücre boyunun seçimi ve ölçülen hızlanma. Eski bir AAA geliştiricisinin pratik notları.
🤔 İzlerkenVideoda hücre boyu nasıl seçiliyor? Nesneler hareket edince ızgara nasıl güncelleniyor? Kaba kuvvete göre kaç kat hızlanma ölçülmüş; bizim demodaki sayılarla karşılaştırın.
LEVEL 2
Dörtlü ağaç
veriye uyum sağlayan bölme
Problem: nesneler eşit dağılmıyorsa
- 300 × 300 km’lik bir uzay haritası; 5.000 geminin neredeyse hepsi dört yıldız sisteminin çevresinde, her biri 2 km çapında bir bölgede.
- Hücre boyu 1 km: 90.000 hücre; 89.980’i boş. Bellek israfı; büyük sorgular çok hücre gezer.
- Hücre boyu 50 km: 36 hücre; dördünde 1.250’şer gemi. Her gemi 1.250 gemiyle test: yine N².
- Izgaranın çözünürlüğü her yerde aynı. Kalabalık yerde ince, boş yerde kaba olmasını isteriz.
Fikir: dolunca dörde böl
- Bütün dünya tek bir kare. Her kare en çok k nesne tutar (kapasite).
- Kapasite aşılınca kare dört eşit çocuğa bölünür; nesneler çocuklara dağıtılır.
- Sonuç: kalabalık yerde küçük, boş yerde büyük kareler.
- 3B’de aynı fikir: sekizli ağaç (octree).
🎮 Nerede?Seyrek, kümeli dünyalar (uzay oyunları, şehirler) · arazi ayrıntı düzeyi · görüntü sıkıştırma · harita karoları
Çizimle: altı nokta eklendikten sonra dörtlü ağaç
Her kutu en çok 2 nokta tutar. Üçüncü nokta (c) gelince kök dörde bölündü (mavi çizgiler); sol üstte a ve d varken e gelince o çeyrek de dörde bölündü (mor kesikli). Noktaların kalabalık olduğu köşe ince ince bölünür, boş yerler büyük kutular olarak kalır: ağaç dünyaya değil verinin dağılımına uyar.
Elle izleme: ekleme (kapasite 2, dünya 8 × 8)
| eklenen | ne oldu | ağaç |
|---|---|---|
| a (1, 1) | kökte yer var | kök: a |
| b (6, 2) | kökte yer var | kök: a, b |
| c (2, 6) | kök doldu → dörde böl; a, b, c dağıtılır | SolÜst: a · SağÜst: b · SolAlt: c · SağAlt: — |
| d (1, 3) | SolÜst (0–4, 0–4): yer var | SolÜst: a, d |
| e (3, 1) | SolÜst doldu → dörde böl (2 × 2’lik kareler) | SolÜst → [a] [e] [d] [—] |
| f (7, 7) | SağAlt: yer var | SağAlt: f |
(Ekranda y aşağı: “üst” = küçük y.) Hangi çocuğa gideceği iki karşılaştırma: x ≥ merkez.x mi, y ≥ merkez.y mi? a(1,1) için SolÜst’ün merkezi (2, 2): ikisi de hayır → SolÜst’ün SolÜst’ü.
Sorgu: (7, 1) çevresinde r = 1,5
| kare | daireye en yakın noktası | uzaklık | karar |
|---|---|---|---|
| kök | — | 0 | aç |
| SolÜst (0–4, 0–4) | (4, 1) | 3 | buda (3 nokta atlandı) |
| SağÜst (4–8, 0–4) | (7, 1) | 0 | aç → b’ye bak: √2 ≈ 1,41 ✔ |
| SolAlt (0–4, 4–8) | (4, 4) | 4,2 | buda |
| SağAlt (4–8, 4–8) | (7, 4) | 3 | buda |
6 noktadan yalnızca 1’ine bakıldı. “En yakın nokta” = dairenin merkezini kareye kıstırmak (G3’te yine göreceğiz).
Canlı: dörtlü ağaç 🌳
- Ekranı okuyun: gri noktalar nesneler; ince çizgiler ağacın kareleri. Yeşil daire fareyi izleyen sorgu. Sarı kareler sorgunun açtığı yapraklar; sarı noktalar bakılanlar; yeşil noktalar daire içindekiler.
- Boş bir yere birkaç kez üst üste tıklayın: beşinci noktada (kapasite 4) kare dörde bölünür. Aynı yere tıklamaya devam edin: bölünme derinleşir.
- Alt satırı okuyun: “… dal hiç açılmadı · … noktaya bakıldı (kaba kuvvet: …)”. Daireyi boş bölgeye götürün: bakılan nokta 0’a yakın.
- “kare kapasitesi”ni 1 yapın: çok derin, çok düğümlü ağaç. 10 yapın: sığ ağaç, yaprak başına daha çok test. Tatlı nokta ortada.
- “🎯 +100 kümeli”ye birkaç kez basın: sağ üstteki küme incecik bölünürken sol alt hâlâ dört büyük kare.
🔎 DEMODA DENEYİN
- Ekranı okuyun: gri noktalar nesneler; ince çizgiler ağacın kareleri. Yeşil daire fareyi izleyen sorgu. Sarı kareler sorgunun açtığı yapraklar; sarı noktalar bakılanlar; yeşil noktalar daire içindekiler.
- Boş bir yere birkaç kez üst üste tıklayın: beşinci noktada (kapasite 4) kare dörde bölünür. Aynı yere tıklamaya devam edin: bölünme derinleşir.
- Alt satırı okuyun: “… dal hiç açılmadı · … noktaya bakıldı (kaba kuvvet: …)”. Daireyi boş bölgeye götürün: bakılan nokta 0’a yakın.
- “kare kapasitesi”ni 1 yapın: çok derin, çok düğümlü ağaç. 10 yapın: sığ ağaç, yaprak başına daha çok test. Tatlı nokta ortada.
- “🎯 +100 kümeli”ye birkaç kez basın: sağ üstteki küme incecik bölünürken sol alt hâlâ dört büyük kare.
Kod: dörtlü ağaç (1/2)
Kod: dörtlü ağaç (2/2)
🎒 Kodu okuyalım
| ifade | ne demek | neden böyle |
|---|---|---|
p.x >= this.x && p.x < this.x + this.w | sol kenar dahil, sağ kenar hariç | Tam sınırdaki nokta tek bir çocuğa düşsün; iki kareye birden girmesin. |
this.derinlik >= 8 | derinlik sınırı | Aynı noktada 100 nesne varsa kare sonsuza kadar bölünür. Sınırda kapasiteyi aşmaya izin verilir. |
this.cocuklar.some(c => c.ekle(p)) | çocukları sırayla dene; ilk kabul edende dur | some ilk true’da keser: nokta yalnızca bir çocuğa girer. |
constrain(cx, this.x, this.x + this.w) | merkezi kareye kıstır | Karenin daireye en yakın noktasını verir; uzaklığı r’den büyükse kare daireye değmiyor. |
return sonuc (budamada) | bu dalı hiç gezme | Bütün hızlanma bu tek satırdan gelir. |
sonuc = [] varsayılan parametre | ilk çağrıda boş liste | Özyinelemede aynı liste aşağı taşınır; her düzeyde yeni liste kurulmaz. |
ÖnermeNoktalar birbirine çok yaklaşmıyorsa ağacın derinliği kabaca log₂(dünya kenarı / en küçük kare); ekleme ve nokta arama derinlik kadar adım sürer. Küçük bir bölge sorgusu, o bölgeye değen yapraklar + derinlik kadar düğüm gezer. Ağaç kendini dengelemez: derinlik sınırı bu yüzden şart.
🐍 Laboratuvar: hangi çeyrek?
Dörtlü ağaçta bir noktanın hangi çocuğa gideceğini söyleyen fonksiyon (elle izlemedeki “iki karşılaştırma”). Sağdaysa (
px >= cx) +1, alttaysa (py >= cy) +2. Bölme, çarpma, if zinciri gerekmez.Oyunlarda: gezegenler, araziler ve harita karoları
🚀 Kerbal Space Program: dörtlü ağaçtan gezegen
- Bir gezegenin yüzeyi bir küpün altı yüzüne açılır; her yüz bir dörtlü ağaçtır.
- Kameraya yakın kareler bölünür, bölünür: ayağınızın altındaki arazi metre ölçeğinde, ufuktaki dağ kilometre ölçeğinde üçgenlenir.
- Uzaklaştıkça çocuklar silinir, ebeveyn kare geri gelir. Aynı gezegen yörüngeden de yüzeyden de çizilebilir.
- Açık dünya oyunlarının arazi sistemlerinin çoğu bu fikrin bir çeşididir: “ayrıntı düzeyi” (LOD) = ağaçta ne kadar derine indiğiniz.
🗺️ Harita karoları
- Çevrimiçi haritalar dünyayı 256 pikselli kare resimlere böler. Yakınlaştırma düzeyi 0: bütün dünya tek karo. Düzey 1: 4 karo. Düzey 2: 16…
- Bir karonun adresi
z/x/y: yakınlaştırma düzeyi ve o düzeydeki sütun, satır. Bir karonun dört çocuğu:(z+1, 2x, 2y)…(z+1, 2x+1, 2y+1). - Bu, dünyanın üzerine kurulmuş bir dörtlü ağaç. Strateji oyunlarının yakınlaştırılabilir haritaları ve dev dokuları parça parça yükleyen sistemler aynı şemayı kullanır.
Ortak fikir: ihtiyaç olan yerde ayrıntı.
LEVEL 3
BVH
kutuların kutusu
Problem: farklı boyutlar ve ışın sorguları
- Izgara ve dörtlü ağaç uzayı böler. Bir nesne iki bölgenin sınırına düşerse ikisine de kaydolur; dev bir nesne yüzlerce hücreye.
- Bir ışın için ızgarada yol boyunca bütün hücreleri tek tek gezmek gerekir.
- Fikir: uzayı değil, nesneleri grupla. Her nesnenin bir sınırlayıcı kutusu (AABB) var; yakın nesnelerin kutuları daha büyük bir kutuya, onlar daha büyüğüne…
- Kök kutu bütün sahneyi sarar. Her nesne ağaçta tam bir kez bulunur; boyutu ne olursa olsun.
- Sorgu (ışın, kutu, nokta): büyük kutuya değmiyorsa içindeki her şeyi atla.
Kurma: sırala, ortadan böl
- Bütün nesneleri saran kutuyu bul.
- Kutunun uzun ekseni boyunca nesneleri merkezlerine göre sırala.
- Ortadan ikiye böl; iki yarı için aynısını yap.
- İki ya da daha az nesne kalınca dur: yaprak.
Elle: merkezleri x = 1, 2, 4, 7, 8, 9 olan altı kutu → {1, 2, 4} | {7, 8, 9} → {1} | {2, 4} ve {7} | {8, 9}. Derinlik 2.
🎮 Nerede?Işın izleme · fizik motorlarının geniş aşaması · raycast (“mermi neye çarptı?”, “fare hangi nesnede?”) · kamera ayıklama
Çizimle: ışın, iki dilim ve iki kutu
Işın O = (0, 0)’dan (10, 5)’e gidiyor. Mavi şerit x dilimi (4 … 6): ışın ona t = 0,4’te girip t = 0,6’da çıkıyor. A kutusunun y dilimine (1 … 4) zaten içindeyken giriyor: giriş 0,4 ≤ çıkış 0,6 → vurdu, (4, 2) noktasında. B’nin y dilimine (3,5 … 5) ise t = 0,7’de giriyor; ama o sırada x diliminden çoktan çıkmış: ıskaladı.
Işın bir kutuya giriyor mu? “Dilim” testi
- Işın: P(t) = O + t·d, t: 0 … 1 (G1’deki parametrik gösterim).
- Kutu, iki dilimin kesişimidir: x’te [x₀, x₁] ve y’de [y₀, y₁].
- Işın x dilimine
t = (x₀ − O.x)/d.x’te girer,(x₁ − O.x)/d.x’te çıkar (d.x eksiyse yer değiştirir). y için aynısı. - Kutunun içinde olmak = iki dilimin de içinde olmak. O hâlde: giriş = girişlerin büyüğü, çıkış = çıkışların küçüğü.
- giriş ≤ çıkış ise ışın kutuyu keser; giriş t’si çarpma anıdır. Değilse ıskalar.
Elle hesap: O = (0, 0), d = (10, 5)
| kutu A: x 4–6, y 1–4 | kutu B: x 4–6, y 3,5–5 | |
|---|---|---|
| x dilimi | 0,4 … 0,6 | 0,4 … 0,6 |
| y dilimi | 0,2 … 0,8 | 0,7 … 1,0 |
| giriş = büyük olan | max(0,4, 0,2) = 0,4 | max(0,4, 0,7) = 0,7 |
| çıkış = küçük olan | min(0,6, 0,8) = 0,6 | min(0,6, 1,0) = 0,6 |
| sonuç | 0,4 ≤ 0,6 → VURDU, t = 0,4 → (4, 2) | 0,7 > 0,6 → ıskaladı |
B için: ışın x dilimini terk ettiğinde (t = 0,6) henüz y dilimine girmemişti (t = 0,7).
ÖnermeBVH’de bir ışın sorgusu, dengeli ağaçta yaklaşık 2·log₂N kutu testi yapar: 1.000 nesne için ~20, 1.000.000 için ~40 (kaba kuvvet: N). Kurma: sıralamalar yüzünden N log N.
Canlı: ışın ve kutu ağacı 🎯
- Ekranı okuyun: gri kutular nesneler; renkli çerçeveler BVH düğümleri (her renk bir derinlik). Mavi nokta nişancı (sürüklenir), siyah çizgi ışın, kırmızı nokta ilk vuruş.
- Kalın çerçeveler ışının girdiği düğümler; soluk kesikli çerçeveler ıskalanan ve içi hiç açılmayan düğümler. Sarı: gerçekten test edilen nesneler.
- “gösterilen derinlik”i 0’dan 5’e tek tek artırın: ağacın katlarını görün (0 = bütün sahne, sonra ikiye, dörde…).
- Işını boşluğa doğrultun: birkaç düğüm testiyle “hiçbir şeye çarpmıyor” cevabı gelir.
- Sol üstteki iki satırı karşılaştırın. Nesne sayısını 8 → 60 yapın: kaba kuvvet 8 → 60; BVH’nin sayısı çok daha yavaş artar (ağaç yalnızca birkaç kat derinleşir).
🔎 DEMODA DENEYİN
- Ekranı okuyun: gri kutular nesneler; renkli çerçeveler BVH düğümleri (her renk bir derinlik). Mavi nokta nişancı (sürüklenir), siyah çizgi ışın, kırmızı nokta ilk vuruş.
- Kalın çerçeveler ışının girdiği düğümler; soluk kesikli çerçeveler ıskalanan ve içi hiç açılmayan düğümler. Sarı: gerçekten test edilen nesneler.
- “gösterilen derinlik”i 0’dan 5’e tek tek artırın: ağacın katlarını görün (0 = bütün sahne, sonra ikiye, dörde…).
- Işını boşluğa doğrultun: birkaç düğüm testiyle “hiçbir şeye çarpmıyor” cevabı gelir.
- Sol üstteki iki satırı karşılaştırın. Nesne sayısını 8 → 60 yapın: kaba kuvvet 8 → 60; BVH’nin sayısı çok daha yavaş artar (ağaç yalnızca birkaç kat derinleşir).
Kod: BVH kurma ve ışın (1/2)
Kod: BVH kurma ve ışın (2/2)
🎒 Kodu okuyalım
| ifade | ne demek | neden böyle |
|---|---|---|
{ x0: Infinity, …, x1: -Infinity } | “boş” kutu | İlk nesneyle min/max alınınca doğru değerlere oturur; özel durum gerekmez. |
s.length >> 1 | uzunluğun yarısı (tam sayı) | Bir bit sağa kaydırma = 2’ye bölüp aşağı yuvarlama. |
[ta, tb] = [tb, ta] | iki değişkeni yer değiştir | Yön eksiyse ışın dilime “uzak” kenardan girer; giriş her zaman küçük t olsun. |
abs(dd) < 1e-9 | ışın bu eksene paralel | Bölme yapılamaz; ışın o dilimin içinde değilse zaten ıskalar. |
t > enIyi.t | kutu, eldeki en yakın vuruştan uzakta | İkinci budama: daha yakın bir şey bulduysak arkadaki kutuları açma. |
enIyi nesnesi parametrede | sonucu taşıyan ortak kutu | Özyinelemenin her düzeyi aynı “şu ana kadarki en iyi”yi günceller (Geometrik BST’deki en yakın komşu gibi). |
🌱 Isınma kodu: iki kutu çakışıyor mu?
Sınırlayıcı kutu (AABB) testi: geniş aşamanın en çok çağrılan fonksiyonu; BVH’de kutu sorgusunun budama testi. İki kutu ancak her iki eksende de örtüşüyorsa çakışır; tek eksende ayrılarsa ayrıdırlar. Başlangıç kodu yalnızca x’e bakıyor: alt alta duran iki kutuyu çakışıyor sanıyor. (G3’teki “ayıran eksen” fikrinin en basit hâli.)
Oyunlarda: Box2D’nin “şişman” kutuları
- Box2D, sayısız 2B oyunun (ve Unity’nin 2B fiziğinin) arkasındaki fizik motoru. Geniş aşaması bir BVH: “dinamik AABB ağacı”.
- Sorun: nesneler her kare kıpırdar. Her kıpırtıda ağacı güncellemek pahalı.
- Çözüm: ağaca nesnenin gerçek kutusu değil, her yönde 0,1 metre büyütülmüş “şişman” kutusu konur. Nesne şişman kutusunun içinde kaldığı sürece ağaca dokunulmaz.
- Nesne kutudan çıkınca yeniden eklenir; yeni kutu, hareket yönünde hızın 4 katı kadar ileri uzatılır: “birkaç kare daha buralardasın” tahmini.
- Bedeli: biraz daha fazla yanlış alarm (şişman kutular daha çok örtüşür). Dar aşama onları eler. Kazanç: duran ve yavaş nesneler için sıfır güncelleme.
Yorum satırındaki btDbvt: 3B fizik motoru Bullet’in aynı fikirdeki ağacı. Kaynak: Erin Catto, Box2D v2.4.
Oyunlarda: ışın izleme neden bu kadar geç geldi?
- Bir karede milyonlarca ışın, sahnede milyonlarca üçgen. Her ışını her üçgenle sınamak: 10¹² test. İmkânsız.
- BVH ile ışın başına birkaç düzine kutu testi ve birkaç üçgen testi yeter (önermedeki 2·log₂N).
- Grafik kartlarındaki ışın izleme desteği (2018’den beri) temelde iki işi donanıma gömer: ışın–kutu ve ışın–üçgen testleri ve BVH’de gezinme. Oyun motoru sahneyi iki katlı bir BVH olarak verir: her model için bir alt ağaç, modellerin üstünde bir üst ağaç.
- Hareketli modelde alt ağaç yeniden kurulmaz; yalnızca kutuları yeniden sığdırılır (“refit”).
- Sebastian Lague’ün “Coding Adventure: More Ray Tracing!” videosu bir BVH’yi sıfırdan yazıp her adımda kazancı ölçer (Kaynaklar).
📜 Titanfall’ın çarpışmaları
Respawn’ın GDC konuşması “Extreme SIMD: Optimized Collision Detection in Titanfall”, hızlı hareket eden pilotlar ve dev robotlar için çarpışma sorgularını kutu ağaçları ve işlemcinin toplu (SIMD) komutlarıyla nasıl hızlandırdıklarını anlatır: bir düğümün birkaç çocuk kutusu tek komutla aynı anda test edilir.
Ortak ders (Y18): en büyük kazanç, işi hızlandırmaktan değil yapmamaktan gelir.
Quiz 2 · BVH
Bir BVH’de ışın, kök kutunun sol çocuğunu ıskalıyor. Sol çocuğun altında 5.000 üçgen var. Kaç üçgen testi yapılır?
Sınırlayıcı kutu, içindeki her şeyi tamamen sarar. Işın kutuya girmiyorsa içindeki hiçbir nesneye değemez; o dalın tamamı tek bir kutu testiyle elenir. Demodaki soluk kesikli çerçeveler tam olarak bu elenen dallardır.
LEVEL 4
Hangisini seçmeli?
tek doğru yok; dağılıma bak
Karşılaştırma
| yapı | en iyi olduğu durum | zayıf yanı | oyun örneği |
|---|---|---|---|
| Düzgün ızgara / uzaysal hash | Benzer boyutlu, çok sayıda, hareketli nesne; her kare baştan kurulur | Çok farklı boyutlar; nesnelerin tek yere yığılması | DOOM blockmap, Minecraft parçaları, mermiler, sürüler |
| Dörtlü / sekizli ağaç | Kümeli, seyrek dağılım; çoğunlukla durağan nesneler; ayrıntı düzeyi | Hareketli nesnede güncelleme; işaretçi ağacı önbellek dostu değil | Kerbal gezegenleri, arazi LOD’u, harita karoları |
| kd-ağacı (Geometrik BST sunumu) | Durağan nokta kümesinde en yakın komşu | Ekleme/silme dengesizleştirir | en yakın siper/kaynak, foton haritası |
| BVH | Farklı boyutlu şekiller; ışın ve kutu sorguları; kısmen hareketli | Kurması pahalı; iyi bölme kuralı ister | Box2D / Bullet geniş aşaması, ışın izleme |
| Sweep and prune (Geometrik BST sunumu) | Kareden kareye az değişen sahne; tek eksende sıralı liste | Bir eksende yığılma | PhysX’in geniş aşama seçeneklerinden biri |
Karar sırası: önce ölç (Y18) → sorun gerçekten çift sayısıysa ızgarayla başla → dağılım ya da boyutlar ızgarayı bozuyorsa ağaca geç. Motor kullanıyorsanız geniş aşama zaten hazırdır; kendi oyun mantığınız (“yakınımdaki düşmanlar”) için ızgara çoğu zaman yeter.
Quiz 3 · seçim
300 × 300 km’lik bir uzay haritasında 5.000 gemi var ve neredeyse hepsi dört yıldız sisteminin çevresinde toplanmış; aradaki boşluk bomboş. Tek tip hücreli düzgün ızgara neden kötü bir seçim?
Düzgün ızgaranın çözünürlüğü her yerde aynıdır. Kümeli dağılımda ya boşluk için çok fazla hücre ya da kümeler için çok kalabalık hücre elde edersiniz. Uzaysal hash boş hücre sorununu çözer ama kalabalık hücre sorununu çözmez; dörtlü ağaç ya da iki katlı ızgara (kaba + ince) veriye uyum sağlar.
LEVEL 5
Hepsi bir arada
tam kod, araçlar, kapanış
📦 Tam kod: p5.js ile 1.500 topu çarpıştırmak
Bu döngü + “Kod: uzaysal hash ızgarası” slaytındaki Izgara sınıfı.
🎮 Çalıştırın, kopyalayın, bozun
▶ Eksiksiz örneği aç — yaklaşık 60 satır: 1.500 top; G tuşu ızgarayı açıp kapatır. FPS sayacını izleyin.
Deneyin:
- G’ye basın: test sayısı 2.248.500’e fırlar; FPS düşer.
HUCRE’yi 4 ve 200 yapıp test sayısını formülle tahmin edin, sonra okuyun.- Top sayısını 5.000 yapın: ızgarayla hâlâ akıcı mı?
- Fareyle tıklanan noktadaki topları patlatın:
yakindakiler(mouseX, mouseY, 40).
🧰 Motorlarda ve kütüphanelerde
| Unity (2B) | Physics2D.OverlapCircle · Raycast | Box2D’nin dinamik AABB ağacını sorgular. NonAlloc sürümleri çöp üretmez. |
| Unity (3B) | Physics.OverlapSphere · Proje Ayarları → Physics → Broadphase Type | PhysX: Sweep and Prune, Multibox Pruning ya da Automatic Box Pruning arasında seçim. |
| Unity DOTS | NativeParallelMultiHashMap | Kendi uzaysal hash’inizi iş parçacıklarında kurmak için (binlerce ajan). |
| Unreal | OverlapMultiByChannel · TOctree2 · THierarchicalHashGrid2D | Hazır sorgular ve kendi verileriniz için sekizli ağaç / hash ızgarası. |
| Godot | PhysicsDirectSpaceState2D.intersect_shape · Area2D | Motorun BVH’si üzerinden sorgu. |
| JavaScript | d3-quadtree · rbush | Hazır dörtlü ağaç ve R-ağacı (harita uygulamalarının standardı). |
| Python | scipy.spatial.cKDTree | Analiz ve araçlar için en yakın komşu sorguları. |
Kural: çarpışma için motorun fiziğini kullanın. Oyun mantığı sorguları (“en yakın 5 düşman”, “patlama yarıçapındakiler”, sürü komşuları) için fizik motorunu her kare sorgulamak pahalı olabilir; orada kendi küçük ızgaranız çoğu zaman daha hızlıdır.
🤖 Bu konuyu bir YZ kod asistanıyla yazarken
Sık yapılan hatalar — kontrol edin
Math.roundya da| 0ile hücre hesabı (eksi koordinatta yanlış)- Nesne hareket ettiği hâlde ızgaradaki eski kaydını silmemek
- Hücre boyundan büyük nesneyi tek hücreye koymak
- Aynı çifti iki kez test etmek (i < j kuralı)
- Her kare yeni liste/nesne üretmek (çöp toplayıcı takılması, Y18)
- Dörtlü ağaçta derinlik sınırı koymamak
İyi bir istek (prompt) örneği
“p5.js. {x, y, r} dairelerle çalışan bir SpatialHash sınıfı yaz: clear(), insert(obj) (dairenin değdiği bütün hücrelere), query(x, y, r) (tekrarsız adaylar). Hücre hesabı Math.floor ile; eksi koordinatlar desteklensin. Listeleri kareler arasında yeniden kullan. Bir test sayfası: 2.000 daire, bir tuşla kaba kuvvet / ızgara arasında geçiş, ekranda test sayısı ve FPS, iki yöntemin bulduğu çarpışma kümelerinin aynı olduğunu doğrulayan bir console.assert.”
- Doğruluk testini isteyin: hızlı yapı, kaba kuvvetle aynı sonucu vermeli
- Nesne boyutlarını ve dağılımını söyleyin; yapı seçimi buna bağlı
- Ölçüm isteyin: test sayısı, kare süresi
💬 Tartışma soruları
Yanınızdakiyle 2 dakika konuşun, sonra sınıfça tartışalım
- Minecraft’ta “parça sınırı”nı bilen oyuncular çiftliklerini ona göre kurar. Bir oyunun iç veri yapısının oyuncular tarafından keşfedilip kullanılması iyi bir şey mi, bir kusur mu?
- DOOM 1993’te düzgün ızgara kullandı; bugünün fizik motorları kutu ağacı kullanıyor. DOOM’un haritaları ve nesneleri hakkında ne biliyoruz ki ızgara orada iyi bir seçimdi?
- Bir “survivor” oyununda ekranda 5.000 düşman var ve hepsi oyuncunun üstüne yığılıyor. Izgara neden işe yaramamaya başlar? Tasarımla (kodla değil) nasıl çözerdiniz?
- Motor zaten geniş aşamayı yapıyorsa bu konuyu neden öğreniyoruz? Kendi ızgaranızı yazmanın mantıklı olduğu iki durum söyleyin.
- Gerçek hayatta “uzayı bölüp yalnızca yakındakilere bakmak” fikrini nerede kullanıyoruz? (posta kodları, kütüphane rafları, harita karoları…)
🚀 Proje ve araştırma önerileri
- [kolay] Mermi cehennemi — p5.js’te 3.000 mermi ve 200 düşman; uzaysal hash ile çarpışma. Ekranda test sayısı ve FPS; G tuşuyla kaba kuvvete geçiş.
- [kolay] Patlama yarıçapı — Tıklanan noktada patlama: yarıçap içindeki nesneleri ızgara sorgusuyla bulup itin. Sorgunun baktığı hücreleri boyayın.
- [orta] Boids + ızgara — Y7’deki sürüyü 2.000 kuşa çıkarın; komşu aramayı ızgarayla yapın. Hücre boyu–test sayısı grafiğini çizip bu sunumdaki formülle karşılaştırın.
- [orta] Dörtlü ağaçla uzay haritası — Kümeli 10.000 yıldız; fareyle kutu seçimi dörtlü ağaç sorgusuyla. Açılan ve budanan düğümleri görselleştirin.
- [zor] Şişman kutulu BVH — Hareketli 500 kutu için BVH; Box2D’deki gibi büyütülmüş kutular kullanın. Kare başına kaç nesnenin yeniden eklendiğini büyütme payına göre ölçün.
- [araştırma] Hangisi ne zaman? — Aynı sahneyi (eşit dağılım, kümeli dağılım, karışık boyutlar) ızgara, dörtlü ağaç ve BVH ile çalıştırıp test sayısı ve süre tablosu çıkarın.
Neler öğrendik? 🎒
- Sorun: herkes herkesle = N². Çözüm: uzayı böl, yalnızca yakındakilere bak. Geniş aşama aday üretir, dar aşama kesin test eder.
- Izgara / uzaysal hash:
floor(konum / boy); test ≈ 4,5·k·N; hücre boyu ≈ nesne çapı. (DOOM blockmap, Minecraft parçaları.) - Dörtlü ağaç: dolunca böl; kümeli dağılıma uyum sağlar; sorgu değmeyen kareyi budar. (Gezegenler, arazi, harita karoları.)
- BVH: kutuların kutusu; dilim testi; ışın başına ≈ 2·log₂N kutu. (Box2D’nin şişman kutuları, ışın izleme.)
- Bölümleme sihir değil: herkes aynı yere yığılırsa yine N². Önce ölç, ızgarayla başla.
- Sonraki: çarpışma tespiti: adayları bulduk; şimdi iki şeklin gerçekten çakışıp çakışmadığını kesin olarak söylemek.
🎮 Bu sunumdaki oyunlar
Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.
Doom 1993 · nişancı
Türü popülerleştiren nişancı; kaynak kodu 1997’de açıldı.
Minecraft 2011 · kum havuzu
Bloklardan oluşan, prosedürel üretilen, neredeyse sonsuz bir dünya.
Kerbal Space Program 2015 · uzay simülasyonu
Küçük yeşil Kerbal’lar için roket tasarlayıp gerçekçi yörünge fiziğiyle uçurursunuz.
Kaynaklar: videolar 🎬
Spatial Hash Grids & Tales from Game DevelopmentSimonDev
Finding collisions among thousands of objects blazing fastTen Minute Physics
Coding Challenge #98.1: Quadtree - Part 1The Coding Train
Coding Adventure: More Ray Tracing! (BVH)Sebastian Lague
Extreme SIMD: Optimized Collision Detection in TitanfallGDC
Quad & Oct Trees - Data Structures For PerformanceKayle Gishen
Kaynaklar: kaynak kodu, yazılar ve etkileşimli sayfalar 📚
- DOOM kaynak kodu: p_maputl.c (blockmap) · Box2D: b2_dynamic_tree.h (dinamik AABB ağacı)
- Robert Nystrom, Game Programming Patterns: Spatial Partition — ücretsiz bölüm; ızgarayı bir savaş alanı örneğiyle adım adım kurar
- An interactive intro to quadtrees · Jim Kang: An interactive explanation of quadtrees — tarayıcıda oynayarak
- Lean Rada: Sort, sweep, and prune — geniş aşamanın öbür klasik yöntemi, canlı örneklerle
- Matthias Müller: Ten Minute Physics — 11. bölüm (uzaysal hash) ve 24. bölüm (BVH), kaynak kodlarıyla
- Christer Ericson, Real-Time Collision Detection (2005), 6. ve 7. bölümler: BVH ve uzaysal bölümleme
- Bu dersin ilgili sunumları: Hash Tabloları · Ağaçlar · BST’nin Geometrik Uygulamaları · Y18 Performans
NEXT LEVEL ▶
Çarpışma Tespiti
Daire, AABB, OBB, ayıran eksen teoremi, ışın–şekil kesişimi
SONRAKİ SUNUM ▶