Opdracht 1: het oplossen van doolhoven

Inleiding

Tag line: “In just a few more years, this technique should be faster than A* !”

Cellulaire automaten kunnen worden gebruikt om doolhoven op te lossen. In deze opdracht word je gevraagd een dergelijke automaat te implementeren.

Uitleg

De bedoeling is dat je een app maakt die eerst een doolhof genereert met een bron (startpunt) en een doel (eindpunt). Daarvoor mag je je eigen code uit Opdracht 0 gebruiken, of iemand anders zijn code uit Opdracht 0 als je die beter vind. Vervolgens doet je CA een flood fill vanaf de bron. Als een cel wordt gevuld door de flood fill, dan registreert de zojuist gevulde cel aan welke kant (NZO of W) de flood binnenkwam (om het zo maar even te omschrijven). Referenties naar die vorige cellen worden terugverwijzers, of back pointers, genoemd. Zoiets als de broodkruimels van Klein Duimpje. In enkele gevallen kan het voorkomen dat de flood van meerdere kanten tegelijk binnenkwam. Dan moeten dus meerdere back pointers worden onthouden. Dus de toestand van een cel zal typisch onder meer een lijst met back pointers bevatten.

Als de flood fill eenmaal het doel heeft bereikt, dan is naast de lopende “forward fill” makkelijk een “reverse fill” op te roepen die alleen de back pointers volgt.

Randvoorwaarden

Hier staat wat moet. Bij afwijkingen worden punten in mindering gebracht.

1. Doolhof. Aan het begin genereert je app met één druk op de knop een doolhof.
2. Afmetingen en kleuren. Identiek als bij Opdracht 0.
3. Bron en doel. Bron: min-pxcor, 0, doel: max-pxcor, 0.
4. Kleuren. Identiek als bij Opdracht 0. Verder staat rood voor exploratie en groen voor kortste pad.
5. Meerdere kortste routes Bij meerdere oplossingen worden alle oplossingen getoond.
6. Andere doolhoftypen. Bij depth-first gegenereerde doolhoven is er maar één kortste pad. Bij doolhoven die wat opener zijn, bestaan er meerdere kortste paden. Om te laten zien dat je cellulaire automaat in het geval van meerdere kortste paden alle kortste paden kan vinden, is het nodig dat je in je app een mogelijkheid biedt om tenminste twee verschillende doolhoven te maken, waarvan één depth-first, en één dat via een algoritme dat in het algemeen wat opener doolhoven geeft. De lijst aan het eind van Opdracht 0 bevat verwijzingen naar dergelijke algoritmen. Je algoritme voor het genereren van een wat opener doolhof mag bestaan uit het lukraak neerzetten van enkele stukken muur in een open veld. Maar het zou mooier zijn als je tweede doolhof op een wat systematischer manier wordt gegenereerd.
7. Het moet echt een cellulaire automaat zijn die het probleem oplost. Dus cellen mogen niet actief hun buurcellen beïnvloeden (“state pushing” / schrijven). Omgekeerd mogen cellen zich wel door buren laten beïnvloeden (“state pulling” / lezen). Sterker, dat moet want beïnvloeding door buren is de essentie van een CA. Turtles laten zoeken is uiterard ook niet toegestaan, het moet echt een CA zijn.

Aanwijzingen

Hier volgen hints en tips.

1. Exploratie. Dit kan verlopen door middel van een flood fill-achtig proces. Een flood fill is niets anders dan een proces dat begint met één cel te “besmetten” waarna voortdurend besmette cellen onbesmette buren “aansteken”.
2. Hoofdtoestand. Elke cel zal typisch een hoofdtoestand bezitten met waarden als bijvoorbeeld als: “start-punt”, “doel”, “muur”, “ongeëxploreerd”, “deel-van-kortste-pad”, verzin het maar. Je bent vrij om de hier genoemde hoofdtoestand-waarden te gebruiken, maar wie zegt dat je ze allemaal nodig hebt, of dat dit de juiste toestanden zijn. Zoek het zelf uit.
3. Kleuren. Laat hoofd-toestanden de cellen kleuren.
4. Data-structuur. Een cel kan behalve een (hoofd-) toestand ook een data-structuur, zoals bijvoorbeeld een lijst, bevatten. Die lijst kan dan bijvoorbeeld opslaan via welke buurcellen de huidige cel tijdens exploreren gevonden werd. Dat is handig om later een kortste pad te maken.
5. Toestand. Eigenlijk wordt de toestand van een cel gevormd door het conglomeraat van 1) zijn attributen (pcolor, pxcor, pycor, ...), 2) de hoofd-toestand (toestand of: state) en 3) gebruikers-gedefinieerde patch-variabelen die lijsten als waarde hebben of andere data-structuren.
6. Code scheiden. Werk netjes. Scheid code voor het genereren van doolhoven van code die zorgt voor toestand-overgangen in cellen. Dat gaat bijvoorbeeld makkelijk met een scheidslijn:

   ;--- code voor het genereren van een depth-first search doolhof -----------------
   
   turtles-own [ stack ]
   
   to create-maze [ sources goals ]
     ask patches [
       set-state "wall"
       ...
       ...
   

7. Dispatch method. Misschien vind je het handig om een zogenaamde dispatch method (afhandelings-methode) te gebruiken

   to go
     ask patches [ run (word "act-" state) ]
   end
   

   Hier is dat run (word "act-" state). Als je toestand-waarden A, B en C hebt, volstaat het vervolgens om methoden act-A, act-B, en act-C te maken die het gedrag van cellen met toestand respectievelijk A, B en C bepalen. Hier is de Netlogo documentatie van word en van run.

Extra

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

1. Differentiëren in celtype. Door te differentiëren in celtype (door zoveel mogelijk verschillende waarden voor de hoofd-toestand te nemen) kun je het zoekproces misschien nóg slimmer of aanschouwelijker maken.
2. Visualiseren van back pointers. Denk er om dat meerdere back pointers per cel ook correct gevisualeeerd worden.

Zie ook

• A GPU Approach to Path Finding (Chris Wellons). Ik vind de oplossingen die daar worden getoond vrij ingewikkeld. Maar de geanimeerde gifs zijn de moeite waarde om eens te bekijken. Eigenlijk is zelf je eigen oplossing bedenken eenvoudiger.
• Je kunt natuurlijk ook Google-en. De door Google teruggegeven informatie is wel erg divers.