Hierarchical Task Networking in a Turn-Based Combat Simulation!
Introduction
Hierarchical Task Networking (HTN) is a static-traditional planning method that enables AI to predict future in-game situations; the AI can then execute a responsive action (task). For instance, if a player is charging up a powerful attack, the enemy will attempt to interrupt the player before they can cast the spell by either knocking the player down or stunning them. The enemy can even execute distractive measures like throwing a smoke bomb to reduce the player's accuracy, as mentioned in the 2021 "AI Summit: Advanced Real-Time Hierarchical Task Networks: A New Approach" GDC talk by Tomohiro Mori and Kousuke Namiki. These actions or tasks the AI can pursue can come in two types: primitive and compound. Primitive tasks are the direct singular action the AI will conduct. While compound tasks are multiple primitive tasks, the AI can perform as a response (EX: the AI ducking and reloading from player fire). Hierarchical Task Networking is remarkable as it has the ability to further breakdown compound tasks into individual sub-primitive tasks to accomplish the minuscule of details in a responsive action in a game (EX: the AI in a boxing game can block the player's attack in a specific area of there body instead of only executing a face block for all player attacks).
Hierarchical Task Network
Hierarchical Task Networking is a static planning method, which means it thrives in a non-dynamic (static) environment. The AI generates a "chain" of responsive tasks to perform to adapt to the in-game situation. After the AI performs a task, that task can be deleted or stored at the end of the chain for later reuse. Chain of tasks order matters! So if an action the AI wants to execute exists within a chain, but that task is not the first task of that HTN chain, the AI will have to create an entirely new chain with that wanted task first. Highly dynamic environments with HTN utilized can cause performance issues, as the AI will most likely generate a new chain based on every environmental change. Static environments provide "a breathing space" for the AI to recycle and reuse previously created chains with the wanted action first instead of the constant chain generation. The more frequent an agent has to re-plan, the less predictable the agent will be, thus turning the AI into a reactive agent with limited/narrow long-term prediction. To effectively perform Hierarchical Task Networking, one must perform these following actions:
Recycle chain with wanted task first if present.
Create a chain with the wanted task first if a chain was not recycled.
Delete oldest least utilized chain(s) if reached maximum chain list capacity.
Execute chain’s first task.
Recycle Chain
When the agent wants to respond to an in-game situation, HTN checks if there is a valid chain (a chain with the wanted task at the beginning of the chain list) present in the network. If the valid chain is found, every chain is shifted downwards until the wanted chain is the first element of the network, the last element is the oldest and least utilized chain in the network. To optimize chain recycling, instead of checking through a list of all chains, one can classify what type of action that chain can belong to based on the environment. For instance, hiking and jumping over obstacles tasks should most likely not belong to a chain list for a flat-plain-like environment.
Chain Recycling function. I passed in a wantedTaskID as a parameter to compare the agent's wanted task id with the first task in the agent’s HTN chain list (network).
A sort algorithm that shifts the wanted chain to the front of the chain list (network).
Create Chain
If a chain with the agent's wanted task first could not be recycled, a new chain with the wanted task is created with the wanted task as its first element is created. After the wanted task is created, another task that the AI might want to undergo next (based on the in-game situation) is added to that chain until the chain length reaches its max capacity.
I created a new chain with the wanted task and added it to the AI’s chain list (network). I then recycle that chain so that it can be the first element in the network.
When adding a non-agent-wanted task to a chain, I check if the task condition function is true, which takes into account all the situations in the environment. In my case, if the target were to have charged up their attack last turn, the AI may want to add the block task to the chain, to prevent a massive amount of damage in the near future. If the task has been added to the list, decrease the amount of task to make until it reaches zero. (mTaskToMake = the chain length at start)
Delete Chain
For optimization purposes, the delete chain function removes the oldest and least utilized chains in the network only once the network has reached its maximum chain capacity. If one opts to delete executed tasks, then the delete chain function will also delete chains with zero tasks in them as they serve no purpose.
Execute Chain
After recycling or creating a chain with the wanted task first and deleting old leased utilized chains, the agent can then perform their desired action. The desired action (task) is the first element of the chain list (network) and the first element of the chain's task list. After completing the desired action, one could decide to delete the task from the executed chain's task list or move it to the end of that chain's task list for later reuse.
Applications & Conclusion
There are many static-environment-game applications in which Hierarchical Task Networking thrives, one game genre being turn-based strategy. I tried to simulate a combat simulation between a user-controlled player character versus a computer AI, who will utilize in-game situations, like having low health, being de-buffed, or being stunned on the previous turn, to conduct a "smart" responsive action. Overall, with some small feats that I need more time cleaning, the AI delivers a medium balance of re-planning (creating new chains) and reusing previously created tasks to provide a not a low-to-normal level opponent experience. In turn-based games, if the AI's attack pattern is foreseeable, it is most likely continually reusing its HTN chain. If the opponent is less predictable, it may have created new chains to respond to the in-game actions; thus increasing the level of challenge.
The player’s attack options. The player and the opponent AI utilizes the same actions to:
Increase damage (charge).
Avoid damage (block).
Recover health (heal), health percentage based.
Harms the other party (attack).
Forces the other party to lose their turn (stun).
Reduce healing and attack damage (Debuff).
Video Demonstration Link:
With more development time, I would make attacks look more turn-based. There is an initiative value that determines which party will act first, but it is not visually displayed. As a result, the combat looks as if everything is happening at once. Also I would love to add visual effects to the performed actions to display more visual feedback to give more life to my turn-based combat simulation. For example, it would be funny to see a flying red boxing fist hit the blue player!
References
AI Summit. (2022). Ai Summit: Advanced Real-Time Hierarchical Task Networks: A New Approach. GDC Vault. Retrieved April 18, 2022, from https://www.gdcvault.com/browse/?track_category=1402.