Direction based Heuristic for Pathfinding in Video Games

α
Geethu Elizebeth Mathew
Geethu Elizebeth Mathew
σ
Mrs. G.Malathy
Mrs. G.Malathy
α Anna University, Chennai Anna University, Chennai

Send Message

To: Author

Direction based Heuristic for Pathfinding  in Video Games

Article Fingerprint

ReserarchID

CSTGV70VLE

Direction based Heuristic for Pathfinding  in Video Games Banner

AI TAKEAWAY

Connecting with the Eternal Ground
  • English
  • Afrikaans
  • Albanian
  • Amharic
  • Arabic
  • Armenian
  • Azerbaijani
  • Basque
  • Belarusian
  • Bengali
  • Bosnian
  • Bulgarian
  • Catalan
  • Cebuano
  • Chichewa
  • Chinese (Simplified)
  • Chinese (Traditional)
  • Corsican
  • Croatian
  • Czech
  • Danish
  • Dutch
  • Esperanto
  • Estonian
  • Filipino
  • Finnish
  • French
  • Frisian
  • Galician
  • Georgian
  • German
  • Greek
  • Gujarati
  • Haitian Creole
  • Hausa
  • Hawaiian
  • Hebrew
  • Hindi
  • Hmong
  • Hungarian
  • Icelandic
  • Igbo
  • Indonesian
  • Irish
  • Italian
  • Japanese
  • Javanese
  • Kannada
  • Kazakh
  • Khmer
  • Korean
  • Kurdish (Kurmanji)
  • Kyrgyz
  • Lao
  • Latin
  • Latvian
  • Lithuanian
  • Luxembourgish
  • Macedonian
  • Malagasy
  • Malay
  • Malayalam
  • Maltese
  • Maori
  • Marathi
  • Mongolian
  • Myanmar (Burmese)
  • Nepali
  • Norwegian
  • Pashto
  • Persian
  • Polish
  • Portuguese
  • Punjabi
  • Romanian
  • Russian
  • Samoan
  • Scots Gaelic
  • Serbian
  • Sesotho
  • Shona
  • Sindhi
  • Sinhala
  • Slovak
  • Slovenian
  • Somali
  • Spanish
  • Sundanese
  • Swahili
  • Swedish
  • Tajik
  • Tamil
  • Telugu
  • Thai
  • Turkish
  • Ukrainian
  • Urdu
  • Uzbek
  • Vietnamese
  • Welsh
  • Xhosa
  • Yiddish
  • Yoruba
  • Zulu

Abstract

Pathfinding has been one of major research areas in video games for many years. It is a key problem that most of the video games are confronted with. Search algorithms such as the A* algorithm and the Dijkstra’s algorithm representing such regular grid, visibility graphs also have significant impact on the performance. This paper reviews the current widely used solutions for pathfinding and proposes a new method which is expected to generate a higher quality path using less time and memory than other existing solutions. The deployment of the methodologies and techniques is described in detail. The significance of the proposed method in future video games is addressed and the conclusion is given at the end.

References

16 Cites in Article
  1. Peter Hart,Nils Nilsson,Bertram Raphael (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths.
  2. R Korf (1985). Depth-first iterativedeepening: 2. An optimal admissible tree search.
  3. Yngvi Björnsson,Markus Enzenberger,Holte,C Robert (2005). Fringe Search: Beating A* at Pathfinding Game Maps.
  4. Yngvi Björnsson,Vadim Bulitko,Nathan Sturtevant (2009). TBA*: Time-Bounded A*.
  5. Rahul Kala,Anupam Shukla,Ritu Tiwari (2010). Fusion of probabilistic A* algorithm and fuzzy inference system for robotic path planning.
  6. Cen Zeng,Qiang Zhang,Xiaopeng Wei (2012). GA-based Global Path Planning for Mobile Robot Employing A* Algorithm.
  7. Qing Xue,Yung-Ping Chien (1995). DETERMINING THE PATH SEARCH GRAPH AND FINDING A COLLISION-FREE PATH BY THE MODIFIED A* ALGORITHM FOR A 5-LINK CLOSED CHAIN.
  8. B Stout (2000). Game Planning and Programming Basics.
  9. A Botea,M Enzenberger,M Mueller,J Schaeffer (2004). Macro-FF: Improving AI Planning with Automatically Learned Macro-Operators.
  10. Nils Nilsson (1998). Planning.
  11. P Hart,N Nilsson,B Raphael (1968). A formal basis for the heuristic determination of minimum cost paths.
  12. B Stout (1996). Smart moves: intelligent path-finding.
  13. P Tozour (2002). Extending the Spatial Coverage of a Voxel-Based Navigation Mesh.
  14. Steve Rabin,Nathan Sturtevant (2000). Pathfinding Architecture Optimizations.
  15. N Sturtevant,M Buro (2005). Partial pathfinding usingmap abstraction and refinement.
  16. Nathan Sturtevant (2007). Memory-Efficient Abstractions for Pathfinding.

Funding

No external funding was declared for this work.

Conflict of Interest

The authors declare no conflict of interest.

Ethical Approval

No ethics committee approval was required for this article type.

Data Availability

Not applicable for this article.

How to Cite This Article

Geethu Elizebeth Mathew. 2015. \u201cDirection based Heuristic for Pathfinding in Video Games\u201d. Global Journal of Computer Science and Technology - F: Graphics & Vision GJCST-F Volume 15 (GJCST Volume 15 Issue F1): .

Download Citation

Journal Specifications

Crossref Journal DOI 10.17406/gjcst

Print ISSN 0975-4350

e-ISSN 0975-4172

Keywords
Classification
I.2.1 K.8.0
Version of record

v1.2

Issue date

June 4, 2015

Language
en
Experiance in AR

Explore published articles in an immersive Augmented Reality environment. Our platform converts research papers into interactive 3D books, allowing readers to view and interact with content using AR and VR compatible devices.

Read in 3D

Your published article is automatically converted into a realistic 3D book. Flip through pages and read research papers in a more engaging and interactive format.

Article Matrices
Total Views: 8098
Total Downloads: 2214
2026 Trends
Related Research

Published Article

Pathfinding has been one of major research areas in video games for many years. It is a key problem that most of the video games are confronted with. Search algorithms such as the A* algorithm and the Dijkstra’s algorithm representing such regular grid, visibility graphs also have significant impact on the performance. This paper reviews the current widely used solutions for pathfinding and proposes a new method which is expected to generate a higher quality path using less time and memory than other existing solutions. The deployment of the methodologies and techniques is described in detail. The significance of the proposed method in future video games is addressed and the conclusion is given at the end.

Our website is actively being updated, and changes may occur frequently. Please clear your browser cache if needed. For feedback or error reporting, please email [email protected]

Request Access

Please fill out the form below to request access to this research paper. Your request will be reviewed by the editorial or author team.
X

Quote and Order Details

Contact Person

Invoice Address

Notes or Comments

This is the heading

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.

High-quality academic research articles on global topics and journals.

Direction based Heuristic for Pathfinding in Video Games

Geethu Elizebeth Mathew
Geethu Elizebeth Mathew Anna University, Chennai
Mrs. G.Malathy
Mrs. G.Malathy

Research Journals