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

168
views

77
downloads

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

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.