generate a random path between two points

Hello

I found a code on one of these forums for creating a random path inbetween two points. I don't remeber where I found it but I was wondering how to improve this so that the path generated did not overlap on itself? I figured that would involve backtracking when the path has no more possible moves at a certain location.

Thank you

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

[Guillaume]

I think you'll have to search for such an algorithm. I suspect that figuring where to backtrack to would be far for trivial.

Answer 1

[John D'Errico]

This should be pretty easy. Use the graph theory tools in MATLAB. You can find them by:

help graph

The general algorithm is simple now.

Generate a graph that has ALL possible connections between a node any of its immediate neighbors. So each node connects to 2, 3, or 4 neighbors. (Always 4, unless the node is on the edge of the region.)

(1) Given the start point (call it P) pick any node at random that connects to it from the graph. Call the new node Q.

If a path exists that connects this node to the end point, then accept the node you have just chosen as part of the path. At that time, delete ALL edges that connect to node P, thus the previous point on the path. Now you just return to (1), iterating until you find a path that ends at the goal node. At each step, you must decide IF a path exists that connect to the target. You will use the SHORTESTPATH utility for this.

If there was no path in the graph connecting Q to the target point, then delete node Q from the graph (and thus all edges that connect to Q), and choose a NEW node Q that connects to P from the new graph. There must be at least one node Q that will connects to the target, because we knew that P had some path that connects to the target.

In a sense, this is a backtracking algorithm, but it never needs to backtrack by more than one node in the path, because it can choose whether to accept the new node along that path.

Edit: Looks like I need to write code.

P = randompath([1 1],[10,10],[10,10])
P =
     1     1
     2     1
     2     2
     1     2
     1     3
     2     3
     2     4
     3     4
     3     5
     3     6
     4     6
     4     7
     3     7
     3     8
     2     8
     2     7
     1     7
     1     8
     1     9
     1    10
     2    10
     2     9
     3     9
     3    10
     4    10
     5    10
     5     9
     5     8
     6     8
     6     9
     7     9
     7     8
     8     8
     8     7
     9     7
     9     6
     8     6
     7     6
     7     7
     6     7
     6     6
     6     5
     7     5
     7     4
     8     4
     8     5
     9     5
    10     5
    10     6
    10     7
    10     8
    10     9
    10    10
    
plot(P(:,1),P(:,2),'-o')
axis([0 11 0 11])

The algoithm I have indicated will yield a valid path 100% of the time, and it is reasonably fast. I've attached the code as an m-file to this answer. It can never cross itself, since it is designed to delete all edges that talk to a node that has been visited already. At every step in the path, a new node is chosen fully randomly from among the nodes that can still reach the target node. Finally, since it tests at every step that a path does exist that reaches the target, it is always successful in finding a validly non-crossing path.

Here is a random path through a larger region:

P = randompath([1 1],[40,50],[40,50]);
plot(P(:,1),P(:,2),'-o')
axis([0 41 0 51])

If you look carefully, despite the complexity of the path that results, it never does cross itself. A fully non-Catholic path. ;-)

[YUE ZHAO]

Not enough input arguments.

Error in random (line 8)

R = regionsize(4);

[Image Analyst]

John's code works fine. Attached is a full demo with a script that calls the function.

Don't call your script random.m because random is a built-in function name.

You have something before line 8 of the badly-named random.m where you defined regionsize vector but you did not initialize it with at least 4 elements. Attach your script if you need more help.

[YUE ZHAO]

thank you so much!!!!

[John D'Errico]

Funny, I did not remember witing that code. It has definitely been a busy year since January. The code is pretty easy to see how it works though, because it just uses the graph theory tools in MATLAB.

[YUE ZHAO]

one more question about how do i set the random numbers of starting points and ending points in this case

Answer 2

[Adam Danz]

Because I like random walks (example1, example2), I altered an existing code I have to (kind of) do what you're describing. However, John D'Errico's idea would be more efficient if you're looking for a gridded approach.

This takes the folloiwng approach. The inline comments will provide details.

1. The size of each step is chosen randomly between two values (stepSize). If the bounds of stepSize are the same, then the step size is constant.
2. The direction of each step is chosen based on a probability distribution that takes the form of a vonMesis function where directions toward the goal have the highest probability of being selected. The shape of that distribution can be changed by the gravity parameter (it's just the kappa param of the vonMesis).
3. If the next step intersects with the previous path, that step direction is eliminated and a new step direction is chosen until a non-intersecting step is found or we run out of directions.

Requires this FEX function: https://www.mathworks.com/matlabcentral/fileexchange/11837-fast-and-robust-curve-intersections

% Set all parameters
start = [0,0];                  % [x,y] starting point
target = [20,100];              % [x,y] target point
bounds = [0 0, 300 300];        % [xCenter, yCenter, width, height] of path bounds
stepSize = [2 8];               % [min, max] step size (set to equal to have constant step size)
directions = 50;                % the number of possible directions to go within a circle
% NOTE: keep the number of directions small to avoid trying too many alternatives when intersection is found.
doAnimation = true;             % true/false whether to show the animation
gravity = 3;                    % how strongly the point will gravitate to the target
% NOTE: this is the kappa param of the vonMises function; Must be >0; lower values have more randomness.
allowIntersections = false;     % true/false whether to allow the path to intersect iself
% NOTE: when allowIntersections is false, the code is A LOT slower.  This requires
% this FEX function: https://www.mathworks.com/matlabcentral/fileexchange/11837-fast-and-robust-curve-intersections
enforceBounds = true;           % true/false whether to force path to the bounds
maxSteps = 5000;                % Limit the number of steps alowed to avoid exceeding memory

% Set up some functions and variables needed in the loop
dist = @(p1,p2)hypot(p2(1)-p1(1), p2(2)-p1(2)); % Returns distance between point1 and points 2
circ = @(cnt, r, theta)[r*cos(theta) + cnt(1); r*sin(theta) + cnt(2)]; % Compute circumf cordinates [x;y]
vonMises = @(r,p)exp(gravity *(cos(r-p)-1)); % r is angle in radians, p is center
path = start;

% Compute lower and upper bounds of x and y axis
xbounds = [bounds(1)-bounds(3)/2, bounds(1)+bounds(3)/2];
ybounds = [bounds(2)-bounds(4)/2, bounds(2)+bounds(4)/2];

if doAnimation
    % Create world
    fh = figure();
    ax = axes();
    h = plot(start(1),start(2),'b-');
    axis equal
    xlim(xbounds)
    ylim(ybounds)
    grid on
    hold on
    plot(start(1),start(2),'ro')
    plot(target(1),target(2),'rx')
    warning('off','MATLAB:gui:array:InvalidArrayShape');
end

% Loop through each step as long as the current possition is not within
% the maximum step length to the target and we have not exceeded the
% maximum number of steps.
while dist(path(end,:), target) > stepSize(2) && size(path,1)<maxSteps
    % choose a random step size within stepSize bounds
    stepLength = rand(1)*range(stepSize)+stepSize(1);
    % Compute all possible steps in a circle around current position
    theta = linspace(0,2*pi,directions);
    xy = circ(path(end,:), stepLength, theta);
    % Remove points that are out of bounds
    if enforceBounds
        in = inpolygon(xy(1,:),xy(2,:),xbounds([1 2 2 1]),ybounds([1 1 2 2]));
        xy(:,~in) = []; % remove out of bounds
        theta(~in) = [];
        assert(~isempty(xy),'All options were out of bounds.')
    end
    % Compute distance of each point to target
    allDists = pdist2(xy.',target);
    [~, minIdx] = min(allDists);
    % Compute the probability of selecting each coordinate based on it's distance to target
    vmWeights = vonMises(theta, theta(minIdx));
    xInt = 1;
    while ~isempty(xInt) && ~all(vmWeights==0)
        % Choose a random direction given the probabilites
        % This requires Stats & Machine learning toolbox
        idx = randsample(size(xy,2),1,true,vmWeights);
        % Determine if the line intersects with itself
        % uses this function: https://www.mathworks.com/matlabcentral/fileexchange/11837-fast-and-robust-curve-intersections
        if ~allowIntersections && size(path,1)>2
            % This next line is very slow
            xInt = intersections(path(1:end-1,1),path(1:end-1,2), [path(end,1);xy(1,idx)],[path(end,2);xy(2,idx)]);
            if ~isempty(xInt)
                vmWeights(idx) = 0;
                % Inform user that we're trying to find an alternative
                fprintf('Intersection problem. Making attempt %d of %d.\n', sum(vmWeights==0), size(xy,2))
            end
        else
            xInt = [];
        end
    end
    assert(~all(vmWeights==0), sprintf('Could not find a non-intersecting path.'))
    % update current point
    path(end+1,:) = xy(:,idx);  %#ok<SAGROW>
    
    % animate
    if doAnimation
        h.XData(end+1) = path(end,1);
        h.YData(end+1) = path(end,2);
        drawnow
    end
end
% Final path update
path(end+1,:) = target;
warning('on','MATLAB:gui:array:InvalidArrayShape');
if doAnimation
    h.XData = path(:,1);
    h.YData = path(:,2);
end

Here's an example using these parameters

[Vijay]

Thanks for sharing.

After running the script i am getting following error -

Error using assert
All options were out of bounds.

Error in orig (line 56)
        assert(~isempty(xy),'All options were out of bounds.')
 
>> 

Could you please let me know where I am making a mistake.

Thanks!

[Vijay]

However, when we modify

enforceBounds = false; 

then, it works.

But I suppose this will give less control as we are not enforcing bounds? Let me know your thoughts. Thanks.

[Adam Danz]

Thanks for reporting this @Vijay. This is due to a change in behavior for inpolyon in MATLAB r2022b. I've updated my answer with the following change so the answer works before and after this change.

Old line

in = inpolygon(xy(1,:),xy(2,:),xbounds,ybounds); % Replace this line

New line

in = inpolygon(xy(1,:),xy(2,:),xbounds([1 2 2 1]),ybounds([1 1 2 2]));

[Vijay]

Thanks @Adam Danz for quick reply. Its working now with modified line!

[Adam Danz]

🤜🤛

[Vijay]

To make it more complicated and interesting, could anyone please guide me on how to develop a code which not only avoid self interesection but also avoid intersecting other path lines?

I have an idea of creating a global list of paths. After creating a single path from start to target, for each segment of other path, it will check with global list for any intersection with other path. But I guess this would be computationally expensive if there are many paths, also I am not sure how to implement this.

Do you @Andrew Luce have any thoughts? Or anyone has any thoughts, please let me know.

Thanks !!

Answer 3

[Patrick Gipper]

Adam beat me to the punch, but here is an example with more minor modification of the original script.

function [path,error_code] = random_path_pg1(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);
    %
    % old_moves is used to track the move directions in the innermost
    % while loop.  If old_moves is filled then all possible directions
    % have been tried and you are stuck. When this happens the error_code
    % is set to 1 and we exit the function.
    %
    old_moves = zeros(possible_moves,1);
    error_code = 0; % =0 for no error, =1 for a failed random path
    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);
            %
            % Keep track of each move that is tried to prevent an infinite
            % loop.
            %
            old_moves(move) = 1;
            if (sum(old_moves) >= possible_moves)
                error_code=1; % Infinite loop detected
                break
            end
            candidate = current_position + neighbor_offset(move, :);
            %
            % valid = 1 if the candidate is within the board_size
            % boundaries and it is not contained in the path history,
            % otherwise valid = 0
            %
            valid = isInBounds(candidate) && ~ismember(candidate,path,'rows');
        end
        %
        % If an infinite loop was detected in the innermost while loop then
        % you must break out of this while loop too.
        %
        if (error_code == 1)
            break
        end
        %
        % Zero out the old_moves before the start of the next step.
        %
        old_moves = zeros(possible_moves,1);
        current_position = candidate;
        path = [path; current_position];
    end
end

[Patrick Gipper]

One more thing. I find that the random walk with the restrictions of no backtracking and no crossing of the old path history results in failure to get to the goal a majority of the time. The random walker seems to find its way into dead end alleys.

[Patrick Gipper]

Correction of error in my first script. Same conclusion as my comment.

[John D'Errico]

In theory, a continuous random walk path should always be able to escape, since there must be a finite amount of room between the lines if they do not cross. However, the escape route may be very difficult to find if things get sufficiently convoluted. This is why the gridded approach using graph theory tools is far more convenient. You can always use a fine grid to approximate a continuous path. At some point of course, the gridded solution will bog down because of the memory requirement, but at that degree of resolution any scheme can become problematic.