Kunstmatige Intelligentie
Keuzeonderwerp V6 periode 1
Voor het keuzeonderwerp van periode 1 van V6 ga ik mij richten op 2 gebieden die wat met Kunstmatige Intelligentie te maken hebben, namelijk het maken van doolhoven en hoe de computer de weg kan vinden in deze doolhoven. Om dit project tot een goed einde te brengen heb ik me gehouden aan dit stappenplan:
- Orienteren op het gebied van doolhoven en padvind-algoritmes
- Algoritmen uitwerken en vaststellen wat het eindproduct (een goed afgewerkt werkend programma) nodig heeft om te kunnen functioneren.
- Het programmeren van het programma.
Het programma Maze+ inclusief bronbestanden en designsheet kun je hier downloaden. Als je geinteresseerd bent in de ontwikkeling van het programma kun je hieronder verderlezen.
De Orientatie
Het eerste wat ik deed was meer opzoeken over het onderwerp. Ik had al eerder hier en daar wat gelezen over doolhoven en het oplossen ervan, maar veel wist ik nog niet. Ik wist al wel dat je doolhoven grofweg kan indelen in twee categorieen: perfecte doolhoven en niet-perfecte doolhoven. Perfecte doolhoven hebben maar 1 ingang en 1 uitgang. Elk punt in het doolhof is te bereiken vanaf een ander punt, en er is altijd maar 1 weg om van A naar B te komen, wat ook automatische de kortste is. Ik had hier en daar al wat algoritmes bekeken voor dit type doolhoven, dus ik besloot mezelf uitsluitend te richten op deze algoritmes. Uiteindelijk heb ik deze 3 algoritmes uitgekozen: Prim's algoritme, het Hunt & Kill algoritme & het binaire algoritme. Ik ging ook nog zelf een algoritme maken voor een ideetje dat ik had: het muurgroeier-algoritme. Toen moest ik ook nog een pad-vind algoritme zoeken. Na een tijdje zoeken moest ik kiezen tussen deze twee algoritmes: het A* algoritme & Dijkstra's algoritme. Ik koos voor Dijkstra's algoritme, omdat het ietsje makkelijker te implementeren is, en bovendien gaat het A* er een beetje vanuit dat er een bepaalde logica zit in doolhoven, wat over het algemeen niet zo is waardoor je het dus als een mindere goede keus zou kunnen beschouwen.
Algoritmes uitwerken en programma vaststellen
Ik begon met het uitwerken van de algoritmes. Ik zal hieronder beschrijven hoe elk algoritme werkt.
Hunt & Kill
Het Hunt&Kill is het algoritme met de meest (naar mijn mening) interessante naam. Het algoritme is gebaseerd op dat van de recursive backtracker, en is redelijk snel met geheugengebruik recht evenredig met de grootte van het doolhof. Nadeel is dat het niet altijd redelijk interessante doolhoven produceerd, maar dat hoeft geen probleem te zijn. Als je van bovenaf het doolhof bekijkt is hij makkelijk, maar als je er zelf in zit is hij erg moeilijk.
- Neem een punt als startpunt. Maak deze het huidige hokje. Markeer deze als bezocht. Alle andere cellen zijn nog niet bezocht.
- Schakel naar "kill" modus.
- Herhaal:
- Kill modus:
- Zijn er onbezochte buren aangrenzend aan het huidige hokje?
- Zo ja, maak een verbinding tussen het huidge hokje en een willekeurig gekozen hokje door een muur weg te halen. Maak dat willekeurige hokje het huidige hokje.
- Zo nee, schakel naar "hunt" modus.
- Terug naar begin van de loop
- Hunt modus:
- Scan het veld op hokjes die nog niet bezocht zijn
- Zijn er hokjes die bezocht zijn en die grenzen aan bezochte hokjes?
- Zo ja, kies een willekeurig hokje uit die verzameling. Maak een verbinding tussen het gekozen hokje en een willekeurig bezochte buur. Schakel naar "kill" modus.
- Zo nee, dan is het doolhof af. Het algoritme stopt hier!
- Terug naar het begin van de loop
- Kill modus:
Binair
Bij een project voor informatica kan een subtiele referentie naar de binaire aard van de computer natuurlijk niet vergeten worden. Het binaire algoritme is het simpelst van alle algoritmes. Het is het snelst, en gebruikt geheugen recht evenredig aan de grootte van het doolhof. Nadeel is alleen: de doolhoven zijn echt heel erg simpel. Gelukkig heb ik de complexiteit van doolhoven niet als criteria gesteld.
- Voer uit op elke cel:
- Heeft deze cel als y coordinaat 0? Zo ja, dan wordt alleen het linkermuurtje weggehaald.
- Heeft deze cel als x coordinaat 0? Zo ja, dan wordt alleen het bovenste muurtje weggehaald.
- Als beiden niet waar zijn wordt of het bovenste muurtje of het linker muurtje weggehaald. De andere muurtjes raken we niet aan.
- Het doolhof is af!
Prim's
Hoe de doolhoven van Prim's algoritme gegenereerd worden vind ik een mooi proces. Het algoritme verspreid zich als een soort virus over het veld. Het is makkelijk om te begrijpen, maar minder makkelijk om te implementeren. Dit kom omdat je bij het genereren van dit doolhoof gebruik maakt van een dynamische lijst. Dit is een lijst waar je vrij elementen aan toe kunt voegen en uit weg kunt halen. Voordeel is dat het dus een erg dynamisch doolhoof wordt, maar het heeft ook een nadeel. Het bijhouden en bewerken van een dergelijke lijst kost vooral als hij langer wordt erg veel moeite. Het is dus een van de 2 algoritmes die ik heb uitgekozen die niet geheugenloos is. Bovendien zijn de doolhoven redelijk makkelijk op te lossen, als je ze weer van bovenaf bekijkt. Het is verder redelijk snel, en gebruikt geheugen exponentieel aan de grootte van het doolhof.
- Voeg een startcel toe aan de frontenlijst.
- Herhaal totdat de frontenlijst leeg is:
- Kies een willekeurige cel uit de frontenlijst
- Heeft deze cel onbezochte buren?
- Zo ja, maak een verbinding tussen de gekozen cel en de gekozen buur. Voeg de gekozen buur toe aan de frontenlijst.
- Zo nee, verwijder de gekozen cel dan uit de frontenlijst.
- Terug naar het begin van de loop
- Het doolhof is af!
Mijn eigen creatie: het Muurgroeier-algoritme
Met dit algoritme werd ik een keer op een ochtend in m'n hoofd wakker. Ik weet niet of ik het volledig zelf heb bedacht, mogelijkheid is dat ik hem een keer op internet langs heb zien komen maar dat later weer vergeten ben. Het was een leuk algoritme om uit te werken en te implementeren, al had ik het niet altijd naar mijn zin tijdens het implementeren. Dit algoritme is namelijk een algoritme dat werkt op het principe van het plaatsen van muren. De andere algoritmes werken precies vanuit het tegenovergestelde principe: het weghalen van muren. Ik heb het systeem om doolhoven op te slaan in het geheugen dus ook georienteerd op het benaderen van individuele cellen, en niet van individuele muren. Dat zorgde ervoor dat mijn systeem soms terugvocht: bepaalde denkstappen die ik in het algoritme kon maken moesten bij het implementeren met een omweg. Resultaat hiervan is een stuk in mijn programma met een hoop zoals ik het noem "dirty coding": weinig functies en objecten, maar veel losse variabelen en "handwerk" (in plaats van iets om te zetten in een functie het copy-pasten van code en de variabelen daarin veranderen). Gelukkig is het me uiteindelijk wel gelukt. Van dit algoritme heb ik uiteindelijk het meeste geleerd.
- Voeg alle randmuren toe aan de murenlijst. Het veld mag verder geen muren bevatten, behalve de muren die de randen van het doolhof aangeven.
- Herhaal totdat de murenlijst leeg is:
- Kies een willekeurige muur uit de lijst.
- Heeft deze muur nog plekken om zich heen waar geen muren staan, en waar de muur zo neergezet kan worden dat hij niet twee andere muren met elkaar verbind (en dus een passage afsluit?)?
- Zo ja, kies een van die willekeurige muurplekken. Plaats op de gekozen muurplek een muur, en voeg die muur toe aan de murenlijst.
- Zo nee, verwijder deze muur uit de murenlijst.
- Terug naar het begin van de loop
- Het doolhof is af!
Dijkstra's
Toen moest ik als laatste een padvind-algoritme zoeken. Na wat googlen en rondstruinen op wikipedia had ik mijn keuzelijstje vernauwd tot twee keuzes: Dijkstra's algoritme & het A*-algoritme. Ik was eerst van plan het A*-algoritme te gebruiken, maar hier heb ik later van afgezien. Dit was om bepaalde redenen. Ten eerste omdat het A* algoritme veel rekening houdt met afstanden en de vorm van de omgeving. Dit heeft bij de meeste doolhoven geen toegevoegd waarde, aangezien er maar een pad is (het kortste) en de doolhoven altijd zo goed als willekeurig zijn waardoor er geen bedoeling zit in de paden en je de afstanden dus ook niet in kan schatten (wat een onderdeel is van het A*-algoritme). Ten tweede was het A*-algoritme ook wat moeilijker om te implementeren omdat er meerdere dynamische lijsten aan te pas kwamen, waar ik een beetje tegenop zag. Ten derde vond ik het gevolg van het A*-algoritme maar niets: verlies van snelheid door meerdere dynamische lijsten. Daarom heb ik alles meegenomen maar voor Dijkstra's gekozen, omdat ik gewoon een simpel en snel algoritme nodig had.
- Begin bij het starthokje. Voeg dit hokje toe aan de frontenlijst (het algoritme lijkt wel wat op Prim's).
- Herhaal totdat einhokje gevonden is:
- Is dit hokje het eindhokje?
- Zo ja, stop deze loop en ga door met de volgende.
- Zo nee, neem het eerste hokje uit de frontenlijst (de "huidige cel"). Voeg alle nog niet toegevoegde omliggende buren toe aan de frontenlijst. Geef bij elk van deze cellen aan dat de "moedercel" de huidige cel is. Verwijder de huidige cel uit de lijst.
- Begin bij het eindhokje
- Herhaal tot het beginhokje is gevonden:
- Is dit hokje het beginhokje?
- Zo ja, algoritme is klaar!
- Zo nee, voeg het huidige hokje aan de lijst toe. Kijk welke cel de moedercel van het huidige hokje is. Maak die cel de huidige cel.
- Terug naar het begin van de loop.
- Het pad is gevonden
Voor wie het algoritme niet snapt heb ik nog een extra voorbeeld. Stel je voor, je begint bij het beginhokje. Dan zet je op alle omliggende hokjes een bordje met een pijl, en laat alle pijlen wijzen naar het beginhokje. Dan kies je vervolgens een van die hokjes, en zet je op alle hokjes die om dat hokje heenliggen (waar nog geen bordjes op staan) bordjes met pijlen erop, die je allemaal naar het hokje laat wijzen waar je nu opstaat. Dit blijf je doordoen totdat je uiteindelijk op het hokje komt dat je als bestemming had vastgesteld. Als je vanaf hier terug wilt komen naar het startpunt hoef je vervolgens alleen maar de pijlen te volgen! En zo vind je dan het juiste pad. Dit pad is (in mijn geval) automatisch ook het kortste, omdat het allemaal perfecte doolhoven zijn.
Merk op dat de beschrijvingen van de algoritmes niet optimaal en een beetje versimpeld zijn. Het eindresultaat is hetzelfde, maar deze zullen waarschijnlijk een stuk langzamer zijn. Ze leveren echter hetzelfde resultaat als de algoritmes die ik daadwerkelijk gebruikt heb in mijn programma.
Programma vaststellen
Voordat ik begon met programmeren ging ik eerst vaststellen wat ik allemaal nodig had voor het programma. Deze zou ik dan vantevoren eerst gaan maken, en later allemaal combineren in het uiteindelijke programma. Wat had ik nodig?
- 4 doolhof-algoritmes: daar kun je hierboven over lezen.
- Een padvind-algoritme: daar kun je hierboven ook over lezen.
- Een spelsituatie-systeem: dit had ik nodig om makkelijk te kunnen wisselen tussen bijvoorbeeld een hoofdmenu scherm en een scherm met opties voor de doolhoven of een scherm met uitleg over de algoritmes, zonder gelijk 500 regels codes te moeten schrijven.
- Een knoppensysteem: dit is nodig om netjes te kunnen wisselen tussen de verschillende schermen
- Een selectievakjessysteem: dit was nodig om netjes parameters voor de doolhoven aan te geven
- En als laatste, een doolhof opslagsysteem. Dit is nodig om met een versie van Dijkstra's algoritme alle doolhoven op te kunnen lossen. Stel je voor dat elk algoritme de doolhoven op een andere manier (een ander "format") afleverd, dan moest ik voor elk algoritme een aparte versie van Dijkstra's schrijven (in het ergste geval). Maar als ik ervoor kon zorgen dat alle algoritmes hun einddoolhoven zouden maken in een algemeen doolhovensysteem, hoefde ik alleen maar een Dijkstra's algoritme te schrijven voor dat algemene doolhovensysteem, wat natuurlijk flexibel en snel is om te schrijven.
Zo zag mijn "boodschappenlijstje" (ook wel designsheet genoemd) eruit. De originele designsheet is bijgevoegd met het Maze+ programma, als iemand er belangstelling voor heeft. Merk wel op dat het originele document niet mooi ingedeeld is. Het was voor mij puur een lijst om bij te kunnen houden wat er moest gebeuren, wat ik nog nodig had of hoe ik iets aan moest pakken.
Het programmeren
En toen moest ik beginnen met het daadwerkelijk programmeren van het programma, wat heerlijk soepel ging (op het muurgroei algoritme na...). Voor het knoppensysteem had ik al gauw een kandidaat, namelijk een knoppensysteem dat ik had geschreven voor een eerder projectje, wat ik met een paar aanpassingen ook kon gebruiken voor dit project. Het spelsituatie-systeem was ook snel gevonden, dat had ik namelijk eerder ook al geschreven voor een ander project, en kon ik ook (met ietwat meer aanpassingen) gebruiken voor dit project. Om te kunnen schrijven naar het scherm en input van de gebruiker (muis, rood kruisje rechtsboven) te verkijgen heb ik gebruik gemaakt van de SDL engine. SDL staat voor Simple Directmedia Layer. Het is een zoals de naam al zegt simpele engine die ik al vaker gebruikt heb. Hij is lichtgewicht en crossplatform met bovendien een erg grote community, waardoor ik als ik een probleem heb vaak makkelijk een oplossing kan vinden. Het selectievakjesysteem en het doolhof opslagsysteem waren twee niet al te moeilijke maar leuke uitdagingen. Bij beiden heb ik mijn vaardigheid om objectgeorienteerd te programmeren weer verbeterd. Ik maakte er voor mijzelf een uitdaging van door zo min mogelijk globale variabelen te gebruiken, en het is me gelukt om het te beperken tot 3 globale variabelen. Het programmeren van dit programma had me zonder late avonden waarschijnlijk rond de 2 a 3 weken gekost. Ik heb er echter, in verband met een druk schema, uiteindelijk een week aan besteed.
Evaluatie
Wat ging er goed, wat ging er mis? Iets waar ik bij dit project heel erg tevreden over ben is het werk vooraf. Als ik soms met een eigen projectje bezig ben doe ik dingen vaak uit de losse pols. Ik begin gewoon met typen en uiteindelijk kom ik er wel. Niet de mooiste manier, maar het werkt. Hier heb ik dat anders aangepakt: ik heb precies vantevoren vastgesteld wat ik ging doen en hoe ik dat ging doen, waardoor ik bijna nooit met vraagtekens zat (wat ik normaal wel veel heb). Iets anders waar ik echt trots op ben is de object-georienteerdheid van dit progamma. Ik heb veel dingen als "object" benaderd, wat een redelijk nieuw concept voor mij is, waardoor ik bugs razendsnel kon opsporen, systemen en algoritmen makkelijk met elkaar kon combineren en de algehele ontwikkelingssnelheid veel hoger lag dan normaal. Helaas ging niet alles goed. Ik ben namelijk ook veel te laat begonnen met het programmeren, waardoor ik in tijdnood kwam en veel late avonden heb moeten maken om het af te krijgen. Daarnaast kwam het idee voor een zelfgemaakt algoritme ook wat later, wat heel erg veel tijd gekost heeft. Daar had ik misschien beter van af kunnen zien.
Al met al vond ik dit een superleuk project om te maken. Ik heb me goed verdiept in de stof, me goed voorbereid op het programmeren van het programma zelf en (snelheids)grenzen verlegd bij het programmeren. Ik hoop dat jullie net zoveel plezier hebben van het eindresultaat als ik had van het maken van dit programma! :-)