Thursday, March 9, 2017

Algoritmes

Ik had al eerder onderzoek gedaan naar pathfinding algoritmes en het geprobeerd te implementeren in een Unity3D applicatie, maar nog geen succes behaald. Om mijn geheugen weer op te frissen heb ik een paar YouTube filmpjes bekeken die in makkelijke taal uitleggen hoe het Dijkstra, en het A* pathfinding algoritme werken. De meest informatieve en vermakelijke uitleg vond ik op het YouTube kanaal Computerphile (waar ik overigens al op geabonneerd was).



Dijkstra Algoritme

Bij het Dijkstra algoritme verdeel je de mogelijke routes in met "nodes". Dit zijn meetpunten waartussen de afstand wordt gemeten, en als er meerdere routes zijn vanaf die node wordt berekend wat de volgende stap wordt.
De cijfers die op de lijnen staan zijn de afstanden tussen de nodes, dus de visuele representatie van de afstand klopt niet met de werkelijke afstand.


Het nadeel van dit algoritme is dat het één richting kiest, en dan alle mogelijkheden uitprobeert om te kijken welke route het kortste is. Dit is totaal niet efficiënt, maar meer een "brute-force" manier om de route te bepalen. Vooral als er veel richtings-mogelijkheden zijn die dicht bij elkaar liggen kan dit veel onnodige berekeningstijd kosten.

A* Algoritme

Het A* algoritme is een uitbreiding van het Dijkstra algoritme, en werkt efficienter. Bij het A* algoritme wordt per node ook de fysieke afstand van die node tot het doel toegevoegd als variabele. Als je de afstand tot het doel en de afstand tot de volgende node samenvoegt, krijg je data waarmee je sneller nodes uit de lijst kunt verwijderen zodat die niet meer berekend worden. Dit wordt duidelijker uitgelegd in het YouTube filmpje hierboven.

Plan

Nu is mijn plan om in Unity3D met C# een karakter van node naar node te laten lopen, zonder te kijken wat de kortste route is. Zolang het karakter het doel bereikt is het goed. Als dit is gelukt wil ik het Dijkstra algoritme toepassen om de eerste stappen te zetten in pathfinding.

No comments:

Post a Comment