Procedural Generation of Infinite Formations

Thumbnail Image

Files

master_Hirvonen_Jussi_2021.pdf (3.26 MB)

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.

Authors

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

Permanent link to this item

https://urn.fi/URN:NBN:fi:aalto-202110249776

Collections

[dipl] Perustieteiden korkeakoulu / SCI