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

→ Mathematik-Units · std.graph · 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.

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.

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

<WRAP alert> 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. </WRAP>

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.

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.

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.

std.grid rechnet auf Gittern. Straßennetze, Abhängigkeitsgraphen und Ablaufpläne sind keine Gitter — dafür ist 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.