Lists of actions: simple, flexible, extensible AI
Most people are used to solving problems in familiar and understandable ways. We prefer not to go off the beaten track and not reinvent the wheel, even if it promises an obvious benefit. It is very difficult to get rid of this way of thinking, so we continue to use outdated technologies and solutions, thereby causing bewilderment among our more advanced peers. In this and the next article I want to acquaint readers with a wide range of solutions that can improve the quality of development. Today we will talk about lists of actions.
Action lists are a simple but powerful type of artificial intelligence (AI) that every game developer should know about. Although they cannot be scaled for large AI networks, they provide complex, unpredictable behavior and are fairly simple to use. This article will be interesting both for beginners of AI programming, and for experienced craftsmen who want to expand their tools. You will learn what action lists are, and get acquainted with specific examples of their implementation that will be useful to you in developing your own solutions. So, let's begin.
')
In a certain kingdom, in a certain state ...
A few years ago, I began to develop the King Randall's Party game, where you need to build a castle and protect it from a siege. I had to create a smart enough AI able to figure out how to bypass the defense and destroy the castle in order to get the gold protected by the player. This task turned out to be too voluminous, so as an intelligent programmer I broke it into several parts. First, I needed to create a specific set of behaviors for units.
As expected, the search results on the Internet blew my brain. The “Game AI” request led me to the real jungle: planners, finite automata, pack behavior, A * search algorithm, search for a path - which wasn’t there. I was completely taken aback, so I did what any sane person would do in my place: I turned to my dog ​​for advice. When a technical problem arises, I always consult my dog. You probably think I'm completely nuts. What can a dog understand in the design? Well, think what you want. Especially, if I tell you how she studied forbidden secret technologies for many years, you still won’t believe me.
In general, I asked her: “Frankie, AI is such an extensive subject that I don’t know at all where to start. How can I create artificial intelligence for gaming units? ” My school teacher, Mr. Francis, said that there are no stupid questions. But contrary to his words, Frankie looked at me as a complete idiot. After a significant pause, she asked in response: "Jesse, what do you do every morning?".
In the mornings, I usually make a list of everything that I need to do in a day, and determine priorities according to urgency. I told Frankie about it, and she replied: "In short, you make a list of actions." It is a list of tasks or behaviors that are alternately performed by game units. This is one of the forms of the system of final states, which resembles the usual behavior tree with one branch. At least that's what my dog ​​says.
Principle of operation
First, let's write all the behaviors that we want to assign to the AI.
Then arrange them in order of priority - from the lowest to the highest.
Now for each action you need to check the execution conditions, as well as the lock property. If the item blocks subsequent actions, exit the list. We'll talk about the importance of blocking later.
The first action in our example - “Attack a player” - will be performed, provided that the unit is located next to the player. Suppose it is not. Then the alternate testing of the remaining actions begins: whether it is possible (and necessary) to build a ladder at this place, and so on, until an action is found that meets the conditions of execution. Let it be the action "Knock the door."
This is where locking comes into play. If the “Knock the door” action happens instantly, it does not block subsequent actions, and they continue to be performed. However, for most actions, several frames are required, so this is the exception rather than the rule. In our case, the “Knock the door” action calls unit.Attack (door), and then the CurrentState property of the units changes from Waiting to BreakDoor and returns true until the door is broken.
Simple state machine
So, everything is quite feasible. It is worth paying tribute to Frankie: lists of actions perfectly suited for my project. But I was still embarrassed that I had never heard of them before. On the other hand, in the context of AI, transition-based state machines are often mentioned, similar to the Mecanim animation system in Unity3D. You define a set of states and specify when and how transitions occur between them. In exchange for the bone, Frankie explained that when creating a finite state machine, it is necessary not only to identify all states, but absolutely all transitions for each of them. Here you can get confused very quickly. For example, if you have a state of receiving damage, you need to specify all the states from which you can go to it: while walking, jumping, squatting or attacking. This can be useful, but at the same time too difficult. If you have fairly simple requirements for AI, do not fool yourself.
Another disadvantage of finite automata is complicated debugging. If you put a breakpoint to look at the current state of the AI, you will not be able to know what state it was before until you use the additional debugging code.
Disadvantages of action lists
Acquainted with the lists of actions closer, I realized that they are ideal for my project, but also have some drawbacks. Their main disadvantage, directly related to the main advantage, is simplicity. Due to the linear structure of the lists, it is simply impossible to build a complex hierarchy of priorities. Let's say the action “Attack a player” should have a higher priority than “Knock the door”, and less priority than “Move to the goal”. But at the same time, the action “Move to the goal” should be lower priority than “Knock out the door”. Solving such problems using action lists is very difficult, while finite state machines click them like nuts.
In general, action lists are very useful for relatively simple AI systems, but the more complex the artificial intelligence, the more intricate it becomes to use them. However, there are several ways to extend their functionality.
Expansion of functionality
Some units in my game can move and attack at the same time. For them, it would be possible to make 2 lists of actions - for movement and attack. But it would be problematic: what if, with certain movements, units cannot attack, or vice versa, to make certain attacks, you need to stand still? This is where action lanes come to the rescue.
In effect, action bars are an enhanced version of the lock feature that allows actions to block only certain items. Let's see how it works.
Each action refers to one or more bands. Therefore, when the Blocking property returns true, the action blocks only those elements that are on one or more bands with it. For example, “Attack a player” refers to the lane, “Move to the goal” - to the lane, and “Build a ladder” - to both, because during construction a unit cannot move and attack. So now, when performing an action, all subsequent elements will be blocked as intended.
Implementation example
And now is the time to practice. To begin with we will configure the list and actions.
Here is the example of the IActionItem implementation for the BreakDoor action (“Knock the door”):
The list of actions can be arranged as a simple list and fill it with IActionItems.
Then we set the method for processing each frame in turn (do not forget about blocking).
With action stripes, things are a little more complicated. In this example, we define them as a bitfield, and then change the IActionItem interface.
Now we have to change the iterator so that it takes into account our lanes of action. If the specific action bar is blocked, it will be skipped, and if not, it will start as usual. If all bands are blocked, the cycle is interrupted.
Conclusion
After some time, Frankie asked me to summarize my work. Having thought it over carefully, I highlighted a few key points:
• Action lists are much easier to manage and configure than state machines.
• They provide a familiar priority system.
• There are several ways to extend their functionality.
As a rule, in programming there are no universal solutions. Having a lot of tools in your arsenal, you can choose the best solutions for specific problems. For King Randall's Party, action lists were perfect. Who knows, maybe this is exactly what your project needs?
Action lists are a simple but powerful type of artificial intelligence (AI) that every game developer should know about. Although they cannot be scaled for large AI networks, they provide complex, unpredictable behavior and are fairly simple to use. This article will be interesting both for beginners of AI programming, and for experienced craftsmen who want to expand their tools. You will learn what action lists are, and get acquainted with specific examples of their implementation that will be useful to you in developing your own solutions. So, let's begin.
')
In a certain kingdom, in a certain state ...
A few years ago, I began to develop the King Randall's Party game, where you need to build a castle and protect it from a siege. I had to create a smart enough AI able to figure out how to bypass the defense and destroy the castle in order to get the gold protected by the player. This task turned out to be too voluminous, so as an intelligent programmer I broke it into several parts. First, I needed to create a specific set of behaviors for units.
As expected, the search results on the Internet blew my brain. The “Game AI” request led me to the real jungle: planners, finite automata, pack behavior, A * search algorithm, search for a path - which wasn’t there. I was completely taken aback, so I did what any sane person would do in my place: I turned to my dog ​​for advice. When a technical problem arises, I always consult my dog. You probably think I'm completely nuts. What can a dog understand in the design? Well, think what you want. Especially, if I tell you how she studied forbidden secret technologies for many years, you still won’t believe me.
In general, I asked her: “Frankie, AI is such an extensive subject that I don’t know at all where to start. How can I create artificial intelligence for gaming units? ” My school teacher, Mr. Francis, said that there are no stupid questions. But contrary to his words, Frankie looked at me as a complete idiot. After a significant pause, she asked in response: "Jesse, what do you do every morning?".
In the mornings, I usually make a list of everything that I need to do in a day, and determine priorities according to urgency. I told Frankie about it, and she replied: "In short, you make a list of actions." It is a list of tasks or behaviors that are alternately performed by game units. This is one of the forms of the system of final states, which resembles the usual behavior tree with one branch. At least that's what my dog ​​says.
Principle of operation
First, let's write all the behaviors that we want to assign to the AI.
Then arrange them in order of priority - from the lowest to the highest.
Now for each action you need to check the execution conditions, as well as the lock property. If the item blocks subsequent actions, exit the list. We'll talk about the importance of blocking later.
The first action in our example - “Attack a player” - will be performed, provided that the unit is located next to the player. Suppose it is not. Then the alternate testing of the remaining actions begins: whether it is possible (and necessary) to build a ladder at this place, and so on, until an action is found that meets the conditions of execution. Let it be the action "Knock the door."
This is where locking comes into play. If the “Knock the door” action happens instantly, it does not block subsequent actions, and they continue to be performed. However, for most actions, several frames are required, so this is the exception rather than the rule. In our case, the “Knock the door” action calls unit.Attack (door), and then the CurrentState property of the units changes from Waiting to BreakDoor and returns true until the door is broken.
Simple state machine
So, everything is quite feasible. It is worth paying tribute to Frankie: lists of actions perfectly suited for my project. But I was still embarrassed that I had never heard of them before. On the other hand, in the context of AI, transition-based state machines are often mentioned, similar to the Mecanim animation system in Unity3D. You define a set of states and specify when and how transitions occur between them. In exchange for the bone, Frankie explained that when creating a finite state machine, it is necessary not only to identify all states, but absolutely all transitions for each of them. Here you can get confused very quickly. For example, if you have a state of receiving damage, you need to specify all the states from which you can go to it: while walking, jumping, squatting or attacking. This can be useful, but at the same time too difficult. If you have fairly simple requirements for AI, do not fool yourself.
Another disadvantage of finite automata is complicated debugging. If you put a breakpoint to look at the current state of the AI, you will not be able to know what state it was before until you use the additional debugging code.
Disadvantages of action lists
Acquainted with the lists of actions closer, I realized that they are ideal for my project, but also have some drawbacks. Their main disadvantage, directly related to the main advantage, is simplicity. Due to the linear structure of the lists, it is simply impossible to build a complex hierarchy of priorities. Let's say the action “Attack a player” should have a higher priority than “Knock the door”, and less priority than “Move to the goal”. But at the same time, the action “Move to the goal” should be lower priority than “Knock out the door”. Solving such problems using action lists is very difficult, while finite state machines click them like nuts.
In general, action lists are very useful for relatively simple AI systems, but the more complex the artificial intelligence, the more intricate it becomes to use them. However, there are several ways to extend their functionality.
Expansion of functionality
Some units in my game can move and attack at the same time. For them, it would be possible to make 2 lists of actions - for movement and attack. But it would be problematic: what if, with certain movements, units cannot attack, or vice versa, to make certain attacks, you need to stand still? This is where action lanes come to the rescue.
In effect, action bars are an enhanced version of the lock feature that allows actions to block only certain items. Let's see how it works.
Each action refers to one or more bands. Therefore, when the Blocking property returns true, the action blocks only those elements that are on one or more bands with it. For example, “Attack a player” refers to the lane, “Move to the goal” - to the lane, and “Build a ladder” - to both, because during construction a unit cannot move and attack. So now, when performing an action, all subsequent elements will be blocked as intended.
Implementation example
And now is the time to practice. To begin with we will configure the list and actions.
Here is the example of the IActionItem implementation for the BreakDoor action (“Knock the door”):
The list of actions can be arranged as a simple list and fill it with IActionItems.
Then we set the method for processing each frame in turn (do not forget about blocking).
With action stripes, things are a little more complicated. In this example, we define them as a bitfield, and then change the IActionItem interface.
Now we have to change the iterator so that it takes into account our lanes of action. If the specific action bar is blocked, it will be skipped, and if not, it will start as usual. If all bands are blocked, the cycle is interrupted.
Conclusion
After some time, Frankie asked me to summarize my work. Having thought it over carefully, I highlighted a few key points:
• Action lists are much easier to manage and configure than state machines.
• They provide a familiar priority system.
• There are several ways to extend their functionality.
As a rule, in programming there are no universal solutions. Having a lot of tools in your arsenal, you can choose the best solutions for specific problems. For King Randall's Party, action lists were perfect. Who knows, maybe this is exactly what your project needs?
Source: https://habr.com/ru/post/281180/
All Articles