# Obstacle Avoidance or Wall Avoidance for Tiles ?

I have a enemy in my game that is supposed to chase the player around the world and I thought it be a good idea for the enemy not to pass through the walls like a ghost, the levels are tile based, I've initially gone with the wall avoidance since a tile is essentially four lines, but I'm beginning second guessing the idea.

So should I go with Wall Avoidance Steering Behavior or Obstacle Avoidance Behavior ?

• If the enemy is chasing the player, why not generate a path every so often using A* and use obstacle avoidance and wall avoidance to...well avoid obstacles and walls? Commented Aug 20, 2011 at 23:34
• Because the pursuit/steering behavior is easier to get to a point where it chases the character realistically and adopting a wall avoidance algorithm designed for lines to work with tiles is harder than expected. Commented Aug 20, 2011 at 23:51
• A very simple solution/addition to the techniques below would be to push the enemy away from walls. The closer the enemy, the greater the push force. Sort of like negative gravity from the walls.
– Riki
Commented Aug 21, 2011 at 3:34
• @Felheart that is essentially how wall avoidance works :) Commented Aug 25, 2011 at 13:17

Pure obstacle avoidance algorithms in situations like this will create incredibly odd-looking behavior. For example, the creature will look like it's drunk when it's wiggling around some static obstacle in the middle of the way. Or it might take a very long route to get around some obstacles when going around the other way would've taken the enemy a tenth of the time to get to you.

It can also introduce some bugs. For example, if you mark your blocking tiles as obstacles and let the enemies steer away from them based on both distance to the obstacle and distance to you (both in terms of magnitude as well as direction), you might get a situation like this, where the algorithm will make the enemy walk away from the player instead of towards him or where the creature simply may get stuck:

Or your enemy looks like a dumbass:

(or like a cheater if it simply pushes through the small passage :P)

These are pretty dumb examples since it assumes that your avoidance algorithm is very simple (and stupid), but these kinds of scenarios occur sometimes, no matter what kind of algorithm for steering or avoidance you use.

The reason for this is that the enemy has no "whole path"-information, which means that while its current decision based upon the currently relevant obstacle may be correct, it may push him into a state towards the next obstacle where this kind of equilibrium or false decision behavior occurs.

There are probably weird things that you can incorporate into your avoidance algorithm which minimizes these scenarios or makes them go away completely, but I can't help but think that this is ugly.

Instead, just use a regular path finding algorithm like A* to search a path towards your character. Especially in tile-based games, where the cost between nodes (your tiles) usually stays constant, that kind of algorithm is an easy choice.

A* is usually pretty costly if you want to recalculate the path at every frame, but as long as it stays simple (just a couple of enemies) this shouldn't be a problem at all (processors are fast).

You can also opt to only update the path every couple of frames or so since the player won't notice it if the path was calculated once or twice in those 60 frames during the last second.

By the way, if you look for some good explanation for the A* algorithm, I can really recommend the chapter on it in Game Programming Gems 1 (3.3 to 3.5). The book may be hard (or expensive) to come by (it's been a while, but when I searched for it a while ago it was pretty expensive if you wanted to buy it new), but it's worth the money.

You should get Programming Game AI by Example

Yes, steering behaviours are easy to implement, but the seek/pursuit behaviour only works as a decent "hunting" behaviour when there are no obstacles between the player and the enemy. If there are obstacles or walls, then you're pretty much screwed in most situations.

You should seriously consider using A* to generate a path between the enemy and the player. It's not a very difficult algorithm to implement and there are countless examples on the internet. If by "realism" you mean you don't want your enemy to rigidly follow a list of points on a path, that's absolutely fine. Just seek to each point in the path. It will still give a realistic looking hunting motion without getting stuck anywhere.

That being said, your implementation of the wall avoidance algorithm should not be causing you that much hassle if you know how to get it working with lines. Your agent should have a feeler extending from its front that intersects with the line and you can calculate the repulsion force from:

Force = Penetration Depth of Feeler x Wall Normal

Regardless of your wall being a tile (assuming a tile here means a square or rectangle), each side of the tile will have a normal and this combined with the feeler is the key to getting wall avoidance right.

Buckland's implementation of Obstacle Avoidance created two more "feelers" for the agent heading forward-left and forward-right of the agent. When any three of the feelers intersects and object the appropriate repulsion force is calculated and applied to the agent.

TL;DR - Use A*! Wall Avoidance is the same whether you're using a single line or a square/rectangle/hexagon. Each side of the shape has a normal.