Opdracht 2: Hadimassa

Inleiding

Het simuleren van mensenmassa's (Eng.: crowd simulation) kent veel toepassingen. Zo is het bijvoorbeeld een belangrijk hulpmiddel om te bepalen of omgevingen waar veel mensen bij elkaar komen veilig zijn. Denk aan stadions, vliegvelden en festivalterreinen. Over Corona wil ik het niet heben.

Globale omschrijving

Implementeer met een eenvoudige flockingtechniek een mensenmassa die zich beweegt van een bron (bijvoorbeeld ingang) naar een doel (bijvoorbeeld uitgang). De ruimte kan worden ingericht met obstakels. Er wordt aangenomen dat mensen op ieder moment volledige kennis hebben van de kortste weg naar het doel. Het probleem is alleen dat andere mensen dit doel ook hebben en dus in weg kunnen lopen ...

Voorkennis: flocking, zie TCBoN, Sec. 16.3.

Werking

Bewegingsalgoritme

• Perception. Iedere wandelaar bezit een gezichtsveld (Eng.: field of view) in graden, bv. 180⁰, en een persoonlijke ruimte (Eng. minimal interpersonal space), bv. straal 1.5 (gerekend vanuit het middelpunt van die wandelaar). Straal 1.0 zou dan overeenkomen met de buitenkant (“huid”) van de wandelaar, en straal 1.5 zou dan overeenkomen met de tussenruimte van een halve persoon.
• Separation. De wandelaar observeert eerst of er zich een (stukje) hindernis of iemand anders in de doorsnijding van z'n gezichtsveld en persoonlijke ruimte bevindt. (*) Als dat zo is, dan doet de wandelaar een stapje terug (“backup”), en is voor dat moment klaar met bewegen. (Er worden geen nieuwe observaties en/of acties meer gedaan.) Het is toegestaan eerst te controleren op hindernissen en daarna op anderen: Netlogo staat namelijk niet toe dat patches en turtles als één set worden beschouwd.
• Backup. De wandelaar draait volledig naar een willekeurig waargenomen obstakel, en doet vervolgens een klein stapje achteruit. Daarna draait de wandelaar weer terug naar z'n oorspronkelijk oriëntatie. Om een impasse in de animatie te voorkomen draait de wandelaar niet noodzakelijk naar het dichtsbijzijnde stukje hindernis, of naar de dichtsbijzijnde andere wandelaar.
• Orientation. Als en alleen als geen separatiestap heeft plaatsgevonden, zal de wandelaar een klein stukje draaien naar een willekeurige buurveld (Moore-omgeving) die het dichtst bij het doel ligt, en vervolgens een stapje voorwaarts doen. (Zie ook de snippet “turn”.)
• Success. Als het doel bereikt is, teleporteert de wandelaar zichzelf naar één van de (groene) startvelden. Op deze manier blijft het aantal wandelaars in de simulatie constant.

(*) Overal waar “zijn” staat kan ook “haar” worden gelezen. Maar eigenlijk doen we hier aan antropomorfisme.

Vloerplan

• Soorten velden. Het terrein bestaat uit vier soorten velden: bron (groen), doelomgeving (rood), hindernis (sky), en de rest (zwart). (Zie ook “Randvoordwaarden”.) Alle velden behalve de hindernisvelden zijn bewandelbaar.
• Goal patches. Rode velden met alleen rode buren zijn doelvelden. (Dit toont beter in de animatie.)
• Kortste afstand. De bewandelbare velden (alles behalve sky) bezitten informatie over de kortste afstand naar één van de doelvelden. Afstanden worden gemeten volgens de Manhattan metriek. (Verwar roosterlijnen niet met patch-randen. Roosterlijnen lopen zoals altijd over de helen. Patch-randen daarentegen, lopen juist over de halven. Bekijk zo nodig Slide 7-10 van Würzer.)

Randvoorwaarden

Hier staat wat moet.* Bij afwijking van randvoorwaarden worden punten in mindering gebracht. Sommige randvoorwaarden zijn opgesteld om later de beoordeling van je programma te vergemakkelijken.

• Canvas. Het canvas bezit de standaardformaten ([-16, 16]², patchgrootte 13). De randen van het veld zijn niet met elkaar geïdentificeerd. Het veld is dus een rechthoek en niet het oppervlak van een torus. (Anders zouden in de default-layout de wandelaars wel heel makkelijk, via de achterdeur, van bron naar doel kunnen lopen.)
• Turtles. 150 Turtles. Deze zijn geel, rond (vorm “circle”), en bezitten de standaardgrootte.
• Stapgrootte. Wandelaars bezitten verschillende stapgroottes om een impasse in de animatie te voorkomen. Elke wandelaar bezit een constante stapgrootte die bij initalisatie gekozen wordt uit een uniforme verdeling op het interval [0.7x0.35, 1.3x0.35]. De stapgrootte bij een stapje terug is kleiner dan de normale stapgrootte.
• Persoonlijke ruimte. Neem r = 1.1.
• Bijzondere velden. Velden behorend tot de bron (ingang of vertrekpunt) zijn groen, behorend tot de put-omgeving (uitgang- of doel-omgeving) zijn rood, behorend tot obstakels (muren of hindernissen) zijn sky (de laatste is een Netlogokleur).
• Default layout. Er is een button waarmee een default layout op het canvas wordt gebracht.

  to defaults
    set nr-of-turtles     150
    set mean-step-size      0.35
    set collision-radius    1.1
    set field-of-view       1.1
    set length-of-left-bar  7
    ;
    ask box -14   9  -9  14 [ set pcolor green ]
    ask box  10 -16  16 -10 [ set pcolor red   ]
    ask box  (0 - length-of-left-bar)
                  0   0   0 [ set pcolor sky   ]
    ask box   3   0  16   0 [ set pcolor sky   ]
    ask box   3  -5   3   0 [ set pcolor sky   ]
  end
  
  to-report box [ left-x left-y right-x right-y ]
    report patches with [left-x <= pxcor and pxcor <= right-x and
                         left-y <= pycor and pycor <= right-y ]
  end
  

• Paint. Het is mogelijk het veld te schilderen in elk van de vier kleuren. (Zie ook “Snippets”.)
• Wijziging van kortste afstanden. Als kortste afstanden tot het doel wijzigen (bijvoorbeeld door een paint actie) dan zal de app niet lang daarna uit zichzelf de kortste afstanden hebben herberekend.
• Episoden. Intern (dus niet te zien op de GUI) zijn er episoden. Voor elke episode wordt gecheckt of er sliders zijn verschoven of dat het veld is veranderd. Als er sliders zijn verschoven moeten er bv. misschien turtles worden toegevoegd. Als er velden zijn veranderd (bv. door verfacties van de gebruiker) zullen afstanden opnieuw moeten worden berekend. Een episode duurt bv. 200 tikken. Een tik word zoals gewoonlijk gedefinieerd als een periode waarin alle turtles één maal hun actieroutine, bv. move, uitvoeren.
• Doorstroom. De gemiddelde doorstroom wordt bijgehouden, in aankomende wandelaars per episode. Aan het eind van elke episode wordt het zogenaamde lopend gemiddelde geupdate met 5% van het gewone gemiddelde. (Dus lg = 0.95*lg + 0.05*g.) Aan het begin van de simulatie wordt het lopend gemiddele geïnitialiseerd op nul. Elke episode-length tikken wordt het lopend gemiddelde geplot. (We kiezen er voor het lopend gemiddelde te plotten omdat de resulterende grafiek dan vloeiender verloopt en de trend daardoor beter is af te lezen.)
• Bevrijd. Een enkele keer kunnen wandelaars vastlopen. Het is handig een button bevrijd (o.i.d.) te plaatsen die alle aanwezige wandelaars voorzover nodig een zetje geeft, bv. op een dichtstbijzijnde bewandelbare plek zet.

Tips

1. Perceptie. Het gezichtsveld en de persoonlijke ruimte kunnen gelijktijdig worden geïmplementeerd met het primitief in-cone.
2. Afstand. Voor de Manhattan-metriek (zie boven) kan neighbors4 worden gebruikt.
3. Draaien. Om slechts een stukje in de goede richting te draaien kan het primitief subtract-headings worden gebruikt.
4. Draaisnelheid. Als er gedraaid wordt bij vrijheid, is een draaisnelheid van 2⁰ (per keer) een aardige keuze. Maar andere snelheden werken ook. Kijk wat werkt! Varieer desnoods met een tijdelijk aangebrachte schuifbalk.
5. Perceptie vs. actie. Merk op dat perceptie wordt bepaald door het gezichtsveld en de persoonlijke ruimte, maar draaien-bij-vrijheid door de Moore omgeving. Afstand wordt dan weer bepaald door de Manhattan-metriek, dus door de Von Neumann omgeving. Dus er spelen hier 3 verschillende omgevingen. Je kunt het er inderdaad over hebben of dit waarheidsgetrouw en/of intuïtief is, echter deze discussie valt een beetje buiten de opdracht.
6. Een stapje terug. forward my-speed / -8 lijkt goed te werken. Maar andere snelheden werken ook.
7. Volledig draaien naar een veld. Kan met face.
8. Patch sets. Als het vloerplan eenmaal is gedefinieerd (of tussendoor is gewijzigd) is het handig meteen daarna vier of zelfs vijf patch sets te definiëren: bronvelden, doelvelden, hindernisvelden, zwarte velden, en bewandelbare velden (= alle niet-hindernisvelden). De naamgeving hier is een suggestie. Het wordt aangemoedigd zelf geschikte namen te kiezen voor deze patch sets. Herinner: doelvelden zijn inwendige rode velden, dus rode velden met alleen rode velden in hun Moore-omgeving.
9. Kortste afstand. Voor alle bewandelbare velden kan de kortste afstand tot het doel eenvoudig berekend worden met een reverse floodfill. Dit werkt zo: alle doelvelden bezitten kortste afstand nul tot het doel. Vervolgens kijk je welke bewandelbare velden (waarvan de kortste afstand tot het doel nog onbekend is) grenzen aan bewandelbare velden waarvan de kortste afstand tot het doel al wél bekend is. Deze velden krijgen kortste afstand gelijk aan 1 + kortste afstand van een bewandelbare buurveld met minimale kortste afstand tot het doel. Dit proces wordt herhaald totdat van alle bewandelbare velden de kortste afstand tot het doel berekend is. (Zie ook “Snippets”.)
10. Signaleren. Dingen signaleren kun je met een zg. “vlag”. Initeel staat de vlag op FALSE. Gebeurt er iets wat wilde bijhouden (bv. een slider is verschoven), dan zet je vlag op TRUE.
11. Herberekenen van kortste afstand. Na elke paint actie kun je laten signaleren dat het vloerplan is gewijzigd.
12. Elementaire functies. Netlogo bezit geen tekenfunctie (Eng. sign function), en het bezit ook geen generator voor de uniforme verdeling. Definieer deze zelf in aparte functies. Netlogo bezit al wel een generator voor de uniforme verdeling op het eenheidsinterval, te weten random-float.

Snippets

Hieronder volgen snippets (codefragmenten). De snippets zijn facultatief. Het is niet verplicht ze te gebruiken, we hebben misschien zelfs liever dat je je eigen code schrijft. De snippets behoren niet tot de opdracht, en zijn zeker niet bedoeld als stappenplan. De snippets zijn meer bedoeld om je op weg te helpen mocht je vastlopen. De werking van de snippets is niet gegaranderd, en de practicumleiding is niet verplicht om er uitleg over te geven.

1. Patches kleuren met de muis

   to paint [ c ]
     if mouse-down? [
       ask patch mouse-xcor mouse-ycor [
         set pcolor c
       ]
     ]
   end

2. Draai een stukje in de goede richting

   right rotation-angle * sign subtract-headings (towards goal-patch) heading
   

   De draaihoek heb je zelf gedefinieerd (bv. 2⁰). Het doelveld is eerder in je programma bepaald. De functie sign is de tekenfunctie: sign(x) = 1 als x > 0, -1 als x < 0, en 0 anders. Netlogo bezit zelf geen tekenfunctie.
   
   
3. Voorbeeld van een reverse flood fill

   ; initially, all patches are very distant from the source
   ask patches [ set dist TOO_FAR ]
   
   ; inner red patches have distance zero to goal
   ask red-patches with [ all? neighbors [ pcolor = red ] ] [ set dist 0 ]
   
   ; do a reversed flood fill to determine, for the rest of the walkable patches,
   ; the distance to the source
   loop [
    ; from patches with unknown shortest distance to goal that have neighbors
    ; with known shortest distance to goal, it is possible to compute their
    ; shortest distance to goal.  such patches are called "the front"
    let front walkable-patches with [ dist = TOO_FAR and any? neighbors4 with [ dist < TOO_FAR ] ]
    if not any? front [ stop ]
    ask front [
      set dist 1 + min [ dist ] of neighbors4 with [ dist < TOO_FAR ]
    ]
   ]
   

   De constante TOO_FAR zul je zelf moeten definiëren. Je kunt 'm op 9E9 zetten (kortste manier om een vrij groot getal in Netlogo op te schrijven), of, intelligenter, world-width ^ 2 + world-height ^ 2.

Extra

Extra punten kunnen worden verdiend door het aanbrengen van extra features. Het aantal extra punten hangt af van het gewicht van een feature en de implementatie-kwaliteit. Geef, voor de puntentelling, duidelijk aan wat je extra features zijn, onder een kopje “Extra features” in de “Information” tab. Voorbeelden van extra features:

• Gradient (+1). Kleur zwarte velden licht tot donker, afhankelijk van de afstand tot het doel. (Licht is dichtbij.)
• Batch circulatie (+1). Bouw een modus in waarbij wandelaars zich als groep verplaatsen. In dat geval wordt elke wandelaar verwijderd als deze het doel heeft bereikt, net zolang tot er geen wandelaars meer zijn. Daarna start een nieuwe groep. In deze optie is het verplicht een switch in de GUI te plaatsen waarmee het mogelijk is af te wisselen tussen batch (afnemend aantal wandelaars) en echte circulatie (constant aantal wandelaars).
• Variabel gedrag (+1). Een complete set sliders waarmee alle variabelen zoals aantal wandelaars (eerder constant 150), backup-schaling (eerder constant -8), draaisnelheid (eerder constant 20, perceptieradius (eerder constant 1.0), kunnen worden gevarieerd—en een knop om al deze sliders weer op default-waarden -8, 20, 1.0, ... terug te zetten.
• Geen vastlopers (+2). Zorg er op een elegante manier en met minimale middelen voor dat wandelaars niet kunnen vastlopen. Implemteer dit bij voorkeur volledig binnen de wandelroutine van turtles zelf. I.e., het is makkelijk maar ook een beetje goedkoop om alles om de zoveel tikken van buitenaf een beetje op te schudden.
• Trolley car (+2). Implementeer een zich langzaam voortbewegend obstakel (auto, kar met dozen, trolley), en zorg er voor dat dit obstakel zich in vergelijking met de wandelaar langzaam voortbeweegt.

Overig

Over de titel van dit document: Hadimassa was een populair satirisch Nederlands televisieprogramma dat van 1967 tot 1972 door de VARA werd uitgezonden. Hadimassa werd in 1970 de bekroond met de Zilveren Nipkowschijf, een prestigieuze Nederlandse televisieonderscheiding.

Nakijkmodel

Het volgende nakijkmodel zal worden gebruikt.

   ------------------------------------------------------

    1. gratis punt
    2. complete, nette, en intuitieve GUI
    3. randvoorwaarden (kleuren, veldgrootte, stapgrootte, ..)
    4. correct gedrag op wandelaar-niveau
    5. correcte plot
    6. kwaliteit code   ; functionele one-liners zijn cool
    7. executiesnelheid ; maar imperatieve constructies werken meestal sneller ...
    8. documentatie (in code, in tab, *.png)

   ----- cijfer acht ------------------------------------

    9. best of extra feature
   10. "

   ----- cijfer tien ------------------------------------

Een uitgewerkt voorbeeld

Wijzigingen

18 maart 2020

“Elke wandelaar bezit een constante stapgrootte die bij initalisatie gekozen wordt uit een uniforme verdeling op het interval [0.7, 1.3].” gewijzigd naar “Elke wandelaar bezit een constante stapgrootte die bij initalisatie gekozen wordt uit een uniforme verdeling op het interval [0.7x0.35, 1.3x0.35].” Het getal 0.35 is daarmee nu wel het midden.