Player-Traced Empirical Cost-Surfaces for A* Pathfinding

Abstract

This paper discusses the use of empirical cost-surfaces derived from substantial amounts of player-traced movements in an online vehicular combat game, for the purposes of improving A* pathfinding by AI vehicles. The fundamental concept is that we derive navigational meshes from human-player movements, with each node weighted by frequency of use. Our goals include the improvement of path travel times, aesthetic improvements, and the reduction of damage sustained while travelling across the map.

The results presented include quantifiable timings and observational characteristics. Quantifiable improvements include both algorithmic efficiency and travel time efficiency, while observations include the improved ability to avoid risky terrain features as well as other subtle human-like behaviours.

A best -performing non-linear cost function for the A* algorithm, based on player data, is suggested. Continued and future work on the AI in the game is discussed.