Walkable Areas and Path-finding: Difference between revisions
Walkable Areas and Path-finding (view source)
Revision as of 18:23, 9 December 2013
, 9 December 2013→Engine Path-finding Strategy
TheBitPriest (talk | contribs) |
TheBitPriest (talk | contribs) |
||
| Line 27: | Line 27: | ||
# If the flood-fill check fails, the engine looks for the closest walkable area within a 100x100px square around the desired location on a 3x3 pixel grid. If even this fails, the engine searches the entire screen on a 5x5 grid using the euclidean distance to find the closest walkable area. | # If the flood-fill check fails, the engine looks for the closest walkable area within a 100x100px square around the desired location on a 3x3 pixel grid. If even this fails, the engine searches the entire screen on a 5x5 grid using the euclidean distance to find the closest walkable area. | ||
# Following this “quick” test, Dijkstra's path-finding algorithm is used to find a solution on a 3x3 grid. | # Following this “quick” test, Dijkstra's path-finding algorithm is used to find a solution on a 3x3 grid. | ||
# If Dijkstra's algorithm fails, the engine reverts to an optimized recursive algorithm that can find a good, but non-optimal, path to the desired location. This search is capable | # If Dijkstra's algorithm fails, the engine reverts to an optimized recursive algorithm that can find a good, but non-optimal, path to the desired location. This search is capable of navigating even a single pixel, but due to the optimizations, it will not always find a solution. | ||
=== Examples === | === Examples === | ||