Sebastian Lague A* Tutorial Series – Algorithm Explanation – Pt. 01

November 20, 2019

A* Tutorial Series

Pt. 01 – Algorithm Explanation

A* Pathfinding (E01: algorithm explanation)

Link – Tutorial

By: Sebastian Lague


Notes:

G cost = distance from starting node H cost (heuristic) = distance from the end node F cost = G cost + H cost

A* starts by creating a grid of an area. There is a starting node (initial position) and an end node (destination). Generally, you can move orthogonally (which is normalized as a distance of 1) or diagonally (which would then be a value of sqrt of 2, which is approx. 1.4). Just to make it look nicer and easier to read, it is standard to multiply these distances by 10 so that moving orthogonally has a value of 10, and diagonally has a value of 14.

The A* algorithm starts by generating the G cost and H cost of all 8 squares around the starting point (in a 2D example for ease of understanding). These are then used to calculate the F cost for each square. It starts by searching for the lowest F cost and then expanding the calculations to every square in contact with it (orthogonally and diagonally). Recalculations may be necessary if a certain path finds a way to reach the same square with a lower F cost. If multiple squares have the same F cost, it prioritizes the one with the lowest H cost (closest to the end node). And if there is still a tie, it basically can just pick one at random.

It is worth reiterating that the costs of a square can be updated through a single pathfinding event. This however only occurs, if the resulting F cost would be lower than what is already found in that square. This is actually very important as the search can lead to strange paths to certain squares giving them higher F costs than they should have when there is a much more direct way to reach that same square from the starting node.

Coding Approach

Psuedo Code (directly from tutorial):
OPEN //the set of nodes to be evaluated
CLOSED //the set of nodes already evaluated
add the start node to OPEN

loop
current = node in OPEN with the lowest f_cost
remove current from OPEN
add current to CLOSED

if current is the target node //path has been found
return

foreach neighbour of the current node
if neighbour is not traversable OR neighbour is in CLOSED
skip to the next neighbour

if new path to neighbour is shorter OR neighbour is not in OPEN
set f_cost of neighbour
set parent of neighbour to current
if neighbour is not in OPEN
add neighbour to OPEN

There are two lists of nodes: OPEN and CLOSED. The OPEN list are those nodes selected to be evaluated, and the CLOSED list are nodes that have already been evaluated. It starts by finding the node in the OPEN list with the lowest F cost. They then move this node from the OPEN list to the CLOSED list.

If that current node is the target node, it can be assumed the path has been determined so it can end right there. Otherwise, it checks each neighbour of the current node. If that neighbour is not traversable (an obstacle) or it is in the CLOSED list, it just skips to check the next neighbour.

Once it finds a neighbour to check, it checks that it is either not in the OPEN list (so this neighbour is a completely unchecked node since it is in no list since we also just checked to make sure it was not in the CLOSED list) or there is a new path to this neighbour that is shorter (which is done by calculating the current F cost of that neighbour, since it could be different now). If either of these are met it sets the calculated F cost as the actual F cost of this neighbour (since it is either lower or has never been calculated), and then sets the current node as a parent of this neighbour node. Finally, if neighbour was not in the OPEN list, it is added to the OPEN list.

Setting the current node as the parent of the neighbour in the last part of the psuedo code is helpful for keeping track of the full path. This gives some indication of where a node “came from”, so that when you reach the end you have some reference of which nodes to traverse.

UnityLearn – Beginner Programming – Finite State Machine – Pt. 02 – Finite State Machines

Novemeber 18, 2019

Beginner Programming: Unity Game Dev Courses

Beginner Programming: Unity Game Dev Courses

Unity Learn Course – Beginner Programming

Finite State Machines

Building the Machine

This part of the tutorial has a lot more hands on parts, so I skip some of the sections for note purposes when there is not much substance to them other than following inputs.

A key in finite state machines is that an object can only ever be in exactly one state at a time. This helps ensure each state be completely self contained.

Elements of a Finite State Machine:
Context: maintains an instance of a concrete state as the current state
Abstract State: defines an interface which encapsulates behaviors common to all concrete states
Concrete State: implements behaviors specific to a particular state of context

To get started in the tutorial, they created a public abstract class PlayerBaseState which will be the abstract state for this example. PlayerController_FSM is the context. They note that while in this case all the abstract state methods take the PlayerController_FSM (the context) in as a parameter in this case, that does not necessarily have to be the case for the general FSM pattern.

Concrete States

It is noted that the context in a FSM needs to hold a reference to a concrete state as the current state. This is done in the example by creating a variable which holds that of the type that is our abstract state, which is PlayerBaseState in this case. They then create a method called TransitionToState which takes a PlayerBaseState in as a parameter. It then sets the currentState to that parameter state, and then calls the new state’s EnterState method (all states have this method as it is dictated by the abstract class they all implement). This determines what actions should be done immediately upon entering this new state.

Example:

public void TransitionToState(PlayerBaseState state)
{
currentState = state;
currentState.EnterState(this);
}

The tutorial also shows a way to take control of the context’s general Unity methods and pass the work on to the concrete states instead. This example did this with Update and OnCollisionEnter. The abstract state, and in turn, all of the concrete states, have their own Update and OnCollisionEnter method. The context, PlayerController_FSM, then simply calls currentState.Update(this) in its Update method, and currentState.OnCollisionEnter(this) in its OnCollisionEnter method, so that the current concrete state’s logic for these methods are used without flooding the context itself with any more code.

Since it is necessary that your context has some initial state, they do this by simply calling the TransitionToState method within the Start method and entering the IdleState. IdleState is the initial state for this case.

Beginning the Implementation

Important benefits seen using this system:
While working on the concrete classes themselves, we never needed to go back to the PlayerController_FSM class (the context) to modify any code there. The entire behvior is handled within the concrete states and is abstracted from the character controller (the context). Setting expressions was much easier as no checks are needed and this can just be set in the EnterState method of each concrete state.

It is already clear that this method removes a lot of boolean checks from the overall code, and helps organize the code by ensuring any logic about a state is contained within the class for that state itself (with less bleeding into the code of other states).

Continuing the Implementation

It is worth noting that PlayerController_FSM holds a reference to every concrete state except the spinning state. This was done because they actually have the jumping state create a new spinning state on transition each time it is invoked. They apparently do this so that the local field for rotation within the spinning state is reset to 0 each time it is called, but it seems like there would be other ways to do this that seem less wasteful (such as resetting it to 0 when exiting the state). I am also not sure if this is intended behavior, but the spin also immediately cancels upon contacting the ground (resetting the player rotation to 0) with this setup, where as in the previous behavioral setup the spin completed even if the player contacted the ground.

Module Conclusion

Benefits of FSM:

  • More modular
  • Easier to read and maintain
  • Less difficult to debug
  • More extensible

Cons of FSM:

  • Take time to setup initially
  • More moving parts
  • Potentially less performant

Just something very notable with this approach, it seems much harder for me to break than the naive implementation. If I spammed key presses (like pressing jump and duck a lot) with the naive approach, sometimes I could break the system and have the player stuck in the duck position or be ducking while jumping. I have not been able to break it at all with the full FSM setup, which makes sense since transition behaviors solely exist within the states themselves so these inputs cannot be jumbled in any way.

SUMMARY

Using state machine systems appear way easier to use and build on than the “naive” approach of basic boolean behaviors (with lots of if statements and boolean checks). Not only was I very excited about how much easier this appears to work as a scalable option, it also just worked better and more cleanly when it was all put together.

The other version had small bugs that would pop up if you spammed all the different action keys (such as getting stuck ducking or being ducked in a jump), which were possible just because the key presses would get recorded before reaching the bools or if statements that should be telling them that they are not proper options. These very separated states make that type of error impossible as it is only concerned with a single state at a time.

This type of system just seems much cleaner, more organized, and less error prone than what I have done before and I am very excited to try and build a system like this for my own project (for both players and enemy AI).

UnityLearn – Beginner Programming – Finite State Machine – Pt. 01 – Managing State

Novemeber 15, 2019

Beginner Programming: Unity Game Dev Courses

Beginner Programming: Unity Game Dev Courses

Unity Learn Course – Beginner Programming

Managing State

Project Overview

This part of the tutorial has a lot more hands on parts, so I skip some of the sections for note purposes when there is not much substance to them other than following inputs.

The basics covered in this section are:
What is state and how to manage it
Finite State Machine pattern
Build your own finite state machine

Introduction

State: condition of something variable
State Examples: Game state, Player state, NPC State

Finite State Machine: abstract machine that can be in exactly one of a finite number of states at any given time

Parts of a Finite State Machine:
  • List of possible states
  • Conditions for transitioning between those states
  • State its in when initialized (initial state)

Naive Approach to Managing State

This naive approach focuses on boolean states and if staements. It uses a lot of if and else if statements in the Update method to determine what state the player is in and if/when/how they can switch to another state. Even with two states this becomes tedious and somewhat difficult to read. This example is just to emphasize the use of proper finite state machines.

Actions, Triggers, & Conditions

Look at your actions as a set of: actions, triggers, conditions.
Example for Arthur jumping:

  • Actions: Arthur jumps; jumping expression
  • Triggers: Spacebar is pressed
  • Conditions: Arthur is not jumping

Continuing to follow the naive state management approach, we see that everytime we add a new state it makes all snippets about other states more complex and harder to follow. This is very clear that this will become unmanagealbe with only a few states even.

Module Overview

The biggest issue with the naive approach is the interdependent logic of the various states. It makes each state exponentially harder to work with with every state that is added, so it is very limited on its scalability. This does not even come with a benefit to readability, as it also becomes difficult to read quickly.

SUMMARY

Using the naive approach (boolean fields and if/else statements) to manage state is only really useable for extremely simple cases. As soon as you reach 3 or 4 states with even small amounts of logic to manage them, this approach becomes very awkward and unwieldy. Fininte State Machines should hopefully open up a better way to manage more states with better scalability and allow for more complexity with better readability.

Programming A* in Unity

November 14, 2019

A* Programming

Unity

A* Pathfinding (E01: algorithm explanation)

Tutorial #1 – Link

By: Sebastian Lague


Unity – A Star Pathfinding Tutorial

Tutorial #2 – Link

By: Daniel


Unity3D – How to Code Astar A*

Tutorial #3 – Link

By: Coding With Unity


I have used A* before, but I would like to learn how to setup my own system using it so that I can make my own alterations to it. I would like to explore some of the AI methods and techniques I have discovered in my AI class and use that to alter a foundational pathfinding system built with A* to come up with some interesting ways to influence pathfinding in games. I would eventually like to have the AI “learn” from the player’s patterns in some way to influenece their overall “A* type” pathfinding to find different ways to approach or avoid the player.

Classes of AI Agents

October 10, 2019

General AI

Classes of AI Agents

Agents in Artificial Intelligence

Info #1 – Link

By: Sahil_Bansall


Classes of Agents

This link goes over some of the basic setups for a few different classes of AI, which are as follows:

  • Simple Reflex Agents
  • Model-Based Reflex Agents
  • Goal-Based Agents
  • Utility-Based Agents
  • Learning Agent
Simple Reflex Agents

These agents simply react to the current percept, with no regard to percept history. It uses condition-action rules, which simply map a state/condition to an action. So these take in some input with sensors of some type, and then depending on solely that input, it decides an action to take at that time.

Model-based Reflex Agents

These find a rule whose condition matches the current situation. This agent adds an internal state, which is updated with each percept depending on the percept history. This internal state allows the agent to create its own model of the world that cannot be perceived. This agent updates its state with information on how the world evolves independently from the agent, and how the agent actions affect the world.

This type of agent starts to work well with a partially observable environment, since it can make its own “guess” at the full world by making its own models.

Goal-based Agents

These agents make decisions to reach a goal (desired situations). Every action they take gets them closer to the goal. This generally involves using searching and planning.

Utility-based Agents

These agents base actions of preference (utility). How “happy” an agent is is sometimes used to describe its utility. These use utility functions to map a state to a real number which can evaluate what action will make it most happy.

Learning Agent

This type of agent starts with a basic knowledge but then acts and adapts through learning. This learning is done through the use of 4 key conceptual components:

  • Learning Elements: makes improvements by learning from environment
  • Critic: Gives feedback to learning element to inform agent how well it is doing relative to a fixed performance standard
  • Performance Element: selects action
  • Problem Generator: suggests actions that will lead to new and informative experiences

ARTIFICIAL INTELLIGENCE FOR GAMES – by Ian Millington, John Funge

October 1, 2019

Book

ARTIFICIAL INTELLIGENCE FOR GAMES

By: Ian Millington, John Funge

This was just an interesting reading I came across for a gaming AI class, so I wanted to note it for the future. It looks like it covers a lot of interesting topics so it could serve as a nice foundation for starting to understand a lot of the basics on gaming AI.

AI State Machine Tutorials: Tutorial #2

September 25, 2019

Tutorial #2

From Blog Post: Unity Basic AI State Machine Tutorials

Youtube – Unity 3D – Make a Basic AI State Machine

Tutorial #2

By: Joey The Lantern


General Structure

There is a general state machine class, a class for each individual state, and then the class for whatever will be using these states. This format is very similar to the first AI state machine tutorial I followed by UnityCollege3D.

State Machine

They created a new namespace, StateStuff. This was because they did not want anything to be a monobehaviour. This namespace then holds the StateMachine class as well as a public abstract class State. They mention that could be used in place of to allow you to specify what types can use this class, but they went with because it’s more ambiguous and works with more things. This is something I will need to look into, but I am guessing at this point T just means any type. So basically anything can use the StateMachine.

The state machine class was given two variables, State currentState and T Owner. These are both set in a constructor for StateMachine. Owner is what will be using the state machine, and currentState is obviously what state it is currently in.

State Class (within StateMachine script)

There were several abstract methods created for this class. These were: EnterState, ExitState, and UpdateState. EnterState allows you to perform actions immediately upon entering a new state, ExitState performs actions necessary when leaving a state for another, and UpdateState performs the various update actions for that state on that object.

FirstState

This class inherits the State class in the StateStuff namespace. The State here takes in an AI reference (again, I need to look into this more to see what this is actually doing). I see what this is doing better after implementing the abstract class. The type that is passed into State is then the type required by all of the methods that take in a parameter of type T. So since we declared State, now all of the methods require an input of AI _owner (translated from T _owner).

Their general idea is that there is only one instance of each independent state class, and every object that wants to use this state will just reference this same single instance. Following that, they use a bit more of an involved singleton-looking pattern to create this. The setup is the following:
public class FirstState : State
{
private static FirstState _instance;

private FirstState()
{
if (_instance != null)
return;

_instance = this;
}

public static FirstState Instance
{
get
{
if(_instance == null)
{
new FirstState();
}

return _instance;
}
}
}

The second state is exactly the same as the first, it just changes some of the text around so that it matches the new class name.

AI Class

This class represents the main script that would be running on your object that you would like to be using AI. To show the state machine working with it, it simply has a timer in the Update method that changes a bool.

GENERAL FLOW

There is one StateMachine instance and one instance of each individual state class. Each state has an UpdateState method, which generally corresponds with what an object in that state should be doing with an Update method. This is actually called through the StateMachine’s Update method though for every object.

The class which you want to use with the StateMachine and various States (AI in this example) must first reference the StateMachine and pass itself in as a paramter. Then it just needs to make sure to call stateMachine.Update within its own Update method. This is what allows everything to communicate what an object using this state machine should actually do in that state.

Finally, each individual state class is responsible for determing when to change to a new state, and what that new state should be. This is however performed by using the ChangeState method found within the StateMachine class. This method is responsible for calling the ExitState method from the old class, and the EnterState method from the new class.

FINAL NOTES

This setup uses a single instance of a state machine and a single instance for each state, which can be a nice avenue to take since it can really keep things scaled down that way. It also seems nice that the classes simply using this StateMachine setup mostly just need to call the StateMachine’s Update method to really interact with it. It helps keeps them from getting messy with state machine code. It does seem like it could be a bit tricky making sure the individual states themselves have proper references to check within the AI classes to figure out when they should change states with this approach.

AI State Machine Tutorials: Tutorial #3

September 25, 2019

Tutorial #3

From Blog Post: Unity Basic AI State Machine Tutorials

Youtube – ADVANCED AI IN UNITY (Made EASY) – STATE MACHINE BEHAVIORS

Tutorial #3

By: Blackthornprod


NOTES

This tutorial actually dealt with using the Unity Animator to create a sort of state machine setup. You can add behaviours to animation states, which are already setup in a very similar way to the last AI State Machine tutorial I did from Joey the Lantern (Tutorial #2 in this recent tutorial list).

These behaviours already have methods such as OnStateEnter, OnStateExit and OnStateUpdate (as well as several other more animation focused methods). This tutorial uses these to setup the logic for their state machine.

While this seems nice for getting something running very quickly, especially from an animation focused perspective, I think I would rather use the setups from the other tutorials that start more from scratch and allow you to develop the full system yourself. I would much rather follow Tutorial #1 and Tutorial #2 than this one.

Unity AI with Basic State Machine

September 24, 2019

Basic State Machine Setup

Unity Tutorial

Youtube – Unity3D AI with State Machine (FSM), Drones, and Lasers!

Tutorial #1

By: Unity3d College


Tutorial #1

This tutorial goes over a “good” version and a “bad” version of setting up state machines. The bad version will work, and is ok for very small scale projects and objects, but it does lack scalability and has some poor design choices going on.

The real state machine covered in this tutorial is not a monobehaviour, but is still able to access components of objects. This was a point they wanted to make sure they covered with the laser object reference.

To start going over the state machine, they go through the Drone class and its variables. Target is a public Transform but has a private setter. The Team variable Team uses an expression body property to allow the setting of team from the inspector without letting anything else change it.

The next class they go over is the StateMachine class. This starts with a dictionary that contains all of the possible states. It takes in a Type and a BaseState value. The Type is just type of the state class, and the BaseState is a new object of that specific state.

The Update method of StateMachine first checks if there’s a current state. If there is none, it sets a default state. It then performs a method called Tick to determine what the next state is (if it is either the same state again, or a new state). It then checks if the nextState is a different state, and if so, switches to the new state.

Each state has had its own class created, each of which inherits from a public abstract class called BaseState. None of these are monobehaviours, but you can still pass in a GameObject object through any state which gets set to a GameObject variable in the BaseState so the states know which object to control. This BaseState also uses protected variables so that classes that inherit from it may use them, without allowing anything else to access them. And finally, BaseState has a public abstract Type Tick method just to make sure every state class has a Tick method (actions to have an object perform in this state).

While checking through the individual state classes, they mentioned the use of nullables. You can add a “?” to the end of a variable declaration to make it nullable. This allows you to set that variable to null when you normally cannot. They like to do this just as a consistent way to help them check if something actually has had a value assigned to it or not.
Example:
private Vector3? _destination;

They also setup a GameSettings class to help them change general variables that go along with their state machine. This uses a simple singleton pattern setup like the following example:

public static GameSettings Instance { get; private set; }

private void Awake() {
if (Instance != null}
Destroy(gameObject);
else
Instance = this;
}

Unity Basic AI State Machine Tutorials

September 23, 2019

Basic AI State Machines

Unity Tutorials

Youtube – Unity3D AI with State Machine (FSM), Drones, and Lasers!

Tutorial #1

By: Unity3d College


Youtube – Unity 3D – Make a Basic AI State Machine

Tutorial #2

By: Joey The Lantern


Youtube – ADVANCED AI IN UNITY (Made EASY) – STATE MACHINE BEHAVIORS

Tutorial #3

By: Blackthornprod


State machine is just a term I have come across when researching and working with AI projects, so I wanted to delve into it a bit more to understand it better. It is my hope that this will be useful as both game design experience as well as general programming experience. These tutorials I grabbed are mostly from well know Unity devolepers that put out generally good learning content, especially when it comes to the programming side.

I am also looking to take a general AI course and do some more advanced AI work in my thesis, so it makese sense to start finding some more interesting or well defined AI systems and learn how they are made. These tutorials are relatively all on the shorter end as well, so should be easy to knock them all out in a single session.