Home // International Journal On Advances in Software, volume 16, numbers 1 and 2, 2023 // View article

Heatmap Weighted A* Algorithm for NPC Pathfinding and Graph Switching

Authors:
Paul Williamson
Christopher Tubb

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

Abstract:
Non-Player Characters 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 that it is 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. This paper also investigates switching between the heatmap weighted graph and a standard A* graph, depending on the task being undertaken. This graph switching was used in an experiment to evaluate if the model has an impact on navigation perception when subjects were tasked with fighting against NPCs.

Pages: 97 to 108

Copyright: Copyright (c) to authors, 2023. Used with permission.

Publication date: June 30, 2023

Published in: journal

ISSN: 1942-2628