# =========================================================================== # # 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)[]
}