Prírodou inšpirované algoritmy

Vytváranie mapy ulíc

Rozšírené L-systémy

V štandardnom L-systéme, vždy keď je potrebné implementovať nové ohraničenie, tak musí byť veľa pravidiel prepísaných. Takto sa rozšíriteľnosť systému stáva obtiažnou. V tomto systéme sa namiesto implementovania parametrov do pravidiel, vytvára v každom kroku akási obecná šablóna - ideal successor. Takto sa modifikácia a nastavovanie parametrov prenieslo do externých funkcií. Tieto funkcie voláme globalGoals a localConstrains.

Pri aplikovaní pravidiel na reťazec modulov sa vykonajú nasledovné akcie:

• LS sa vráti k ideal successor a parametre nie sú k modulom priradené.
• Volanie funkcie globalGoals. Táto funkcia určuje hodnoty parametrov dominantných globálnych cieľov a nastavia sa všetky hodnoty parametrov.
• Volanie funkcie localConstrains. Parametre sa kontrolujú v rámci lokálnych ohraničení prostredia. Ak sa takto nedajú nastaviť, tak je tento modul vymazaný.

Nástroj pre tvorbu ciest rozlišuje medzi nasledovnými globálnymi cieľmi a lokálnymi ohraničeniami:

• globálne: vzory ulíc a populačná hustota
• lokálne: hranice súše/vody/parkov, križovanie ulíc a nadmorská výška

Takýmto spôsobom je možné bez zmeny pravidiel pridávať nové ciele a ohraničenia.

Pre tvorbu všetkých príkladov boli použité nasledovné pravidlá:

w: R(0, initialRuleAttr) ?I(initRoadAttr, UNASSIGNED)
p1: R(del, ruleAttr) : del<0 ® e
p2: R(del, ruleAttr) > ?I(roadAttr,state) : state==SUCCEED {globalGoals(ruleAttr,roadAttr) creates the parameters for: pDel[0-2], pRuleAttr[0-2], pRoadAttr[0-2]}® +(roadAttr.angle)F(roadAttr.length) B(pDel[1],pRuleAttr[1],pRoadAttr[1]), B(pDel[2],pRuleAttr[2],pRoadAttr[2]), R(pDel[0],pRuleAttr[0]) ?I(pRoadAttr[0],UNASSIGNED) p3: R(del, ruleAttr) > ?I(roadAttr, state) : state==FAILED® e
p4: B(del, ruleAttr, roadAttr) : del>0®B(del-1, ruleAttr, roadAttr)
p5: B(del, ruleAttr, roadAttr) : del==0®[R(del, ruleAttr) ?I(roadAttr, UNASSIGNED)]
p6: B(del,ruleAttr,roadAttr) : del<0® e
p7: R(del,ruleAttr) < ?I(roadAttr,state) : del<0® e
p8: ?I(roadAttr,state) : state==UNASSIGNED {localConstraints(roadAttr) adjusts the parameters for: state, roadAttr}® ?I(roadAttr, state)
p9: ?I(roadAttr,state) : state!=UNASSIGNED® e

Axióma w inicializuje L-systém s cestným modulom R a požiadavkou (query) pre križovatku ?I. Tento segment musí byť umiestnený vnútri oblasti vstupných užívateľských dát. Prvé tri pravidlá kontrolujú modul R. Pravidlo p2 riadi tvorbu ciest a vetvenia. Vytvoria sa dva vetviace moduly, B a cestný modul R plus ?I. Ich atribúty sa inicializujú vzhľadom na globálne ciele, ktoré vracajú reťazec atribútov (pDel[0-2]pre zmazanie vetvy, pRuleAttr[0-2] pre špecifické atribúty pravidla a pRoadAttr[0-2] pre cestné data ako dlžka, uhol atd.)

Modul R používa del parameter ako značku zastavenia: Funkcia globálnych cieľov ju môže nastaviť na zápornú hodnotu a R modul sa potom v ďalšej iteracií vymaže pravidlom p1. V p3 sa každý modul v stave FAILED, ktorý je nastavený funkciou lokálnych ohraničení taktiež vymaže.

Pravidlo p5 vytvorí nový cestný segment v bode vetvenia po tom, ako čas oneskorenia klesne na nulu. Funkcia globalGoals môže obmedziť vetvy nastavením ich del parametra na zápornú hodnotu. Pravidlo p7 zmaže modul ?I v prípade, kde globalGoals v p2 nastavia oneskorenie výsledného modulu na zápornú hodnotu. Posledné dve pravidla určujú aktuálnu tvorbu cesty, kontrolujúc čí sú splnené všetky lokálne ohraničenia volaním funkcie localConstrains, ktorá nastavuje hodnoty v roadAttr. Stavová pramenná je modifikovaná localConstrains na FAILED alebo SUCCED a určí, čí je road segment vytvorený.

Populačná hustota

Hlavné cesty spájajú centrá populácie. Za účelom nájdenia ďalších populačných centier sa vysielajú lúče z konca hlavnej cesty v rámci vopred nastaveného uhla. Pozdĺž týchto lúčov sa berú vzorky z mapy populačnej hustoty. Populácia v každom bode spolu s váhou vo forme inverznej vzdialenosti od konca cesty sa zráta. Smer s najväčšou sumou je vybratý pre ďalší rast. Tento mechanizmus je opísaný na obrázku dole.

Ulice sú tvorené podľa určitého dominantného vzoru. Je to preto, lebo väčšina ulíc v mestských oblastiach je stavaná podľa určitého plánu.

Vzory ciest

Ďalším dôležitým cieľom je súlad ciest s dominantnými vzormi v oblasti. Ulice sú takto obmedzené na vzory, ktoré môžu vytvárať. Tento systém používa niekoľko vzorov, ktoré sa používajú na mapu ulíc a zgrupuje ich do rozdielnych pravidiel:

• Základné pravidlo: Je to najjednoduchšie pravidlo. Všetky cesty sledujú populačné hustoty. Hlavne staršie časti ulíc majú takéto črty.
• Pravidlo New York: Sleduje zadaný globálny alebo lokálny uhol a maximálnu dĺžku a šírku jedného bloku. Je to najčastejší vzor, kde všetky hlavné cesty a ulice tvoria obdĺžnikové bloky.
• Pravidlo Paríž: Hlavné cesty tvoria hviezdicu okolo centra.
• Pravidlo San Francisko: Ulice a hlavné cesty sledujú trasu najmenšej morskej výšky. Cesty na rôznych výškach sú spojené menšími ulicami, ktoré sú čo najkratšie a najstrmšie. Tento vzor je v oblastiach s najväčšími rozdielmi v nadmorskej výške.

Prehľad vzorov použitých v CityEngine.

Ak je v danej oblasti aktívnych viac ako jeden vzorov, tak sa vyhodnotia všetky a takto môžu vzniknúť zmiešané vzory.

Lokálne ohraničenia

Funkcia lokálnych ohraničení sa vykonáva v dvoch krokoch:

• skontroluj čí časť cesty končí vnútri alebo prechádza zakázanou oblasťou
• hľadaj križovatku s inými cestami alebo cesty a križovatky, ktoré sú v rámci špecifikovanej vzdialenosti ku koncu tejto časti

Ak prvé pravidlo zistí, že cesta končí v nejakej zakázanej oblasti, tak sa systém pokúsi zmeniť hodnoty tejto časti cesty nasledujúcimi spôsobmi:

• orež časť cesty tak, aby bola v rámci dovolenej oblasti.
• otoč segment tak, aby bol v rámci dovolenej oblasti.
• hlavné cesty môžu križovať určitú zakázanú oblasť do nejakej špecifickej dĺžky. Daná časť cesty je označená a pri grafickom zobrazení môže byť nahradená napr. mostom alebo tunelom.

Ak funkcia lokálnych ohraničení nájde ulicu v rámci zadaného uhla konca cesty, tak môže vykonať nasledovné činnosti:

• ak sa dve ulice pretínajú potom vytvor križovatku
• ak je koniec cesty blízko existujúcej križovatky potom rozšír ulicu tak, aby dosiahla križovatku.
• ak je blízko cesty potom rozšír ulicu tak, aby vytvorila križovatku.

Obrázok dole ukazuje príklad vytvorenia cestnej mapy použitím zoskenovaných máp Manhatanského ostrova. Najstaršia časť Manhatanu bola vytvorená použitím nevyvíjajúceho sa vzoru. Novšie časti mesta boli vytvorené pomocou vzoru New York. Lokálne ohraničenia menia smer hlavnej cesty podľa tvaru pobrežia pozdĺž ostrova. Všimnite si, že navrhnuté mosty idú veľmi blízko miest, kde sú v skutočnosti.

Systém aplikovaný na Manhatan. Obrázky hore: sieť po 28 a 142 krokoch. Stred: výsledná mapa. Dole: Skutočná mapa.