Wednesday 22 August 2012

Circular Progress/Loading Bars

Progress bars are a common feature in game UI design when representing mechanics such as character interaction, weapon reloading, power meters, etc. A circular progress bar is simply one that fills/empties radially rather than linearly. They have become more popular recently as they are more appealing to the eye than the traditional straight progress bar.

In this blog post, we'll be examining the techniques one could use for designing a circular progress bar as well as their advantages and disadvantages.

Sprite Animations

Sprite animations follow a common game designer philosphy that it's easier to simply display a sequence of images rather than individually updating segments in the game code. The idea is that each image in the series shows the bar more filled than the last, such that when showed in sequence, it appears that the bar is filling. This is an extremely popular approach when creating the activity symbol on loading pages as it requires very little processing power.
Left 4 Dead 2Ghost Recon Future Soldier
The main disadvantage of this implementation is that, unless you use a very large spritesheet, the animation can end up choppy or blocky in nature. For example, in the Left 4 Dead 2 progress bar (pictured above) there are 10 very clear phases (or frames) to the animation, causing a jerky, unsmooth motion. For the purposes of a simple activity bar though, these forms of animations will suffice.

Likewise for interaction progress bars, the size of the spritesheet affects the performance. If you use a minimal spritesheet then the bar will appear choppy for longer interaction times but take up less memory, where as if you use a large spritesheet then the bar will appear smoother but take up more memory.

Primitive Manipulation

This approach still uses a sprite but only consisting of one frame, the completed circle, to avoid having to manually render one. The idea is that we divide the rendering of the sprite into several primitives and manipulate those to create the filling effect.


As you can see, we divide the top section into two (sections 0 and 4) to create a circle/bar which fills starting from the top. From here, we want to gradually expand each of the primitives in a clockwise motion to create the effect of the circle/bar filling.

To get a basic idea of how drawing using primitives works, see Microsoft's Using a Basic Effect with Texturing tutorial. The only difference is that we also use a Centre and UpperCentre position for the top 2 triangles and we will be drawing 5 primitives instead of just 2.

Initialisation

To start with, we first need to calculate how full the circle should be. Assuming that your progress bar has properties for the current, min and max values, the implementation for such might look like this:
float percent = (Value - MinValue) / (MaxValue - MinValue);
Next, we need to determine the index of the primitive we're going to manipulate. First, we want a number between 0 and 4, so we multiply our previously calculated percentage by 4 to get this range.

However, we have a problem in that the transition points (where the ouput changes from 0.99 to 1, for example) are at 0.25, 0.5, 0.75 and 1, which is not right. As such, we need to shift the result by adding 0.5 to get the output we want. Now if we input 0.25, we get a result of 1.5 (halfway through the second segment), which is perfect.
int index = (int)((percent * 4) + 0.5f);

Vertex Calculation

Now we need to calculate the vertex position for the primitive we are adjusting. If we convert the percentage value to an angle between 0 and 2π radians, we can construct a unit vector pointing from the centre of the circle to the vertex position.

To do this we apply a similar methodology as before (value between 0 and 2π radians, offset to start at the top of the circle) to calculate this angle and then construct the vector.
float angle = (percent * MathHelper.TwoPi) - MathHelper.PiOver2;
Vector2 angleVector = new Vector2((float)Math.Cos(angle),
    (float)Math.Sin(angle));
Next, we need to determine a scalar for this unit vector to get the vertex position on the edge of the sprite. This is calculated by comparing the scalars of the X and Y components to get the smallest value (the one which will intersect the edge first).

The reason we use Math.Abs(), or the absolute value, is so that the direction of the unit vector is preserved. The absolute value of a number is the weight or magnitude, i.e. the absolute value of 2 is 2 but the absolute value of -2 is also 2. If we simply used the signed value, we would sometimes get a negative scalar which would create a vector pointing in the opposite direction.
if (Math.Abs((effect.Texture.Width / 2) / angleVector.X)
    < Math.Abs((effect.Texture.Height / 2) / angleVector.Y))
{
    scalar = Math.Abs((effect.Texture.Width / 2) / angleVector.X);
    textureScalar = Math.Abs(0.5f / angleVector.X);
}
else
{
    scalar = Math.Abs((effect.Texture.Height / 2) / angleVector.Y);
    textureScalar = Math.Abs(0.5f / angleVector.Y);
}

Adjusting Vertices

Finally, we adjust the appropriate vertex before rendering the primitives. To start with, we reinitialise the vertex positions and texture coordinates to reset any previous adjustments we may have made. Then we simply change the appropriate vertex using the unit vector and scalars we previously calculated.

The reason I use index + 1 is because we want to adjust the right edge vertex when filling the circle clockwise, not the left. Since my vertices are defined in a clockwise pattern (where the last vertex is the centre), I simply add 1 to my previously calculated primitive index to get the right edge vertex.
vertices[index + 1].Position = Centre
    + new Vector3(angleVector.X * scalar, -angleVector.Y * scalar, 0);
vertices[index + 1].TextureCoordinate = new Vector2(0.5f, 0.5f)
    + (angleVector * textureScalar);
Finally, we render the primitives using GraphicsDevice.DrawUserIndexedPrimitives(). Remember to use index to specificy how many primitives we want to draw. In the case of filling a circle, this is simply index + 1.
foreach (EffectPass pass in effect.CurrentTechnique.Passes)
{
    pass.Apply();

    effect.GraphicsDevice.DrawUserIndexedPrimitives
        <VertexPositionNormalTexture>(PrimitiveType.TriangleList,
        vertices, 0, 7, indexes, 0, index + 1);
}

Unfilling a Circle

Unfilling a circle only involves some minor tweaking to the final section. First, you adjust the left vertex instead of the right, which in the above example only means replacing index + 1 with index.

Then you modify the draw code to start on the appropriate primitive, represented by the fifth argument, and to draw less primitives as index increases, the last argument.
vertices[index].Position = Centre
    + new Vector3(angleVector.X * scalar, -angleVector.Y * scalar, 0);
vertices[index].TextureCoordinate = new Vector2(0.5f, 0.5f)
    + (angleVector * textureScalar);

foreach (EffectPass pass in effect.CurrentTechnique.Passes)
{
    pass.Apply();

    effect.GraphicsDevice.DrawUserIndexedPrimitives
        <VertexPositionNormalTexture>(PrimitiveType.TriangleList,
        vertices, 0, 7, indexes, index * 3, 5 - index);
}

Friday 10 August 2012

Finite State Machines (FSM)

What is a State Machine?

Generally, a state machine is a model for logic systems. It takes the form of an abstract "machine" which can be in one of many different "states". The machine can "transition" between states given some condition has been met.

As an example, a light switch can be modelled using a very basic state machine. It has two states, on and off. If the current state is 'on' and the switch gets toggled then the machine transitions to the 'off' state and vice versa if the current state is 'off'.

How do they apply to games development?

When coding AI (artificial intelligence) for characters, state machines are one of the most common tools in the programmer's arsenal. They provide an intuitive, easy to debug means for creating the various AI behaviours for a character. After all, it's very easy to imagine characters switching between clear behaviours (states), such as 'alerted', 'caution' and 'unaware' in a stealth game.

How could you implement them?

A naive approach would be to simply use a series of if/else statements or a switch structure. For anything more than the most rudimentary of AI behaviour though, this usually leads to messy code that's difficult to debug and hard to follow.
public void Update(GameTime gameTime)
{
    // Change states.
    if (PlayerVisible)
    {
        state = ChaseState;
    }
    else
    {
        // Decide if we should wander or idle.
        if (random.NextDouble() < 0.5)
        {
            state = WanderState;
        }
        else
        {
            state = IdleState;
        }
    }

    // State logic.
    switch (state)
    {
        case ChaseState:
            // Chase logic.
            break;

        case WanderState:
            // Wander logic.
            break;

        // Etc.
    }
}
In this blog post, I'll be discussing a more structured approach that I feel better compartmentalises AI behaviour and keeps the Update() logic easier to follow. It revolves around a central StateMachine class, which manages instances of various State classes.

State Base Class

The base state class will be used for all state behaviour and should declare all of the core functions for any state. For this purpose we'll use a main Update() method for processing logic and Enter() and Exit() methods for initialisation and tidying up when changing states.
abstract class State<T>
{
    public abstract void Update(T owner, GameTime gameTime);

    public abstract void Enter(T owner);
    public abstract void Exit(T owner);
}
We want the state class to be generic, such that it can be used for any character, however if we only use basic object arguments then we won't be able to access any of the class-specific properties and methods for any character. As such, we use the generic type T when declaring the class and functions so that regardless of which character we're creating behaviour for, we can access their properties.

The abstract keyword specifies that both the classes and methods should not be used directly, they must be inherited/overwritten. This concept is similar, though not identical, to the virtual keyword, which means the class/method can be inheritted/overwritten but is still able to be directly used.

StateMachine Class

The state machine class is the class that manages a character's state and should declare methods for the owner to update the state logic and for states to transition between each other. As such we have an Update() method, as well as a ChangeState() and RevertState() method.
class StateMachine<T>
{
    T owner;
    State<T> currentState;
    State<T> previousState;
    State<T> globalState;

    public State<T> CurrentState
    {
        get { return currentState; }
    }

    public State<T> GlobalState
    {
        get { return globalState; }
    }

    public State<T> PreviousState
    {
        get { return previousState; }
    }

    public StateMachine(T owner, State<T> global,
        State<T> current)
    {
        this.owner = owner;
        this.globalState = global;
        this.currentState = current;
        this.previousState = current;
    }

    public void Update(GameTime gameTime)
    {
        if (globalState != null)
        {
            globalState.Update(owner, gameTime);
        }

        if (currentState != null)
        {
            currentState.Update(owner, gameTime);
        }
    }

    public void ChangeState(State<T> newState)
    {
        if (newState == null)
        {
            return;
        }

        previousState = currentState;

        currentState.Exit(owner);

        currentState = newState;

        currentState.Enter(owner);
    }

    public void RevertState()
    {
        ChangeState(previousState);
    }
}
As before, we use generic type T when creating the state machine so that when states are updated, the correct class type can be passed as an argument. In addition, we also store and update a global state which can be used for passive behaviour which is not specific to one state. For example, we might have an enemy who should always change to a chasing state upon spotting the player.

Individual States

Individual states inherit from the base state class, where the desired class is passed in the angle brackets to incorporate the generic type functionality we previously discussed. All the abstract methods are also overriden using this class to access the owner's properties and methods when performing logic.
class EnemyIdleState : State<Enemy>
{
    // Constants/Readonly.
    private static readonly EnemyIdleState instance = new EnemyIdleState();
    const float rethinkTime = 5;

    public static State<Enemy> Instance
    {
        get { return instance; }
    }

    public override void Update(Enemy owner, GameTime gameTime)
    {
        owner.Rethink -= gameTime.ElapsedGameTime;

        if (owner.Rethink <= TimeSpan.Zero)
        {
            owner.StateMachine.ChangeState(EnemyThinkState.Instance);
        }
    }

    public override void Enter(Enemy owner)
    {
        owner.Rethink = TimeSpan.FromSeconds(rethinkTime);
    }

    public override void Exit(Enemy owner)
    {
    }
}
In addition, we also use a concept known as the singleton pattern to prevent multiple copies of identical states from being instanced. The idea is that the class holds an instance of itself, the singleton, which can be accessed using a static property. This way instead of passing new instances when changing states, the singleton can be passed using State.Instance, as seen on line 18.



The concepts discussed in this blogpost are covered in far more detail in Mat Buckland's Programming Game AI by Example book, along with many other AI techniques.