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 Figure 1.

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 Figure 1.

At optimization level 1 the algorithm tries to optimize this path. It does this by attempting to shortcut any two nodes. A shortcut is only possible if it does not properly intersect any polygon in the polygon set. See Figure 2 for an illustration of an optimized version of the path in Figure 1.

At optimization level 1 the algorithm tries to optimize this path. It does this by attempting to shortcut any two nodes. A shortcut is only possible if it does not properly intersect any polygon in the polygon set. See Figure 2 for an illustration of an optimized version of the path in Figure 1.

This raises the question of whether or not the algorithm is able to determine the shortest path for any input. This is not the case, as is demonstrated by the counterexample in Figure 4. The shortcut from <i>v₀</i> to <i>t</i> cannot be taken as this would intersect polygon <i>W</i>. So the final path will go from <i>v₀</i> to <i>t</i> via <i>v₁</i>, even though it is much shorter to go there via <i>w₀</i>. Point <i>w₀</i> is never considered for the path as it is part of a polygon that is not intersected by the direct trajectory from <i>s</i> to <i>t</i>. This illustrates that this algorithm does not guarantee a shortest path, even at the highest optimization level.

This raises the question of whether or not the algorithm is able to determine the shortest path for any input. This is not the case, as is demonstrated by the counterexample in Figure 4. The shortcut from <i>v₀</i> to <i>t</i> cannot be taken as this would intersect polygon <i>W</i>. So the final path will go from <i>v₀</i> to <i>t</i> via <i>v₁</i>, even though it is much shorter to go there via <i>w₀</i>. Point <i>w₀</i> is never considered for the path as it is part of a polygon that is not intersected by the direct trajectory from <i>s</i> to <i>t</i>. This illustrates that this algorithm does not guarantee a shortest path, even at the highest optimization level.

The patent further makes an important note about polygon edges that lie along the display border. It is undesirable to have the path use the display border unnecessarily as this might trigger the game into loading an adjoining game scene. In order to prevent the shortest path algorithm from using polygon edges that lie along the display border, the distance for such edges is defined to be infinity.

The patent further makes an important note about polygon edges that lie along the display border. It is undesirable to have the path use the display border unnecessarily as this might trigger the game into loading an adjoining game scene. In order to prevent the shortest path algorithm from using polygon edges that lie along the display border, the distance for such edges is defined to be infinity.