I have been really busy recently at work, with my Paris presentation and some other projects of mine. That has taken its' toll on the frequency of the blog posts too.
have few hours extra time, I though I'd blog a little bit about a problem in my old code I tried to solve just recently. Very little discussed topic and one of my favorites,
moving along navigation mesh.
—
The goal of the movement code is to solve the case of moving constrained to the navigation mesh boundaries. Since the walkable areas are divided into convex regions we can use this to solve the movement only inside on polygon at a time and then move to the next polygon based on which edge we hit at the end of the current step.
In case the movement target is outside the current polygon, my earlier attempt clamped the point on the polygon boundary, and followed the edge where the point lied on. While this works most of the time and creates nice sliding movement when a non-traversable polygon edge is hit, it also misses some obvious cases.
The Problem
Such example is shown in above picture. The blue arrow indicates the desired movement delta, and the location labeled 'nearest point' shows where the old nearest-point-on-boundary method would move the character. If the bold edge was connected to the next polygon where the agent is supposed to move to, the test to see if we can move to there would fail when using the old method, even if there is obvious line of sight to it.
Improved Solution
An obvious choice would be to use line intersection or ray-casting to check if there is edge crossing the movement. Instead the new solution still avoids using raycasting since there are some corner cases which are hard or just annoying to handle when using intersections (i.e. hitting vertices and parallel edges). The basic idea of the improved old method is as follows.
If the movement target is inside the polygon, we just accept the new target location. If the movement target is outside the polygon, we first detect which edge the movement delta crosses on its way to the target location and follow the edge if it leads to the next polygon or use the old method if we hit obstacle.
Finding the crossing edge can be easily figured out by testing if the target is inside the sector formed by the movement start location and each edge at a time. This test can be quickly one using using 2D cross products. Dashed lines in the above picture show the sectors.
If the found edge (or its neighbour if we clamped to either end point) is connected to the next polygon to move to, we move the current location to the nearest point on the edge and continue to the next polygon and start the iteration over.
If we instead hit an edge which is an obstacle, we move current location to the nearest point on the boundary of the polygon from the target location, just like in the earlier algorithm, to get the nice sliding movement.
More Woes
There are some cases when the start point is not exactly inside current polygon. This can be because of the floating point accuracy or because some external collision resolution pushed the point away from the mesh or something similar. It is desired that our method works even in that kind of cases.
In case the start location is outside, the trick is to first clamp the start location to be inside the polygon and proceed as before. That's it! Because of the floating point accuracy, there is still need to add a little bit of slack into the sector test so that it handles the case where the start point lies close to the boundary.
—
Handling corner cases like this is really important when building robust navigation system. The earlier method was usually not a problem when you would use small delta movements, but it happened sometimes. It should not happen. Not even in 0.01% of the cases. Nothing is more annoying than that you have a valid path which cannot be traversed.
