Walkable Areas and Path-finding: Difference between revisions
Walkable Areas and Path-finding (view source)
Revision as of 18:27, 9 December 2013
, 9 December 2013→Conclusion
TheBitPriest (talk | contribs) (Created page with "=== Introduction === Knowing a few details about the inner workings of AGS's path-finding algorithm can be helpful when designing walkable areas. Some designers have been fr...") |
TheBitPriest (talk | contribs) |
||
| (10 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=== Introduction === | === Introduction === | ||
Knowing a few details about the inner workings of AGS's path-finding algorithm can be helpful when designing walkable areas. Some designers have been frustrated by what would seem to be random | Knowing a few details about the inner workings of AGS's path-finding algorithm can be helpful when designing walkable areas. Some designers have been frustrated by what would seem to be random reasons for a player-character not to be able to navigate to a desired location. For instance, a player-character may be able to successfully navigate a path from one direction and not the other, resulting in the character getting stuck in portions of a room. | ||
=== The Easiest and Optimal Solution === | === The Easiest and Optimal Solution === | ||
The easiest way to ensure that you have an optimized walkable area | The easiest way to ensure that you have an optimized walkable area is to make certain that your area fits within the following 3x3 grid. You can expand the grid by pasting together more points at the same aspect ratio. | ||
[[Image:Pathfinding-grid.png|center|The engine will direct the player character along the green pixels on this grid]] | [[Image:Pathfinding-grid.png|center|The engine will direct the player character along the green pixels on this grid]] | ||
| Line 14: | Line 14: | ||
[[Image:Pathfinding-paint-program-ex.jpg|center|Editing a walkable area bitmap using a grid with image editing software.]] | [[Image:Pathfinding-paint-program-ex.jpg|center|Editing a walkable area bitmap using a grid with image editing software.]] | ||
Here is the repaired mask being successfully navigated by Captain Disaster. The bright green path | Here is the repaired mask being successfully navigated by Captain Disaster. The bright green path on the dark green field is a part of the debugging code that was used to investigate the engine's path-finding strategy. The colors are explained later in this document. | ||
[[Image:Pathfinding-fixed-path-found.png|center|The player-character can successfully navigate this repaired walkable area mask.]] | [[Image:Pathfinding-fixed-path-found.png|center|The player-character can successfully navigate this repaired walkable area mask.]] | ||
| 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 === | ||
| Line 45: | Line 45: | ||
=== Extreme Examples === | === Extreme Examples === | ||
Knowing something about the inner workings of the engine will allow the possibility of following extreme paths. Even so, this is not the recommended usage of this engine that is designed primarily for “classic” point-and-click adventure games. Games created with these extreme paths may stress the target machine. Obtaining | Knowing something about the inner workings of the engine will allow the possibility of following extreme paths. Even so, this is not the recommended usage of this engine that is designed primarily for “classic” point-and-click adventure games. Games created with these extreme paths may stress the target machine. Obtaining adequate performance is left to the discretion of the game designer. | ||
In the image below, the designer chose to direct the player along a one-pixel path. Using the 3x3 grid, the designer was able to create a working and optimal path. | |||
[[Image:Pathfinding-extreme-path-1.png|center|An extreme path.]] | [[Image:Pathfinding-extreme-path-1.png|center|An extreme path.]] | ||
In | In the next case, depicted below, the designer wanted an irregular one-pixel path to connect two larger areas. | ||
[[Image:Pathfinding-extreme-path-2.png|center|A sub-optimal extreme path.]] | [[Image:Pathfinding-extreme-path-2.png|center|A sub-optimal extreme path.]] | ||
| Line 61: | Line 61: | ||
=== Conclusion === | === Conclusion === | ||
The safest, most optimal way to design a walkable area is to make certain that the area fits within the 3x3 grid. Large flat areas pose even less problems, because path-finding is only called when the player-character does not have direct line-of-sight to the desired location. Extreme paths are possible, but they ought to be used cautiously with an eye on performance. | The safest, most optimal way to design a walkable area is to make certain that the area fits within the 3x3 grid. Large flat areas pose even less problems, because path-finding is only called when the player-character does not have direct line-of-sight to the desired location. Extreme paths are possible, but they ought to be used cautiously with an eye on performance. | ||
[[Category:Beginner Tutorials]] | [[Category:Beginner Tutorials]] | ||