Under Ludum Dare 31 I used the Piston/ai_behavior library first time “for real”. This is what I learned!

Four times a year there is a Ludum Dare competition, where you make a game within 48 hours. Here is a screenshot of the game I made, Sea Birds’ Breakfast:

The sea birds in these games are programmed by using something called “AI behavior trees”. While this sounds scary, it is actually easy to use.

A history of the AI behavior library

The project started out as an attempt by Coeuvre to model event logic using the observer pattern. This did not work very well with Rust’s borrow checker. Therefore, I took the features Coeuvre wanted, and built an expression tree around it. In that process I start to think of old problems I had with event programming.

In GUI programming for complex interfaces, one event might trigger another, which triggers the first one, and the entire program hangs. I wanted a way of programming event logic where you could see the infinite loops. As shown below it can still happen, but it is a lot easier to find out why.

What I did not expect to find, was a way to make building blocks of logic that runs forever. Those are not loops that causes the program to hang, but they never terminate in the logical sense. This is possible because it gets updated in incremental time steps. In normal programming you have to break out of infinite loops, but when you have parallel semantics, you can add the loop to another one that controls the flow from the outside.

Then I read an article about AI behavior trees, and found out that by combining failure tolerance and parallel semantics, we would cover both event logic and AI game logic. It was very time consuming to craft out the building blocks, but eventually it was done.

Then, after weeks of work, the problem was that nobody knew how to program with it!

Coeuvre started the sprite library, which is the first case of “real world” usage. It uses AI behavior trees to animate sprites, where the behavior is something you can “play” and “pause” etc.

How it looks like in code

Here is the constructor of SeaBirds:

impl SeaBirds {
    pub fn new() -> SeaBirds {
        use piston::ai_behavior::{ 
            While, Action, WaitForever, WhenAny, Wait, Sequence
        };

        let circling = Action(Action::Circling);
        let circle_until_player_within_distance =
            Sequence(vec![
                While(box Wait(5.0), vec![
                    circling.clone()
                ]),
                While(box Action(Action::PlayerWithinDistance(50.0)), vec![
                    circling.clone()
                ]),
            ]);
        let give_up_or_attack = WhenAny(vec![
            Action(Action::PlayerFarAwayFromTarget(100.0)),
            Sequence(vec![
                Action(Action::PlayerWithinDistance(10.0)),
                Action(Action::AttackPlayer(0.1)),
            ])
        ]);
        let attack_attempt =
            While(box give_up_or_attack, vec![
                Action(Action::FlyTowardPlayer)
            ]);
        let behavior = While(box WaitForever, vec![
            circle_until_player_within_distance,
            attack_attempt,
        ]);
        SeaBirds {
            birds: Vec::new(),
            behavior: behavior,
        }
    }
}

As you can see from the code, a behavior tree is constructed by putting together smaller blocks. There are blocks that come with the library, such as Wait(5.0) which means “wait 5 seconds”. The Action block is used to do custom behavior, for example, Action(Action::FlyTowardPlayer).

Each sea bird stores a “state” of the behavior:

pub struct SeaBird {
    pub pos: [f64, ..2],
    pub dir: [f64, ..2],
    pub target: [f64, ..2],
    pub circling_angle: f64,
    pub state: ai_behavior::State<Action, ()>,
}

The last part to make this work, is to describe how each action updates:

state.event(e, |_, dt, action, _| {
     match *action {
        Action::Circling => {
            let angle = *circling_angle;
            let angle_pos = add(*target, 
                scale([angle.cos(), angle.sin()], circling::RADIUS));
            *dir = normalized_sub(angle_pos, *pos);
            *pos = add(*pos, scale(*dir, dt * SPEEDUP * circling::SPEED));

            let diff = sub(angle_pos, *pos);
            let diff_len = len(diff);
            if diff_len < circling::ADVANCE_RADIUS {
                *circling_angle = angle + _360 / circling::N;
            }
            
            (ai_behavior::Running, 0.0)
        }
        Action::PlayerWithinDistance(dist) => {
            let diff = sub(*pos, player.pos);
            if len(diff) < dist {
                (ai_behavior::Success, dt)
            } else {
                (ai_behavior::Running, 0.0)
            }
        }
        Action::PlayerFarAwayFromTarget(dist) => {
            let diff = sub(*target, player.pos);
            if len(diff) > dist {
                (ai_behavior::Success, dt)
            } else {
                (ai_behavior::Running, 0.0)
            }
        }
        Action::FlyTowardPlayer => {
            *dir = normalized_sub(player.pos, *pos);
            *pos = add(*pos, scale(*dir, dt * SPEEDUP * circling::SPEED));
            (ai_behavior::Running, 0.0)
        }
        Action::AttackPlayer(val) => {
            player.state = player::State::Bitten(::settings::player::BITTEN_FADE_OUT_SECONDS);
            blood_bar::decrease(val);
            (ai_behavior::Success, dt)                    
        }
    }
});

Each action returns Success, Failure or Running and the number of seconds left of the update time delta. For example, FlyTowardPlayer never succeeds or fails, it always returns (ai_behavior::Running, 0.0). On the other hand, AttackPlayer returns immediately, so it does not “spend” any time by returning (ai_behavior::Success, dt).

Summary:

1. Create a behavior tree (how the sea birds behave)
2. Store a state per instance of the behavior (what the sea bird does in the moment)
3. Describe how custom actions gets executed (how the sea bird interacts with the world)

That is all you need to use the library, and once you get used to this setup, you can combine it with more powerful patterns.

A sea bird attacks

When a sea bird started attacking me, it suddenly hang the entire program. First I thought this was a bug in the AI library, but the logic flaw was in the sea bird behavior.

What I found out, is that there was no pause after attacking the player. The sea bird went immediately from attacking to checking the distance and then back to attacking. Because neither action consumes time, it ran in an infinite loop. The circling logic was as following:

let circle_until_player_within_distance =
    Sequence(vec![
        While(box Action(Action::PlayerWithinDistance(50.0)), vec![
            circling.clone()
        ]),
    ]);

I solved this by duplicating the circling loop and combining them with a sequence:

let circle_until_player_within_distance =
    Sequence(vec![
        While(box Wait(5.0), vec![
            circling.clone()
        ]),
        While(box Action(Action::PlayerWithinDistance(50.0)), vec![
            circling.clone()
        ]),
    ]);

The only difference between two loops is the condition. Now, after the sea bird attempted an attack, it waits 5 seconds before it can attempt another one.

Unlike a while-loop in “normal” programming, the body of the loop runs in parallel with the condition. It runs until the condition terminates or when the body fails. If the condition succeeds, then the entire loop succeeds, but if it fails or the body fails, then the entire loop fails.

It is also possible to express the same behavior another way (for this particular case):

While(box Sequence(vec![Wait(5.0), Action::PlayerWithinDistance(50.0))]), vec![
    circling.clone()
]);

The circling behavior runs forever, neither has it a beginning or end, so it does not matter if two follow each other instead of one.

AI behavior trees vs alternatives

It worked very well for something I had to code up quickly. There are other ways to do the same, for example by using finite state machines or an entity/component system.

I imagine that when working on a state machine, it would be terrible hard to do any kind of parallel behavior, and if I wanted to join two states I would likely mess up the control flow.

If I were to use an entity/component system, I would have to enable/disable the components that the systems uses for behavior, and this might not be as flexible.

A state at a given moment is described as multiple paths through the behavior tree. This is like adding another dimension to normal programming. While it easy to use on the surface, there could be cases where this leads to a problem.

It is still at the experimental stage, for but some problems I believe this becomes a powerful tool.

Piston-Graphics got a new design. The new design is based on a principle “objects as functions”. Let’s take a look at it!

This is how you clear the screen and draw an image:

graphics::clear([1.0, ..4], gl);
graphics::image(&image, &c, gl);

The Context object now only contains view and transform information, so the actual render logic must be provided through other parts of the library.

When looking up the source code for the image function, you see this:

/// Draws image.
pub fn image<B: BackEnd<I>, I: ImageSize>(
    image: &I, c: &Context, back_end: &mut B
) {
    Image::new().draw(image, c, back_end);
}

The image function is a convenience function for a more powerful way of rendering images. The Image type is declared as following:

/// An image
#[deriving(Copy)]
pub struct Image {
    /// The color
    pub color: Option<internal::Color>,
    /// The rectangle to draw image inside
    pub rectangle: Option<internal::Rectangle>,
    /// The image source rectangle
    pub source_rectangle: Option<internal::SourceRectangle>,
}

If you want a colored image, you can use Image::colored([r, g, b, a]).draw(&image, &c, gl).

With Piston-Current you can also use builder methods:

use current::Set;

Image::new().set(Color([r, g, b, a])).set(SrcRect([x, y, w, h])).draw(&image, &c, gl);

This pattern is a modified version of Rust-Modifier, tuned to work better with generics.

So why is the Image separated from the image data?

The principle is called “objects as functions” and defines a type of semantics where you do not want to deal with pure states or pure functions. First you think of what the main purpose of using the object is, and use as argument the part that changes most frequently. In the case of rendering an image, the actual image object changes most frequently. We could call it DrawImage instead of Image but because the library is fully generic over image objects, it makes sense to just use Image or graphics::Image if you have an image object.

Initially this started out as an experiment, but after seeing how nice this played out in practice, I decided to go with it.

For example, it makes it easier to separate out stuff and name things from loops. Here is an old piece of code that renders a snake’s tail from Sea Snake Escape:

let n = snake.tail.len() / 2;
for i in range(0, n) {
    let x = snake.tail[i * 2];
    let y = snake.tail[i * 2 + 1];
    if (i / 8) % 2 == 1 {
        cam.circle(x, y, rad).color(colors::BLACK).draw(gl);
    } else {
        cam.circle(x, y, rad).color(settings::SNAKE_TAIL_COLOR).draw(gl);
    }
}

If you look briefly over the source, it is not easy to see immediate what going on. Here is the new design:

let black = graphics::Ellipse::new(colors::BLACK);
let tail = graphics::Ellipse::new(settings::SNAKE_TAIL_COLOR);
for i in range(0, n) {
    let x = snake.tail[i * 2];
    let y = snake.tail[i * 2 + 1];
    if (i / 8) % 2 == 1 {
        black.draw(graphics::ellipse::circle(x, y, rad), cam, gl);
    } else {
        tail.draw(graphics::ellipse::circle(x, y, rad), cam, gl);
    }
}

black and tail easier to spot because they appear first in the line. Not a major improvement over the old design, but it is nicer. I like how it refactors in ways that makes it easier to improve code incrementally.

The library is a lot easier to understand now, with -1000 loc (lines of code), and it is easier to add new features in a modular way.

While the old design had the benefit of having no run time state, such as whether to render a border or not, the potential performance benefit was traded against the readability. For example, Rectangle is also used for round and bevel shapes. On the up side, you can draw a filled rectangle with a border through a single call.

The old design is pushed to branches “olddesign”.

You can now decide between the following ways to write the event loop:

// Move window by value (this prevents you from using the window elsewhere).
for e in Events::new(window) {
    ...
}

// Use shared reference (this allows you to use the window elsewhere).
let window = RefCell::new(window);
for e in Events::new(&window) {
    ...
}

// Use current window (the window must be set as current object).
for e in Events::new(current::UseCurrent::<Window>) {
    ...
}

// Specify usage.
let window = RefCell::new(window);
let usage = current::Use(&window);
for e in Events::new(usage) {
    ...
}

This is powered by the new Piston-Current library.

To learn more, read Best coding practices with current objects