Opdracht 0: het genereren van doolhoven

Inleiding

Voor een volgende programmeeropdracht hebben we doolhoven nodig. Nu is het een beetje tijdrovend om doolhoven handmatig te gaan construeren. Handiger is het om doolhoven door een computer-programma te laten genereren. Daar gaat deze opdracht over.

Globale omschrijving

Programmeer in Netlogo een doolhoven-generator.

Begin

Alle begin is moeilijk, zeker als je net een nieuwe taal leert. We gaan doolhoven genereren met zg. turtles. Probeer daarom eerst eens een turtle te programmeren die in stapjes rechtuit loopt en een spoor trekt (gebruik forward 1 en set pcolor 1. Probeer daarna eens een turtle te programmeren die in stapjes rechtuit loopt, een spoor trekt en kan keren bij randen (gebruik can-move? 1 en left 90) Daarna een turtle die in stapjes rechtuit loopt, een spoor trekt, kan keren bij randen en kan keren bij het eigen spoor. Als je dit gedaan hebt kun je je werk vergelijken met dit voorbeeld-programma. Dit kun je downloaden en in Netlogo openen.

Uitleg

Hier volgt uitleg over de hele opdracht.

1. Depth-first. Er zijn talloze manieren om doolhoven te genereren. Wij kiezen voor een algoritme dat gegarandeerd een zg. weg-samenhangend doolhof construeert met lange gangen. Dit algoritme is onder twee namen bekend: depth-first search danwel recursive backtracking. De naamgeving heeft te maken met de implementatiemethode (stack danwel recursie). We komen daar later op terug. Weg-samenhang betekent dat alle doolhof-locaties met elkaar verbonden zijn.
2. Turtle. In deze opdracht gebruik je een turtle om een doolhof te maken. Zet deze ergens neer, en laat hem (haar, het) een weg vreten door de hagen. De gebaande paden moeten strict noord-zuid danwel oost-west zijn. Turtles mogen alleen evenwijdig aan de x- en y-as lopen.
3. Backtracking. Kan een turtle niet verder, dan gaat deze naar de vorig bezochte patch en bekijkt vanaf daar alle vier de richtingen om mogelijk verder te gaan. Zit de turtle daar ook vast, dan bezoekt de turtle de patch van daarvoor, en bekijkt vanaf daar alle vier de richtingen om mogelijk verder te gaan. Als ook dat niet lukt, dan de patch van daarvoor, enzovoort. Dit backtracking-mechnsime kan recursief of met behulp van een stack worden geïmplementeerd.

Randvoorwaarden

Hier staat wat moet. Bij afwijking van randvoorwaarden worden punten in mindering gebracht.

1. Single-button. Het doolhof moet uiteindelijk met één druk op een knop te genereren zijn. Als het doolhof gereed is, doet Netlogo niets meer en staat er alleen een doolhof. Zo er turtles waren zijn die nu weg.
2. Layout. Om nakijken te vergemakkelijken dient je doolhof 101x101 patches groot te zijn, patch size 4, doolhof wit, muren zwart. Zorg ervoor dat je canvas een vierkant is en geen cilinder of torus.

Aanwijzingen

Een stack: last in, first out.

1. Muren zijn, evenals paden, cellen. Je hebt paden en muren. Veel doolhof generereer-algoritmen gaan er vanuit dat paden zijn opgebouwd uit cellen en dat muren worden gerepresenteerd door scheidingswanden (streepjes) tussen cellen. Bij Netlogo is dat laatste moeilijk te realiseren. Daar is het handiger om muren te representeren als cellen. In Netlogo zijn muren dus patches. Lees ook Miga's blog.
2. Turtle. Gebruik een turtle om je doolhof te maken. Zet deze aan het begin ergens neer ( move-to one-of patches ), en laat haar (hem, het) een willekeurige kant op wijzen ( set heading 90 * random 4 ). Voor ons type doolhof moet een turtle op een oneven patch staan: ( move-to one-of patches with [ pxcor mod 2 = 0 and pycor mod 2 = 0 ] ). Je hebt gelijk: modulo nul is even, maar het default Netlogo canvas begint te tellen vanaf nul.
3. Depth-first. Als je depth-first gaat implementeren met een stack, dan kun je het volgende doen:

   ; een stack kan in Netlogo word geïmplementereerd als lijst.  dat is hier nog niet te zien
   ; de stack wordt alleen gedeclareerd
   
   turtles-own [
     stack ; alle zelf-verzonnen variabelen, functies en routines zijn rood
   ]
   
   to setup
     ; init code (bijvoorbeeld: clear-all)
     create-turtles 1 [
       ; turtle init code ... (zet hem op z'n plek, geef hem een vorm en een kleur, laat hem een kant op wijzen)
       set stack (list patch-here)
       ; na initialisatie bevat de stack één element, namelijk de patch onder de turtle
       ; je kunt hier ook zien dat de stack geïmplementereerd is als lijst
       ;
       ; stack-initalisatie respecteert niet echt de pop en push routines. om dat te verhelpen kun je
       ; een stack-init procedure schrijven, een stack-init doen, en dan vervolgens het eerste element
       ; er op duwen.
       ; ...
       ; andere turtle init code ...
     ]
   end
   
   ; --- hulp routines voor de stack implementatie --------------------------------------
   
   to push [ element ] ; duw element op de stapel
     set stack (fput element stack) ; stop een element voor in de lijst
     ; haakjes zijn hier niet echt nodig.  ze zijn ingevoegd voor het begrip
   end
   
   to-report pop ; haal een element van de stapel en geef dit terug
     ; code om een element van de stack te halen en terug te geven.  sluit af met: report <waarde>
   end
   

4. Vastlopen. Een turtle loopt zich vast als deze in alle richtingen geen stap vooruit kan doen.
5. Probing (“aftasten”). Om te bepalen of een turtle een stap vooruit kan zetten, moeten zowel de cel waar de turtle terecht zal komen, als de cel één stap verder worden afgetast. Deze twee cellen moeten bestaan en nog niet belopen zijn. Je kunt hier Netlogo routines voor schrijven.
6. Een daadwerkelijke stap.

   to step
      ; neem twee stappen, kleur de belopen velden wit, en onthou de locatie waar je aankomt
   end
   

7. Een move.

   to move
     ; probeer eens wat .....
     ; als de turtle in alle vier de richtingen niet verder kan, doe dan een backtrack stap
     backtrack
     ; de huidige move is nu beëindigd
   end
   
   to backtrack
     move-to pop
   end
   

8. Testen. Het is raadzaam te testen met een klein veld, en de turtle eerst per button-klik een stap te laten nemen. Maak een twee buttons voor move. Eén van het type “run forever”, en één gewone. Met de gewone button kun je stappen. Stappen kan worden vergemakkelijkt door de gewone button een action key, bijvoorbeeld S, te geven in het edit menu.
9. Single-button. Zorg er tenslotte voor dat je doolhof genereer-algoritme stopt. Dit kan door zoiets als

   to create-maze
     ask turtles [ ; vraag alle turtles (er is er maar één maar dat maakt niet uit)
       while [ not empty? stack ] [ move ] ; blijf actief zolang de stack nog niet leeg is
       die ; vraag turtle zichzelf te killen als z'n stack leeg is :-(
     ]
   end
   

Extra

Extra punten kunnen worden verdient door het aanbrengen van de volgende features.

1. Flood fill. Klik met je muis op een stuk doolhof om vanaf daar water (of bloed) door het doolhof te laten stromen.

   to flood-fill ; deze procedure wordt gekoppeld aan een knop die, als die ingedrukt is, ingedrukt blijft
     if mouse-down? [ ; vang muisklikken op
       ask patch mouse-xcor mouse-ycor [ set pcolor red ] ; vul patch onder de cursor met rood
     ]
     ; code die er voor zorgt dat witte doolhofcellen die grenzen aan rode doolhofcellen zelf ook rood worden
     ; ...
   end
   

2. Curviness. Stel met een slider in hoe bochtig het doolhof wordt. De ervaring leert dat het handig is om curviness waarden 0..100 te laten aannemen en met een lage curviness bochtige doolhoven te genereren. (Je mag het ook anders doen.)
3. Non-determinisme Het bij vastlopen draaien en andere richtingen uitproberen ( repeat 4 [ ... ] ) verloopt in het voorbeeld hierboven deterministisch (altijd op dezelfde manier), door bij vastlopen steeds 90 graden naar rechts te draaien. Het zou mooier zijn het zoeken naar alternatieve richtingen non-deterministisch te laten verlopen. In het laatste geval probeert de turtle alternatieven richtingen uit in een willekeurige volgorde. Non-deterministisch gedrag levert doolhoven op die iets meer variëren.
4. Meerdere turtles. Leg dan uit wat het toevoegt.
5. Implementeer backtracken met recursie. De stack wordt dan bijgehouden door Netlogo zelf. (Let wel op met grote doolhoven. Netlogo gooit bij elke functie-aanroep nu een compleet activation record op z'n eigen call stack.)

Zie ook

• Jamis Buck's presentatie over allerlei soorten maze generating algorithms. Aanbevolen!
• Jamis Buck's blog. Met een verwijzing naar zijn boek “Mazes for Programmers”.
• < A href="http://weblog.jamisbuck.org/2011/2/7/maze-generation-algorithm-recap" target="_blank">Jamis Buck's maze algorithm recap
• Miga's blog. Hierin wordt goed uitgelegd dat, als je een maze genereert waar zowel paden als muren zijn opgebouwd uit cellen (Netlogo: patches), je altijd een canvas moeten nemen met oneven zijden, dat je turtle in het begin moet staan op een patch met oneven x- en y-coördinaten, en dat je turtle elke keer twee patches vooruit moet stappen.
• ... en natuurlijk Wikipedia's pagina voor het genereren van doolhoven.
• In mei 2015 verscheen een boekje in de Zebra-reeks, getiteld labyrinten en doolhoven. Dit boekje is geschreven door Wim Kleijne en kost 10,=