Breadth First Search on Labyrinth in Matlab

Question

I'm trying on implementing an breadth first algorithm, that solves a labyrinth. As an input I have a n*m binary matrix, where '1' stands for obstacle/wall and '0' for path/ free cell.

I do get how the algorithm generally works, but I'm struggling with how to store and proceed the information in matlab. So basically I start with my start cell, and check all it's direct neighbours for obstacles. If they are free, I mark them as a potential path, and then I do the same recursively for all those cells again.

But i just can't figure out how to store the information, so that in the end i will only have one path. any ideas?

Take a look at the link I referenced. It basically has a MATLAB implementation of BFS, as well as well as GIF animation of how BFS works to get out of a maze. However, if you want BFS to work, you need to know the starting and ending point of the maze. — rayryeng, Dec 05 '14 at 16:41
However, if you want me to write an answer specifically for your case, we can! — rayryeng, Dec 05 '14 at 17:16

mehmet · Accepted Answer · 2014-12-05T16:43:10.190

0

You can use open and closed list like in the a star pathfinding algorithm. Check the all neighbours and if the neighbour is not a obstacle, put in the open list. Examine all neighbours and the neighbour which has a min cost, put it in the closed list. In the end, you have the optimal path in the closed list. Basically it is something like that..

edited Dec 05 '14 at 16:43

answered Dec 05 '14 at 16:31

mehmet

1,631
16
21

score 0 · Answer 2 · answered Dec 05 '14 at 17:43

This is a function that search a connected component in an unoriented graph by deep first search. BFS should be even easier to code.

function comp = findNodeComponentDFS(G, node)
%Find a connected component of the given node in the unoriented graph. Use
%Deep first search (Cormen, Rivest, Leiserson)
%G - connectivity matrix
%node - given node
%comp - contain the numbers of all nodes in the found connected component
%except the node itself
N = length(G);
white = ones(1,N);%unexamined vertices
grey = zeros(1,N);%vertices that are currently examining but with not all edges have been    examined yet
black = zeros(1,N);%vertices with all the edges have been examined
prev = zeros(1,N);
current = node;
stop=false;
while (~stop)
    grey(current) = 1;
    white(current) = 0;
    next = find(G(current,:) & white,1);
    if (isempty(next))
        black(current) = 1;
        if (prev(current)==0)
            stop = true;
        else
            current = prev(current);%back to previous vertice
        end
    else
        prev(next) = current;
        current = next;
    end
end
comp = find(black);

thanks a lot to everyone!! i got it now finally. i was just confused on how to store and reference the path, but turns out storing it in a matrix/ open list was far easier than i thought :) — WednesdayAddams, Dec 06 '14 at 12:18

Breadth First Search on Labyrinth in Matlab

2 Answers2