Tekoälysovellus A* -reitinhakualgoritmilla

Abstract

Tekoäly on yksi keskeisimmistä konsepteista ohjelmoinnissa. Päätöksentekokyky ja tilannetajuinen reagointi syventävät kokemusta peleissä ja tuovat käyttömukavuutta hyötyohjelmissa.

Opinnäytetyön aiheena oli suunnitella tekoäly peliprojektiin, missä käyttäjä etenee ylhäältä päin kuvatussa ympäristössä vältellen tietokoneen hallitsemia hahmoja. Tekoälyn ohjaamien yksiköiden tuli pystyä liikkumaan ympäristössä, sekä reagoida muuttuvaan tilanteeseen kentällä. Tämän lisäksi tekoälyn tuli olla laajennettavissa.

Tekoälyä suunnitellessa päädyttiin rakennevaihtoehdoista hierarkiseen tilakoneeseen. Tämä helpottaa laajentamista osakokonaisuuksien ollessa mahdollisimman tehokkaasti eristettyjä toisistaan.

Liikkumisessa tarvittiin reitinhakualgoritmia esteiden kiertämiseksi. Toteutus tapahtui Dijkstran algoritmin tuloksia painottavalla sovelluksella, joka yleisesti tunnetaan nimellä A*.

Pelin tarkoituksiin suunnitellussa tekoälyssä reitinhakualgoritmi osoittautui haastavimmaksi osaksi vieden suurimman osan kehitystyöhön kulutetusta ajasta. Lopputuloksena syntynyttä tekoälymoduulia on vähäisillä muutoksilla mahdollista hyödyntää navigointisovelluksessa reitinhakumoduulina.

Artificial intelligence is one of the most vital concepts of programming. The ability to make decisions and situational reacting can bring depth to the gaming experience and increase usability in software.

The subject of this thesis was to design and create an artifical intelligence to be used in a game where the player moves around in an enviroment, viewed from the top down, dodging computer controlled characters. The A.I. must be able to move in the same enviroment and react to the situation in the playing area. On top of this the A.I. should be readily expendable in case of improvements.

While designing the A.I., a finite state machine was chosen as the end result. This architecture emphasizes the modularity, making it much easier to alter any aspect of said A.I. individually.

For mobility a path-finding algorithm was needed. This was done with A*-algorithm, an expansion of a well-known Dijkstra's algorithm that prioritizes results to reduce calculation time.

The implementation of the path-finding algorithm ended as the most challenging part of this A.I., taking up most of the time spent in development by a great margin. The A.I. created could be potentially re-purposed to serve any navigational software as well.