# How to change from random walk ro self avoiding random walk in Julia

Could someone help me to change the random walk to self-avoiding random walk? I tried to do that but without success. Below is the code for the random walk, that works:

``````using StatsBase, LinearAlgebra

# Here I defined the position in the NxN matrix
function position(vertical, horizontal, N)

ud = BitArray(a == vertical  for a = 1:N )              # Goes up or down
lr = transpose(BitArray(a == horizontal  for a = 1:N )) # Goes left or right

return ud .* lr
end

function SAW(N, Iterations=3) # SAW, Self Avoiding Walk

x = ceil(N/2) # x,y are the starting positions
y = ceil(N/2)
Mat = zeros(Int8, N , N)  # this is the lattice
pos = zeros(Int8, N , N) # this is our position

for i in 1:Iterations

RandomOnes = sample(-1:2:1, 2, replace = false)  #gives the values -1 or 1
ZeroOne    = sample(0:1, 1, replace = false)     #gives the values 0 or 1

#Check where a free space is and create a list accordingly

# In order to avoid moving diagonally, only one of the two variables (x,y)
# can have the values 1 or -1, the other one has to be 0 (e.g. if x = 1 then y = 0)
if ZeroOne == 1
x += RandomOnes
y += 0
else
x += 0
y += RandomOnes
end

Mat += position(y,x,N)
pos  = position(y,x,N)
end

for i in 1:N
for j in 1:N
if Mat[i,j] == 1
Mat[i,j] += 0
end
end
end

return Mat, pos
end
``````

I know that I have to save the last position of my walker, and see if he was already there but I have no idea how to implement it in my code

Which part is confusing to you?
You can start by creating some array or set to hold the past positions. Every time the walker moves, you save the new position inside it. Every time the walker is supposed to move, you check if the potential new position is inside the array or not, and handle accordingly.

4 Likes

A naive approach to implement a SAW would be to set a volume for each random walker. At each time, you have to check if the current walker is within any volume of other existing walkers. However, this approach is not practically useful. To see a review of advanced algorithms, see here for example: simulator.

unfortunately thats the part where I don’t know how to code, I tried a different approach for avoiding runing into itself:

``````   for i in 1:11

RandomOnes = sample(-1:2:1, 2, replace = false)  #gives the values -1 or 1
ZeroOne    = sample(0:1, 1, replace = false)     #gives the values 0 or 1

if ZeroOne == 1
if position(y+1,x,N)[y+1,x] & position(y-1,x,N)[y-1,x] == 0
y += RandomOnes
x += 0
elseif position(y+1,x,N)[y+1,x] == 0
y += 1
x += 0
elseif position(y-1,x,N)[y-1,x] == 0
y += -1
x += 0
end
return x, y

if ZeroOne == 0
if position(y,x+1,N)[y,x+1,] & position(y,x-1,N)[y,x-1] == 0
x += RandomOnes
y += 0
elseif position(y,x+1,N)[y,x+1] == 0
x += 1
y += 0
elseif position(y,x-1,N)[y,x-1]== 0
x += -1
y += 0
end
``````

Please be more specific. Do you not know how to create an array, or how to check membership of one? Or how to put something into an array? Because those are the three things you need.

I guess all the things you mentioned

``````positions = [] # create
push!(positions, newpos) # put newpos in array
if newpos in positions
# do stuff
end
``````

The order and when to do what is for you to figure out (refer to my first comment).

1 Like

Welcome Student!

Allow me first, if I may, to advice you to consider to change your nick to Courageous_Student Here you have a solution I wrote quickly; I haven’t tested it thoroughly but it shows nonetheless a few of the things you can do in Julia and perhaps you can adapt it to you needs. Hopefully is self-explanatory but ask questions otherwise.

``````using DataStructures

function sarw(latsize::T,
start::Tuple{T,T},
nsteps::T) where T<: Integer

# Ordered Dictionary to store a `from` `to` lattice
# of size latsize x latsize
lat = OrderedDict{Tuple{T,T},Tuple{T,T}}()

# possible movements
up(pos) = (pos,pos+1)
down(pos) = (pos,pos-1)
left(pos) = (pos-1,pos)
right(pos) = (pos+1,pos)

# returns free positions to move from pos
function free(pos,latsize)
frl = []
check(dir) = (1<= dir <= latsize) && (1<= dir <= latsize) &&
check(up(pos))
check(down(pos))
check(left(pos))
check(right(pos))
frl
end

# nsteps number of steps
for i in 1:nsteps
fw = free(start,latsize)
if length(fw) == 0
@info "no free places to move"
return lat
end
start = lat[start] = rand(fw)
end

lat
end
``````

If we run the code we have

``````using Random
Random.seed!(36)

# self-avoiding random walk starting at (50,50) in a lattice of 100x100
# and performing 1000 steps or stopping when the random walk is blocked.
rw = sarw(100,(50,50),1000)

[ Info: no free places to move
OrderedDict{Tuple{Int64, Int64}, Tuple{Int64, Int64}} with 59 entries:
(50, 50) => (50, 51)
(50, 51) => (49, 51)
(49, 51) => (49, 52)
(49, 52) => (49, 53)
[...]
``````

We can also plot the walk with Julia

``````using Plots
plot()
for (k,v) in rw
plot!([k,v],[k,v],arrow=true,color=:black,
linewidth=2,label=nothing)
end
current()
`````` 2 Likes