Procedural content generation

[armageddon_2k1]

Ik las in de PC Gameplay een reuze interessant artikel over procedural content generation. Hoogstwaarschijnlijk kennen de meeste van jullie het wel, maar ik leg het toch even uit. Het basis idee is dat je gegevens genereert en niet daadwerkelijk zelf helemaal maakt.

Stel je wil een fictief planetenstelsel modelleren. Wat je dan kan doen, en wat ook vaak gedaan wordt, is een planeet modelleren in 3ds Max, hier textures voor maken. Vervolgens maak je modellen voor de steden, huisjes, rivieren, bossen etc. Best veel werk. Maar het is wel te doen. Het wordt een probleem echter wanneer je besluit om dan die andere 21 (voorbeeldje he? ) planeten wil modelleren....dat wordt gewoon een rotwerk. Stel nou dat die ene planeet 100MB was kwa informatie (textures, modellen etc.) dan wordt het hele stelsel 2,2GB.

Wat de insteek van Procedural Content Generation (PCG) dan is om eigenlijk uit te gaan van een paar basis modellen, textures, physiscs regels etc. en deze algoritmisch aan te passen tot unieke instanties. Je genereert algoritmisch een aarde en de rivieren, landmassa's etc etc. Als je dit nu ook nog doet met een bepaalde randomness met een seed erin, kan je eigenlijk 1 unieke planeet koppelen aan 1 enkele seed. Je hebt dus 1 algoritme om een planeet en z'n flora en fauna uit te rekenen mbv een stel basisblokken van pakweg 100mb. Hoeveel planeten je ook genereert...de basisblokken zullen niet veranderen kwa grootte. En voor 1 miljoen unieke planeten heb je alleen maar een bestandje nodig met 1 seed in principe erin bij wijze van spreken en dus dit algoritme met z'n bijbehorende basisblokken.

Ik wist dat er wel al onderzoek was naar deze techniek maar niet dat er nu weer daadwerkelijk games gemaakt werden. Het idee is eigenlijk al heel oud. Ten tijde van Elite en Elite II was het onmogelijk veel ruimte te gebruiken op een computer en toch bevatten deze games vele duizenden, wellicht wel miljoenen, planeten. Nu is er echter een opvolger en die wou ik jullie ook niet onthouden, namelijk Infinity (http://www.fl-tw.com/Infinity/) en je hebt natuurlijk Spore (http://www.spore.com/) dat hetzelfde idee toepast. Ook Speedtree (http://www.speedtree.com) is onderhand bekend.
Echter het meest indrukwekkende voorbeeld is wel .kkrieger van .theprodukkt (http://www.theprodukkt.com/kkrieger) wat er uitziet als een waardige tegenstander van de laatste Unrea Tournament, maar maar 96kb groot is. En een oude bekende is natuurlijk Diablo II (http://www.blizzard.com/diablo2/).

Waarom dit topic dan?
Ten eerste om degene die er niet bekend mee zijn dit te laten zien en hopen dat ze ook net als ik echt een enorm *wow*-gevoel krijgen.
Ten tweede om te vragen of er misschien mensen bezig zijn met zulke projecten of projectjes in hun vrije tijd en dat willen laten zien. Ik ben zelf bezig (als testje begonnen) met een doolhofgenerator die puur op randomness mbv een seed gebaseerd is. Niet spectaculair, wel leuk.
Ten derde omdat ik eigenlijk vrij weinig informatie kan vinden over dit onderwerp en ik hoop of mensen wellicht links etc hebben waar ik verder kan loeren.
Ten vierde omdat ik wel graag een discussie wil starten over wat dit betekend voor de (games)toekomst.

Mijn idee over de (games)toekomst is toch wel dat PCG een enorme invloed gaat hebben in de computerwereld. Het einde van de enorme textures en gigantisch data die het inneemt voor een enkele game komt langzaam in zicht en de processoren zijn onderhand zo krachtig dat die (helemaal met het dual/quad-core verhaal) meer en meer geschikt zijn hiervoor. Als we zo doorgaan neemt een game binnenkort vele GB's in. Binnenkort wordt het misschien mogelijk om 3d games te maken waar het oppervlakte met gemak een gebied als europa beslaat. Of wellicht handig voor 3d-film- en effectenspecialisten die dus unieke explosies/bomen/textures in een handomdraai kunnen maken, waardoor het er nog realistischer uit gaat zien. Zelfs op animatiegebied kan het mooier (zie Spore), want ook daar is PCG mogelijk. Maar misschien nog wel interessanter, is dat de ontwikkelingskosten omlaag kunnen. Als we op het huidige ontwikkelingstempo doorgaan kwa games is een game over 10 jaar bijna onbetaalbaar voor een ontwikkelaar, omdat er alleen al 500 mensen met de textures bezig zijn. Aangezien er minder mensen nodig zijn om al die individuele content te maken en er eigenlijk een kleinere groep is voor de basiscontent + algoritmes is er misschien meer ruimte voor risico en dus originaliteit. Volgens mij is er een ware revolutie in gamesland op til Nu maar hopen dat de mainstream ontwikkelaars dit ook (gaan) zien.

Jullie visie, links, verhalen, projectjes etc zijn erg welkom

[Creepy]

Nog even geen visie, links, verhalen, projecties etc van mij, maar wel een move naar SEA aangezien we hier niet echt over implementatie en taal specifieke zaken bezig zijn

[RobIII]

armageddon_2k1 schreef op zondag 21 januari 2007 @ 00:00:
En voor 1 miljoen unieke planeten heb je alleen maar een bestandje nodig met 1 miljoen seed nr's erin bij wijze van spreken en dus dit algoritme met z'n bijbehorende basisblokken.

Waarom zou je een miljoen seed nr's nodig hebben? Ook die kun je procedureel genereren hoor Vele (Semi)RNG's hebben een bepaalde seed die vervolgens altijd dezelfde sequence oplevert

armageddon_2k1 schreef op zondag 21 januari 2007 @ 00:00:
Het idee is eigenlijk al heel oud.

Ik denk dat je nog maar een klein idee hebt van hoe oud het al is. In de tijd dat geheugen schaars was werd menig spel zo opgebouwd, de gemiddelde "demo" (uit "the scene") deed het er zelfs om en daarmee doel ik dan voornamelijk, maar niet alleen, op de 64k of minder demo's.

armageddon_2k1 schreef op zondag 21 januari 2007 @ 00:00:
Ten tweede om te vragen of er misschien mensen bezig zijn met zulke projecten of projectjes in hun vrije tijd en dat willen laten zien. Ik ben zelf bezig (als testje begonnen) met een doolhofgenerator die puur op randomness mbv een seed gebaseerd is. Niet spectaculair, wel leuk.

Daar heb je weer zo'n voorbeeld dat in mijn "286-tijd" ook al bestond, maar nogmaals: zo'n beetje elk spel of demo of non-kantoor-app deed dat in die tijd wel in meer of mindere mate.

armageddon_2k1 schreef op zondag 21 januari 2007 @ 00:00:
Ten derde omdat ik eigenlijk vrij weinig informatie kan vinden over dit onderwerp en ik hoop of mensen wellicht links etc hebben waar ik verder kan loeren.

Wellicht omdat het toen de normaalste gang van zaken was; alleen is het anno 2005/2006 verheven tot niveau's als Spore dat doen; toch was het indertijd ook heel gangbaar.

armageddon_2k1 schreef op zondag 21 januari 2007 @ 00:00:
Ten vierde omdat ik wel graag een discussie wil starten over wat dit betekend voor de (games)toekomst.

Het is al jaren mogelijk (ik ben niet zo'n gamer dus heb niet echt goede voorbeelden) om bijvoorbeeld random levels te genereren. Kijk eens naar Worms bijvoorbeeld. Zolang het level aan bepaalde grondregels voldoet valt er prima iets voor te randomizen.

armageddon_2k1 schreef op zondag 21 januari 2007 @ 00:00:
Mijn idee over de (games)toekomst is toch wel dat PCG een enorme invloed gaat hebben in de computerwereld. Het einde van de enorme textures en gigantisch data die het inneemt voor een enkele game komt langzaam in zicht en de processoren zijn onderhand zo krachtig dat die (helemaal met het dual/quad-core verhaal) meer en meer geschikt zijn hiervoor.

De texture's e.d. zijn wellicht groter en processor intensiever, maar wederom was het "in die tijd" ook prima mogelijk om ("pre-rendered") textures en levels te genereren. Kijk eens naar Outcast bijvoorbeeld (die is nog niet eens zo heel oud trouwens); die werkte met een voxel-engine waarmee je prima random landschappen realtime kunt genereren. Ik doe even een gok (nogmaals; ik ben niet zo'n games kenner) maar games als Creatures, The Sims en zelfs Pacman bouw(d)en min of meer op zulke principes. Waarmee ik dus wil aangeven dat het helemaal niet zo wereldschokkend is, maar dat maakt mijn respect voor developers van games als Spore echt niet minder.
Ik verzin maar even wat (weet dus niet of het zo is) maar games als bijvoorbeeld Boulderdash ( ) zouden prima geschikt zijn voor deze techniek en ik vermoed dan ook dat die in meer of mindere mate ook gebruikt werden. Misschien niet zo zeer voor de "blokken" (textures) maar wel voor de levels an sich.

armageddon_2k1 schreef op zondag 21 januari 2007 @ 00:00:
Binnenkort wordt het misschien mogelijk om 3d games te maken waar het oppervlakte met gemak een gebied als europa beslaat.

Dat is dus nu al prima mogelijk; of er spelers zijn die letterlijk 3 jaar willen zoeken naar die ene "poort" of "deur" in zo'n gigantisch level is natuurlijk een tweede. Wederom; ik weet amper iets van games, maar bevat WoW niet van dergelijke ongelofelijk grote speelvelden?

armageddon_2k1 schreef op zondag 21 januari 2007 @ 00:00:
Jullie visie, links, verhalen, projectjes etc zijn erg welkom

Bij deze dus mijn 2 cent; het is misschien voor jou een ontdekking, maar nieuw is het zeer zeker niet

[ Voor 3% gewijzigd door RobIII op 21-01-2007 00:25 ]

[Not Pingu]

armageddon_2k1 schreef op zondag 21 januari 2007 @ 00:00:
Wat de insteek van Procedural Content Generation (PCG) dan is om eigenlijk uit te gaan van een paar basis modellen, textures, physiscs regels etc. en deze algoritmisch aan te passen tot unieke instanties. Je genereert algoritmisch een aarde en de rivieren, landmassa's etc etc. Als je dit nu ook nog doet met een bepaalde randomness met een seed erin, kan je eigenlijk 1 unieke planeet koppelen aan 1 enkele seed.

Wat is dan het random element erin? Ervan uitgaande dat de seed slechts een opmaat vormt voor het uiteindelijk random product.

Ik wist dat er wel al onderzoek was naar deze techniek maar niet dat er nu weer daadwerkelijk games gemaakt werden. Het idee is eigenlijk al heel oud. Ten tijde van Elite en Elite II was het onmogelijk veel ruimte te gebruiken op een computer en toch bevatten deze games vele duizenden, wellicht wel miljoenen, planeten. [..] En een oude bekende is natuurlijk Diablo II (http://www.blizzard.com/diablo2/).

Levels / locaties on-the-fly genereren of inrichten is idd al heel oud, maar dat wordt dan ook niet bedoeld met PCG.

Overigens denk ik dat je een te rooskleurig beeld hebt van PCG. Ik merk dat het idee je fantasie in gang heeft gezet. Het probleem is echter dat er weinig garantie is dat een computer echt interessante content genereert. Het probleem met random gegenereerde levels zoals in Diablo 2 is dat de computer minder makkelijk kan kijken of er bijv. wel een pad is voor de speler om naar het doel te komen, of controleren of ergens een erg ongebalanceerd gedeelte is gemaakt.

Er zijn nou eenmaal dingen die je een computer niet kunt aanleren, zoals het maken van een origineel verhaal. PCG kan ook hooguit random combinaties maken van bouwstenen die ontworpen zijn.

Mijn idee over de (games)toekomst is toch wel dat PCG een enorme invloed gaat hebben in de computerwereld. Het einde van de enorme textures en gigantisch data die het inneemt voor een enkele game komt langzaam in zicht en de processoren zijn onderhand zo krachtig dat die (helemaal met het dual/quad-core verhaal) meer en meer geschikt zijn hiervoor.

Het is een trade-off, of je genereert de textures vantevoren en slaat ze op en spaart de processor, of je genereert ze on-the-fly en spaart je... DVD speler? Want die textures die worden gegenereerd moeten nog steeds in het geheugen worden opgeslagen.

Bovendien is niet voor elk patroon of texture een 'slim' algorithme te bedenken.

[Verwijderd]

Not Pingu schreef op zondag 21 januari 2007 @ 00:29:
Er zijn nou eenmaal dingen die je een computer niet kunt aanleren, zoals het maken van een origineel verhaal. PCG kan ook hooguit random combinaties maken van bouwstenen die ontworpen zijn.

Een met de hand gemaakt level is natuurlijk ook gewoon één specifieke combinatie van bouwstenen. Het opstellen van een dusdanig 'slim' algoritme dat combinaties maakt die hetzelfde niveau van afwerking hebben als een met de hand gemaakte kan uiteraard erg ingewikkeld worden, maar dit betekent niet dat het onmogelijk is.

[Verwijderd]

Ik heb een paar week terug aan de hand van het pcgp artikel Infinity eens geprobeerd en de filmpjes bekeken, zag er indrukwekkend uit.

In het geval van Infinity vertellen ze dat ze werelden/stelsels kunnen maken die zij als programmeur en wij als speler nooit in 1 echte mensenleven kunnen opzoeken. Dat is iets wat mij wel aantrekt. En als de content dan ook nog eens interessant is om over te chatten/praten en het visuele ook aantrekkelijk is om te showen in de vorm van screenshots bijvoorbeeld. Lijkt me leuke communities opleveren die elkaar dingen kunnen showen of samen, in dit geval, zonnestelsels bezoeken etc. gaan waar nog nooit iemand anders is geweest


Wat ik gelezen heb is dat PCG momenteel als nadeel heeft dat je mensen moet hebben die nogal een kennis van wiskunde moeten hebben en dat die er naar verhouding maar weinig zijn. Maar dat moet vanzelf groeien als deze techniek vaker gebruikt gaat worden.
Wat ik ook nog weleens lees is de vergissing dat PCG random zou zijn, maar kan zo even niet een mooi artikel vinden waar het tegendeel uitgelegd wordt.

Voordeel (volgens mij stond dat in de pcgp artikel) is dat je jaren later vrij makkelijk een grafische update kunt uitvoeren in de vorm van een patch die maar een paar kB of MB groot is. En dat brengt gelijk een nadeel met zich mee want welk bedrijf wil nu eigenlijk zo'n spel maken want er moet tenslotte geld verdient worden en een spel dat "oneindig" is verkoopt niet (in de zin van opvolgers/andere games kopen omdat het oude al uitgespeeld is wat nu dan niet het geval zou zijn etc)...
Volgens mij waren de geruchten dat men bij Spore al diverse dingen eruit halen/laten om in toekomstige expansionpacks te stoppen maar officieel was de statement dat ze anders de releasedate niet zouden halen meende ik of iets in die trent.

[RobIII]

Verwijderd schreef op zondag 21 januari 2007 @ 01:21:
In het geval van Infinity vertellen ze dat ze werelden/stelsels kunnen maken die zij als programmeur en wij als speler nooit in 1 echte mensenleven kunnen opzoeken. Dat is iets wat mij wel aantrekt. En als de content dan ook nog eens interessant is om over te chatten/praten en het visuele ook aantrekkelijk is om te showen in de vorm van screenshots bijvoorbeeld. Lijkt me leuke communities opleveren die elkaar dingen kunnen showen of samen, in dit geval, zonnestelsels bezoeken etc. gaan waar nog nooit iemand anders is geweest

Ik vrees dat als je er een X-tal bezocht hebt dat de lol er weer gauw vanaf is. Ik denk dat je snel gaat zien dat het "procedural" is en dus een patroon gaat zien. Ik denk dan ook dat jullie het mooier voorstellen dan het werkelijk is.

Verwijderd schreef op zondag 21 januari 2007 @ 01:21:
Wat ik gelezen heb is dat PCG momenteel als nadeel heeft dat je mensen moet hebben die nogal een kennis van wiskunde moeten hebben en dat die er naar verhouding maar weinig zijn. Maar dat moet vanzelf groeien als deze techniek vaker gebruikt gaat worden.

Volgens mij valt die kennis van wiskunde die je nodig zou hebben best wel mee; procedural content is eigenlijk niets anders dan content die op basis van een x-tal "grondregels" word gegenereerd.

Verwijderd schreef op zondag 21 januari 2007 @ 01:21:
Wat ik ook nog weleens lees is de vergissing dat PCG random zou zijn, maar kan zo even niet een mooi artikel vinden waar het tegendeel uitgelegd wordt.

Random tot op zekere hoogte ja, maar omdat er dus aan een aantal "grondregels" moet worden voldaan (wil het speelbaar/bruikbaar blijven) is de "echte" randomness er natuurlijk uit en de mogelijkheden toch (min of meer) beperkt.

Verwijderd schreef op zondag 21 januari 2007 @ 01:21:
Voordeel (volgens mij stond dat in de pcgp artikel) is dat je jaren later vrij makkelijk een grafische update kunt uitvoeren in de vorm van een patch die maar een paar kB of MB groot is. En dat brengt gelijk een nadeel met zich mee want welk bedrijf wil nu eigenlijk zo'n spel maken want er moet tenslotte geld verdient worden en een spel dat "oneindig" is verkoopt niet (in de zin van opvolgers/andere games kopen omdat het oude al uitgespeeld is wat nu dan niet het geval zou zijn etc)...

Ook voor een spel dat "oneindig" is zijn prima updates/expansion packs te maken; kwestie van de grondregels uitbreiden/aanpassen.

Verwijderd schreef op zondag 21 januari 2007 @ 01:21:
Volgens mij waren de geruchten dat men bij Spore al diverse dingen eruit halen/laten om in toekomstige expansionpacks te stoppen maar officieel was de statement dat ze anders de releasedate niet zouden halen meende ik of iets in die trent.

Dat laatste lijkt mij persoonlijk geloofwaardiger en ook logischer; zo "erg" zijn die "grote boze bedrijven" nou ook weer niet en er is prima voort te borduren op reeds bestaande "oneindige" concepten zolang je maar nieuwe "grondregels" legt en mogelijkheden schept die er voorheen nog niet waren.

Wat ik wil duidelijk maken met deze (en vorige) post is dat (IMHO) procedural content genaration écht niet de vinding van de eeuw/jaar/maand is en dat er hier in dit topic veel meer van wordt verwacht dan er (tot op heden) waargemaakt kan worden (althans, dat gevoel krijg ik bij jullie posts).

edit: Schiet me nu wel een leuke te binnen:
Binnen NFSU kun je ook een "oneindig" aantal combinaties maken om je auto te pimpen (ik noem maar wat; 35 soorten spoilers, 50 soorten velgen, 15 body kits, 250 soorten bestickering enzovoorts enzovoorts). Maar wordt het spel daar werkelijk zo anders van? Het blijft hetzelfde spelletje, echter de "parameters" (handling, looks en dat soort zaken) veranderen in meer of mindere mate. Datzelfde concept kun je ook (min of meer) toepassen op Spore en consorten; hoewel het daar less obvious is misschien. Toch zal je wezen zich "voorspelbaar" gedragen aan de hand van een x-tal parameters die jij in je "wezen-designer" hebt gedefinieerd. Dat moet ook wel, want anders had je PC ook geen benul gehad wat 'ie er mee zou moeten doen.

[ Voor 13% gewijzigd door RobIII op 21-01-2007 01:51 ]

[Not Pingu]

Verwijderd schreef op zondag 21 januari 2007 @ 00:35:
Een met de hand gemaakt level is natuurlijk ook gewoon één specifieke combinatie van bouwstenen. Het opstellen van een dusdanig 'slim' algoritme dat combinaties maakt die hetzelfde niveau van afwerking hebben als een met de hand gemaakte kan uiteraard erg ingewikkeld worden, maar dit betekent niet dat het onmogelijk is.

Dat het theoretisch onmogelijk is zou ik niet durven beweren. Maar je geeft het proces van leveldesign wel heel erg ongenuanceerd weer. Een goed leveldesigner heeft kennis nodig van architectuur, compositie, kleurgebruik en natuurlijk gameplay. Dat zijn dingen die je momenteel niet in een algorithme kunt stoppen en naar mijn idee kan het nog heel lang duren voordat we zover zijn. Leuk om erover te fantaseren, maar dat je erover kunt fantaseren betekent nog niet dat het echt binnen handbereik is.

[armageddon_2k1]

RobIII schreef op zondag 21 januari 2007 @ 00:20:
[...]

Waarom zou je een miljoen seed nr's nodig hebben? Ook die kun je procedureel genereren hoor Vele (Semi)RNG's hebben een bepaalde seed die vervolgens altijd dezelfde sequence oplevert

Dat kan ook bijvoorbeeld Zo heb ik het nog niet gezien

[...]

Ik denk dat je nog maar een klein idee hebt van hoe oud het al is. In de tijd dat geheugen schaars was werd menig spel zo opgebouwd, de gemiddelde "demo" (uit "the scene") deed het er zelfs om en daarmee doel ik dan voornamelijk, maar niet alleen, op de 64k of minder demo's.
[...]

Daar heb je weer zo'n voorbeeld dat in mijn "286-tijd" ook al bestond, maar nogmaals: zo'n beetje elk spel of demo of non-kantoor-app deed dat in die tijd wel in meer of mindere mate.

Ik noem Elite en Elite II...die zijn erg oud. Ik denk dat ik dus wel idee heb hoe oud het is
Elite komt echt uit het 86/88-tijdperk. Dat is nogal wat ouder.

Wellicht omdat het toen de normaalste gang van zaken was; alleen is het anno 2005/2006 verheven tot niveau's als Spore dat doen; toch was het indertijd ook heel gangbaar.


[...]

Het is al jaren mogelijk (ik ben niet zo'n gamer dus heb niet echt goede voorbeelden) om bijvoorbeeld random levels te genereren. Kijk eens naar Worms bijvoorbeeld. Zolang het level aan bepaalde grondregels voldoet valt er prima iets voor te randomizen.


[...]

De texture's e.d. zijn wellicht groter en processor intensiever, maar wederom was het "in die tijd" ook prima mogelijk om ("pre-rendered") textures en levels te genereren. Kijk eens naar Outcast bijvoorbeeld (die is nog niet eens zo heel oud trouwens); die werkte met een voxel-engine waarmee je prima random landschappen realtime kunt genereren. Ik doe even een gok (nogmaals; ik ben niet zo'n games kenner) maar games als Creatures, The Sims en zelfs Pacman bouw(d)en min of meer op zulke principes. Waarmee ik dus wil aangeven dat het helemaal niet zo wereldschokkend is, maar dat maakt mijn respect voor developers van games als Spore echt niet minder.
Ik verzin maar even wat (weet dus niet of het zo is) maar games als bijvoorbeeld Boulderdash ( ) zouden prima geschikt zijn voor deze techniek en ik vermoed dan ook dat die in meer of mindere mate ook gebruikt werden. Misschien niet zo zeer voor de "blokken" (textures) maar wel voor de levels an sich.

Je noemt nu wel stuk voor stuk games die een stuk minder indrukwekkend zijn kwa schaal dan games als Elite en Infinity. Het is de schaal die PCG zo interessant maakt.

Dat is dus nu al prima mogelijk; of er spelers zijn die letterlijk 3 jaar willen zoeken naar die ene "poort" of "deur" in zo'n gigantisch level is natuurlijk een tweede. Wederom; ik weet amper iets van games, maar bevat WoW niet van dergelijke ongelofelijk grote speelvelden?

WoW heeft zeker niet zo'n grote wereld. Europa is erg groot hoor En dan nog, al had WoW zo'n grote wereld, dan was het niet met PCG gemaakt. Als ze dan een enorme landmassa toe willen voegen kost dat weer enorm veel tijd/schijfruimte etc. WoW is indrukwekkend, maar is eigenlijk puur gebouwd op het 'oude' idee van games maken.

Bij deze dus mijn 2 cent; het is misschien voor jou een ontdekking, maar nieuw is het zeer zeker niet

Zoals je dus hebt kunnen lezen heb ik ook gezegd dat ik al wist dat het bestond, dus een ontdekking vind ik het niet. Echter, met de huidige technieken is zoveel mogelijk dat ik het onder de aandacht wil brengen.

[Bergen]

Not Pingu schreef op zondag 21 januari 2007 @ 00:29:
[...]


Wat is dan het random element erin? Ervan uitgaande dat de seed slechts een opmaat vormt voor het uiteindelijk random product.

Hiervoor moet je even begrijpen wat een seed precies inhoudt.

De woorden 'seed' en 'random' kun je in 1 adem noemen. Als je als programmeur een programma 10 willekeurige getallen laat uitspugen, het programma afsluit, opent en nogmaals 10 getallen laat uitspugen, dan zul je zien dat het weer dezelfde 10 getallen zijn. Waarom? Omdat de randomizer niet is geinitialiseerd. Hij begint dus altijd bij hetzelfde getal, bij dezelfde 'seed'. De seed is zeg maar een intern begingetal voor de randomizer.

Door een randomizer bij de programmastart op een bepaalde seed in te stellen krijg je elke keer weer andere getallen. Tenzij je de randomizer steeds weer op dezelfde seed zet natuurlijk. Je zou bij elke start een andere seed kunnen maken door bijvoorbeeld zelf een seed van de huidige datum en tijd te maken. Die is bij elke start immers toch weer anders.

Dat laatste is in elke moderne taal geautomatiseerd. Binnen bijvoorbeeld Delphi kun je bij de programmastart simpelweg "randomize" aanroepen om de seed in te stellen op iets semi-willekeurigs. (Zal ook wel aan de hand van de datum/tijd gebeuren.)

Deze zin uit de topicstart...

En voor 1 miljoen unieke planeten heb je alleen maar een bestandje nodig met 1 miljoen seed nr's erin bij wijze van spreken [..]

...klopt dus ook niet. Een seed hoeft maar 1 maal, bij de programmastart, te worden ingesteld en dat gaat ook nog eens automatisch.

[edit]
Uit de Delphi-help:

Description

Randomize initializes the built-in random number generator with a random value (obtained from the system clock). The random number generator should be initialized by making a call to Randomize, or by assigning a value to RandSeed.

Do not combine the call to Randomize in a loop with calls to the Random function. Typically, Randomize is called only once, before all calls to Random.

[ Voor 14% gewijzigd door Bergen op 21-01-2007 10:25 ]

[armageddon_2k1]

Bergen schreef op zondag 21 januari 2007 @ 10:19:
...klopt dus ook niet. Een seed hoeft maar 1 maal, bij de programmastart, te worden ingesteld en dat gaat ook nog eens automatisch.

Je hebt gelijk. Ik dacht niet helemaal goed door eigenlijk Ik heb de tekst al aangepast.

Not Pingu schreef op zondag 21 januari 2007 @ 00:29:
Wat is dan het random element erin? Ervan uitgaande dat de seed slechts een opmaat vormt voor het uiteindelijk random product.

Je wil natuurlijk een complete wereld baseren op 1 enkele seed. Je wil natuurlijk niet dat als je de game opslaat dat je dan als je hem weer laadt dat je een hele andere wereld hebt. Als je echter een nieuwe game start wil je wel met een nieuwe seed beginnen.

[Mithrandir]

Ik snap niet dat jullie zo'n probleem maken van een implementatiedetail: de manier waarop je aan de 'willekeurige' getallen moet komen die je uit de seed genereert.

Iets veel lastigers is om uit de getallen die je hebt gegenereerd een zinvolle wereld te maken. Je moet niet vergeten dat het helemaal niet moeilijk is om iets te genereren. Iets leuks wat spannend is en moeilijk maar niet onmogelijk met een interessant verhaal, dát is moeilijk te genereren. Daar zou je je druk om moeten maken.

Je zou kunnen zeggen dat bijvoorbeeld world of warcraft een seed zou moeten gebruiken om een level te genereren, maar dat is helemaal geen goed idee. Het zou saai en monotoon worden. Spelers willen een duidelijke lijn in een verhaal kunnen ontdekken. Dat verhaal moet echter wel nieuw en spannend zijn. Zoiets kun je niet genereren; er is zoveel informatie nodig om ieder level uniek én uitdagend te maken dat je zoiets nooit in één seed zou kunnen stoppen, omdat dat gewoon teveel informatie is om in een seed kwijt te kunnen. (Als je heir meer over wilt lezen moet je zoeken naar informatietheorie: je kunt 100 bit aan pure informatie nooit kleiner maken dan die 100 bit, dus je kunt een goed uitgebalanceerd level nooit opslaan als slechts een seed)

[ Voor 43% gewijzigd door Mithrandir op 21-01-2007 14:03 ]

[armageddon_2k1]

Waarom gaan jullie ervan uit dat er dan alleen nog maar PCG gebruikt gaat worden? Ik zeg niet dat het toepasbaar is op alle games en al helemaal niet op verhaallijnen. Het is echter een hele goede tool imo om uitgebreidere games te maken met minder tijdsinvesteringen. Het is een werkwijze die perfect kan samenwerken met de huidige manier van werken. Infinity is juist een extreem voorbeeld. Logischere voorbeelden zijn algoritmes die ieder karakter er uniek uit laten zien in een game. Daarnaast zijn er ook al mooie resultaten met textures die al naar gelang de tijdsduur toeneemt verouderen. Dit is met gewone bitmap-technologie lastiger.

Ik snap echt niet waar jullie de ideeen vandaan halen dat complete games gemaakt worden op deze manier. Het is wel mogelijk (kijk naar Spore) echter.

@Mithrandir:
Hoe weet jij of een level saai en monotoon wordt door gebruik te maken van deze techniek? Het is net iets als zeggen dat games die gebruik maken van OOP saai en monotoon worden. Het is een compleet andere techniek. Diablo 2 maakt van PCG gebruik en de levels, vind ik althans, blijven uitdagend. Of het saai of monotoon wordt is compleet afhankelijk van wat voor basisblokken men gebruikt, wat voor algoritmes men maakt etc etc etc. Games als Spore, Infinity/Elite en .kkrieger verschillen dusdanig dat je er niet direct een label op kan plakken.
Daarnaast is jou informatietheorie-voorbeeld niet nuttig. Ik kan je zo vertellen dat ik wel met C# 1000 bitmapjes kan genereren die allemaal een texture van een uniek blaadje van een boom bevatten. Als ik dat programma weer draai kan ik ervoor kiezen of ik dezelfde dump aan bpm'tjes wil of dat ik een compleet nieuwe set wil. Het programma zelf is niet groter als een basisbmp'tje + wat code. Speedtree is hierop gebaseerd. Daarnaast is er al een ontwikkelaar voor de Xbox geweest die een Xbox Arcade game (welke niet groter mag zijn dan 50mb) heeft uitgebracht (RoboBlitz) waar 800mb aan textures in zit, maar die worden nu algoritmisch gemaakt en het ziet er bijna net zo uit.

quote: RoboBlitz Site

As an example, the 73 full materials (about 200 maps: diffuse, specular, normal, etc.) of the first level, representing 80MB of DXT compressed content, are being generated in 4 seconds at load-time. The ProFX description file weighs only 280KB!

De textures verschillen iets, maar zien er even goed uit. Je bent dus niet bezig met datacompressie, maar bezig met een manier om zo goed mogelijk in de buurt te komen van het origineel. Het hele 100bit verhaal is dus niet toepasbaar.
Bij deze technologie wordt gebruik gemaakt van Fourier-transformatie en wavelets...dat is echt iets compleet anders dan compressie. (Zie http://www.profxengine.com/). Als je weet wat Fouriers en wavelets zijn is het al een stuk duidelijker

Laten we wel voorop stellen dat verhaallijnen etc allemaal nog gewoon gemaakt moeten worden door story-artists etc.

[ Voor 73% gewijzigd door armageddon_2k1 op 21-01-2007 16:14 ]

[Mithrandir]

Het grote probleem is niet dat je dingen simpel kunt generen door middel van code, maar dat je ontwerpers opeens op een compleet andere manier moeten aan werken. Ze moeten code gaan tikken om textures te genereren in plaats van dat ze gewoon een texture kunnen maken.

Een programmeur, die over het algemeen weinig kaas van ontwerpen heeft gegeten, kan zulke textures makkelijk genereren. Het grote probleem is dat je geen ontwerper vindt die zulke dingen kan programmeren.

En als je een ontwerper wél een texture laat maken en daarna wil je iets dat er op lijkt laten genereren, kom je wel bij het informatietheorie verhaal.

---

Infinity lijkt een leuk voorbeeld van generated content, maar er zijn maar een beperkt aantal mogelijkheden voor zo'n planeet natuurlijk. 'Levels', zoals je die over het algemeen in spelletjes tegenkomt, worden door veel meer parameters bepaald.

[armageddon_2k1]

Ik zou zeggen...lees eens wat over dat ProFX op die site. Hoe je het ook went of keert, ze zijn er toch in geslaagd om textures enorm te 'comprimeren' (ja, expres tussen aanhalingstekens). Wat betreft het feit dat men andere technieken aan moet leren....tja, dat heet ontwikkeling. Je kan niet eeuwig blijven hangen in een techniek die eigenlijk helemaal niet efficient is. Het kan namelijk echter ook zo zijn dat er specifieke middleware (zoals ProFX) voor ontworpen gaat worden. Net als met de Havoc engine eigenlijk, welke het physics-programmeerwerk grotendeels uit handen neemt. Let's face it....er zullen weinig programmeurs zijn die Finite-Element-Methods, Mechanica etc kunnen programmeren.

Daarnaast bevat Infinity niet echt levels, maar is het een vrije open wereld. En al zou het levels bevatten, ook dat moet mogelijk zijn, ware het niet dat je verdomd goede algoritmes moet verzinnen.

En als je een ontwerper wél een texture laat maken en daarna wil je iets dat er op lijkt laten genereren, kom je wel bij het informatietheorie verhaal.

Zou je dit wellicht verder uit willen leggen? En misschien kijken naar de Fourier Transforms en Wavelets? En kijk ook eens naar .kkrieger.

[ Voor 36% gewijzigd door armageddon_2k1 op 21-01-2007 16:55 ]

[Mithrandir]

armageddon_2k1 schreef op zondag 21 januari 2007 @ 16:47:
Ik zou zeggen...lees eens wat over dat ProFX op die site. Hoe je het ook went of keert, ze zijn er toch in geslaagd om textures enorm te 'comprimeren' (ja, expres tussen aanhalingstekens). Wat betreft het feit dat men andere technieken aan moet leren....tja, dat heet ontwikkeling. Je kan niet eeuwig blijven hangen in een techniek die eigenlijk helemaal niet efficient is. Het kan namelijk echter ook zo zijn dat er specifieke middleware (zoals ProFX) voor ontworpen gaat worden. Net als met de Havoc engine eigenlijk, welke het physics-programmeerwerk grotendeels uit handen neemt. Let's face it....er zullen weinig programmeurs zijn die Finite-Element-Methods, Mechanica etc kunnen programmeren.

Daarnaast bevat Infinity niet echt levels, maar is het een vrije open wereld. En al zou het levels bevatten, ook dat moet mogelijk zijn, ware het niet dat je verdomd goede algoritmes moet verzinnen.


[...]

Zou je dit wellicht verder uit willen leggen? En misschien kijken naar de Fourier Transforms en Wavelets? En kijk ook eens naar .kkrieger.

Ik weet dat een boel afbeeldingen omgezet kunnen worden naar een veel beperkter aantal paramteres (wat je kunt doen met bv fourier transforms). Wat graphics betreft wil ik je ook geen ongelijk geven.

Over de 'levels' (of een wereld in infinity een level is maakt niet zoveel uit) zijn we het geloof ik ook eens.
Bij infinity is het makkelijk om met een paar paramters aan te geven hoe een nieuwe wereld er uit zou moeten zien. Bij een willekeurig ander spel zal het veel moeilijker zijn om een 'level' of 'wereld' of 'omgeving' te discretiseren, omdat er simpelweg veel meer mogelijkheden zijn.

Ik wil je dus best gelijk geven dat voor sommige applicaties of onderdelen daarvan (de graphics) het heel goed mogelijk is, maar dit topic ging tot nu toe vooral over het genereren van speelwerelden. En daarin is het over het algemeen geen goed idee om dingen te laten genereren.

_{(Volgens mij zijn we het met elkaar eens)}

[Verwijderd]

armageddon_2k1 schreef op zondag 21 januari 2007 @ 09:48:
Ik noem Elite en Elite II...die zijn erg oud. Ik denk dat ik dus wel idee heb hoe oud het is
Elite komt echt uit het 86/88-tijdperk. Dat is nogal wat ouder.

Elite komt uit het 6502/Z80 tijdperk. 8 bits en vector graphics omdat de Acorn BBC en Electron de textures niet konden trekken.

[armageddon_2k1]

Verwijderd schreef op zondag 21 januari 2007 @ 20:05:
[...]
Elite komt uit het 6502/Z80 tijdperk. 8 bits en vector graphics omdat de Acorn BBC en Electron de textures niet konden trekken.

Later is het geport naar de 86/88 geloof ik door Chris Sawyer

[Bergen]

Mithrandir schreef op zondag 21 januari 2007 @ 13:59:
Ik snap niet dat jullie zo'n probleem maken van een implementatiedetail: de manier waarop je aan de 'willekeurige' getallen moet komen die je uit de seed genereert.

We maken er geen probleem van, ik gaf alleen aan dat de voorstelling van de 'seed' niet klopte, met een ietswat uitgebreide uitleg.

Voor iedereen die de implementatie wél interessant vindt: Perlin Noise is een voorbeeld van procedural texture generation.

Iets veel lastigers is om uit de getallen die je hebt gegenereerd een zinvolle wereld te maken. Je moet niet vergeten dat het helemaal niet moeilijk is om iets te genereren. Iets leuks wat spannend is en moeilijk maar niet onmogelijk met een interessant verhaal, dát is moeilijk te genereren. Daar zou je je druk om moeten maken.

Ik vraag me af in hoeverre dat mogelijk is. Kun je een computer leren wat een mens als 'spannend' ervaart? Verassende element kun je wel random inbouwen, maar dan is het echt random en heeft het mijns inziens niets meer met procedural generation te maken.