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
A new offline path search algorithm for computer games that considers damage as a feasibility criterion
Download
index.pdf
Date
2008
Author
Bayılı, Serhat
Metadata
Show full item record
Item Usage Stats
299
views
145
downloads
Cite This
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, Thesis
Suggestions
OpenMETU
Core
A test oriented service and object model for software product lines
Parlakol, Nazif Bülent; Karagöz, Pınar; Department of Computer Engineering (2010)
In this thesis, a new modeling technique is proposed for minimizing regression testing effort in software product lines. The “Product Flow Model” is used for the common representation of products in application engineering and the “Domain Service and Object Model” represents the variant based relations between products and core assets. This new approach provides a solution for avoiding unnecessary work load of regression testing using the principles of sub-service decomposition and variant based product/sub...
Limited-Damage A*: A path search algorithm that considers damage as a feasibility criterion
Bayılı, Serhat; Polat, Faruk (2011-05-01)
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 ...
Learning cooperation in hunter-prey problem via state abstraction
İşçen, Atıl; Polat, Faruk; Department of Computer Engineering (2009)
Hunter-Prey or Prey-Pursuit problem is a common toy domain for Reinforcement Learning, but the size of the state space is exponential in the parameters such as size of the grid or number of agents. As the size of the state space makes the flat Q-learning impossible to use for different scenarios, this thesis presents an approach to make the size of the state space constant by producing agents that use previously learned knowledge to perform on bigger scenarios containing more agents. Inspired from HRL metho...
Automatic web service composition with ai planning
Kuzu, Mehmet; Çiçekli, Fehime Nihan; Department of Computer Engineering (2009)
In this thesis, some novel ideas are presented for solving automated web service composition problem. Some possible real world problems such as partial observability of environment, nondeterministic effects of web services, service execution failures are solved through some mechanisms. In addition to automated web service composition, automated web service invocation task is handled in this thesis by using reflection mechanism. The proposed approach is based on AI planning. Web service composition problem i...
A 3D topological tracking system for augmented reality
Ercan, Münir; Can, Tolga; Department of Computer Engineering (2010)
Augmented Reality (AR) has become a popular area in computer Science where research studies and technological innovations are extensive. Research in AR first began in the early 1990s and thenceforth, a number of di erent tracking algorithms and methods have been developed. Tracking systems have a critical importance for AR and marker based vision tracking systems became the mostly used tracking systems due to their low cost and ease of use. Basically, marker systems consist of special patterns that are plac...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
S. Bayılı, “A new offline path search algorithm for computer games that considers damage as a feasibility criterion,” M.S. - Master of Science, Middle East Technical University, 2008.
