Archive for the ‘AI’ Category

Ludum Dare 48h & Locomotion

By JC on July 30th, 2008

It looks like there’s another Ludum Dare 48 hour game programming competition starting soon, so I’ll hopefully be taking part in that. Spread the word and join in – the more the merrier!

Meanwhile, back on my main project, I’m having much trouble with just trying to get a simple “chase player” behaviour. Pathfinding (with A*) wasn’t too hard but there’s lots of icky low-level details for moving a character around the environment which are creaping into my behaviour and generally cluttering it up. And due to the highly temporary nature of behaviours stopping and restarting a behaviour (such as repathing when the player moves far enough to invalidate the current behaviour) tends to lead to unpleasant animation jittering as it rapidly switches between idle and running animations.

So I’m trying to pull out some of the low-level movement and animation into a “locomotion” layer. The idea being that it will take high level orders like “run left to this point” or “jump to this waypoint” and it’ll automatically handle transitioning from the current animation to the next as well as the low-level ground following and animation ticking.

The idea is that if a behaviour aborts or switches the locomotion layer will still retain the current action and state, so it’ll continue with it’s current animation until issued a new order by the behaviour. So hopefully switching to or restarting the “chase” behaviour means that instead of snapping to a halt and then starting to run again (often in the same direction) the enemy should continue to run as it was until the “chase” behaviour decides where it actually wants to go. The locomotion layer should probably have a default anim to revert too should the current action finish, so if a behaviour is taking a particularly large time to respond it’ll start playing an idle animation rather than doing nothing.

That’s the theory at least. In practice drawing the line between locomotion and AI logic is proving tricky, so we’ll see how it evolves as things progress…

Jumping, launch velocities and rounding errors

By JC on July 18th, 2008

The physics behind a jump in a platformer is pretty simple and something I must have written a thousand times, but having an AI player jump and land where it wants to is considerably trickier. My initial attempt was to string a bezier curve between the start and end points and just make it follow that – this is easy to do and very reliable (as it will always get to the exact end point) but produces unconvincing motion. It really needs to use the proper physics otherwise it looks out of place.

So if we’re using the proper physics we want to calculate a launch velocity then just let the simulation do the rest. However finding a suitable launch velocity isn’t easy – there’s lots of unknowns and variables, largely because there’s lots of potential jump arcs which take you between two points. You need to nail down a few of the variables so that ideally only one solution pops out.

After several failed attempts I’ve found that specifying the jump apex gives nice consistent and controllable results. I can pick the apex by applying an offset from the highest of the start and end points then split the jump into three components- the vertically to the apex, vertically from the apex, and horizontally for the whole jump:

ImmutableVector2f startPos = enemy.getPosition();
ImmutableVector2f endPos = nextWaypoint.getPosition();

// First, find jump apex
final float highestY = Math.max(startPos.y(), endPos.y());
final float apexY = highestY + 100;

// Vertically, to apex
// t = sqrt( 2s / a )

final float s1 = apexY - startPos.y();
final float t1 = (float)Math.sqrt( (2 * s1) / -FallBehaviour.GRAVITY);

// What's our launch speed for this section?
final float vy = -FallBehaviour.GRAVITY * t1;

// Vertically from apex

final float s2 = apexY - endPos.y();
final float t2 = (float)Math.sqrt( (2 * s2) / -FallBehaviour.GRAVITY);

// Total time for entire jump
final float tTotal = t1 + t2;

// Horizontally
final float s3 = (endPos.x() - startPos.x());
final float vx = s3 / tTotal;

brain.jump( new Vector2f(vx, vy) );

Unfortunately this has two down sides – the structure of a level means that sometimes there is an interveaning platform that the AI wants to jump “through” but the simulation causes it to land there instead. The other down side is that rounding errors mean you don’t always hit the target exactly, and since my collision is all sub-pixel that means you can miss the edge of the platform by a fraction and end up plummetting to your doom.

The solution is to also calculate the expected time length of the jump and when that time is reached snap the enemy to the target point (and disable all other ground collisions in between). This gives us the best of both approaches – the AI always ends up exactly where it wanted to, but while following a convincing curve. And since we’re doing a proper simulation if something happens during the jump (like we get hit) we can easily turn off the special collision handling and let the physics take over.

On an entirely different note, Deaths (thanks indie gamer) is a really neat idea for a platformer with a twist (and, amusingly, no AI whatsoever). Passive online interaction like this is something I’ve been thinking about for a while but can never manage to come up with an idea where it’s an important part of the gameplay rather than just a novelty – Deaths manages this quite well I think.

Yet More On Behaviour Trees

By JC on July 10th, 2008

So I’ve been going through as much stuff on behaviour trees that I can find to try and figure out whether they’re going to be appropriate for what I’m doing and how they actually work. “Behavior Trees for Next-Gen Game AI” is very comprehensive and well worth a watch if you’re interested (despite my dislike for videos – text is just so much more practical), and I think I can see how it would come together to produce interesting behaviour.

In a way I’m actually feeling a little disappointed – the current game design doesn’t call for massivly complex AI (you are fighting zombies after all) but now i have the urge to switch to something with fewer enemies with a much richer set of behaviours. But that will have to wait, and the current game will give me a chance to walk before I run anyway.

I’m not entirely sure how i’m going to handle interrupted states and animation (like when an enemy gets hit right in the middle of an attack). Currently I’m thinking of having behaviours listen to events, and making them fail and bail out if they take damage. It seems like it would work, but it sounds like it would require handling this event all over the tree, which could get tedious and error prone. On the other hand it might be a good way of intelligently playing different damaged/death animations depending on what we were doing at the time.

Behaviour / AI rambling

By JC on July 7th, 2008

Enemy behaviour in my current (as yet unnamed) game hasn’t come on very far – just a single enemy with a traditional hard-coded finite state machine (done the old-school way, with a big switch statement). Which was initially fine as it let me get some of the more important low-level details into place, but now I’m looking at adding more enemies it’s not looking so hot so something more elaborate is called for.

Ai Game Dev has been in my bookmarks for a while now, and provides a lot of interesting reading. The approach F.E.A.R. takes towards it’s AI is particularly interesting and probably something which would work well, but is a little beyond me at the moment. Instead what’s caught my eye is behaviour trees. In particular it seems to solve a problem that I’ve been having – how to write specific modules of behaviour (like a specific enemy attack) in a way that they can be reused and rearranged rather than having an explicit “next” behaviour.

I’m not sure I entirely understand how it’s all going to fit together with some of the higher level gameplay interactions, but it’s a promising direction. I think I shall leave my current FSM enemy as it is and code up the next enemy as a behaviour tree (or possibly do the same one again) and see what the resulting code is like.

Since I havn’t really done a scrolling beat-em-up before, I’m expecting to take a few wrong turns with the AI before I find something that works. If anyone has any experience to share then feel free to leave a comment.