Saturday, February 12, 2011

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.

8 comments:

  1. love the pics and videos you put into your blog, it show your interest in the subject!

    ReplyDelete
  2. and with power of your experience, how would you do such interaction of game-logic\animation <-> pathfinder in this case
    >>the pathfinder cannot help you since it does not know about the blocker
    ie character could use jump-over anims to pass barrels

    + via callback in pathfinder on each obstacle
    + completely offload all work ( obstacle processing, animation choose ) to custom game-logic
    + custom pathfinder with integrated game-logic, to able to use pathfinder related data

    ReplyDelete
  3. Is this intended to replace the regeneration of a navigation mesh? Or augment it for "even more temporary" obstacles?

    ReplyDelete
  4. Tomat, There area a couple of other cases in the DetourCrowd that needs to handle similar cases, like how to handle animations/game-logic during off-mesh connection (aka jump link), and how to handle dead-locks with anima/game-logic.

    My plan is to detect those cases, find potential locations to resolve the cases, and then build a list of agents which need to be updated by the game. That way the game can poll the list of agents which needs to be update in some special way and things will be fast. Basically the game just needs to update the animations.

    Namreeb, Yes and no. Some games, which have simpler scnerarios and have just few obstacles here and should work fine with this method. I will keep working on the "correct" method too of regenerating the navmesh.

    ReplyDelete
  5. Hi Mikko,

    You mentioned an approach to select which tangent of an obstacle an agent should seek, based on whichever tangent results in the shortest distance from the agent to the tangent to the goal.

    Is that approach always correct? What about the following case?

    ............
    ......G.....
    ............
    .L--------|.
    .|........|.
    .|....0...|.
    .|........|.
    AR--------|.
    ............

    (Agent 'A' is trying to reach goal 'G'. Obstacle 'O' is obstructing the path. The agent may select either left tangent 'L' or right tangent 'R'.)

    When an agent gets very close to a tangent, the agent-to-tangent distance approaches zero, leaving the tangent-to-goal distance as the dominant term. I find this results in the incorrect tangent being selected ('R' in the diagram) since the correct tangent ('L' in the diagram) has a slightly greater total distance.

    How does one reject these incorrect tangents? Are there further steps required when selecting tangents?

    Thanks!

    ReplyDelete
  6. The distance from then agent to the tangential points is the same for left and right tangent. To break ties and the singularity case really close to the obstacle, I think I used similar side bias as the HRVO uses, that is, one side is favored over the other. Or it could be that I just did not handle that case in my proto.

    ReplyDelete
  7. Are you speaking of a single circular obstacle, where the distance to each tangential point will always be equal?

    What about non-circular obstacles, such as a single rectangle (I tried to illustrate a rectangle in the diagram, but failed) or even a large cluster of circular obstacles, where the distance to each tangential point is not equal? I imagine some additional steps beyond a distance estimation would be required in these cases, but nothing comes to mind yet!

    ReplyDelete
  8. @Chris, I see now, I failed to read your ascii a little :)

    I've tested few heuristics in the past, for example at some point I calculated the obstacle size perpendicular to the desired movement direction. I remember struggling a lot in certain cases where the agent would just oscillate between a couple of almost as good choices. Your idea about considering the whole cluster sounds good.

    ReplyDelete