Steering

From GPWiki

In many games there are 'agents' (enemies, usually) moving around though some kind of world. Having these move in a way that looks intelligent and believable is an interesting problem. I'll try to illustrate some basic techniques here.

Problems

If you want your agents to look like they have any brains at all, and are part of a real world, there are some things you'll have to solve. The most important points are:

• Going somewhere (direction)
• Moving in a consistant manner
• Avoiding static obstacles
• Avoiding other agents and moving things in general
• Not getting stuck

The first point is largely beyond the scope of this article. Unless standing still, the agent will be going somewhere, usually a specific somewhere. A pathfinding algorithm (A* for example) can be used to generate a path, and sometimes just going in a certain direction will do. Just assume that we know 'where' we are going, for paths a special system has to be made make the agent go to the next 'waypoint' when it reaches it's current waypoint.

On the second point, moving in a consistent manner, you'll have to make some decisions. Usually agents have some constants like 'turning speed', 'maximum speed' etc. Having agents change direction instantly (flipping around), looks awful, but is very convenient. In the same way, having a 'velocity' on every agent, making them speed up and slow down, is a lot harder than just allowing them to decide their speed at will every frame. For your first attempt at a steering system I'd recommend having your units turn around with a certain speed, but not bothering with velocities (for 'walking' agents this looks okay).

When an agent is moving somewhere, he must not move through obstacles. That is fixed easily enough with a collision detection system that just stops the agent when it bumps into something, but the agent will still look a little dumb, bumping into stuff left and right. A big part of this problem can be solved with good pathfinding, which can easily be used to make the agent move around static obstacles. For moving stuff this is harder, it is not simple to predict where everybody else will be once the agent is somewhere further along the path it is very possible that some other agent is blocking its way.

A common solution to this problem is doing the avoidance of moving obstacles on-the-fly when moving, making little detours around stuff that gets in your way. As long as the moving obstacles are not too big and not too tightly packed, this works. You can get nasty traffic jams this way though, which brings us to the last problem, getting stuck. Quite a few solutions to this have been developed for this, but none are very easy or robust. You can make agents send signals to each other when blocking each other (something to the effect of "get out of my way!"). Another idea is to deliberately make agents take different path, possibly computing the general density of agents in all areas and making agents avoid busy areas.

Reynolds

I know this is a little cheap, but what I'm going to do here is link to an article by Craig Reynolds and advise you to read it very well. This is a long, well illustrated article explaining some great steering techniques. No use repeating it's content here.

• Reynolds on steering

More on obstacle avoidance

In Reynolds' article, obstacle avoidance is touched only briefly. His solution is basically:

• Find the nearest obstacle that blocks your way.
• Decide on which side of the obstacle you want to go.
• Steer that way until it is no longer in your way.

In an environment with sparse, more or less spherical obstacles this works great. But when obstacles have more complex shapes, or are clustering together to form bigger obstacles, this falls apart entirely. The agent will go around a group of obstacles by the longest way, or get stuck in a corner. In most games, you'll want to have obstacles on your map in arbitrary locations, so you'll need something smarter.

I was implementing a top-down game in which the map contains convex polygon-shaped obstacles. After realizing the naive steering approach wasn't going to work I looked into using A* to do the pathfinding. This requires some kind of graph-structure of the map though, and to generate a graph from my map would be quite computationally expensive. I could of course pre-generate them, but since agents have different sizes they wouldn't all be able to reach the same places so the graphs would differ for different agents. On top of that, having to re-generate the pathfinding data for my maps every time I made a change would be annoying. So I was looking for something that did not require this kind of data.

The solution I came up with is something between A* and naive steering. When an agent needs to find a path from point A to B, he generates some waypoints which look like they might be useful, and performs an A* search on those. The algorithm is not guaranteed to come up with an optimal path, in fact it performs quite poorly in a maze-like environment, but for not-too-crowded maps it works great.

So how does it work? First off, be sure to read the article on A* if you are not familiar with that algorithm, because this explanation assumes you know how that works. Just like with A* you use an 'open list' of nodes that need to be looked at, and a 'closed list' of nodes that have been handled. The starting position gets added to the open list. Then:

• If the open list happens to be empty, we could not find a path and give up.
• Otherwise, find the node in the open list for which the distance travelled to get there plus the distance between that node and the goal position is the smallest.
• Move this node from the open to the closed list.
• Take a line from this point to the goal and look for obstacles that would block the agent when travelling in this line.
• If no obstacles found, we've found a path.
• Otherwise, for both sides of the nearest obstacle:
  • Find a point for which the path between the current node and P passes just past the obstacle (you'll need to do some math trickery to get this point, I had the function that checks whether an object is blocking a path also return the corner of that obstacle that lies furthest away from the path for both sides of the obstacle).
  • If the line between the current node and P is blocked by another obstacle, repeat the previous step for that obstacle (but only look at the same side of this obstacle as the side that we are handling of the original obstacle, the other side is blocked by the original obstacle anyway).
  • Once a line that is not blocked is found, add it's P point to the open list (together with the distance travelled to get there and some kind of pointer to the current node).
• Repeat.

Important: You will want to add some maximum-attempts counter to both the inner and the outer loop in this algorithm. Otherwise they could get stuck in an infinite loop when there is no solution.

Anyway, the part about projecting lines past obstacles' sides and going to the next obstacle if the line is still blocked might be a little vague still, so I've illustrated it in figure 1. The triangles are the agents, and they are trying to get to the crosses. Only, those circles are in their way. So what they do is pick a path that goes to the side of the obstacle, and then a little further to actually get past it (in order to prevent having trouble with that same obstacle when trying to find the next waypoint). In situation A this leads to two non-blocked waypoints, and the one that gives the shortest path is picked (the dashed line is a route that was considered but not picked, the orange lines are blocked paths). In situation B, when the agent tries to find a path that goes to the left (our left) of the obstacle, it runs into yet another obstacle. So it generates a new path to go around that obstacle. In this situation it ends up deciding to go around the other way, where there is no second obstacle, because that is shorter.

Figure 1: The different potential destination points generated to get around an obstacle.