Procedurele generatie

In de informatica verwijst procedurele generatie naar technieken om content ter plekke te genereren met behulp van algoritmen in plaats van het handmatig te creëren. De content wordt door het computerprogramma gegenereerd wanneer het programma wordt uitgevoerd; dit staat tegenover content die voor distributie van het programma wordt ontwikkeld en meegeleverd zodat het programma het kan gebruiken. Procedurele generatie wordt met name gebruikt in films, grafische software en bij het ontwikkelen van levels in computerspellen. Voorbeelden van zaken die procedureel gegenereerd kunnen worden zijn landschappen, texturen en 3D objecten. Geluid wordt zelden procedureel gegenereerd, met uitzondering van spraaksynthese.

Geschiedenis[bewerken | brontekst bewerken]

Computerspellen[bewerken | brontekst bewerken]

De eerste computerspellen hadden weinig geheugen ter beschikking waardoor ze content ter plekke moesten genereren: er was simpelweg onvoldoende geheugen om een level en andere zaken in het geheugen te bewaren. Met behulp van toevalsgeneratoren werden levels gegenereerd die er handgemaakt uitzagen. The Sentinel (1986) had bijvoorbeeld 10.000 unieke levels in slechts 48 of 64 kilobytes. In Elite (1984) werden gehele sterrenstelsels gegenereerd aan de hand van de rij van Fibonacci.^[1] Andere voorbeelden zijn Rescue on Fractalus! (1985) waarin de heuvels van een planeet gegenereerd werden en River Raid (1982) waarin een doolhof met obstakels gegenereerd werd.

In 2004 werd .kkrieger uitgebracht, een first-person shooter voor de pc; het spel was kort en eenvoudig maar alle grafische effecten waren teruggebracht tot slechts 96 kilobyte. Dit is een groot verschil met commerciële spellen die verspreid over meerdere cd's verkocht worden en vaak meer dan 2 gigabyte in beslag nemen. Het spel RoboBlitz (2006) maakte gebruik van procedurele generatie en het kon hierdoor via Xbox Live Arcade verspreid worden.

Het spel Spore (2008), ontworpen door Will Wright, maakt veelvuldig gebruik van procedurele generatie. De wezens in Spore worden volledig procedureel geanimeerd en vormgegeven. Ook de omgeving wordt procedureel gegenereerd. In de first-person shooter Borderlands (2009) van Gearbox Software worden honderdduizenden wapens procedureel gegenereerd.

Demoscene[bewerken | brontekst bewerken]

De demoscene is een subcultuur die zich bezighoudt met maken van computerprogramma's, demo's genaamd, die visuele kunst procedureel genereren. In deze demo's tracht men de hardware (met name de processor en de videokaart) zo efficiënt mogelijk te gebruiken om allerlei effecten te produceren. Veel hedendaagse technieken waren voor het eerst te zien in demo's.

Films[bewerken | brontekst bewerken]

In films wordt procedurele generatie gebruikt om bijvoorbeeld landschappen, planeten of andere omgevingen te genereren. De omgevingen in Star Trek: Nemesis (2002) en Stealth (2005) zijn bijvoorbeeld gegenereerd met EnGen (Environment Generator) van Digital Domain, een aangepaste versie van Terragen 2.^[2] Procedurele animatie wordt gebruikt om grote groepen mensen of andere personages te animeren, zoals een kudde dieren of legers. Voorbeelden zijn de wildebeesten in De Leeuwenkoning^[3] (1994) en een leger Hunnen in Mulan^[4] (1998).

Procedurele generatie biedt ook de mogelijkheid om allerlei voorwerpen te genereren die lichtelijk van elkaar verschillen of om imperfecties toe te voegen. Dit geeft een realistisch effect aangezien in werkelijkheid geen twee objecten exact hetzelfde zijn. De schappen in een supermarkt kunnen zo bijvoorbeeld gevuld worden met allerlei producten zonder dat elk product handmatig vormgegeven hoeft te worden.

Techniek[bewerken | brontekst bewerken]

De gebruikte functies bij procedurele generatie dienen referentieel transparant te zijn. Hierdoor kunnen ze in willekeurige volgorde na elkaar toegepast worden en de tussenresultaten kunnen in een cache bewaard worden voor efficiëntie. Dit is vergelijkbaar met luie evaluatie in functionele programmeertalen.

Het genereren van texturen wordt vaak gedaan met behulp van wiskundige technieken, zoals fouriertransformatie en wavelets.^[5]

Toepassingen[bewerken | brontekst bewerken]

Terrein[bewerken | brontekst bewerken]

Een visuele weergave van een hoogtemap: hoe lichter een pixel, hoe hoger het terrein.

Ragdoll physics zijn een voorbeeld van procedurele animatie.

Procedurele generatie kan gebruikt worden om een terrein te genereren aan de hand van verschillende karakteristieken, zoals heuveligheid en wateren, maar ook voor de mate van begroeiing.

De meeste computerapplicaties maken voor terrein gebruik van een hoogtemap (heightmap): een tweedimensionale afbeelding waarin de hoogte van het terrein is opgeslagen. Er bestaan vele algoritmen waarmee een realistische hoogtemap gegenereerd kan worden.^[6]^[7] Deze algoritmen houden bijvoorbeeld rekening met het verschil tussen twee punten in de hoogtemap: hoe geleidelijker het verschil, hoe geleidelijker de heuvels in het landschap. Deze algoritmen bepalen alleen het verloop van het terrein; andere algoritmen kunnen toegepast worden om de texturen toe te voegen en de begroeiing en/of bebouwing.

Voorbeelden van algoritmen voor het genereren van terrein zijn het diamond-square algoritme, Perlin noise (wordt voor allerlei doeleinden gebruikt) of algoritmen die gebaseerd zijn op fractals. Ook kunnen wiskundige functies en technieken gebruikt worden, zoals splines. Een andere aanpak is het simuleren van natuurkundige processen, zoals erosie van water, platentektoniek of inslagen van meteorieten.

Animatie[bewerken | brontekst bewerken]

Procedurele animatie wordt gebruikt om deeltjes te simuleren (zoals rook, vuur of water) en de bewegingen van kleding, haar of vacht. Daarnaast wordt het gebruikt voor het bewegen van personages en voorwerpen. Procedurele animatie is een vorm van digitale animatie.

Voor het bewegen van personages kan inverse kinematica gebruikt worden. Hierbij wordt de beweging van de ledematen (zoals de hoeken en de snelheden waarmee ze bewegen) berekend aan de hand van de posities van de ledematen op bepaalde tijdstippen.

Een andere techniek is animatie op basis van gedrag (behavioral animation): bij deze aanpak wordt de animatie berekend door aan te geven hoe een personage reageert op zijn omgeving. De animatie wordt niet vastgelegd maar dynamisch uitgevoerd afhankelijk van de omstandigheden. Een personage kan reageren op dingen in zijn omgeving maar ook op het gedrag van andere personages. Met deze techniek kunnen grote groepen dieren of mensen geanimeerd worden door gedragsregels aan te geven voor de afzonderlijke leden van de groep. Hieruit kan gedrag ontstaan dat niet direct te herleiden is tot bepaalde gedragsregels maar wat veroorzaakt wordt door de samenwerking van de gedragsregels (dit wordt emergent gedrag genoemd).

In computerspellen wordt soms ragdoll physics gebruikt om personages te kunnen animeren bij het vallen of wanneer ze door iets geraakt worden. Bij ragdoll physics wordt de beweging van een skelet gesimuleerd: een personage wordt opgebouwd uit ledematen die op bepaalde punten aan elkaar vastzitten. Om de rekentijd te beperken was de simulatie vaak eenvoudig en hield het geen rekening met de onmogelijkheid van bepaalde draaibewegingen van gewrichten. Het lichaam kon zo in allerlei onnatuurlijke houdingen terechtkomen.

Texturen[bewerken | brontekst bewerken]

Procedurele texturen gegenereerd met Art of Illusion.

Texturen kunnen op verschillende manier gegenereerd worden: het is mogelijk een textuur te genereren met wiskundige technieken of men kan een textuur produceren met behulp van bestaande afbeeldingen.

Het dynamisch genereren van texturen biedt ook nieuwe mogelijkheden in bijvoorbeeld computerspellen. De texturen kunnen veranderd worden tijdens het spel. Zo kan men een verouderingsproces laten verlopen naarmate de tijd in het spel vordert.^[5]

Procedurele texturen dienen niet verward te worden met textuursynthese waarbij men een textuur tracht te produceren met dezelfde kenmerken als het origineel. Bij procedurele texturen wordt een nieuwe textuur geproduceerd op basis van algoritmen met parameters terwijl bij textuursynthese een bestaande textuur centraal staat. Bij procedurele generatie van texturen kunnen wel hulpafbeeldingen gebruikt worden maar de uiteindelijke textuur kan volledig verschillen van de gebruikte hulpafbeeldingen. Dit is bij textuursynthese niet het geval: daar lijkt de geproduceerde textuur zo veel mogelijk op het gebruikte origineel.

Objecten[bewerken | brontekst bewerken]

Procedurele generatie kan ook gebruikt worden voor andere doeleinden, zoals bijvoorbeeld gebouwen^[8] en steden^[9]. Een driedimensionaal object bestaat uit allerlei veelhoeken en er kan een algoritme ontwikkeld worden wat zo'n driedimensionaal object genereert aan de hand van parameters. Ook andere structuren, zoals wegennetwerken, kunnen gegenereerd worden.