|
to the weblog
back to the front page
maze construction via deep first search in Javawritten 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
|