In game industry, Behaviour tree is commonly used concerning about AI-driven development. but what we learn about AI first is normally Finite State Machine(FSM). In my project, I will use FSM as my method to code the main enemy and there are couple of reasons for this choice. And literature review grants me a clear view of these two main solution.
In my internship with a FPS project, the enemy AI is a critical part of all. What should enemy AI do at this moment? Do they always have the right option? What should they do under complex situations? Or more advanced, do they have their own personality?
The designer I talked to give me a model for these AI-related problems. They called it the OODA loop – Observe, Orient, Decide and Act. That is from strategist and U.S. Air Force Colonel John Boyd[3]. But this procedure is for fighter pilots, which cannot be directly used as an AI judgment model. In short, there will be a blackboard or Director AI to do the Observe and part of Orient job. And in actual contact, each AI-driven enemy will do the rest. Limitation of information input of each enemy will ensure the flexibility of changing circumstances and make them feel “real”. And yes, there are different personality for each enemy which result in various actions facing players.
All actions above is implemented by the Behavior Tree. Here I will not fully explain how exactly behavior tree works. Tree in computer science is a data structure which provide a way to store information. And behavior tree is more like judgment procedure using the Tree structure. There are father nodes and children nodes. Decisions will only goes from father nodes to children nodes all the way down to minimal nodes, which is basic actions like running or shooting. And in different conditions, father nodes will choose different child node to make the right choice.
In comparison, there are finite state machine to operate this procedure easier to understand.
FSM is also a concept in computer science. Each state represent a situation where the AI stays in. And with factors changes, the current state will change to another like from running to standing. There are also many conditions that helps FSM to decide.
Differences
And the main difference between these two methods is extendibility. In FSM, each state added will bring huge pressure to calculation and storage part. From description above, we can conclude that for N states in total, there will be N^2 conditional judgments max in one tick. And also it is heavy coding for developers.
There are also problems in behavior tree. The biggest one would be that different trees might conflict with each other. Like in what condition, should the AI run from players instead of shooting players? Director AI might have a decision but enemy AI have another. So in actual development, there are more structure added to avoid conflictions. Also the behavior trees will consume huge amount of memory and calculation ability when they are numerous. But there are also ways to avoid that.
Conclusion
In conclusion, in AAA project in game industry, the behavior tree will be used frequently due to its good extendibility. The designer need no programming skills to arrange fixed tree nodes. Coding team can focus more on basic nodes development. But for smaller team or project, FSM is also acceptable for simple AI enemy. And it is also convenient for indie developers who act as programmer and designer simultaneously. For my project, I will choose FSM and see how it goes. If there are problems in maintaining, I will switch to behavior tree structure instead.
Bibliography
Angerman, W.S., 2004. Coming full circle with Boyd’s OODA loop ideas: An analysis of innovation diffusion and evolution.
Saini, S., Chung, P.W.H. and Dawson, C.W., 2011, August. Mimicking human strategies in fighting games using a data driven finite state machine. In 2011 6th IEEE Joint International Information Technology and Artificial Intelligence Conference (Vol. 2, pp. 389-393). IEEE.
Nicolau, M., Perez-Liebana, D., O’Neill, M. and Brabazon, A., 2016. Evolutionary behavior tree approaches for navigating platform games. IEEE Transactions on Computational Intelligence and AI in Games, 9(3), pp.227-238