Show/Hide Menu
Hide/Show Apps
anonymousUser
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Videos
Videos
Thesis submission
Thesis submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
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
8
views
3
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
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, 2008.