A critical aspect in most games is aesthetic and reliable entity movement across the world. They should be able to follow paths and navigate across the terrain realistically; they shouldn't ghost through things, get wedged in the landscape or bounce uncontrollably off walls.

That can't be too hard, can it? Yet after a year of development these cretins still can't follow a simple path without messing it up occasionally. This post is a breeze through the dysfunctional history of entity steering in my engine.

The Prequels - Big visions

Initially the world was simple; entities are floating squares¹, velocity is (x, y), position is (x, y, 1.0). A hardcoded velocity punts them across space with the simple formula pos += vel * speed. Nobody is impressed.

An arrival steering behaviour, back when life was simpler.

Now what if they became 3D cuboids, and used real forces to move around? I falsely envisioned that this would be epic and integrated the Bullet physics engine to produce the monstrosity below². Now they can follow flat paths somewhat mechanically.

Please excuse the gross, washed out colours, they'll soon be improved. In fact, we'll soon be tossing out all this code in search of simplicity (spoilers!).

Perhaps the terms "mechanical", "stiff" and "godawful" spring to mind.

There are so many parameters that can be tweaked here that finding a nice combination takes a long time. Among those many variables is acceleration, maximum speed, and friction. Even after many iterations friction continues to be the worst of all, grounding them at random.

A random subset of the entities happen to have a surface area too great to slide around on this featureless plane. This is not ideal.

This all looks a bit unnatural, surely they should face their direction of travel? Attempting to apply just enough angular velocity to turn around and not overshoot or spin endlessly tested my patience enough to scrap forces and manually set their linear and angular velocities by hand. Here starts the slow realisation that a 3D physics engine doesn't fit my requirements.

Somehow they look even less organic with these very wooden right angle turns.

The Dark Times - Physics

Now they can follow paths and turn on the spot; this calls for a few seconds of celebration before substantially moving the goalposts. Colliding with the world is surely of great importance, to avoid glitching through walls and spoiling all the fun? Let's see how that goes.

They really are making a gallant effort to push through to their destination, I almost feel sorry for them.

Perfect! Although I forgot that the world is 3D and is not entirely flat. How are they going to climb up those ledges? I might as well continue this tragic journey down the physics rabbit hole and let them jump.

Even though the pathfinding knows about the presence of jumps (it is composed of instructions such as [walk_to(A), jump_up_to(B), jump_down_to(C)]), my first plan was to let them jump any time they see an obstruction in front of them. I gave them invisible collision-detecting sensor cones that would trigger a short, sharp, upwards force when it collides with the world. Doesn't that sound simple and totally watertight (dripping sarcasm intended)?

The perspective has rotated a bit, to demonstrate what a bunch of crackpots we're dealing with here. Their brains are receiving a constant stream of jump commands, and they are feverishly complying.

As it turns out, this was a terrible idea and a constant source of bugs, such as:

• The sensor should not always intersect with the ground and make them bunnyhop
• The sensor needs to be long enough to give them enough time to actually scale the obstacle before they reach it
• The jump needs to be high enough to scale the obstacle, not just bruise their knees
• But not that high
• The sensor can sometimes brush an obstacle during a turn, causing them to jump unnecessarily and end up in a place they didn't expect
• A jump should not be defined as "go upwards until obstacle is gone" or they become skyrockets
• Glancing at another uncollidable entity is not an excuse to jump/take off

The Renaissance - Return to simplicity

After a few months away from the project the thought of continuing with this 3D mess was too much to bear. I threw out the physics, forces and the third dimension, and returned to the realm of simple 2D topdown games (although still based in a 3D world). Movement would be implemented with simple vectors representing velocity, acceleration and steering direction - a breath of fresh air.

After so many of those slow, blundering cuboids, it really is refreshing to see these little circles zipping around so smoothly.

Our primitive 2D shapes have no knowledge of the physical world, only that the path they follow will guide them to their destination³. As they arrive at each waypoint on their path, their z coordinate (vertical, pointing up towards the screen from their perspective) is set to be 1 above the ground, giving the illusion of "scaling" the world. This is a terrible hack that looks glitchy occasionally, but it gets around the problem of jumping and gravity for now.

This is far from perfect (or even functional), however. Often these poor souls will overshoot a tiny bit when following a path, just enough that the coordinates rollover from e.g. (5.0, 5.0) to (4.98, 5.0). This is enough for the pathfinding to decide that it should pathfind from the solid block at (4, 5) instead of the accessible space at (5, 5), which immediately fails. Since there's allegedly no path away, they sit there forever, pitifully bleating in the logs that they're stuck.

Annoyingly, this is a problem that constantly comes back to haunt me. One "fix" was to try to pathfind from both the floor and ceil of their current position, or from all their adjacent neighbours. This covered up the problem for a short while until it reared its ugly head again. Besides, it was an awful hack - friends don't let friends build game engines out of piles of hacks.

How heart-breaking, they're really giving it their all. Over time they all eventually get wedged in the walls, just like our orange friend in the top left there.

The Can of Worms - World modification

Adding the ability to break blocks revealed a whole new host of problems. Some will lay low until I get to them (such as aborting and recalculating paths), but others immediately arose and got in the way. For example, when an entity is ordered to break the block they're standing on.

As soon as this block disappears, they are technically floating for a split second. They took this as a good opportunity to decide they were totally lost (after all, there are now no paths that lead to or from this air block), and hover there for eternity. The need for gravity increases.

They rush to break the blocks in the selected 2x2 region, but greed gets the best of the green one, freezing him in midair. Take it slow, kids.

The Comeback - Simple physics

At this point it had been a while since our adventures with 3D physics, and I was prepared to take another shot at collision resolution. This time it would be simplified and totally avoid all the issues with full rigid body physics. Unfortunately, it only introduced new problems.

For testing I set up a nice, perfectly easy situation for our little guy to navigate. He starts out underneath this little staircase, and should swerve out and around the block in front of him to reach his destination - go!

Nothing ever works on the first try.

It seems the threshold for arriving at each waypoint on the path is more permissive than the collision resolution. We can see that his path of 3 waypoints (go down, left then up) is nearly completed before he is punted back to the start, even through he believes he only has 1 waypoint left to go, which is straight through the solid staircase.

This is fine, let's just⁴ make the collision resolution a tad more lenient.

If you reduced everything to 5FPS this might look alright. I'll keep that idea in the back of my mind for when things get really bad.

Well, at least he arrives where he meant to go, but what a shame about the journey. The thought of attempting to keep debugging and tweaking this to make it just right was triggering at the time, so I decided to try another solution; avoid collisions rather than resolve them.

Context steering

I plan to cover the technical details of steering behaviours at some point in the future, including the concept of context steering. In the meantime, it can be summarised as a flexible method of choosing which way to travel based on interests and dangers.

The present situation fits these 2 categories well; the direction towards the next waypoint on a path is registered as an interest, and any potential collisions with the world can be registered as a danger.

He no longer bounces off the world, avoiding steering into obstacles in the first place. Although the journey is now acceptable, he doesn't actually arrive at his destination. 1 step forward, 1 big bounce backwards.

It almost works! He successfully steps out from underneath the staircase and marches towards his target! Hold the celebration, though - we have a new problem. Or technically, a new breed of our original problem. He overshoots his target off the step and falls down to the next step; at least, he would if there was gravity. Instead, he finds himself floating above the stairs, thoroughly confused and most certainly incapable of arriving at his destination.

I guess it's time to add gravity again.

Gravity 2.0

This time, the physics are vastly simplified. The 2 "forces" can be described as follows:

• if floating { pos.z -= 1 }
• if colliding with world { pos.z += 1 }

That's it; if all of the blocks beneath the entity are air, "fall" down 1 block per tick until the ground is reached, and if any of the blocks occupied by the entity are solid, bubble upwards 1 block per tick until this is no longer true.

This actually works surprisingly well for its simplicity. Following a path can now ignore jumps/steps and just jam the entity in the direction they're supposed to go, and they will either obey gravity and fall or rise upward and "step up". Has movement finally been solved?

It seems that these miscreants were raised by crows.

As it turns out, it's a good idea to implement both forces together, rather than only the "bubble up" force, otherwise you end up with hilarious bugs like this one. They managed to climb up to the platform on the right but can't come down without gravity. This answers the question "why are they taking turns dive-bombing that food?" - because they're floating 3 metres in the air above it!

The Present - Disobedience

There are still many more problems to deal with. This next one can be described as spontaneous amnesia, or maybe it's just pure stubbornness.

It makes me feel better to blame them for their stupid behaviour rather than the code. I'm sure they do it on purpose.

This is the bug I'm grappling with at the time of writing, caused again by their attempting to pathfind from their exact position. Here, he is sprinting towards the food on that ledge, and in the split second that he is jumping/stepping up he happens to reconsider his life choices. As he is currently floating in midair, he decides that there is no food accessible from his position and wanders away instead. A second later, he joyfully discovers there is food only a few metres away, and runs to pick it up.

The solution I have in mind is to keep track of the last accessible occupied space and use that for navigation, rather than the possibly-midair exact position. Maybe this will bury this bug for a few weeks before it reappears under a different guise.

Conclusion

I've ranted about a lot here, and you could even pretend it was all with purpose and boils down to a handful of widely applicable life lessons:

• Think on major architectural decisions - don't churn out thousands of lines of code on a whim. Even if the time budget for this project is "infinite", motivation and resources are not.
• Not all games need perfect collisions and physics - For this type of game, overlap with walls and other entities is fine, especially as the player does not have direct control over entities.
• Keep moving forward - if it kinda works, move on to the next thing. Leave some TODOs if you know how you could improve it in the future. You don't want to end up with a perfect entity walking simulator and no game in 5 years.
• Bugs get funnier as the game gets more complex - Logic bugs can now be blamed on the stupidity and vanity of the minions. Why can't they just do what I tell them?