Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
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
180
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
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.