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

Jump to navigation Jump to search
Added images.
m (Fixed broken link, the SVN no longer exists. Replaced by equivalent darcsweb link)
(Added images.)
Line 9: Line 9:
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.
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.


The purpose of barred access polygons is to prevent Ego from walking through solid objects. Figure [*] illustrates the semantics of this polygon type. The end point <i>t</i> is inside a barred access polygon so <i>t</i> cannot be reached. In that case the path goes to the near point <i>t'</i>, and stops there. The start point <i>s</i> 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 <i>s</i> 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 <i>s</i>.
[[Image:Pathfinding-figure05.png|frame|Figure 5: Three barred access polygons and a path computed for start point <i>s</i> and end point <i>t</i>.|center]]


Figure [*] shows the semantics of total access polygons. As we can see, the polygons that contain <i>s</i> and <i>t</i> 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.
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 <i>t</i> is inside a barred access polygon so <i>t</i> cannot be reached. In that case the path goes to the near point <i>t'</i>, and stops there. The start point <i>s</i> 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 <i>s</i> 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 <i>s</i>.


Figure [*] illustrates the semantics of near-point access polygons. The path goes from <i>s</i> to the near point <i>s'</i> and ends at <i>t</i> coming from the near point <i>t'</i>. We did not come across any near-point access polygons in games so the purpose behind these is unknown.
[[Image:Pathfinding-figure06.png|frame|Figure 6: Three total access polygons and a path computed for start point <i>s</i> and end point <i>t</i>.|center]]


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 colour for each polygon type. We found a contained access polygon this way and we observed its semantics in Sierra SCI. Figure [*] illustrates these semantics. As the end point <i>t</i> is outside the polygon it cannot be reached. The path will end at the near point <i>t'</i> 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.
Figure 6 shows the semantics of total access polygons. As we can see, the polygons that contain <i>s</i> and <i>t</i> 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.
 
[[Image:Pathfinding-figure07.png|frame|Figure 7: Three near-point access polygons and a path computed for start point <i>s</i> and end point <i>t</i>.|center]]
 
[[Image:Pathfinding-figure08.png|frame|Figure 8: A contained access polygon and a path computed for start point <i>s</i> and end point <i>t</i>.|center]]
 
 
Figure 7 illustrates the semantics of near-point access polygons. The path goes from <i>s</i> to the near point <i>s'</i> and ends at <i>t</i> coming from the near point <i>t'</i>. 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 colour 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 <i>t</i> is outside the polygon it cannot be reached. The path will end at the near point <i>t'</i> 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==
==Keyboard handling==
236

edits

Navigation menu