Alternating up and down in my script to find path through 'maze'

2 views (last 30 days)
Scrip folder is attached! (.zip)
The point of this script is to find if a path exists of 1's between the bottom row and top row. A path consisting of straight lines only, no diagonals.
Concept of the script
The maze:
0 1 1 0 1 1 0 (path is made bold)
0 1 0 0 0 0 0
0 1 1 1 1 0 0
0 0 0 0 1 0 0
1 1 1 0 1 1 0
1 0 1 1 1 0 0
1 1 0 0 0 0 0
Initiating step:
Search the bottom row for values equal to 1, then change these into 2's.
Looping step:
Now scan the row above for values equal to 1, which are attached to values of 2. (Like a virus)
Now scan left and right of these new 2's for other 1's that are attached to these, and turn these into 2's aswell.
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 1 1 1 1 0 0
0 0 0 0 1 0 0
2 2 2 0 1 1 0
2 0 1 1 1 0 0
2 2 0 0 0 0 0
As can be seen above we now encounter a point where there's only 0s above and so the script should go down.
I am unable to find an efficient way for alternating up and down within my script, so that it keeps searching for new 1's connected to 2's.
I have been struggling with this specific problem for over 5 hours already and am getting really upset.
Any help is greatly aprecciated!

Accepted Answer

Meg Noah
Meg Noah on 14 Jan 2020
Try this algorithm:
Goal:to assign a label to each connected track of 1's on a background of 0's.
Procedure: Scan image left to right and top to bottom.
Mask/Template:
- U
L C
for evaluating the C center pixel compared to the U up pixel and the L left pixel.
Algorithm:
let the initial label be k = 1
scan image left to right then top to bottom evaluating each pixel:
if f( C ) == 0
do nothing
else
if f(U)==1 & f(L) ==0
label( C) = label(U);
elseif f(U)==0 & f(L) ==1
label( C) = label(L)
elseif f(U) == 1 & f(L) ==1
label ( C) = label(L)
label(L) <-> label(U)
elseif f(U) == 0 and f(L) == 0
label( C) = k
k = k + 1 (increment label value)
end
end

More Answers (0)

Community Treasure Hunt

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

Start Hunting!