  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.
