Bachelorproef: 2D Grid Algorithms

Pathfinding

2011-05-21T21:37:00.000+02:00

Nadat ik de maze generation algoritmen afgewerkt heb ben ik begonnen aan de pathfinding algoritmen. Momenteel zijn DFS, BFS, Dijkstra en A* geimplementeerd.

De volgende afbeeldingen tonen de laatste stap en de oplossing van het A* algoritme. Witte cellen hebben een kost van 1 en de grijze cellen een kost 2. De kosten zijn echter vermenigvuldigd met 10 om het rekenen met kommagetallen te vermijden/beperken (hetgeen relatief veel tijd in beslag kan nemen).

Maze generation algoritmen geïmplementeerd

2011-04-18T21:09:00.001+02:00

Momenteel zijn de perfect maze generations algoritmen die besproken worden op ThinkLabyrinth geïmplenteerd.

Met uitzondering van Eller's algoritme zijn deze algoritmen ook al opgenomen in het verslag. Voor sommige algoritmen dien ik de complexiteit echter nog te (her)berekenen.

Eerste Algoritme

2011-03-24T20:43:00.001+01:00

Vandaag heb ik het eerste algoritme geïmplementeerd. Dit algoritme is het Recursive Backtracking maze generation algoritme. Het is ook mogelijk om het algoritme te visualiseren.

Visualisatie van het recursive backtracking algoritme: het groene vak is de start-locatie, het blauwe vak is de huidige cel. De gele vakken zijn posities die terug bezocht zullen worden tijdens de uitvoering (t.g.v. backtracking). De witte cellen zijn cellen die niet meer bezocht zullen worden.

Momenteel is de implementatie van het framework zo goed als af. De mogelijkheid om settings op te slaan en een grid op te slaan ontbreekt echter nog en er dienen

nog een aantal bugs opgelost te worden in verband met threads. Ook dienen er een paar wijzigingen gedaan te worden in de GUI zodat er meerdere threads tegelijk uitgevoerd kunnen worden.

Normaal gezien zou het implementeren van de algoritmes nu vrij vlot moeten gaan.

Implementatie framework

2011-02-22T09:40:00.000+01:00

Na het uitwerken van de structuur ben ik gisteren begonnen aan het implementeren van het framework.

Ontwerp

2011-02-11T14:48:00.000+01:00

Ik ben gisteren begonnen aan het uitwerken van een structuur voor het framework. Het voordeel van een framework is dat de algoritmen achteraf eenvoudig geïmplementeerd en getest kunnen worden, zonder dat er aanpassingen dienen te gebeuren aan de code voor het testen van de algoritmen en de grafische voorstelling van de algoritmen. Best zijn implementaties van de algoritmen niet te afhankelijk van het framework, zodat ze eenvoudig herbruikt kunnen in andere applicaties.