Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

Pathfinding

Engels: Pathfinding · Ook wel: pathing, path-finding

In het kort

Pathfinding (ook pathing genoemd) is een methode waarbij een computerprogramma de kortste route tussen twee punten berekent. Die methode is een praktischer vorm van het oplossen van een doolhof en werkt met een gewogen graaf, waarin elke verbinding een gewicht heeft. Het onderzoeksveld van pathfinding steunt sterk op het algoritme van Dijkstra voor het vinden van een kortste pad op een gewogen graaf.

Waarom is dit belangrijk?

Met pathfinding kunnen veel voertuigen en robots tegelijk een botsvrije route naar hun doel volgen, ook als hun taken elkaar overlappen. In magazijnen en op luchthavens sturen systemen zo rijdende machines die goederen of vliegtuigen verplaatsen. Medewerkers in die sectoren rekenen op die planning voor hun dagelijkse werk, maar bij grote drukte is een optimale oplossing soms te zwaar om tijdig te berekenen.

Zo werkt het in de praktijk

In computerspellen zit pathfinding in titels met bewegende objecten of NPC’s, niet-speelbare personages. Chris Crawford beschreef in 1982 hoe tanks in Tanktics vastliepen op land in U-vormige meren. Spelmakers plannen routes ook met een navigation mesh, een net van loopvlakken.

Onderzoekers zoeken snelle planning op grote kaarten met weinig processortijd. In 2004 stelden Botea en collega’s Hierarchical Path-Finding A* (HPA*) voor. HPA* deelt de kaart in clusters, zoekt een grove route en vult die per cluster aan.

In praktische reissystemen versnellen contraction hierarchies de routeberekening door het netwerk vooraf te vereenvoudigen. Bij een veranderende omgeving verfijnt Partial-Refinement A* (PRA*) alleen de eerste stappen. De rest van de route werkt het programma tijdens de uitvoering verder uit.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026