Very Temporary Obstacle Avoidance

In the rush of trying to make everything perfect, it is sometimes hard to remember that a simpler solution could work too. This ties to my efforts to handle temporary obstacles.

If you want a rock solid way of handling temporary obstacles, there is no other way than to bake them into your navigation graph. There is just no way around it.

But at the same time there are huge number of cases, where you just would like to sprinkle few crates and barrels here and there for the player to shoot at, and will just break your navigation.

Purely local obstacle avoidance cannot handle them (or you are really lucky, if it does!). Local avoidance gets stuck in local minima (i.e. U-shaped cluster of obstacles), or platos (i.e. row of obstacles).

There is range of algorithms that fit somewhere in between local avoidance and global path planning. Which will solve the case of some temporary obstacles here and there, but will break of the obstacles for too complicated shapes.

Avoiding Temporary Obstacles Locally

One potential solution is to use small grid around the NPC to find around the obstacles. I have experimented with this earlier and it works really well. Another solution is to cluster the obstacles to for larger obstacles and use their silhouettes to find path around them.

That silhouette based obstacle avoidance is also discussed in an article in Game Programming Gems 3 called "A Fast Approach to Navigation Meshes" by Stephen White and Christopher Christensen. It is one of my all time favorite articles. I must have read it billion times.

I have tried to improve the algorithm few times in the past, but never quite got it right. I was working on a recent request last week and the idea popped up again, and I thought I'd give it a another go.

Basic Method

The basic process works so that you have a certain segment goal in the world where you would like to move to. First you check that if there is something blocking the way. In practice it means finding intersection between the segment from agents current location to the next sub-goal (i.e. next corner on the path) and all the temporary obstacles near by.

If something is blocking the way, we find tangent of the obstacle, and choose one side to steer around the obstacle. The side is selected based on which detour is shorter. The distance is approximated by a path from the start point, via the tangent point, to the goal location.

The first tricky problem with the method is how to handle multiple obstacles. Naively just visitin all the obstacles and finding a furthest tangents, will lead poor behavior when there is passages through the obstacles.

Obstacle Clusters

One solution to this is to first cluster all the overlapping obstacles. Then when you hit one obstacle in a cluster, you simply find the furthest tangents of all the obstacles in the cluster.

Sometimes this leads to a case where the newly chosen path will be still blocked. The solution is to check if there is some obstacles blocking the path to the new target, and iterate until the path is collision free.

Iterative algorithms are always tricky in realtime games and simulations. The goo things about this method is that just one iteration will give you a collision free solution. If the new path will lead to collision with another obstacle, that collision will eventually be the first hit and it will be corrected. The result is ugly, but it'll work. In practice this means that you can limit the iterations to 2-4 and it will handle most of the cases with gracefully!

Dealing with Obstacles Touching Walls

The next problem to solve is how to handle cases where one side of the obstacle touches navigation mesh boundary wall.

The solution I have used is to add special obstacles at the navmesh boundary, I call terminator nodes. When a terminator node falls on either side of the silhouette that side is marked as blocked and that is prohibited to be selected. If there is terminator node on both sides, it means that the path is blocked. This is really important feature of this method. It is not perfect, but it signals when it does not know that answer!

It Will Break

You should be also aware that using this method will eventually lead to situations where the path is blocked and the pathfinder cannot help you since it does not know about the blocker. You have to deal with it.

Your imagination is the limit how to handle such cases. You could for example just teleport the NPC to the other side of the obstacle, or the NPC could jump or climb over the obstacle using animation, the NPC could try to kick the blocking obstacle, shoot it, or you could detect that newly added obstacle creates a blocking wall and just break obstacles in the cluster until it is safe again.

That is, you need to have some kind of game mechanic to either break obstacles or skip them. One thing you should not do is to just disable the obstacle, since it can and will lead the agent to be inside the obstacle for long time.

Closing Words

There are quite a few more tricky details in the process I did not cover. I hope to polish those ideas a bit more and explain them at later stage. I think the method should be applicable to convex polygon obstacles too, which would make it even more usable. I have to try that out.

I think this method could be interesting choice for those who wish to add few obstacles here and there and whose game design can allow some game logic to pass through the obstacles when they block the NPCs path.