Reitinhakualgoritmien vertailu videopeliympäristöissä

Abstract

Reitinhaku on prosessi, jossa etsitään reittiä maaliin erilaisissa ympäristöissä. Tässsä tutkielmassa vertaillaan keskenään erilaisia reitinhakualgoritmeja, ja arvioidaan niiden käytettävyyttä videopeliympäristöissä. Algoritmien kompastuskiviä pyritään hahmottamaan ensisijaisesti tarkastelemalla algoritmien toimintaa avoimissa ympäristöissä. Tarkasteltavista algoritmeista A*-algoritmi osoittautuu selvästi muita algoritmeja ylivertaisemmaksi ja käytetymmäksi. Tutkielman havaintoja hyödyntämällä kyetään tekemään parempia ratkaisuja käytettävien reitinhakualgoritmien valinnassa. Jatkotutkimuksen kannalta todetaan A*-algoritmin optimoinnin tarjoavan hyvin mahdollisuuksia.

Pathfinding is the process of finding a route to a desired destination in different environments. This dissertation compares different pathfinding algorithms and evaluates their usability in video game environments. The stumbling blocks of algorithms are sought to be perceived primarily by looking at the operation of algorithms in open environments. Of the algorithms examined, the A * algorithm proves to be clearly superior and more used than other algorithms. By utilizing the findings of the dissertation, it is possible to make better decisions in the choice of pathfinding algorithms to be used. Considering further research, it is stated that the optimization of the A * algorithm offers great opportunities.