Return to Answer

You say you know how to generate a path of polygons to reach the goal. Then you must also know the edges you will cross, and may use this to build an actual walking path. A simple way of doing that would be to use the center of each edge as a waypoint, which gives you a functional but not very pretty curve to follow.

There are a few different ways to make it prettier. I usually "relax" the curve (not sure what the correct terminology is here) by, going backwards from the goal, moving the waypoints along their corresponding edges to minimize the distance to the next waypoint. I.e. the last node before the goal is moved to minimize the distance to the goal, the next-to last is moved to minimize the distance to the last waypoint, and so on...

Finding the point with the minimal distance is equivalent to projecting a point (the goal/next waypoint) onto a line segment (edge). Stack Overflow has a few answers on this, Shortest distance between a point and a line segment for example.

Note: this assumes that all navmesh polygons are convex (which they should be and hopefully are) because then we can exploit that, by definition, all paths between to points on the edge are entirely inside the polygon. Meaning we don't have to care at all about making sure the path is valid when moving the points on along edges (this time assuming obstacles are handled elsewere).

You say you know how to generate a path of polygons to reach the goal. Then you must also know the edges you will cross, and may use this to build an actual walking path. A simple way of doing that would be to use the center of each edge as a waypoint, which gives you a functional but not very pretty curve to follow.

There are a few different ways to make it prettier. I usually "relax" the curve (not sure what the correct terminology is here) by, going backwards from the goal, moving the waypoints along their corresponding edges to minimize the distance to the next waypoint. I.e. the last node before the goal is moved to minimize the distance to the goal, the next-to last is moved to minimize the distance to the last waypoint, and so on...

Finding the point with the minimal distance is equivalent to projecting a point (the goal/next waypoint) onto a line segment (edge). Stack Overflow has a few answers on this, Shortest distance between a point and a line segment for example.

Note: this assumes that all navmesh polygons are convex (which they should be and hopefully are) because then we can exploit that, by definition, all paths between to points on the edge are entirely inside the polygon. Meaning we don't have to care at all about making sure the path is valid when moving the points on along edges (this time assuming obstacles are handled elsewere).

You say you know how to generate a path of polygons to reach the goal. Then you must also know the edges you will cross, and may use this to build an actual walking path. A simple way of doing that would be to use the center of each edge as a waypoint, which gives you a functional but not very pretty curve to follow.

There are a few different ways to make it prettier. I usually "relax" the curve (not sure what the correct terminology is here) by, going backwards from the goal, moving the waypoints along their corresponding edges to minimize the distance to the next waypoint. I.e. the last node before the goal is moved to minimize the distance to the goal and so on...

This assumes that all navmesh polygons are convex (which they should be and hopefully are) because then we can exploit that, by definition, all paths between to points on the edge are entirely inside the polygon. Meaning we don't have to care at all about making sure the path is valid when moving the points on along edges (this time assuming obstacles are handled elsewere).

You say you know how to generate a path of polygons to reach the goal. Then you must also know the edges you will cross, and may use this to build an actual walking path. A simple way of doing that would be to use the center of each edge as a waypoint, which gives you a functional but not very pretty curve to follow.

There are a few different ways to make it prettier. I usually "relax" the curve (not sure what the correct terminology is here) by, going backwards from the goal, moving the waypoints along their corresponding edges to minimize the distance to the next waypoint. I.e. the last node before the goal is moved to minimize the distance to the goal, the next-to last is moved to minimize the distance to the last waypoint, and so on...

Finding the point with the minimal distance is equivalent to projecting a point (the goal/next waypoint) onto a line segment (edge). Stack Overflow has a few answers on this, Shortest distance between a point and a line segment for example.

Note: this assumes that all navmesh polygons are convex (which they should be and hopefully are) because then we can exploit that, by definition, all paths between to points on the edge are entirely inside the polygon. Meaning we don't have to care at all about making sure the path is valid when moving the points on along edges (this time assuming obstacles are handled elsewere).

You say you know how to generate a path of polygons to reach the goal. Then you must also know the edges you will cross, and may use this to build an actual walking path. A simple way of doing that would be to use the center of each edge as a waypoint, which gives you a functional but not very pretty curve to follow.

There are a few different ways to make it prettier. I usually "relax" the curve (not sure what the correct terminology is here) by moving the waypoints along their corresponding edges to minimize the distance to the previous waypoint going backwards from the goal.

This assumes that all navmesh polygons are convex (which they should be and hopefully are) because then we can exploit that, by definition, all paths between to points on the edge are entirely inside the polygon. Meaning we don't have to care at all about making sure the path is valid when moving the points on along edges (this time assuming obstacles are handled elsewere).

You say you know how to generate a path of polygons to reach the goal. Then you must also know the edges you will cross, and may use this to build an actual walking path. A simple way of doing that would be to use the center of each edge as a waypoint, which gives you a functional but not very pretty curve to follow.

There are a few different ways to make it prettier. I usually "relax" the curve (not sure what the correct terminology is here) by, going backwards from the goal, moving the waypoints along their corresponding edges to minimize the distance to the next waypoint. I.e. the last node before the goal is moved to minimize the distance to the goal and so on...

This assumes that all navmesh polygons are convex (which they should be and hopefully are) because then we can exploit that, by definition, all paths between to points on the edge are entirely inside the polygon. Meaning we don't have to care at all about making sure the path is valid when moving the points on along edges (this time assuming obstacles are handled elsewere).