Game-AI moet voortdurend ruimtelijke vragen beantwoorden. Waar is de dichtstbijzijnde dekking? Hoe ver kan deze eenheid bewegen voordat hij een obstakel raakt? Welke richting moet een vijand die strafing uitvoert nemen om een bepaalde afstand tot de speler te behouden? SDF’s maken van elk van die vragen een veldevaluatie: één getal geeft de speling, en één gradiënt geeft de richting. Dit artikel behandelt de drie belangrijkste navigatieworkloads, omgevingsafstandsvelden voor speling- en plaatsingsquery’s, gradiëntgebaseerde sturing voor obstakelvermijding en stroomvelden voor menigtebeweging, en vergelijkt de hele benadering met traditionele navigatiemeshes.

Voor de basis van hoe teken en gradiënt werken, begin met het Signed Distance Fields overzicht . Voor de engine-brede context, zie SDF’s in game-ontwikkeling .

Omgevingsafstandsvelden als Navigatiedata

Een traditionele navigatiemesh slaat beloopbare polygoonregio’s op met connectiviteitsinformatie. Een afstandsveld slaat op elk punt in de ruimte de afstand tot het dichtstbijzijnde obstakel op. Die extra informatie maakt query’s mogelijk die een navmesh niet efficiënt kan beantwoorden.

Het meest bruikbare veld voor navigatie is het unsigned distance field van obstakelgeometrie, het environmental distance field (EDF). Op elke wereldpositie geeft het EDF terug hoe ver de dichtstbijzijnde muur of het dichtstbijzijnde obstakel verwijderd is. Een waarde van 2,0 betekent dat de agent 2 meter speling heeft in alle richtingen. Merk op dat het veld hier unsigned is: navigatie hoeft alleen te weten hoe ver een punt van het dichtstbijzijnde obstakel verwijderd is, niet of het erbinnen ligt, omdat beloopbare ruimte wordt gedefinieerd als buiten alle obstakels zijn.

Dit ondersteunt direct:

• Spelingquery’s: kan een eenheid met straal $r$ een positie innemen zonder een obstakel te raken? Controleer of $\text{EDF}(\mathbf{p}) \geq r$.
• Dekkingsselectie: sample kandidaatposities en kies degene met de beste combinatie van afstand tot de vijand, afstand tot het dichtstbijzijnde dekkingsoppervlak en line-of-sight-eigenschappen.
• Flankeringspaden: bereken een pad dat een minimale afstand tot een obstakel aanhoudt in plaats van langs de grens te scheren.

Elk van deze zou herhaalde closest-point-zoekopdrachten tegen een mesh vereisen. Tegen een EDF zijn het enkele evaluaties, daarom is het voorbakken van een EDF voor statische levelgeometrie en het per agent query’en ervan het standaardpatroon.

Gradiëntgebaseerde Sturing

De gradiënt van het environmental distance field wijst naar het dichtstbijzijnde obstakel. Voor een eenheid die een vaste afstand tot een muur wil bewaren, kan de stuurkracht aantrekking langs het navigatiepad combineren met repulsie van obstakeloppervlakken:

vec3 obstacleSteering(vec3 position, SDF environment, float preferredDistance) {
    float d = evaluateSDF(position, environment);
    if (d > preferredDistance * 2.0) return vec3(0.0);  // Too far to care

    vec3 gradient = normalize(gradientSDF(position, environment));

    // Push away if too close, pull toward if too far
    float error = d - preferredDistance;
    float strength = clamp(abs(error) / preferredDistance, 0.0, 1.0);
    return strength * sign(error) * gradient;
}

Wanneer de eenheid dichterbij is dan de voorkeursafstand, is de fout negatief en duwt de kracht hem weg van het obstakel. Wanneer hij verder weg is, trekt de kracht hem naar het obstakel toe. De grootte loopt lineair op van nul bij de voorkeursafstand tot volledige sterkte wanneer de afstandsfout gelijk is aan de voorkeursafstand. Dit creëert vloeiend, natuurlijk ogend muurvolggedrag zonder expliciete padsegmenten.

Een uitgewerkt voorbeeld: voorkeursafstand 1,0. Op een positie waar het EDF 0,7 leest, is de eenheid 0,3 dichterbij dan de voorkeur, is de fout -0,3, is de sterkte 0,3 en is de kracht 0,3 eenheden in de richting weg van het obstakel. Bij een EDF-waarde van 1,4 is de eenheid 0,4 te ver, is de fout +0,4 en trekt de kracht hem 0,4 eenheden terug naar het obstakel. Tussen de twee uitersten gaat de kracht precies door nul bij de voorkeursafstand, zodat de eenheid zich in een stabiele offset nestelt: geen oscillatie, omdat de krachtgrootte krimpt naarmate de fout krimpt.

Gradiëntgebaseerde sturing combineert met padvolging: het pad levert een richting, de EDF-sturing levert de obstakeloffset, en de twee vectoren worden met gewichten gemengd. Eenheden die een corridorwand volgen sturen er simpelweg langs, en de voorkeursafstandsparameter doet dubbel dienst als menigteafstandsregelaar wanneer eenheden dezelfde waarde delen.

Stroomvelden voor Menigtebeweging

Voor grote aantallen agenten wordt het berekenen van individuele paden duur. Een stroomveld vervangt per-agent-padzoeken door een enkel globaal vectorveld dat elke agent volgt. Het stroomveld wordt opgebouwd door de Eikonaalvergelijking op te lossen vanuit doellocaties, wat een afstandsveld vanaf het doel produceert. Op een grid wordt dit berekend met het Dijkstra-algoritme of een fast marching-methode: elke cel slaat de opgebouwde reiskosten naar het doel op, en de stroomrichting bij een cel wijst naar de buur met de laagste kosten, naar het doel toe.

Agenten lezen eenvoudig de stroomrichting op hun huidige positie en bewegen. Afstandscontroles bij het doel stoppen hen wanneer ze aankomen. Het veld wordt alleen herberekend wanneer obstakels of doelen veranderen, wat het veel goedkoper maakt dan het uitvoeren van individuele A*-zoekopdrachten voor honderden eenheden.

Deze techniek wordt gebruikt in real-time strategy games, tower defense games en elk scenario met dichte menigten van onafhankelijk bewegende eenheden. De gemene deler is dat het afstandsveld dubbel werk doet: de waarden coderen de padlengte naar het doel, en de gradiënt codeert de richting van de volgende stap.

Afstandsvelden vs Navigatiemeshes voor Padzoeken

Eigenschap	Navigatiemesh	Afstandsveld
Query voor afstand tot dichtstbijzijnde obstakel	Closest-point-zoekopdracht op polygonen	Enkele veldevaluatie
Speling op een punt	Benaderd of per polygoon	Exact uit het veld
Padzoeken	A* over polygoongraaf	Dijkstra of A* over grid, of stroomveld
Geheugen	Compacte polygoondata	Gridsamples, resolutieafhankelijk
Dynamische obstakels	Regio’s herbouwen	Veld herberekenen of lokaal bijwerken
Muurvolggedrag	Padvereffeningstrucs	Natuurlijke gradiëntsturing

De twee representaties zijn in de praktijk complementair. Navmeshes blinken uit in padzoeken over lange afstanden met schaarse, efficiënte grafen, en zijn de standaardkeuze wanneer agenten exacte beloopbare regio’s nodig hebben met doorgangen, deuren en trappen. Afstandsvelden blinken uit in lokale beslissingen: spelingcontroles, obstakeloffset en dichte menigte-routing. Een productie-AI-systeem gebruikt vaak beide, een navmesh voor globale routes en een voorgebakken EDF voor lokale sturing en plaatsing.

De belangrijkste beperking van de afstandsveldbenadering is geheugen- en updatekost. Een 3D-EDF over een groot level verbruikt geheugen dat afhankelijk is van de gridresolutie, en het voorbakken is een voorbewerkingsstap die moet worden herhaald wanneer het level verandert. Dit zijn dezelfde afwegingen als behandeld in voorgebakken signed distance fields , hier toegepast op navigatiedata in plaats van renderingdata.

Samenvatting

Navigatie zet het SDF-contract om in drie AI-workloads:

• Speling- en plaatsingsquery’s lezen EDF-waarden direct: is deze plek veilig voor een eenheid met straal $r$?
• Gradiëntgebaseerde sturing gebruikt de EDF-gradiënt als een signed foutsignaal dat te dichtbij zijnde eenheden wegduwt en te ver weg zijnde eenheden naar de voorkeursoffset trekt.
• Stroomvelden zetten de Eikonaalvergelijking om in een enkel globaal vectorveld dat hele menigten routeert.

Dezelfde voorgebakken veldrepresentatie voedt de botsingsquery’s die op dezelfde statische levelgeometrie draaien, zodat één bake zowel het AI-systeem als het fysicasysteem bedient.