Funnel AlgorithmEdit
The funnel algorithm is a practical method for computing the shortest path through a corridor in a polygonal environment. It is widely used in real-time pathfinding for agents operating in environments represented as navmeshes or simple polygons. By “pulling” a string taut through a sequence of portals, the algorithm yields a smooth, efficient route that respects the geometry of the space. This makes it a staple in modern pathfinding systems found in video games and in certain robotics applications, where predictable performance and deterministic results matter.
In essence, the funnel algorithm turns the problem of finding a path from a start point to a goal into a sequence of decisions about a widening and narrowing funnel as you move through a chain of portals. Each portal represents a boundary between adjacent convex regions in a navigation mesh or a corridor of connected polygons. The outcome is a polyline that lies along the edges of the corridor and is guaranteed to be a shortest path within that corridor, even if it is not the absolute shortest path in the unrestricted plane. The technique is closely related to the idea of string pulling, hence the alternative name often used in literature string-pulling.
What makes the funnel algorithm appealing is its balance of simplicity and speed. Once the corridor is established, the algorithm operates in linear time with respect to the number of portals, and it uses only a small, constant amount of state beyond the growing path. This makes it well suited to run in real-time environments where agents must react quickly to changes or updates in the environment, as is common in video games and certain robotics scenarios. The approach also scales well to 2D and, with careful adaptation, to 3D navmeshes, where portals can be thought of as cross-sections between adjacent regions.
Below are the core concepts and steps that underpin the funnel algorithm.
Fundamentals
Portal chain: The sequence of boundaries (portals) that connect adjacent convex regions along the agent’s route through the environment. Each portal typically has two endpoints, forming a left and a right edge as seen from the agent’s perspective.
Apex point: The current anchor point of the funnel. When the path determined by the funnel is updated, the apex moves forward along the path as needed.
Left and right funnel edges: The two boundary edges emanating from the apex that bound the feasible region for the remaining path. These edges are updated as new portals are processed.
The corridor: The geometric region formed by the chain of portals. The funnel algorithm guarantees the resulting path stays within this corridor.
Portals: The edges or shared boundaries that define the transition between adjacent polygons in a navigation mesh or polygonal decomposition. Portals are central to many pathfinding pipelines, bridging high-level route planning with low-level geometry.
Shortest path within the corridor: The objective is to produce the path that minimizes length while lying inside the corridor defined by the portals; in practice this is the shortest feasible route given the corridor constraints.
Related techniques: The funnel algorithm sits beside other methods in the toolbox of pathfinding, such as A*-based search, path smoothing, and alternative variants like more general strip-pulling approaches.
Algorithmic Outline
Initialization: Start with the agent’s position as the apex and consider the first portal in the chain. The initial left and right edges bound the feasible region for the remainder of the path.
Portal processing: For each subsequent portal, project its left and right endpoints into the funnel’s frame and update the left and right edges accordingly. If a new endpoint lies outside the current funnel, the corresponding edge is tightened toward the apex, and the apex is advanced to the point where the path can safely progress.
Edge crossing: When the left and right edges cross, the path to the apex is finalized up to the crossing point, and the algorithm resets with a new apex at that point. The remaining portals then form a new funnel segment to continue toward the goal.
Path extraction: The sequence of apex updates forms the polyline that constitutes the final path. This path is guaranteed to be the shortest path that lies within the corridor defined by the portal chain.
Complexity: The typical performance is O(n) time, where n is the number of portals in the chain, with constant extra memory beyond the computed path. This efficiency is particularly valuable in real-time environments and is one reason why the funnel algorithm is standard in many pathfinding pipelines.
Practical notes: In practice, the geometry of the corridor and the precision of numerical calculations can influence behavior at tight corners or degenerate portals. Robust implementations address these edge cases to maintain consistent performance and a stable path.
Applications and Variants
Real-time games: The funnel algorithm is a core component of navmesh-based AI, helping agents navigate complex worlds smoothly and efficiently while avoiding unnecessary zig-zagging. It frequently appears in systems that also use A* for initial path discovery and then apply the funnel for path refinement.
Robotics and simulation: In planar robotics and crowd simulation, the method provides a reliable way to route agents through polygonal environments, balancing speed and path quality. It is often paired with higher-level planners and works well when the environment is decomposed into convex regions.
2D versus 3D: In 2D, portals are straightforward line segments between adjacent regions. Extending the funnel idea to 3D requires handling portal surfaces or cross-sections and can introduce additional complexity, but the core principle of pulling a string through a chain of boundaries remains intact.
Alternatives and complements: Some practitioners pair the funnel algorithm with post-processing steps such as path smoothing to further reduce unnecessary turning or with alternative heuristics like Theta* for more direct routes when appropriate. In dynamic environments, re-running the funnel algorithm on updated portal chains is common practice.
Open-source and industry use: Given its simplicity and robustness, the funnel algorithm is widely implemented across game engines and simulation frameworks, often in conjunction with standard libraries for linear algebra and geometry. Its predictability makes it appealing for teams prioritizing stability and performance.