Adversarial Navigation Mesh Alteration


  • David Hale Univeristy of North Carolina at Charlotte
  • G. Youngblood Univeristy of North Carolina at Charlotte


agent navigation, pathplanning, dynamic environment


Game environments are becoming more and more mutable from the actions of both Players and Non Player Characters (NPCs). However, current generation AI agents do not take advantage of the tactical abilities these mutable worlds provide. We propose a method to make the game agents aware of the mutability of the world by extending their repertoire of abilities to include world alteration commands and some evaluation functions, which determine when and where to alter the world for the greatest tactical gain. Primarily, our work focuses on the Adversarial Navigation Mesh Alteration (ANMA) algorithm, which evaluates potential changes to the map in adversarial environments from an attacker and defender point of view. We present an empirical evaluation of the ANMA algorithm in a Capture The Flag (CTF) simulation environment with several teams of agents. One group of agents (adaptive) lacks the ability to initiate world deformations, but they can respond and re-plan to take advantage of world modifications. The second team of agents (builders) can only generate additional paths through the world using the attacker portion of ANMA. The third team of agents (universal) is able to fully deform the world by generating new paths or removing existing paths using both the attacker and defender sections of ANMA. We evaluated these teams and observed that builder agents beat adaptive agents at a rate of 1.33 to 1. The more advanced universal agents beat adaptive agents at a rate of 2.75 to 1 and builder agents 1.4 to 1.




How to Cite

Hale, D., & Youngblood, G. (2010). Adversarial Navigation Mesh Alteration. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 6(1), 120-125. Retrieved from