245
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Semantics"
Jump to navigation
Jump to search
SCI/FreeSCI/Pathfinding/Semantics (view source)
Revision as of 00:36, 1 February 2009
, 00:36, 1 February 2009Added images, linkify section references. Page done.
(Added images.) |
(Added images, linkify section references. Page done.) |
||
| Line 4: | Line 4: | ||
We performed most of the tests with the <tt>experimentator</tt> tool, developed by Christoph Reichenbach. This tool takes a polygon set description in text format, and transforms it into an SCI program that can be run both with Sierra SCI and with FreeSCI. The program draws the polygon set on the display and allows the user to select a start and destination point. It then calls AvoidPath and draws the returned path on the display. This has proven to be invaluable for discovering the semantics of AvoidPath. We used slightly modified versions of this tool for experimenting with the containment test sub-function and keyboard support. | We performed most of the tests with the <tt>experimentator</tt> tool, developed by Christoph Reichenbach. This tool takes a polygon set description in text format, and transforms it into an SCI program that can be run both with Sierra SCI and with FreeSCI. The program draws the polygon set on the display and allows the user to select a start and destination point. It then calls AvoidPath and draws the returned path on the display. This has proven to be invaluable for discovering the semantics of AvoidPath. We used slightly modified versions of this tool for experimenting with the containment test sub-function and keyboard support. | ||
We discuss the different polygon types in Polygon types section and the special treatment of the display border in Display border and Containment test sections describes the semantics of the containment test sub-function. Finally, we give the results of SCI vertex ordering tests in the Vertex ordering section. | We discuss the different polygon types in [[SCI/FreeSCI/Pathfinding/Semantics#Polygon types|Polygon types]] section and the special treatment of the display border in [[SCI/FreeSCI/Pathfinding/Semantics#Display_border|Display border]] and [[SCI/FreeSCI/Pathfinding/Semantics#Containment_test|Containment test]] sections describes the semantics of the containment test sub-function. Finally, we give the results of SCI vertex ordering tests in the [[SCI/FreeSCI/Pathfinding/Semantics#Vertex_ordering|Vertex ordering]] section. | ||
==Polygon types== | ==Polygon types== | ||
| Line 29: | Line 29: | ||
Even though the mouse is the main method for moving Ego in SCI1, the games still have keyboard support. This keyboard support exhibits the same behaviour as in SCI0. That is, after the user presses a directional key Ego will move in that direction until he bumps into an object, at which point he will stop. As the user has only indicated a direction, it is impossible to know to what exact location the user wants Ego to go. No attempts to avoid obstacles are made. | Even though the mouse is the main method for moving Ego in SCI1, the games still have keyboard support. This keyboard support exhibits the same behaviour as in SCI0. That is, after the user presses a directional key Ego will move in that direction until he bumps into an object, at which point he will stop. As the user has only indicated a direction, it is impossible to know to what exact location the user wants Ego to go. No attempts to avoid obstacles are made. | ||
The games implement this by calling AvoidPath with the optimization level set to 0. The end point is chosen in such a way that it is outside of the display and exactly in the direction the user has indicated. For example, if Ego is positioned at coordinates (100, 100) and the user presses left; the end point might be (-10000, 100). Optimization level 0 is perfect for implementing this functionality as the returned path will move along the direct trajectory from start point to end point until the first obstacle is encountered (see Figure | The games implement this by calling AvoidPath with the optimization level set to 0. The end point is chosen in such a way that it is outside of the display and exactly in the direction the user has indicated. For example, if Ego is positioned at coordinates (100, 100) and the user presses left; the end point might be (-10000, 100). Optimization level 0 is perfect for implementing this functionality as the returned path will move along the direct trajectory from start point to end point until the first obstacle is encountered (see Figure 1). The games simply take the first two points of the returned path and throw away the rest. | ||
Setting the optimization flag to 0 also causes AvoidPath to make two changes to the polygon set. The first change is that total access polygons are removed. The second is that near-point access polygons are turned into total access polygon. A likely reason for removing total access polygons is to prevent Ego from bumping into such a polygon as if it were an obstacle. Total access polygons are used to bar off special areas and prevent pathfinding from accidentally directing Ego into such an area. However, when the user directs Ego into such an area with the keyboard there is no reason to avoid the area. | Setting the optimization flag to 0 also causes AvoidPath to make two changes to the polygon set. The first change is that total access polygons are removed. The second is that near-point access polygons are turned into total access polygon. A likely reason for removing total access polygons is to prevent Ego from bumping into such a polygon as if it were an obstacle. Total access polygons are used to bar off special areas and prevent pathfinding from accidentally directing Ego into such an area. However, when the user directs Ego into such an area with the keyboard there is no reason to avoid the area. | ||
| Line 37: | Line 37: | ||
==Display border== | ==Display border== | ||
As mentioned in [[SCI/FreeSCI/Pathfinding/Patent#Sierra.27s_pathfinding_patent|Sierra's pathfinding patent]] section, polygon edges along the display border should not be part of the path that is returned by AvoidPath. We determined that this also goes for vertices along the display border, as illustrated in Figure | |||
[[Image:Pathfinding-figure09.png|frame|Figure 9: A barred access polygon that touches the display border and a path computed for start point <i>s</i> and end point <i>t</i>.|center]] | |||
[[Image:Pathfinding-figure10.png|frame|Figure 10: A barred access polygon that touches the display border and a path computed for start point <i>s</i> and end point <i>t</i>.|center]] | |||
As mentioned in [[SCI/FreeSCI/Pathfinding/Patent#Sierra.27s_pathfinding_patent|Sierra's pathfinding patent]] section, polygon edges along the display border should not be part of the path that is returned by AvoidPath. We determined that this also goes for vertices along the display border, as illustrated in Figure 9. The dotted line shows the path that would have been taken if the polygon were not touching the display border. We also determined that polygon edges along the display border are ignored when it comes to computing the near point. This is illustrated in Figure 10. t′′′ is the near point in this case and not t′ or t′′, even though both are closer to t than t′′′ is. | |||
==Containment test== | ==Containment test== | ||