Video game pathfinding and improvements to discrete search on grid-based maps

摘要: The most basic requirement for any computer controlled game agent in a video is to be able successfully navigate the environment. Pathfinding an essential component of navigation system. is, at simplest level, search technique finding route between two points real-time multi-agent nature games places extremely tight constraints on pathfinding problem. This study aims provide first complete review current state both regards graph algorithms employed as well implications within dynamic environments. Furthermore this thesis presents novel work form domain specific algorithm use grid-based maps: spatial grid A* which shown offer significant improvements over intended domain.