Çarpışma Tespiti

OYUN GEOMETRİSİ VE FİZİĞİ · G3

Çarpışma Tespiti

Daire, kutu, ayıran eksen teoremi, ışın, hitbox — “değdi mi?” sorusuna kesin cevap ve sonrasında ne yapılacağı

PRESS ▶ TO START

Bu derste oyunun haritası 🗺️

Çarpışma şekilleri ve hitbox — gördüğünüz model ile çarpışan şekil aynı değildir; Rocket League’in altı kutusu
Temel testler — daire–daire, kutu–kutu, daire–kutu; Quake’in şişirilmiş haritaları
Ayıran eksen teoremi (SAT) — dışbükey çokgenler; gölgeler ve en kısa çıkış; Box2D
Tespit yetmez: çözüm — eksen eksen hareket, kayma, sekme; Celeste’in piksel piksel yöntemi; tünelleme
Işınlar — ışın–daire; hitscan mermi, görüş hattı, fare
Her adımda — elle hesap → canlı demo → kod (JavaScript / Python / C#) → oyunlardaki karşılığı

🎮 Bu dersin sonunda…

bir oyunun çarpışmalarının neden “haksız” ya da “cömert” hissettirdiğini açıklayabilecek; daire, kutu ve dışbükey çokgenler için çarpışma testlerini yazabilecek; çakışan iki şekli en kısa yoldan ayırabilecek ve duvarların içinden geçmeyen bir platform karakteri kodlayabileceksiniz.

🤔 ISINMA: “VURMADI Kİ!”

Bir dövüş oyununda yumruğunuz rakibin burnunun dibinden geçti, ekranda değdiğini gördünüz ama oyun saymadı. Ya da tam tersi: mermi yanınızdan geçti, yine de öldünüz. Neden?

Çünkü oyun, ekranda gördüğünüz çizimleri çarpıştırmaz. Onların yerine geçen görünmez, basit şekilleri çarpıştırır: hitbox.
Bir karakter modeli on binlerce üçgendir; saniyede 60 kez, onlarca nesneyle kesin test edilemez. Bir kutu ya da kapsül ise birkaç karşılaştırma.
Hitbox’ın modelden büyük ya da küçük olması bir tasarım kararıdır: zorluk ve adalet hissi buradan ayarlanır.
Bu sunumun iki sorusu: değdi mi? (tespit) ve değdiyse ne olacak? (çözüm).

🎯 Bu konu için bilmeniz gerekenler

Yeşil = gerekli · kesikli = faydalı ama şart değil. Tıklayınca ilgili sunuma gider.

G1 · Geometri Temelleri G2 · Uzaysal Bölümleme (geniş aşama)Y0 · Hazırlık (nokta çarpım, izdüşüm)

BST’nin Geometrik Uygulamaları (sweep and prune)Y17 · Zorluk (oyuncuya cömert davranmak)

Neden?G2 adayları buldu: “bu ikisi çakışıyor olabilir”. Bu sunum kesin cevabı veriyor (dar aşama). Ayıran eksen teoremi tek bir araca dayanır: Y0’daki nokta çarpım (bir noktanın bir eksen üzerindeki gölgesi).

🧰 Kodlamadan korkuyorsanızDaire ve kutu testleri birkaç satır ve çoğu 2B oyun için yeter. SAT’ı bilmek, motorun içinde ne olduğunu anlamanızı sağlar; kendiniz yazmak zorunda değilsiniz.

Mini sözlük

hitbox · hurtbox	vuruş kutusu · hasar kutusu	Saldırının çarpışan şekli · karakterin hasar alabilen şekli
collider · collision shape	çarpıştırıcı · çarpışma şekli	Modelin yerine çarpıştırılan basit şekil
AABB · OBB	eksen hizalı kutu · yönlü kutu	Kenarları eksenlere paralel kutu · döndürülebilen kutu
capsule	kapsül	İki ucu yuvarlak silindir: karakterlerin standart şekli
SAT (separating axis theorem)	ayıran eksen teoremi	İki dışbükey şekil, gölgelerinin ayrıldığı bir eksen varsa çakışmaz
projection	izdüşüm (gölge)	Şeklin bir eksen üzerine düşen aralığı: nokta çarpımların en küçüğü ve en büyüğü
MTV (minimum translation vector) · penetration	en kısa itme vektörü · iç içe geçme	Şekilleri ayıran en kısa hareket · ne kadar gömüldükleri
collision response · resolution	çarpışma tepkisi · çözüm	Çakışma bulununca yapılan: ayırma, sektirme, kaydırma
raycast · hitscan	ışın gönderme · anında isabet	Bir ışının ilk çarptığı şeyi bulmak · mermiyi ışın olarak hesaplamak
CCD (continuous collision detection)	sürekli çarpışma tespiti	Kareler arasındaki yolu da sınayarak tünellemeyi önlemek

LEVEL 0

Çarpışma şekilleri ve hitbox

gördüğün ile çarpışan aynı değil

Altı çarpışma şekli, tek bakışta

Oyun nesnenin görünen şekliyle değil, onu saran basit bir çarpışma şekliyle (kesikli mavi) çarpıştırır. Soldan sağa: test ucuzdan pahalıya, şekil kabadan inceye gider. Sonraki tablo aynı altı şeklin ne zaman seçileceğini söyler.

Hangi şekil, ne zaman?

şekil	test maliyeti	iyi olduğu yer	zayıf yanı
Daire / küre	en ucuz: bir kare uzaklık	mermiler, toplar, patlama yarıçapı; dönse de değişmez	uzun, ince nesnelere uymaz
AABB (eksen hizalı kutu)	dört karşılaştırma	karolar, platformlar, arayüz, geniş aşama (G2)	dönen nesnede kutu büyür, boşluk artar
Kapsül	parça–nokta uzaklığı	ayakta duran karakterler: basamak ve köşede takılmadan kayar	köşeli nesnelere uymaz
OBB (yönlü kutu)	SAT, 4 eksen	araçlar, kasalar, dönen platformlar	AABB’den pahalı
Dışbükey çokgen	SAT ya da GJK	fizik nesneleri (çoğu zaman modelin dışbükey zarfı, G1)	içbükey olamaz
Üçgen ağı (mesh)	pahalı; BVH şart (G2)	durağan dünya: arazi, bina	hareketli nesnede kullanılmaz

Kural: işinizi gören en basit şekli seçin. İçbükey nesne (L, U, halka) birkaç dışbükey parçanın birleşimi olarak kurulur. Karmaşık karakterde tek şekil yerine birkaç kutu/kapsül: baş, gövde, kollar (kafadan vuruş hasarı).

Çizimle: vuran kutu, vurulan kutu

Dövüş oyununda “yumruk değdi mi?” diye bakılmaz; kırmızı kutu mavi kutuya değdi mi? diye bakılır. Kutuları tasarımcı elle çizer: yumruktan uzun bir vuruş kutusu ya da gemiden çok küçük bir hasar noktası bilinçli seçimlerdir.

Gerçek örnekler: kutular görünür yapılınca

Tek kutu ve parça parça kutular — **Tek kutu mu, parça parça mı?** Solda karakterin tamamını saran tek kutu: kolun altındaki boşluktan geçen mermi de “vurdu” sayılır. Sağda baş, gövde, kollar ve bacaklar ayrı kutu: boşluk azalır ve **kafadan vuruş** ayrı puanlanabilir.
Görsel: Sigfried Arnold (Suit), Wikimedia Commons, CC BY-SA 3.0

Dövüş oyununda saldıran karakterin kutuları — **Dövüş oyunu, saldırı karesi.** Yeşil: karakterin başkalarıyla çarpışan gövde kutusu. Sarı/mavi: vurulabildiği yerler (hurtbox). Kırmızı: saldırının vurduğu yer (hitbox); yumruğun ucunda.
Görsel: Ftiercel, Dabmasterars, Wikimedia Commons, CC BY 3.0

Tremulous oyununda hitbox — **Gerçek bir oyundan:** açık kaynaklı nişancı oyunu Tremulous’ta iki modelin kırmızı tel kutuları. Kıvrık yaratık, şekline hiç benzemeyen düz bir **kutuyla** çarpışıyor.
Görsel: Tremulous geliştiricileri, Wikimedia Commons, GPL

Oyun içinde bu kutular görünmez; geliştiriciler onları hata ayıklama görünümünde açar. Sonraki slayttaki iki video, ticari oyunlarda aynı görünümü gösteriyor.

🎬 Oyunların içinden: kutuları açınca ne görünür?

Street Fighter IV, kutu görüntüleyici (Lullius, 49 sn). Gerçek maçta her karede değişen kutular: vuruş kutuları saldırı anında beliriyor, vurulma kutuları animasyonla birlikte kayıyor. YouTube’da aç

How Games Fake Melee Attacks to Make Combat Feel Great (GDQuest, 2 dk). Kılıç darbesinin kutusu neden kılıçtan büyük çizilir; “cömert” kutunun oyun hissine etkisi. YouTube’da aç

🤔 İzlerkenStreet Fighter’da vuruş kutusu, karakterin çizilmiş kolundan ya da bacağından uzun mu, kısa mı? İkinci videoya göre kutuyu çizimden büyük yapmak oyuncuya ne hissettirir; küçük yapmak ne hissettirir? Daha fazlası: How Hitboxes Work in Video Games (Inside Gaming, 4 dk) · Super Street Fighter 2 Hitboxes (Xenozip, 3 dk) · Hitboxes and Hurtboxes in Godot (GDQuest, 15 dk).

Oyunlarda: hitbox bir tasarım kararıdır

🥊 Dövüş oyunları: kare kare kutular

Her saldırı karesinde iki tür kutu: hitbox (saldırının vurduğu yer) ve hurtbox (karakterin vurulabildiği yer). Vuruş = bir hitbox, rakibin hurtbox’ına değdi.
Kutular animasyonla birlikte kare kare elle çizilir. Bir yumruğun kutusu kolun ucundan uzun olabilir; tekme sırasında bacağın hurtbox’ı kaybolabilir (o saldırı “bacağı vurulamaz” olur).
Denge ayarı çoğu zaman çizime dokunmadan, yalnızca kutuyu birkaç piksel büyütüp küçülterek yapılır. Oyuncular bu “kare verisini” (frame data) ezberler.

🎯 Mermi cehennemi: birkaç pikselBu türde oyuncunun hasar kutusu geminin ortasında birkaç piksellik bir noktadır: mermi kanadınızdan geçer, ölmezsiniz. Yüzlerce mermi arasından sıyrılma hissi bu cömert kutudan gelir (Y17).

🚗 Rocket League: yüzlerce araba, altı kutu

Oyunda yüzlerce farklı araba gövdesi var, ama çarpışmada yalnızca altı standart kutudan biri kullanılır (Octane, Dominus, Plank, Breakout, Hybrid, Merc).
Yeni bir araba eklenince bu altı kutudan birine atanır. Böylece görünüş satılabilir ama avantaj satılamaz; rekabet adil kalır.
Bedeli: bazı arabaların burnu kutusundan taşar ya da kutu arabadan taşar; oyuncular “hangi araba kutusuna en iyi oturuyor” diye tartışır.

🔫 Counter-Strike: kutudan kapsüleCS:GO’nun 2015 güncellemesi karakterlerin vuruş şekillerini kutulardan kapsüllere çevirdi: eklemlere daha iyi oturan, koşarken ve zıplarken modelden daha az taşan şekiller. “Vurdum ama saymadı” şikâyetlerinin bir kısmı şekil seçimiyle çözüldü.

Hata ayıklama görünümü (Y19): kutuları ekranda çizdirmeden hitbox ayarlanmaz. Unity: Gizmos; Unreal: show collision.

LEVEL 1

Temel testler

daire, kutu ve ikisi birlikte

Çizimle: daire–daire

Kalın çizgiler iki yarıçaptır, merkezleri birleştiren doğrunun üzerine konmuş. Aralarında boşluk kalıyorsa daireler ayrı; üst üste biniyorsa çakışıyor. “Merkezler arası uzaklık, yarıçapların toplamından küçük mü?” sorusu budur. Üç çizim, sonraki slayttaki tablonun üç satırıdır.

Daire–daire: merkezler ne kadar yakın?

İki daire, merkezleri arasındaki uzaklık yarıçapların toplamından küçükse çakışır.
Uzaklık için karekök gerekir; ama karşılaştırma için gerekmez: iki tarafın karesini al.

$$d_x^2 + d_y^2 \;<\; (r_1 + r_2)^2$$

Elle hesap

A (x, y, r)	B (x, y, r)	dx² + dy²	(r₁ + r₂)²	sonuç
(2, 3, 1,5)	(5, 7, 3)	9 + 16 = 25	4,5² = 20,25	çakışmıyor
(2, 3, 1,5)	(5, 7, 4)	25	5,5² = 30,25	çakışıyor
(0, 0, 5)	(10, 0, 5)	100	100	yalnızca değiyor

“Değme” (eşitlik) çakışma sayılsın mı? < ile <= arasındaki fark; tutarlı olun.

🎮 Nerede?

Mermi–düşman (mermi cehennemi oyunlarında her şey dairedir)
Patlama yarıçapı, toplama mıknatısı, “yakınımda mı?”
Sürüde ayrılma kuralı (Y7)
3B’de küre–küre: aynı formül, bir terim fazla (d_z²)

Neden kareler?sqrt bölmeden bile pahalıdır ve burada tamamen gereksiz: iki pozitif sayının sırası, karelerinin sırasıyla aynıdır. Unity’de sqrMagnitude, Unreal’da SizeSquared bu yüzden var (Y0).

Çizimle: kutu–kutu

Her kutunun x eksenine ve y eksenine düşen “gölgesine” bakın. Kutular ancak iki gölge çifti de örtüşüyorsa çakışır; tek bir eksende ayrılmaları yeter.

Kutu–kutu: iki eksende de örtüşmeli

Eksen hizalı iki kutu (AABB). Her kutu x’te bir aralık, y’de bir aralık kaplar.
İki aralık ne zaman örtüşür? a.sol < b.sağ ve b.sol < a.sağ. (Tersi: biri öbürünün tamamen solunda ya da sağında.)
Kutular çakışır ⇔ x aralıkları örtüşür ve y aralıkları örtüşür.
Tek bir eksende ayrıklarsa ayrıktırlar: ilk “hayır”da çıkın (çoğu çift ilk karşılaştırmada elenir).

Elle hesap

	x aralıkları	y aralıkları	sonuç
A [0–10] × [0–6], B [8–14] × [5–9]	8 < 10 ✔	5 < 6 ✔	çakışıyor
A aynı, B [8–14] × [7–9]	8 < 10 ✔	7 < 6 ✘	çakışmıyor
A aynı, B [12–14] × [1–3]	12 < 10 ✘	—	çakışmıyor

🎮 Nerede?

Karo tabanlı her oyun: karakter kutusu ile duvar karoları
Arayüz: fare bu düğmenin üstünde mi (nokta–kutu)?
Geniş aşamanın her yerinde: BVH düğümleri, sweep and prune (G2)
Kamera: nesnenin kutusu ekran kutusuyla örtüşüyor mu? (çizmeye değer mi?)

İpucu: SAT’ın ilk hâlix ve y eksenlerindeki “gölgelere” bakıyoruz ve bir eksende boşluk bulursak “ayrık” diyoruz. Level 2’deki ayıran eksen teoremi bu fikri her yöne genelleştirecek.

Çizimle: daire–kutu

Kural: kutunun daire merkezine en yakın noktasını bul; o nokta merkeze yarıçaptan yakınsa çakışıyorlar. Dört daire, sonraki slayttaki tablonun dört satırıdır.

Daire–kutu: kutunun en yakın noktası

Kutunun, dairenin merkezine en yakın noktasını bul. O nokta dairenin içindeyse çakışıyorlar.
En yakın nokta nasıl bulunur? Merkezin x’ini kutunun [sol, sağ] aralığına, y’sini [üst, alt] aralığına kıstır (clamp). Her eksen ayrı ayrı.
Merkez kutunun solundaysa en yakın nokta sol kenarda; çaprazındaysa köşede; içindeyse kendisi (uzaklık 0).

Elle hesap: kutu x 0–100, y 0–60 · r = 10

merkez	kıstırılmış nokta	uzaklık	sonuç
(120, 30)	(100, 30)	20	çakışmıyor
(105, 30)	(100, 30)	5	çakışıyor
(120, 80)	(100, 60) köşe	√800 ≈ 28,3	çakışmıyor
(108, 68)	(100, 60) köşe	√128 ≈ 11,3	çakışmıyor (!)

Yaygın kestirme ve hatası

“Kutuyu her yönde r kadar büyüt; merkez büyük kutunun içinde mi diye bak.”

Kenarlarda doğru, köşelerde yanlış. Son satır: (108, 68), büyütülmüş kutunun (−10…110, −10…70) içinde → “çakışıyor” der. Gerçek uzaklık 11,3 > 10: değmiyor.

Büyütülmüş kutunun köşesi sivri; oysa kutudan r uzaklıktaki noktaların sınırı köşede yuvarlaktır.

🎮 Nerede?Top–tuğla (Breakout), top–raket, yuvarlak karakter–karo duvar, daire biçimli patlama–kutu biçimli bina. Kıstırma aynı zamanda çarpma noktasını ve oradan çarpma yönünü (normal) verir.

Canlı: üç temel test 🔵⬛

Ekranı okuyun: soldaki şekil fareyi izler, sağdaki sabit. Çakışınca ikisi de kırmızıya döner; sağ üstte sonuç yazar. Üstteki menüden testi seçin.
daire – daire: mor çizgi merkezler arası uzaklık. Alttaki sayıları okuyun: kare uzaklık ile yarıçaplar toplamının karesi karşılaştırılıyor.
kutu – kutu: altta ve solda iki kutunun eksenlerdeki gölgeleri (mavi, sarı çubuklar). Kutuyu yalnızca x’te örtüşecek ama y’de ayrık kalacak biçimde tutun: çakışma yok.
daire – kutu: mor nokta kutunun daireye en yakın noktası. Daireyi kutunun kenarı boyunca kaydırın: nokta kenar üzerinde kayar, köşeye gelince köşede takılır.
Daireyi köşenin çaprazında, kenar hizalarının hemen dışında tutun: kutunun “büyütülmüş” hâline girmiş olurdu ama gerçekte değmiyor.

🔎 DEMODA DENEYİN

Ekranı okuyun: soldaki şekil fareyi izler, sağdaki sabit. Çakışınca ikisi de kırmızıya döner; sağ üstte sonuç yazar. Üstteki menüden testi seçin.
daire – daire: mor çizgi merkezler arası uzaklık. Alttaki sayıları okuyun: kare uzaklık ile yarıçaplar toplamının karesi karşılaştırılıyor.
kutu – kutu: altta ve solda iki kutunun eksenlerdeki gölgeleri (mavi, sarı çubuklar). Kutuyu yalnızca x’te örtüşecek ama y’de ayrık kalacak biçimde tutun: çakışma yok.
daire – kutu: mor nokta kutunun daireye en yakın noktası. Daireyi kutunun kenarı boyunca kaydırın: nokta kenar üzerinde kayar, köşeye gelince köşede takılır.
Daireyi köşenin çaprazında, kenar hizalarının hemen dışında tutun: kutunun “büyütülmüş” hâline girmiş olurdu ama gerçekte değmiyor.

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

🔗 Collision Detection

Jeffrey Thompson

Nokta, daire, dikdörtgen, çizgi ve çokgen çarpışmalarının p5.js ile adım adım anlatımı.

📘 Spatial Partition

Game Programming Patterns (Robert Nystrom)

Izgara, quadtree ve BSP ile “yakınımdaki nesneler” sorusunu hızlandırmak.

🔗 cp-algorithms

cp-algorithms.com

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

Kod: üç temel test

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`dx * dx + dy * dy < rr * rr`	kare uzaklık, kare yarıçap toplamı	Karekök yok. `**` yerine çarpma: en hızlısı.
`a.x < b.x + b.w && b.x < a.x + a.w`	x aralıkları örtüşüyor	“a’nın solu b’nin sağından önce ve b’nin solu a’nın sağından önce.” `&&` kısa devre: ilk yanlışta gerisi hesaplanmaz.
`constrain(v, lo, hi)` · `max(lo, min(hi, v))`	v’yi [lo, hi] aralığına kıstır	p5.js’te `constrain`, Unity’de `Mathf.Clamp`, Python’da elle.
`box.ClosestPoint(c)`	kutunun c’ye en yakın noktası	Unity’nin hazır kıstırması; her collider türünde var.
`(a - b).sqrMagnitude`	kare uzaklık	`Vector2.Distance` karekök alır; karşılaştırmada bunu kullanın.

ÖnermeÜç test de sabit zamanlıdır: şeklin büyüklüğünden bağımsız birkaç çarpma ve karşılaştırma. Bu yüzden karmaşık modeller yerine bu şekiller çarpıştırılır.

🌱 Isınma kodu: iki daire çakışıyor mu?

Başlangıç kodu yalnızca a’nın yarıçapına bakıyor. Düzelttikten sonra bir adım daha: Math.sqrt’u kaldırıp iki tarafın karesini karşılaştırın: dx*dx + dy*dy < (a[2] + b[2]) ** 2. Elle hesap tablosundaki üç satır testlerde.

🌱 Isınma kodu: kutunun en yakın noktası

“Kıstırma” (clamp): bir sayıyı iki sınırın arasına çekmek. Her eksen için ayrı ayrı: Math.min(Math.max(p[0], sol), sağ). Başlangıç kodu yalnızca sol ve üst kenarı uyguluyor; kutunun sağındaki ya da altındaki noktalar için yanlış. Bir sonraki laboratuvarın (daire–kutu) yarısı bu fonksiyon.

🧪 Canlı laboratuvar: daire kutuya değiyor mu?

Başlangıç kodu yaygın kestirmeyi kullanıyor: kenarlarda doğru, köşelerde yanlış. Sağda daire kutuların arasında dolaşırken köşelerin çaprazından geçtiği anlarda kalın sarı çerçeveyle “YANLIŞ” yazısını göreceksiniz. Doğrusu: px = min(max(c[0], sol), sağ), py aynı şekilde; sonra (px − c[0])² + (py − c[1])² < r².

Oyunlarda: Quake “büyütme” hilesini nasıl doğru yaptı? (1996)

Quake’te oyuncu bir kutudur (32 × 32 × 56 birim). Kutuyu haritanın binlerce yüzeyiyle çarpıştırmak 1996’da pahalıydı.
Hile: oyuncuyu noktaya indir, haritayı oyuncunun kutusu kadar şişir. “Kutu duvara değiyor mu?” sorusu “nokta, şişirilmiş duvarın içinde mi?” sorusuna dönüşür: çok daha ucuz.
Şişirme harita derlenirken bir kez yapılır ve dosyaya üç ayrı çarpışma haritası (“hull”) yazılır: nokta için, oyuncu boyu için, iri canavarlar için.
Kodda görüyorsunuz: hareket eden şeyin enine bakılır (size[0]) ve uygun harita seçilir.
Bedeli: yalnızca üç boy var. Quake’te her yaratığın çarpışma kutusu bu üçünden biridir; modeli ne olursa olsun.

Az önceki “kutuyu büyüt” kestirmesinin köşe hatası burada yok, çünkü büyütülen şekil de büyüten şekil de kutu (kutu ⊕ kutu = kutu). Aynı fikir Y9’da: navmesh, ajanın yarıçapı kadar içeri çekilerek pişirilir ki ajan nokta gibi yürüyebilsin. Matematikteki adı Minkowski toplamı.

Quiz 1 · temel testler

Yarıçapı 10 olan bir top (120, 80) noktasında. Kutu x: 0–100, y: 0–60 aralığını kaplıyor. Kutunun topa en yakın noktası hangisi ve çakışıyorlar mı?

Kıstırma: x = 120 → 100’e, y = 80 → 60’a çekilir. En yakın nokta kutunun köşesi (100, 60). Uzaklık √(20² + 20²) ≈ 28,3 > 10: çakışmıyor. (Elle hesap tablosunun üçüncü satırı.)

LEVEL 2

Ayıran eksen teoremi

gölgeler ayrılıyorsa şekiller ayrıdır

Çizimle: dönen şekillerde neden yeni bir fikir gerek?

Soldaki sorun bizi sağdaki fikre götürür: iki dışbükey şeklin arasına bir cetvel sığıyorsa, cetvele dik bir eksendeki gölgeleri birbirinden ayrıdır. Ayıran eksen teoremi bunu tersinden kullanır: gölgelerin ayrıldığı tek bir eksen bulursan şekiller çakışmıyor.

Problem: dönen kutular ve çokgenler

Araba 30° döndü. Artık kenarları eksenlere paralel değil: AABB testi çalışmaz.
Sınırlayıcı AABB’sini kullanırsak (dönmüş kutuyu saran büyük kutu): köşelerde büyük boşluklar; araba duvara değmeden “çarptı” sayılır.
Gemiler, kayalar, eğimli platformlar: genel dışbükey çokgenler.

İlk akla gelen: kenarları tek tek kesiştir

A’nın her kenarını B’nin her kenarıyla kesiştir (G1). n × m kesişim testi.

Biri öbürünün tamamen içindeyse hiçbir kenar kesişmez: kaçırır. Ek olarak “nokta içinde mi” testi gerekir.
Çakışıyorlarsa ne kadar ve hangi yöne itmeli? Kesişim noktaları bunu söylemez.

Fikir: araya bir cetvel sığar mı?

İki dışbükey şekil çakışmıyorsa aralarından bir doğru geçirebilirsiniz.
O doğruya dik bir eksen düşünün. İki şekli o eksene izdüşürün (üstten ışık tutup gölgelerine bakın): gölgeler ayrıktır.
Tersinden: gölgelerin ayrıldığı tek bir eksen bulursanız şekiller kesinlikle çakışmıyor.
Hiçbir eksende gölgeler ayrılmıyorsa çakışıyorlar.

Hangi eksenlere bakmalı?Sonsuz eksen var; ama yalnızca kenarların dikmelerine bakmak yeter. Üçgen + dörtgen = en çok 7 eksen; iki kutu (OBB) = 4 eksen (karşılıklı kenarlar aynı ekseni verir).

Çizimle: kare ile üçgenin gölgeleri

Sonraki slayttaki elle izlemenin çizimi. Solda iki eksende de kırmızı (örtüşme) var; sağda üçgen kaydırılınca x eksenindeki gölgeler ayrılıyor ve iş orada bitiyor.

Gölge nasıl hesaplanır? Nokta çarpım

Eksen: birim vektör n. Bir P noktasının eksendeki yeri: P · n = P_xn_x + P_yn_y (Y0).
Çokgenin gölgesi: bütün köşelerinin nokta çarpımlarının en küçüğü ve en büyüğü: bir [min, max] aralığı.
İki aralığın örtüşmesi: min(aMax, bMax) − max(aMin, bMin). Artı: örtüşüyor (o kadar). Eksi ya da sıfır: ayrık.
Bir kenarın dikmesi: kenar (e_x, e_y) ise dikme (−e_y, e_x); uzunluğuna bölerek birim yap.

Elle izleme: kare A (0,0) (2,0) (2,2) (0,2) ve üçgen B (1,1) (4,1) (2,5, 3)

eksen n	A’nın gölgesi	B’nin gölgesi	örtüşme
(1, 0) — karenin kenarı	[0, 2]	[1, 4]	2 − 1 = 1
(0, 1) — karenin kenarı	[0, 2]	[1, 3]	2 − 1 = 1
(−0,8, −0,6) — üçgenin kenarı	[−2,8, 0]	[−3,8, −1,4]	−1,4 − (−2,8) = 1,4
(0,8, −0,6) — üçgenin kenarı	[−1,2, 1,6]	[0,2, 2,6]	1,6 − 0,2 = 1,4

Dört eksende de örtüşme var → çakışıyorlar. En küçük örtüşme 1 (x ya da y ekseni): kareyi 1 birim sola (ya da yukarı) itmek ayırmaya yeter.

Üçgeni (3, 1) (5, 1) (4, 3)’e taşıyın: ilk eksende A [0, 2], B [3, 5] → örtüşme −1. Ayıran eksen bulundu; kalan üç eksene bakmaya gerek yok.

Çizimle: en kısa çıkış ve bir uyarı

MTV (minimum translation vector): iki şekli ayırmaya yeten en kısa itme. En az örtüşen eksen boyunca, örtüşme kadar itilir.

Çakışıyorlarsa: en kısa çıkış (MTV)

Hiçbir eksende boşluk yok. Her eksen için “bu yönde şu kadar itersem ayrılırlar” diyebiliriz: o eksendeki örtüşme miktarı.
En az örtüşen eksen = en kısa çıkış yolu. İtme vektörü = o eksen × örtüşme miktarı.
Yön: eksen A’dan B’ye mi bakıyor, tersine mi? A’nın merkezinden B’nin merkezine giden vektörle nokta çarpımına bak; A’yı B’den uzaklaştıracak tarafa çevir.
İki nesne de hareketliyse itmeyi paylaştır (ör. kütleyle ters orantılı); biri duvarsa hepsini öbürüne ver.

⚠️ Yalnızca dışbükey

İçbükey şekilde (L, U) gölgeler her eksende örtüşebilir ama şekiller birbirine değmeyebilir: U’nun içindeki kutu.

Çare: içbükey şekli dışbükey parçalara bölün ya da dışbükey zarfıyla (G1) yetinin.

Daire içinDairenin “kenarı” yok; ek eksen olarak dairenin merkezinden çokgenin en yakın köşesine giden yön sınanır. Dairenin gölgesi: merkez · n ± yarıçap.

Kutu–kutu testiAABB testi, eksenleri (1, 0) ve (0, 1) olan SAT’tır. “En az örtüşen eksen” fikri de aynen geçerli: karakter duvara yandan mı, üstten mi girdi? Daha az gömüldüğü eksenden geri it.

🧭 DEMOYU OKUMA KILAVUZU (bir sonraki slayt)

Mavi şekil sizin (sürükleyin, kaydırıcıyla döndürün); sarı şekil sabit.
Kesikli doğru o an seçili eksen. Üzerindeki kalın mavi ve sarı çizgiler iki şeklin o eksendeki gölgeleri; ince kesikli çizgiler gölgeyi belirleyen köşelerden iner.
Gölgelerin örtüşen kısmı kırmızı çizilir. Kırmızı yoksa o eksen bir ayıran eksendir.
Sağ üstteki liste bütün eksenler: “AYRIK (boşluk …)” ya da “örtüşme …”. ▶ işareti seçili eksen.
Yeşil ok (yalnızca çakışınca): en az örtüşen eksen boyunca en kısa çıkış. “↔ ayır” düğmesi mavi şekli o kadar iter.

Canlı: gölgelere bak 🔦

Şekilleri uzak tutun: listede en az bir satır yeşil “AYRIK”. Demo o ekseni otomatik seçer; gölgeler arasında boşluk var.
Mavi şekli sarıya yaklaştırın, ama değdirmeyin. “eksen: sıradaki ▶” ile eksenleri gezin: çoğunda gölgeler örtüşüyor! Tek bir ayrık eksen yetiyor.
Şimdi iç içe sokun: bütün satırlar “örtüşme”. Listede “← en küçük” yazan eksene bakın; yeşil ok o yönde.
“↔ ayır”a basın: şekiller tam değecek kadar ayrılır. Fizik motorları her karede bunu yapar.
Mavi şekli döndürün: eksenler de döner. Bir köşeyi sarı şeklin kenarına saplayın: en kısa çıkış o kenarın dikmesi.

Mavi şekil sizin (sürükleyin, kaydırıcıyla döndürün); sarı şekil sabit.
Kesikli doğru o an seçili eksen. Üzerindeki kalın mavi ve sarı çizgiler iki şeklin o eksendeki gölgeleri; ince kesikli çizgiler gölgeyi belirleyen köşelerden iner.
Gölgelerin örtüşen kısmı kırmızı çizilir. Kırmızı yoksa o eksen bir ayıran eksendir.
Sağ üstteki liste bütün eksenler: “AYRIK (boşluk …)” ya da “örtüşme …”. ▶ işareti seçili eksen.
Yeşil ok (yalnızca çakışınca): en az örtüşen eksen boyunca en kısa çıkış. “↔ ayır” düğmesi mavi şekli o kadar iter.

🔎 DEMODA DENEYİN

Şekilleri uzak tutun: listede en az bir satır yeşil “AYRIK”. Demo o ekseni otomatik seçer; gölgeler arasında boşluk var.
Mavi şekli sarıya yaklaştırın, ama değdirmeyin. “eksen: sıradaki ▶” ile eksenleri gezin: çoğunda gölgeler örtüşüyor! Tek bir ayrık eksen yetiyor.
Şimdi iç içe sokun: bütün satırlar “örtüşme”. Listede “← en küçük” yazan eksene bakın; yeşil ok o yönde.
“↔ ayır”a basın: şekiller tam değecek kadar ayrılır. Fizik motorları her karede bunu yapar.
Mavi şekli döndürün: eksenler de döner. Bir köşeyi sarı şeklin kenarına saplayın: en kısa çıkış o kenarın dikmesi.

Kod: ayıran eksen teoremi (1/2)

Kod: ayıran eksen teoremi (2/2)

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`for (const P of [A, B])`	önce A’nın kenarları, sonra B’ninkiler	Aynı döngü gövdesi iki şekil için de çalışır.
`{ x: -(b.y - a.y) / u, y: (b.x - a.x) / u }`	kenarın birim dikmesi	(e_x, e_y) → (−e_y, e_x): 90° döndürme. `u`’ya bölmezseniz örtüşme miktarı yanlış ölçekte çıkar.
`if (ortusme <= 0) return null`	ayıran eksen bulundu: hemen çık	Çoğu çift çakışmaz ve ilk birkaç eksende elenir. SAT’ı hızlı yapan satır.
`if (ortusme < enAz) …`	en az örtüşen ekseni hatırla	Döngü biterse (çakışma varsa) çıkış yönü bu eksen.
son `if`: nokta çarpım < 0 ise ekseni ters çevir	itme A’yı B’den uzaklaştırsın	Dikmenin hangi yöne baktığı köşe sırasına bağlı; merkezlerle düzeltiyoruz.
dönüş: `null` ya da `{x, y}`	ayrık / itme vektörü	Tek fonksiyon hem tespiti hem çözüm için gereken bilgiyi verir.

Önermen ve m köşeli iki dışbükey çokgen için SAT en çok n + m eksen sınar; her eksende n + m nokta çarpım: toplam (n + m)². İki kutu için 4 eksen × 8 köşe. Çakışmayan çiftlerde çoğu zaman ilk eksenlerde biter.

🐍 Laboratuvar: gölge (izdüşüm)

SAT’ın tek hesabı. Her köşe için nokta çarpımı alın; en küçüğü ve en büyüğü gölgenin iki ucudur. Python’da: s = [p[0]*axis[0] + p[1]*axis[1] for p in poly], sonra [min(s), max(s)]. Elle izlemedeki kare ve üçgen testlerde.

🐍 Laboratuvar: iki gölge ne kadar örtüşüyor?

SAT’ın karar adımı: min(a_max, b_max) - max(a_min, b_min). Eksi çıkarsa aralıklar ayrıktır (o eksen bir ayıran eksendir): 0 döndürün. Artı çıkan değerlerin en küçüğü “en kısa çıkış” uzaklığıdır.

Oyunlarda ve motorlarda SAT; öbür büyük algoritma GJK

🎮 SAT nerede?

Box2D: iki çokgenin çarpışması tam olarak bu: kaynak koddaki b2FindMaxSeparation fonksiyonu bir çokgenin kenar dikmeleri üzerinde en büyük ayrılığı arar; ayrılık artıysa “ayıran eksen bulundu” der ve çıkar.
N (Metanet Software, 2004): tek kişilik ninja platform oyunu; yapımcıları çarpışmayı SAT ile yazdı ve yöntemi bugün hâlâ okunan iki etkileşimli derste anlattı (Kaynaklar).
Araç oyunları: dönen dikdörtgen arabalar için OBB–OBB testi = 4 eksenli SAT.

GJK: aynı soru, başka yol

SAT, çok köşeli şekillerde ve 3B’de (kenar çiftlerinin çarpımları da eksen olur) pahalanır.
GJK (Gilbert–Johnson–Keerthi, 1988): iki şeklin “farkını” düşünür ve orijinin o farkın içinde olup olmadığına bakar.
Şekle tek soru sorar: “şu yönde en uçtaki noktan hangisi?” Bu yüzden daire, kapsül, çokgen aynı kodla çalışır.
Çoğu 3B fizik motorunun dar aşamasıdır.

Reducible’ın “A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)” videosu algoritmayı sıfırdan, görsel olarak kurar (Kaynaklar). Bu derste yazmayacağız; adını ve fikrini bilmeniz yeter.

Quiz 2 · SAT

İki dışbükey çokgen için 7 eksenden 6’sında gölgeler örtüşüyor, 1’inde aralarında boşluk var. Sonuç?

Teorem “bütün eksenlerde örtüşme varsa çakışır” der; tersinden, bir tanesinde bile boşluk varsa şekilleri ayıran bir doğru vardır. Bu aynı zamanda hız kazandırır: çoğu çift çakışmaz ve ilk birkaç eksende elenir (koddaki return null).

LEVEL 3

Tespit yetmez: çözüm

değdi; şimdi ne olacak?

Çizimle: “eksen eksen” çözüm, dört adımda

Oyuncu 20 piksel genişliğinde; bu kare sağa 8, aşağı 3 piksel gitmek istiyor. Önce yalnızca x ilerletilir ve duvara girdiyse geri yaslanır; sonra yalnızca y. Sonuç: yatayda durur, dikeyde düşmeye devam eder; duvar boyunca kayma kendiliğinden çıkar. Sayılar sonraki slayttaki elle izlemeyle aynıdır.

Çakışmayı bulmak işin yarısı

çözüm	ne yapar	nerede
Yok say	yalnızca “değdi” olayını bildir	tetik alanı, toplanabilir eşya, hasar bölgesi
İptal et	hareketi geri al	çok basit oyunlar; karakter duvara ve zemine yapışır
İtip ayır	en kısa çıkış vektörü (MTV) kadar it	fizik nesneleri, yukarıdan bakışlı oyunlar
Eksen eksen	önce x’te ilerle ve çöz, sonra y’de	karo tabanlı platform oyunlarının standardı
Kaydır	hızın duvara dik kısmını at	duvar boyunca sürtünerek yürüme (3B karakterler)
Sektir	hızın dik kısmını ters çevir	top, mermi, pinball (G5)

Elle izleme: eksen eksen

Oyuncu x = 96, genişlik 20 (sağ kenarı 116). Duvar x = 120’de başlıyor. Bu kare dx = +8, dy = +3.

x adımı: x = 104 → sağ kenar 124 > 120: çakıştı. Sağa gidiyorduk → duvarın sol kenarına yasla: x = 120 − 20 = 100. vx = 0.
y adımı: y += 3 → çakışma yok: kalır.
Sonuç: yatayda durdu, dikeyde düşmeye devam ediyor: duvar boyunca kayma kendiliğinden çıktı.

x ve y’yi birlikte ilerletip sonra çözseydik: çakışmanın yandan mı alttan mı geldiğini bilemezdik; karakter köşelerde takılır ya da yukarı fırlardı.

🧭 DEMOYU OKUMA KILAVUZU (bir sonraki slayt)

Yeşil kutu sizsiniz. A / D yürü, W zıpla, X atıl (bir anda 300 piksel). Sarı toplar altın; gri kareler zemin ve platformlar.
Mor ince çubuk 6 piksel kalınlığında bir duvar: tünelleme deneyi için.
Üstteki menü çarpışma yöntemini seçer: 1) yok, 2) yalnızca tespit, 3) eksen eksen çözüm.
“sürekli tespit” kutusu hareketi 4 piksellik alt adımlara böler.
Sol üstte sayaçlar: toplanan altın, duvardan geçme (tünelleme) ve zeminden düşme sayısı. Sesler açık.

Canlı: üç çarpışma yöntemi, bir karakter 🏃

1) yok: karakter zeminin içinden düşer. Hiçbir test yok.
2) yalnızca tespit: düşmüyor; ama A/D ile yürümeyi deneyin. Zemine değdiği için hareket iptal ediliyor: yapıştı. Tespit etmek yetmedi.
3) eksen eksen: yürüyün, zıplayın, platformlara çıkın, duvara doğru yürürken zıplayın: duvar boyunca kayıyor. Altınları toplayın.
Mor duvarın soluna geçip X ile sağa atılın (birkaç kez deneyin): karakter çoğu seferde duvarın öbür tarafında; “tünelleme” sayacı artar. Bazen de tam denk gelip durur: aralıklı hatalar en zor bulunanlardır.
“sürekli tespit”i işaretleyip tekrar atılın: duvar her seferinde durdurur. Aynı hız, aynı duvar; fark yalnızca kaç noktada sınadığımız.

Yeşil kutu sizsiniz. A / D yürü, W zıpla, X atıl (bir anda 300 piksel). Sarı toplar altın; gri kareler zemin ve platformlar.
Mor ince çubuk 6 piksel kalınlığında bir duvar: tünelleme deneyi için.
Üstteki menü çarpışma yöntemini seçer: 1) yok, 2) yalnızca tespit, 3) eksen eksen çözüm.
“sürekli tespit” kutusu hareketi 4 piksellik alt adımlara böler.
Sol üstte sayaçlar: toplanan altın, duvardan geçme (tünelleme) ve zeminden düşme sayısı. Sesler açık.

🔎 DEMODA DENEYİN

1) yok: karakter zeminin içinden düşer. Hiçbir test yok.
2) yalnızca tespit: düşmüyor; ama A/D ile yürümeyi deneyin. Zemine değdiği için hareket iptal ediliyor: yapıştı. Tespit etmek yetmedi.
3) eksen eksen: yürüyün, zıplayın, platformlara çıkın, duvara doğru yürürken zıplayın: duvar boyunca kayıyor. Altınları toplayın.
Mor duvarın soluna geçip X ile sağa atılın (birkaç kez deneyin): karakter çoğu seferde duvarın öbür tarafında; “tünelleme” sayacı artar. Bazen de tam denk gelip durur: aralıklı hatalar en zor bulunanlardır.
“sürekli tespit”i işaretleyip tekrar atılın: duvar her seferinde durdurur. Aynı hız, aynı duvar; fark yalnızca kaç noktada sınadığımız.

Kod: platform karakteri, eksen eksen (1/2)

Kod: platform karakteri, eksen eksen (2/2)

🎒 Kodu okuyalım

ifade	ne demek	neden böyle
`duvarlar.find(d => …)`	koşulu sağlayan ilk duvar (yoksa `undefined`)	Çok duvar varsa G2’deki ızgarayla yalnızca yakındakilere bakılır.
`o.x = dx > 0 ? d.x - o.w : d.x + d.w`	sağa gidiyorsak duvarın soluna, sola gidiyorsak sağına yasla	Hareket yönü, hangi kenardan girdiğimizi söyler. Eksen eksen çalışmanın bütün faydası bu.
`if (dy > 0) { …; o.yerde = true; }`	yalnızca aşağı giderken çarptıysa yerdeyiz	Tavana kafa vurmak “yerde” sayılmamalı; yoksa tavana yapışıp tekrar zıplarsınız.
`ceil(max(abs(dx), abs(dy)) / 4)`	en çok 4 piksellik kaç adım gerekir?	Yavaş harekette 1 adım (bedava); hızlı harekette hız kadar adım. 4 = en ince duvardan küçük bir sayı.
`o.yerde = false` (döngüden önce)	her kare baştan karar ver	Platformdan yürüyüp çıkınca bayrak kendiliğinden düşer.

📸 Oyundan bir kare: Celeste (2018)

Celeste (2018) ekran görüntüsü — Piksel hassasiyetinde platform oyunu: karakter her karede bir piksel bir piksel ilerletilip her adımda çarpışma sınanıyor. Sonraki slayt oyunun açık kaynak kodundan bu döngüyü gösteriyor.
Görsel: Celeste ekran görüntüsü, Maddy Makes Games, Wikimedia Commons, CC BY-SA 4.0

Oyunlarda: Celeste neden hiç duvara gömülmez?

Celeste ve TowerFall’un yapımcısı Maddy Thorson, iki oyunun fiziğini kısa bir yazıda anlattı. Kurallar şaşırtıcı derecede basit:
Her çarpıştırıcı bir AABB; konum ve boyutların hepsi tam sayı (piksel).
Hareket piksel piksel: her pikselde “bir ötesi dolu mu?” diye bakılır. Doluysa durulur. Karakter bir duvarın içinde hiç bulunmaz; “itip ayırma” diye bir adım yok.
Kesirli hız kaybolmasın diye artan kısım bir kalan değişkeninde birikir: karede 0,3 piksel hız → dördüncü karede 1 piksel.
Çarpınca ne olacağı çağıran tarafından verilir (carpinca): oyuncu hızını sıfırlar, ok duvara saplanır, top seker. Aynı hareket kodu, farklı tepkiler.
Tünelleme imkânsız: hız ne olursa olsun her piksel sınanır. (Bedeli: çok hızlı nesnede çok test; küçük, piksel sanatlı oyunda sorun değil.)

Demodaki “alt adımlar”ın uç hâli: adım boyu 1 piksel. Kaynak: Maddy Thorson, “Celeste & TowerFall Physics” (Kaynaklar). Kod, yazıdaki yöntemin p5.js ile yeniden yazımıdır.

Kayma ve sekme: hızı ikiye ayır

Çarpılan yüzeyin normali n (yüzeye dik birim vektör; SAT’ta en az örtüşen eksen, daire–kutuda merkez − en yakın nokta).
Hızı iki parçaya ayır: yüzeye dik kısım = (v · n) n; yüzeye paralel kısım = v − (v · n) n.
Kayma: dik kısmı at, paraleli koru. Karakter duvara çapraz yürüyünce durmaz, duvar boyunca süzülür.
Sekme: dik kısmı ters çevir (esneklik katsayısıyla çarp), paraleli koru.

Elle hesap

v = (3, 4), zemin: n = (0, −1) (ekranda yukarı).

v · n = −4 (zemine doğru).

Kayma: v − (−4)·n = (3, 4) − (0, 4) = (3, 0)

Tam sekme (e = 1): v − 2·(−4)·n = (3, 4) − (0, 8) = (3, −4)

Unity’de hazırları: Vector3.ProjectOnPlane(v, n) (kayma) ve Vector3.Reflect(v, n) (tam sekme). Godot’da move_and_slide() bütün döngüyü yapar: hareket et, çarp, kay, tekrar dene.

Çizimle: tünelleme

Çarpışma yalnızca karelerin çekildiği anlarda sınanır. Nesne iki kare arasında duvarın öbür yanına geçtiyse, hiçbir karede duvarla örtüşmemiştir ve test “değmedi” der.

Tünelleme: hesap ve çareler

Bir karede kat edilen yol = hız × dt. 60 FPS’de saniyede 6.000 piksel giden bir şey karede 100 piksel atlar.
Nesnenin eni w, engelin kalınlığı d ise: karedeki yol w + d’den büyükse nesne hiçbir karede engelle örtüşmeyebilir.
Demodaki sayılar: w = 16, d = 6 → 22 pikselden uzun adımlar riskli. Adım 100: konuma göre yaklaşık 4 denemenin 3’ünde atlar.
Hata aralıklıdır: test ederken görmezsiniz, oyuncu görür. Kare hızı düşen bilgisayarda daha sık olur (dt büyür!).

çare	nasıl	ne zaman
Alt adımlar	hareketi küçük parçalara böl; her parçada sına	basit; çoğu 2B oyun (demo)
Piksel piksel	alt adımın uç hâli	piksel sanatlı platform oyunları (Celeste)
Süpürme testi	şeklin kare boyunca taradığı hacmi sına; ilk temas anını bul	fizik motorları (Unity: Continuous)
Işın / parça	küçük, hızlı nesnenin yolunu kesiştir (G1)	mermiler
Tasarım	en yüksek hızı ve en ince duvarı sınırla; sabit zaman adımı (G5)	her zaman

🥊 Hatırlatma: MeleeSuper Smash Bros. Melee saldırı kürelerini iki kare arasında birleştirip kapsül gibi sınar (G1): hızlı yumruk için süpürme testi.

Hikâye: çarpışmayı ekran kartına sormak

1977’de Atari 2600’ün belleği 128 bayttı. Çarpışma testi için ne yer vardı ne işlemci.
Çözüm: görüntü yongası zaten her pikseli çiziyordu. İki nesnenin pikselleri aynı noktaya gelirse yonga bir çarpışma bayrağı kaldırıyordu; oyun bir sonraki karede bayrağa bakıyordu.
Bedavaya piksel kusursuz çarpışma! Aynı fikir Commodore 64’ün ve Sega Master System’in görüntü yongalarında da vardı.
Ama bayrak yalnızca “bir şeyler çarpıştı” diyordu; neyin neye, nerede çarptığını söylemiyordu. Geliştiriciler bunun etrafından dolanmak zorundaydı.

📜 Okuması keyifli

Nicole Express’in “Collision Detection Is Hard: The Story of Alf” yazısı, Master System’deki bir oyunun bu donanım bayrağına güvenmesinin, farklı konsol sürümlerinde nasıl hatalara yol açtığını adım adım çözer (Kaynaklar).

Ders: “piksel kusursuz” kulağa ideal gelir ama oyuncu için çoğu zaman en iyi his, basit ve biraz cömert bir kutudan gelir.

LEVEL 4

Işınlar

mermi, görüş, fare

Çizimle: ışın–daire

Işın O’dan çıkıp sağa gidiyor; t ışın üzerindeki uzaklık. Daireye iki yerde değer: küçük t giriş (ilk çarpma), büyük t çıkış. Sonraki slayt bu iki sayının nasıl hesaplandığını gösterir.

Işın–daire: ne zaman, nerede çarpar?

Işın: P(t) = O + t·d (d birim vektör, t ≥ 0: t doğrudan uzaklık). Daire: merkez C, yarıçap r.

Çarpma anında |P(t) − C| = r. m = O − C dersek ve iki tarafın karesini açarsak:

$$t^2 + 2(m \cdot d)\,t + (m \cdot m - r^2) = 0$$

b = m · d, k = m · m − r² ile: $$t = -b \pm \sqrt{b^2 - k}$$

b² − k < 0: kök yok → ıskaladı.
Küçük kök (−b − √…) giriş, büyük kök çıkış. İlk çarpma: giriş.
k > 0 ve b > 0: dışarıdayız ve uzaklaşıyoruz → hemen “ıskaladı”.

Elle hesap: O = (0, 0), d = (1, 0), C = (5, 1), r = 2

m = (−5, −1)

b = m · d = −5 (merkeze doğru gidiyoruz)

k = 25 + 1 − 4 = 22 (dışarıdayız)

b² − k = 25 − 22 = 3 ≥ 0 → çarpıyor

t = 5 − √3 ≈ 3,27 → nokta (3,27, 0)

Sağlama: (3,27, 0) ile (5, 1) arası √(1,73² + 1²) = 2 ✔

Kod: ışın–daire

b > 0: merkezden uzaklaşıyoruz; k > 0: dışarıdayız. İkisi birden doğruysa karekök bile almadan çıkıyoruz: çoğu ışın çoğu daireyi böyle eler. max(0, …): ışın dairenin içinde başlıyorsa uzaklık 0.

Çizimle: ışın nerelerde kullanılır?

Mermi, görüş, zemin, fare: hepsi “bir noktadan bir yöne giden çizgi ilk neye çarpar?” sorusudur.

Işın gönderme: en çok kullanılan sorgu

Hitscan mermi: tetik çekildiği an namludan bir ışın; ilk çarptığı şey vurulur. Mermi nesnesi yok, uçuş süresi yok (G1: DOOM).
Mermi nesnesi (projectile): her kare ilerleyen, yerçekiminden etkilenen bir nesne; roket, ok, el bombası. Hızlıysa her kare kat ettiği yol bir ışın olarak sınanır.
Görüş hattı: gözden hedefe ışın; arada duvar var mı? (Y11)
Zemin testi: ayaklardan aşağı kısa ışın; yerde miyim, eğim kaç derece?
Fare seçimi: kameradan fare yönüne ışın; ilk çarptığı nesne seçilir.
Hepsi aynı soru: O + t·d için en küçük t. Şekil başına bir test (ışın–daire, ışın–kutu [G2’deki dilim testi], ışın–parça [G1]); BVH hangi şekillere bakılacağını azaltır.

🔫 Nişancı oyunlarının küçük sırrı

Birçok nişancı oyununda ışın namludan değil, kameranın ortasından çıkar: nişangâhın gösterdiği yere isabet etmesi için. Silah modeli sağ altta durduğu için, köşeden bakarken namlu duvarın arkasında olsa bile mermi duvara takılmaz.

Garbaj’ın “The Slightly Odd Way Bullets Work In FPS Games” videosu bunu ve çözümlerini 4 dakikada gösterir (Kaynaklar).

🦔 Sonic’in “duyargaları”Klasik Sonic oyunlarında karakter bir kutuyla değil, ayaklarından, yanlarından ve başından çıkan birkaç kısa algılayıcı çizgiyle (ışınla) zemini yoklar: iki ayak ışını zeminin yüksekliğini ve eğimini verir. Döngülerde ve yokuşlarda koşabilmesinin temeli bu.

Quiz 3 · çözüm ve ışın

Okçuluk oyununuzda ok saniyede 3.000 piksel gidiyor (60 FPS’de karede 50 piksel) ve 10 piksel kalınlığındaki tahta hedefin içinden geçiyor. En uygun çözüm?

Ok küçük ve hızlı: bir karede aldığı yol hedefin kalınlığından büyük. Konum yerine yolu sınamak (G1’deki parça kesişimi ya da bir ışın) tünellemeyi tamamen ortadan kaldırır ve tam isabet noktasını da verir. Kare hızını düşürmek sorunu büyütür: karede 100 piksel.

LEVEL 5

Hepsi bir arada

tam kod, araçlar, kapanış

📦 Tam kod: p5.js ile mini platform oyunu

Bu 35 satır + “Kod: platform karakteri” slaytındaki hareket ve carpan fonksiyonları.

🎮 Çalıştırın, kopyalayın, bozun

▶ Eksiksiz oyunu aç — yaklaşık 90 satır: karolardan harita, eksen eksen çarpışma, atılma ve tünelleme deneyi, çarpışma kutularını gösteren H tuşu.

Deneyin:

hareket’te x ve y adımlarını tek seferde yapıp sonra çözmeyi deneyin: köşelerde ne oluyor?
hareket’i Celeste yöntemiyle (piksel piksel) yeniden yazın.
Hareketli bir platform ekleyin (her kare x’i değişen bir duvar).
Dikenler ekleyin: hasar kutusunu çizimden küçük tutun (cömert kutu).

🧰 Motorlarda

Unity	`BoxCollider2D`, `CircleCollider2D`, `CapsuleCollider2D`, `PolygonCollider2D` · `OnCollisionEnter2D` / `OnTriggerEnter2D`	Trigger = yalnızca tespit; normal collider = tespit + çözüm. Hızlı nesne için Rigidbody’de `Collision Detection: Continuous`.
Unity	`Physics2D.Raycast` · `BoxCast` · `CircleCast` · `OverlapBox`	Işın ve “süpürme” sorguları; katman maskesiyle neye bakılacağını sınırlayın.
Unreal	Collision Presets · `LineTraceSingleByChannel` · `SweepSingleByChannel`	Kanal ve tepki matrisi: kim kimi engeller, kim kimle yalnızca örtüşür.
Godot	`CharacterBody2D.move_and_slide()` · `Area2D` · `RayCast2D`	`move_and_slide` bu sunumdaki “hareket et, çöz, duvar boyunca kay” döngüsünün hazır hâli.
p5.js	p5.collide2D · p5play	Hazır testler; p5play içinde Box2D tabanlı fizik.
Fizik motorları	Box2D (2B) · Bullet, PhysX, Jolt (3B)	Geniş aşama (G2) + dar aşama (SAT/GJK) + çözüm; çoğu oyun motorunun içinde bunlardan biri var.

Sizin işiniz: doğru şekli seçmek, kutuları ayarlamak (cömert mi, cimri mi), katmanları kurmak ve hata ayıklama çizimiyle görmek.

🤖 Bu konuyu bir YZ kod asistanıyla yazarken

Sık yapılan hatalar — kontrol edin

Daire–kutuda “kutuyu büyüt” kestirmesi (köşede yanlış)
SAT’ta eksenleri birim uzunluğa getirmemek (örtüşme miktarı yanlış çıkar)
İtme vektörünün yönünü ters almak (şekiller iç içe geçer)
x ve y’yi birlikte hareket ettirip sonra çözmek (köşelere takılma)
Hızlı nesnede yalnızca son konumu sınamak (tünelleme)
Her karede GetComponent ve yeni dizi üreten sorgular (Y18)

İyi bir istek (prompt) örneği

“p5.js, motor yok. Karo tabanlı bir platform karakteri yaz: (1) {x, y, w, h, vx, vy} oyuncu ve AABB duvar listesi. (2) Hareket eksen eksen: önce x’te ilerle ve çöz, sonra y. (3) Bir karede 4 pikselden fazla hareket varsa alt adımlara böl. (4) yerde bayrağı yalnızca aşağı doğru çarpışmada. (5) Hata ayıklama: bir tuşla çarpışma kutularını ve son çarpılan duvarı çiz. (6) Test: 3.000 px/sn hızla 6 piksellik duvara doğru atılınca duvarın öbür tarafına geçmediğini doğrulayan bir console.assert.”

Şekilleri ve koordinat sistemini açıkça tanımlayın
Tünelleme testini siz isteyin
Kutuları çizdiren hata ayıklama modu isteyin

💬 Tartışma soruları

Yanınızdakiyle 2 dakika konuşun, sonra sınıfça tartışalım

En son hangi oyunda “vurmadı ki!” ya da “değmedim bile!” dediniz? Şimdi bakınca kutu sizce nasıldı: büyük mü, yanlış yerde mi, yoksa ağ gecikmesi mi?
Rocket League’de bütün arabalar altı kutudan birini kullanıyor. Her arabaya kendi şekline oturan bir kutu verilseydi oyun daha mı iyi olurdu, daha mı kötü?
Mermi cehennemi oyunlarında oyuncunun hasar kutusu birkaç piksel. Bu “hile” mi? Kutuyu geminin tamamı kadar yapsaydınız oyun nasıl değişirdi?
Quake’te her yaratığın çarpışma kutusu üç boydan biri olmak zorundaydı. Bu teknik sınır yaratık tasarımını nasıl etkilemiş olabilir?
Hız koşucuları duvardan geçme hatalarını seviyor. Bir geliştirici olarak yıllar sonra bulunan böyle bir hatayı düzeltir miydiniz?

🚀 Proje ve araştırma önerileri

[kolay] Kutuları göster — Daha önce yaptığınız bir oyuna tek tuşla açılan çarpışma kutusu görünümü ekleyin; oyuncu ve düşman kutularını ±%20 değiştirip his farkını not edin.
[kolay] Mini platform — Örnek oyunu genişletin: hareketli platform, diken (küçük hasar kutusu), çift zıplama, 3 seviye.
[orta] Celeste usulü — Aynı platform oyununu tam sayı konumlar ve piksel piksel hareketle yeniden yazın; “kalan” değişkenini ekranda gösterin. İki yöntemi 6.000 px/sn hızda karşılaştırın.
[orta] SAT oyun alanı — Fareyle döndürülen ve sürüklenen dışbükey çokgenler; çakışınca en kısa itmeyle ayrılsınlar. Gölgeleri çizin.
[zor] Dövüş oyunu kutuları — İki karakter, üçer saldırı; her animasyon karesi için elle tanımlanmış hitbox/hurtbox. Antrenman modunda kutuları çizin; hızlı saldırıda Melee’deki gibi kareler arası birleştirme yapın.
[araştırma] Cömertlik deneyi — Aynı engel parkurunu üç hasar kutusu boyutuyla (çizimin %60, %100, %140’ı) 10 kişiye oynatın; ölüm sayısı ve “adil miydi?” puanlarını karşılaştırın.

Neler öğrendik? 🎒

Oyun çizimleri değil basit şekilleri çarpıştırır; kutunun boyutu bir tasarım kararıdır (dövüş oyunları, Rocket League’in altı kutusu).
Daire–daire: kare uzaklık < (r1 + r2)². Kutu–kutu: iki eksende de örtüşme. Daire–kutu: merkezi kutuya kıstır. (Quake: haritayı şişir, oyuncuyu nokta yap.)
SAT: gölgelerin ayrıldığı tek eksen yeter; hiç yoksa en az örtüşen eksen en kısa çıkıştır. Yalnızca dışbükey. (Box2D.)
Tespit ≠ çözüm: yok say, iptal et, itip ayır, eksen eksen çöz, kaydır, sektir. (Celeste: piksel piksel, hiç gömülmeden.)
Tünelleme: yol > en + kalınlık ise risk; alt adımlar, süpürme testi ya da ışın.
Işın: hitscan, görüş hattı, zemin testi, fare seçimi; hep “en küçük t”.
Sonraki: görünürlük ve ışık: bir noktadan bütün yönlere ışın gönderip “neyi görüyorum?” sorusunu cevaplamak.

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

Rocket League 2015 · araba futbolu

Roket destekli arabalarla oynanan futbol; fiziği ve ağ kodu çok incelendi.

📖 Fandom wikisi · ▶ video 1:33

Quake 1996 · nişancı

Tamamen 3B ilk büyük nişancılardan; BSP ve görünürlük tablolarının ders kitabı örneği.

📖 Fandom wikisi · ▶ video 0:49

Celeste 2018 · platform

Bir dağa tırmanış; zor ama cömert kontrol noktalı hassas platform oyunu.

📖 Fandom wikisi · ▶ video 1:24

Street Fighter 1987– · dövüş

Dövüş oyunlarının klasiği (en ünlüsü 1991’deki II); vuruş kutuları ve kare kare zamanlama türün temeli.

📖 Fandom wikisi · ▶ video 0:49

Counter-Strike 1999– · takım nişancısı

Teröristler ve antiterör timi; isabet ve gecikme telafisi çok tartışılan rekabetçi nişancı.

📖 Fandom wikisi · ▶ video 1:49

Doom 1993 · nişancı

Türü popülerleştiren nişancı; kaynak kodu 1997’de açıldı.

📖 Fandom wikisi · ▶ video 1:00

Sonic the Hedgehog 1991 · platform

SEGA’nın hız temalı platform oyunu; karakter yere “duyarga” çizgileriyle tutunur.

📖 Sonic Retro · 🎯 Sonic Physics Guide · ▶ video 0:31

Kaynaklar: videolar 🎬

A Strange But Elegant Approach to a Surprisingly Hard Problem (GJK Algorithm)
Reducible

Building Collision Simulations: An Introduction to Computer Graphics
Reducible

Convex Polygon Collisions #1
javidx9

Arbitrary Rectangle Collision Detection & Resolution
javidx9

How 2D Game Collision Works (Separating Axis Theorem)
Skeffles

The Slightly Odd Way Bullets Work In FPS Games
Garbaj

How Games Fake Melee Attacks to Make Combat Feel Great
GDQuest

SM64’s Invisible Walls Explained Once and for All
pannenkoek2012

Kaynaklar: kaynak kodu, yazılar ve etkileşimli sayfalar 📚

Maddy Thorson: Celeste & TowerFall Physics — tam sayı konumlar, piksel piksel hareket, hareketli platformlar
Quake kaynak kodu (id Software): world.c · Box2D: b2_collide_polygon.cpp (çokgen–çokgen, SAT)
Metanet Software: N Tutorial A: Collision Detection and Response — “N” oyununun yapımcılarından, etkileşimli SAT anlatımı
Jeffrey Thompson: Collision Detection · dyn4j: SAT · noonat: Intersection Tests in 2D
Sonic Retro: Sonic Physics Guide — algılayıcı çizgiler, eğimler, hız değerleri
Nicole Express: Collision Detection Is Hard: The Story of Alf — donanım çarpışma bayrakları
Christer Ericson, Real-Time Collision Detection (2005), 4. ve 5. bölümler: sınırlayıcı şekiller ve temel testler

NEXT LEVEL ▶

Görünürlük ve Işık

Işın dökümü, görüş çokgeni, gölge dökümü, savaş sisi, BSP

SONRAKİ SUNUM ▶