2,051
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Algorithms"
Jump to navigation
Jump to search
m
SCI/FreeSCI/Pathfinding/Algorithms (view source)
Revision as of 03:10, 23 January 2011
, 03:10, 23 January 2011behaviour -> behavior
m (Fixed a reference link that was broken, replaced it by another source. Added source to another.) |
m (behaviour -> behavior) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
=Algorithms= | =Algorithms= | ||
In this section we discuss the algorithms that were considered and motivate our final choice. We describe the pathfinding algorithms in | In this section we discuss the algorithms that were considered and motivate our final choice. We describe the pathfinding algorithms in the ''Pathfinding'' section and the polygon containment algorithms in ''Polygon containment'' section. | ||
==Pathfinding== | ==Pathfinding== | ||
We learnt by observation that the input size generally does not exceed 100 nodes. At these small input sizes the asymptotic performance of an algorithm is not very significant. We decided that we did not want to sacrifice ease of implementation for an algorithm with better asymptotic | We learnt by observation that the input size generally does not exceed 100 nodes. At these small input sizes the asymptotic performance of an algorithm is not very significant. We decided that we did not want to sacrifice ease of implementation for an algorithm with better asymptotic behavior. We also decided to limit ourselves to true shortest path solutions, as we want Ego to take the shortest path to his destination. | ||
An optimal O(n log n) shortest path algorithm was discovered by Hershberger and Suri <ref>John Hershberger, Subhash Suri, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2037 "An optimal algorithm for Euclidean shortest paths in the plane"], SIAM Journal on Computing, Vol. 28 , No. 6, pp. 2215-2256, December 1999.</ref>, but it is too complex to implement in such a short time frame. Simpler algorithms exist that are based on visibility graphs. For a polygon set <i>P</i> a visibility graph <i>G</i> contains all vertices of the polygons in <i>P</i>. The start and end point are added to <i>G</i>.<i>G</i> has an edge between two vertices <i>v</i> and <i>w</i> if the line (<i>v</i>, <i>w</i>) does not intersect the interior of any polygon in <i>P</i>. Once the visibility graph has been constructed the shortest path can be found by using an algorithm for determining the shortest path in a graph, such as Dijkstra’s algorithm. The visibility graph on <i>n</i> vertices contains n<sup>2</sup> edges in the worst case. This means that any shortest path algorithm based on visibility graphs will have at least <i>O(n<sup>2</sup>)</i> running time. The trivial algorithm determines the visibility of two vertices <i>v</i> and <i>w</i> by testing for an intersection between the line (<i>v</i>, <i>w</i>) and all edges in the input set, leading to <i>O(n<sup>3</sup>)</i> running time. | An optimal O(n log n) shortest path algorithm was discovered by Hershberger and Suri <ref>John Hershberger, Subhash Suri, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2037 "An optimal algorithm for Euclidean shortest paths in the plane"], SIAM Journal on Computing, Vol. 28 , No. 6, pp. 2215-2256, December 1999.</ref>, but it is too complex to implement in such a short time frame. Simpler algorithms exist that are based on visibility graphs. For a polygon set <i>P</i> a visibility graph <i>G</i> contains all vertices of the polygons in <i>P</i>. The start and end point are added to <i>G</i>.<i>G</i> has an edge between two vertices <i>v</i> and <i>w</i> if the line (<i>v</i>, <i>w</i>) does not intersect the interior of any polygon in <i>P</i>. Once the visibility graph has been constructed the shortest path can be found by using an algorithm for determining the shortest path in a graph, such as Dijkstra’s algorithm. The visibility graph on <i>n</i> vertices contains n<sup>2</sup> edges in the worst case. This means that any shortest path algorithm based on visibility graphs will have at least <i>O(n<sup>2</sup>)</i> running time. The trivial algorithm determines the visibility of two vertices <i>v</i> and <i>w</i> by testing for an intersection between the line (<i>v</i>, <i>w</i>) and all edges in the input set, leading to <i>O(n<sup>3</sup>)</i> running time. | ||