Procedural Generation of Infinite Formations

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Date
2021-10-18
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
33 + 4
Series
Abstract
In this master's thesis, we explore how an infinite formation can be achieved in a computer program. We call an infinite formation a data structure that, when expressed in a coordinate system, extends indefinitely in at least one direction. An infinite formation, as the name suggests, comprises an infinite amount of data. Because we do not have infinite storage space, infinite formations have to be procedurally generated. They cannot be fully generated, however, as it is not possible to finish generating a structure that has no end. By dividing an infinite formation into parts that are finite in size, the parts can be generated and utilized. Therefore, in order to use an infinite formation, it has to be represented by an algorithm that can procedurally generate the formation in parts. We examine three ways of procedurally representing infinite formations: fractals, hash functions and noise functions. To evaluate the suitability of these methods, we compare their products with a theoretical, perfect infinite formation. An ideal infinite formation is deterministic, consists of unique parts, and all its parts are accessible in constant time. Our conclusion is that of the methods considered, noise functions produce infinite formations with the best qualities.

Tässä diplomityössä tutkitaan, miten loputtomia muodostelmia voidaan käyttää tietokoneohjelmissa. Loputtomalla muodostelmalla tarkoitetaan tässä työssä tietorakennetta, joka koordinaatistoon sijoitettuna ulottuu loputtomiin ainakin yhteen suuntaan. Loputtomat muodostelmat koostuvat äärettömästä määrästä tietoa. Koska tietoa ei ole mahdollista tallentaa tietokoneelle rajattomasti, loputtomat muodostelmat on luotava tyhjästä, kun niitä halutaan käyttää. Tämä saavutetaan tuottamalla loputtomat muodostelmat algoritmeilla. Loputon rakenne ei kuitenkaan koskaan ole valmis, vaikka siitä valmistettaisiin kuinka paljon. Tästä syystä loputtomat muodostelmat on jaettava rajallisen kokoisiin osiin, jotta nämä osat pystytään tekemään valmiiksi. Loputtomia muodostelmia voidaan siis käyttää tuottamalla ne algoritmeilla, jotka tuottavat muodostelmat osissa. Tässä työssä tarkastellaan loputtomien muodostelmien tuottamista fraktaaleilla, hajautusalgoritmeilla ja kohina-algoritmeilla. Työssä todetaan, että ihanteellinen loputon muodostelma on sellainen, jonka kaikki osat ovat ennalta määrättyjä, ainutlaatuisia ja tuotettavissa yhtä nopeasti. Menetelmiä vertaamalla havaitaan, että tarkastelluista menetelmistä kohina-algoritmit tuottavat ominaisuuksiltaan parhaita loputtomia muodostelmia.
Description
Supervisor
Uitto, Jara
Thesis advisor
Uitto, Jara
Keywords
endless, infinite, data structures, algorithms, formations
Other note
Citation