Task

For a maze generated by this task, write a function
that finds (and displays) the shortest path between two cells.



Note that because these mazes are generated by the Depth-first search algorithm, they contain no circular paths,
and a simple depth-first tree search can be used.




ver,hor:=make_maze();  // see above link for this code
 
fcn munge(a,b){ String(a[0,2],b,a[3,*]) } // "+---" --> "+-*-"
 
fcn solveMaze(ver,hor, a,b, u,v, w,h){
   if (a==u and b==v) return(True);
 
   sh:=hor[b][a]; sv:=ver[b][a];
   hor[b][a]=munge(sh,"*"); ver[b][a]=munge(sv,"*");   // drop breadcrumb
 
   foreach dx,dy in (T( T(0,-1),T(1,0),T(0,1),T(-1,0) )){
      x:=a+dx; y:=b+dy; hy:=hor[y]; vy:=ver[y];
      if ( (0<=x<w) and (0<=y<h) and // (x,y) in bounds
	   (dx==0 or (dx== 1 and vy[x]=="    ") or   // horizontal
		     (dx==-1 and vy[a][0]==" " and vy[x][2]!="*")) and
	   (dy==0 or (dy== 1 and hy[x]=="+   ") or   // vertical
		     (dy==-1 and hor[b][a][1]==" " and hy[x][2]!="*"))
         )
      {
	 sh:=hy[x];
	 if(solveMaze(ver,hor, x,y, u,v, w,h)){
	    hy[x]=sh; // remove splat on wall but not floor while backing out
	    return(True); 
	 }
      }
   }
   hor[b][a]=sh; ver[b][a]=sv;  // pick up breadcrumb when backtracking
   return(False);
}
 
w:=(hor[0].len() - 1); h:=(hor.len() - 1);
startx:=(0).random(w); starty:=(0).random(h);
endx  :=(0).random(w); endy  :=(0).random(h);
 
sh:=hor[starty][startx];
if (not solveMaze(ver,hor, startx,starty, endx,endy, w,h))
   println("No solution path found.");
else{
   hor[starty][startx]=sh;
   ver[starty][startx]=munge(ver[starty][startx],"S");
   ver[endy][endx]    =munge(ver[endy][endx],"E");
   foreach a,b in (hor.zip(ver)) { println(a.concat(),"\n",b.concat()) }
}