====== std.grid — Gitter und Pfadfindung ======
Rechteckige Gitter mit Kosten je Zelle: Nachbarschaft mit 4 oder 8 Richtungen, Bresenham und Sichtlinie, BFS-Distanzkarten, Dijkstra und A*.
→ [[lyx_-_programmiersprache:units:mathematik|Mathematik-Units]] · [[lyx_-_programmiersprache:units:graph|std.graph]] · [[lyx_-_programmiersprache:units:dist|std.dist]]
import std.grid;
Schicht 0, hängt an ''std.math'' und ''std.alloc''. 22 Funktionen, eine Konstante (''GRID_BLOCKED'' = 0). Alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt.
----
===== Darstellung =====
Ein Gitter ist ein Feld aus ''w · h'' ''int64''-Werten — die **Kosten**, eine Zelle zu betreten. ''GRID_BLOCKED'' ist ''0'' und bedeutet unpassierbar; alles ab 1 ist begehbar und kostet entsprechend.
var c: int64 := alloc(w * h * 8);
GridFill(c, w, h, 1); // alles begehbar, Kosten 1
GridSet(c, 2, 1, w, GRID_BLOCKED); // Mauer bei (2,1)
Die Umrechnung zwischen Koordinaten und Index übernehmen ''GridIndex(x, y, w)'', ''GridX(idx, w)'' und ''GridY(idx, w)''. ''GridInBounds'' und ''GridWalkable'' prüfen Rand und Begehbarkeit.
----
===== Der wichtigste Punkt: welche Heuristik zu welcher Nachbarschaft =====
Fast jede Funktion nimmt ein Flag ''diag''. Der Unterschied ist **nicht nur** die Zahl der Nachbarn — er entscheidet auch darüber, welche Heuristik A* überhaupt verwenden darf.
unit main;
import std.io;
import std.string;
import std.alloc;
import std.grid;
fn ZF(t: pchar, v: f64): void { Print(t); PrintF64(v); }
fn ZI(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }
fn main(): int64 {
ZI("Manhattan (0,0)->(1,1) : ", GridManhattan(0,0,1,1));
ZF("Octile (0,0)->(1,1) : ", GridOctile(0,0,1,1));
ZF("Heuristic diag=false : ", GridHeuristic(0,0,1,1,false));
ZF("Heuristic diag=true : ", GridHeuristic(0,0,1,1,true));
return 0;
}
Manhattan (0,0)->(1,1) : 2
Octile (0,0)->(1,1) : 1.414213
Heuristic diag=false : 2.000000
Heuristic diag=true : 1.414213
**A* findet den kürzesten Weg nur, wenn die Heuristik den Restweg nie überschätzt.** Genau hier liegt der häufigste Fehler:
* **4 Richtungen** → Manhattan ist richtig.
* **8 Richtungen** → Manhattan **überschätzt**. Der Schritt von (0,0) nach (1,1) kostet tatsächlich 1,414, Manhattan behauptet 2. A* liefert dann Wege, die kürzer aussehen als sie sind, und bricht die Suche zu früh ab. Richtig ist die **Oktil-Distanz**.
''GridHeuristic(x1, y1, x2, y2, diag)'' wählt anhand von ''diag'' die passende — die Zahlen oben zeigen es. Wer eine eigene Heuristik einsetzt, muss das selbst im Blick behalten.
Diagonale Schritte kosten das √2-fache eines geraden. Alles andere ergäbe Wege, die diagonal billiger sind als gerade, und ließe Pfade zickzack laufen.
----
===== Pfadfindung =====
unit main;
import std.io;
import std.string;
import std.alloc;
import std.grid;
fn ZI(t: pchar, v: int64): void { Print(t); PrintLn(IntToStr(v)); }
fn main(): int64 {
var w: int64 := 5; var h: int64 := 5;
var c: int64 := alloc(w * h * 8);
GridFill(c, w, h, 1);
GridSet(c, 2, 0, w, GRID_BLOCKED);
GridSet(c, 2, 1, w, GRID_BLOCKED);
GridSet(c, 2, 2, w, GRID_BLOCKED);
GridSet(c, 2, 3, w, GRID_BLOCKED);
ZI("Walkable(2,1) : ", GridWalkable(c,2,1,w,h) as int64);
ZI("Walkable(2,4) : ", GridWalkable(c,2,4,w,h) as int64);
var px: int64 := alloc(64 * 8);
var py: int64 := alloc(64 * 8);
var len: int64 := GridAStar(c, w, h, 0, 0, 4, 0, false, px, py, 64);
Print("A* Laenge="); Print(IntToStr(len)); Print(" Weg: ");
var i: int64 := 0;
while (i < len) {
Print("("); Print(IntToStr(peek64(px + i*8))); Print(",");
Print(IntToStr(peek64(py + i*8))); Print(") ");
i := i + 1;
}
PrintLn("");
ZI("LineOfSight (0,0)-(4,0): ", GridLineOfSight(c,0,0,4,0,w,h) as int64);
ZI("LineOfSight (0,4)-(4,4): ", GridLineOfSight(c,0,4,4,4,w,h) as int64);
ZI("FloodCount von (0,0) : ", GridFloodCount(c,w,h,0,0,false));
return 0;
}
Walkable(2,1) : 0
Walkable(2,4) : 1
A* Laenge=13 Weg: (0,0) (1,0) (1,1) (1,2) (1,3) (1,4) (2,4) (3,4) (4,4) (4,3) (4,2) (4,1) (4,0)
LineOfSight (0,0)-(4,0): 0
LineOfSight (0,4)-(4,4): 1
FloodCount von (0,0) : 21
Die Mauer verläuft bei ''x=2'' über ''y=0…3'' und lässt nur unten bei ''y=4'' eine Lücke. A* geht genau dort herum — 13 Felder statt der 5 auf direktem Weg. ''LineOfSight'' bestätigt es: durch die Mauer nein, entlang ''y=4'' ja. ''FloodCount'' zählt 21 erreichbare Zellen — 25 minus die 4 blockierten.
^ Funktion ^ Zweck ^
| ''GridBfs(cells, w, h, sx, sy, diag, out)'' | Distanzkarte in Schritten, ignoriert Kosten |
| ''GridDijkstra(…)'' | Distanzkarte **mit** Kosten |
| ''GridAStar(…, gx, gy, diag, outX, outY, maxLen)'' | ein Weg zu einem Ziel, Länge als Rückgabe |
| ''GridPathFrom(prev, goal, w, …)'' | Weg aus einer BFS-/Dijkstra-Vorgängerkarte |
| ''GridPathCost(…)'' | Kosten eines fertigen Weges |
| ''GridReachable'' · ''GridFloodCount'' | was ist von hier aus erreichbar? |
| ''GridLine(x0, y0, x1, y1, …)'' | Bresenham-Linie |
| ''GridLineOfSight(…)'' | dieselbe Linie, aber an der ersten Sperre abgebrochen |
| ''GridNeighbors(cells, x, y, w, h, diag, outX, outY)'' | begehbare Nachbarn, Anzahl als Rückgabe |
**''GridAStar'' braucht ''maxLen''** und schreibt nicht darüber hinaus. Der Rückgabewert ist die tatsächliche Länge; passt der Weg nicht, ist das erkennbar.
> **Ein Ziel oder viele?** ''GridAStar'' sucht **einen** Weg zu **einem** Ziel und ist dafür am schnellsten, weil die Heuristik die Suche lenkt. Wer die Entfernung zu **allen** Feldern braucht — Einflusskarten, Reichweiten, „wie weit komme ich in 5 Zügen" —, nimmt ''GridBfs'' oder ''GridDijkstra'' und wertet die Karte danach beliebig oft aus.
----
===== Abgrenzung =====
''std.grid'' rechnet auf **Gittern**. Straßennetze, Abhängigkeitsgraphen und Ablaufpläne sind keine Gitter — dafür ist [[lyx_-_programmiersprache:units:graph|std.graph]] da, das Dijkstra und Bellman-Ford auf allgemeinen Graphen bietet. Umgekehrt hat ''std.graph'' **kein** A*; die zielgerichtete Suche gibt es nur hier.
Jump-Point-Search als Aufsatz auf ''GridAStar'' gibt es nicht — er lohnt ohnehin nur bei gleichteuren Zellen.
----
Letzte Aktualisierung: 2026-08-16 · alle Beispiele mit ''lyxc 1.0.21A'' übersetzt und ausgeführt; die Heuristik-Zulässigkeit einzeln nachgemessen, der A*-Weg Feld für Feld gegen die Gitterbelegung geprüft.