How to create a random path between two known points in matrix in MATLAB

Question

If there is a matrix and two known points, how to create one random path (no need to be the shortest) between these two points with:

1. a path that can have a level of deviation
2. a path can be totally random (but not necessary)
3. the next step can be only from 4 neighbors

ex. 5x5 matrix with two known points: (2,1) and (5,5)

After input: pt1 = [2,1]; pt2 = [5,5];.

How could I get the pattern such as follows with the path recorded in the parameter, such aspath = [2,1;2,2-;3,2;4,2;4,3;4,4;4,5;5,5].

X X X X X

o o X X X

X o X X X

X o o o o

X X X X o

Answer 1

PART A - Aim is to find coordinates of a line/path connecting two points on a 2D domain such that no two neighboring coordinates are diagonal to each other i.e. that is left/right/top/bottom only.

Function codes

function pts_array = points_array(pt1,pt2)

if pt1(1)==pt2(1)
    if pt2(2)>pt1(2)
        pts_array = [repmat(pt1(1),(pt2(2)-pt1(2)+1),1) (pt1(2):pt2(2))'];
    elseif pt2(2)<pt1(2)
        pts_array = flipud([repmat(pt1(1),(pt1(2)-pt2(2)+1),1) (pt2(2):pt1(2))']);
    else
        pts_array = pt1;
    end
elseif pt1(2)==pt2(2)
    if pt2(1)>pt1(1)
        pts_array = [(pt1(1):pt2(1))' repmat(pt1(2),(pt2(1)-pt1(1)+1),1)];
    elseif pt2(1)<pt1(1)
        pts_array = flipud([(pt2(1):pt1(1))' repmat(pt1(2),(pt1(1)-pt2(1)+1),1)]);
    else
        pts_array = pt1;
    end
else

    gslope1_org = (pt2(2)-pt1(2))/(pt2(1)-pt1(1));
    if gslope1_org <1
        pt1 = fliplr(pt1);
        pt2 = fliplr(pt2);
    end
    gslope1 = (pt2(2)-pt1(2))/(pt2(1)-pt1(1));

    off1 = 1;

    pts_array = [pt1];
    gpt1 = pt1;
    while 1
        slope1 = (pt2(2)-gpt1(2))/(pt2(1)-gpt1(1));
        if (slope1<gslope1)
            gpt1 = [gpt1(1)+off1 gpt1(2)];
            pts_array = [pts_array; gpt1];
        else
            new_y = floor(gpt1(2)+slope1);
            range_y = (gpt1(2)+1 : floor(gpt1(2)+slope1))';
            gpt1 = [gpt1(1) new_y];
            pts_array = [pts_array ; [repmat(gpt1(1),[numel(range_y) 1]) range_y]];
        end
        if isequal(gpt1,pt2)
            break;
        end
    end

    if gslope1_org <1
        pts_array = fliplr(pts_array);
    end
end

function pts_array = points_array_wrap(pt1,pt2) %%// Please remember that this needs points_array.m

x1 = pt1(1);
y1 = pt1(2);
x2 = pt2(1);
y2 = pt2(2);

quad4 = y2<y1 & x2>x1; %% when pt2 is a lower height than pt1 on -slope
quad3 = y2<y1 & x2<x1; %% when pt2 is a lower height than pt1 on +slope
quad2 = y2>y1 & x2<x1; %% when pt2 is a higher height than pt1 on -slope

if quad4
    y2 = y2+ 2*(y1 - y2);
end

if quad2
    y2 = y2 - 2*(y2 - y1);
    t1 = x1;t2 = y1;
    x1 = x2;y1 = y2;
    x2 = t1;y2 = t2;
end

if quad3
    t1 = x1;t2 = y1;
    x1 = x2;y1 = y2;
    x2 = t1;y2 = t2;
end

pts_array = points_array([x1 y1],[x2 y2]);

if quad4
    offset_mat = 2.*(pts_array(:,2)-pt1(2));
    pts_array(:,2) = pts_array(:,2) - offset_mat;
end

if quad3
    pts_array = flipud(pts_array);
end

if quad2
    offset_mat = 2.*(pt1(2)-pts_array(:,2));
    pts_array(:,2) = pts_array(:,2) + offset_mat;
    pts_array = flipud(pts_array);
end

return;

Script

pt1 = [2 1];
pt2 = [5 5];

pts_array = points_array_wrap(pt1,pt2);

plot(pts_array(:,1),pts_array(:,2),'o'), grid on, axis equal
for k = 1:size(pts_array,1)
    text(pts_array(k,1),pts_array(k,2),strcat('[',num2str(pts_array(k,1)),',',num2str(pts_array(k,2)),']'),'FontSize',16)
end

Output

pts_array =

     2     1
     2     2
     3     2
     3     3
     4     3
     4     4
     4     5
     5     5

Plot

PART B - Aim is to find coordinates of a line/path connecting two points on a 2D domain through given spaces.

In this special case, we are assuming that there are some spaces and only through which the path is to be connected. This is not asked by OP, but I thought it could interesting to share. So, for this, the spaces would be the o's as shown in OP's question.

Code

function your_path = path_calc(mat1,starting_pt,final_pt)

[x1,y1] = find(mat1);
pt1 = [x1 y1];
d1 = pdist2(pt1,final_pt,'euclidean');
[~,ind1] = sort(d1,'descend');
path1 = pt1(ind1,:);
your_path =  path1(find(ismember(path1,starting_pt,'rows')):end,:);

return;

Run - 1

%%// Data
mat1 = zeros(5,5);
mat1(2,1:2) = 1;
mat1(3,2) = 1;
mat1(4,2:5) = 1;
mat1(5,5) = 1;

starting_pt = [2 1];
final_pt = [5 5];

%%// Path traces
path = path_calc(mat1,starting_pt,final_pt);

Gives -
mat1 =

0     0     0     0     0
1     1     0     0     0
0     1     0     0     0
0     1     1     1     1
0     0     0     0     1


path =

2     1
2     2
3     2
4     2
4     3
4     4
4     5
5     5

Run - 2

%%// Data
mat1 = zeros(5,5);
mat1(2,1:2) = 1;
mat1(3,2) = 1;
mat1(4,2:5) = 1;
mat1(5,5) = 1;
mat1 = fliplr(mat1');

%%// Notice it starts not from the farthest point this time
starting_pt = [2 3];
final_pt = [5 1];

%%// Path traces
path = path_calc(mat1,starting_pt,final_pt);

Gives

mat1 =

     0     0     0     1     0
     0     1     1     1     0
     0     1     0     0     0
     0     1     0     0     0
     1     1     0     0     0


path =

     2     3
     2     2
     3     2
     4     2
     5     2
     5     1

Answer 2

To find a purely random path from the start to the goal, this function selects a random direction, checks that there is a valid neighbor in that direction and if there is, moves to that new neighbor and adds it to the path.

Directions can be invalid if, for instance, we're in the leftmost column and try to move left. We could check beforehand and only select randomized directions that lead to valid neighbors, but that would complicate the code and the chances of selecting a valid neighbor are at worst 50/50.

function path = random_path(start, goal, board_size)

    m = board_size(1);
    n = board_size(2);
    isInBounds = @(x) x(1) >= 1 && x(1) <= m && x(2) >= 1 && x(2) <= n;

    neighbor_offset = [ 0, -1;    % Neighbor indices:
                       -1,  0;    %        2
                        0,  1;    %    1   x   3
                        1,  0];   %        4
% Edit: get the actual size of our neighbor list
    [possible_moves, ~] = size(neighbor_offset);

    current_position = start;
    path = current_position;

    while sum(current_position ~= goal) > 0
        valid = false;
        while ~valid
% Edit: "magic numbers" are bad; fixed below
%           move = randi(4);
            move = randi(possible_moves);
            candidate = current_position + neighbor_offset(move, :);
            valid = isInBounds(candidate);
        end
        current_position = candidate;
        path = [path; current_position];
    end
end

The while condition:

sum(current_position ~= goal) > 0

continues while at least one of the coordinates of sum and goal are different. I'm sure this could be written more concisely, so if there are any suggestions as to how to improve this I'd be grateful.

Likewise, the isInBounds anonymous function also seems a bit clunky, so any suggestions there would be appreciated as well.

At any rate, here's a sample of the output. Since the paths are completely random, some of them can get quite long:

random_path([2,1], [5,5], [5,5])

ans = 

   2   1 
   3   1 
   2   1 
   3   1 
   3   2 
   4   2 
   4   1 
   5   1 
   4   1 
   4   2 
   3   2 
   3   1 
   2   1 
   1   1 
   2   1 
   3   1 
   3   2 
   4   2 
   4   3 
   4   4 
   4   3 
   4   2 
   4   3 
   5   3 
   4   3 
   3   3 
   4   3 
   4   2 
   4   1 
   4   2 
   4   1 
   4   2 
   4   3 
   4   2 
   5   2 
   5   3 
   5   2 
   4   2 
   3   2 
   3   3 
   3   4 
   3   5 
   3   4 
   2   4 
   3   4 
   4   4 
   5   4 
   5   3 
   4   3 
   3   3 
   3   2 
   4   2 
   4   3 
   4   4 
   5   4 
   5   5