Offline Grid-Based Coverage path planning for guards in games
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Large-Scale Multi-Robot Coverage Path Planning on Grids with Path Deconfliction
We study Multi-Robot Coverage Path Planning (MCPP) on a 4-neighbor 2D grid G, which aims to compute paths for multiple robots to cover all cells of G. Traditional approaches are limited as they first compute coverage tre…
Multi-Agent Path FindingOnline Concurrent Multi-Robot Coverage Path Planning
Recently, centralized receding horizon online multi-robot coverage path planning algorithms have shown remarkable scalability in thoroughly exploring large, complex, unknown workspaces with many robots. In a horizon, the…
Benchmarking Classical Coverage Path Planning Heuristics on Irregular Hexagonal Grids for Maritime Coverage Scenarios
Coverage path planning on irregular hexagonal grids is relevant to maritime surveillance, search and rescue and environmental monitoring, yet classical methods are often compared on small ad hoc examples or on rectangula…
Learning Coverage Paths in Unknown Environments with Deep Reinforcement Learning
Coverage path planning (CPP) is the problem of finding a path that covers the entire free space of a confined area, with applications ranging from robotic lawn mowing to search-and-rescue. When the environment is unknown…
Deep Reinforcement Learningreinforcement-learningContinuous World Coverage Path Planning for Fixed-Wing UAVs using Deep Reinforcement Learning
Unmanned Aerial Vehicle (UAV) Coverage Path Planning (CPP) is critical for applications such as precision agriculture and search and rescue. While traditional methods rely on discrete grid-based representations, real-wor…
Deep Reinforcement LearningMotion Planning