Authors: Nicholas Mario Wardhana, Henry Johan, Peter Kok Keong Loh, Hock Soon Seah, Darren Wee Sze Ong
In virtual environments, such as First Person Shooter (FPS), Role Playing Game (RPG) and Real-Time Strategy (RTS) computer games, pathfinding is used to determine a character’s path from a starting position to a goal position. It is common in this process to use waypoint representations instead of the raw map to reduce the computational and storage costs. Waypoints are usually created and connected manually by the game designer. Several research approaches to generate map representation in games exist but most of them focus on roadmap . Visibility graph is commonly used to connect waypoints automatically, such as in . However, because there are many paths originating from a waypoint, a pathfinding process between two waypoints will be time-consuming. In this paper, we address these issues by generating waypoints based on the map geometry and also proposing a technique to establish a more efficient connection graph with less number of connections to reduce the computational cost and storage overheads.