Proseduraalinen kenttägenerointi kuutiomarssittamalla
Remes, Anssi (2020)
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-2020120125502
https://urn.fi/URN:NBN:fi:amk-2020120125502
Tiivistelmä
Kuutiomarssitusalgoritmi on keino, jolla voidaan muodostaa tarkkoja 3D-malleja joukoista kolmiulotteisen avaruuden pisteitä. Alkuperäisessä käyttötarkoituksessa pisteet voivat esittää esimerkiksi magneettikuvauksen mittaustuloksia. Algoritmi toimii hyvin nopeasti, sillä sen toiminta perustuu hakutaulukkoon, jonka mukaisesti jokaiselle pisteiden muodostamalle kuutiolle asetetaan sen tapausta vastaavat polygonit. Kun algoritmi on marssinut lävitse jokaisen datan kuution, muodostuu polygoneista valmis mitattavaa kappaletta esittävä malli.
Tietokonepeleissä sisältöä generoidaan usein automatisoidusti niin, että peleissä voi olla lähes rajaton määrä tavaroita, hahmoja tai kenttiä. Tällaista proseduraalisesti generoitua sisältöä ei tarvitse luoda käsin, eikä sitä tarvitse tallentaa, sillä se luodaan pelin aikana parametreistä ja moduuleista. Kenttägeneroinnissa ohjelmallinen sisällön luominen mahdollistaa usein kenttien muokkaamisen niiden modulaarisen rakenteen vuoksi. Synnyttämällä kenttien geometria kuutiomarssittamalla voidaan luoda tällaisia kolmiulotteisia muokattavia pelikenttiä nopeasti. Algoritmin käyttäminen mahdollistaa myös monimutkaisen kenttägenerointilogiikan lisäämisen, sillä se tarvitsee toimiakseen ainoastaan taulukon vokseleita, joita voidaan muokata monella yksinkertaisella tavalla.
Tämän opinnäytetyön tavoite on esittää käytännön sovellutus kuutiomarssitusalgoritmille tietokonepelien kenttägeneroinnissa sekä pohtia tekniikan rajoituksia ja potentiaalia. Tässä opinnäytetyössä tuotettiin pelidemo Unity-pelimoottorissa, jossa kentän lohkojen satunnaisella Perlin-kohinalla täytetyistä vokselitaulukoista luodaan kuutiomarssittamalla reaaliaikaisesti muokattavia pelikenttiä. Työ esittelee tekniikan toimintaa ja monta eri tapaa, joilla algoritmin käyttäminen voi palvella kenttägeneroinnin tarpeita, kuten luolia sisältävien vuorien luomisen yhdistämällä kaksi- ja kolmiulotteista Perlin-kohinaa. Lisäksi demossa esitellään pelattavuutta, jossa pelaaja voi muokata generoitua kenttää hyvinkin yksityiskohtaisesti. Kuutiomarssituksen toimiessa todella nopeasti kentän muokatut vokselitaulukot voidaan kuutiomarssittaa uudelleen pelinaikaisesti ja muokkaukset näkyvät kentässä lähes välittömästi.
Demon avulla havainnollistetaan, miten kenttägeneroinnin parametrien muuttaminen vaikuttaa algoritmin tekemään lopputulokseen sekä, miten generoinnissa kentän osia voidaan lisätä, poistaa tai yhdistellä. Kentän vokselitaulukkojen ollessa yksinkertaisesti muokattavissa sen vokselien arvoja voidaan muokata samalla tavoin kuin pikseleitä kuvankäsittelyssä. Tässä työssä käytetyt esimerkit eivät täytä minkään varsinaisen tietokonepelin kenttägeneroinnin tarpeita, vaan esittävät millä tavoin kehittäjän on mahdollista muokata kuutiomarssitettavaa kenttää. Mahdollisuuksien ja jatkokehitysideoiden lisäksi työssä onnistuttiin löytämään lukuisia vikoja algoritmin käyttämisessä peleissä. Kuutiomarssitusta käytettäessä pelin kenttägenerointiin on tärkeätä huomioida kuinka nopeasti kentän koon kasvattaminen nostaa tarvittavaa laskentatehoa ja muistin määrää. Algoritmin toimintaa voidaan optimoida useilla keinoilla, mutta laskenta-ajan säästäminen voi kasvattaa vaaditun muistin määrää ja päinvastoin. Pelintekijän on pystyttävä sovittamaan algoritmin toiminta omaan peliinsä tavalla, joka palvelee kehitettävän pelin visiota sen laitevaatimusten pysyessä hillittynä. Cube marching algorithm allows turning series of points in three-dimensional space into accurate 3D-models. In its original purpose, the points could be, for example, from the results of a magnet resonance imaging. The algorithm works rapidly as it uses a lookup table to place according polygons into each cube formed by the points in the data. After the algorithm has marched through every cube in the data, the polygons form a complete model of the scanned object.
Content in video games is often automatically created, so that there are nearly infinite amounts of items, characters or levels. This type of procedurally generated content is not made by hand and it does not need to be saved as it is generated in runtime from modules according to set parameters. Using procedural generation in levels often allows the editing of its modules. Generating these kinds of editable levels quickly is possible by using cube marching. Using the algorithm also enables implementing complex level generation logic because it requires only a table of voxels which are trivial to edit in multiple different ways.
This thesis contains the details of developing a game demo, in which cube marching is used to form levels from Perlin-noise and that can be edited in real-time. Demo has been developed in Unity game engine and it explores the possibilities and technical requirements of the algorithm. This thesis demonstrates the techniques available to the developers to use in their cube marching based level generation, like the possibility of creating mountains and caves by combining both two- and three-dimensional Perlin noise. Additionally, the demo presents gameplay in which the player can edit the level in high detail. Because the cube marching algorithm runs so quickly the edits done to the level’s voxel tables can be displayed near instantly as a change in the terrain’s shape.
The game demo is used to showcase how its level generation’s parameters affect its outcome and how it is possible to add, remove or combine parts of the level. Because editing the level’s voxel tables is trivial the voxels can be edited similarly to pixels in image processing. The examples in this thesis were not made for any video game in mind, but to demonstrate the ways of editing the cube marched level. The thesis succeeded to find several faults in the technique in addition to its possibilities when it is used in video games. When using cube marching in level generation it is important to note that increasing the size of the levels raises the amount of required processing power and memory rapidly. The algorithm can be optimized in a plethora of ways, but by saving processing time the amount of required memory increases and vice versa. The game developer must implement the algorithm in such a way that it serves the vision for their game while its hardware requirements stay reasonable.
Tietokonepeleissä sisältöä generoidaan usein automatisoidusti niin, että peleissä voi olla lähes rajaton määrä tavaroita, hahmoja tai kenttiä. Tällaista proseduraalisesti generoitua sisältöä ei tarvitse luoda käsin, eikä sitä tarvitse tallentaa, sillä se luodaan pelin aikana parametreistä ja moduuleista. Kenttägeneroinnissa ohjelmallinen sisällön luominen mahdollistaa usein kenttien muokkaamisen niiden modulaarisen rakenteen vuoksi. Synnyttämällä kenttien geometria kuutiomarssittamalla voidaan luoda tällaisia kolmiulotteisia muokattavia pelikenttiä nopeasti. Algoritmin käyttäminen mahdollistaa myös monimutkaisen kenttägenerointilogiikan lisäämisen, sillä se tarvitsee toimiakseen ainoastaan taulukon vokseleita, joita voidaan muokata monella yksinkertaisella tavalla.
Tämän opinnäytetyön tavoite on esittää käytännön sovellutus kuutiomarssitusalgoritmille tietokonepelien kenttägeneroinnissa sekä pohtia tekniikan rajoituksia ja potentiaalia. Tässä opinnäytetyössä tuotettiin pelidemo Unity-pelimoottorissa, jossa kentän lohkojen satunnaisella Perlin-kohinalla täytetyistä vokselitaulukoista luodaan kuutiomarssittamalla reaaliaikaisesti muokattavia pelikenttiä. Työ esittelee tekniikan toimintaa ja monta eri tapaa, joilla algoritmin käyttäminen voi palvella kenttägeneroinnin tarpeita, kuten luolia sisältävien vuorien luomisen yhdistämällä kaksi- ja kolmiulotteista Perlin-kohinaa. Lisäksi demossa esitellään pelattavuutta, jossa pelaaja voi muokata generoitua kenttää hyvinkin yksityiskohtaisesti. Kuutiomarssituksen toimiessa todella nopeasti kentän muokatut vokselitaulukot voidaan kuutiomarssittaa uudelleen pelinaikaisesti ja muokkaukset näkyvät kentässä lähes välittömästi.
Demon avulla havainnollistetaan, miten kenttägeneroinnin parametrien muuttaminen vaikuttaa algoritmin tekemään lopputulokseen sekä, miten generoinnissa kentän osia voidaan lisätä, poistaa tai yhdistellä. Kentän vokselitaulukkojen ollessa yksinkertaisesti muokattavissa sen vokselien arvoja voidaan muokata samalla tavoin kuin pikseleitä kuvankäsittelyssä. Tässä työssä käytetyt esimerkit eivät täytä minkään varsinaisen tietokonepelin kenttägeneroinnin tarpeita, vaan esittävät millä tavoin kehittäjän on mahdollista muokata kuutiomarssitettavaa kenttää. Mahdollisuuksien ja jatkokehitysideoiden lisäksi työssä onnistuttiin löytämään lukuisia vikoja algoritmin käyttämisessä peleissä. Kuutiomarssitusta käytettäessä pelin kenttägenerointiin on tärkeätä huomioida kuinka nopeasti kentän koon kasvattaminen nostaa tarvittavaa laskentatehoa ja muistin määrää. Algoritmin toimintaa voidaan optimoida useilla keinoilla, mutta laskenta-ajan säästäminen voi kasvattaa vaaditun muistin määrää ja päinvastoin. Pelintekijän on pystyttävä sovittamaan algoritmin toiminta omaan peliinsä tavalla, joka palvelee kehitettävän pelin visiota sen laitevaatimusten pysyessä hillittynä.
Content in video games is often automatically created, so that there are nearly infinite amounts of items, characters or levels. This type of procedurally generated content is not made by hand and it does not need to be saved as it is generated in runtime from modules according to set parameters. Using procedural generation in levels often allows the editing of its modules. Generating these kinds of editable levels quickly is possible by using cube marching. Using the algorithm also enables implementing complex level generation logic because it requires only a table of voxels which are trivial to edit in multiple different ways.
This thesis contains the details of developing a game demo, in which cube marching is used to form levels from Perlin-noise and that can be edited in real-time. Demo has been developed in Unity game engine and it explores the possibilities and technical requirements of the algorithm. This thesis demonstrates the techniques available to the developers to use in their cube marching based level generation, like the possibility of creating mountains and caves by combining both two- and three-dimensional Perlin noise. Additionally, the demo presents gameplay in which the player can edit the level in high detail. Because the cube marching algorithm runs so quickly the edits done to the level’s voxel tables can be displayed near instantly as a change in the terrain’s shape.
The game demo is used to showcase how its level generation’s parameters affect its outcome and how it is possible to add, remove or combine parts of the level. Because editing the level’s voxel tables is trivial the voxels can be edited similarly to pixels in image processing. The examples in this thesis were not made for any video game in mind, but to demonstrate the ways of editing the cube marched level. The thesis succeeded to find several faults in the technique in addition to its possibilities when it is used in video games. When using cube marching in level generation it is important to note that increasing the size of the levels raises the amount of required processing power and memory rapidly. The algorithm can be optimized in a plethora of ways, but by saving processing time the amount of required memory increases and vice versa. The game developer must implement the algorithm in such a way that it serves the vision for their game while its hardware requirements stay reasonable.