Wat is Pathfinding?
Pathfinding is het zoeken naar een route van punt A naar punt B, met behulp van een computer. Vaak is het ook de bedoeling dat de kortste route gevonden wordt, en ook nog in een korte tijd. Een pathfinding-algoritme, of kortstepad-algoritme, moet dus de kortste route in de kortste tijd zien te vinden. Pathfinding is nauw verbonden aan de Grafentheorie, de wiskundige tak die grafen bestudeert. Grafen zijn verzamelingen van punten die met lijnen verbonden zijn. Dit kan vergeleken worden met een kaart, de graaf, met wegen, de lijnen en de kruispunten van die wegen, de punten. Vaak worden aan de lijnen een getal toegekend, het gewicht van de lijn of de kosten om er langs te gaan. Er zijn veel toepassingen van pathfinding: navigatiesystemen en routeplanners, (strategie-)videospellen en zelfs het internet. Pathfinding is een belangrijke wetenschap en daarom zijn er ook verschillende algoritmen bedacht. Ik zal de twee bekendste algoritmen bespreken, het algoritme van Dijkstra en het A* (A-ster) algoritme, en tenslotte een uitleg van mijn eigen script.
Het algoritme van Dijkstra
Ontworpen in 1956 en gepubliceerd in 1959 door Edsger Dijkstra. Dit is het meest bekende algoritme en wordt vaak gezien als hét kortstepad-algoritme. Dit betekent niet dat dit ook het enige pathfinding-algoritme is. Het algoritme van Dijkstra wordt gebruikt door verschillende internetprotocollen, voor het vinden van de kortste route tussen computers of routers. Het algoritme van Dijkstra geeft gegarandeerd het kortste pad, als er überhaupt een pad tussen A en B bestaat, maar kan hier wel lang over doen. De snelheid van het algoritme is afhankelijk van de manier waarop de punten en lijnen opgeslagen zijn in het geheugen van de computer. De meest optimale manier is doormiddel van een Fibonacci-hoop, waarop ik niet verder in zal gaan, in dat geval is de snelheid: O(|E| + |V|×log|V|), waarbij |E| het aantal lijnen is en |V| het aantal punten. O() is een manier om de snelheid van een algoritme of functie uit te drukken. Wanneer deze zijn opgeslagen als een lineaire lijst, een set gegevens die te bereiken zijn via een numerieke index, is de snelheid O(|V|²) hierbij heeft het aantal lijnen dus geen invloed, maar het is wel veel langzamer. Dat de prestaties van het algoritme afhankelijk zijn van de manier waarop de data opgeslagen, of preciezer: gerepresenteerd wordt, komt door de manier waarop de computer met deze gegevens te werk gaat. De verschillende representaties hebben elk een andere manier van nieuwe gegevens toevoegen, gegevens opvragen of vinden en gegevens verwijderen.
Hoe het werkt
- Neem de set punten in de graaf, die noemen we Q, stel de afstand A(p) van elk punt in op oneindig, dit betekent dat het punt nog niet behandeld is.
- Maak een tweede set, R, die leeg is. Hierin komen de punten die we behandeld hebben.
- Punt S noemen we het startpunt, punt E het eindpunt, punt N het huidige punt. Stel A(S) = 0: de afstand van het startpunt naar het startpunt is 0. En N = S.
- Herhaal de volgende stappen totdat er geen punten meer in Q zitten.
- Bekijk elk punt, die noemen we P, die met 1 lijn verbonden is aan het huidige punt N, noem N de ouder van punt P: O(P) = N.
- Als P al in R zit, we hebben P dus al bekeken, sla de rest dan over en ga door naar het volgende buurpunt van N.
- Als P = E hebben we het kortste pad gevonden, ga nu naar stap 6.
- Stel de afstand van elk van deze punten, P, in op A(N) + a(P): de afstand van het huidige punt tot punt S + de afstand van P tot het huidige punt.
- Stop punt N in set R, die hebben we nu bekeken en hoeven we niet weer te bekijken.
- Laat punt N nu het punt zijn waarvan A(P) het kortste is. Dus: van alle punten die we bekeken hebben, stel die met de kortste afstand van S naar P, in als het huidige punt: N.
- Als Q leeg is, er zijn geen punten meer over, en we hebben het eindpunt niet gevonden, is er geen pad.
-
Als we wel bij punt E zijn uitgekomen ga dan na via de ouders van punt P, O(P) wat het pad is: Doe het volgende totdat we punt S hebben bereikt:
- Noem Z de route van E naar S.
- Voeg P toe aan Z.
- Stel P = O(P): stel de ouder van P in als P.
Om dit abstracte verhaal te verduidelijken hier een:
Voorbeeld
Neem nu deze graaf:
![[X]](ex2-1.png)
Nu willen we van punt C naar punt A. Eerst kijken we naar alle punten die met 1 lijn verbonden zijn aan C, dit zijn D, F en B. De afstand van C → D is 14, D krijgt dus als afstandswaarde 14 toegekend, C → F = 9 en C → B is ook 9. Nu hebben we C behandeld en kijken we er niet meer naar. Nu kijken we naar het volgende punt met de kortste route, de kleinste waarde, (onthoud: in het begin hebben alle punten, behalve het startpunt, een afstandswaarde oneindig). We kijken naar B (F ligt even ver weg, dan gaan we maar op alfabetische volgorde). De omliggende punten zijn C, F en E. C hebben we al gehad, daar kijken we dus niet meer naar. F heeft al een afstandswaarde gekregen, we kijken of we via B een kortere route hebben: C → B → F = 9 + 10 = 19, dit is langer dan C → F ( = 9), dus laten we de kortere afstand staan. Dan kijken we naar E: die heeft nog een afstandswaarde oneindig dus vervangen we die waarde door C → B + B → E = 9 + 15 = 24. Nu hebben we alle punten die aan B liggen gehad en schuiven we B in de set punten die we behandeld hebben. De tussenstand is nu:
![[X]](ex2-2.png)
Nu kijken we weer welk van de overgebleven punten de kortste afstand heeft, dit is nu F (9). De punten om F heen, die we nog niet gehad hebben, zijn D en E. De afstand van F → D = 2, C → F → D = 11, dus: de route van C → D via F is korter dan de directe route. We overschrijven de waarde van D naar 11. Dan nu nog van F → E = 11, C → F → E = 9 + 11 = 20 dus de nieuwe waarde van E wordt nu 20. F is nu ook gedaan. Huidige tussenstand:
![[X]](ex2-3.png)
We hebben D en E nu nog over, eerst kijken we naar D. Het enige punt dat daar nu nog over is, is punt A, het eindpunt, de route van C → F → D → A = 9 + 2 + 6 = 17. A krijgt nu waarde 17, D is nu ook gedaan. Als we via E naar A gaan komen we uit op: C → F → E → A = 9 + 11 + 9 = 29. Dat is een langere route dus blijft A 17. De kortste route van C naar A is dus 17.
![[X]](ex2-4.png)
Het A* algoritme.
Het A* algoritme wordt het meest gebruikt in spellen en andere toepassingen waarbij accuraatheid minder belangrijk is dan snelheid. Dit algoritme is een uitbreiding op het algoritme van Dijkstra, door de toevoeging van een heuristische functie. Het A* algoritme kijkt niet alleen naar de afstand van een punt tot het startpunt, maar ook naar de geschatte afstand van dat punt naar het eindpunt. Het A* algoritme wordt niet toegepast op een graaf, maar op een rooster, hierbij komen de hokjes, cellen, overeen met de punten en is er vaak een vaste prijs om van de ene cel naar de andere te gaan. Sommige cellen vormen obstakels waar het algoritme een pad omheen moet vinden, dit komt in ieder strategie-videospel voor. Het is ook bijna niet te doen het A* algoritme toe te passen op een graaf omdat het vrijwel onmogelijk een heuristische functie te maken die werkt op een graaf.
Wat een heuristische functie nu precies is
De heuristische functie berekent een geschatte afstand van een punt tot het eindpunt. Het is niet de bedoeling dat deze afstand precies overeen moet komen met de werkelijke afstand, die berekenen kost bijna altijd net zoveel als het pad vinden zonder heuristische functie. Een heuristische functie houdt meestal juist geen rekening met obstakels. Wanneer de heuristische functie een afstand oplevert die kleiner is dan de werkelijke afstand, dit gebeurt het vaakst vanwege obstakels, zal het algortime meer cellen bekijken maar levert het nog steeds gegarandeerd het kortste pad op. Wanneer de heuristische afstand precies even groot is als de werkelijke afstand zal het A* algoritme het snelst werken omdat het alleen de cellen bekijkt die op het uiteindelijke pad liggen, wanneer de heuristische functie een 'perfecte' waarde oplevert zal het A* ook perfect werken. Als de heuristische afstand groter is dan de werkelijke afstand kan het zo zijn dat het kortste pad niet gevonden wordt, maar werkt het algoritme wel sneller. Een bekend en veelgebruikte heuristische functie is de Manhattan-afstand. Deze functie berekent de H(p) waarde op basis van een rechte lijn van p naar het eindpunt. Manhattan-afstand: H(p) = (|xp - xeind| + |yp - yeind|)×kostenmin.
Hoe het A* algoritme werkt
In feite is het A* algoritme maar een kleine verandering op het algoritme van Dijkstra, daarom zal ik niet alle stappen hier nog een keer opnoemen. Het enige dat verandert is dat de kosten om naar een bepaald punt, of bepaalde cel te gaan niet alleen wordt bepaald door de afstand tussen dat punt en het startpunt maar ook de heuristische afstand. Nu wordt aan elk punt een waarde toegekend: F(p) = A(p) + H(p), waarbij F(p) de kosten van het punt is, A(p) de afstand tussen het punt en het startpunt en H(p) de waarde van de heuristische functie voor dat punt is.
Een voorbeeld met een rooster
Zie het volgende rooster:
| # | # | # | # | # | # | # | # | # | # | # |
| # | # | |||||||||
| # | # | # | ||||||||
| # | S | # | E | # | ||||||
| # | # | # | ||||||||
| # | # | |||||||||
| # | # | # | # | # | # | # | # | # | # | # |
Nu willen we van S naar E. Voor het gemak spreken we af dat we alleen in rechte lijnen kunnen bewegen, dus: alleen naar links, rechts, boven en onder.
| # | # | # | # | # | # | # | # | # | # | # |
| # | # | |||||||||
| # | A:1 H:7 | # | # | |||||||
| # | A:1 H:7 | S | A:1 H:5 | # | E | # | ||||
| # | A:1 H:7 | # | # | |||||||
| # | # | |||||||||
| # | # | # | # | # | # | # | # | # | # | # |
We kijken eerst naar S, naar de cellen eromheen. Elke cel krijgt een A(p) van 1: immers ze liggen 1 stap van het beginpunt af. Dan kijken we naar de heuristische afstand die is voor de cel links van het startpunt 5 en voor de anderen 7. Voor de linkercel is de F-waarde, de totale kosten, 6 en voor de anderen 8, de linkse kost het minst en daar gaan we dus verder mee. Punt S is gesloten.
| # | # | # | # | # | # | # | # | # | # | # |
| # | # | |||||||||
| # | A:1 H:7 | A:2 H:6 | # | # | ||||||
| # | A:1 H:7 | S | A:1 H:5 | A:2 H:4 |
# | E | # | |||
| # | A:1 H:7 | A:2 H:6 | # | # | ||||||
| # | # | |||||||||
| # | # | # | # | # | # | # | # | # | # | # |
Wederom is de linkercel de beste route.
| # | # | # | # | # | # | # | # | # | # | # |
| # | # | |||||||||
| # | A:1 H:7 | A:2 H:6 | A:3 H:5 |
# | # | |||||
| # | A:1 H:7 |
S | A:1 H:5 | A:2 H:4 |
# | E | # | |||
| # | A:1 H:7 | A:2 H:6 | A:3 H:5 |
# | # | |||||
| # | # | |||||||||
| # | # | # | # | # | # | # | # | # | # | # |
Hier links is een muur en alle andere open cellen hebben dezelfde F-waarde: 8. Om dit op te lossen kijken we nu alleen naar de laagste H-waarde, de cellen die waarschijnlijk het dichtst bij het eindpunt liggen, dan houden we er 2 over: boven en onder de laatst bekeken cel. We gaan naar de onderste cel kijken, gebaseerd op een willekeurige keuze.
| # | # | # | # | # | # | # | # | # | # | # |
| # | # | |||||||||
| # | A:1 H:7 | A:2 H:6 | A:3 H:5 |
# | # | |||||
| # | A:1 H:7 |
S | A:1 H:5 | A:2 H:4 |
# | E | # | |||
| # | A:1 H:7 | A:2 H:6 | A:3 H:5 |
# | # | |||||
| # | A:4 H:6 | # | ||||||||
| # | # | # | # | # | # | # | # | # | # | # |
Hoewel de zojuist ontdekte cel dichterbij het eindpunt ligt, is de F-waarde wel 10 en dat is groter dan alle andere die we bekeken hebben. Dus kijken we naar de andere cel, die boven de vorige cel ligt. Die kost evenveel, 4 + 6, dus gaan we naar een andere cel, die met de laagste F-waarde en H-waarde.
| # | # | # | # | # | # | # | # | # | # | # |
| # | A:2 H:8 | A:3 H:7 | A:4 H:6 | # | ||||||
| # | A:2 H:8 | A:1 H:7 | A:2 H:6 | A:3 H:5 | # | # | ||||
| # | A:1 H:7 | S | A:1 H:5 | A:2 H:4 | # | E | # | |||
| # | A:2 H:8 | A:1 H:7 | A:2 H:6 | A:3 H:5 | # | # | ||||
| # | A:2 H:8 | A:3 H:7 | A:4 H:6 | # | ||||||
| # | # | # | # | # | # | # | # | # | # | # |
Alle open cellen hebben een F-waarde van 10, dus kijken we weer naar de laagste H-waarde. Dat is A:4, H:6, laten we weer naar de onderste cel kijken.
| # | # | # | # | # | # | # | # | # | # | # |
| # | A:2 H:8 | A:3 H:7 | A:4 H:6 | # | ||||||
| # | A:2 H:8 | A:1 H:7 | A:2 H:6 | A:3 H:5 | # | # | ||||
| # | A:1 H:7 | S | A:1 H:5 | A:2 H:4 | # | E | # | |||
| # | A:2 H:8 | A:1 H:7 | A:2 H:6 | A:3 H:5 | # | # | ||||
| # | A:2 H:8 | A:3 H:7 | A:4 H:6 | A:5 H:5 | # | |||||
| # | # | # | # | # | # | # | # | # | # | # |
Nu wordt het weer wat makkelijker, de F-waarden van alle cellen zijn nog steeds gelijk, maar de cel die we daarnet hebben ontdekt heeft wel de laagste H-waarde, daar gaan we mee verder.
| # | # | # | # | # | # | # | # | # | # | # |
| # | A:2 H:8 | A:3 H:7 | A:4 H:6 | # | ||||||
| # | A:2 H:8 | A:1 H:7 | A:2 H:6 | A:3 H:5 | # | # | ||||
| # | A:1 H:7 | S | A:1 H:5 | A:2 H:4 | # | E A:10 | # | |||
| # | A:2 H:8 | A:1 H:7 | A:2 H:6 | A:3 H:5 | # | A:7 H:3 | A:8 H:2 | A:9 H:1 | A:10 H:2 | # |
| # | A:2 H:8 | A:3 H:7 | A:4 H:6 | A:5 H:5 | A:6 H:4 | A:7 H:3 | A:8 H:2 | A:9 H:3 | # | |
| # | # | # | # | # | # | # | # | # | # | # |
Zo hebben we het pad gevonden.
| # | # | # | # | # | # | # | # | # | # | # |
| # | A:2 H:8 | A:3 H:7 | A:4 H:6 | # | ||||||
| # | A:2 H:8 | A:1 H:7 | A:2 H:6 | A:3 H:5 | # | # | ||||
| # | A:1 H:7 | S | A:1 H:5 | A:2 H:4 | # | E A:10 | # | |||
| # | A:2 H:8 | A:1 H:7 | A:2 H:6 | A:3 H:5 | # | A:7 H:3 | A:8 H:2 | A:9 H:1 | A:10 H:2 | # |
| # | A:2 H:8 | A:3 H:7 | A:4 H:6 | A:5 H:5 | A:6 H:4 | A:7 H:3 | A:8 H:2 | A:9 H:3 | # | |
| # | # | # | # | # | # | # | # | # | # | # |
Nog een toevoeging: dit gebeurde niet in dit voorbeeld, omdat we alleen recht bewogen, maar wanneer een reeds geopende cel opnieuw bezocht wordt kijken we of de huidige weg, dus van het startpunt via de huidige cel naar de bekeken cel, sneller is.
Mijn eigen maaksel
Tenslotte wil ik nog mijn eigen script bespreken. Ik heb het gemaakt vóórdat ik me erg heb verdiept in Dijkstra en A*, in retrospect is mijn eigen maaksel vrijwel hetzelfde als het algoritme van Dijkstra. Het grootste verschil is de manier waarop ik de reeds verkende route bijhoud. Het is geschreven in Javascript maar ik zal het regel-voor-regel uitleggen. Er is meer code dan ik hier bespreek, maar dit is het gedeelte dat het eigenlijke pad-vinden doet.
KortstePad: function(start, eind){
var routes = [], dezeLijn, dezeRoute, kortste, nieuweRoute, x, y;
We beginnen met het declareren van de KortstePad-functie, die neemt 2 parameters, namelijk het begin- en eindpunt. Daarna declareren we de lijst, array, routes die nu leeg is. Verder declareren we nog een aantal andere variabelen die we later zullen gebruiken, het is gebruikelijk alle variabelen aan het begin van een functie te declareren.
for(x = 0; x < start.lijnen.length; x++){
dezeLijn = start.lijnen[x];
// Elke lijn is een nieuwe Route
dezeRoute = new Padvinder.Route();
routes.push(dezeRoute);
dezeRoute.voegLijnToe(dezeLijn, dezeLijn.anderePunt(start));
}
/*
De routes array is nu gevuld met alle punten die 1 punt verder dan het startpunt zijn
Nu gaan we langs die Routes en breiden we ze uit met de Lijnen en Punten die aan die punten liggen
*/
Nu gaan we eerst alle lijnen bij langs die aan het beginpunt, start, zitten. Elk Punt-object heeft een attribuut lijnen, dit attribuut is een lijst met alle lijnen die aan dit punt zitten.
De for-functie is een speciale functie die in vrijwel elke programmeertaal voorkomt, het begint met de initalisatie van een variabele, in dit geval x daarna komt de voorwaarde, in dit geval: zolang x kleiner is dan het aantal lijnen aan start, en tenslotte de opdracht, in dit geval: verhoog de waarde van x met 1 (x++ is een verkorte manier van schrijven voor x = x + 1).
De volgende regels code, die tussen de { en } moeten worden uitgevoerd zolang de for-lus loopt. dezeLijn is nu een verwijzing naar de lijn die we nu behandelen, dit is eigenlijk alleen maar om niet de hele tijd start.lijnen[x] te hoeven typen.
Als ergens in de code // voorkomt betekent het dat de rest van die regel commentaar is, het wordt genegeerd door de computer. dezeRoute is een nieuwe Route, daarna voegen we dezeRoute toe aan de lijst met routes, tenslotte voegen we dezeLijn toe aan de dezeRoute.
De andere parameter dezeLijn.anderePunt(start) verwijst naar het punt op dezeLijn dat tegenover start ligt.
De tekst tussen /* en */ is ook een manier van commentaar, het wordt dus genegeerd door de computer, maar dit keer over meer dan 1 regel.
x = 0;
kortste = null; // De tot-dan-toe kortste Route die al klaar is
while(x < routes.length){
dezeRoute = routes[x];
Nu gaan we x hergebruiken, en stellen we kortste op null. Null is een speciale waarde in Javascript, het is niet hetzelfde als nul (0), maar een indicator dat de variabele leeg is.
De while-functie is een simpelere vorm van de for-functie (of preciezer: de for-functie is een uitgebreidere vorm van de while-functie). De code tussen de { en } wordt uitgevoerd zolang aan de voorwaarde tussen de haakjes voldaan wordt, in dit geval: zolang x lager is dan het aantal routes dat we hebben.
dezeRoute is nu een verwijzing naar routes[x].
// Deze route is klaar
if(dezeRoute.puntB == eind){
// Nieuwe kortste Route
if(dezeRoute.lengte < kortste || kortste === null){
kortste = dezeRoute.lengte;
}
x++;
continue;
}
Eerst kijken we of we het eindpunt hebben bereikt, in een Route-object verwijst puntB altijd naar het eindpunt van de route, als puntB het eind-punt is (het punt waarnaar we zochten) is de route klaar. Dan kijken we of de totale lengte van dezeRoute korter is dan de tot-nu-toe kortste bekende route, óf als kortste gelijk is aan null (oftewel: dit is de eerste route die klaar is). Als dat zo is, is de lengte van dezeRoute de kortste route.
Dan verhogen we x met 1, zodat we met de volgende iteratie van de while-lus naar de volgende route kijken.
continue betekent dat de rest van de code tussen de {-haakjes níet moet worden uitgevoerd maar dat de computer terug moet gaan naar het begin, de voorwaarde opnieuw evalueren en de code voor de while-lus weer vanaf het begin moet uitvoeren. (Het lijkt raar dat dit commando dan continue heet, maar er is ook nog een opdracht break, die zorgt dat de lus helemaal wordt afgebroken en dat de computer dus doorgaat na de }).
// Als deze Route (nu al) langer is dan de kortste, sla 'm dan over
if(kortste !== null && dezeRoute.lengte > kortste){
x++;
continue;
}
Nu kijken we of deze route, die nog niet klaar is, langer is dan de tot-nu-toe kortste route, als dat zo is moet hij overgeslagen worden omdat hij alleen nog langer kan worden.
Net als bij de vorige if verhogen we x met 1 en gaan we weer terug naar het begin van de lus.
/*
Ga langs alle lijnen en maak nieuwe Routes van alle lijnen die niet teruglopen naar een Punt waar we al geweest zijn
*/
for(y = 0; y < dezeRoute.puntB.lijnen.length; y++){
dezeLijn = dezeRoute.puntB.lijnen[y];
// Deze lijn gaat terug
if(dezeRoute.pad.indexOf(dezeLijn.anderePunt(dezeRoute.puntB)) != -1){
continue;
}
nieuweRoute = dezeRoute.kloon();
nieuweRoute.voegLijnToe(dezeLijn, dezeLijn.anderePunt(dezeRoute.puntB));
routes.push(nieuweRoute);
}
x++;
} // Einde while-lus
Zoals de commentaar al zegt: nu gaan we langs alle lijnen aan het laatste punt van deze route.
We beginnen een nieuwe lus, dit keer met y en stellen dezeLijn als de huidige lijn. Dan kijken we of het andere punt aan de lijn al in de route zit, dat betekent dat de lijn terug gaat, dus slaan we die over zodat we niet in rondjes gaan lopen.
Dan maken we een kopie van dezeRoute en plakken we dezeLijn daar aan vast. Dan voegen we die route toe aan de lijst met routes.
Wanneer de for-lus afgelopen is verhogen we x weer en eindigt de while-lus ook.
// Haal nu alle lege elementen eruit en sorteer 'm op de lengte
routes = routes.filter(function(elm){ return (elm != null && elm.puntB == eind); }).sort(Padvinder.kortsteEerst);
return routes;
}
Nu we alle routes hebben gevonden halen we de lege routes en de routes die niet tot het eindpunt zijn gekomen eruit met de filter-functie en sorteren we die op de totale lengte van de route. Tenslotte retourneert de KortstePad-functie die lijst met routes, gesorteerd op lengte met de kortste route als eerst.
Conclusie
Pathfinding is een stuk belangerijker dan ik had verwacht. De twee algoritmen, die van Dijkstra en het A*-algoritme, zijn maar twee van vele algoritmen voor het vinden van het kortste pad. Deze algoritmen zijn wel de twee belangrijkste, bekendste en bijna alle anderen zijn gebaseerd op deze. Het algoritme van Dijkstra geeft altijd gegarandeerd het kortste pad, maar des te meer punten of cellen er zijn, des te langer doet het algoritme er over. Het algoritme van Dijkstra is de beste keuze wanneer het belangerijk is het kortste pad te vinden en de tijd waar die het algoritme nodig heeft niet belangrijk is. Het A*-algoritme geeft niet altijd het kortste pad, maar is bijna altijd sneller dan het algoritme van Dijkstra, daarom is het A*-algoritme beter wanneer het pad snel gevonden moet worden en het niet zoveel uit maakt als dat pad niet de kortst mogelijke is. Pathfinding is nog best moeilijk, het schrijven van mijn eigen algoritme kostte nog best veel tijd, maar vreemd genoeg niet meer tijd dan nodig was voor de hele testpagina eromheen. Eigenlijk had ik me nog wat meer willen verdiepen in het A*-algoritme en daar nog zelf een script voor schrijven, helaas is dat niet klaar gekomen.