Maze solving: Difference between revisions

From Rosetta Code
Content added Content deleted
m ({{omit from|GUISS}})
Line 851: Line 851:
+---+---+---+---+---+---+---+---+---+---+---+
+---+---+---+---+---+---+---+---+---+---+---+
</pre>
</pre>

{{omit from|GUISS|Only the operator can see where the walls of the maze are}}
{{Unimpl Page|ZX Spectrum Basic}}

Revision as of 14:57, 12 July 2011

Task
Maze solving
You are encouraged to solve this task according to the task description, using any language you may know.

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.

C

Taken from maze generation task, with slight modification. I chose to show a slim maze because I found it somehow amusing. <lang C>#include <stdio.h>

  1. include <stdlib.h>

enum { NORTH, EAST, WEST, SOUTH, USED = 1 << 4, DEST = 1 << 5,

};

typedef struct cell_t *cell; struct cell_t { int conn; /* or'd flags: 4 directions, and USED */ cell c[4]; /* direction to neighbors */ };

  1. define can_go(c, i) (c->c[i] && !(c->c[i]->conn & USED))

void walk(cell c) { c->conn |= USED; while (1) { for (int i = 0, a = 0; i < 4; i++) { a += can_go(c, i); if (i == 3 && !a) return; }

int d; do { d = rand() % 4; } while (!can_go(c, d));

c->conn |= (1 << d); c->c[d]->conn |= (1 << (3 - d));

walk(c->c[d]); } }

  1. define can_try(c, dir) \

(c->c[dir] && !(c->c[dir]->conn & USED) && (c->conn & (1 << dir))) int solve(cell c) { c->conn |= USED; if (c->conn & DEST) return 1; /* solved */ for (int d = 0; d < 4; d++) if (can_try(c, d) && solve(c->c[d])) return 1; c->conn &= ~USED;

return 0; }

  1. define for_i for(int i = 0; i <= y; i++)
  2. define for_j for(int j = 0; j <= x; j++)
  3. define goes(dir) (cells[i][j].conn & (1 << dir))

void make_maze(int y, int x) { struct cell_t cells[y][x]; x--; y--;

for_i for_j { cell c = &cells[i][j]; c->conn = 0; c->c[NORTH] = i > 0 ? &cells[i - 1][ j ] : 0; c->c[SOUTH] = i < y ? &cells[i + 1][ j ] : 0; c->c[WEST] = j > 0 ? &cells[ i ][j - 1] : 0; c->c[EAST] = j < x ? &cells[ i ][j + 1] : 0; } walk(&cells[0][0]);

/* mark cells for solving */ for_i for_j cells[i][j].conn &= ~USED; cells[y][x].conn |= DEST; solve(&cells[0][0]);

for_j { printf("+---"); } printf("+\n");

for_i { for_j { printf(j > 0 && goes(WEST) ? " " : "| "); printf( (cells[i][j].conn & USED) ? "* " : " "); } printf("|\n");

for_j { printf(i < y && goes(SOUTH) ? "+ " : "+---"); } printf("+\n"); } }

int main() { //srand(time(0)); make_maze(4, 20); }</lang>Output:<lang>+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | * | | * * * * * * * * | | | + +---+ +---+ +---+ +---+---+---+---+---+---+ +---+ + +---+ + + | * * | | * * | | | * * | | | | +---+ +---+ +---+ +---+ + +---+ + +---+---+ +---+---+ +---+ + | | * * | | * * | | | | | * * * | | * * | + +---+ +---+---+---+ + + + +---+---+---+ +---+---+ +---+ + + | * * * * * | | | * * * | * | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+</lang>

D

Basic define <lang d>import std.stdio, std.random ;

immutable string[] Tiles = 

   [" ","╞","╥","╔","╡","═", "╗","╦","╨","╚","║","╠","╝","╩","╣","╬"] ;

immutable string[] Paths = 

   [" "," "," ","┌"," ","─", "┐"," "," ","└","│"," ","┘"," "," "," "] ;

alias uint Room ; enum Open { EMPTY = 0U , EAST = 1, SOUTH = 2, WEST = 4, NORTH = 8, 

           EPATH = 16, SPATH = 32, WPATH = 64, NPATH = 128,
           ENTRY = 256, EXIT = 512, Visited = 1024 }

struct Where { 

   immutable int x, y ;
   Where opBinary(string op)(Where rhs) if (op=="+") {
       return Where(x + rhs.x, y + rhs.y) ;
   }
   bool bounded(int w, int h) {
       return (x >= 0 && y >= 0 && x < w && y < h) ;
   }
   bool bounded(Room[][] r) {
       return (x >= 0 && y >= 0 && r.length > 0 && y < r.length && x < r[0].length ) ;
   }

} struct Door { Open opening = Open.EMPTY ; Where where ; alias where this ; }

immutable Open[Open] Opposite ; immutable Where[Open] NeibrPos ;

static this() { // workarround for Associative Array init. 

   Opposite = [Open.EAST:Open.WEST, Open.SOUTH:Open.NORTH,
               Open.WEST:Open.EAST, Open.NORTH:Open.SOUTH] ;
   NeibrPos = [Open.EAST:Where( 1,0), Open.SOUTH:Where(0, 1),
               Open.WEST:Where(-1,0), Open.NORTH:Where(0,-1)] ;

}

const AsPath = true ;

void connectTo(ref Room[][] r, Door d, bool asPath = false) { 

       auto s/*hift*/ = asPath ? 4 : 0 ;
       r[d.y][d.x] |= (d.opening << s) ;
       auto there = d.where + NeibrPos[d.opening] ;
       if(there.bounded(r))
           r[there.y][there.x] |= (Opposite[d.opening] << s) ;

} bool connected(ref Room[][] r, Door d) { 

       auto there = d.where + NeibrPos[d.opening] ;
       return (r[    d.y][    d.x] & d.opening) && there.bounded(r) &&
              (r[there.y][there.x] & Opposite[d.opening]) ;

}

void printMaze(Room[][] maze, bool showPath = false) { 

   foreach(row ; maze) {
       foreach(cell;row)
           if(showPath)
               write(Paths[0xf & (cell >> 4)]) ;
           else
               write(Tiles[0xf & (cell)]) ;
       writeln() ;
   }

} </lang> Generate Maze: <lang d>Room[][] genMaze(uint w, uint h, ref Door entry = Door.init, ref Door exit = Door.init) { 

   Room[][] r = new Room[][](h, w) ; // default value = 0 means un-visited empty room

   bool validDoor(Door d) {
       if(d.where.bounded(w,h))
           switch(d.opening) {
               case Open.EAST : return (d.x == w - 1) ;
               case Open.WEST : return (d.x == 0) ;
               case Open.NORTH: return (d.y == 0) ;
               case Open.SOUTH: return (d.y == h - 1) ;
           }
       return false ;
   }

   Door makeDoor() { // create door at random edge
       switch([Open.EAST, Open.WEST, Open.NORTH, Open.SOUTH][uniform(0,4)]) {
           case Open.EAST : return Door(Open.EAST , Where(w-1, uniform(0,h))) ;
           case Open.WEST : return Door(Open.WEST , Where(  0, uniform(0,h))) ;
           case Open.NORTH: return Door(Open.NORTH, Where(uniform(0,w),   0)) ;
           case Open.SOUTH: return Door(Open.SOUTH, Where(uniform(0,w), h-1)) ;
       }
   }

   Open[] neibrDir = NeibrPos.keys ;

   // depth-first search algorithm to generate maze
   void visit(Where here) {
       r[here.y][here.x] |= Open.Visited ;
       randomShuffle(neibrDir) ;
       foreach(dir; neibrDir) {
           auto there = here + NeibrPos[dir] ;
           if(there.bounded(w,h))                              // bounded?
               if((r[there.y][there.x] & Open.Visited) == 0) { // un-visited?
                   connectTo(r, Door(dir, here)) ;
                   visit(there) ;
               }
       }
   }

   // make entry & exit doors if not provided or invalid
   while(entry.opening == Open.EMPTY || entry.where == exit.where || !validDoor(entry))
       entry = makeDoor() ;
   while( exit.opening == Open.EMPTY || entry.where == exit.where || !validDoor(exit))
       exit  = makeDoor() ;
   r[entry.y][entry.x] |= (entry.opening | Open.ENTRY) ;
   r[ exit.y][ exit.x] |= ( exit.opening | Open.EXIT) ;

   // generate maze starting from entry
   visit(entry.where)  ;

   return r ;

}</lang> Solver: <lang d>bool solveMaze(ref Room[][] r, Door entry, Door exit ) { 

   Open[] neibrDir = NeibrPos.keys ;

   foreach(row ; r) // clear old path, if any
       foreach(cell;row)
           cell &= ~(Open.EPATH|Open.WPATH|Open.SPATH|Open.NPATH) ;

   bool trace(Door here) {
       if(here.where == exit.where) { // reach exit
           r.connectTo(exit, AsPath) ;
           return true ;
       }
       foreach(dir ; neibrDir) {
           //  here.opening is direction to enter the room@here
           //  _dir_ is direction to exit the room@here, which is opposite to there.opening
           if( (dir != here.opening) && ((dir & r[here.y][here.x]) != 0)) { // path exist?
               auto there = Door(Opposite[dir], here.where + NeibrPos[dir]) ;
               if( there.bounded(r))
                   if(trace(there)) { // reach exit, use stack to trace back the path
                       r.connectTo(Door(dir, here.where), AsPath) ;
                       return true ;
                   }
           }
       }
       return false ; // dead end
   }

   auto success = trace(entry) ;
   if(success)
       r.connectTo(entry, AsPath) ;
   return success ;

}</lang> Sample run: <lang d>void main() { 

   Door entry, exit;
   auto maze = genMaze(40, 12, entry, exit) ;

   printMaze(maze) ;
   if(solveMaze(maze, entry, exit))
       printMaze(maze, AsPath) ;
   else
       writeln("No solution!?") ;

}</lang> Output:) 

╔═╗╞╗╔╡╔══╗╔╦╗╔═╗╞╗╔═══╦══╗╞╗╔═╗╔╦╗╚╗╞═╗
╚╗╚═╝╠╗║╔╗╚╝║║║╞╩═╝╚╗╔═╝╔╗╠═╝╠╡╠╝╨╚╗╚═╦╝
╔╝╔══╝╚╩╝╚╡╔╝║╠════╗║╚═╗║║║╔╗║╔╝╔══╩═╡╚╗
╠╗║╔╗╔═╗╥╔╗║╥║╨╔╗╔╗║║╞╗║╨╚╝║╚╝║╥║╞╦╗╔╦╡║
║╚╝╨╚╣╔╩╣║╚╝║╚╗║╚╝╚╣╚╦╝╚╗╔═╝╞╗║║╠╗║║║╚╗║
╚═══╗╨╚╗║║╔╡╚╗╚╣╥╔╗╚╗╚╗╥║╚═╗╔╝║║║╚╝╨║╥║║
╔═══╝╔═╣║╚╩═╗║╔╝╚╝╚═╝╔╝║╚═╗║╚╗║╠╝╔══╝║╚╝
╚═╗╔═╝╞╝╚═╗╔╝║╚╗╔═╗╔╗║╞╬╗╥║╚╗║║╠╡╚══╗╚═╗
╔═╝║╔╗╔═╗╔╝╚╗╚╦╝║╥╚╝╚╝╔╝╚╣╚╗║║║╨╔══╗╚╗╔╣
╩══╝║╚╝╥╠╝╞╗║╥║╔╝╠╦╗╔╗╚═╗╚╗║║║╚═╝╔╡║╔╩╝╨
╔╡╔╦╝╔═╣╚═╗║║╚╝║╞╝║║╨╠══╝╥║╠╝╠╗╞═╣╔╝╚══╗
╚═╝╚═╝╞╝╞═╩╝╚══╩══╝╚═╝╞══╩╝╚═╝╚══╝╚════╝
       ┌──┐┌┐      ┌───┐     ┌─┐   └┐   
     ┌┐│  └┘│      └┐┌─┘     │ │    └─┐ 
  ┌──┘└┘   ┌┘       │└─┐   ┌┐│┌┘      └┐
┌┐│      ┌┐│        │  │   │└┘│     ┌┐ │
│└┘      │└┘        └┐ └┐┌─┘  │     │└┐│
└───┐    │           └┐ │└─┐  │     │ ││
┌───┘    └──┐        ┌┘ └─┐│  │  ┌──┘ └┘
└─┐        ┌┘   ┌─┐┌┐│    │└┐ │  └──┐   
┌─┘        └┐   │ └┘└┘    └┐│ │ ┌──┐└┐  
┘           │  ┌┘          ││ └─┘  │┌┘  
            │  │           └┘     ┌┘└──┐
            └──┘                  └────┘
 
 
 
 
 
 
 
 
 
 
 
 
 

J

<lang J> NB. source Dijkstra_equal_weights graph NB. NB. + +---+---+ NB. | 0 1 2 | (sample cell numbers) NB. +---+ + + NB. | 3 4 | 5 NB. +---+---+---+ NB. NB. graph =: 1;0 2 4;1 5;4;1 3;2 NB. The graph is a vector of boxed vectors of neighbors.

Dijkstra_equal_weights =: 4 : 0 

dist =. previous =. #&_ n =. # graph =. y [ source =. x
dist =. 0 source } dist
Q =. 0
while. #Q do.
  u =. {.Q
  Q =. }.Q
  if. _ = u{dist do. break. end.
  for_v. >u{graph do.
    if. -. v e. previous do.
      alt =. >: u { dist
      if. alt < v { dist do.
        dist =. alt v } dist
        previous =. u v } previous
        if. v e. Q do.
          echo 'belch'
        else.
          Q =. Q,v
        end.
      end.
    end.
  end.
end.
dist;previous

)

path =. 3 : 0 

 p =. <:#y
 while. _ > {:p do.
   p =. p,y{~{:p
 end.
 |.}:p

)

solve=:3 :0 

 NB. convert walls to graph
 shape =. }.@$@:>
 ew =. (,.&0 ,: 0&,.)@>@{.  NB. east west doors
 ns =. (, &0 ,: 0&, )@>@{:
 cell_offsets =. 1 _1 1 _1 * 2 # 1 , {:@shape
 cell_numbers =. i.@shape
 neighbors =. (cell_numbers +"_ _1 cell_offsets *"_1 (ew , ns))y
 graph =. (|:@(,/"_1) <@-."1 0 ,@i.@shape)neighbors NB. list of boxed neighbors
 NB. solve it
 path , > {: 0 Dijkstra_equal_weights graph

)

display=:3 :0 NB. Monadic display copied from maze generation task 

 size=. >.&$&>/y
 text=. (}:1 3$~2*1+{:size)#"1":size$<' '
 'hdoor vdoor'=. 2 4&*&.>&.> (#&,{@;&i./@$)&.> y
 ' ' (a:-.~0 1;0 2; 0 3;(2 1-~$text);(1 4&+&.> hdoor),,vdoor+&.>"0/2 1;2 2;2 3)} text

 a=. display y
 size=. >.&$&>/y
 columns=. {: size
 cells =. <"1(1 2&p.@<.@(%&columns) ,.  2 4&p.@(columns&|))x
 '+' cells } a  NB. exercise, replace cells with a gerund to draw arrows on the path.

) 

  4 (display~ solve)@maze 9

┌ ┬───┬───┬───┬───┬───┬───┬───┬───┐ │ + │ │ │ ├ ┼───┼ ┼ ┼ ┼───┼ ┼ ┼ ┤ │ + + │ │ │ │ │ ├───┼ ┼───┼───┼───┼───┼───┼ ┼───┤ │ │ + + + │ + + + │ │ ├ ┼───┼───┼ ┼ ┼───┼ ┼───┼───┤ │ + + │ + + + └───┴───┴───┴───┴───┴───┴───┴───┴───┘

</lang>

PicoLisp

<lang PicoLisp>(de shortestPath (Goal This Maze) 

  (let (Path NIL  Best NIL  Dir " > ")
     (recur (This Path Dir)
        (when (and This (not (: mark)))
           (push 'Path (cons This Dir))
           (if (== Goal This)
              (unless (and Best (>= (length Path) (length Best)))
                 (setq Best Path) )
              (=: mark T)
              (recurse (: west) Path " > ")
              (recurse (: east) Path " < ")
              (recurse (: south) Path " \^ ")
              (recurse (: north) Path " v ")
              (=: mark NIL) ) ) )
     (disp Maze 0
        '((Fld) (if (asoq Fld Best) (cdr @) "   ")) ) ) )</lang>

Using the maze produced in Maze generation#PicoLisp, this finds the shortest path from the top-left cell 'a8' to the bottom-right exit 'k1': 

: (shortestPath 'a8 'k1 (maze 11 8))
   +   +---+---+---+---+---+---+---+---+---+---+
 8 | >   >   v | >   v |                       |
   +   +   +   +   +   +   +---+   +---+---+   +
 7 |   |   | >   ^ | v |   |       |       |   |
   +---+   +---+---+   +   +   +---+   +   +   +
 6 |   |       |     v |   |           |   |   |
   +   +---+   +---+   +---+---+---+   +   +---+
 5 |       |       | >   >   >   v |   |       |
   +---+   +---+   +---+---+---+   +---+---+   +
 4 |   |       |       |       | v | >   >   v |
   +   +---+   +---+   +---+   +   +   +---+   +
 3 |       |       |   |       | v | ^   < | v |
   +   +---+---+   +   +   +   +   +---+   +   +
 2 |       |       |   |   |   | v | >   ^ | v |
   +   +   +   +---+   +   +---+   +   +---+   +
 1 |   |               |         >   ^ |     >
   +---+---+---+---+---+---+---+---+---+---+---+
     a   b   c   d   e   f   g   h   i   j   k

Prolog

Works with SWI-Prolog and XPCE.

<lang Prolog>:- dynamic cell/2.

- dynamic maze/3.
- dynamic path/1.

maze_solve(Lig,Col) :- retractall(cell(_,_)), retractall(maze(_,_,_)), retractall(path(_)),

% initialisation of the neighbours of the cells forall(between(0, Lig, I), ( forall(between(0, Col, J), assert(maze(I, J, []))))),

% creation of the window of the maze new(D, window('Maze')), forall(between(0,Lig, I), (XL is 50, YL is I * 30 + 50, XR is Col * 30 + 50, new(L, line(XL, YL, XR, YL)), send(D, display, L))),

forall(between(0,Col, I), (XT is 50 + I * 30, YT is 50, YB is Lig * 30 + 50, new(L, line(XT, YT, XT, YB)), send(D, display, L))),

SX is Col * 30 + 100, SY is Lig * 30 + 100, send(D, size, new(_, size(SX, SY))), L0 is random(Lig), C0 is random(Col), assert(cell(L0, C0)), \+search(D, Lig, Col, L0, C0), send(D, open),

% we look for a path from cell(0, 0) to cell(Lig-1, Col-1) % creation of the entrance erase_line(D, -1, 0, 0, 0),

% creation of the exit Lig1 is Lig-1, Col1 is Col-1, erase_line(D, Lig1, Col1, Lig, Col1),

% seraching the path assert(path([[0, 0], [-1, 0]])), walk(Lig, Col), path(P), display_path(D, P).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% walk(Lig, Col) :- path([[L, C] | _R]), L is Lig - 1, C is Col - 1, retract(path(P)), assert(path([[Lig, C]|P])).

walk(Lig, Col) :- retract(path([[L, C] | R])), maze(L, C, Edge), member([L1, C1], Edge), \+member([L1, C1], R), assert(path([[L1,C1], [L, C] | R])), walk(Lig, Col).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% display_path(_, []).

display_path(D, [[L, C] | R]):- new(B, box(10,10)), send(B, fill_pattern, new(_, colour(@default, 0,0,0))), X is C * 30 + 60, Y is L * 30 + 60, send(D, display, B, point(X,Y)), display_path(D, R).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% search(D, Lig, Col, L, C) :- Dir is random(4), nextcell(Dir, Lig, Col, L, C, L1, C1), assert(cell(L1,C1)), assert(cur(L1,C1)),

retract(maze(L, C, Edge)), assert(maze(L, C, [[L1, C1] | Edge])), retract(maze(L1, C1, Edge1)), assert(maze(L1, C1, [[L, C] | Edge1])),

erase_line(D, L, C, L1, C1), search(D, Lig, Col, L1, C1).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% erase_line(D, L, C, L, C1) :- ( C < C1 -> C2 = C1; C2 = C), XT is C2 * 30 + 50, YT is L * 30 + 51, YR is (L+1) * 30 + 50, new(Line, line(XT, YT, XT, YR)), send(Line, colour, white), send(D, display, Line).

erase_line(D, L, C, L1, C) :- XT is 51 + C * 30, XR is 50 + (C + 1) * 30, ( L < L1 -> L2 is L1; L2 is L), YT is L2 * 30 + 50, new(Line, line(XT, YT, XR, YT)), send(Line, colour, white), send(D, display, Line).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% nextcell(Dir, Lig, Col, L, C, L1, C1) :- next(Dir, Lig, Col, L, C, L1, C1); ( Dir1 is (Dir+3) mod 4, next(Dir1, Lig, Col, L, C, L1, C1)); ( Dir2 is (Dir+1) mod 4, next(Dir2, Lig, Col, L, C, L1, C1)); ( Dir3 is (Dir+2) mod 4, next(Dir3, Lig, Col, L, C, L1, C1)).

% 0 => northward next(0, _Lig, _Col, L, C, L1, C) :- L > 0, L1 is L - 1, \+cell(L1, C).

% 1 => rightward next(1, _Lig, Col, L, C, L, C1) :- C < Col - 1, C1 is C + 1, \+cell(L, C1).

% 2 => southward next(2, Lig, _Col, L, C, L1, C) :- L < Lig - 1, L1 is L + 1, \+cell(L1, C).

% 3 => leftward next(2, _Lig, _Col, L, C, L, C1) :- C > 0, C1 is C - 1, \+cell(L, C1).

</lang> output :

PureBasic

<lang PureBasic>;code from the maze generation task is place here in its entirety before the rest of the code

Procedure displayMazePath(Array maze(2), List Path.POINT()) 

 Protected x, y, vWall.s, hWall.s
 Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2)
 Protected Dim mazeOutput.mazeOutput(mazeHeight)
 Protected Dim mazeRow.mazeOutput(0)
 Static pathChars.s = "@^>v<"
 
 For y = 0 To mazeHeight
   makeDisplayMazeRow(mazeRow(), maze(), y): mazeOutput(y) = mazeRow(0)
 Next
 
 If ListSize(path())
   FirstElement(path())
   Protected prevPath.POINT = path()
   
   While NextElement(path())
     x = path()\x - prevPath\x
     y = path()\y - prevPath\y
     Select x
       Case -1: dirTaken = #dir_W
       Case 1: dirTaken = #dir_E
       Default
         If y < 0
           dirTaken = #dir_N
         Else
           dirTaken = #dir_S
         EndIf 
     EndSelect
     hWall = mazeOutput(prevPath\y)\hWall
     mazeOutput(prevPath\y)\hWall = Left(hWall, prevPath\x * #cellDWidth + 2) + Mid(pathChars, dirTaken + 1, 1) + Right(hWall, Len(hWall) - (prevPath\x * #cellDWidth + 3))
     prevPath = path()
   Wend 
   hWall = mazeOutput(prevPath\y)\hWall
   mazeOutput(prevPath\y)\hWall = Left(hWall, prevPath\x * #cellDWidth + 2) + Mid(pathChars, #dir_ID + 1, 1) + Right(hWall, Len(hWall) - (prevPath\x * #cellDWidth + 3))
   
   For y = 0 To mazeHeight
     PrintN(mazeOutput(y)\vWall): PrintN(mazeOutput(y)\hWall)
   Next 
 EndIf

EndProcedure

Procedure solveMaze(Array maze(2), *start.POINT, *finish.POINT, List Path.POINT()) 

 Protected mazeWidth = ArraySize(maze(), 1), mazeHeight = ArraySize(maze(), 2)
 Dim visited(mazeWidth + 1, mazeHeight + 1) ;includes padding for easy border detection
 
 Protected i
 ;mark outside border as already visited (off limits)
 For i = 1 To mazeWidth
   visited(i, 0) = #True: visited(i, mazeHeight + 1) = #True
 Next
 For i = 1 To mazeHeight
   visited(0, i) = #True: visited(mazeWidth + 1, i) = #True
 Next
 
 Protected x = *start\x, y = *start\y, nextCellDir
 visited(x + offset(#visited, #dir_ID)\x, y + offset(#visited, #dir_ID)\y) = #True
 
 ClearList(path())
 Repeat
   If x = *finish\x And y = *finish\y
     AddElement(path())
     path()\x = x: path()\y = y
     Break ;success
   EndIf 
   
   nextCellDir = #firstDir - 1
   For i = #firstDir To #numDirs
     If Not visited(x + offset(#visited, i)\x, y + offset(#visited, i)\y)
       If maze(x + offset(#wall, i)\x, y + offset(#wall, i)\y) & wallvalue(i) <> #Null
         nextCellDir = i: Break ;exit for/next search
       EndIf 
     EndIf 
   Next 
   
   If nextCellDir >= #firstDir
     visited(x + offset(#visited, nextCellDir)\x, y + offset(#visited, nextCellDir)\y) = #True
     
     AddElement(path())
     path()\x = x: path()\y = y
     
     x + offset(#maze, nextCellDir)\x: y + offset(#maze, nextCellDir)\y
   ElseIf ListSize(path()) > 0
     x = path()\x: y = path()\y
     DeleteElement(path())
   Else 
     Break
   EndIf 
 ForEver

EndProcedure

demonstration

If OpenConsole() 

 Define.POINT start, finish
 start\x = Random(mazeWidth - 1): start\y = Random(mazeHeight - 1)
 finish\x = Random(mazeWidth - 1): finish\y = Random(mazeHeight - 1)
 NewList Path.POINT()
 solveMaze(maze(), start, finish, path())
 If ListSize(path()) > 0
   PrintN("Solution found for path between (" + Str(start\x) + ", " + Str(start\y) + ") and (" + Str(finish\x) + ", " + Str(finish\y) + ")")
   displayMazePath(maze(), path())
 Else
   PrintN("No solution found for path between (" + Str(start\x) + ", " + Str(start\y) + ") and (" + Str(finish\x) + ", " + Str(finish\y) + ")")
 EndIf 
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf</lang> Using the maze produced in Maze generation#PureBasic, this additional code will find and display the path between two random maze cells. A working example requires combining the two code listings by placing the 'maze generation' code at the beginning of the 'maze solving' code.

Sample output: 

Solution found for path between (3, 2) and (7, 1)
+---+---+---+---+---+---+---+---+---+---+
| v   <   <   <   < |   | v   <   <     |
+   +---+---+---+   +   +   +---+   +---+
| >   v         | ^ |   | v | @ | ^   < |
+---+   +---+---+   +   +   +   +---+   +
|   | v |     >   ^ |     v | ^     | ^ |
+   +   +   +---+---+---+   +   +---+   +
| v   < |               | >   ^ | >   ^ |
+   +---+---+---+---+   +---+   +   +   +
| v |       |           |       | ^ |   |
+   +---+   +   +---+---+---+---+   +---+
| >   >   v |       |     >   v | ^   < |
+---+---+   +---+---+---+   +   +---+   +
|         >   >   >   >   ^ | >   >   ^ |
+---+---+---+---+---+---+---+---+---+---+

Python

<lang Python>

  1. python 3

def Dijkstra(Graph, source): 

   
       +   +---+---+
       | 0   1   2 |
       +---+   +   +
       | 3   4 | 5  
       +---+---+---+

       >>> graph = (        # or ones on the diagonal
       ...     (0,1,0,0,0,0,),
       ...     (1,0,1,0,1,0,),
       ...     (0,1,0,0,0,1,),
       ...     (0,0,0,0,1,0,),
       ...     (0,1,0,1,0,0,),
       ...     (0,0,1,0,0,0,),
       ... )
       ...
       >>> Dijkstra(graph, 0)
       ([0, 1, 2, 3, 2, 3], [1e+140, 0, 1, 4, 1, 2])
       >>> display_solution([1e+140, 0, 1, 4, 1, 2])
       5<2<1<0
   
   # Graph[u][v] is the weight from u to v (however 0 means infinity)
   infinity = float('infinity')
   n = len(graph)
   dist = [infinity]*n   # Unknown distance function from source to v
   previous = [infinity]*n # Previous node in optimal path from source
   dist[source] = 0        # Distance from source to source
   Q = list(range(n)) # All nodes in the graph are unoptimized - thus are in Q
   while Q:           # The main loop
       u = min(Q, key=lambda n:dist[n])                 # vertex in Q with smallest dist[]
       Q.remove(u)
       if dist[u] == infinity:
           break # all remaining vertices are inaccessible from source
       for v in range(n):               # each neighbor v of u
           if Graph[u][v] and (v in Q): # where v has not yet been visited
               alt = dist[u] + Graph[u][v]
               if alt < dist[v]:       # Relax (u,v,a)
                   dist[v] = alt
                   previous[v] = u
   return dist,previous

def display_solution(predecessor): 

   cell = len(predecessor)-1
   while cell:
       print(cell,end='<')
       cell = predecessor[cell]
   print(0)

</lang>

Tcl

Works with: Tcl version 8.6

This script assumes that the contents of the generation task have already been sourced. Note that the algorithm implemented here does not assume that the maze is free of circuits, and in the case that there are multiple routes, it finds the shortest one because it is a breadth-first search (by virtue of the queue variable being used as a queue). <lang tcl>oo::define maze { 

   method solve {} {

### Initialization of visited matrix and location/path queue set visited [lrepeat $x [lrepeat $y 0]] set queue {0 0 {}}

### Loop to do the searching ### while 1 { # Check for running out of path; an error in maze construction if {[llength $queue] == 0} { error "cannot reach finish" } # Visit the next square from the queue set queue [lassign $queue cx cy path] if {[lindex $visited $cx $cy]} continue lset visited $cx $cy 1 lappend path $cx $cy # Check for reaching the goal if {$cx == $x-1 && $cy == $y-1} break # Add the square in each direction to the queue if a move there is legal foreach {dx dy} {0 1 1 0 0 -1 -1 0} { set nx [expr {$cx + $dx}]; set ny [expr {$cy + $dy}] if { $nx >= 0 && $nx < $x && $ny >= 0 && $ny < $y && ($dx && idx($verti, min($cx,$nx), $cy) || $dy && idx($horiz, $cx, min($cy,$ny))) } then { lappend queue $nx $ny $path } } }

### Loop to set up the path rendering ### # (-2,-2) is just a marker that isn't next to the maze at all, so # guaranteeing the use of the last 'else' clause foreach {cx cy} $path {nx ny} [concat [lrange $path 2 end] -2 -2] { if {$nx-$cx == 1} { lset content $cx $cy "v" } elseif {$nx-$cx == -1} { lset content $cx $cy "^" } elseif {$ny-$cy == -1} { lset content $cx $cy "<" } else { lset content $cx $cy ">" } }

### Return the path ### return $path 

   }

}

  1. Do the solution (we ignore the returned path here...)

m solve

  1. Print it out

puts [m view]</lang> Example output: 

+   +---+---+---+---+---+---+---+---+---+---+
| v     |                                   |
+   +---+   +---+---+---+---+---+---+---+   +
| v |       | >   v | >   v |   |           |
+   +   +---+   +   +   +   +   +   +---+   +
| v     | >   ^ | v | ^ | v |   |       |   |
+   +---+   +---+   +   +   +   +---+   +---+
| v | >   ^ | v   < | ^ | v |       |   |   |
+   +   +---+   +---+   +   +   +---+   +   +
| >   ^ | v   < | >   ^ | v |       |       |
+---+---+   +---+   +---+   +---+   +---+---+
| v   <   < | >   ^ | v   < | >   >   >   v |
+   +---+---+   +---+   +---+   +---+---+   +
| >   v |     ^   < | >   >   ^ |       | v |
+---+   +---+---+   +---+---+---+   +   +   +
|     >   >   >   ^ |               |     >  
+---+---+---+---+---+---+---+---+---+---+---+
Automatically Generated: This result set should be accurate to within fifteen minutes of the last viewing.
Awareness

If ZX Spectrum Basic is a language you like, or are interested in, please inform your fellow members of the ZX Spectrum Basic community; this page can't be emptied without your and their participation.

Tasks not implemented in ZX Spectrum Basic

1

2

4

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Draft tasks not implemented in ZX Spectrum Basic

1

3

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Tasks omitted from ZX Spectrum Basic

A

B

C

D

E

F

H

I

M

N

O

P

R

S

T

U

V

W

Y


End of List

Again, feel free to try your hand at any of the tasks listed on this page.


Retrieved from "https://rosettacode.org/wiki/Maze_solving?oldid=167868"