Opdracht

	Algemene introductie:

	We beginnen met een set van acht primitieve doolhoven. Deze doolhoven zijn in het begin nog niet uitdagend, 
	en zullen naar mate de evolutie vorderd steeds complexer en interessanter van aard worden. Om op dit niveau 
	terecht te komen, nemen we deze vantevoren gedefinieerde doolhoven naar de volgende stap.

	De filosofie achter een genetische algoritme is de "survival of the fittest". Het belangrijkste element voor 
	dit algoritme is de evaluatie functie. Deze evaluatie functie controleert de huidige set van acht doolhoven, 
	en laat een gegeven maximum aantal kandidaten door naar de volgende stap. Dit leidt naar de genetische algoritme 
	zelf.

	Nadat de set van beste kandidaten is aangekomen aan de poort van evolutie, dan kunnen er drie dingen gebeuren. 
	Deze zijn als volgt: cross-over, cloning en mutation. Cross-over houdt in dat de kandidaat een andere kandidaat 
	toegewezen krijgt, en deze zullen zich met elkaar mengen. Zoals de quote van Nokia: connecting people. De cloon 
	is het exacte duplicaat van zijn voorganger. Nadat een cross-over of een cloon is gegenereerd, bestaat er nog 
	een kleine kans dat er een mutatie plaatsvind. Bij de mutatie worden kleine aanpassingen gemaakt.

	Hierna wordt de oude set van ouders ge-elimineerd en begint de evolutionaire cirkel overnieuw met de evaluatie 
	van de nieuwe generatie.


	Omschrijving:
	
	Het bouwen van een genetische doolhofgenerator in Python.

	De opdracht bestaat uit vijf delen:
		* Breadth First Search Algorithm
		* Genetisch Algoritme
		* Cellulaire Automata
		* Sorteeralgoritme
		* Animatiefunctie
		* Statistiek

	Deze punten zijn hieronder toegelicht:
		

	De random doolhof generatie functie:
		Random
	Motivatie:
		Geimplementeerd volgens de pricipes van het Genetic Algoritm
	De werking:
		Berekend per vakje een gegeven kans op een muur, standaard 25%

		
	De evaluatie functie:
		Breadth-First Search algorithm
	Motivatie:
		Het Breadth-First algoritme leent zich uitstekend voor het evalueren van meerdere belangrijke aspecten van 
		doolhoven. Een functionele doolhof moet minimaal 1 ingang, 1 uitgang hebben, en 1 mogelijke doorgang bevatten. 
		Ook kan met behulp van dit algoritme de lengte van de weg geteld worden.
	De werking:
		Breadth-First pakt een node uit de queue. Vervolgens bekijkt het de vervolg nodes, en stopt deze ook allemaal 
		in de queue. Tegelijkertijd worden deze nodes gemarkeerd als 'bezocht', zodat toekomstige vervolg nodes die 
		al gemarkeerd zijn als bezocht, niet nogmaals afgelopen worden. Dit om veel onnodige recursie te voorkomen. 
		Hierna begint het algoritme weer van voor af aan.

	
	De evolutie functie:
		Genetic Algorithm
	Motivatie:
		We wilden een niet-lineaire biologische doolhof structuur genereren, in plaats van de standaard en veel 
		rekenkundig complexere methoden, zoals met behulp van slechts een cellulaire automata. We hebben ook fractals 
		overwogen, maar deze genereren zowiezo geen uitdagende doolhoven, alleen langdurig (afhankelijk van de diepte).
	De werking:
		In pseudo-code:
	
			Choose initial population
			Repeat
				Evaluate the individual fitnesses of a certain proportion of the population
				Select best-ranking individuals to reproduce
				Mate pairs at random
				Apply crossover operator
				Apply mutation operator
			Until terminating condition 
			
	
	De print functie:
		Cellulaire Automata
	Motivatie:
		Mensen houden van eye-candy, dus alles moet eruit zien "just dandy". We kunnen bij organische doolhoven 
		niet zomaar tekens vervangen om het als een mooier geheel eruit te laten zien. Om de huidige cellen te 
		vervangen met toepasselijkere aansluitende tekens, moet rekening gehouden worden met de aanliggende cellen.
	De werking:
		Per cel, controleer neighbours, kies de juiste nieuwe toestand en ga naar de volgende cel.

	
	Sorteer algoritme:
		Bubblesort, StupidSort, QuickSort, BogoSort
	Motivatie:
		Voor de implementatie van het Genetic Algorithm was het noodzakelijk het geevolueerde aantal kinderen 
		te sorteren van goed naar slecht (op basis van heuristiek). Hiervoor gebruikten we oorspronkelijk alleen 
		BubbleSort, maar na enig grondig research, stuitten we op enkele meer exotische zoekalgoritmes. Alle 
		bovenstaande algoritmes zijn werkend geimplementeerd in onze code, maar voor de practische toepassing 
		gebruiken we de QuickSort, omdat dat het meest efficiente algoritme is.
	De werking:
		Er worden twee arrays meegegeven, te weten de qualified mazes Q en de heuristieken H. De QuickSort neemt de 
		middelste waarde in de array van heuristieken. Deze waarde heet de pivotwaarde. Vervolgens wordt alles in de 
		array opgesplits in drie array: less, equal en greater dan de pivotwaarde. Alle bijbehorende qualified mazes 
		in Q worden tegelijkertijd zodat ze nog steeds overeenkomen met hun heuristieken. De drie lijsten worden 
		recursief afgewerkt, en uiteindelijk samengevoegd en gereturned.
	
	
	Animatiefunctie:
		Print list
	Motivatie:
		We vonden het een leuk idee om het gevonden snelste weg door de geevolueerde doolhof te animeren.
	Werking:
		We maken gebruik van twee functies, generateWalkthrough die een list aanmaakt die alle coordinaten in het 
		snelste pad in de doolhof zet. Elke stap in een volledige doolhof is gescheiden met een "-". Vervolgens kan 
		deze list doorgegeven worden aan de functie animateList, die elke regel in de list wegschrijft in een andere 
		buffer list tot het een "-" tegenkomt, vervolgens de inhoud van de buffer op scherm schrijft, buffer leegt en 
		weer verder gaat. Het resultaat is een "animatie" op het scherm.

	
	Statistiek:
		Staafdiagram
	Motivatie:
		Om de voortgang van de evolutie te kunnen bestuderen, is een staafdiagram erg handig. Het geeft snel een 
		overzichtelijke weergave.
	Werking:
		Per generatie word de gemiddelde heuristiek opgeslagen. Het is mogelijk onafhankelijk van het aantal generaties 
		in te stellen hoeveel staven er weergegeven moeten worden.