2,051
edits
Difference between revisions of "SCI/FreeSCI/Pathfinding/Algorithms"
SCI/FreeSCI/Pathfinding/Algorithms (view source)
Revision as of 03:10, 23 January 2011
, 03:10, 23 January 2011behaviour -> behavior
m (Deleted references to numbers. No links as the sections are in the same document) |
m (behaviour -> behavior) |
||
| Line 3: | Line 3: | ||
==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. | ||