generate a random path between two points

39 次查看（过去 30 天）
Andrew Luce
Andrew Luce 2020-1-28
编辑： Vijay 2023-12-18
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
  1 个评论
Guillaume
Guillaume 2020-1-28
I think you'll have to search for such an algorithm. I suspect that figuring where to backtrack to would be far for trivial.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（3 个）

John D'Errico
John D'Errico 2020-1-28
编辑：John D'Errico 2020-1-29
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])
untitled.jpg
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])
untitled.jpg
If you look carefully, despite the complexity of the path that results, it never does cross itself. A fully non-Catholic path. ;-)
  5 个评论
显示 3更早的评论
John D'Errico
John D'Errico 2020-10-25
编辑：John D'Errico 2020-10-25
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
YUE ZHAO 2020-10-26
one more question about how do i set the random numbers of starting points and ending points in this case

请先登录，再进行评论。

Adam Danz
Adam Danz 2020-1-29
编辑：Adam Danz 2023-12-13
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
  6 个评论
显示 4更早的评论
Vijay
Vijay 2023-12-18
编辑：Vijay 2023-12-18
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 !!

请先登录，再进行评论。

Patrick Gipper
Patrick Gipper 2020-1-29
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
  3 个评论
显示 1更早的评论
Patrick Gipper
Patrick Gipper 2020-1-29
Correction of error in my first script. Same conclusion as my comment.
John D'Errico
John D'Errico 2020-10-25
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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品


版本

R2019b

Community Treasure Hunt

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

Start Hunting!

Translated by