Clarifications and extensions to tactical waypoint graph algorithms for video games

ABSTRACT

This paper explores pathfinding in a video game environment using a waypoint graph, a common way of representing locations in the environment. I take algorithms created by Lars Liden on finding strategic positions for agents within a waypoint graph and extend these algorithms. I demonstrate how the extended algorithms are able 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.

References

1. Liden, L. Strategic and Tactical Reasoning with Waypoints. AI Game Programming Wisdom. Charles River Media, Hingham, MA, 2002, 211--219.
2. Nareyek, A. Artificial Intelligence in Computer Games - State of the Art and Future Directions. ACM Queue 1, 10 (2004), 58--65.
3. Salomon, B., Garber, M., Lin, M., Manocha, D. Interactive Navigation in Complex Environments Using Path Planning, University of North Carolina, Chapel Hill, NC, 2003.
4. Tan, D., Robertson, T., Czerwinski, M. Exploring 3D navigation: combining speed-coupled flying with orbiting. In Proceedings of the SIGCHI conference on Human factors in computing systems. (2001), 418--425.

Index Terms

• Applied computing

  • Computers in other domains

    • Personal computers and PC applications

      • Computer games

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Discrete space search

      • Game tree search

• Information systems

  • Information systems applications

    • Multimedia information systems

      • Massively multiplayer online games

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Virtual worlds software

        • Interactive games

• Theory of computation

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design