MATHEMATICAL AND GRAPH-THEORETICAL ANALYSIS OF BEHAVIOR TREES FOR NPC MODELING

Abstract

Behavior Trees (BTs) have emerged as a widely adopted method for modeling Non-Player Character (NPC) behavior in digital games, offering modularity, scalability, and flexibility compared to traditional approaches such as Finite State Machines. This paper explores the theoretical underpinnings of BTs and their application in NPC modeling. Behavior trees are formalized using graph theory, propositional logic, and probabilistic models, and their computational complexity is analyzed to position them within the broader mathematical framework of decision-making systems. Furthermore, practical examples are presented to demonstrate the advantages of BTs in creating adaptive and realistic NPC behaviors. The results highlight that BTs not only provide practical benefits for game developers but also offer a rigorous mathematical structure for analyzing decision-making models, enabling comparison with alternative approaches such as Markov Decision Processes and reinforcement learning.