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 10:15, 30 January 2009
, 10:15, 30 January 2009More linkify
m (Anchors fixed again) |
(More linkify) |
||
| 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 [[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>. | 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>. | ;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. | ||
:;<span id="assumption_1">Assumption 1</span> : 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. | ||