Two Random walker, self avoiding Help
1 view (last 30 days)
Show older comments
Jessica Benidict
on 19 Nov 2014
Commented: Asatur Khurshudyan
on 3 Dec 2019
Consider a 20 by 20 two-dimensional lattice with x and y coordinates varying from 1 to 20. My program needs to simulate two people moving on this lattice in a self-avoiding random walk with periodic boundary conditions. One person starts at position (5,15) and the other starts at (15,5). “Self-avoiding” means that once a node has been visited by one of the walkers, it can never be visited again by either walker.
Help in making this self avoiding and adding another walker??
if true
%Random walk in 2D, periodic boundaries
xmax = 20; %grid size
ymax = 20; %grid size
nsteps = 400; %number of steps in the simulation
x = round(xmax/2);
y = round(ymax/2);
plot(x,y,'bo')
ht = title('Steps taken = 0');
h = [];
axis([0.8 xmax+0.2 0.8 ymax+0.2])
hold on
for i = 1:nsteps
d = randi(4); %direction (north(1), west(2), south(3), east(4))
dx = 0;
dy = 0;
switch d
case 1
dy = 1;
case 2
dx = -1;
case 3
dy = -1;
case 4
dx = 1;
end
nx = x + dx;
ny = y + dy;
%Now apply periodic boundary conditions
if nx<1
x = x + xmax;
nx = nx + xmax;
elseif nx>xmax;
x = x - xmax;
nx = nx - xmax;
end
if ny<1
y = y + ymax;
ny = ny + ymax;
elseif ny>ymax;
y = y - ymax;
ny = ny - ymax;
end
%Draw a line from the current position to the next position
if ~isempty(h)
set(h,'MarkerEdgeColor','b')
end
line([x nx],[y ny])
h = plot(nx,ny,'r*');
set(ht,'String',['Steps taken = ' num2str(i)])
x = nx;
y = ny;
pause(0.1) %the pause that refreshes
end
hold off
end
1 Comment
Accepted Answer
Guillaume
on 19 Nov 2014
Can't you just record all the visited points in a 20x20 logical matrix.
3 Comments
Guillaume
on 19 Nov 2014
%... (initialisation)
visited = zeros(xmax, ymax); %turn to 1 when visited
for i = 1:nsteps
cangothatway = [ ~visited(x, mod(y, ymax)+1) %can go north?
~visited(mod(x-2, xmax)+1, y) %can go west?
~visited(x, mod(y-2, ymax)+1) %can go south?
~visited(mod(x, xmax)+1, y)]; %can go east?
availabledir = find(cangothatway);
if isempty(availabledir)
%reached a dead end!
break;
end
dirindex = randi(numel(availabledir));
d = availabledir(dirindex);
%... (calculate next position, draw line, etc.)
visited(x, y) = 1;
end
Image Analyst
on 19 Nov 2014
Or, using logical data type.
visited = false(xmax, ymax); % Turn true when visited
...
visited(x, y) = true;
More Answers (0)
See Also
Categories
Find more on Directed Graphs in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!