## Ziel der Simulation
Gesucht ist eine möglichst kleine Anzahl von Wächtern, die gemeinsam den gesamten begehbaren Bereich eines Grundrisses überwachen. Die Simulation macht damit ein klassisches Problem der algorithmischen Geometrie anschaulich, bei dem Sichtbarkeit, Abdeckung und geschickte Platzierung zusammenwirken.^1^
Didaktisch eignet sich die App, um räumliches Vorstellungsvermögen, argumentatives Begründen und heuristisches Problemlösen zu fördern. Lernende erleben unmittelbar, dass eine „gefühlt gute“ Platzierung nicht automatisch zur vollständigen Abdeckung führt, und dass Engstellen, Ecken, Nischen teils unerwartete Schwierigkeiten bedeuten.
Im Unterricht kann die Simulation zum entdeckenden Arbeiten eingesetzt werden, etwa zum Vergleichen verschiedener Strategien, zum Formulieren von Vermutungen oder zum Diskutieren der Frage, wann ein Level als gelöst gelten kann. Gleichzeitig unterstützt die farbige Darstellung der Sichtbereiche den Aufbau eines tragfähigen Verständnisses dafür, wie lokale Sichtbeziehungen zu einer globalen Flächenabdeckung zusammengeführt werden.
## Hinweise zur Bedienung
### Einstellungen
- **Level:** Wählt einen Grundriss mit eigener Schwierigkeit und eigener maximaler Wächterzahl.
- **Maximale Anzahl Wächter:** Gibt an, wie viele Wächter höchstens gesetzt werden dürfen.
- **Zeit \(t\):** Zeigt die bisher verstrichene Zeit im aktuellen Level an.
- **Reset:** Setzt das aktuelle Level zurück.
### Spiel
- Tippe oder klicke auf eine freie Stelle im Grundriss, um einen neuen Wächter zu platzieren.
- Ziehe einen Wächter mit Maus oder Touch-Geste an eine andere Position.
- Tippe einen Wächter kurz an, um ihn zu entfernen.
- Jeder Wächter besitzt eine eigene Farbe; überlagerte Sichtbereiche werden farblich gemischt dargestellt.
- Ein Level ist gelöst, wenn die gesamte freie Fläche mit der erlaubten Anzahl an Wächtern abgedeckt ist.
## Implementierung
Die Simulation modelliert den Grundriss als quadratischen Koordinatenraum mit rechteckigen Hindernissen. Wächter werden als Punkte dargestellt; von jedem Wächter aus werden Sichtstrahlen zu relevanten Hindernisecken betrachtet, um daraus ein Sichtpolygon zu konstruieren. Die Grundidee folgt dem Konzept des Sichtpolygons, also der Menge aller Punkte, die von einem Standpunkt aus ohne Hindernis dazwischen sichtbar sind.^2^
Programmtechnisch läuft die Berechnung in mehreren Schritten ab:
1. **Geometrie des Levels aufbauen:** Aus den Hindernissen werden Ecken und Kanten des Grundrisses bestimmt.
2. **Sichtbereich je Wächter berechnen:** Für jeden Wächter werden Strahlen in Richtung aller relevanten Ecken ausgesendet; zu jedem Strahl wird der nächstgelegene Schnittpunkt mit einer Hinderniskante bestimmt.
3. **Sichtpolygon zeichnen:** Die gefundenen Punkte werden nach ihrem Winkel sortiert und als Polygon mit halbtransparenter Füllung dargestellt.
4. **Abdeckung numerisch prüfen:** Zur Erfolgskontrolle wird die freie Fläche durch ein feines Raster angenähert. Für jeden Rasterpunkt wird geprüft, ob er in einem Hindernis liegt oder von mindestens einem Wächter aus sichtbar ist. Ein Level gilt als gelöst, wenn alle freien Rasterpunkte abgedeckt sind.
5. **Spielzustand aktualisieren:** Beim Verschieben, Hinzufügen oder Entfernen von Wächtern werden Sichtbereiche und Abdeckung neu berechnet.
Mathematisch basiert die Sichtprüfung auf Schnittpunkten zwischen einem Strahl und den Kanten der Hindernisse. Für einen Strahl mit Richtung ``d`` und eine Kante von ``a`` nach ``b`` wird ein lineares Gleichungssystem in den Parametern ``t`` und ``u`` gelöst, sodass der Schnittpunkt in der Form ``g + t d = a + u (b-a)`` beschrieben wird. Gültig ist ein Treffer genau dann, wenn ``t > 0`` und ``0 <= u <=1``; dadurch liegt der Punkt vor dem Wächter auf dem Strahl und zugleich auf dem betrachteten Kantenstück.
## Quellen
1. [Art gallery problem – Wikipedia](https://en.wikipedia.org/wiki/Art_gallery_problem)
2. [Visibility polygon – Wikipedia](https://en.wikipedia.org/wiki/Visibility_polygon)