Shortest Cityblock Path with Multiple Nodes (Goals) with Still Obstacles

I have spent a great deal of time reading about A* search, Dijkstra’s, and Best-First-Search algorithms. I did an exhausutive search of all m-file exhanges, toolboxes, and whatnot, but I couldn't find a solution to my problem.

As the title suggests, I have a square map (you may call it a grid, or a matrix). I have a predefined starting point, and there are predefined still obstacles. There could be as few as one goal, or there could be multiple nodes.

What I need:

I need to find the shortest cityblock path (moving diagonally isn't allowed) that passes through all goals, and plots the path on the original grid with obstacles and starting point indicated.

To help you visualize the problem, see the image

In this image, the numbers one through eight represent the only possible nodes. The blue blocks are obstacles, and the path cannot pass through it. The gray squares are equivalent to the white ones. I used color just to make it easier to understand the map.

Let me give an example with the desired solution. Assume there are only 2 desired nodes we want to pass by: node 2 and node 8. The output map should look something like this:

Answer 1

[Image Analyst]

See Steve's blog series on shortest paths. http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/

[Pyro]

I came accross it, but it doesn't address obstacles nor multiple nodes.

[Image Analyst]

It does address obstacles - you must not have read through to the 5th article in the series where it avoids the letters in the image.

It doesn't do multiple nodes but I think you can do that process once for each identified node that you have.

[Pyro]

Oh.. I didn't notice a fifth article. Only came across parts I and II. I will try to find it. Thanks m8

[Image Analyst]

The links are listed at the bottom of the articles.

Here is article 5 directly.