Miten A*-algoritmia voidaan hyödyntää peleissä

Abstract

Tässä tutkielmassa tarkastellaan, miten A*-algoritmi ja siitä johdetut HPA*- ja KM-A*-algoritmit toimivat ja miten niitä voidaan hyödyntään pelikartoissa. A*-algoritmi on hyvin käytetty polunetsinnässä, mutta sen vaatimat resurssit tekevät siitä hitaan peleille. HPA*- ja KM-A* -algoritmit pyrkivät nopeuttamaan A*:n toimintaa tinkimällä reitin tarkkuudesta. Kummatkin nopeuttavat huomattavasti A*:n toimintaa, mutta tuovat myös ongelmia.

In this study we look at A*-algorithm and its modifications HPA*- and KM-A*-algorithm and how they work on game maps. A*-algorithm is still very widely used in pathfinding but its resource heavy pathfinding makes it slow to use in games. HPA* and KM-A*-algorithm try to speed the pathfinding process by cutting from optimality of the path. Both of these algorithms offer a great speed increase for A* but they also present their own problems with the speed enhancing techniques.