Heatmap Weighted A* Algorithm for NPC Pathfinding

Paul Williamson, Christopher Tubb

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Non-Player Characters (NPCs) are characters within a video game, which are not controlled by a human participant. While they are mainly used to fulfil a role not designated for a human player, there are occasions when an NPC needs to play in a human role, and therefore needs to imitate appropriate gameplay behaviours, in such a way they are not easily distinguished from a human player. Navigation is a fundamental gameplay behaviour; focused on how a player traverses the environment when undertaking objectives. This paper explores the possibility of modelling human navigation by modifying A* algorithm with a heatmap derived from human-based data. This is achieved by having participants complete a search and collect experiment, the data is saved for analysis and to develop a navigation model. NPCs using the model undertake the same experiment but with a heatmap weighted A* graph. The experiment explores adjusting the weight of the heatmap so its influence on the pathfinding varies and a comparison can be made to see which weight better reflects the human results.
Original languageEnglish
Title of host publicationSIMUL 2022, The Fourteenth International Conference on Advances in System Simulation
PublisherInternational Academy, Research, and Industry Association
Pages15-21
ISBN (Print)978-1-68558-001-8
Publication statusPublished - 16 Oct 2022
EventThe Fourteenth International Conference on Advances in System Simulation (SIMUL 2022) - Lisbon, Portugal
Duration: 16 Oct 202220 Oct 2022
Conference number: 14th

Publication series

Name
ISSN (Electronic)2038-4537

Conference

ConferenceThe Fourteenth International Conference on Advances in System Simulation (SIMUL 2022)
Abbreviated titleSIMUL 2022
Country/TerritoryPortugal
CityLisbon
Period16/10/2220/10/22

Keywords

  • NPC
  • Player Modelling
  • Pathfinding
  • Gameplay
  • A* Algorithm

Fingerprint

Dive into the research topics of 'Heatmap Weighted A* Algorithm for NPC Pathfinding'. Together they form a unique fingerprint.

Cite this