A new offline path search algorithm for computer games that considers damage as a feasibility criterion

Date

2008

Author

Bayılı, Serhat

Metadata

Show full item record

Pathfinding algorithms used in today’s computer games consider path length or a similar criterion as the only measure of optimality. However, these games usually involve opposing parties, whose agents can inflict damage on those of the others’. Therefore, the shortest path in such games may not always be the safest one. Consequently, a new suboptimal offline path search algorithm that takes the threat sources into consideration was developed, based on the A* algorithm. Given an upper bound value as the tolerable amount of damage for an agent, this algorithm searches for the shortest path from a starting location to a destination that would cause the agent suffer no more damage than the specified maximum. Due to its mentioned behavior, the algorithm is called Limited-Damage A* (LDA*). Performance of LDA* was tested in randomly-generated and hand-crafted fully-observable maze-like square environments with 8-way grid-abstractions against Multiobjective A* (MOA*), which is a complete and optimal algorithm. It was found to perform much faster than MOA* with allowable sub-optimality in path length.

Subject Keywords

Computer enginnering.

URI

http://etd.lib.metu.edu.tr/upload/2/12609725/index.pdf
https://hdl.handle.net/11511/17723

Collections

Graduate School of Natural and Applied Sciences, Theses