Flow Field -algoritmin soveltaminen Supreme Commander 2:n polunetsinnässä

Abstract

Polunetsintäalgoritmien tärkeä tehtävä on ohjata pelihahmoja pelikentällä paikasta A paikkaan B. Polunetsintäalgoritmin rakentaminen on haastavaa, koska sen tahdotaan toimivan nopeasti, tuottavan lyhyitä polkuja ja käyttävän muistia sekä laskutoimituksia mahdollisimman vähän. Reaaliaikastrategiapeleissä erityinen ongelma polunetsintäalgoritmeille on, että niiden täytyy pystyä täyttämään aiemmat kriteerit ja kyetä samanaikaisesti käsittelemään useampia eri yksiköitä eri maastotyypeissä. Erilaisia kehitettyjä polunetsintäalgoritmeja ovat leveyshakua, syvyyshaku, Dijkstran algoritmi, A*-algoritmi ja Flow Field -algoritmi. A*- ja Flow Field -algoritmi erottuvat joukosta, koska ne kykenevät heuristiikkaan, joka antaa niille suuntavaiston polunetsinnän määränpäästä. Heuristiikan avulla polunetsintäalgoritmi käyttää vähemmän tietokoneresursseja ja samalla määrittää polun nopeammin. Näin ollen reaaliaikastrategiapeleissä yleisesti käytettyjä algoritme-ja ovat A* ja Flow Field. Tässä tutkielmassa pohditaan näiden molempien algoritmien eroja reaaliaikastrategiapelien polunetsintäalgoritmeina ja sitä, kuinka Supreme Commander 2:ssa sovelletaan Flow Fieldia polunetsinnän tehostamiseksi. Molemmat polunetsintäalgoritmit ovat hyvin samanlaisia, mutta ne eroavat polunetsintäpyyntöjen käsittelyssä. A* tuottaa polunetsinnässään vain yhden polun määränpäähän ja kykenee käsittelemään vain yhden polunetsintäpyynnön kerrallaan. Flow Field -algoritmi tuottaa useampia polkuja määränpäähän ja pystyy kerralla käsittelemään useampia polunetsintäpyyntöjä. Flow Fieldissa on myös hyödyllistä, että useampien polkujen avulla voidaan vähentää konfliktien syntymistä, kun monia yksiköitä liikkuu samanaikaisesti pelikentällä. Supreme Commander 2:ssa Flow Field -algoritmia sovelletaan A*-algoritmin ja erilaisien menetelmien, kuten sektorien, portaalien ja näkölinjan, kanssa tehokkaan polunetsintäalgoritmin saavuttamiseksi. Supreme Commander 2:n sovellettu polunetsintäalgoritmi etsii laadukkaampia polkuja nopeammin ja kuluttaa vähemmän muistia ja laskutoimituksia kuin pelkkä Flow Field -algoritmi.