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.

Keywords

• Artificial intelligence
• Digital games
• Behavior trees
• Mathematical modeling
• Game NPCs

References

1. [1] Nilsson NJ. John McCarthy. Natl Acad Sci 2012; 1–27.
2. [2] Esteva A, Robicquet A, Ramsundar B, Kuleshov V, DePristo M, Chou K, Dean M. A guide to deep learning in healthcare. Nat Med 2019; 25(1): 24–29.
3. [3] Pan Y, Hassan MM, Gumaei A, Alsanad A, Alrubaian A. Voice command recognition using deep learning for IoT applications. Future Gener Comput Syst 2020; 106: 624–634.
4. [4] Grigorescu S, Trasnea B, Cocias T, Macesanu G. A survey of deep learning techniques for autonomous driving. J Field Robot 2020; 37(3): 362–386.
5. [5] Sermanet P, Lynch A, Kavukcuoglu Y, Chintala S. Navigating complex environments with end-to-end reinforcement learning and attention. In: IEEE Conference on Computer Vision and Pattern Recognition; 2019.
6. [6] Silver D, et al. Mastering the game of Go with deep neural networks and tree search. Nature 2016; 529(7587): 484–489.
7. [7] Champandard AJ. AI game development: Synthetic creatures with learning and reactive behaviors. Indianapolis, IN, USA: New Riders, 2007.
8. [8] Justesen N, Bontrager P, Togelius J, Risi S. Deep learning for video game playing. IEEE Trans Games 2019; 12(1): 1–20.

9. [9] Shaker N, Togelius J, Nelson MJ. Procedural content generation in games: A textbook and an overview of current research. Cham, Switzerland: Springer, 2016.
10. [10] Hunicke R. The case for dynamic difficulty adjustment in games. In: ACM SIGCHI Int Conf Advances in Computer Entertainment Technology; 2005.
11. [11] Yannakakis GN, Togelius J. Artificial intelligence and games. Cham, Switzerland: Springer, 2018.
12. [12] Drachen A, Sifa R, Thurau C. Player modeling in video games: A survey. ACM Comput Surv 2015; 48(3): 1–40.
13. [13] Liapis A, Yannakakis GN, Togelius J. Sentient sketchbook: Computer-aided game level authoring. In: 8th Int Conf Foundations of Digital Games; 2013.
14. [14] El-Nasr MS, Drachen A, Canossa A. Game analytics: Maximizing the value of player data. Cham, Switzerland: Springer, 2016.
15. [15] Türkmen S, Mungan HY, Tekir S. Bir platform oyununa kullanıcı performansı temelinde yapay zeka uyarlaması (article in Turkish). In: 9th Turkish National Software Engineering Symposium; 2015.
16. [16] Riedl MO. A python engine for teaching artificial intelligence in games. arXiv:1511.07714, 2015.
17. [17] Ram A, Ontañón S, Mehta M. Artificial intelligence for adaptive computer games. In: FLAIRS Conference; 2007. pp. 22–29.
18. [18] Aiolli F, Palazzi CE. Enhancing artificial intelligence in games by learning the opponent’s playing style. In: Entertainment Computing Symposium. Boston, MA, USA: Springer, 2008. pp. 1–10.
19. [19] Mourato F, dos Santos MP, Birra F. Automatic level generation for platform video games using genetic algorithms. In: 8th Int Conf Advances in Computer Entertainment Technology; 2011. pp. 1–8.
20. [20] Marcotte R, Hamilton HJ. Behavior trees for modelling artificial intelligence in games: A tutorial. Comput Games J 2017; 6(3): 171–184.
21. [21] Sekhavat YA. Behavior trees for computer games. Int J Artif Intell Tools 2017; 26(3): 1730001.
22. [22] Mnih V, Kavukcuoglu K, Silver D, Graves A, Antonoglou I, Wierstra D, Riedmiller M. Playing Atari with deep reinforcement learning. arXiv:1312.5602, 2013.
23. [23] Ling C, Tollmar K, Gisslén L. Using deep convolutional neural networks to detect rendered glitches in video games. Proc AAAI Conf Artif Intell Interactive Digital Entertainment 2020; 16: 66–73.
24. [24] Flórez-Puga G, Gomez-Martin MA, Gomez-Martin PP, Díaz-Agudo B, Gonzalez-Calero PA. Query-enabled behavior trees. IEEE Trans Comput Intell AI Games 2009; 1(4): 298–308.
25. [25] Marzinotto A, Colledanchise M, Smith C, Ögren P. Towards a unified behavior trees framework for robot control. In: IEEE Int Conf Robotics and Automation (ICRA); 2014. pp. 5420–5425.
26. [26] Diestel R. Graph theory. 5th ed. Cham, Switzerland: Springer, 2017.
27. [27] Bondy JA, Murty USR. Graph theory. London, UK: Springer, 2008.
28. [28] Ögren P, Colledanchise M. Behavior trees in robotics and AI. Boca Raton, FL, USA: CRC Press, 2018.
29. [29] Huth M, Ryan M. Logic in computer science: Modelling and reasoning about systems. 2nd ed. Cambridge, UK: Cambridge University Press, 2004.
30. [30] Champandard AJ. Behavior trees for AI: How they work. Game AI Pro 2013; 1: 1–12.
31. [31] Bertsekas DP. Dynamic programming and optimal control. 4th ed. Belmont, MA, USA: Athena Scientific, 2017.
32. [32] Kaelbling LP, Littman ML, Moore AW. Reinforcement learning: A survey. J Artif Intell Res 1996; 4: 237–285.
33. [33] Togelius J, Yannakakis GN, Stanley KO, Browne C. Search-based procedural content generation: A taxonomy and survey. IEEE Trans Comput Intell AI Games 2011; 3(3): 172–186.
34. [34] Knuth DE. The art of computer programming, volume 1: Fundamental algorithms. 3rd ed. Boston, MA, USA: Addison-Wesley, 1997.
35. [35] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithms. 3rd ed. Cambridge, MA, USA: MIT Press, 2009.
36. [36] Goodrich MT, Tamassia R. Data structures and algorithms in Java. 5th ed. Hoboken, NJ, USA: Wiley, 2010.
37. [37] Sedgewick R, Wayne K. Algorithms. 4th ed. Boston, MA, USA: Addison-Wesley, 2011.
38. [38] Hopcroft JE, Ullman JD, Aho AV. Data structures and algorithms. Boston, MA, USA: Addison-Wesley, 1983.
39. [39] Weiss MA. Data structures and algorithm analysis. Redwood City, CA, USA: Benjamin-Cummings, 1995.
40. [40] Comer D. The ubiquitous B-tree. ACM Comput Surv 1979; 11(2): 121–137.
41. [41] Isla D. Handling complexity in the Halo 2 AI. In: Game Developers Conference; 2005.
42. [42] Colledanchise M, Ögren P. Behavior trees in robotics and AI: An introduction. arXiv:1709.00084, 2017.