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

General Usage
1

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)[1]  #gives the values -1 or 1
        ZeroOne    = sample(0:1, 1, replace = false)[1]     #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

2

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
3

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.

4

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)[1]  #gives the values -1 or 1
        ZeroOne    = sample(0:1, 1, replace = false)[1]     #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
5

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.

6

I guess all the things you mentioned

7 
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
8

Welcome Student!

Allow me first, if I may, to advice you to consider to change your nick to Courageous_Student :slightly_smiling_face:

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[1],pos[2]+1)
    down(pos) = (pos[1],pos[2]-1)
    left(pos) = (pos[1]-1,pos[2])
    right(pos) = (pos[1]+1,pos[2])

    # returns free positions to move from pos
    function free(pos,latsize)
        frl = []
        check(dir) = (1<= dir[1] <= latsize) && (1<= dir[2] <= latsize) &&
                     !haskey(lat,dir) && push!(frl,dir)
        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[1],v[1]],[k[2],v[2]],arrow=true,color=:black,
          linewidth=2,label=nothing)
end
current()

image

2 Likes