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

SCI/FreeSCI/Pathfinding/Specification (view source)

Revision as of 10:15, 30 January 2009

248 bytes added , 10:15, 30 January 2009

@@ Line 2: / Line 2: @@
 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 Section 2.2.
+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 [[http://wiki.scummvm.org/index.php/SCI/FreeSCI/Pathfinding/Patent#Sierra.27s_pathfinding_patent| Sierra's pathfinding patent]] section.
 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>.
@@ 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>.
-: There are four different types of polygons, as described in Section 3.1. 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.
+: 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>.
@@ 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>.
-:We proceed by formalizing the two assumptions from Section 3.1.
+:We proceed by formalizing the two assumptions from [[SCI/FreeSCI/Pathfinding/Semantics#Polygon_types|Polygon types]] section.
 :;<span id="assumption_1">Assumption 1</span> : All polygons in the polygon set are not self-intersecting.