Difference between revisions of "SCI/FreeSCI/Pathfinding/Future"
(Merging of the FreeSCI Pathfinding documentation. Work in progress.) |
m ("Assumption 1" and "Assumption 2" are now linked correctly) |
||
| Line 1: | Line 1: | ||
=Conclusions and recommendations for future work= | =Conclusions and recommendations for future work= | ||
The main goal of this internship was to implement the | The main goal of this internship was to implement the voidPath function without infringing Sierra’s pathfinding patent. We accomplished this by choosing an algorithm that is very different from the one described in the patent. The algorithm we chose has one advantage over the algorithm used by Sierra, namely that it always computes the shortest path. Our implementation performed well in the basic tests we performed. However, at this time we are aware of two limitations. | ||
The first limitation is related to the rounding of intersecting points as in | The first limitation is related to the rounding of intersecting points as in [[SCI/FreeSCI/Pathfinding/Implementation#Rounding real numbers|Rounding real numbers]] section. Our implementation tries nearby points in ℤ<sup>2</sup>. If an intersected polygon is very thin, a rounded point may end up on the wrong side of the polygon. This would make it possible to walk through very thin polygons with the keyboard. We used the experimentator to test very thin polygons in Sierra SCI and we observed that it suffers from the same limitation. A possible solution for this problem would be to ignore rounded points that lie left of the intersected edge. | ||
The second limitation is related to Assumption 2. In practice there are game scenes that contain intersecting polygons, and thus violate this assumption. As we currently know of only one scene for which this is the case (Conquests of the Longbow, room 210.), this issue was ignored for the present | The second limitation is related to [[SCI/FreeSCI/Pathfinding/Specification#assumption_2|Assumption 2]]. In practice there are game scenes that contain intersecting polygons, and thus violate this assumption. As we currently know of only one scene for which this is the case (''Conquests of the Longbow'', room 210.), this issue was ignored for the present project. This scene works correctly in Sierra SCI, even though tests with the <tt>experimentator</tt> showed that Sierra SCI does not support intersecting polygons in general. If there are more game scenes that violate the assumption, it might be necessary to add support for intersecting polygons. | ||
This would create an interesting problem as the visibility graph algorithm we used is fundamentally incompatible with intersecting polygons. | This would create an interesting problem as the visibility graph algorithm we used is fundamentally incompatible with intersecting polygons. | ||
| Line 10: | Line 10: | ||
The algorithm stores the edges that the sweeping line intersects in a tree, ordered by distance. Let <i>e<sub>0</sub></i> and e1 be edges. If <i>e<sub>0</sub></i> and <i>e<sub>1</sub></i> do not intersect then their ordering does not depend on the position of the sweeping line, but if they intersect at a point <i>p</i> this ordering flips when the sweeping line hits <i>p</i>. It may be possible to store intersection points and initiate a tree reordering when the sweeping line hits an intersection point. However, it might be better to detect intersecting polygons and fall back to the trivial <i>O(n<sup>3</sup>)</i> algorithm, which does not make use of such an ordered data structure. Other problems arise when a vertex <i>v</i> of one polygon lies on an edge e of another. In that case it would be possible to create a path that goes through <i>e</i> via <i>v</i>, as <i>e</i> does not properly intersect any edges incident to <i>v</i> and thus would not obstruct visibility. | The algorithm stores the edges that the sweeping line intersects in a tree, ordered by distance. Let <i>e<sub>0</sub></i> and e1 be edges. If <i>e<sub>0</sub></i> and <i>e<sub>1</sub></i> do not intersect then their ordering does not depend on the position of the sweeping line, but if they intersect at a point <i>p</i> this ordering flips when the sweeping line hits <i>p</i>. It may be possible to store intersection points and initiate a tree reordering when the sweeping line hits an intersection point. However, it might be better to detect intersecting polygons and fall back to the trivial <i>O(n<sup>3</sup>)</i> algorithm, which does not make use of such an ordered data structure. Other problems arise when a vertex <i>v</i> of one polygon lies on an edge e of another. In that case it would be possible to create a path that goes through <i>e</i> via <i>v</i>, as <i>e</i> does not properly intersect any edges incident to <i>v</i> and thus would not obstruct visibility. | ||
It may be possible to add support for intersecting polygons by first merging the intersecting polygons into one polygon. In some cases this does not work, however. Let <i>P</i> and <i>Q</i> be two polygons whose intersection is a single point <i>p</i>. If we now merge <i>P</i> and <i>Q</i> we get a polygon that is self-intersecting at <i>p</i>, which would still be illegal input for the visibility graph algorithm as it violates Assumption 1. | It may be possible to add support for intersecting polygons by first merging the intersecting polygons into one polygon. In some cases this does not work, however. Let <i>P</i> and <i>Q</i> be two polygons whose intersection is a single point <i>p</i>. If we now merge <i>P</i> and <i>Q</i> we get a polygon that is self-intersecting at <i>p</i>, which would still be illegal input for the visibility graph algorithm as it violates [[SCI/FreeSCI/Pathfinding/Specification#assumption_1|Assumption 1]]. | ||
All of this suggests that there is no quick fix that adds support for intersecting polygons. If it turns out that support for intersecting polygons is necessary, further research will need to be performed. | All of this suggests that there is no quick fix that adds support for intersecting polygons. If it turns out that support for intersecting polygons is necessary, further research will need to be performed. | ||
Latest revision as of 03:22, 30 January 2009
Conclusions and recommendations for future work
The main goal of this internship was to implement the voidPath function without infringing Sierra’s pathfinding patent. We accomplished this by choosing an algorithm that is very different from the one described in the patent. The algorithm we chose has one advantage over the algorithm used by Sierra, namely that it always computes the shortest path. Our implementation performed well in the basic tests we performed. However, at this time we are aware of two limitations.
The first limitation is related to the rounding of intersecting points as in Rounding real numbers section. Our implementation tries nearby points in ℤ2. If an intersected polygon is very thin, a rounded point may end up on the wrong side of the polygon. This would make it possible to walk through very thin polygons with the keyboard. We used the experimentator to test very thin polygons in Sierra SCI and we observed that it suffers from the same limitation. A possible solution for this problem would be to ignore rounded points that lie left of the intersected edge.
The second limitation is related to Assumption 2. In practice there are game scenes that contain intersecting polygons, and thus violate this assumption. As we currently know of only one scene for which this is the case (Conquests of the Longbow, room 210.), this issue was ignored for the present project. This scene works correctly in Sierra SCI, even though tests with the experimentator showed that Sierra SCI does not support intersecting polygons in general. If there are more game scenes that violate the assumption, it might be necessary to add support for intersecting polygons.
This would create an interesting problem as the visibility graph algorithm we used is fundamentally incompatible with intersecting polygons.
The algorithm stores the edges that the sweeping line intersects in a tree, ordered by distance. Let e0 and e1 be edges. If e0 and e1 do not intersect then their ordering does not depend on the position of the sweeping line, but if they intersect at a point p this ordering flips when the sweeping line hits p. It may be possible to store intersection points and initiate a tree reordering when the sweeping line hits an intersection point. However, it might be better to detect intersecting polygons and fall back to the trivial O(n3) algorithm, which does not make use of such an ordered data structure. Other problems arise when a vertex v of one polygon lies on an edge e of another. In that case it would be possible to create a path that goes through e via v, as e does not properly intersect any edges incident to v and thus would not obstruct visibility.
It may be possible to add support for intersecting polygons by first merging the intersecting polygons into one polygon. In some cases this does not work, however. Let P and Q be two polygons whose intersection is a single point p. If we now merge P and Q we get a polygon that is self-intersecting at p, which would still be illegal input for the visibility graph algorithm as it violates Assumption 1.
All of this suggests that there is no quick fix that adds support for intersecting polygons. If it turns out that support for intersecting polygons is necessary, further research will need to be performed.