Limited-Damage A*: A path search algorithm that considers damage as a feasibility criterion

Date

2011-05-01

Author

Bayılı, Serhat
Polat, Faruk

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

183
views

0
downloads

Pathfinding algorithms used in todays computer games consider the 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 based on the A* algorithm was developed, which takes the threat zones in the game map into consideration. Given an upper limit as the tolerable amount of damage for an agent, this algorithm searches for the shortest path from a starting location to a destination, where the agent may suffer damage less than or equal to the specified limit. Due to its behavior, the algorithm is called Limited-Damage A* (LDA*). Performance of LDA* was tested in randomly-generated maze-like grid-based environments of varying sizes, and in hand-crafted fully-observable environments, in which 8-way movement is utilized. Results obtained from LDA* are compared with those obtained from Multiobjective A* (MOA*), which is a complete and optimal algorithm that yields exact (best) solutions for every case. LDA* was found to perform much faster than MOA*, yielding acceptable sub-optimality in path length.

Subject Keywords

Agent search, Path search in virtual environments, Offline path planning, Heuristic search, Multiobjective search, Multiobjective search

URI

https://hdl.handle.net/11511/35535

Journal

KNOWLEDGE-BASED SYSTEMS

DOI

https://doi.org/10.1016/j.knosys.2010.12.009

Collections

Department of Civil Engineering, Article

Suggestions

OpenMETU
Core

A new offline path search algorithm for computer games that considers damage as a feasibility criterion Bayılı, Serhat; Polat, Faruk; Department of Computer Engineering (2008) 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 tole...
Real-Time Moving Target Search Undeger, Cagatay; Polat, Faruk (2007-11-23) In this paper, we propose a real-time moving target search algorithm for dynamic and partially observable environments, modeled as grid world. The proposed algorithm, Real-time Moving Target Evaluation Search (MTES), is able to detect the closed directions around the agent, and determine the best direction that avoids the nearby obstacles, leading to a moving target which is assumed to be escaping almost optimally. We compared our proposal with Moving Target Search (NITS) and observed a significant improvem...
Quantum Search in Sets with Prior Knowledge Çalıkyılmaz, Umut; Turgut, Sadi; Department of Physics (2021-10-7) Quantum search algorithm revolutionized the field by reducing the complexity significantly for the search problem. However, by not being able to decrease the complexity to logarithmic scales, this algorithm still needs a significant amount of time to solve the search problem for large sets. It is proven that the order of the time required to solve this problem cannot be reduced further but, making an improvement by some constant factor is still possible. This aim has been pursued by some scientists in the p...
MOD* Lite: An Incremental Path Planning Algorithm Taking Care of Multiple Objectives Oral, Tugcem; Polat, Faruk (2016-01-01) The need for determining a path from an initial location to a target one is a crucial task in many applications, such as virtual simulations, robotics, and computer games. Almost all of the existing algorithms are designed to find optimal or suboptimal solutions considering only a single objective, namely path length. However, in many real life application path length is not the sole criteria for optimization, there are more than one criteria to be optimized that cannot be transformed to each other. In this...
Real-time edge follow: A real-time path search approach Undeger, Cagatay; Polat, Faruk (2007-09-01) Real-time path search is the problem of searching a path from a starting point to a goal point in real-time. In dynamic and partially observable environments, agents need to observe the environment to track changes, explore to learn unknowns, and search suitable routes to reach the goal rapidly. These tasks frequently require real-time search. In this paper, we address the problem of real-time path search for grid-type environments; we propose an effective heuristic method, namely a real-time edge follow al...

Citation Formats

S. Bayılı and F. Polat, “Limited-Damage A*: A path search algorithm that considers damage as a feasibility criterion,” KNOWLEDGE-BASED SYSTEMS, pp. 501–512, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/35535.