De weg uit het doolhof

Met cellulaire automaten kunnen we meer dan mooie patronen genereren. Ze vormen een krachtig gereedschap om allerlei processen en principes mee te simuleren. Ik laat hier een simulatie zien met een cellulaire automaat waarmee je de weg uit een doolhof kunt vinden. Een belangrijk verschil met de game of life is dat de cellen nu op meerdere manieren gevuld kunnen zijn.  Preciezer, een cel is niet alleen bezet of niet, maar kan bezet zijn met verschillende kleuren.

Het model van het doolhof bestaat uit een vierkant van cellen waarin de muren worden gevormd door bruine cellen. Bij de uitgang is een cel gevuld met groen. De persoon die probeert de ontsnappen staat in een rode cel.

Net als bij de game of life geven we regels hoe de cellulaire automaat gaat veranderen. Het zal duidelijk zijn dat de verandering alleen zal plaatsvinden rond de rode cel. Daarom formuleren we de regels vanuit die cel. Alle regels gelden dus alleen als de cel rood is:

  1. Als een van je buurcellen (links, rechts, boven, onder) groen is: kleur die cel rood, en kleur je eigen cel geel. Stop daarna. [Ga naar de groene cel]
  2. Als een van je buurcellen leeg is, kleur die rood en kleur je eigen cel geel. [Ga naar een lege cel]
  3. Als geen van je buurcellen leeg is, maar er is wel een gele, kleur die rood, en de cel waar je vandaan komt blauw. [Volg het spoor terug]
  4. In alle andere gevallen stop je.

Hier is de simulatie:

Als je hem start, zie je dat de rode cel beweegt naar lege cellen. Wanneer er geen lege cellen in de buurt zijn, volgt hij het gele spoor terug, tot er weer een lege cel is die geprobeerd kan worden, net zolang tot de uitgang is bereikt.  Het gele spoor tekent de gevolgde weg. De gele vakjes zou je daarom ook broodkruimels kunnen noemen. Het weer teruggaan naar eerder neergelegde broodkruimels noemen we backtracken.

Als je wilt kun je opnieuw beginnen en met muisklikken muren bijmaken of wegbreken, en kijken hoe de route verandert, of onmogelijk wordt.

Omdat de regels er voor zorgen dat er altijd maar één rode cel is, is het verleidelijk die een eigen identiteit te geven. Het is de representatie van de persoon die de uitweg zoekt. De gekleurde cel wordt een ding, met een eigen gedrag. Zoiets wordt een agent genoemd, en de simulatie wordt dan, in goed Nederlands,  een agent-based simulation. Aardig van deze simulaties is dat ze laten zien dat je met weinig eenvoudige regels relatief ingewikkeld gedrag kunt begrijpen.

 

2 gedachten over “De weg uit het doolhof

  1. Gaaf principe, uitdagender dan het opzetten van een boomstructuur. Ik vroeg me alleen af wat er gebeurt als er een doodlopend stuk rondloopt, dan kan de agent niet verder, toch?

  2. Klopt, als je in een soort lus terechtkomt loopt hij vast en volgt het spoor terug, uiteindelijk naar zijn beginpositie.

Geef een reactie