Heatmap Weighted A* Algorithm for NPC Pathfinding

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.