Difference between revisions of "SCI/FreeSCI/Pathfinding/Patent"

We now proceed with describing the pathfinding phase, limiting ourselves to the most important aspects. The basic idea behind the algorithm is to construct a path that follows the direct trajectory from start point to end point, except where the trajectory properly intersects a polygon (this is covered by claim 6 of the patent). If the direct trajectory properly intersects a polygon <i>P</i>, then there must be more than one intersection point. Let <i>p</i> be the intersection point closest to the start point, and <i>q</i> be the intersection point closest to the end point. The computed path reaches <i>p</i> on the direct trajectory, then goes from <i>p</i> to <i>q</i> along the edges of the polygon and then resumes the direct trajectory. There are two ways to walk from <i>p</i> to <i>q</i>; the algorithm takes the shortest one. Optimization level 0 returns such a path, as illustrated in the following figure.

We now proceed with describing the pathfinding phase, limiting ourselves to the most important aspects. The basic idea behind the algorithm is to construct a path that follows the direct trajectory from start point to end point, except where the trajectory properly intersects a polygon (this is covered by claim 6 of the patent). If the direct trajectory properly intersects a polygon <i>P</i>, then there must be more than one intersection point. Let <i>p</i> be the intersection point closest to the start point, and <i>q</i> be the intersection point closest to the end point. The computed path reaches <i>p</i> on the direct trajectory, then goes from <i>p</i> to <i>q</i> along the edges of the polygon and then resumes the direct trajectory. There are two ways to walk from <i>p</i> to <i>q</i>; the algorithm takes the shortest one. Optimization level 0 returns such a path, as illustrated in the following figure.