ToDo/Pathfinding/Semantics

Semantics

As the patent is not very precise when it comes to semantics, we performed a series of tests to get a more accurate picture of Sierra's implementation. The AvoidPath stub mentions an additional containment test sub-function and a fourth polygon type that the patent does not mention. We had to determine the semantics of those as well. It was also unclear how AvoidPath is used for the SCI0-style keyboard support still present in SCI1 games.

We performed most of the tests with the experimentator 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.

Polygon types

We performed a test with each of the three polygon types mentioned in the patent. The purpose was to see what the exact semantics are when the start or end point is inside such a polygon.

Figure 5: Three barred access polygons and a path computed for start point s and end point t.

The purpose of barred access polygons is to prevent Ego from walking through solid objects. Figure 5 illustrates the semantics of this polygon type. The end point t is inside a barred access polygon so t cannot be reached. In that case the path goes to the near point t', and stops there. The start point s is also inside a barred access polygon. This is a little peculiar as that position is not reachable, but we had no justification for disallowing this setup as input. We see that in this case the polygon that contains s is ignored. We observed different semantics in more recent SCI games, where instead of ignoring the polygon the path immediately leaves the polygon via the near point of s.

Figure 6: Three total access polygons and a path computed for start point s and end point t.

Figure 6 shows the semantics of total access polygons. As we can see, the polygons that contain s and t are ignored. In some game scenes a special event is triggered when Ego enters a particular area. Those areas usually have a total access polygon around it. This prevents the pathfinding routine from directing Ego into such an area when the end point is not in that area.

Figure 7: Three near-point access polygons and a path computed for start point s and end point t.

Figure 8: A contained access polygon and a path computed for start point s and end point t.

Figure 7 illustrates the semantics of near-point access polygons. The path goes from s to the near point s' and ends at t coming from the near point t'. We did not come across any near-point access polygons in games so the purpose behind these is unknown.

The fourth polygon type is the contained access polygon. Unfortunately we could not test its semantics with the experimentator. The experimentator only works with a particular version of Sierra SCI that predates the addition of this fourth polygon type. In order to solve this problem we added a debug mode to FreeSCI to visualize the polygons on the display, using a different color for each polygon type. We found a contained access polygon this way and we observed its semantics in Sierra SCI. Figure 8 illustrates these semantics. As the end point t is outside the polygon it cannot be reached. The path will end at the near point t' instead. The idea of this polygon is that it defines the outer boundary and Ego must stay inside of it, i.e. no path may exit this polygon. As any two polygons cannot intersect it follows that there can only be one such polygon. With more than one contained access polygon no path exists that is fully contained in each of those polygons.

Keyboard handling

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 behavior 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 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.

As mentioned earlier, we never encountered a near-point access polygon in a game. Therefore we can only speculate as to the reason for turning near-point access polygons into total access polygon. A possible explanation might be that starting in a near-point access polygon could cause Ego to walk off into a different direction than the user had indicated. We have no plausible explanation for why they are turned into total access polygons, rather than being removed altogether.

Display border

Figure 9: A barred access polygon that touches the display border and a path computed for start point s and end point t.

Figure 10: A barred access polygon that touches the display border and a path computed for start point s and end point t.

As mentioned in 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

The containment test takes as input a point p and a polygon P and determines if p is contained in P. This is obviously the case if p lies on the inside of P. However, it was unclear if points that lie exactly on an edge of P are considered to be inside or outside of P. With a modified version of the experimentator we determined that the former is the case.

Vertex ordering

Polygons are usually defined by a closed path of vertices. It is useful to use a fixed ordering of the vertices (either clockwise or anticlockwise). This has the advantage that the inside of a polygon is always on the same side of the directed edges of that polygon and thereby simplifies the implementation of the pathfinding algorithm. As the patent explicitly discusses the benefits of a fixed vertex ordering, it seemed likely that SCI games use it as well. We ran tests with SCI games in order to confirm this, but we determined that clockwise and anticlockwise ordering are used indiscriminately.