InfiniTower/docs/adr/0004-spatial-grid-fuer-gegner-nachbarschaft.md

ADR-0004: Spatial Grid für Gegner-Nachbarschaft und weiche Separation

• Status: Angenommen
• Datum: 2026-08-10
• Betrifft: Gegner-gegen-Gegner-Kollision, Zielauswahl in tower_fire, geteilter Reichweiten-Scan für das Auslöse-System, Projektil-Kollision
• Baut auf: ADR-0001 (alle Zahlen aus Res<Balance>), ADR-0002 (Ablageregel Resource vs. Component; vollständige Neuberechnung statt Buchführung), Perf-Messungen aus #4, Cap-Analyse in #1, Auslöse-Entscheidung in #12

Kontext

Die Gegner-gegen-Gegner-Kollision steht seit #4 als „offene Architekturfrage" im Raum — Stapeln zulassen oder Spatial Grid mit weicher Separation — und hat seitdem in keiner ADR und auf keiner Liste gestanden. Sie entscheidet, ob 10 000 Gegner spielbar statt nur lauffähig sind, und sie ist teuer nachzurüsten.

Der eigentliche Grund für eine eigene ADR ist aber nicht die Separation. Drei Systeme brauchen dieselbe Nachbarschaftsabfrage und wollten sie bisher jedes für sich beantworten:

Abfrage	Radius	Aufrufe pro Frame
Weiche Separation: „welche Gegner sind mir zu nahe?"	Separationsradius (klein)	einmal je Gegner → bis 10 000
Zielauswahl in tower_fire: „welcher Gegner ist der nächste?"	Turm-Range (groß)	einmal (ein Turm)
Geteilter Reichweiten-Scan für das Auslöse-System (#12)	Turm-Range (groß)	einmal (ein Turm)

Dazu kommt die Projektil-Kollision mit einem kleinen Trefferradius und einem Aufruf je Projektil. #4 hat sie als einzige davon gemessen.

#12 hat den geteilten Reichweiten-Scan bereits entschieden — „der Scan wird einmal gemacht und geteilt, sonst läuft er siebenmal pro Frame gegen 10 000 Entities". Diese ADR erledigt den zweiten Teil derselben Beobachtung: der eine geteilte Scan ist immer noch ein linearer Durchlauf über alle Gegner. Ein Grid macht daraus eine Abfrage, an der vier Konsumenten hängen — es ist geteilte Infrastruktur, keine Optimierung eines einzelnen Systems.

Die Messungen, gegen die hier gerechnet wird (#4, #1)

Größe	Wert
Gesamte Gameplay-Logik bei 10 000 Gegnern	0,114 ms von 16,67 ms (0,7 %)
move_enemies, teuerstes Logik-System	~10 ns pro Gegner → 0,100 ms bei 10 000
Population-Maintainer bei 50 000 Gegnern	6,1 µs
Kollisions-Paartest	1,5–6,5 ns, exakt linear in n·m
Naives O(n·m) trägt bis	~5·10⁵ Paartests pro Frame
Bruch unter 60 fps	~70 000 Sprites, Rendering dominiert mit 96–98 %

move_enemies ist mit 0,100 ms von 0,114 ms fast die gesamte Logik. Das ist der Maßstab: Ein System, das einen Durchlauf über dieselbe Gegnermenge macht, kostet höchstens so viel wie dieses.

Geprüft an der Bevy-0.19-Doku (docs.rs über context7, nicht aus dem Gedächtnis)

• Bevy 0.19 bringt keine Struktur für Nachbarschaftsabfragen im Gameplay mit. bevy::math::bounding liefert Aabb2d, BoundingCircle, Bounded2d und IntersectsVolume — also Volumen und Schnitttests für die Narrow Phase, keine Broad Phase. Wer eine Nachbarschaftsabfrage will, baut sie oder holt sie sich als Dependency.
• Query::par_iter / par_iter_mut existieren; par_iter ist auf lesende Queries beschränkt. Zusammen mit Local<Parallel<Vec<_>>> wäre ein parallel gefüllter Rebuild möglich — er wird hier nicht gebaut, siehe Rechnung unten.
• Local<T> und Resource überleben Systemläufe. Die Bucket-Vektoren des Grids werden über clear() wiederverwendet; es gibt keine Allokation pro Frame.

Entscheidung

1. Ein Uniform Grid als Resource, einmal pro Frame neu gebaut

SpatialGrid ist eine Resource: ein dichtes Array fester Größe über die Arena, je Zelle ein Vec<Entity>. Die Arena ist beschränkt (die Spawn-Peripherie muss laut Spec-Feature 1 sichtbar sein) und der Turm steht fest in der Mitte — es gibt keinen Grund für eine Hashmap. Der Zellindex ist zwei Divisionen und zwei floor. Gegner außerhalb des Gitters werden in die Randzelle geklemmt.

Das Grid ist kein Component an der Turm-Entity: Es beschreibt nicht den Turm, sondern die Welt, und es überlebt keinen Run-Wechsel als Zustand — es wird ohnehin jeden Frame neu gebaut. Damit bleibt die Ablageregel aus ADR-0002 §6 unberührt.

2. Zellgröße: der kleinste Radius, der pro Gegner abgefragt wird

Die Kosten einer Radiusabfrage sind (⌈2r/c⌉+1)² Zellen mal der mittleren Belegung. Beide Fehlerrichtungen kosten: c ≪ r erzeugt viele leere Zellenköpfe, c ≫ r erzeugt Kandidaten, die der Narrow-Phase-Test wieder verwirft.

Die Zellgröße folgt dem Separationsradius, nicht der Turm-Reichweite. Der Grund ist nicht der Radius, sondern die Häufigkeit: Die Separationsabfrage läuft einmal je Gegner, also bis zu 10 000-mal pro Frame; der Reichweiten-Scan und die Zielauswahl laufen bei genau einem Turm einmal pro Frame. Eine Zellgröße, die für die einmalige große Abfrage gewählt wird, verteuert die 10 000-fache kleine Abfrage; umgekehrt verteuert eine kleine Zelle die einmalige große Abfrage nur um Zellenköpfe, und die sind kein Narrow-Phase-Test.

Verbindlich:

cell_size = ‹1,0› × max(Separationsradius, Trefferradius)

Alle drei Werte sind ‹Platzhalter› und leben in Balance (ADR-0001 §4 — keine Schwelle als Literal im Gameplay-Code). Bei cell_size = Separationsradius berührt eine Separationsabfrage genau den 3×3-Block um die eigene Zelle und nie mehr.

Die Turm-Range bestimmt die Zellgröße ausdrücklich nicht. Täte sie es, läge die gesamte in Reichweite befindliche Population in wenigen Zellen — und die Separationsabfrage wäre wieder O(n), also genau das, was das Grid entfernen soll. Range ist außerdem ein Stat, der über den Run wächst (ADR-0002 §3); eine Zellgröße, die einem wachsenden Stat folgt, wäre eine Struktur, die sich im laufenden Run umbaut.

3. Rebuild pro Frame, kein inkrementelles Update — gerechnet, nicht geschätzt

Der Rebuild ist ein Durchlauf über dieselbe Gegnermenge wie move_enemies, in derselben Speicherreihenfolge, mit weniger Arithmetik: move_enemies liest Transform, bildet die Richtung zur Mitte (Subtraktion plus Normalisierung, also eine Wurzel), skaliert und schreibt Transform zurück. Der Rebuild liest Transform, rechnet zwei Divisionen und zwei floor und schiebt eine Entity in einen Vec.

	Rechnung	Ergebnis
Obergrenze Rebuild bei HARD_ENEMY_CAP	10 000 × ≤10 ns	≤0,10 ms
Anteil am Frame-Budget	0,10 / 16,67	≤0,6 %
Logik gesamt danach	0,114 + 0,10	≤0,22 ms = ≤1,3 %
Selbst am gemessenen Bruchpunkt	70 000 × 10 ns	0,7 ms = 4,2 %

Die 10 ns sind eine großzügige Obergrenze, weil sie den teureren Nachbarn als Maßstab nimmt.

Was ein inkrementelles Update dagegen einspart, ist nach oben durch dieselben ≤0,10 ms begrenzt — und es spart nicht einmal die, denn den Zellindex muss es genauso je Gegner ausrechnen, um einen Zellwechsel überhaupt zu erkennen. Der Rest der Ersparnis ist der Vec-Push. Dagegen steht: ein Rückindex je Entity (in welcher Zelle und an welcher Position liegt sie?), ein Entfernen aus einem Vec in der Mitte, und ein Zustand, der zwischen Frames korrekt bleiben muss, während Gegner spawnen, sterben und bei radialer Konvergenz ständig Zellgrenzen überqueren.

Das ist dieselbe Abwägung, die ADR-0002 §6 für die Akkumulatoren getroffen hat, mit demselben Ergebnis: vollständige Neuberechnung statt Buchführung über das Rückgängigmachen. Buchführung schlägt fehl, und hier kauft sie unter 0,6 % Frame-Budget.

Aus demselben Grund wird der Rebuild nicht parallelisiert. par_iter plus Local<Parallel<Vec<_>>> und ein Merge-Schritt wären in Bevy 0.19 verfügbar; sie kaufen einen Bruchteil von 0,6 %.

Nebenrechnung zur nicht entschiedenen Spielgeschwindigkeit (#1, Spec „Lücken" Punkt 11): Nur die Simulation skaliert, nicht das Rendering. x4 ergibt ≤0,4 ms Rebuild, also ≤2,4 % des Budgets. Die Entscheidung hier präjudiziert den Multiplikator nicht.

4. Die Projektil-Kollision läuft über dasselbe Grid

#4 hat gemessen, dass naives O(n·m) bis ~5·10⁵ Paartests pro Frame trägt, und genau das empfohlen. Diese ADR kehrt das um, aus drei Gründen:

1. Der gemessene Spielraum ist am Auslegungspunkt aufgebraucht. 10 000 Gegner × ‹50› gleichzeitige Projektile sind 5·10⁵ Paartests — die Grenze, nicht ein Abstand zu ihr.
2. Beide Faktoren wachsen entlang der Schwierigkeitskurve, das Budget nicht. n wächst mit target_population(wave), m wächst, weil AttackInterval über Workshop, Cards und In-Run-Upgrades sinkt (ADR-0002 §3, Modus Interval). Das Produkt wächst also quadratisch gegen ein festes Budget. Ein Grenzwert, den man im ersten Run einhält und in Run 20 reißt, ist kein Grenzwert.
3. Das Grid steht ohnehin. Die Abfrage kostet nur noch den 3×3-Block, weil der Trefferradius nach Punkt 2 in die Zellgröße eingegangen ist. Ein zweiter, anders strukturierter Durchlauf über die Gegnermenge wäre genau das Muster, das #12 als Bruchstelle benannt hat.

Der Narrow-Phase-Test bleibt, was er war: der gemessene 1,5–6,5-ns-Paartest, nur gegen ‹k› Kandidaten aus dem Block statt gegen n. bevy::math::bounding liefert dafür BoundingCircle und IntersectsVolume.

5. Weiche Separation: ein geklemmter Versatz, keine Kraft

Die Separation ist keine Kollisionsauflösung. Überlappung bleibt erlaubt; das Ziel ist, den Ring lesbar zu halten, nicht Durchdringung zu verhindern. Wer Durchdringung verbietet, baut den Stau, den die Cap-Analyse als „Stau am Turmring, den keine DPS-Menge auflöst" benannt hat.

Je Gegner, aus dem 3×3-Block:

1. Nachbar-Budget: höchstens ‹k› Nachbarn werden berücksichtigt. Das deckelt Kosten und Kraft in einem — dieselbe Regelform wie das „Ziel-Limit pro Auslösung" der Cap-Analyse, das die Spec in Feature 8 schon trägt. Eine Projektregel statt zweier.
2. Summe der Wegdrück-Vektoren, je Nachbar normiert und mit dem Abstand abfallend gewichtet.
3. Klemmung: Der resultierende Versatz wird auf ‹f› × (Speed × dt) mit ‹f› < 1 begrenzt und als Positionsversatz angewandt, nicht als Beschleunigung.

Das Problem, das die Klemmung löst, sitzt am Turmring. Radial auf einen Punkt konvergierende Körper erzeugen dort die höchste Dichte, die es im Spiel gibt. Die Nachbarschaft eines Gegners am Ring ist tangential ungefähr isotrop, radial aber nicht — hinter ihm, zum Turm hin, steht niemand, der zurückdrückt. Der Rest-Vektor zeigt deshalb nach außen, vom Turm weg. Ohne Klemmung ist das die Pulsier-Fehlerform: Der Ring drückt sich selbst auseinander, die Gegner laufen wieder heran, der Ring drückt sich wieder auseinander — und dazwischen fallen Gegner aus ihrer Angriffsreichweite.

Mit der Klemmung kann ein Gegner in einem Frame nie weiter versetzt werden, als er sich bewegt. Der radiale Anlauf wird also nie umgekehrt, ein Gegner verlässt seine Angriffsposition nicht, und Jitter braucht ein Überschwingen, das es konstruktiv nicht mehr gibt. Aus der Kraft wird eine begrenzte Ausdünnung.

‹k›, ‹f›, Separationsradius und die Abstandsgewichtung sind ‹Platzhalter› in Balance. Sie findet nur Spielen, wie die vier freien Zahlen aus #8. Diese ADR erfindet keine.

6. Einordnung in den Frame

Verbindliche Reihenfolge, explizit festgelegt, nicht aus der Registrierungsreihenfolge geerbt:

1. move_enemies — schreibt Transform
2. rebuild_spatial_grid — liest Transform, schreibt SpatialGrid
3. alle Konsumenten, lesend auf SpatialGrid: weiche Separation, geteilter Reichweiten-Scan, tower_fire, Projektil-Kollision

Verbindlich: Kein Konsument iteriert die Gegner-Query direkt. Das ist die schärfere Fassung des Akzeptanzkriteriums, das die Spec für Feature 4 schon führt — aus „es gibt genau einen Reichweiten-Scan" wird „es gibt genau einen Durchlauf über die Gegnermenge, und das ist der Rebuild".

Eine Folge wird ausdrücklich in Kauf genommen: Die Separation schreibt Transform, nachdem das Grid gebaut wurde. Das Grid ist innerhalb desselben Frames also um genau einen Separationsversatz veraltet. Der ist nach Punkt 5 kleiner als ein Bewegungsschritt und damit kleiner als eine Zelle. Die Alternative — Separation vor dem Rebuild — verschiebt dieselbe Ungenauigkeit auf tower_fire und die Auslöse-Bedingungen, wo sie sichtbarer wäre.

Verworfene Alternativen

• Stapeln zulassen, keine Separation (der Vorschlag, den die Spec unter „Lücken" Punkt 9 festgehalten hat). Der billigste Weg, und für sich genommen vertretbar — aber er löst nur eines der vier Probleme. Die Zielauswahl in tower_fire bleibt O(n), obwohl #4 sie als nächsten Hotspot nach dem Rendering benannt hat, und der geteilte Reichweiten-Scan bleibt ein linearer Durchlauf. Das Grid trägt sich über drei Konsumenten, nicht über die Separation. Dazu kommt ein Design-Argument: Am Turmring liegen ohne Separation tausende Sprites deckungsgleich übereinander, und die Soll-Population — die Größe, auf der die gesamte Schwierigkeitskurve steht — ist dann nicht mehr abzulesen.
• Echte Kollision über eine Physik-Engine (bevy_rapier, avian). Löst Durchdringung, also nicht das Problem; bringt einen Solver, einen Integrationsschritt und eine Dependency, deren Release-Takt an Bevy-Versionen hängt — dieselbe Einwendung, die ADR-0001 gegen bevy_common_assets erhoben hat. Bei tausenden radial konvergierenden Körpern produziert ein Solver genau den Stau, den die Cap-Analyse benennt.
• Eine fertige Spatial-Query-Crate (etwa bevy_spatial). Spart den Rebuild-Code, der aus einer Schleife und einem Index besteht, und tauscht ihn gegen eine Dependency plus eine fremde Vorstellung davon, was eine Abfrage kostet. Ob eine 0.19-kompatible Fassung existiert, wurde nicht geprüft — die Entscheidung hängt nicht daran.
• Quadtree oder BVH. Passen sich ungleicher Dichte an. Die Dichte hier ist aber bekannt und gerichtet — ein Attraktor in der Mitte, radiale Anläufe —, und ihr Rebuild ist kein linearer Durchlauf, sondern eine Sortierung mit Vergleichen. Die Rechnung in Punkt 3 gilt für sie nicht.
• Inkrementelles Update des Grids. Siehe Punkt 3: Die Ersparnis ist nach oben durch ≤0,10 ms begrenzt, der Preis ist ein Rückindex je Entity und eine Bug-Klasse.
• Ein eigenes Grid je Konsument, jeweils mit passender Zellgröße. Drei bis vier Rebuilds statt einem und drei bis vier Stellen, an denen ein veraltetes Grid entstehen kann. Der gemessene Preis eines Rebuilds ist das Argument dagegen.

Konsequenzen

Positiv

• Vier Nachbarschaftsabfragen haben eine Quelle. Ein neuer Konsument (Death Wave, ein späterer Aura-Effekt) bekommt sie, ohne einen fünften Durchlauf über die Gegnermenge einzuführen.
• Die Zielauswahl in tower_fire — laut #4 der nächste Hotspot nach dem Rendering — wird von einem linearen Scan zu einem Zellenlauf von innen nach außen, der beim ersten Treffer abbricht.
• Der Rebuild hat keinen Zustand zwischen Frames. Es gibt kein veraltetes Grid, keinen Rückindex und keine Reparaturroutine.
• Die Projektil-Kollision hört auf, entlang der Schwierigkeitskurve zu wachsen.

Negativ

• Der erste unbedingte Kostenpunkt des Projekts. Alles bisherige läuft bei Änderung (EffectiveStats, ADR-0002 §7) oder bei Ereignis. Der Rebuild läuft jeden Frame, auch wenn nichts passiert. ≤0,6 % ist bezahlbar, aber es ist eine neue Art von Kosten.
• SpatialGrid ist eine Resource, die sich jeden Frame ändert. is_changed() auf ihr ist als Signal wertlos. Sie darf insbesondere nie eine Quelle für die EffectiveStats-Neuberechnung werden (ADR-0002 §7), sonst läuft die wieder jeden Frame und verliert genau den Beobachtungspunkt, für den sie gebaut wurde.
• Eine Zellgröße für vier Radien ist ein Kompromiss. Die Reichweiten-Abfrage durchläuft einen Block, der mit dem Range-Stat wächst — siehe Revisions-Auslöser 2.
• Die Separation ist innerhalb des Frames um einen Versatz veraltet (Punkt 6).
• Die weiche Separation wird nach Gefühl getunt, nicht gegen einen Test. ‹k›, ‹f› und der Separationsradius sind so frei wie die vier Zahlen aus #8 — und der Beleg, dass sie stimmen, ist ein Blick auf den Turmring, keine Zahl.

Offene Punkte, die diese ADR nicht entscheidet

• Death Wave als vierter Konsument. Der radiale Sweep fragt einen wachsenden Ring ab und muss Gegner „in der Reihenfolge ihres Abstands" treffen (Spec-Feature 8). Ein zellweiser Lauf von innen nach außen ist die naheliegende Form, und der gebatchte Massentod aus Spec-„Lücken" Punkt 10 wäre dann eine Zellordnung statt tausender Einzelereignisse. Das ist hier nicht entschieden — es gehört zu der ADR, die für Massenwirkung und Ziel-Limit noch fehlt.
• Arena-Maße und Zellenzahl. Die Kantenlänge des Gitters folgt aus der Arena, und die steht nicht fest. Bis dahin ist offen, ob die Spawn-Peripherie im Gitter liegt oder in die Randzellen klemmt.
• SlowAura und andere Gegner-modifizierende Fähigkeiten (ADR-0002 §9) sind naheliegende weitere Konsumenten. Sie fallen mit der Card-Liste.

Revisions-Auslöser

Diese Entscheidung wird neu getroffen, sobald eines der folgenden Ereignisse eintritt:

1. Der Rebuild ist nicht mehr der billigere Durchlauf. Eine Messung mit dem Aufbau aus examples/perf_spike.rs bei HARD_ENEMY_CAP zeigt rebuild_spatial_grid teurer als move_enemies im selben Frame. Die Entscheidung gegen das inkrementelle Update steht und fällt mit dieser Annahme; ist sie widerlegt, wird sie neu getroffen — nicht vorher.
2. Radien-Spreizung. Ein Konsument braucht einen Abfrageradius kleiner als eine halbe Zelle oder größer als ‹20› Zellkanten. Dann trägt eine Auflösung nicht mehr für alle Abfragen, und zwei Auflösungen oder eine hierarchische Struktur sind zu prüfen.
3. Die Separation frisst den radialen Fortschritt. Ein Gegner braucht vom Spawn bis zum Turmring mehr als ‹1,2›× die aus Speed und Abstand erwartete Zeit. Dann ist die Klemmung zu schwach dosiert oder die Form der Separation falsch — beobachtbar in der Run-Telemetrie, nicht nur im Bild.
4. Das Bewegungsmodell ist nicht mehr rein radial. Ausweichen, Umkreisen, Knockback oder ein zweiter Anziehungspunkt. Dann fällt die Dichteannahme „Maximum am Turmring", auf der Punkt 5 steht, und die Zellgröße ist neu zu bestimmen.