236
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Specification"
Jump to navigation
Jump to search
SCI/FreeSCI/Pathfinding/Specification (view source)
Revision as of 00:42, 1 February 2009
, 00:42, 1 February 2009Added images. Page done
(Merging of the FreeSCI Pathfinding documentation. Work in progress.) |
(Added images. Page done) |
||
| (6 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
In this section we give a formal specification of the AvoidPath kernel function. | In this section we give a formal specification of the AvoidPath kernel function. | ||
This function computes a path from a start point to an end point, avoiding a set of polygons. We start out by formalizing the main notions from | This function computes a path from a start point to an end point, avoiding a set of polygons. We start out by formalizing the main notions from [[SCI/FreeSCI/Pathfinding/Patent#Sierra.27s_pathfinding_patent|Sierra's pathfinding patent]] section. | ||
A point v is a position in the plane. Let < | A point v is a position in the plane. Let <i>x(v)</i> denote the x–coordinate of <i>v</i> and <i>y(v)</i> the y–coordinate of <i>v</i>. | ||
A path is a list of points (v<sub>0</sub> , …, v<sub>n</sub> ) and a polygon is a closed path. We now define the near point: | A path is a list of points (v<sub>0</sub> , …, v<sub>n</sub> ) and a polygon is a closed path. We now define the near point: | ||
| Line 10: | Line 10: | ||
;Definition 1 : Let <i>P</i> be a polygon and p be a point. Let <i>E</i> be the set of edges of <i>P</i> that do not lie along the display border. The near point of <i>p</i> is a point at minimal distance from p that lies on an edge in <i>E</i>. | ;Definition 1 : Let <i>P</i> be a polygon and p be a point. Let <i>E</i> be the set of edges of <i>P</i> that do not lie along the display border. The near point of <i>p</i> is a point at minimal distance from p that lies on an edge in <i>E</i>. | ||
: There are four different types of polygons, as described in | : There are four different types of polygons, as described in [[SCI/FreeSCI/Pathfinding/Semantics#Polygon_types|Polygon types]] section. We now formalize the constraints the polygon types impose on the path that is to be computed. We start with the barred access polygon. If the start point is contained in the polygon we use the semantics used by later versions of Sierra SCI, i.e . the path must leave the polygon immediately via the near point. This way the traversal through the polygon is minimal. | ||
;Definition 2 : Let <i>P</i> be a barred access polygon. If the start point s is contained in <i>P</i> the path must immediately exit the polygon via the near point of <i>s</i>. Except for that edge, the path may not intersect the inside of <i>P</i>. If the end point <i>t</i> is contained in <i>P</i> the path must end at the near point of <i>t</i>, instead of <i>t</i>. | ;Definition 2 : Let <i>P</i> be a barred access polygon. If the start point s is contained in <i>P</i> the path must immediately exit the polygon via the near point of <i>s</i>. Except for that edge, the path may not intersect the inside of <i>P</i>. If the end point <i>t</i> is contained in <i>P</i> the path must end at the near point of <i>t</i>, instead of <i>t</i>. | ||
| Line 30: | Line 30: | ||
;Definition 6 : Let <i>P</i> be a polygon. If <i>P</i> is a contained access polygon then the barred area of <i>P</i> consists of the edges of <i>P</i> and the area outside of <i>P</i>. If <i>P</i> is not a contained access polygon then the barred area of <i>P</i> consists of the edges of <i>P</i> and the area inside of <i>P</i>. | ;Definition 6 : Let <i>P</i> be a polygon. If <i>P</i> is a contained access polygon then the barred area of <i>P</i> consists of the edges of <i>P</i> and the area outside of <i>P</i>. If <i>P</i> is not a contained access polygon then the barred area of <i>P</i> consists of the edges of <i>P</i> and the area inside of <i>P</i>. | ||
:We proceed by formalizing the two assumptions from | :We proceed by formalizing the two assumptions from [[SCI/FreeSCI/Pathfinding/Semantics#Polygon_types|Polygon types]] section. | ||
:;Assumption 1 : All polygons in the polygon set are not self-intersecting. | :;<span id="assumption_1">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="assumption_2">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. | ||
::'''Specification 1''' CONTAINED(</ | ::'''Specification 1''' CONTAINED(<i>v</i>, <i>P</i> ) | ||
::Input: | ::Input: | ||
::* Apointv | ::* Apointv | ||
::* ApolygonP | ::* ApolygonP | ||
::Output: true when <i>v</i> is contained in <i>P</i>, false otherwise. | ::Output: true when <i>v</i> is contained in <i>P</i>, false otherwise. | ||
| 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. | ||
| Line 62: | Line 64: | ||
;Definition 8 : Let <i>S</i> be the polygon set. Let <i>s</i> be the start point and t be the end point. Let <i>I</i> be the set of intersection points of the line (<i>s</i>, <i>t</i>) and the polygons in <i>S</i>. The blocking point of <i>(s, t) wrt S</i> is the point <i>p ∈ I</i> closest to <i>s</i> for which the line (<i>t</i>, <i>p</i>) intersects the inside of the polygon at <i>p</i>. | ;Definition 8 : Let <i>S</i> be the polygon set. Let <i>s</i> be the start point and t be the end point. Let <i>I</i> be the set of intersection points of the line (<i>s</i>, <i>t</i>) and the polygons in <i>S</i>. The blocking point of <i>(s, t) wrt S</i> is the point <i>p ∈ I</i> closest to <i>s</i> for which the line (<i>t</i>, <i>p</i>) intersects the inside of the polygon at <i>p</i>. | ||
:[[Image:Pathfinding-figure11.png|frame|Figure 11: Path from <i>s</i> to <i>t</i> as computed by KeyboardPath.|center]] | |||
:Figure 11 shows an example of a path computed by this sub-function. The blocking point <i>s′</i> is determined and then <tt>ShortestPath</tt> is used to compute the portion of the path from <i>s′</i> to <i>t</i>. This leads to the following specification: | :Figure 11 shows an example of a path computed by this sub-function. The blocking point <i>s′</i> is determined and then <tt>ShortestPath</tt> is used to compute the portion of the path from <i>s′</i> to <i>t</i>. This leads to the following specification: | ||