# Blend-spaces

A blend space is a concept used in animation scripting where several animations are asssigned a position on a graph, and one or more input parameters calculate what mix of which animations should be playing at the current moment.

Here we see an example of a One Dimensional blend space. Speed is controlling where the blend is calculated to be on the graph. The bottom node represents the idle animation, where speed is equal to zero. Above that are the Run, Walk and current blend position (in orange). A 2D blend space is exactly what it sounds like - many animations can be mapped onto a graph with two dimenstions rather than just one. A common example of this would be a characters base movement. Below we can see many different animations have been plotted on a graph representing direction along one axis, and speed along another. Using this the scripter is able to create a state for an animation state machine that takes into account these two inputs to play a blend that will see the character turning and running in the correct way. # Animation State Machines

This is one of several small posts that aim to give an overview of animation technology in current games, as part of an ongoing scripting tutorial series.

Animation state machines are a core concept used in modern computer games, and are a necessary component for us to understand and work with characters and scripted moments.

There are three main components that compose animation state machines

### States

These contain an animation. When a state is active, the character is playing this animation. You may be able to alter the way the animation plays, but nothing more.
The only caveat is that states can also contain blend-spaces, which we will cover in an upcoming blog post.

### Transitions

These are the links between states. They define which animations are allowed to blend between each other. For example, you may add transitions to allow a character to blend from Idle to Walking, but not straight from Idle to Running. ### Rules

These are the set of conditions that you write, that when met allow one state to travel through a transition to another state. They are heavily parameter driven - as an example, speed increasing may transition from the idle to a walking state. There are some more advanced elements to animations state machines, such as the way they handle additive animations, encapsulate other state machines and send messages based on their state. These will all be covered in the next blog posts.

# Djikstra and A* search algorithms

Since we covered navmeshes briefly, I also thought it would be good to provide a quick overview of the pathfinding algorithms that underpin them.

This knowledge will serve as a good jumping off point if you want to delve deeper, but can also be very useful in recognising what might be happening with an AI when they are not behaving as expected.

### Djikstra’s Algorithm

This is the most basic search algorithm that we would reasonably use in a 3D video game, and it is very closely related to A* search which is the industry standard algorithm, so it’s a good place to start.

The concept is very simple.

1. From your starting point you search every adjacent space and place them into a list representing the frontier of the search.
2. After all of the adjacents have been explored, you search the adjacents of the frontier nodes
3. You repeat this on and on and on, until you find the goal node
4. You then recurse back though the adjacencies until you have a path back to the start

### A* Algorithm

This is simply an optimisation of Djikstra. It uses a concept called a Heuristic - this is simply an estimation of how close each node is to the goal node. For this example we will use linear distance to the goal node (the most common heursitic).

1. From the starting point you look for the adjacent with the smallest heuristic value and place them into a list representing the frontier of the search
2. You then move onto the next node with the lowest heuristic cost
3. You continue to do this until you reach the goal node
4. You then recurse back though the nodes until you have a path back to the start

The difference here is that instead of searching all adjacencies before you expand the frontier, you are trying to guess which direction the search should go in to be successful faster.

Of course this isn’t always optimal, as shown in this example. however it’s an edge case and it still slightly more optimal that Djikstra seaching the same space.  # Navigation meshes explained

As a gameplay scripter we work a lot with AI, and so it’s important to understand the basics of how these systems are put together so we have a better understanding of how to work with them.

A little history

Historically AI navigation was handled with waypoint grids. They use a search algorithm to query the location of an AI and work out what order they need to travel between nodes to get to the desired location, resulting in a path they can follow.

This was fine for a long time, until someone came up with the concept of a navigation mesh. These have an enormous amount of advantages we'll cover briefly.

For pathfinding they actually work the same way as waypoint grids, only each point is associated with a convex polygon. An initial path is still calculated using the central points of each polygon. The difference is that the paths then go through two phases of optimisation.

The first is a culling phase, in which the grid works out if there are any unnecessary links. The path then runs a smoothing algorithm using the bounds of the polygons and a radius for the agent to set how extremely or subtly this path is smoothed. This gets rid of the strange zigzagging we used to see in games - the result of sticking to the links on a waypoint grid.

### Further notes

Just on their own this would be enough to use them over grids, but there are some added benefits that come with this implementation.

Path correction
AI can use the knowledge of polygon bounds to correct their paths around obstacles, as long as they can remain within the bound of the mesh. Smarter actions
The AI can make sure that they have enough space to complete an action, such as a dodge-roll, so that they avoid doing stupid looking things like rolling into a wall, or worse - rolling off an edge. Extensibility
Navmeshes allow for multiple agents with different navigation requirements, such as larger or smaller AI's, or AI's that have restrictions based on turning circles (things like planes, boats or vehicles), therefore allowing all of them to use one set of navigation data. # Delta time

The following is part of an ongoing series of basic tutorials for gameplay scripters.

Delta time is a simple but fundamental aspect of how we program in games.

Simply - delta time is the measure of how much time has passed between each frame. Updates aren't fixed (they can take different times to complete), because of this, if you are moving an object a fixed amount each frame, it will actually move at a variable speed.

What you really want is to be able to move something at a constant speed.

The solution is simple: We measure the amount of time passed in milliseconds since the last frame and we multiply it by our delta time.

This means that if a frame takes more time to complete, your object will move further to compensate.

SudoCode
object's position + increment * delta time

Unity C#
myObject.transform.position += myVectorOffset * Time.deltaTime;  # Scripting Handbook: Vectors

The following is part of an ongoing series of basic tutorials for gameplay scripters.

In maths a vector represents a line that has a direction and magnitude (length).

Programmatically a vector is a list of numbers, for our purposes we mostly use vectors that hold 2 or 3 numbers, with a so-called 2D vector holding two numbers, representing X and Y, while a 3D vector holds 3: X, Y and Z.

What this means practically, is that we often use vectors to hold a position in X, Y and Z. This however, is not traditionally what we mean when we’re talking about a mathematical vector. A true vector, the line with direction and magnitude, often represents a displacement - a set of instructions that describes how far and in what direction we should move.

How the data is stored does not change, whether we are storing a displacement or a position. If you look at the above image, you can see two quite different things. A point at 3, 2 and a 3, 2 vector. We would actually store these things in exactly the same way, it is our use of it that changes what that vector actually does.

It is also worth noting that a vector in programming languages simply refers to a one-dimensional array, (single list) or numbers. A vector as the concept we are talking about here, again just refers to how you use it.

You can see from this image a number of differences. A point does not store any kind of information about heading and has no length. A vector on the other hand, has no knowledge of where it is in the world, it simply represents a set of instructions on how to move from any point.

Vector Terminology Magnitude / Length - refers to the length of the vector from start point to end point.

### 2D Calculations

SudoCode

√ (x * x + y * y)

Unity C#
by accessing the magnitude variable in your vector -
`myVector.magnitude;`

### 3D Calculations

SudoCode

lengthOfAdjacentSide = √ ( (x * x + y * y) )

√ ( lengthOfAdjacentSide * lengthOfAdjacentSide + z * z) The picture above should help explain this sudocode. You are trying to work out the length of a 2D triangle described by the dashed lines. You know one size because it’s simply the Z value. The other side, the one marked adjacent, is actually the length of a 2D vector laid flat.

Unity C#

by accessing the magnitude variable in your vector
`myVector.magnitude;`

by calling a static function in the vector library
`Vector3.Magnitude( myVector );`

UE4 Blueprints 