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.

Introductie

Ik heb besloten om voor Creative Technology mijzelf te verdiepen in pathfinding algoritmes, omdat ik daar tijdens het maken van games altijd tegenaan liep. Ik had moeite om de computergestuurde karakters op een intelligente manier door de spelwereld te laten bewegen, en te laten reageren op veranderingen in de omgeving.


Daarvoor heb ik een korte plan van aanpak opgesteld om tussentijds te kunnen meten of ik goed op weg ben om mijn doel te bereiken.


--------------------------------------------------------------------------------------------------------------------------

Plan van Aanpak

Leerdoel:
Het begrijpen en toepassen van een pathfinding algoritme.

Technologie:
Ik wil dit gaan uitvoeren in Unity3D met de C# programmeertaal.

Doel:
Een AI een lijst van objecten geven, zodat het daarna de kortste weg door een ruimte kan vinden om die objecten te pakken, terwijl het om obstakels heenloopt.

Plan:


  • Onderzoek naar verschillende soorten algoritmes
  • Bepalen welk algoritme geschikt is voor mijn doel
  • Bepalen welk algoritme haalbaar is om te leren binnen de beschikbare tijd
  • Implementeren van ontwijken obstakels
  • Implementeren van pakken objecten

--------------------------------------------------------------------------------------------------------------------------