245
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Patent"
SCI/FreeSCI/Pathfinding/Patent (view source)
Revision as of 03:57, 30 January 2009
, 03:57, 30 January 2009Fixed formatting
m (Convert the number section to the name, linkify it) |
m (Fixed formatting) |
||
| Line 22: | Line 22: | ||
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 v0to t cannot be taken as this would intersect polygon <i>W</i>. So the final path will go from <i>v<sub>0</sub></i> to <i>t</i> via <i>v<sub>1</sub></i>, even though it is much shorter to go there via <i>w<sub>0</sub></i>. Point <i>w<sub>0</sub></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 v0to t cannot be taken as this would intersect polygon <i>W</i>. So the final path will go from <i>v<sub>0</sub></i> to <i>t</i> via <i>v<sub>1</sub></i>, even though it is much shorter to go there via <i>w<sub>0</sub></i>. Point <i>w<sub>0</sub></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. | ||
==References== | ==References== | ||
<references /> | <references /> | ||