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 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_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 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 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

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

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!

How Music was Made for the Super Nintendo

For all you Nintendo fans out there, I found this really interesting video on how they made music with the Super Nintendo! It amazes me how game developers had to produce music with a chip that could only contain 64 kb of memory! Such games that were made with the SNES were Super Mario World, Final Fantasy VI, and Castlevania IV.

I’d definitely check it out, especially if you are one of those nostalgic gamers that dig these beats!

The Build Engine: Part 2

I know it has been a while! I was really sick this whole past week, and I had a ton of schoolwork!

Anyway, the Build Engine utilizes two forms of storage for creating maps: an array of sectors and an array of walls.

In the Build Engine, the current sector the players are in have to be tracked after updating their positions. This is achieved by calling the updatesector(int newX, int newY, int* lastKnownSectorID) function in the code. The algorithm written to do this behavior pattern is as specified below:

1. The algorithm starts by assuming the player hasn’t moved much within the last update and will try and utilize the lastKnownSectorID to see if the player is in the last known sector.

2. If the algorithm fails to find the player in the last known Sector, it will check the neighboring sectors of the last known Sector by utilizing its portals.

3. If it fails to find the player in the neighboring sectors, then the algorithm will linearly search all of the sectors.

I think Fabien Sanglard’s website best explains this idea with the following picture

Retrieved from http://fabiensanglard.net/duke3d/build_engine_internals.php

The Build Engine: Part 1

Remember how the Doom Engine utilized Binary Space Partitioning to partition their maps? Well, the game Doom actually preprocessed and partitioned each map individually ahead of time with Binary Space Partitioning, which was a very time-consuming process at the time and even could take up to 30 minutes per map. However, Doom had the flexibility of sorting walls, determining the positions of sectors, and even collision detection. The walls in Doom could NOT move. 

However, Ken Silverman's Build engine removed this limitation of static walls by not implementing preprocessed maps. Build instead relies on what is known as a Portal System. Portal Systems are really useful and fast for eliminating regions of world geometry that are not within the player's view. The idea behind portal systems involves dividing the game world up into different zones that are connected by portals. Essentially, portals are represented by convex polygons from which one region (zone) of the world can be seen from another region (zone) of the world. Think of this as if you are standing in a room (a zone) and you are looking into the next room (another zone). The portals would be the doorways leading into the next rooms! Since game worlds can become massive, rendering the entire world all at once will really slow down your computer/device or possibly even crash them! However, since only certain regions of the world within the player's field of view need to be rendered, we can GREATLY speed up graphical processing and rendering! I'll provide a picture for extra clarification!

Portal System with Culling of regions to what is visible through the player's eyes. Everything that is white is not rendered!

Retrieved from https://www.panda3d.org/manual/index.php/Portal_Culling

Very detailed Portal System diagram., which is considered faster than BSP!

Retrieved from https://www.semanticscholar.org/paper/Portholes-and-planes%3A-faster-dynamic-evaluation-of-Roden-Parberry/54505db0eeab8b75a65d06818a295bd9b43172db

The Build Engine: A Very Brief Introduction

The Build Engine was created by Ken Silverman in the early to mid-1990s. The Build Engine was a huge step-up from the Doom Engine by providing many new features that were never seen before, such as destructible environments, sloped floors/ceilings, mirrors, looking up/down, flying/crouching/underwater, voxels and 3D immersion. However, the Build Engine is not a completely 3D game engine, since it utilized a 2D grid for world editing and added a height component for its sectors. This height component allowed each sector to have a different ceiling height and floor height! Floors and ceilings can hinge along one of the sector's walls to create slopes! Tomorrow I'll talk more about Build's Sectors and Portal System. I just wanted to quickly introduce this topic today since I've been busy setting up for school, hence the short posts recently!

Here is a video that overviews what the engine is capable of!

NOTE: The quality is low on this video though.

Learning to Create Video Games Helps STEM Skills

Before I begin discussing the Build Engine (tomorrow), I wanted to share an interesting article I found on how learning to create video games can help the younger generation, including underrepresented groups such as women and other minorities, improve their STEM skills. Not to mention, these underrepresented groups in STEM can be used to change game character stereotypes and also can be used to change the perceptions of the gaming industry in general. In case you don't know, STEM stands for Science, Technology, Engineering and Mathematics. This article suggests that creating games allows children to utilize their creativity and artistic talents as well as learn how to collaborate effectively with other people in their future fields! Game design has been known to help children learn mathematical skills in topics like variables, graphing, and fractions. It seems like teaching programming skills and other computer capabilities from environments like Scratch, Kodu, or Alice can be beneficial for cognitive thinking. Check it out!

http://stemchallenge.org/about/why-games/

The Doom Game Engine: Part 4

The Doom engine renders walls by utilizing its Binary Space Partitioning (BSP). The engine renders the walls by traversing the nodes (which represent sectors/subsectors) in the Binary Tree, which draws these subsectors by order of distance from the camera; this means the closest segs (line segments of a wall) are drawn first. As segs are drawn, they are stored in a Linked List data structure. The Linked List is used to clip other segs AND the edges of sprites rendered later on. To reduce the burden on the engine's performance, there is a static limit of 256 segs that may be rendered at once. The excess segs are NOT drawn, leaving visible gaps where walls should be. However, because of the order in which segs are drawn, the gaps are out in the distance where they are less noticeable.

When the engine reaches a solid (one-sided) wall at a particular X coordinate, no more lines are drawn in that area. As this occurs, the engine creates a blueprint (or map) of the areas of the screen where solid walls have been reached. This implies that areas which are currently invisible to the player are clipped completely. Essentially this means that whatever the player is not looking at in the engine is NOT being rendered!

Wall textures are stored as a bunch of vertical columns, which is useful to the renderer since it can render walls by drawing many vertical columns of textures. Since all the walls in the doom engine are drawn vertically, the player cannot look up or down realistically. It is possible to approximate looking up and down via "Y-shearing." Y-Shearing works by increasing the vertical resolution and then imagining a "viewing window" on that space. One can imagine the scene being rendered as a very tall image, in which a sliding window represents the player's view. Sliding the window upwards corresponds to looking upwards, and sliding the window downwards correspond to looking downwards. As the window moves up or down, it creates the illusion that the player is looking up or down. The view tends to become more distorted as the player looks further away from the horizon line.

http://doom.wikia.com/wiki/Doom_rendering_engine

Y-Shearing image representation

The Doom Game Engine: Intermission

Intermission time!

Here are some cool videos that discuss Doom 1 and its BSP system! These videos explain BSP pretty good!

The Doom Game Engine Part 3

Doom makes use of a system known as Binary Space Partitioning (BSP). Binary space partitioning (BSP) is a technique used for recursively subdividing a space into convex shapes by utilizing mathematical hyperplanes. This process can take quite some time for a large level. Because of BSP, it is not possible to move the walls in the Doom Engine. 

Each level is divided up into a data structure known as a Binary Tree. Each location in the Binary Tree is called a "node", where each node in the Doom Engine represents a certain area/region of the level. The root node (which is the first node at the top of the tree from which every other node originates) represents the entire level. At each branch of the tree there is a dividing line which divides the area of the node into two subnodes. This dividing line also divides linedefs into line segments called "segs".

The leaves of the tree (the bottom-most nodes with no children nodes) are convex polygons. These convex polygons are referred to as subsectors (or "SSECTORS"), and these subsectors are bound to a specific sector. Each subsector has a list of line segments (segs) associated with it.

The BSP system sorts the subsectors into the correct rendering order by using an algorithm as stated:

1. Begin at the root node.

2. Draw the child nodes of this node recursively. The child node closest to the camera is drawn first using a Scanline algorithm. The Scanline algorithm works like this according to Wikipedia: "All of the polygons to be rendered are first sorted by the top y-coordinate at which they first appear. Then each row or scan line of the image is computed using the intersection of a scanline with the polygons on the front of the sorted list. This happens while the sorted list is updated to discard no-longer-visible polygons as the current scan line progresses down the picture."

3. Once a subsector has been found, draw it.

The process is complete when the whole column of pixels is filled (i.e., there are no more gaps left). This ordering ensures that objects that are not visible aren't drawn or rendered; this allows maps to become very large without much performance loss!

https://en.wikipedia.org/wiki/Scanline_rendering

https://en.wikipedia.org/wiki/Binary_space_partitioning

Binary Tree Data Structure

Scan-line algorithm example retrieved from https://en.wikipedia.org/wiki/Scanline_rendering#/media/File:Scan-line_algorithm.svg

The Doom Game Engine Part 2

Over this last weekend, I was moving into my new college apartment, so I was SUPER busy! 

But today is Doom Engine part 2! 

The level editor in the game engine consisted of basic objects, such as vertices to represent single 2D points in space. These vertices can be joined together to create lines, which are known as "linedefs" in the engine. Each of these "linedefs" could have either one or two sides, known as "sidedefs." The editor could group these sidedefs together to create 2D polygons, and the polygons in the game engine are called sectors, which represent certain areas/rooms in a given level. One-sided linedefs represent a solid wall in the engine, while two-sided linedefs represent connections between two different sectors. Sidedefs are used to store wall textures, which are completely separate from the floor texture and ceiling texture.  

Every sector has a certain number of properties:

• a floor height,

• a ceiling height,

• a light level,

• a floor texture,

• and a ceiling texture.

What's interesting is that each sector only has ONE light level, so if you want to change the level of the lighting, you'd have to create a whole new sector and alter the light level of that sector! Sidedefs are used to store wall textures, which are completely separate from the floor texture and ceiling texture. Each sidedef can have up to 3 textures: the lower, middle and upper textures. With one-sided linedefs (i.e. solid walls), it is only possible to use the middle texture for the entire wall! But with two-sided linedefs (i.e. connections between sectors), the lower and upper textures are used to fill the gaps where adjacent sectors have different floor and ceiling heights. For example, the lower textures would be used to represent stairs. Most sidedefs don't utilize the middle texture often, even though they technically could. However, the middle texture is only really useful for hanging textures in mid-air. An example of a middle texture would be a transparent bar texture that appears to form a cage on a two-sided linedef!