Date Added: Oct 2011
Pathfinding has been one of major research areas in video games for many years. It is a key problem that most video games are confronted with. Search algorithm such as Dijkstra's algorithm and A algorithm are representing only half of the picture. The underlying map representations such as regular grid, visibility graph and navigation mesh also have significant impact on the performance. This paper reviews the current widely used solutions for pathfinding and proposes a new method which is expected to generate a higher quality path using less time and memory than other existing solutions. The deployment of methodology and techniques is described in detail. The aim and significance of the proposed method in future video games is addressed and the conclusion is given at the end.