BST’nin Geometrik Uygulamaları

OYUNLARDA YAPAY ZEKÂ · ARAMA AĞAÇLARI

Aralık arama, süpürme doğrusu, kd-ağaçları, aralık ağaçları — oyun dünyasında “yakınımda ne var?”

PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

1B aralık arama — “kameranın gördüğü x aralığında kim var?”
Doğru parçası kesişimi — süpürme doğrusu fikri sweep line
kd-ağaçları — 2B aralık arama: RTS seçim kutusu
En yakın komşu — “en yakın düşman kim?”
Aralık arama ağaçları — zaman aralıkları, vuruş pencereleri
Çarpışma: geniş faz — AABB, sweep and prune, fizik motorları

🎮 Bu dersin sonunda…

…Unity’nin fizik ayarlarındaki “Broadphase Type: Sweep and Prune” seçeneğinin ne olduğunu ve 10.000 birimlik bir RTS’de “menzilimde kim var?” sorusunun nasıl hızlı yanıtlandığını bileceksiniz.

🤔 ISINMA: SEÇİM KUTUSU

Bir RTS’de haritada 10.000 birim var. Oyuncu fareyle bir kutu çiziyor. Hangi birimler kutunun içinde?

Kolay: her birime tek tek bak → 10.000 kontrol. Tamam, bir kez yapılırsa sorun değil.

Ama yapay zekâ her karede, her birim için “menzilimdeki düşmanlar kim?” diye soruyor: 10.000 × 10.000 = 100 milyon kontrol, saniyede 60 kez. 😱

Bugünün sorusu: “içinde ne var?” sorusunu her şeye bakmadan nasıl yanıtlarız?

Mini sözlük

range search · range count	aralık arama · aralık sayma	Bir aralıktaki anahtarları bul · say
orthogonal	dik / eksenlere paralel	Yatay ve dikey çizgiler, eksene hizalı kutular
sweep line · event	süpürme doğrusu · olay	Düzlemi soldan sağa tarayan hayali çizgi · çizginin durduğu noktalar
kd-tree (2d-tree)	kd-ağacı	Sırayla x’e ve y’ye göre bölen BST
nearest neighbor	en yakın komşu	Bir noktaya en yakın nokta
pruning	budama	Sonuç içeremeyeceği belli olan alt ağaca hiç girmemek
interval	aralık	[başlangıç, bitiş] çifti: zaman, x aralığı…
AABB · broad phase	eksene hizalı kutu · geniş faz	Çarpışma adaylarını hızlıca eleyen ilk aşama

LEVEL 0

1B aralık arama

1d range search — bir doğru üzerindeki noktalar

1B aralık arama
doğru parçası kesişimi
kd-ağaçları
en yakın komşu
aralık arama ağaçları
çarpışma: geniş faz

Problem: bir eksen üzerindeki noktalar

Sıralı sembol tablosuna iki yeni işlem:

Aralık sayma range count: lo ile hi arasında kaç anahtar var?
Aralık arama range search: bu anahtarlar hangileri?

🎮 2B yan kaydırmalı oyun (side-scroller)Düşmanlar x konumlarına göre tutuluyor. Kamera [kameraX, kameraX + 1280] aralığını görüyor. Hangi düşmanları güncelleyip çizelim? Ekran dışındakiler “uyusun”.

Aynı soru: “skor tablosunda 1500–1600 MMR arasındaki oyuncular”, “şu iki zaman damgası arasındaki olaylar”.

Hangi yapı?

yapı	ekleme	aralık sayma	aralık arama
sırasız dizi	1	N	N
sıralı dizi	N	lg N	R + lg N
dengeli BST	lg N	lg N	R + lg N

N = toplam anahtar, R = aralıktaki anahtar sayısı (cevabın boyutu). R’yi yazdırmak zaten R adım sürer; bundan iyisi olamaz.

Neden aralık sayma lg N?rank(k) = k’dan küçük anahtar sayısı. O hâlde: sayı = rank(hi) − rank(lo) (+1, hi tablodaysa). İki rank çağrısı = iki kez lg N. Hiçbir anahtara tek tek bakmadan saydık!

Aralık sayma — kod

rank: Arama Algoritmaları sunumundaki ikili arama — bulamazsa lo = “kendisinden küçüklerin sayısı”
Sıralı dizide ya da BST’de (Ağaçlar sunumundaki rank) aynı fikir

🎒 Örneka = [10, 20, 30, 40, 50], aralık [15, 40]:
rank(40) = 3, rank(15) = 1 → 3 − 1 = 2, 40 dizide olduğu için +1 → 3 (20, 30, 40) ✔

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`rank(a, key)`	key’den küçük kaç eleman var?	ikili arama; bulamazsa `lo` tam ekleneceği yer
`rank(a, hi) − rank(a, lo)`	[lo, hi) aralığındakiler	iki arama: ~2 lg N, aralık ne kadar büyük olursa olsun
`if (a[r] === hi) count++`	hi dizideyse onu da say	aralık iki ucu da kapalı: [lo, hi]
kullanım	“bu x aralığında kaç birim var?”	saymak için birimleri tek tek gezmek gerekmez

BST’de aralık arama: kamera penceresi

Aralık arama — kural

Düğüm x’te:

lo < x.key ise → sola in (solda aralığa düşen olabilir)
lo ≤ x.key ≤ hi ise → x’i raporla
x.key < hi ise → sağa in

Koşul tutmuyorsa o alt ağaca hiç girmeyiz: içindeki anahtarların hepsi aralığın dışında. Bu fikrin adı budama pruning — bu dersin her algoritmasında karşımıza çıkacak!

ÖnermeDengeli bir BST’de aralık arama R + lg N ile orantılı süre alır.

Sadece iki “sınır yolu” (lo’ya ve hi’ye giden yollar, ≤ lg N’er düğüm) ve aralığın içindeki R düğüm ziyaret edilir.

🔗 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.

🔗 Data Structure Visualizations

David Galles (USF)

Neredeyse her veri yapısı için bir oyun alanı: ekle, sil, ara düğmeleriyle yapının nasıl değiştiğini izleyin.

🔗 cp-algorithms

cp-algorithms.com

Algoritmaların matematiksel ve kod düzeyinde ayrıntılı anlatımı (geometri, graf, veri yapıları).

Quiz 1 · 1B aralık arama

1 milyon düşmanın x konumları dengeli bir BST’de. Kamera aralığında 50 düşman var. Aralık arama yaklaşık kaç düğüm ziyaret eder?

R + (iki sınır yolu): 50 sonuç + her biri ~lg 10⁶ ≈ 20 düğümlük iki yol. Bir milyonun yanında ~90 düğüm! Sırasız dizide 1 milyonun hepsine bakmak gerekirdi.

LEVEL 1

Doğru parçası kesişimi

orthogonal line segment intersection — süpürme doğrusu

1B aralık arama
doğru parçası kesişimi
kd-ağaçları
en yakın komşu
aralık arama ağaçları
çarpışma: geniş faz

Problem: yatay ve dikey parçaların kesişimleri

N tane yatay ya da dikey doğru parçası. Bütün kesişim noktalarını bul.

Kaba kuvvet: her yatayı her dikeyle dene → ~N²/4 test
N = 1 milyon → 250 milyar test 😱

Kolaylık için: hiçbir iki uç noktanın x’i (ya da y’si) aynı değil diyelim. (Gerçek kodda eşitlikler dikkatle ele alınır.)

🎮 Tron ışık motosikletleriHer motosiklet arkasında yatay ve dikey çizgilerden oluşan bir iz bırakır. Kim kimin izine çarptı? Izgara tabanlı haritalarda duvar–lazer kesişimleri, PCB/devre editörleri, 2B seviye editöründe çakışan duvarlar… aynı problem.

Fikir: soldan sağa süpür

Bütün x koordinatlarını sırala: bunlar olaylar events
Dikey bir çizgi soldan sağa ilerlesin. Her olayda dur:
Yatay parçanın sol ucu → y’sini BST’ye ekle
Yatay parçanın sağ ucu → y’sini BST’den sil
Dikey parça [y1, y2] → BST’de 1B aralık arama! Bulunan her y bir kesişim.

💡 Sihir2B bir problemi, bir sürü 1B probleme çevirdik. BST her an “süpürme doğrusunu kesen yatay parçaları” tutuyor.

Süpürme doğrusu — animasyon

Kesikli kırmızı = süpürme doğrusu · mavi kalın = BST’deki (aktif) yataylar · sarı = şu anki olay · yeşil şerit = aralık sorgusu · kırmızı nokta = kesişim.

Süpürme doğrusu — analiz

ÖnermeSüpürme doğrusu algoritması N dik doğru parçasının R kesişimini N lg N + R ile orantılı sürede bulur.

Kanıt

Olayları sıralamak: N lg N
Her yatay için bir ekleme + bir silme: N lg N
Her dikey için bir aralık arama: N lg N + R

N = 1 milyon: 250 milyar test yerine ~20 milyon adım. ~10.000 kat fark.

📜 Çip tasarımı ve Moore yasası

1970’lerde çip tasarımcıları devre çizimlerindeki hataları (çakışan iletkenler) kaba kuvvetle, yani N² ile kontrol ediyordu.

Moore yasası: transistör sayısı her ~2 yılda bir 2 katına çıkar. Bilgisayarlar da 2 kat hızlanır. Ama N² algoritma 2 kat büyük çipte 4 kat iş yapar → kontrol süresi her nesilde 2 katına çıkar!

Süpürme doğrusu (N lg N) ile bu sorun çözüldü: hızlı bilgisayarlar daha büyük çipleri yetişerek kontrol edebildi. İyi algoritma = daha iyi donanımın kapısı.

Quiz 2 · doğru parçası kesişimi

Süpürme doğrusu algoritmasında BST’de ne tutulur?

BST “aktif” yatayları tutar: sol ucu geçilmiş ama sağ ucu henüz gelmemiş olanlar. Bir dikey parça gelince, sadece bunlarla kesişebilir → y aralığında 1B arama yeter. x’ler BST’de değil, olay sırası olarak sıralanır.

LEVEL 2

kd-ağaçları

2d-trees — düzlemi sırayla x’e ve y’ye göre böl

1B aralık arama
doğru parçası kesişimi
kd-ağaçları
en yakın komşu
aralık arama ağaçları
çarpışma: geniş faz

2B aralık arama

Düzlemde N nokta. Eksenlere hizalı bir dikdörtgenin içindekileri bul (ya da say).

🎮 RTS seçim kutusu
🎮 Mini harita: kamera dikdörtgenindeki birimleri çiz
🎮 Yapay zekâ: “şu bölgede kaç düşman var?” (tehdit haritası)
Veritabanı: “yaşı 20–30 ve geliri 40–60 bin olanlar” (2 boyut!)

İlk fikir: ızgara gridHaritayı M × M kareye böl, her karede o karedeki noktaların listesi. Sorguda sadece dikdörtgenin değdiği karelere bak.

Sorun: kümelenme clustering. MMO’da oyuncuların çoğu şehirde toplanır: birkaç kare binlerce oyuncu, geri kalan binlerce kare bomboş. Kare boyutunu ne seçerseniz seçin biri kötü olur.

Izgara (ve “uzamsal hash”) noktalar düzgün dağılmışsa çok iyidir — Hash Tabloları sunumunda tekrar göreceğiz.

2d-ağacı: verilere uyum sağlayan bölme

Bir BST, ama anahtar nokta
Çift derinlik (0, 2, 4…): x’e göre karşılaştır → noktadan geçen dikey çizgi: sol / sağ
Tek derinlik (1, 3, 5…): y’ye göre karşılaştır → yatay çizgi: üst / alt
Her düğüm, düzlemin bir dikdörtgen bölgesine karşılık gelir ve onu ikiye böler
Kalabalık yerlerde bölgeler küçülür, boş yerlerde büyük kalır → kümelenmeye uyum 🎉

⚙️ “k” neden?k-boyutlu ağaç: 3B oyunlarda x, y, z sırayla (3d-ağacı). Derinlik d’de d % k numaralı koordinata göre bölünür.

2d-ağacı oyun alanı: ekleme

Sol tarafa tıklayarak nokta ekleyin (ya da “Örnek sorgu”). Notlar her karşılaştırmayı anlatıyor; sağda aynı noktaların BST görünümü.

🎒 Ön bilgi: nokta sınıfı ve varsayılan parametre

Point: x ve y’yi bir arada tutan küçük sınıf (p5.js’teki createVector gibi)
p.x = “p noktasının x’i”
Varsayılan parametre default parameter: vertical=True → çağıran vermezse True kabul edilir. İlk çağrı insert(root, p) kökte dikey başlar
not vertical / !vertical: her seviyede yön değişir (True → False → True…)
% (mod): d % 2 == 0 → d çift mi? (k boyutta d % k)

2d-ağacına ekleme — kod

BST’nin put’u ile aynı iskelet. Tek fark: hangi koordinatı karşılaştıracağımız derinliğe göre değişir.

BenzerlikBST: key < x.key
2d-ağacı: p.x < x.p.x ya da p.y < x.p.y

Uyarı: 2d-ağacı kendini dengelemez. Rastgele noktalarda yüksekliği ~lg N civarındadır; noktalar sıralı gelirse (ör. hepsi bir çizgi üzerinde) BST gibi bozulabilir.

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`vertical`	bu düğüm dikey çizgiyle mi bölüyor?	seviyeler sırayla x’e ve y’ye göre böler
`p.x < x.p.x`	dikey çizginin solunda mı?	x seviyesinde BST karşılaştırması x’e göre
`p.y < x.p.y`	yatay çizginin altında mı?	y seviyesinde y’ye göre
`!vertical`	çocuğa inerken yönü değiştir	her seviye alanı bir öncekinin dik yönünde böler
`new KdNode(p, vertical)`	boş yere yeni düğüm	sıradan BST eklemesinin aynısı; yalnızca karşılaştırılan koordinat değişiyor

2d-ağacında aralık arama

Sorgu dikdörtgeni q. Düğüm x’te:

x’in bölgesi q ile kesişmiyorsa → bu alt ağaçta aradığımız nokta olamaz → BUDA ✂️
x’in noktası q’nun içindeyse → raporla
Sol ve sağ alt ağaçlarda özyinelemeyle ara

Bölge = düğümün sorumlu olduğu dikdörtgen (kök: bütün harita). Ekleme sırasında ebeveynin bölgesinden hesaplanıp düğümde saklanır.

ÖnermeTipik süre: R + lg N.

En kötü durum (noktalar dengeli dağılmışken bile): R + √N — yine N’den çok daha iyi.

Aralık arama — kendiniz deneyin

Sol tarafta fareyle dikdörtgen çizin. Gri gölgeli bölgeler budanan alt ağaçlar: oradaki noktalara hiç bakılmadı. Sayaçta kaba kuvvetle karşılaştırın.

🎒 Ön bilgi: dikdörtgen sınıfı

Eksene hizalı dikdörtgen axis-aligned rectangle: 4 sayı yeter.

contains(p): nokta içeride mi? → x ve y aralıkta mı
intersects(r): iki dikdörtgen kesişiyor mu? → x aralıkları kesişiyor ve y aralıkları kesişiyor

🎒 İki aralık ne zaman kesişmez?Biri ötekinin tamamen solunda ya da tamamen sağındaysa: a.max < b.min veya b.max < a.min. Tersini alınca (De Morgan): kesişir ⇔ a.min ≤ b.max ve b.min ≤ a.max.

🎒 Python’daki a <= b <= c zinciri = a <= b and b <= c. C#/JS’te bu kısa yazım yok, iki karşılaştırma && ile birleştirilir.

Aralık arama — kod

🎒 found listesi her özyinelemeli çağrıya aynı liste (referans) olarak verilir: hepsi aynı listeye ekler. Sonuçları toplamanın en basit yolu.

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`x.rect`	bu düğümün alt ağacının kapladığı dikdörtgen	düğümle birlikte saklanır
`if (!x.rect.intersects(q)) return`	sorgu bu bölgeye hiç değmiyor	bütün alt ağacı atla: budamanın kendisi
`q.contains(x.p)`	düğümün noktası sorgu kutusunda mı?	yalnızca içerdekiler sonuca eklenir
iki yönde özyineleme	sorgu iki yana da değebilir	BST’deki aralık aramasının iki boyutlu hâli
maliyet	tipik: R + log N	R bulunan nokta sayısı; seçim kutusu küçükse çok hızlı

Quiz 3 · kd-ağaçları

2d-ağacında aralık arama yaparken bir alt ağaç ne zaman budanır?

Bölge kesişmiyorsa içindeki hiçbir nokta sorguda olamaz → güvenle atlarız. C bir tuzak: düğümün kendi noktası dışarıda olabilir ama bölgesi sorguyla kesişiyorsa alt ağaçlarında içeride noktalar olabilir — inmek zorundayız.

LEVEL 3

En yakın komşu

nearest neighbor — “en yakın düşman kim?”

1B aralık arama
doğru parçası kesişimi
kd-ağaçları
en yakın komşu
aralık arama ağaçları
çarpışma: geniş faz

Oyun yapay zekâsının en sık sorusu

🎯 Kule savunması: kule en yakın düşmana ateş eder
⛏️ RTS: işçi en yakın maden / depo
❤️ Bot: canı azsa en yakın sağlık paketi
🧲 Mıknatıs: en yakın altınlar oyuncuya uçar
🤖 Makine öğrenmesi: k-en yakın komşu (kNN) sınıflandırma

Kaba kuvvetHer nokta için mesafe hesapla, en küçüğünü al → N mesafe hesabı. 1.000 kule × 10.000 düşman × 60 FPS = saniyede 600 milyon mesafe hesabı.

⚙️ Küçük hile: karekök almaSadece karşılaştırıyorsak √ gerekmez: dx² + dy² küçükse mesafe de küçüktür. Unity’de Vector3.sqrMagnitude tam bu yüzden var — karekök pahalıdır.

2d-ağacında en yakın komşu

Şimdiye kadarki en iyi aday ve uzaklığı best (başta ∞)
Düğüm x’te: x’in bölgesinin sorguya en kısa uzaklığı ≥ best ise → orada daha yakın nokta olamaz → BUDA ✂️
x’in noktası daha yakınsa → yeni en iyi
Önce sorgunun bulunduğu taraftaki alt ağaca in (orada yakın nokta bulma ihtimali yüksek → best çabuk küçülür → daha çok budama)
Sonra diğer tarafa (muhtemelen budanacak)

🎮 Sezgi“Şu ana kadar bulduğum en yakın düşman 50 metrede. Şu oda bana en az 80 metre uzakta. Odaya bakmama gerek yok!”

En yakın komşu — kendiniz deneyin

Sol tarafta bir yere tıklayın. Mor kesikli çember = şimdiki en iyi uzaklık; çember küçüldükçe daha çok bölge budanır. Sayaçtaki “mesafe hesabı”nı N ile karşılaştırın.

En yakın komşu — kod

🎒 En yakın komşu kodundaki yeni ifadeler

math.hypot · Math.hypot	hipotenüs	`√(dx² + dy²)`: Pisagor. C#’ta `Math.Sqrt(dxdx + dydy)`
rect.distance_to(q)	bölgeye uzaklık	Dikdörtgenin q’ya en yakın noktasına uzaklık; q içerdeyse 0. Hesap: `dx = max(xmin − q.x, 0, q.x − xmax)`, dy benzer, sonra hypot
best = nearest(…, best)	değer taşıma	En iyi aday her çağrıya verilir, (belki güncellenmiş olarak) geri döner. Global değişken gerekmez
a ? b : c	üçlü işleç ternary	“a doğruysa b, değilse c”. Geleneksel hâli: `if (qOnLeft) first = x.Left; else first = x.Right;`
best is None or …	kısa devre	best None ise ikinci kısım (`best.p`) hiç çalışmaz → null hatası olmaz

Ölçüm: kaba kuvvet vs 2d-ağacı

ÖnermeTipik durumda en yakın komşu araması lg N civarında düğüm ziyaret eder. En kötü durumda (çok kötü dağılım) N.

⚙️ Küçük N’de sürprizN = 1.000’de kaba kuvvet ağaçla başa baş (hatta hızlı) olabilir: düz bir dizide art arda gezinmek önbellek dostu ve dallanmasız. Ağaç ancak N büyüyünce açık ara kazanır. Ölçmeden karar verme!

Akrabalar ve tarihçe 📜

1975 · Jon Bentleykd-ağacını “Multidimensional binary search trees used for associative searching” makalesiyle tanıttı. Bentley sonra “Programming Pearls” kitabıyla da ünlendi.

🎮 1993 · DOOM ve BSP ağacıJohn Carmack, DOOM’un seviyelerini BSP ağacı binary space partitioning ile önceden böldü: kd-ağacının kuzeni, ama bölme çizgileri duvarlar boyunca, her yönde olabilir. Oyun, ağacı gezerek duvarları önden arkaya doğru sırada çizebildi — 1993 bilgisayarlarında akıcı 3B!

Quadtree (Ağaçlar sunumu): her düğüm 4’e böler, kd-ağacı 2’ye. Octree: 3B’de 8’e.
Işın izleme ray tracing: sahnedeki üçgenler kd-ağacı ya da BVH’de tutulur — “bu ışın hangi üçgene çarpar?”

🎬 Ara: DOOM’un BSP ağacı

Why Doom is Awesome: Binary Space Partitioning
ShreddedNerd · 26 dk 25 sn · YouTube’da aç

1993’te DOOM, 90’ların sıradan bilgisayarında gerçek zamanlı 3B görüntü üretmek için seviyeyi önceden bir BSP ağacına böldü. Bu sunumdaki “uzayı bölen ağaç” fikrinin oyun tarihindeki en ünlü kullanımı. İlk 12 dakika yeterli.

🤔 İzlerkenVideoda BSP ağacı hangi soruya cevap veriyor: “neyi önce çizeyim?” mi, “nerede çarpıştım?” mı? Ağaç neden oyun başlamadan, editörde kuruluyor? 2d-ağacıyla benzerliği ne, farkı ne?

LEVEL 4

Aralık arama ağaçları

interval search trees — [başlangıç, bitiş] aralıkları

1B aralık arama
doğru parçası kesişimi
kd-ağaçları
en yakın komşu
aralık arama ağaçları
çarpışma: geniş faz

Problem: aralıklar kümesi

Anahtarlar artık aralık: [lo, hi]. İşlemler:

aralık ekle / sil
verilen bir aralıkla kesişen bir aralık bul
kesişen bütün aralıkları bul

🎮 Oyunda aralıklar

Dövüş oyunu: saldırının aktif kareleri (ör. 12–15. kareler). Rakibin kaçınma penceresiyle çakışıyor mu?
Buff / debuff süreleri: “t = 42,5 sn’de hangi etkiler aktif?”
Ritim oyunu: notaların zaman pencereleri
Sunucu: oda / maç rezervasyonları çakışıyor mu?

Fikir: BST + alt ağaçtaki en büyük bitiş

BST’nin anahtarı: aralığın sol ucu (lo)
Her düğüme bir alan daha: max = bu alt ağaçtaki aralıkların en büyük sağ ucu
Eklerken yol üstündeki max’ları güncelle (gerekirse büyüt)
Arama kuralı (kesişen bir aralık):
1. x kesişiyorsa → bulundu ✔
2. sol alt ağaç boşsa → sağa
3. sol alt ağacın max’ı < sorgunun lo’su → sağa
4. yoksa → sola

Neden max?“Solda biten en son aralık bile sorgudan önce bitiyorsa, solda kesişen olamaz.” Tek bir sayıyla koca alt ağacı budadık. Bu tür ek bilgi taşıyan ağaçlara genişletilmiş augmented ağaç denir (BST sunumundaki size gibi).

Aralık arama ağacı — kendiniz deneyin

Üstte zaman çizelgesi, altta ağaç. Düğümün sağ üstündeki küçük sayı = max. Sorguları deneyin: 23 25 (bulunur), 11 13 (yok), 9 9.

Neden “sola gidince sağa bakmaya gerek yok”?

ÖnermeArama sola gittiyse ve solda kesişen aralık yoksa, sağda da yoktur.

Kanıt

Sola gittik → solda max ≥ lo olan bir aralık var: [c, max]
O aralık sorguyla kesişmiyor → tek yol: sorgudan sonra başlıyor: c > hi
Sağ alt ağaçtaki her aralığın sol ucu (BST sırası!) ≥ c > hi
→ sağdakilerin hepsi sorgudan sonra başlıyor → kesişen yok. ∎

Sonuç: arama tek bir yol boyunca iner → dengeli ağaçta lg N. Bütün kesişenleri bulmak: R lg N.

Kesişen bir aralık bul — kod

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`aLo ≤ bHi && bLo ≤ aHi`	iki aralık kesişiyor mu?	kesişmemek için biri öbürünün tamamen solunda olmalı; ikisi de değilse kesişir
`x.left.max`	sol alt ağaçtaki en büyük bitiş	her düğümde saklanır (artırılmış ağaç)
`x.left.max < lo` ise sağa	soldaki her aralık sorgu başlamadan bitiyor	sol alt ağaçta kesişen aralık olamaz
aksi hâlde sola	solda kesişen varsa bulunur	sola inip bulamazsak sağda da yoktur: solda bitişi lo’dan büyük bir aralık var ama sorguyla kesişmiyorsa sorgu bittikten sonra başlıyor demektir; ağaç başlangıca göre sıralı olduğu için sağdakiler ondan da geç başlar, onlar da kesişmez
maliyet	~lg N (dengeli ağaçta)	tek bir kökten yaprağa yol

Quiz 4 · aralık arama ağaçları

[3, 5] ve [5, 9] aralıkları (uçlar dahil) kesişir mi? Peki [3, 5] ve [6, 9]?

Kural: a.lo ≤ b.hi ve b.lo ≤ a.hi. [3,5]–[5,9]: 3 ≤ 9 ✔, 5 ≤ 5 ✔ → kesişir (5. noktada değiyorlar). [3,5]–[6,9]: 6 ≤ 5 ✗ → kesişmez. Dövüş oyununda “değmek” vuruş sayılır mı? Bu bir tasarım kararı: < ile ≤ arasındaki fark!

LEVEL 5

Çarpışma: geniş faz

broad phase — AABB, dikdörtgen kesişimi, sweep and prune

1B aralık arama
doğru parçası kesişimi
kd-ağaçları
en yakın komşu
aralık arama ağaçları
çarpışma: geniş faz

Fizik motorunda çarpışma iki aşamadır

Geniş faz broad phase: her nesneyi saran eksene hizalı kutular (AABB) ile “çarpışıyor olabilecek” çiftleri hızlıca bul
Dar faz narrow phase: sadece bu aday çiftler için gerçek şekillerle (çokgen, kapsül, ağ) pahalı ve kesin test

N nesne → N²/2 çift. 2.000 nesne = 2 milyon çift, her karede! Geniş fazın görevi bunu birkaç yüz adaya indirmek.

🎒 AABB axis-aligned bounding boxNesneyi saran, kenarları eksenlere paralel en küçük kutu. İki AABB çakışır ⇔ x aralıkları kesişir ve y aralıkları kesişir. Yani: iki tane 1B aralık testi! (2d-ağacındaki intersects ile aynı.)

Dikdörtgen kesişimi: süpürme + aralık ağacı

Çözüm: Level 1’deki süpürme doğrusunun aynısı!

Olaylar: dikdörtgenlerin sol ve sağ kenarlarının x’leri (sıralı)
Sol kenar → önce dikdörtgenin y aralığıyla kesişenleri aralık arama ağacında ara, sonra y aralığını ağaca ekle
Sağ kenar → y aralığını ağaçtan sil

ÖnermeN dikdörtgenin R kesişen çiftini bulmak: N lg N + R lg N.

Oyunların favorisi: sweep and prune (SAP)

Kutuları sol kenarlarına (xmin) göre sırala
Soldan sağa süpür, bir aktif liste tut: x aralığı hâlâ süren kutular
Yeni kutu gelince: sağ kenarı geride kalanları aktif listeden at (prune), kalanlarla y testi yap

🎮 Gizli silah: kare tutarlılığıNesneler bir karede çok az hareket eder temporal coherence. Önceki karenin sırası neredeyse sıralı → insertion sort neredeyse doğrusal çalışır! (Temel Sıralama sunumundaki “neredeyse sıralı girdi” sorusunun cevabı buydu.)

Sweep and prune — canlı

Kutu sayısını artırın, yöntemi değiştirin: “çift testi” sayacı kaba kuvvette N²/2, SAP’ta çok daha az. Altta x eksenine izdüşümler. “insertion sort kaydırma” her karede ne kadar küçük?

Gerçek motorlar ne kullanıyor?

Unity 3B (PhysX): Project Settings → Physics → Broadphase Type: Sweep and Prune, Multibox Pruning, Automatic Box Pruning
Unity 2B ve birçok 2B oyun (Box2D): dinamik AABB ağacı — kutuların kutularından oluşan, dengelenen bir ikili ağaç
Bullet (Blender, birçok oyun): btAxisSweep3 (SAP) ya da dinamik AABB ağacı
Godot, Unreal (Chaos): AABB ağaçları ve ızgaralar

⚙️ Neden tek bir “en iyi” yok?

Nesneler hareketli mi, statik mi?
Boyutları benzer mi (ızgara iyi) yoksa çok farklı mı (ağaç iyi)?
Hep aynı eksende mi kümeleniyorlar (SAP kötüleşir: hepsi aynı x’te!)

Bu yüzden motorlar seçenek sunar; profil çıkarıp ölçmek gerekir (Analiz sunumu!).

Quiz 5 · çarpışma

Sweep and prune, kutuları her karede sıralarken neden insertion sort kullanmayı tercih eder?

Insertion sort’un maliyeti ~ N + (ters sıralı çift sayısı). Bir karede sadece birkaç kutu birbirinin önüne geçer → çok az takas. Quicksort ya da mergesort her karede baştan N lg N öderdi. Doğru algoritma = verinin özelliğine uygun algoritma.

🧪 Kod laboratuvarı: iki aralık kesişiyor mu?

Verilen kod yanlış. Önce çalıştırıp hangi testte patladığına bakın. Sonra doğru kuralı yazın. Bonus: aynı şeyi “kesişmeme” koşulunun tersi olarak !(a[1] < b[0] || b[1] < a[0]) biçiminde yazın — ikisi neden aynı? (De Morgan)

🐍 Kod laboratuvarı — AABB çakışması (Python)

İki hata var: y_ok eksik ve son satırdaki mantık işleci yanlış. (İpucu: iki kutu ancak her iki eksende de üst üste biniyorsa çakışır.) Unity’deki Bounds.Intersects ve p5.js çarpışma kütüphaneleri tam olarak bunu yapar.

Derin hikâye: Barnes–Hut ve galaksileri hesaplamak (1986)

N cisimli bir kütle çekim simülasyonunda (yıldızlar, galaksiler) her cisim diğer hepsini çeker: N² kuvvet hesabı. Bir milyon yıldız için her adımda bir trilyon hesap.
Josh Barnes ve Piet Hut’un 1986’da Nature’da yayımladığı fikir: uzayı bir sekizli ağaçla (2B’de dörtlü ağaç) böl. Uzaktaki bir grup yıldızı, kütle merkezinde duran tek bir kütle gibi düşün. Bir düğüm “yeterince uzak” mı? (Düğümün boyutu / uzaklık < θ.) Uzaksa tek hesap, değilse çocuklarına in.
Sonuç: N² yerine yaklaşık N log N; astrofizikteki büyük simülasyonların temel yöntemlerinden biri oldu.

DersGeometrik ağaçların sırrı: uzaktaki ayrıntıyı özetlemek. Oyunlardaki ayrıntı düzeyi (LOD, Y18), çarpışma için geniş faz, “yakınımdaki düşmanlar” sorguları ve dörtlü ağaçlı haritalar aynı düşünceye dayanır.

Kaynak: Barnes & Hut 1986, Nature · Wikipedia: Barnes–Hut simulation

🧰 Kütüphaneler ve araçlar

ad	platform	ne yapar / sınırları	nasıl eklenir
scipy.spatial.KDTree	Python	k-d ağacı: en yakın k komşu, yarıçap sorguları; C ile hızlı.	`pip install scipy`
scikit-learn NearestNeighbors	Python	KDTree/BallTree arasında otomatik seçim; çok boyutlu veri.	`pip install scikit-learn`
Physics.OverlapSphereNonAlloc · Physics2D	Unity	Fizik motorunun kendi geniş faz yapısıyla yarıçap/kutu sorguları; NonAlloc ile çöp yok.	yerleşik
kdbush · rbush	JavaScript	Statik noktalar için çok hızlı k-d ağacı; dikdörtgenler için R-ağacı (Mapbox).	`npm install kdbush rbush`
nanoflann	C++	Başlık dosyasından ibaret hızlı k-d ağacı.	GitHub

🧩 Oyunlarda geometrik arama

En yakın düşman / hedef: k-d ağacı ya da ızgara. Hareketli nesneler için her kare ağacı baştan kurmak pahalıysa ızgara (uzaysal hash) çoğu zaman daha basit ve hızlı.
Alan etkili büyüler: yarıçap içindekiler (OverlapSphere).
Geniş faz çarpışma: fizik motorları bunu sizin yerinize yapar; kendi sisteminizde dörtlü ağaç/ızgara.
Statik harita nesneleri (ağaçlar, binalar, toplanabilirler): bir kez kurulan k-d ağacı ya da R-ağacı.

Sık hatalar

Ağacı her karede sıfırdan kurmak.
Mesafeyi karşılaştırırken karekök almak (kare mesafe yeter).
Dörtlü ağaçta sınıra denk gelen nesneleri sadece bir düğüme koymak.
Unity’de her kare OverlapSphere (çöp): NonAlloc sürümü.

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin

Her kare ağacı yeniden kurmak
Gereksiz karekök
Sınırdaki nesneleri kaybetmek
Her kare çöp üreten sorgular

İyi bir istek (prompt) örneği

“Unity 6, C#. 2B bir dörtlü ağaç yaz: QuadTree(Rect sınırlar, int kapasite, int maksDerinlik); Insert(T, Vector2), Query(Rect, List sonuç), QueryRadius(Vector2, float, List) — kare mesafe; Clear() ve yeniden kullanılabilir düğüm havuzu (çöp yok). 5.000 hareketli birimle her kare yeniden kurma ve uzaysal hash ızgarasıyla karşılaştırmalı ölçüm yapan bir test sahnesi ve doğruluk testleri ekle.”

Nesneler hareketli mi statik mi yazın
Kare mesafe kullanımını isteyin
Izgara ile karşılaştırma ölçümü isteyin
NonAlloc ya da dışarıdan verilen sonuç listesi isteyin

🚀 Proje ve araştırma önerileri

[kolay] Barnes–Hut 2B — p5.js’te 2.000 cisimli galaksi; θ’yı değiştirip doğruluk/hız dengesini gösterin.
[orta] En yakın düşman — k-d ağacı, dörtlü ağaç ve ızgarayı 5.000 hareketli birimle ölçün.
[orta] Alan etkili büyü — Unity’de OverlapSphereNonAlloc ile çöp üretmeyen AOE sistemi.
[araştırma] R-ağacı — Harita nesnelerini (dikdörtgenler) R-ağacına koyup görünür alan sorgularını ölçün.

📄 Akademik okumalar ve kaynaklar

Bentley 1975 · Multidimensional Binary Search Trees Used for Associative Searching (Communications of the ACM 18(9))
k-d ağaçları.

Finkel & Bentley 1974 · Quad Trees: A Data Structure for Retrieval on Composite Keys (Acta Informatica 4)
Dörtlü ağaçlar.

Barnes & Hut 1986 · A Hierarchical O(N log N) Force-Calculation Algorithm (Nature 324)
Barnes–Hut.

Guttman 1984 · R-Trees: A Dynamic Index Structure for Spatial Searching (SIGMOD 1984)
R-ağaçları.

Neler öğrendik? 🎒

problem	çözüm	tipik süre	🎮 oyunda
1B aralık arama	BST (rank, range)	R + lg N	kamera penceresi, MMR aralığı
dik doğru parçası kesişimi	süpürme + BST	N lg N + R	Tron izleri, duvarlar
2B aralık arama	2d-ağacı	R + lg N	seçim kutusu, mini harita
en yakın komşu	2d-ağacı + budama	lg N	en yakın düşman / kaynak
1B aralık kesişimi	aralık arama ağacı	R lg N	vuruş pencereleri, buff’lar
dikdörtgen kesişimi	süpürme + aralık ağacı / SAP	N lg N + R lg N	fizik motoru geniş faz

Ortak fikir: budama — cevabı içeremeyecek bölgeye hiç bakma. Ve süpürme — 2B problemi bir dizi 1B probleme çevir.

Alıştırmalar 🏋️

Kâğıt-kalem: (0.7, 0.2), (0.5, 0.4), (0.2, 0.3), (0.4, 0.7), (0.9, 0.6) noktalarını sırayla bir 2d-ağacına ekleyin; bölmeleri çizin.
p5.js’te 2.000 rastgele “düşman” ve fareyi izleyen bir “kule” yapın. En yakın düşmanı önce kaba kuvvetle, sonra 2d-ağacıyla bulun; FPS’i karşılaştırın.
RTS seçim kutusunu 2d-ağacıyla yazın. Birimler hareket ediyorsa ağacı ne sıklıkla yeniden kurmalısınız?
Aralık arama ağacına “bütün kesişenleri bul” işlemini ekleyin (ipucu: her iki alt ağaca da gerektiğinde inen özyineleme).
SAP demosunda bütün kutuları aynı dikey şeritte toplayın (hepsi aynı x’te). Ne oluyor? Neden?
🤖 Bir YZ asistanına “Unity’de 5.000 birim için en yakın düşmanı verimli bul” deyin. Hangi yapıyı önerdi (ızgara, kd-ağacı, Physics.OverlapSphere)? Neden?

🎮 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ı.

📖 Fandom wikisi · ▶ video 1:00

Kaynaklar: videolar 🎬

K-d Trees
Computerphile

KD-Tree Nearest Neighbor Data Structure
Stable Sort

Coding Challenge #98.1: Quadtree
The Coding Train (p5.js!)

Why Doom is Awesome: Binary Space Partitioning
ShreddedNerd

Doom’un Gizli Ağacı (Türkçe)
Sezai Kumru

Sweep-Line Algorithm for Line Segment Intersection
Philipp Kindermann

Sweep And Prune
Dennis Morgovan

Augmented Data Structures: Interval Trees
Jaya Krishna

Kaynaklar: okuma 📚

NEXT LEVEL ▶

Öncelik Kuyrukları

İkili yığın, heapsort, olay zamanlayıcıları — ve A*’ın açık listesi

SONRAKİ SUNUM ▶