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.