Artificial Intelligence: Behavior Trees Part 4

Types of Decorator Nodes

Decorator nodes only have exactly one child node, and their purpose is to somehow alter the functionality of that individual child node through some sort of operation. You can think of Decorators as “manipulators”, since they are ultimately used to manipulate the return statuses of its only child. Common examples of Decorator nodes are inverting the returned status of its only child node, repeating the processing of the child node, or terminating its child node.

  • Inverter - Inverter Decorator nodes are used to negate the result of their child node’s returned status In other words, if the Inverter’s only child node returns “Success”, then the Inverter sends “Failure” back up to its parent. If the Inverter’s only child node returns “Failure”, then the Inverter sends “Success” back up to its parent. Inverters are often used in conditional tests.

  • Succeeder - Succeeder Decorator nodes ALWAYS return “Success” back to its parent, regardless of the returned status of the Succeeder’s child. This is extremely useful in cases where you anticipate “Failure” in some branch of the tree and when you don’t want to abandon processing of a sequence that that branch contains. Fun Fact: There is no need to create an opposite “Failer” Decorator node because you can easily attach an Inverter as the parent to the Succeeder to always guarantee “Failure” is returned back up the tree!

  • Repeater -A Repeater Decorator node reprocess its child node each time the child node returns a status back up. You can also use Repeaters to reprocess the child node a fixed number of times too, like a loop. Repeater Decorator nodes are commonly used towards the top of Behavior Tree to allow for the tree to run continuously.

  • Repeat Until Fail - A “Repeat Until Fail” Decorator node acts in the same way as the Repeater. It reprocesses its child node each time UNTIL the child node returns a “Failure” status. Once the “Repeat Until Fail” node receives the “Failure” status message from its child, it returns “Success” back up the tree.

Artificial Intelligence: Behavior Trees Part 3

Hello everyone! I’m back from a long break of exhaustion of finishing another semester at college and from the holiday season!

I was previously talking about Behavior Trees, and today I want to continue where I left off with different types of Composite Nodes. Recall that Composite Nodes define the root of a particular branch of a Behavior Tree and the rules for how that branch is executed. In other words, they are mainly used for controlling the logic of each branch of the tree and which AI behavior(s) to perform on that branch.

Types of Composite Nodes

  • Sequences - Sequences are extremely useful when you have a series of AI behaviors that ALL must be completed “successfully” in a particular order before accomplishing a certain task. For example, imagine you want an AI to walk through a door that is currently closed. In order for the AI to complete this task, it first needs to walk to the door, open the door, then walk through the door, and finally close the door. These are all behaviors that must be completed in that order to complete the entire task. A Sequence is a type of Composite Node (i.e. a rule) that visits every child node in order from left-to-right in a linear fashion while checking for a “Success” status message to be returned for each node. If any one of the children nodes sends a “Failure” status message, the entire Sequence stops executing and is also said to “fail”. For example, with the door analogy used above, a failure message may be sent if the AI was interrupted by something, such as the player, another AI, or another event like the door being locked or the path being blocked. You can also think of a Sequence as an AND logic gate operation.

  • Selectors - Selectors are very useful when your AI has many different choices of the actions it can take in a given priority order, and you want the AI to find the single, best action that can be performed “Successfully”. For example, reconsider the last scenario with the game AI walking through a door. With the Sequence above, we assumed the door was always unlocked and could be opened. But what happens if the AI gets to the door and its locked? We can use a Selector here to check if the door can be opened! If the door is locked, meaning the ‘Open Door’ behavior sent a failure status message to the Selector, then the AI can attempt to unlock the door and then open the door. If that behavior “fails”, maybe the AI can try to bust the door in. If that behavior sends failure back to the Selector, then perhaps the door cannot be opened and the Selector also fails. However, you can see that a Selector gives the user a lot more control on the behaviors an AI can exhibit. A Selector is a type of Composite Node that visits it children in priority order from left-to-right and checks for the first child node that returns a “Success” status message. If all of the children nodes send a “Failure” status message, the entire Selector stops executing and also is said to “fail.” You can think of a Selector as an OR logic gate operation.

Here are some really good pictures to show what a Behavior Tree with just Sequences and Selectors looks like to help you understand! These pictures were made by another blogger named Chris Simpson. They are not made by me!

A Sequence Composite node that just describes an AI walking through a doorway. This tree just consists of a Leaf Nodes that define general behaviors for simplicity. The code structure to perform these behaviors is more complicated.Retrieved from htt…

A Sequence Composite node that just describes an AI walking through a doorway. This tree just consists of a Leaf Nodes that define general behaviors for simplicity. The code structure to perform these behaviors is more complicated.

Retrieved from http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

A Behavior Tree with a Sequence and Selector Composite Nodes that also describes an AI walking through a doorway.Retrieved from: http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

A Behavior Tree with a Sequence and Selector Composite Nodes that also describes an AI walking through a doorway.

Retrieved from: http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

A Behavior Tree with a series of Sequences and Selectors that represent an AI attempting to get into a building through both a doorway and a window.Retrieved from: http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How…

A Behavior Tree with a series of Sequences and Selectors that represent an AI attempting to get into a building through both a doorway and a window.

Retrieved from: http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

Artificial Intelligence: Behavior Trees Part 2

I want to briefly describe the different types of nodes that exist within a Behavior Tree data structure when considering AI.

There are 3 general archetypes of Behavior Tree nodes:

  • Composite - Composite nodes are nodes that mainly exist to control the flow of an artificially intelligent agent’s behavior (or sequence of behaviors) and in which order to perform these behaviors. These nodes can have one or more children nodes and are responsible for processing (i.e. determining the status of) any or all of their children nodes. The most common type of Composite node is the Sequence, which processes each child in some specified sequence (in an order) and returns failure to its parent node if any of the children nodes returns a failure status message. The Sequencer will return success if every child returns success.

  • Decorator - Decorator nodes are like Composites, except these nodes can only have one child. Depending on the type of Decorator node, their specific purpose is to either:

    • transform or manipulate the result they receive from their child node's status

    • to terminate (stop execution of) the child

    • or repeat processing of the child

    The most common type of Decorator is the Inverter, which simply just inverts the result returned by the child node (child returns failure —> decorator returns success, or child returns success —> decorator returns failure)

  • Leaf - Leaf nodes are the most expressive and powerful types of nodes for a developer, since these nodes define the game-specific behaviors/actions that an AI can perform. The developer can create the AI behaviors however he/she wants with these nodes! Without these nodes, a Behavior Tree would be useless because there wouldn’t be any behaviors for the AI to perform! Leaf nodes don’t have any children and are (usually) at the lowest level of a tree. Leaf nodes can also be used for determining the current state of the game or to check if a given condition in the game is satisfied.

Sample View of a Behavior Tree with the 3 Archetypes of NodesRetrieved from https://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

Sample View of a Behavior Tree with the 3 Archetypes of Nodes

Retrieved from https://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

Artificial Intelligence: Introducing Behavior Trees

Behavior Trees are exactly what they sound like! A Behavior Tree is considered a tree-based data structure that is used in all sorts of fields today for controlling the behavior of Artificially Intelligent agents. These so-called “Behaviors” can be anything you, as the programmer, can think of. Maybe you want an AI to walk to a certain location on the map and stop if interrupted by the player. Or maybe you the AI to switch between daily routines, such as washing his/her hands, watching TV, talking to others, picking up items, and sleeping. The AI behavior is whatever you define it to be.

More formally, a Behavior Tree (BT) is defined as a tree of hierarchical nodes that control the logical flow of decision making for an artificially intelligent agent, whether that agent be a Robot, a Non-Player Character (NPC) in a video game, or any other autonomous AI entity. Essentially, Behavior Trees offer a way to structure the switching of tasks (or actions) among an AI through the use of control flow and decision making nodes that the programmer specifies. Behavior Trees generally have many different types of nodes, but all nodes in a Behavior Tree tend to have the same core functionality, independent of the implementation.

A core aspect of Behavior Trees is that the leaf nodes of the tree define the actual behaviors that control the AI entity in a game and the branches of the tree contain Utility nodes that control the logical traversal of the tree depending on the behavior best-suited for the given AI’s situation. I like to call the leaf nodes “Behavioral nodes.”

Each node in a Behavior Tree can return different status messages that inform the parent node about whether a certain event or action occurred.

In a basic Behavior Tree, there are three different kinds of status messages:

  1. Success - A node returns a ‘Success’ status message when an action/operation was performed successfully. For example, if an AI is walking to a certain location and finally arrives at its destination, its behavioral leaf node will return success to its parent.

  2. Failure - A node returns a ‘Failure’ status message when an action/operation could NOT be performed successfully. For example, if an AI is walking to a certain location and the player interrupts this AI by either talking to it or running into it, its behavioral leaf node may return failure to its parent.

  3. Running - A node returns a ‘Running’ status message when an action/operation in still in progress and success or failure has not been determined yet. These nodes will continuously be checked again.

General Tree Data Structure Pictorial Representation and TerminologyRetrieved from https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm

General Tree Data Structure Pictorial Representation and Terminology

Retrieved from https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm

An Actual Behavior Tree, perhaps used for a Video Game. The Utility nodes (Selector, Sequence, etc.) will be discussed next.Retrieved from https://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

An Actual Behavior Tree, perhaps used for a Video Game. The Utility nodes (Selector, Sequence, etc.) will be discussed next.

Retrieved from https://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

New Topic: Artificial Intelligence with Implementation

Hello Everyone!

I’ve recently been interested in some concepts revolving around Artificial Intelligence, since I am starting to learn more and more about data structures in my Computer Science courses. I just wanted to give you guys a heads-up that I will be going into depth on AI next! I want to explore the many different AI data structure design choices, the positives/negatives of various approaches and their applications in the workforce in the present day!

I will try to be as detailed as possible about this topic and I will be discussing quite advanced Computer Science concepts some days. However, no worries! I’m learning information about AI right now as we speak too. I plan to discuss the conceptual side of AI for those that don’t have a strong programming background, as well as the programmer side of AI for those that do. Or if you are somewhere in-between, that’s fine too!

I hope to discuss AI with Behavior Trees soon!

I’ve been busy lately, but I plan on staying consistent again soon.

See you soon!

Retrieved from https://www.houseofbots.com/news-detail/3408-1-must-aware-with-the-capability-of-ai

Retrieved from https://www.houseofbots.com/news-detail/3408-1-must-aware-with-the-capability-of-ai

What Makes "Good" AI in Video Games?

Hello everyone!

I found some really fascinating video on what makes Artificial Intelligence “seem good” in video games. It discusses all sorts of aspects on how AI should let the players “cheat” in a way, how they should have memory, how they communicate with their physical interactions among you and others in the world, and much more. I’ve recently been interested in AI, so I will have more to discuss soon. I’m going to find and talk about an article soon to help you guys learn what I’m learning too!

An Introduction to Artificial Intelligence in Video Games

I first became interested in the subject of AI back in March of 2017, when I was on spring break in my senior year of high school. I was reading a book on beginning C++ programming, and I remember the author began discussing how to program a Tic-Tac-Toe game with an Artificially Intelligent opponent. As I observed the C++ code and typed the source code onto my computer, the more I realized how the games I play use artificial intelligence.

For example, one of the most interesting games that uses AI is Animal Crossing for the GameCube. For people who haven't played that game, essentially you are a kid that moves into a new town and you buy a house, and the whole goal of the game is to interact and socialize with other animals, pay off your debt, and purchase new daily items at Tom Nook's shop! Not to mention, that game even mimics the current weather outside in real life in the video game (i.e. if it is raining in real life, it is either rainy or cloudy in the game). One day in the game represents one day in real life; it matches your calendar on your GameCube. But the AI still fascinates me, because every animal in that game has its own personality and almost every time you talk to that same animal, they say something different. There must be hundreds of sayings! The animals even know the time you last talked to them (i.e. the number of days in real life that have gone by). The animals make a lot of decisions for themselves too, like fishing or running around, or even testing you with questions! It is really a brilliant, yet simple game. All you have to do is talk to animals and upgrade your house by finding money or selling items. 

Anyway, as I mentioned before, Ben Sawyer in his book The Ultimate Game Developer's Sourcebook discusses Artificial Intelligence, and I wanted to highlight some key concepts related to AI that I've learned. I don't want to describe anything super technical here because it would probably be extremely confusing to people who haven't seen algorithms before. I am also still learning some of these algorithms myself!

Nevertheless, here are a few important ideas he discusses about AI, but in my own words:

*Note: an 'agent' usually refers to any interactive object or entity, such as an AI, within a game.

  • An Artificially Intelligent agent in a game represents a non-player controlled object that appears to make decisions similar to that of a person in real life using a decision-making algorithm. This algorithm processes information provided by the program, where the rules of what kinds of decisions to make (and possibly when to make them) have been formulated by the game designer or programmer himself.

 

  • An Artificially Intelligent agent makes decisions depending on certain factors or conditions, not randomly. For example, these decisions may revolve around the external environment, such as the numbers of threats near the AI's base, or the time of day and a human's hunger level. For example, if the player has an army surrounding the AI's base, then the AI may decide to send all its troops to that location to protect its base after taking 1/2 damage. Or If it is around noon to 2 P.M. sometime, usually a human is hungry for lunch. Thus an artificially intelligent agent at this time in the game may say "Man, I need to eat lunch."

 

  • The hardest part of Artificial Intelligence in video games is the fact that few decisions are "cut and dry", meaning that most decisions either aren't simple to make or sometimes overlap. For example, in real life, you may schedule to hang out with a friend and go to the movies, but you also have to consider "how do I get to the movie theater? Do I drive or is my friend picking me up? Will I need money for food? What time do I leave? Do I need to reserve seats online?", etc. This is why AI depends a lot on Game Theory, and requires a set of actions (or decisions) to be made with certain rules defined in an algorithm. The more factors your algorithm considers, the more realistic your characters may react. This is especially important in games like the Sims or even in sports games like Madden

 

  • As long as the AI appears intelligent to the player without seeming TOO smart, then the game will seem realistic and thus more entertaining. If your AI appears to be too powerful or "cheating" in the eyes of the player (say, by seeing everything you have and knowing your strategy) , then the AI will actually seem literally "artificial." Just like humans, Artificially Intelligent agents must appear to make mistakes at times! This makes them vulnerable and more realistic! Otherwise, the game becomes frustrating and unfulfilling.

Hope that was all interesting! See you guys tomorrow!

AI.png

Briefly on Ray Tracing and Real-Time Rendering

Ever since I wanted to create my own video game engine, I've always been keeping my eye on any sort of new gaming discoveries that have been made. I continually look at past articles on certain game engine techniques.

Lately, I've been studying some really complex mathematics behind Ray Tracing, which is a rendering technique that uses rays of light to determine object interactions and realistic reflections within the gaming world. It is STUNNING how realistic this rendering technique is! However, the only problem with Ray Tracing is that it requires a LOT of processor power to the point where it currently is not able to render in Real-Time on almost all computers. Movies are able to utilize this rendering technique because there are "rendering farms" that can render different scenes for hours and hours. However, video games update every fraction of a second, and thus cannot rely on mastering real-time rendering for all sorts of gaming computers anytime soon. 

Yet, I've read that Nvidia, a leading computing company that manufactures GPUs and specializes in graphics for gaming, has come out with a Ray Tracing library called RTX way back in March. Nvidia seems to be striving for real-time rendering in the distant future using this library! They also announced their largest GPU called the "Quadro GV100", which is supposedly $9,000!

There is so much to explain, and I will do my best to elaborate as I am learning this amazing topic! 

Here is a link to "How Nvidia’s RTX Real-Time Ray Tracing Works", which provides a really cool demo video for the upcoming game Metro: Exodus in 2019. I'll post the Metro video and a couple of video demos below too! 

 

How Nvidia's RTX Real-Time Ray Tracing Works

https://www.extremetech.com/extreme/266600-nvidias-rtx-promises-real-time-ray-tracing