Path finding - e-ucm/ead GitHub Wiki

Illustrated example

The illustrated example shows the general path-finding algorithm.

Node expansion is the only "original" part, and is based on the observation that the only significant nodes in an optimal path within a polygon are start, finish, and polygon vertices. Using this observation, we can construct an optimal path from start to finish without having to build a full mesh.

The decision of which nodes to expand follows the time-honoured A* algorithm‎, using euclidean distance as the heuristic.

Perspective

When perspective is present, certain distances are larger than they appear. Perspective results in an 3x3 transformation matrix using homogeneous coordinates: the viewToWorld matrix. If no perspective is desired, the identity matrix can be used.

Before path-finding starts, the path polygon is transformed "world" coordinates by applying viewToWorld. Both start and finish points are also transformed to world coordinates. Path-finding is performed on world-coordinates (thus guaranteeing "world-minimal" paths), and the resulting path is transformed back to view-coordinates (using the inverse of viewToWorld, unsurprisignly named worldToView) for display.