原文链接：https://medium.com/@mscansian/a-with-navigation-meshes-246fd9e72424

To understand the concept it’s mandatory that you feel comfortable with a grid-based A* algorithm. If you don’t fully understand A* please take your time to read this article for beginners.

Before you start, you need to create your navmesh. It can be made of anything, from triangles to polygons. The only constrain is that each individual node is convex. This is useful because it guarantees that any straight line inside a single node is a valid path. Some AAA games (Valve) use rectangles as navmesh nodes. There are some increased speed with this approach, but I recommend that you (at least for now) stick with triangles. Might not be the most speed-friendly way but it is, by far, the easiest to code.

There are several ways to build your navmesh. You can try doing it manually or using algorithms that calculate them dynamically. In the end you will need a list of connections between every node and its neighbors. You don’t actually need to build this list if your triangles have coincident vertices with its neighbors.

With everything mapped, it’s time to make it work! An example of the problematic could be illustrated by the following example:

Find the shortest (or reasonably short) path from START to END making sure that this path is inside the navmesh.

Normally, your starting/ending point is not on any vertex. So we need to find out in which triangle it is situated. An easy method to do this is to call a function PointInsideTriangle(). We provide this function with the triangle vertices and a point and it should returns true if the point is inside the triangle or false otherwise. There are several ways to code this, my favorite one works with cross products. This mathematical approach is fast and reliable. Its algorithm is described on this website. There is in fact another way of doing the same thing. It involves computing some triangle areas and comparing them. Though this approach sounds easier, I strongly discourage you from using it. It’s very computing-intensive and the variable decimal precision can lead to errors. Instead use the algorithm described on the website above.

Now that we have you function coded, we must check our starting and ending point against all triangles into the navmesh until we find where they are located. It may sound like a very computing-intensive operation and sure it is! The good news is that we only need to calculate this once for the entire path. After this analysis you can come up with any of those 3 results. It’s important to handle them carefully.

1. Both point are located on the same triangle
   Good news! This means that we can use a straight line as our path and for sure this is the shortest way. No further intensive calculations necessary.
2. One or both points are outside all triangles
   This means that one or both points are outside your navmesh. On this situation I would probably stop this path calculation and return just a null path. But it’s up to you! You can make a code to handle this kind of error.
3. Both points are located on different triangles
   This means that we should proceed with our path calculation.

Now that you know on which triangle your starting point is located you can add this point to the closed list and send all the adjacent points to the open list (and keep a record of its parent point — in this case the starting point). The adjacent points in this case are all the triangle vertices. By doing it you will get this:

For each point, calculate the G and H cost. You can find a lot of ways to calculate this on the internet, or just use the distance between the last point (starting point) and the vertex for G and the distance between the vertex and the ending point for H. It`s not the best coefficient but works! After you are done, selected the point with lower F cost (F = G + H).

Repeat the same process with this point (send its adjacent points to the open list and add the point to the closed list). If any point that you are trying to send to the open list is already there: Just check if the G cost from this new path is better than the former, if true, then change the G cost, and the point parent. Also, when calculating the G cost, remember that it is the G cost to the point V2 plus the Distance between V2 and the point you are calculating.

You know you are finished, the time that you add to the closed list one of the vertices of the triangle that contains the ending point. To check this, you can find the 3 vertices of the ending triangle and check every time you add a point to the closed list.
When you find this vertex, your next point is just a straight line to the ending point, since you have a convex navmesh and you can draw a straight line between any 2 points inside it.

Just like the algorithm for grids, backtrack your way to the starting point (using the parent points you recorded) and you will find you path.

You will notice that this algorithm provides a wall-hugging path, since it use the vertices to generate the path. You can fix this by deleting useless points (if you can go from A directly to C without falling off the navmesh, then the point B is useless and you can delete it).

Source code (Blitz3D)

1. https://github.com/mscansian/b3d-binaryheaps
2. https://github.com/mscansian/b3d-astar-pathfinding