245
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Specification"
Jump to navigation
Jump to search
m
SCI/FreeSCI/Pathfinding/Specification (view source)
Revision as of 02:52, 30 January 2009
, 02:52, 30 January 2009Added name anchors for linking
m (oops, wrote <u> instead <i>) |
m (Added name anchors for linking) |
||
| Line 32: | Line 32: | ||
:We proceed by formalizing the two assumptions from Section 3.1. | :We proceed by formalizing the two assumptions from Section 3.1. | ||
:;Assumption 1 : All polygons in the polygon set are not self-intersecting. | :;<span id="anchor_name">Assumption 1</span> : All polygons in the polygon set are not self-intersecting. | ||
:;Assumption 2 : Let <i>S</i> be the polygon set. For all points <i>p</i> there is at most one polygon <i>P</i> in <i>S</i> for which <i>p</i> is contained in the barred area of <i>P</i>. | :;<span id="anchor_name">Assumption 2</span> : Let <i>S</i> be the polygon set. For all points <i>p</i> there is at most one polygon <i>P</i> in <i>S</i> for which <i>p</i> is contained in the barred area of <i>P</i>. | ||
::We now specify the sub-functions of <tt>AvoidPath</tt>. The first sub-function is Contained. | ::We now specify the sub-functions of <tt>AvoidPath</tt>. The first sub-function is Contained. | ||
| Line 56: | Line 56: | ||
:Output: A shortest path from <i>s</i> to <i>t</i> that does not violate the constraints imposed by any polygon in <i>S</i>. | :Output: A shortest path from <i>s</i> to <i>t</i> that does not violate the constraints imposed by any polygon in <i>S</i>. | ||
:The third sub-function <tt>KeyboardPath</tt> computes a path for keyboard support. This is not a true sub-function of <tt>AvoidPath</tt>, but we treat it as such to simplify our presentation. The semantics are described in Section 3.2. As computing the entire path as in Figure 1 would be in conflict with claim 6 of the patent, we are forced to change the semantics. Instead of using the patented method, we only compute the first edge of this path and use <tt>ShortestPath</tt> for the remainder of the path. As the games only use the first edge this works fine in practice. This first edge ends in what we call the blocking point. | :The third sub-function <tt>KeyboardPath</tt> computes a path for keyboard support. This is not a true sub-function of <tt>AvoidPath</tt>, but we treat it as such to simplify our presentation. The semantics are described in Section 3.2. As computing the entire path as in Figure 1 would be in conflict with claim 6 of the patent, we are forced to change the semantics. Instead of using the patented method, we only compute the first edge of this path and use <tt>ShortestPath</tt> for the remainder of the path. | ||
:As the games only use the first edge this works fine in practice. This first edge ends in what we call the blocking point. | |||
:It is tempting to define the blocking point as the first intersection that is encountered when travelling the direct trajectory from start point to end point. | :It is tempting to define the blocking point as the first intersection that is encountered when travelling the direct trajectory from start point to end point. | ||