Home // SIMUL 2022, The Fourteenth International Conference on Advances in System Simulation // View article

Heatmap Weighted A* Algorithm for NPC Pathfinding

Authors:
Paul Williamson
Christopher Tubb

Keywords: NPC; Player Modelling; Pathfinding; Gameplay; A* Algorithm;

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.

Pages: 15 to 21

Copyright: Copyright (c) IARIA, 2022

Publication date: October 16, 2022

Published in: conference

ISSN: 2308-4537

ISBN: 978-1-68558-001-8

Location: Lisbon, Portugal

Dates: from October 16, 2022 to October 20, 2022