to the weblog
back to the front page

maze construction via deep first search in Java

written in July, 2003

Java is certainly not the language of my choice. Well, but if you align the code a little bit uncommonly it might at least look kind of funny...



                     import                                                    java 
                     .util.                                                  Random 
                     ;import                                              java.util 
       	       	     .Set;import       	       	       	       	       	 java.util.
		     HashSet;public    	       	       	       	       class//grmpf
                     StudentMazeGenerator implements MazeGenerator { private Random 
                     random = new Random();private Set visited;protected Maze maze;
                     protected MazeGeneratorListener lis; public Maze generateMaze(
                     int                                               wiiidth, int     
                     he,                                      MazeGeneratorListener
                     lis                                    ) { maze = MazeFactory.
                                                    createMaze( wiiidth, he );(this 
                                                .lis = lis) .startingMazeGeneration
                                         ( maze ); visited = new HashSet();    	   
                                      initP(); generateMaze(0,0);return  	   
                              maze;} private int[][] perms; public     		   
                           void generateMaze( int x, int       	  
                     y){visited.add(new NNode(x,y));   	      	  
                        lis.mazeModified(maze);	       	      	  
                            int actual=random 	       	      	  
                                    .nextInt(24);      	      	  
                                        // showPerm (  	       	  
                                                // actual ) ; 	  
                                                    for( int i=0; 
                     i<4                                   ;i++){//System
                     //.                                         out. println 
                     //(                                                 "dir: "+i+ 
                     // " perm: " + perms[actual][i] ); // intentionally left blank
                     switch ( perms [ actual ] [ i] ) { case 0: if ( y != 0 && ! //
                     maze.canMoveNorthFrom( x, y ) && ! visited.contains( new NNode
                     ( x, y-1 ))){ maze.removeWallNorthOf(x,y);generateMaze(x,y-1);
                     }break;case 1: if (x!=maze.getWidth()-1&&!maze.canMoveEastFrom
                     ( x,y ) && ! visited.contains( new NNode( x + 1, y ))) { maze. 
                     removeWallEastOf ( x, y ); generateMaze( x + 1, y ); } break ; 
                     case                                                       2 : 
                     if(                                                        y!= 
                                                                                    
                             maze .   	      	     	     
                          getHeight() 	      	     	     
                         -1 && ! maze .	      	     	     
                       canMoveSouthFrom(x       ,y)&&! 	     
                      visited.contains(new     NNode(x,y     
                      +1))){     maze.removeWallSouthOf(x,       
                     y-1+1           -1+1);   generateMaze     
                     ( x,              y +1           ); }   
                     break             ;case           3 :   
                      if(              x!=             0&&   
                      1!=             0&&0            <1&&   
                       1!=           0&&!            maze    
                        .canMoveWestFrom           (x, y)    
                       &&! visited.contains( new NNode(x     
                      -1, y ))) { maze.removeWallWestOf(     
                     x,y);generateMaze(x-1,y);} break; 	     
                     }} } private int[][] permutation  	     
                     ( int[] input ) { int[][] result	     
                     = new     	       	       	      	     
                     int[   	      	   	     
                     1 	    	       	   	     
                       	    	      	       	       	      
                     ]                           [ ( input    
                     ).	                         length ]; 
                     result                      [0]=input
                     ;for(int                       left =  
                     0; left <                       input  
                     .length-1;left                    ++) 
                     {int anz=(result                  ) .  
                     length +1-1; for(                 int  
                     right =left+1; right              <1+
                     1-2   +input.length;right         ++)
                     {for     (int line=0; line        <0+ 
                     anz          ; line++ ){ int[]   nxt=  
                     new            int[input.length];for(
                     int               h=0; h <nxt.length;
                     h++                 ) nxt[h]= result[  
                     line                    ][h];nxt[left  
                     ] =                     result [ line  
                     ] [                        right];nxt
                     [right]                       =result
                     [ line ][                        left
                     ];result= 	       	       	       	  
                               	      	  	     
                                 append(result 	     
                              ,nxt ); }} } return    
                            result; } private int[   
                          ][] append( int[][] r, int[ 
                        ] a ){ int[][] res = new int[r 
                       .length+       1][      ];for(int
                      i=0;i<          res         .length 
                      - 1;            i++            )res 
                      [i]             =r[             i ];
                     res[             res              .//   
                     length           -1]              =a;
                     return           res              ; } 
                     void            initP            () {
                      int             [ ]            perm 
                      =               new           int[  
                       4];            perm    [0]=0;perm  
                        [1]           =1;perm[2]=2;perm[  
                        3]=3;         perms=permutation(  
                          perm        );}private void  	 
                                      showPerm( int  
                                      permno){ 	     
                                              	     
                     System.out            .print(
                     "perm no "           + permno+  
                     ": ");for           (int y=0; y< 
                      perms            [permno].length; 
                      y++ )           System.out. print(
                      perms          [permno][y]     +" " 
                      ) ;            System .         out 
                      .             println()          ;}}
                     class          NNode{int          x ;
                     int           y; public          NNode
                     (int          x,int y){          this 
                     .x=          x; this.y           = y  
                      ;}          public int         getX    
                      (){        return x;}        public  
                      int        getY () {        return   
                       y;} public boolean        equals (   
                        Object o) {if(o==        null||!(o  
                        instanceof NNode         )) return
                           false;NNode 	       	       	  
                              node=(   			
                       NNode)  
                      o;return 
                      node.getX
                     ()==getX( 
                     ) && getY 	
                      ()==node 	
                        .getY 
		       	      
                       ();}    
                      public        
                      int //.       
                     hashCode( 
                     ){ return 
                      x+1000* 
                        y;}} 

This program can really be compiled and it actually solves the problem (see below).


download



Max-Gerd Retzlaff <m.retzlaff@gmx.net>, <mgr@bl0rg.net>, or <mgr@vantronix.net>
GnuPG- / OpenPGP-Information:
   Type bits/keyID    Date       User ID
   pub  1024/81239F12 2002/03/12 Max-Gerd Retzlaff <mgr@hannover.ccc.de>
             Key fingerprint =  49 CD 21 F2 41 AC 72 C5  D0 D1 27 DC C2 B2 48 AE  81 23 9F 12 
   uid                           Max-Gerd Retzlaff <m.retzlaff@gmx.net>
   sub  4096g/63E36E39 2002-03-12
   local copy of the key

First version on July, 17th 2003. Last modified: Sun Jun 13 05:23:45 CEST 2004