Polunetsintä pelisovelluksessa
Leppäkoski, Alex (2021)
Leppäkoski, Alex
2021
All rights reserved. This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-202105057214
https://urn.fi/URN:NBN:fi:amk-202105057214
Tiivistelmä
Insinöörityön tarkoituksena oli toteuttaa pelisovellukseen polunetsintä, jotta tietokoneen ohjaamat pelihahmot pystyvät liikkumaan pelikartalla sijainnista toiseen esteiden lomassa. Pelisovellus luotiin käyttämällä C++-ohjelmointikieltä ja OpenGL-kirjastoa. Tavoitteena oli tehdä polunetsinnästä suorituskyvyltään tehokas ratkaisu pelisovellukselle siten, että peli ei hidastu näkyvästi sen suorituksen takia.
Insinöörityön toteutukseen käytettiin A*-algoritmia, joka on pelisovelluksissa yksi käytetyimmistä polunetsintäalgoritmeista. Heuristiikaksi valittiin Manhattanin etäisyys, jota polunetsintäalgoritmi käyttää arvioimaan etäisyyttä kohteeseen. A*-algoritmi määrittelee kuljettavan reitin muun muassa heuristiikan avulla.
Pelikartta pilkottiin pieniin itsenäisiin kokonaisuuksiin polunetsinnän nopeuttamiseksi. Kun käsiteltävä alue on pienempi, suoritusnopeuden enimmäiskesto lyhenee. Suoritusnopeutta pystytään parantamaan entisestään hierarkkisen tietorakenteen avulla.
Insinöörityön lopputuloksena saatiin toteutettua polunetsintä pelisovellukselle. Polunetsintä ohjelmoitiin omaan moduuliinsa. Selvisi, että polunetsintäominaisuus vaatii lisää optimointia, jotta se olisi julkaisuvalmis.
Insinöörityö edisti pelisovelluksen tavoitteita. Insinöörityö mahdollisti pelisovelluksen pelaamista sen nykyisessä tilassa ja mahdollistaa myös tulevia ominaisuuksia, joissa vaaditaan polunetsintää. Insinöörityöraportin avulla voi pohtia polunetsintään tarvittavia ratkaisuja myös muihin pelisovelluksiin ja helpottaa oikeiden ratkaisujen löytämistä.
Insinöörityön toteutukseen käytettiin A*-algoritmia, joka on pelisovelluksissa yksi käytetyimmistä polunetsintäalgoritmeista. Heuristiikaksi valittiin Manhattanin etäisyys, jota polunetsintäalgoritmi käyttää arvioimaan etäisyyttä kohteeseen. A*-algoritmi määrittelee kuljettavan reitin muun muassa heuristiikan avulla.
Pelikartta pilkottiin pieniin itsenäisiin kokonaisuuksiin polunetsinnän nopeuttamiseksi. Kun käsiteltävä alue on pienempi, suoritusnopeuden enimmäiskesto lyhenee. Suoritusnopeutta pystytään parantamaan entisestään hierarkkisen tietorakenteen avulla.
Insinöörityön lopputuloksena saatiin toteutettua polunetsintä pelisovellukselle. Polunetsintä ohjelmoitiin omaan moduuliinsa. Selvisi, että polunetsintäominaisuus vaatii lisää optimointia, jotta se olisi julkaisuvalmis.
Insinöörityö edisti pelisovelluksen tavoitteita. Insinöörityö mahdollisti pelisovelluksen pelaamista sen nykyisessä tilassa ja mahdollistaa myös tulevia ominaisuuksia, joissa vaaditaan polunetsintää. Insinöörityöraportin avulla voi pohtia polunetsintään tarvittavia ratkaisuja myös muihin pelisovelluksiin ja helpottaa oikeiden ratkaisujen löytämistä.