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

Jump to navigation Jump to search

SCI/FreeSCI/Pathfinding/Implementation (view source)

Revision as of 10:32, 30 January 2009

599 bytes added ,  10:32, 30 January 2009
Fix broken links, the SVN is not working anymore. Beautify link in reference
(Added name anchor for linking)
(Fix broken links, the SVN is not working anymore. Beautify link in reference)
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Implementation=
=Implementation=
In this chapter we discuss the more important aspects of the implementation. In Section 6.1 we discuss the data types we used. Section 6.2 has some details on basic geometry functions and how they were used in the implementation. Some details on the implementation of the path-finding functionality can be found in Section 6.3. And Section 6.4 discusses the issue of rounding real numbers to integers.
In this chapter we discuss the more important aspects of the implementation. In Section ''Data types'' we discuss the data types we used. Section ''Basic geometry'' has some details on basic geometry functions and how they were used in the implementation. Some details on the implementation of the path-finding functionality can be found in Section ''Pathfinding''. And Section ''Rounding read numbers'' discusses the issue of rounding real numbers to integers.


This report does not contain the actual program text that we produced. The program text is spread across the following four files that can be found on-line:
This report does not contain the actual program text that we produced. The program text is spread across the following four files that can be found on-line:
* http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/engine/kpathing.c?op=file&rev=1571&sc=0
* [http://void.cs.colorado.edu/cgi-bin/darcsweb.cgi?r=glutton;a=annotate_shade;h=20060520133532-00091-969972be3900210a314816cfff729940128ac439.gz;f=src/engine/kpathing.c src/engine/kpathing.c] <!-- revision 1571 -->
* http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/scicore/aatree.c?op=file&rev=1571&sc=0
* [http://void.cs.colorado.edu/cgi-bin/darcsweb.cgi?r=glutton;a=annotate_shade;h=20060520133532-00091-969972be3900210a314816cfff729940128ac439.gz;f=src/scicore/aatree.c src/scicore/aatree.c] <!--revision 1571) -->
* http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/include/aatree.h?op=file&rev=1571&sc=0
* [http://void.cs.colorado.edu/cgi-bin/darcsweb.cgi?r=glutton;a=annotate_shade;h=20060520133532-00091-969972be3900210a314816cfff729940128ac439.gz;f=src/include/aatree.h src/include/aatree.h] <!-- revision 1571 -->
* http://svn.a-eskwadraat.nl/wsvn/FreeSCI/freesci/branches/glutton/src/include/list.h?op=file&rev=1571&sc=0
* [http://void.cs.colorado.edu/cgi-bin/darcsweb.cgi?r=glutton;a=annotate_shade;h=20060520133532-00091-969972be3900210a314816cfff729940128ac439.gz;f=src/include/list.h src/include/list.h] <!-- revision 1571 -->


==Data types==
==Data types==
Line 13: Line 13:
A potential pitfall here is overflow. However, in our case this is not a big problem as FreeSCI is written for machines with an integer size of at least 32 bits and the integer size in SCI is only 16 bits.
A potential pitfall here is overflow. However, in our case this is not a big problem as FreeSCI is written for machines with an integer size of at least 32 bits and the integer size in SCI is only 16 bits.


The two main choices for the polygon data type are an array of vertices, or a circular list of vertices. Arrays are convenient when vertices of a polygon are processed sequentially, but this is not the case here as the visibility graph algorithm processes the vertices by angle. Therefore we chose lists instead of arrays. As C does not provide any built-in list data types we took and modified the list macros from FreeBSD’s queue.h header file <ref>The FreeBSD Project, FreeBSD source code file queue.h, revision
The two main choices for the polygon data type are an array of vertices, or a circular list of vertices. Arrays are convenient when vertices of a polygon are processed sequentially, but this is not the case here as the visibility graph algorithm processes the vertices by angle. Therefore we chose lists instead of arrays. As C does not provide any built-in list data types we took and modified the list macros from FreeBSD’s queue.h header file <ref>The FreeBSD Project, [http://www.freebsd.org/cgi/cvsweb.cgi/~checkout~/src/sys/sys/queue.h?rev=1.66&content-type=text/plain FreeBSD source code file queue.h], revision
1.66, http://www.freebsd.org/cgi/cvsweb.cgi/~checkout~/src/sys/sys/queue.h?rev=1.66&content-type=text/plain, 2006.</ref>. We decided to order the vertices in such a way that the barred area is always left of an edge. That means that barred, total and near-point access polygons use anticlockwise ordering, and contained access polygons use clockwise ordering. As we have seen in Section 3.5, SCI games do not have such a fixed vertex ordering, so we added code to detect the current vertex ordering, and reverse it if necessary.
1.66, 2006.</ref>. We decided to order the vertices in such a way that the barred area is always left of an edge. That means that barred, total and near-point access polygons use anticlockwise ordering, and contained access polygons use clockwise ordering. As we have seen in Section 3.5, SCI games do not have such a fixed vertex ordering, so we added code to detect the current vertex ordering, and reverse it if necessary.


For the balanced search tree required for the visibility graph algorithm we implemented an Andersson tree <ref>A. Andersson. Balanced Search Trees Made Simple, Third Workshop on Algorithms and Data Structures, pp 60-71, Springer-Verlag, 1993, ISBN 3540571558.</ref>. Andersson trees are easier to implement than other BB-trees yet offer similar performance. For storing the visibility graph itself we decided to use an adjacency matrix.
For the balanced search tree required for the visibility graph algorithm we implemented an Andersson tree <ref>A. Andersson. Balanced Search Trees Made Simple, Third Workshop on Algorithms and Data Structures, pp 60-71, Springer-Verlag, 1993, ISBN 3540571558.</ref>. Andersson trees are easier to implement than other BB-trees yet offer similar performance. For storing the visibility graph itself we decided to use an adjacency matrix.
Line 25: Line 25:
These functions are the foundation for implementing some of the more complex functions. We give several examples in the remainder of this section.
These functions are the foundation for implementing some of the more complex functions. We give several examples in the remainder of this section.


Given two edges (<i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>) and (<i>p<sub>1</sub></i>, <i>p<sub>2</sub></i>) we use Left to detect the convexity of the vertex at <i>p<sub>1</sub></i>. Namely, the vertex at <i>p<sub>1</sub></i> is convex if Left(<i>p<sub>0</sub></i>, <i>p<sub>1</sub></i> , <i>p<sub>2</sub></i>). This relies on a fixed vertex ordering as described in Section 6.1.
Given two edges (<i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>) and (<i>p<sub>1</sub></i>, <i>p<sub>2</sub></i>) we use Left to detect the convexity of the vertex at <i>p<sub>1</sub></i>. Namely, the vertex at <i>p<sub>1</sub></i> is convex if Left(<i>p<sub>0</sub></i>, <i>p<sub>1</sub></i> , <i>p<sub>2</sub></i>). This relies on a fixed vertex ordering as described in section [[SCI/FreeSCI/Pathfinding/Implementation#Data types|Data types]].


As we described in Chapter 4, we need to compute the blocking point for keyboard support. The blocking point is the first intersection point <i>p</i> that is encountered when traveling the direct trajectory from start point <i>s</i> to end point <i>t</i> that has the property that the line (<i>t</i>, <i>p</i>) intersects the inside of the polygon that contains <i>p</i>, locally at <i>p</i>. We refer to this property as Inside(<i>p</i>, <i>t</i>). We make a case distinction on whether or not <i>p</i> lies exactly on a vertex. If <i>p</i> does not lie on a vertex it lies on exactly one edge (<i>p<sub>0</sub></i> , <i>p<sub>1</sub></i>). Because of the vertex ordering we know that the inside of the polygon is left of that edge. This implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p<sub>1</sub>, <i>t</i>). If <i>p</i> lies on a vertex there are two neighbouring vertices at <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i>. We now need to make another case distinction on the convexity of the vertex at <i>p</i> (using Left as demonstrated earlier in this section).
As we described in [[SCI/FreeSCI/Pathfinding/Specification|Specification]] chapter, we need to compute the blocking point for keyboard support. The blocking point is the first intersection point <i>p</i> that is encountered when traveling the direct trajectory from start point <i>s</i> to end point <i>t</i> that has the property that the line (<i>t</i>, <i>p</i>) intersects the inside of the polygon that contains <i>p</i>, locally at <i>p</i>. We refer to this property as Inside(<i>p</i>, <i>t</i>). We make a case distinction on whether or not <i>p</i> lies exactly on a vertex. If <i>p</i> does not lie on a vertex it lies on exactly one edge (<i>p<sub>0</sub></i> , <i>p<sub>1</sub></i>). Because of the vertex ordering we know that the inside of the polygon is left of that edge. This implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p<sub>1</sub>, <i>t</i>). If <i>p</i> lies on a vertex there are two neighbouring vertices at <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i>. We now need to make another case distinction on the convexity of the vertex at <i>p</i> (using Left as demonstrated earlier in this section).


If the vertex at <i>p</i> is convex that implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p</i>, <i>t</i>) and Left(<i>p</i>, <i>p<sub>1</sub></i> , <i>t</i>). If the vertex at <i>p</i> is not convex that implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p</i>, <i>t</i>) or Left(<i>p</i>, <i>p<sub>1</sub></i>, <i>t</i>).
If the vertex at <i>p</i> is convex that implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p</i>, <i>t</i>) and Left(<i>p</i>, <i>p<sub>1</sub></i> , <i>t</i>). If the vertex at <i>p</i> is not convex that implies that Inside(<i>p</i>, <i>t</i>) if Left(<i>p<sub>0</sub></i> , <i>p</i>, <i>t</i>) or Left(<i>p</i>, <i>p<sub>1</sub></i>, <i>t</i>).
Line 33: Line 33:
One of the steps in the visibility graph algorithm is the ordering by angle of vertices around a specific point <i>p</i>. The angle is 0 for points on the ray extending right from <i>p</i>, and increases clockwise. Let <i>&alpha;(q, p)</i> denote the angle (in degrees) of point <i>q</i> relative to point <i>p</i>. We used the <tt>Qsort</tt> POSIX function to do the ordering. This function calls a callback function for comparing two elements (in our case points). The arctangent function could be used here to compute the two angles, but this function is generally very slow. We chose a different solution that is outlined below.
One of the steps in the visibility graph algorithm is the ordering by angle of vertices around a specific point <i>p</i>. The angle is 0 for points on the ray extending right from <i>p</i>, and increases clockwise. Let <i>&alpha;(q, p)</i> denote the angle (in degrees) of point <i>q</i> relative to point <i>p</i>. We used the <tt>Qsort</tt> POSIX function to do the ordering. This function calls a callback function for comparing two elements (in our case points). The arctangent function could be used here to compute the two angles, but this function is generally very slow. We chose a different solution that is outlined below.


We partition the plane around p into two parts (we ignore the trivial partition <i>{p}</i> for which no angle can be determined). Partition A = <i>{(x, y) &#8712; &#8484;<sup>2</sup>|y < y(p)&#8744;(y = y(p)&#8743;x > x(p))}</i>, being the set of all points q for which <i>0 &#8804; &#945;(q,p) < 180</i>. Partition B <i>={(x,y) &#8712; &#8484;<sup>2</sup>|y > y(p)&#8744;(y = y(p)&#8743;x < x(p))}</i>, being the set of all points <i>q</i> for which <i>180 &#8804; &#945;(q, p) < 360</i>.
We partition the plane around <i>p</i> into two parts (we ignore the trivial partition <i>{p}</i> for which no angle can be determined). Partition A = <i>{(x, y) &#8712; &#8484;<sup>2</sup>|y < y(p)&#8744;(y = y(p)&#8743;x > x(p))}</i>, being the set of all points q for which <i>0 &#8804; &#945;(q,p) < 180</i>. Partition B <i>={(x,y) &#8712; &#8484;<sup>2</sup>|y > y(p)&#8744;(y = y(p)&#8743;x < x(p))}</i>, being the set of all points <i>q</i> for which <i>180 &#8804; &#945;(q, p) < 360</i>.


If the two points <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i> that are to be compared are not in the same partition the one in partition A is trivially at a smaller angle. Otherwise, <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i> are in the same partition. Two things have been accomplished by partitioning the plane in this way. The first is that Collinear(<i>p</i>, <i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>) holds if <i>&alpha;(p<sub>0</sub>, p) = &alpha;(p<sub>1</sub>, p)</i> (distance from <i>p</i> is the comparison criteria in this case). The second is that Left(<i>p</i>, <i>p<sub>0</sub></i> , <i>p<sub>1</sub> ) holds if <i>&#945;(p<sub>1</sub>, p) < &#945;(p<sub>0</sub> , p)</i>. We implemented the sorting by angle using Left and Collinear in this manner, thus avoiding the use of expensive trigonometry functions.
If the two points <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i> that are to be compared are not in the same partition the one in partition A is trivially at a smaller angle. Otherwise, <i>p<sub>0</sub></i> and <i>p<sub>1</sub></i> are in the same partition. Two things have been accomplished by partitioning the plane in this way. The first is that Collinear(<i>p</i>, <i>p<sub>0</sub></i>, <i>p<sub>1</sub></i>) holds if <i>&alpha;(p<sub>0</sub>, p) = &alpha;(p<sub>1</sub>, p)</i> (distance from <i>p</i> is the comparison criteria in this case). The second is that Left(<i>p</i>, <i>p<sub>0</sub></i> , <i>p<sub>1</sub> ) holds if <i>&#945;(p<sub>1</sub>, p) < &#945;(p<sub>0</sub> , p)</i>. We implemented the sorting by angle using Left and Collinear in this manner, thus avoiding the use of expensive trigonometry functions.
Line 40: Line 40:
The first step of <i>ShortestPath</i> is to check for both the start and end point whether it is contained in the barred area of any polygon in the polygon set <i>P</i>. If necessary, we then deal with this situation according to the specification in Chapter 4. If a start or end point <i>p</i> is contained in a total access polygon we remove that polygon from <i>P</i>. For other polygon types we compute the near point of <i>p</i> and use that for pathfinding instead. We add the original point <i>p</i> to the path during the post-processing phase. The only exception is the case where the end point is contained in the barred area of a barred or contained access polygon. In that case the path ends at the near point of <i>p</i>, rather than <i>p</i>.
The first step of <i>ShortestPath</i> is to check for both the start and end point whether it is contained in the barred area of any polygon in the polygon set <i>P</i>. If necessary, we then deal with this situation according to the specification in Chapter 4. If a start or end point <i>p</i> is contained in a total access polygon we remove that polygon from <i>P</i>. For other polygon types we compute the near point of <i>p</i> and use that for pathfinding instead. We add the original point <i>p</i> to the path during the post-processing phase. The only exception is the case where the end point is contained in the barred area of a barred or contained access polygon. In that case the path ends at the near point of <i>p</i>, rather than <i>p</i>.


We find the near point of <i>p</i> by first computing, for each edge e of <i>P</i>, the point on <i>e</i> that is closest to <i>p</i>. This is straightforward <ref>P. Bourke. Minimum Distance between a Point and a Line, http://astronomy.swin.edu.au/~pbourke/geometry/pointline/, 1988.</ref>. If <i>P</i> has <i>n</i> vertices this gives us <i>n</i> candidates. Out of all the candidates at minimal distance from <i>p</i> we randomly pick one as the near point.
We find the near point of <i>p</i> by first computing, for each edge e of <i>P</i>, the point on <i>e</i> that is closest to <i>p</i>. This is straightforward <ref>[http://astronomy.swin.edu.au/~pbourke/geometry/pointline/ P. Bourke. Minimum Distance between a Point and a Line], 1988.</ref>. If <i>P</i> has <i>n</i> vertices this gives us <i>n</i> candidates. Out of all the candidates at minimal distance from <i>p</i> we randomly pick one as the near point.


After the pre-processing step the start and end points are not strictly contained in the barred area of any of the polygons.
After the pre-processing step the start and end points are not strictly contained in the barred area of any of the polygons.
Timofonic
236

edits

Retrieved from "https://wiki.scummvm.org/index.php?title=Special:MobileDiff/10039...10055"

Navigation menu