Offline Grid-Based Coverage path planning for guards in games
This work addresses the issue of poor and unnatural coverage behavior in video game NPCs, though it is an incremental step towards more efficient algorithms.
The paper tackled the problem of exhaustive coverage path planning for guards in video games by introducing a novel grid-based algorithm for 2D polygonal areas with holes, showing good performance in experiments across various scenarios including complex game maps.
Algorithmic approaches to exhaustive coverage have application in video games, enabling automatic game level exploration. Current designs use simple heuristics that frequently result in poor performance or exhibit unnatural behaviour. In this paper, we introduce a novel algorithm for covering a 2D polygonal (with holes) area. We assume prior knowledge of the map layout and use a grid-based world representation. Experimental analysis over several scenarios ranging from simple layouts to more complex maps used in actual games show good performance. This work serves as an initial step towards building a more efficient coverage path planning algorithm for non-player characters.