Find ANY way that connects two points of one color in the rectangle

Question

Here is a rectangle MxN (in pixels). Any pixel of that rectangle is black or white.

There is a way through black pixels only, always, that connects any black pixel A and any pixel B. Using another words, there is a way via black pixels, that could bring you from any black pixel to any other black pixel.

The statement above is not exactly true for white pixels.

The question is: Build ANY way that connects (Xstart, Ystart) and (Xfinish,Yfinish).

P.S. you have the matrix MxN of values 1 or 0 (white or black). You have a black point (Xstart, Ystart) and black(Xfinish,Yfinish).

Any language (javascript, C# or whatever is OK). I need the idea. Any way is OK. The algorithm for the shortest way is not so important, if it becomes much more complicated.

The are 4 ways only: South, North, East and West. NW, SW, NE, SE (diagonals) are NOT OK.

Answer 1

To find any path you can just do a breadth-first traversal. But we can do better by controlling in what direction we search.

A* is an algorithm that does just that, and it is a common path finding algorithm for this kind of problem. You assign a cost to all pixels around you and try the one with the lowest cost until you have found a path.

The cost function is an estimate of how long the path is to your goal. You can of course not know the exact length in reasonable time (because that's already the problem you are trying to solve!) so it must be an estimate. You can use anything for a cost function, but you get better results with a better estimate. A simple one is the Manhattan distance:

abs(X - Xfinish) + abs(Y - Yfinish)

It has been shown that A* will give an optimal answer (the shortest path) if your cost function never overestimates the distance; if so, the cost function is called admissible. So to find an optimal path it is better to underestimate than to overestimate the distance. Too much underestimation will unfortunately give you worse runtime performance, though, because you need to try more pixels/nodes before finding a path. One cost function that is admissible is the regular Euclidean distance as given by the Pythagorean theorem:

sqrt((X - Xfinish)^2 + (Y - Yfinish)^2)