Reitinhakualgoritmien käyttö ja soveltaminen videopelituotannossa

Abstract

Reitinhaku on usean vuosikymmenen ollut laajasti käsitelty ongelma muun muassa karttasovelluksissa, robotiikassa ja videopeleissä. Ongelmassa keskitytään siihen, miten paikasta A päästään paikkaan B mahdollisimman nopeasti. Ratkaisuna tähän ongelmaan on kehitetty erilaisia reitinhakualgoritmeja, jotka voivat erittäin nopeasti löytää lyhimmän tai ainakin melkein lyhimmän reitin. Eri algoritmeilla on kuitenkin hyvin erilaiset lähestymistavat ongelmaan. Tämän takia oikean algoritmin valitseminen kyseessä olevaan sovelluskohteeseen on kriittistä reitinhaun tehokkuuden kannalta. Tehokas reitinhaku on keskeinen tekijä hyvälle käyttäjäkokemukselle karttasovelluksissa ja videopeleissä. Robotiikassa ja autonomisissa järjestelmissä tehokkaat reitinhakualgoritmit parantavat järjestelmien toiminnallisuutta ja koettua älykkyyttä. Tutkielmassa käsitellään viimeisen viiden vuoden tutkimuskirjallisuuden kannalta olennaisia algoritmeja, ja miten näitä sovelletaan videopeleihin. Voidaan havaita, että uudemmat algoritmit voivat oikein toteutettuina olla huomattavasti tehokkaampia kuin vanhemmat vaihtoehdot. Voidaan myös havaita, että oikean mallintamistekniikan ja heuristiikan valitseminen on ratkaisevaa sovelluskohteen suorituskyvyn ja toiminnallisuuden kannalta.