Shortest Path with Obstacle Avoidance (ver 1.3)

Computes shortest path between two points in the plane, avoiding obstacles.
12.1K Downloads
Updated 26 Aug 2008

No License

SHPATH - shortest path with obstacle avoidance (ver 1.3)

Given a "terrain" matrix consisting of zeros (for open space) and ones (for obstacles), this function computes the shortest path between two specified points while avoiding obstacles.

A two-stage solution is employed. In stage one, the algorithm rapidly propagates through all possible pathways to find a representative shortest route. In stage two, the path is contracted to follow closely around sharp corners and eliminate quantization noise. Although the map coordinates (and intial and final points) are integers, the solution coordinates are reals to allow for the elimination of jitter from map quantization.

Note that diagonal "moves" ARE allowed.

To avoid confusion over X/Y conventions for grid matrices, the issue is avoided entirely by referring only to the row and column entries in the grid. The user is invited to employ whatever convention he or she is comfortable using for mapping Cartesian coordinates to the grid matrix entries.

The user is encouraged to see the code comments (or the "help" text) and to run the example code.

Michael Kleder, Oct 2005

Cite As

Michael Kleder (2024). Shortest Path with Obstacle Avoidance (ver 1.3) (https://www.mathworks.com/matlabcentral/fileexchange/8625-shortest-path-with-obstacle-avoidance-ver-1-3), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R14SP2
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.0.0.0

Improved speed and precision; improved unit-width corridor penetration; improved penetration between diagonally adjacent obstacle squares; improved example plot; improved description text