Reitinetsintä kolmiulotteisissa peliympäristöissä

Abstract

Reitinetsintä on yleinen haaste, joka pitää ratkaista monenlaisissa videopeleissä. Sen ratkaiseminen on usein perusvaatimuksena pelihahmojen toiminnalle, sillä hahmojen täytyy kyetä suunnistamaan luontevasti pelimaailman läpi. Tämän tutkielman tavoitteena on kartoittaa kolmiulotteisten peliympäristöjen reitinetsintään soveltuvia tekniikoita sekä arvioida niiden ongelmia ja mahdollisuuksia. Tutkielmassa perehdytään ensin yleisimpiin peleissä käytettyihin reitinetsintäalgoritmeihin ja sitten tapoihin, joilla näitä algoritmeja voidaan soveltaa peliympäristöihin. Yleisiksi reitinetsintäalgoritmeiksi osoittautuvat A*-algoritmi, geneettiset algoritmit ja muurahaisyhdyskuntaoptimointi. A*-algoritmi on melko yksinkertainen ja tehokas reitinetsintäalgoritmi, mutta sen toimintakyky heikkenee, jos ympäristössä tapahtuu usein muutoksia. Geneettiset algoritmit ja muurahaisyhdyskuntaoptimointi sen sijaan soveltuvat hyvin myös muuttuviin ympäristöihin. Havaitaan, että A*-algoritmista on tehty erilaisia muunnoksia, jotka tehostavat algoritmin tiettyjä osia, mutta heikentävät toisia. Tällaisen muunnoksen käytöstä voi olla hyötyä, jos tehostetut ominaisuudet ovat pelille tärkeitä. Heikentyneet ominaisuudet täytyy kuitenkin ottaa myös huomioon ja arvioida, miten muunnos vaikuttaisi kokonaisuutena peliin. Jotta reitinetsintäalgoritmeja voidaan käyttää pelissä, peliympäristön pohjalta täytyy ensin muodostaa graafi. Tutkielmassa havaitaan, että tämän graafin toteutustavan valinta on tärkeä reitinetsintäjärjestelmän ominaisuuksiin vaikuttava tekijä. Kirjallisuudesta löydetään kolme yleisesti käytettyä graafimallia, joista jokainen soveltuu paremmin tietynlaisiin käyttökohteisiin ja huonommin toisiin. Näistä kolmesta mallista soveltuvimmaksi kolmiulotteisiin ympäristöihin osoittautuu navigaatioverkko. Navigaatioverkot mallintavat pintoja, joilla pelihahmot voivat kävellä, ja ne mahdollistavat kahta muuta tarkasteltua graafimallia tarkemman ja joustavamman reitinetsinnän. Verkon voi luoda pitkälti automaattisesti peliympäristön pohjalta, mikä säästää aikaa, mutta manuaalinen muokkaaminen on myös mahdollista. Näin pelisuunnittelijat voivat ensin luoda karkean navigaatioverkon automaattisesti ja sitten hienosäätää sitä pelin tarpeisiin. Tutkielman yhteydessä toteutetaan myös yksinkertainen navigaatioverkkoja hyödyntävä reitinetsintäjärjestelmä, joka havainnollistaa navigaatioverkkojen toimintaa. Järjestelmälle voidaan antaa mielivaltainen kolmiulotteinen malli navigaatioverkoksi, joten reitinetsintää voidaan tarkastella monenlaisissa tilanteissa. Järjestelmää voitaisiin myös helposti laajentaa oikeaksi peliksi, sillä se toteutetaan samoilla työkaluilla, joilla monet pelit on tehty.