The funnel algorithm creates a piecewise linear path where each segment of the path is delimited by polygon boundaries (i.e., interior edges). In some scenarios, a series of such line segments are actually co-linear and it is some distance away that an actual turn enters the scenario. This is a simple implementation and guarantees a collision-free path, but it has an issue.
If, for dynamic reasons, the agent is not able to cross the interior edge at the point on the funnel path, the agent will have an irrational desire to cross at that point. This leads to unnatural behavior (particularly for agents that lack the ability to use the full PreferredVelocity which would account for the portal width).
It is impractical to attempt to get every agent type to be able to reason about PreferredVelocity properly. So, that means the path itself should be smarter.
Proposal:
Coalesce colinear segments in the funnel path so that it only hinges on true direction changes. As the agent veers off to the side, it can cross the portal in a different direction.
Challenge: in this case, it is possible for the line segment connecting the current agent position to the next turning point to intersect an obstacle (the straight-line path is not collision free). We would have to do a test at every time step to see if the current path direction passes safely through the next portal.
If the next turning point is in the next portal, it should trivially be true by construction.
Otherwise, if the line intersects the portal with sufficient clearance, it is true.
Finally, if it doesn't intersect the portal with enough clearance (or at all), the path should be broken to turn at the nearest point in the next portal that provides clearance.
NOTE: this still does not solve the problem where the next portal already has a turning point and the agent can't get to it. The flipside of this idea is to look forward as well. So, more generally, the goal would be to add and remove turning points dynamically to account for drift due to dynamic limitations in following the static path.
The funnel algorithm creates a piecewise linear path where each segment of the path is delimited by polygon boundaries (i.e., interior edges). In some scenarios, a series of such line segments are actually co-linear and it is some distance away that an actual turn enters the scenario. This is a simple implementation and guarantees a collision-free path, but it has an issue.
If, for dynamic reasons, the agent is not able to cross the interior edge at the point on the funnel path, the agent will have an irrational desire to cross at that point. This leads to unnatural behavior (particularly for agents that lack the ability to use the full
PreferredVelocitywhich would account for the portal width).It is impractical to attempt to get every agent type to be able to reason about
PreferredVelocityproperly. So, that means the path itself should be smarter.Proposal:
Coalesce colinear segments in the funnel path so that it only hinges on true direction changes. As the agent veers off to the side, it can cross the portal in a different direction.
Challenge: in this case, it is possible for the line segment connecting the current agent position to the next turning point to intersect an obstacle (the straight-line path is not collision free). We would have to do a test at every time step to see if the current path direction passes safely through the next portal.
NOTE: this still does not solve the problem where the next portal already has a turning point and the agent can't get to it. The flipside of this idea is to look forward as well. So, more generally, the goal would be to add and remove turning points dynamically to account for drift due to dynamic limitations in following the static path.