Monday, May 31, 2010

Towards Better Navmesh Path Planning

As many users of Detour have noticed, navmeshes sometimes create extra detours in the paths. This is due how the cost of traversal between different polygons are calculated. The distance to travel from one polygon to another is often approximated either calculating the distance between the centers of the navmesh polygons or, between the edge midpoints of the navmesh polygons. As seen on the above pictures.

Edge midpoints is slightly better in practice, but both will create odd paths when you have long thing triangles or large polygons next to smaller polygons.

There is a nice recent paper Shortest Paths with Arbitrary Clearance from Navigation Meshes which describes another method based on visibility. I'm itching to try that out!

That paper also reminds me why Recast subtracts the agent radius before building the navmesh. It is just really complicated to find thick paths. Even just selecting a valid end point is really complicated matter.

[EDIT] Here's how the visibility optimized heuristic should work (heuristic #3). The idea is that if there is direct line-of-sight from the current node (S) to goal (G) via the next edge (e), then the node at the next edge will be placed at the intersection of the edge and segment SG. Else, the node is placed at the vertex which is closest to G. (The picture below assumes that the node locations are calculated and cached as they are encountered.)

Thursday, May 27, 2010

Constrained Movement Along Navmesh pt. 2

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.

Monday, May 3, 2010

The Design Evolution of Zen Bound Level Tree

While cleaning up yesterday, I found some old sketch books. Some of then are from the era I was working on Zen Bound and early incarnation of Recast.

I thought I'd collect some sketches and screenshots how the Zen Bound level selection tree came to be and put them in a rough timeline. It was really hard process for many reasons. The total time span across about half a year, so many at many times we were diving in muddy waters. Now in retrospect it looks quite a bit more coherent process.

Here's the image, it is really wide image, zoom in!

Sunday, May 2, 2010

The Moment You Get It

Pretty much every on project I have worked on–which have succeeded to a degree–I have had a moment when I know that it is going to work. The above image, named navtest.png dated December 3rd 2008, was the point when I knew that Recast is going to work.

Up to that point it had been a huge struggle to find a way to partition the surface. Based on the previous incarnations of the same idea (there were 2 or 3 version before that, depending how I count it) I knew that the the triangulation can easily become the bottleneck of the algorithm. So I worked really hard to reduce one dimension from the problem, and eventually it paid out.

The following months after that it was a cake walk to add tracing the contours, simplifying them and finally doing the triangulation. Four months later March 29th 2009 I made the first commit to Google Code.