# =========================================================================== # # Depth First Search maze generation. I used an octagonal grid for fun. # # Taken from: www.contextfreeart.org/gallery/view.php?id=4264 # # Added: 22.12.2021 # # Autor: flembobs # =========================================================================== #

CF::Impure = 1 CF::Background = [ b -0.86 h 230 sat 0.6 ]

vector2 vertex(i,n,l)=let(A=(360*(i/n));(sin(A)*l,cos(A)*l))

vector8 O8()=0,0,0,0,0,0,0,0 vector64 O64()=O8(),O8(),O8(),O8(),O8(),O8(),O8(),O8()

# convert grid x,y pos to vector64 index, -1 = out of bounds idx(vector2 pos)=

if( pos[0]<0 || pos[0]>=8 || pos[1]<0 || pos[1]>=8,
  -1,
  8*pos[1]+pos[0])

# convert vector idx to grid pos vector2 idx_pos(i)=(mod(i,8),floor(i/8))

# convert a direction index to a grid offset vector2 dir(k)=select(k,

(1,0),
(1,1),
(0,1),
(-1,1),
(-1,0),
(-1,-1),
(0,-1),
(1,-1))

# return index of neighbour of i at k (or -1) neighbour(i,k)=

let(
  pos_i=idx_pos(i);
  k_off=dir(k);
  step_k=(pos_i[0]+k_off[0],pos_i[1]+k_off[1]);
  idx(step_k)
)

# return 0..7 if i and j are adjecent else -1 adjacent_(i,j,k)=

if(k<0,-1,
  if(neighbour(i,k)==j, k, adjacent_(i,j,k-1)))

adjacent(i,j)=adjacent_(i,j,7)

# return direction opposite to dir i opposite(i)=mod(i+4,8)

# is there a wall at cell i, in pos j? wall(vector2 pos,k,vector64 maze)=

neighbour(idx(pos),k) ≠ -1 &&
bitand(bitright(maze[idx(pos)],k),1) == 1
# Note: 1 = wall, 0 = path

# Stack = [ size, 1..64 ] # Store 64 values in stack with first elem = stack size

# create empty stack vector65 stack_new()=(0,O64())

# size of stack is stored in final element stack_size(vector65 S)=S

# Read value from top of stack stack_head(vector65 S)=S

# Discard the top value from stack return new vector vector65 stack_pop(vector65 S)=

(S[0]-1,0,S[1,63])

# Push i onto the stack vector65 stack_push(vector65 S, i)=

(S[0]+1,S[2,63],i)

# Edit vector V to put value n at index i – # - it is broken up this way to avoid cfdg stack overflow vector4 ev4(vector4 V, i, n)=

if(i==0,n,V[0]),if(i==1,n,V[1]),
if(i==2,n,V[2]),if(i==3,n,V[3])

vector8 ev8(vector8 V, i, n)=

let(
  A=V[0,4];B=V[4,4];
  len=4;L=i<len;
  (if(L,ev4(A,i,n),A),if(L,B,ev4(B,i-len,n)))
)

vector16 ev16(vector16 V, i, n)=

let(
  A=V[0,8];B=V[8,8];
  len=8;L=i<len;
  (if(L,ev8(A,i,n),A),if(L,B,ev8(B,i-len,n)))
)

vector32 ev32(vector32 V, i, n)=

let(
  A=V[0,16];B=V[16,16];
  len=16;L=i<len;
  (if(L,ev16(A,i,n),A),if(L,B,ev16(B,i-len,n)))
)

vector64 ev64(vector64 V, i, n)=

let(
  A=V[0,32];B=V[32,32];
  len=32;L=i<len;
  (if(L,ev32(A,i,n),A),if(L,B,ev32(B,i-len,n)))
)

vector64 edit_vector(vector64 V, i, n)= ev64(V,i,n)

unvisited_neighbour_(vector64 V, i,k,r_off)=

if(k<0, -1,
  let(
    N=neighbour(i,mod(k+r_off,8));
    if(N==-1 || is_visited(V,N), 
      unvisited_neighbour_(V, i,k-1,r_off),
      N)
  )
)

unvisited_neighbour(vector64 V, i)=

unvisited_neighbour_(V, i,7,randint(8))

vector64 mark_visited(vector64 V, i)=

edit_vector(V,i,1)

is_visited(vector64 V, i) = V==1

vector64 link(vector64 maze,i,j)=

let(
  I=min(i,j);
  J=max(i,j);
  ki=adjacent(I,J);
  I0=maze[I];
  linked=bitor(I0,bitleft(1,ki));
  if(ki==-1,
    maze,
    edit_vector(maze,I,linked)
  )
)

startshape DFS_MAZE (O64(), stack_push(stack_new(),randint(64)), O64()) []

shape DFS_MAZE(vector64 maze, vector65 S, vector64 V) {

if ( stack_size(S)<=0 )
{
  MAZE(maze)[]
}
else
{
  i=stack_head(S)
  V1=mark_visited(V,i)
  N=unvisited_neighbour(V1,i)
  S1=if(N==-1,stack_pop(S),stack_push(S,N))
  M1=if(N==-1,maze,link(maze,i,N))
  DFS_MAZE(M1,S1,V1)[]
}

}

shape MAZE(vector64 maze) {

loop i=8 [ x 1 ]
loop j=8 [ y -1 ]
{
  OCT(0)[ s 0.7 b 1 ]
  OCT(1)[ s 0.7 b 0.2 ]
  CIRCLE [ s 0.2 b 1 z 1000]
  loop k=4 [h 60]
  {
    W = wall((i,j),k,maze)

    if(W)
    {
      p0=(0,0)
      L=if(mod(k,2)==0,1,sqrt(2))
      p1=vertex(k+2,8,L)
      LINE(p0,p1)[b 0.8 sat 0.8 z 100]
    }
  }
}

}

path LINE(vector2 p1, vector2 p2) {

MOVETO(p1)
LINETO(p2)
STROKE(0.1, CF::RoundCap)[]

}

path OCT(F) {

MOVETO(vertex(0,8,0.5))

loop i=8 [] LINETO(vertex(i,8,0.5))
CLOSEPOLY()

if(F)
  FILL()[]
else
  STROKE(0.08)[]

}