How to tune steering behaviours to pick the best target around obstacles?

I want to chase an enemy, but there are obstacles in the world. Imagine there's an obstacle stopping me reaching the closest enemy, but in another, unobstructed, direction is another enemy but at a further distance:

***************
E ** P        E
***************

* - obstacle
E - enemy
P - player


My enemy-chasing behaviour returns a vector pointing towards the left-most enemy, and my obstacle avoidance behaviour returns a vector pointing to the right, away from the obstacles. At some point they balance out and I have stalemate!

This could all be avoided if there was an elegant way of choosing the other enemy at the beginning.

Is this a common problem in steering behaviours? How is it regularly solved? I may have a lot of enemies, so pathfinding to each first may be inefficient.

• are you on a grid? do obstacles move? – Luis Estrada Aug 13 '12 at 20:24
• I don't think I'm fully understanding it right, but by what I understand, your code is selecting it's target based solely on distance and you want it to further improve it by making it choose targets with least "obstacles" when two have a similar distance. In that case, you can count the amount of "turns" your (path-finding?) algorithm calculated for each target, and pick the target that has the least. – XenoRo Aug 13 '12 at 20:33
• I use path finding in combination with steering. Find a valid path to the nearest enemy and steer that way. You can also use the path to steer towards way-points along the way, making your steering smarter by avoiding dead-ends and choosing the shortest path. – MichaelHouse Aug 13 '12 at 20:45

As Byte56 mentioned in the comments use path finding. If you only want to get the closest enemy then use breadth first search, preferably with limited depth, and use the first encountered enemy as your target. Also, as Byte already mentioned, you will need waypoints for your steering, you can't just start steering towards the enemy position as the path to get there might not be in the direction towards that entity in case there are obstacles in the way.

• This answer is inspired! – MichaelHouse Aug 13 '12 at 21:31
• Haha yes I almost felt bad writing it :) – Mikael Högström Aug 13 '12 at 21:33
• No worries, you expand the parts that need expanding. Also making it clear that you just need to find the nearest enemy with BFS, no need to path to each enemy. – MichaelHouse Aug 13 '12 at 21:59

Instead of path finding, you can also prioritize your steering components. Instead of weighting them 50:50 make it 40:60 with prioritizing obstacle avoidance. That will let you end up in wall some time however.

You can also alter your steering output. If obstacle avoidance has nothing to avoid, use the other vectors(weighted or not), but if obstacle avoidance has something it needs to avoid, only use that. This however might give you jittery movement when you alternate between collision avoidance and not.

A good solution I have found is to compute the other vectors first and then use them to influence the obstacle avoidance. The avoidance vector sets the lower bounds (right and left) needed to not collide and with the vector from the rest of the input, you can choose which vector is better(smallest angle). Add hysteresis, so you don't change from one direction to the other and you will get mostly smooth movement, without path finding. It is however still difficult getting the avoidance bounds right for concave objects.

• +1 for third paragraph. A two-stage steering behaviour system is interesting. – tenpn Aug 14 '12 at 8:46