Proseduraalinen maaston generointi geneettisillä algoritmeilla Maanmittauslaitoksen avointa tietoaineistoa hyväksi käyttäen

Abstract

Videopelien kehityksestä ja niiden julkaisusta on tullut entistä saavutettavampia itsenäisille tekijöille erilaisten verkossa toimivien markkina-alustojen myötä. Ihmistyövoiman puute voi kuitenkin olla rajoittava tekijä esimerkiksi pelimaailmojen luomisen kanssa, sillä maastojen ja tilojen tekeminen käsin on usein sekä hidasta että taitoa vaativaa. Vaihtoehtona maastojen tuottamiselle on jo pitkän aikaa ollut myös joitakin proseduraalisia menetelmiä, joissa maasto generoidaan tietokoneella erilaisten algoritmien avulla. Näistä yleisimmin käytössä ovat fraktaaliset menetelmät, joihin perustuvia toteutuksia on nähty myös monissa julkaistuissa peleissä. Fraktaalit ovat hyvin yksinkertaisia toteuttaa ja nopeita käyttää, mutta niillä on myös heikkoutensa, kuten generoinnin lopputuloksen paikallisten yksityiskohtien säätämisen hankaluus. Tämän työn tavoitteena olikin etsiä proseduraaliselle maaston generoinnille vaihtoehtoja, jotka vastaisivat fraktaalisten generointimenetelmien ongelmiin, kuten niiden itsesimilaarisuudesta johtuvaan tunnistettavuuteen. Työssä ratkaisua etsittiin erityisesti todellisesta maailmasta kerättyyn paikkatietoon perustuvista menetelmistä yhdistellen tätä geneettisiin algoritmeihin ja agenttipohjaiseen järjestelmään. Paikkatiedoksi valikoituivat Maanmittauslaitoksen avoimesta tietoaineistosta saatavilla olevat korkeus- ja maastomallit, joista koostetuilla maastokohteita kuvaavalla aineistolla agenttien toimintaa ohjataan. Tämän lisäksi korkeusaineistosta koostetut kartat toimivat pohjana geneettiselle algoritmille, joka pyrkii kokoamaan aineiston kartoista uusia maastonmuotoja lähtömaastoa mukaillen. Kukin järjestelmän agenteista on sidottu maastoaineistossa esiintyvään maastokohteeseen ja pyrkii jäljittelemään sen esiintyvyyttä alkuperäisessä maastossa koon ja esiintymiskorkeuden suhteen. Nämä agentit suorittavat kulkuja generoitavaan maastoon ja asettelevat geenejä kartalle, jotka sitten sulauttavat käsittelemiään korkeusnäytteitä niille määrättyihin kohtiin tuotettavaa karttaa. Lopuksi työssä tarkasteltiin korkeusjakaumia ja niiden eroja lähtöaineistona käytetyn ja tuotetun maaston välillä. Tämän tarkoituksena oli selvittää toteutetun geneettisen algoritmin kuntoisuutta sekä agenttien ohjauksen sopivuutta tarkoitukseensa. Tarkastellun perusteella toteutettu järjestelmä on kykenevä tuottamaan lähtömaastoa muistuttavia ominaisuuksia, mutta sen toiminnassa on myös selkeitä puutteita, joiden takia lopputuloksen laatu vaihtelee. Näistä esimerkiksi maaston lähtökorkeuden ja vesistöjen pinnan valinnan satunnaisuus aiheutti suuria vaihteluita järjestelmän lopputuotoksessa. Toteutuksessa havaittujen ongelmien korjaamiseksi tarjottiin myös lopuksi ratkaisuja, kuten lähtökorkeuden valintaa tilannekohtaisemmin lähtömaaston ominaisuuksiin perustuen ja järjestelmän ohjaamisen laajentamista myös muihin ominaisuuksiin kuin korkeuden ja kohteiden koon hajontaan.

Developing and publishing video games has become increasingly available for independent developers due to different online marketing platforms. Lack of human work force can, however, be limiting factor for elements such as game world and terrain creation. Handcrafting worlds will often require significant amount of time and knowledge to be viable. Procedural methods of generating terrain with computers using algorithms have been an alternative already in the past. One of the more widely used being fractals which have been utilized in several published video games. Fractal methods are easy to implement and fast to calculate, however, they do have weaknesses such as lack of control related to local features of the generation result. The aim of this work is to find alternative procedural solutions that would offer solutions to problems prevalent in use of fractal methods such as recognizability caused by the self-similarity of generated terrains. Implementation in this work sought solutions from geographical information systems -based methods combining them with genetic algorithms and intelligent agents. Implementation uses height and terrain models from Finnish National Land Survey open database to produce data representing terrain features, which is then used to control the behavior of terrain agent system. In addition, spliced height samples from the height model are used as basis for genetic algorithm to combine into new terrain imitating features of the source terrain. Each of the agents in the system represents a terrain feature from the terrain model and attempts to mimic height and size occurrence of connected feature in their output. The agents execute random travels across terrain to be generated placing genes along their route, which can then blend height samples they have processed to the positions appointed for them. The last part of this work concentrates on examining the height distributions of generated terrain compared to the source material. The purpose of this was to determine the fitness of implemented genetic algorithm as well as the suitability of agent directing for its task. Based on examination, implemented system is capable of creating features mimicking the source terrain. However, it also lacks in certain areas, causing the output of the system to vary. Problem areas included for example selection of both the level of terrain starting point as well as the surface level of generated bodies of water, both of which can cause lot of variation in the resulting terrain output. Some possible solutions were discussed related to fixing problems discovered. These included controlling the terrain level starting point in more situational way based on features of specific terrain and implementing more precise system control utilizing other properties of source terrain than mere height and size distributions of terrain and features.