How to generate a random walk along the edges in a hexagon grid?

I wrote the following function to generate a 2D hexagonal grid taking inputs a1, a2 (the direction cosines of two edges of a hexagon) and the number of hexagons on each side. I need to generate a random walk such that the path is only along the edges of the hexagon and moving forward (along the positive x-axis, the path should not trace back to the origin). Can anyone help me out? I tried biasing the paths but it didn't work. Attaching the code for generation of the hexagon grid. A simple execution of the code would be:

>> a1=[1 0];

>> a2=[-1/2 sqrt(3)/2];

>> h=10;

>> top=3;

>> btm=3;

>> hexmesh(a1,a2,h,top,btm);

function[vertices] = hexmesh(a1,a2,h,top,btm)
% a1=First vector
% a2=Second vector
% h=cells horizontal
% top=cells above
% btm=cells below
% This function plots a hexagonal grid having h*(top+btm) cells with
% a1 and a2 being the two vectors comprising the first hexagon in the
% formula hex = a0 + m*a1 + n*a2 where m,n are integers
%% Drawing the top half
numhex=0;
vertices=[];
for ii=1:h % horizontal cells
    for jj=1:top % number of cells at top half
        a1=[1 0];
        a2=[-1/2 sqrt(3)/2];
        if rem(ii-1,2) == 0
            transh=(3/2)*(ii-1)*a1;
        end
        if rem(ii-1,2) == 1
            transh=((3/2)*ii-1)*a1+ a2;
        end   
        transv=(jj-1)*(a1+2*a2);
        x1=0*a1+0*a2 + transh + transv;
        x2=1*a1+0*a2 + transh + transv;
        x3=0*a1+1*a2 + transh + transv;
        x4=2*a1+1*a2 + transh + transv;
        x5=1*a1+2*a2 + transh + transv;
        x6=2*a1+2*a2 + transh + transv;
        vxt=0.25.*[x1(1) x3(1) x5(1) x6(1) x4(1) x2(1) x1(1)]-0.124181; % set of x-coor points from a single polygon in top half
        vyt=0.25.*[x1(2) x3(2) x5(2) x6(2) x4(2) x2(2) x1(2)];
        plot(vxt,vyt,'k'); hold on;
        numhex=numhex+1;
        dum=[vxt(1:6);vyt(1:6)];
        vertices=[vertices dum];
    end
end
axis equal;
%% Drawing bottom half
a2(2)=-a2(2);
for kk=1:h 
    for ll=1:btm % number of cells in btm half
        if rem(kk-1,2) == 0
            transh=(3/2)*(kk-1)*a1;
        end
        if rem(kk-1,2) == 1
            transh=((3/2)*kk-1)*a1+ a2;
        end   
        transv=(ll-1)*(a1+2*a2);
        x11m=0*a1+0*a2 + transh + transv;
        x22m=1*a1+0*a2 + transh + transv;
        x33m=0*a1+1*a2 + transh + transv;
        x44m=2*a1+1*a2 + transh + transv;
        x55m=1*a1+2*a2 + transh + transv;
        x66m=2*a1+2*a2 + transh + transv;
        vxb=0.25.*[x11m(1) x33m(1) x55m(1) x66m(1) x44m(1) x22m(1) x11m(1)]-0.124181; % set of x-coor points from a single polygon in bottom half
        vyb=0.25.*[x11m(2) x33m(2) x55m(2) x66m(2) x44m(2) x22m(2) x11m(2)];
        plot(vxb,vyb,'k');
        numhex=numhex+1;
        dum=[vxb(1:6);vyb(1:6)];
        vertices=[vertices dum];
    end
end
grid on
%% Drawing middle hexagons
% a3,a4=vectors comprising the middle row of hexagons
a3=[-a2(1) a2(2)];
a4=[-a2(1) -a2(2)];
for pp=1:h/2
    transh=3*(pp-1)*a1;
    x11m=1*a3+1*a4 + transh;
    x22m=2*a3+1*a4 + transh;
    x33m=3*a3+2*a4 + transh;
    x44m=3*a3+3*a4 + transh;
    x55m=2*a3+3*a4 + transh;
    x66m=1*a3+2*a4 + transh;
    vxm=0.25.*[x11m(1) x22m(1) x33m(1) x44m(1) x55m(1) x66m(1) x11m(1)]-0.124181;
    vym=0.25.*[x11m(2) x22m(2) x33m(2) x44m(2) x55m(2) x66m(2) x11m(2)];
    plot(vxm,vym,'k');
    numhex=numhex+1;
    dum=[vxm(1:6);vym(1:6)];
    vertices=[vertices dum];
end

Answer 1

[Debadipto]

Hi Retam,

You can use the following function to generate a random walk along the edges in the hexagon grid. The function takes as input the "vertices" vector generated by the "hexmesh" function.

function random_walk(vertices)
    
    v = unique(round(vertices', 4), 'rows');
    l = 1;
    r = 1;
    i = 1;
    d = dictionary;
    temp_len = 0;
    
    % the vertices and edges of the hexagon can be seen as a graph
    % so we create a directed adjacency list of vertices of the hexagon
    while r < size(v, 1)
        while r <= size(v, 1) && v(l, 1) == v(r, 1)
            r = r + 1;
        end 
        if temp_len == 0
            temp_len = r - 1;
        end
        stop = r;

        if mod(i, 2) == 0
            while r <= size(v, 1) && l < stop
                d(num2str([v(l, 1) v(l, 2)])) = num2str([v(r, 1) v(r, 2) v(r, 1) v(r, 2)]);                
                r = r + 1;
                l = l + 1;
            end
        elseif i == 1 || mod(i - 3, 4) == 0
            while r <= size(v, 1) && l < stop
                d(num2str([v(l, 1) v(l, 2)])) = num2str([v(r, 1) v(r, 2) v(r + 1, 1) v(r + 1, 2)]);                
                r = r + 1;
                l = l + 1;
            end                
        else
            d(num2str([v(l, 1) v(l, 2)])) = num2str([v(r, 1) v(r, 2) v(r, 1) v(r, 2)]);                
            r = r + 1;
            l = l + 1;
            while r <= size(v, 1) && l < stop - 1
                d(num2str([v(l, 1) v(l, 2)])) = num2str([v(r - 1, 1) v(r - 1, 2) v(r, 1) v(r, 2)]);                
                r = r + 1;
                l = l + 1;
            end        
            d(num2str([v(l, 1) v(l, 2)])) = num2str([v(r - 1, 1) v(r - 1, 2) v(r - 1, 1) v(r - 1, 2)]);                
            l = l + 1;
        end

        i = i + 1;
    end
        
    x = [];
    y = [];
    rnd = randi(temp_len, 1, 1);
    vertex = num2str([v(rnd, 1) v(rnd, 2)]);

    x(end + 1) = v(rnd, 1);
    y(end + 1) = v(rnd, 2);
    
    % generate a random walk across the nodes of the graph
    while isKey(d, vertex)
        rnd = randi(2, 1, 1);
        temp = str2num(d(vertex));
         
        next_vertex = [];
        if mod(rnd, 2) == 0
            next_vertex = [temp(1, 1) temp(1, 2)];
        else
            next_vertex = [temp(1, 3) temp(1, 4)];
        end

        x(end + 1) = next_vertex(1, 1);
        y(end + 1) = next_vertex(1, 2);
        vertex = num2str(next_vertex);
    end

    plot(x, y, 'r', 'LineWidth', 2);
end

The function can be used as illustrated in the following code snippet

>> a1=[1 0];
>> a2=[-1/2 sqrt(3)/2];
>> h=10;
>> top=3;
>> btm=3;
>> vertices = hexmesh(a1,a2,h,top,btm);
>> random_walk(vertices);

Generated random walk:

Regards,

Debadipto Biswas

[Retam Paul]

Worked like a charm. Thanks a lot. I will update further if I run into any special case using your code!!