Elon University Home

Elon Computing Sciences

Clarifications And Extensions To Tactical Waypoint Graph Algorithms For Video Games

Presentation at Elon Student Undergraduate Research Forum, Spring 2007

Dustin E. White (Dr. Shannon Duvall ) Department of Computing Sciences

This project explores Artificial Intelligence techniques for pathfinding, implemented in a video game environment. Video games provide a natural application for Artificial Intelligence because the complex environments of the game already exist, and video games can provide a place to apply theories that are more difficult to apply to the real world. Pathfinding, or how the computer controlled character (agent) moves around the environment, has important applications in video games as well as many other real-world situations.

One common way for agents to move around in a video game environment is through the use of waypoint graphs. Waypoint graphs are a series of connected points which represent paths that the agent can take to move through the environment. The layout of this graph can be exploited to gather additional information that is useful to the agent. One such piece of information is a set of locations which represent the entrances or exits (called pinch points) to an area such as a room. These pinch points can be used to find strategic locations such as suitable places for the agents to ambush an enemy. Liden developed algorithms to find pinch points if an area has only one or two pinch points and he developed an algorithm to find ambush points near a pinch point (Liden, 2002).

After studying Liden’s algorithms, I extended these algorithms to effectively calculate tactical ambush positions and pinch points for any number of agents. The extended algorithms are also able to work in an environment where the agent does not have complete knowledge of the waypoint graph. It is common for more than one agent to be present in a video game so using the extended algorithms is a more practical approach to finding pinch points and ambush points. Finally, I implemented the algorithms into a 2D adventure video game. The results show new ways to extend current pathfinding capabilities.

Liden, L. (2002). Strategic and Tactical Reasoning with Waypoints. In S. Rabin (Ed.), AI Game Programming Wisdom (pp. 211-220). Hingham, MA: Charles River Media, Inc.