Space colonization van A. runions
1 basis algoritme voor meerdere toepassingen

Published
juli 21, 2020

Procedurele algoritmes zijn vaak geïnspireerd door natuurlijke fenomenen. Een zeer populair algoritme is Space Colonization. Dit algoritme werd door Adam Runions et al. voorgesteld om de groei van nerven in een blad (verder bladvenatie genoemd) te simuleren. Veel fenomenen in de natuur volgen gelijkaardige principes als deze van zijn venatie algoritme, hierdoor is dit algoritme over de jaren heen gebruikt voor verschillende andere toepassingen. Bijvoorbeeld: wegen- en stedengeneratie, boomgeneratie en zelfs als basis voor crowd simulaties.

In deze blogpost bespreken we de basis van dit algoritme en hoe dit zeer snel van 1 implementatie kan worden uitgebreid naar verschillende toepassingen kunnen gaan.

Bladvenatie

Space colonization rust op een simulatie lus waarbij elke nieuwe stap een iteratie is op de vorige, aan de hand van bron punten en doel punten. Elke iteratie worden er nieuwe bron- en doelpunten geplaatst. Zo verkrijgen we een groei simulatie met competitie voor plaats. We leggen dit verder uit aan de hand van blad venatie. 

In het venatie algoritme begint men eerst met een stam op een bladvorm waaruit de bladnerven zullen groeien (a). Dan plaatst men verschillende auxin bronnen in de vorm van punten (rode punten op de afbeelding) op willekeurige plaatsen op het blad. Auxin is een groeihormoon in planten die cel groei promoot. In dit algoritme worden het gebruikt als doelen waar de bladnerven naar toe zullen groeien.

Elke auxin bron zoekt het dichtstbijzijnde bladnervenpunt binnen een bepaalde radius. Bij open venatie kan elke auxin bron maar met 1 nervenpunt gelinkt worden, maar een nervenpunt kan met meerdere auxin bronnen gelinkt zijn. Hierna worden de richtingsvectoren vanuit het aderpunt naar de gelinkte auxin punten berekend. Als een ader punt meerdere richtingsvectoren heeft, dan wordt het gemiddelde hiervan genomen en de nieuwe aderpunten worden 1 unit lengte verder geplaatst op deze nieuwe vectoren.

A. Runions

Als de bladaders te dicht bij een auxin bron komen, dan wordt deze bron verwijderd. Na elke iteratie vergroot men de blad oppervlakte en worden er nieuwe auxin punten geplaatst op nieuwe willekeurige locaties op het blad, met een voorkeur naar de bladrand. Indien deze nieuwe auxin bronnen te dicht bij bestaande auxin bronnen zijn, worden deze ook verwijderd om clusters van nerven te voorkomen. 

Hiernaast zie je een door ons uitgewerkt voorbeeld van dit algoritme in actie.

 

 

 

 

 

Andere toepassingen

Vervolgens hebben we dit toegepast op 3D meshes in de vorm van een physaryum polycephalum (slime mold) en klimop groeisimulatie. In plaats van de auxin bronnen te plaatsen op een 2D oppervlak dat meegroeit, plaatsen we nu de doelpunten op het 3D mesh oppervlak. Om ervoor te zorgen dat de nerven niet door de mesh groeiden hebben we een A* pathfinding algoritme toe gevoegd. Dit pathfinding algoritme gebruikt de 3D mesh als grid om over te lopen.

Dit algoritme is erg veelzijdig. Dit wordt geïllustreerd door de hoeveelheid voorbeelden die we vonden in papers van andere onderzoeksgroepen en in de industrie. Hieronder enkele voorbeelden.

Space colonization wordt toegepast om wegennetwerken en steden te generen in films en games (zie de Ghost Recon Wildlands blogpost). Hiernaast ziet u een voorbeeld van G. D. Fernandes en A. R. Fernandes die een gesloten space colonization algoritme gebruiken om zo een stratenplan voor niet gestructureerde steden te genereren.

G.D. en A.R. Fernandes

E. de Lima Bicho beschrijft in zijn paper uitgebracht hoe hij dit algoritme toegepast wordt op een crowd simulatie.

Bij een crowd simulatie is het competitie voor plaats onderdeel van space colonization heel interessant. Zoals we konden observeren bij de bladvenatie en de slime mold simulaties, zal het algoritme vermijden om doorheen zichzelf te groeien, een soort van collision avoidance. Door alle mogelijke doelpunten een score te geven, kunnen we de agents sturen (bijvoorbeeld: over zebrapaden, vermijden van motorwegen, etc), zonder onze agents een vast pad te geven en hebben ze dus nog de vrijheid om te manoeuvreren indien nodig.

Hierdoor verkrijgen we dus een snelle, efficiënte crowd simulatie techniek zonder collision berekeningen.

Conclusie

Een procedureel algoritme kan vaak als basis dienen om meerdere systemen die nodig zijn voor een project aan te sturen. De kost om het initiële algoritme op te bouwen wordt zo verlaagd door de inzetbaarheid op verschillende toepassingen.