Thursday, April 20, 2017

Plan van aanpak

Plan van aanpak

Doel:
Een pathfinding algoritme maken in C# dat werkt in de Unity3D-engine, dat 4 verschillende items kan oppakken voordat het naar het eindpunt beweegt, terwijl het de kortst mogelijke route kiest.

Planning:
4 mei 2017:
Zonder bugs één item kunnen oppakken en dan naar de uitgang lopen.

11 mei 2017:
Twee vooraf bepaalde items kunnen oppakken en naar de uitgang lopen.

19 mei 2017:
Een lijst van 3 items ingeven, het algoritme zoekt een weg naar deze items en loopt naar de uitgang

23 mei 2017:
Een lijst van 3 items ingeven, het algoritme zoekt de kortste weg naar deze items en loopt naar de uitgang.

1 juni 2017:
Een onbeperkte lijst van items ingeven (boodschappenlijst?), het algoritme zoekt de kortste weg naar deze items en loopt naar de uitgang.

Thursday, April 13, 2017

Optimalisatie - Deel 3

De vorige keer kwam ik er achter dat het toevoegen van een tegel aan een List de bottleneck was van mijn applicatie. Daarom ben ik onderzoek gaan doen naar Lists in C#, en waarom ze zo langzaam zijn.

Ik stuitte op dit artikel: http://jacksondunstan.com/articles/3066
De schrijver had wat testjes gedaan met het schrijven en lezen van Lists en Arrays, en kwam tot conclusie dat Arrays vele malen sneller zijn dan Lists.



Dus toen besloot ik om de List te vervangen voor een Array. Ik voeg de tegel niet meer toe aan de List tijdens het creëren van de tegel, maar als alle tegels zijn gecreërd zoek ik alle objecten met de Tile-class en stop die in een Array.

Nu ga ik van 37 seconden naar 3.7 seconden voor het maken van een veld van 101x101 tegels!


Tuesday, April 11, 2017

Optimalisatie - deel 2

Bij velden groter dan 100x100 tegels duurde het erg lang om de applicatie te laden, en bij velden groter dan 250x250 tegels liep de applicatie vast. Dus om uit te zoeken waar dit aan lag ben ik gaan kijken hoe ik mijn for-loop kan optimaliseren.

Omdat bij het starten van de applicatie alles vastliep totdat het gehele veld was geinitialiseerd, ben ik gaan kijken of ik de tegels niet stukje voor stukje kon initialiseren, zodat de computer niet meteen vol op zijn donder krijgt.

Hiervoor ben ik gaan uitzoeken wat de volgorde van het uitvoeren van een script was, want ik wil dat eerst de absolute basis van de applicatie gestart is, voordat alle tegels worden toegevoegd. Ook moeten de tegels niet 100% van alle processorkracht opvreten, zodat de computer niet vastloopt of hangt.

Op de site van Unity stond gelukkig duidelijk uitgelegd wat de volgorde van een script in Unity is.

De functies die voor mij interessant zijn:

  1. Start() - In deze functie creeer ik alle tegels. Wordt 1x per script aangeroepen, als de applicatie wordt opgestart.
  2. Update() - Wordt ieder frame aangeroepen
  3. Coroutine() - Wordt ieder frame na de Update aangeroepen. Jij geeft aan wanneer dit start of stopt.

Ik besloot om de for-loop om tegels te creeren in een coroutine te zetten, zodat de applicatie eerst helemaal kan opstarten, en het visueel zichtbaar is hoe het veld van tegels wordt opgebouwd.

Hierdoor liep de computer niet meer vast bij grote aantallen tegels, maar de performance werdt niet beter. Daarom ben ik gaan uitzoeken waar de bottleneck nu zat, dit is te zien in het onderstaande filmpje:



Nu moet ik gaan uitzoeken hoe ik dit probleem ga overbruggen...


Tuesday, March 14, 2017

Optimalisatie

In het filmpje in de vorige post kon je zien dat een grid van 81x81 tegels bijna een minuut kostte om te laden. Dit kwam niet omdat het pathfinding algoritme zo heftig is, maar omdat ik niet slim omging met mijn code.
Ik ging bij iedere tegel door de lijst van alle tegels heen om te kijken of er buurtegels in de lijst zaten. Dus bij een grid van 51x51 tegels ging ik 2601 keer door die lijst heen, niet echt efficient!
Nu ga ik 1x door de lijst heen en bereken ik d.m.v. de index welke tegel er links, rechts, boven en onder ligt.

Ook heb ik de positie het doel (de frikandel speciaal) gerandomised, en animeer ik het pad naar het doel toe, om het allemaal wat dynamischer te maken.

Als je op spatie drukt wordt er een doolhof gegenereerd, en dat wordt daarna gecheckt of het doel te bereiken is. Als dat niet zo is wordt er een nieuw doolhof gegenereerd, net zo lang totdat het doel te bereiken is.

Ik had in de vorige post als doel gesteld om het pathfinding te optimaliseren, maar omdat ik dit nog niet helemaal snap, en de pathfinding in principe snel werkt, ga ik eerst kijken naar het implementeren van tussenstations. Dus het karakter moet naar bepaalde tussendoelen voordat het naar het einddoel mag lopen.


Friday, March 10, 2017

Het werkt !?!

Na een middag tutorials kijken en uitproberen ben ik zo ver gekomen dat ik het kortste pad naar een doel kan berekenen. Vooral deze tutorial-serie heeft mij veel geholpen:



Ik ben eerst de buur-tegels van iedere tegel gaan zoeken, en die gaan toevoegen aan een lijst van de desbetreffende tegel. Dus iedere tegel heeft een lijst van buurtegels. Omdat iedere tegel 1x1 groot is was dit redelijk makkelijk. Per tegel kijk ik welke tegel 1 unit boven, onder, links en rechts van die tegel ligt, en die voeg ik toe. Het is niet geoptimaliseerd, want hij loopt steeds door de hele lijst van tegels heen, maar het werkt.



Ik heb de diagonale tegels gecomment, omdat het pad dan soms door een muur heenloopt.

Daarna heb ik de g, h en f waardes bepaald van iedere tegel, zoals uitgelegd in de 2e post.

De g waarde is de afstand tot het startpunt
De h waarde is de afstand naar het doel
De f waarde zijn de g & h waardes opgeteld.

Daarna heb ik aan de hand van de YouTube tutorial hierboven het daadwerkelijke pathfinding geimplementeerd.



Uiteindelijk blijft er een lijst van tegels over die het pad vormen, die kleur ik dan rood om het pad aan te geven. Ook kleur ik de tegels die zijn "uitgeprobeert" door het algoritme geel. Hopelijk kan ik met wat optimalisatie zo min mogelijk gele tegels krijgen, maar dat is een volgende stap.

Dit is het resultaat tot nu toe:

Thursday, March 9, 2017

De eerste stappen

Als eerste moet er een vloer gemaakt worden waar het karakter over kan lopen, en waar de obstakels op geplaatst kunnen worden. Dit doe ik met een simpele for-loop die verschillende rijen van tegels maakt.




Dit is dan het resultaat.

(De texture voor de tegel heb ik hier vandaan gehaald.)

Hierna heb ik er voor gezorgt dat de camera centreert op de vloer, dat de tegels een child worden van het vloer-object, en dat ze aan een lijst met tegels worden toegevoegd.

Ook heb ik een start en eind tegel toegevoegd.





Ik heb een repository aangemaakt op GitHub zodat je kunt meekijken in de code:
https://github.com/Drtizzle/tijnartsCT/tree/master/CT%20Pathfinding/Assets/

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.