# solve a maze recursively

Page 1 of 1

## 3 Replies - 7825 Views - Last Post: 27 February 2012 - 07:17 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=268482&amp;s=8c27ccd652c35bb2cf1a687908fe0fbe&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 CrossChatter

Reputation: 0
• Posts: 2
• Joined: 27-February 12

# solve a maze recursively

Posted 27 February 2012 - 07:01 AM

Hello, this assignment is outside my scope of understanding, and my professor is subpar in his ability to teach, if someone could just point me in the right direction to start that would be awesome. This is the source code we were given. I understand the concepts just not the implementation. The explanation to the assignment can be found http://knight.temple...gnment_05.html.
*Side note Lakaemper is not my professor if he was I doubt I would be having these problems.
```
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package maze;

import java.awt.Point;

public class Main implements MazeListener {

Maze maze;

public Main() {
// a 30 rows x 50 columns maze
maze = new Maze(30, 50);

// register object of class Main to the maze

// an example how to call "showPath"'
// the list I generate here is not a valid path, but just some
// arbitrary values
// this will generate some red boxes in your display.
for (int i = 10; i < 20; i++) {
}
maze.showPath(ll.iterator());

}

public void MazeClicked(int row, int col) {
System.out.print("You clicked " + row + " " + col+". ");
System.out.println("The data at this position is: " + maze.getMazeData(row, col));
}

public static void main(String[] args) {
new Main();
}
}

package maze;

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.Iterator;

public class Maze extends JFrame implements ActionListener{
private final int   DEFAULTCHAMBERSIZE=8;

//
private byte [][]   theMaze;    // the maze, containing chambers
private JPanel      mazePanel;
private Container   cp;
private long        count;
private MazeListener mazeListener;

// -------------------------------------------------------------------------
// inner class MyPanel
// -------------------------------------------------------------------------
private class MyPanel extends JPanel implements MouseListener{
int chamberSize;

public MyPanel(){
// where to go now ?
int noRows=theMaze.length;
int noColumns=theMaze[0].length;

chamberSize = DEFAULTCHAMBERSIZE;
if (Math.max(noRows,noColumns)<100)
chamberSize=DEFAULTCHAMBERSIZE*2;
else if (Math.max(noRows,noColumns)>200)
chamberSize = DEFAULTCHAMBERSIZE/2;

setPreferredSize(new Dimension(noColumns * chamberSize, noRows * chamberSize));
}

public void paint(Graphics g){
int noRows=theMaze.length;
int noColumns=theMaze[0].length;
for (int r=0;r<noRows;r++){
for (int c=0; c<noColumns; c++){
int w=theMaze[r][c];
int posX=c*chamberSize;
int posY=r*chamberSize;
if ((w & 0x20) != 0)
g.setColor(Color.green);          // the exit
else if((w & 0x10) != 0)
g.setColor(Color.red);            // path
else
g.setColor(Color.orange);         // default background

g.fillRect(posX,posY,chamberSize,chamberSize);

// the walls
g.setColor(Color.black);
int cs = chamberSize -1;
if ((w & 1)==1)
g.drawLine(posX,posY,posX+cs,posY);
if ((w & 2)==2)
g.drawLine(posX,posY,posX,posY+cs);
if ((w & 4)==4)
g.drawLine(posX,posY+cs,posX+cs,posY+cs);
if ((w & 8)==8)
g.drawLine(posX+cs,posY,posX+cs,posY+cs);
}
}
}

public void mouseClicked(MouseEvent e) {
}

public void mouseEntered(MouseEvent e) {
}

public void mouseExited(MouseEvent e) {
}

public void mousePressed(MouseEvent e) {
// clear old path entries
int noRows=theMaze.length;
int noColumns=theMaze[0].length;
for (int r=0;r<noRows;r++){
for (int c=0; c<noColumns; c++){
theMaze[r][c] = (byte)(theMaze[r][c] & 0x2f);
}
}

// get mouse position
int x=e.getX();
int y=e.getY();
int col=(int)Math.floor(x/chamberSize);
int row=(int)Math.floor(y/chamberSize);

// if a listener is registered: call MazeClicked
if (mazeListener != null){
mazeListener.MazeClicked(row,col);
}
else
System.out.println("As long as nothing is registered, a click won't do too much...");
}

public void mouseReleased(MouseEvent e) {
}

}
// -------------------------------------------------------------------------

// -------------------------
// Constructor
// -------------------------
public Maze(int r, int c) {
super("The Maze");
setDefaultCloseOperation(EXIT_ON_CLOSE);
cp=getContentPane();
cp.setLayout(new BorderLayout());
JButton b1=new JButton("New Maze");
b1.setBackground(Color.CYAN);

generate(r,c);  // generate maze, draw it on panel, pack

setVisible(true);
}

// -----------------------------------------
// add listener, typically a path generator
// -----------------------------------------
mazeListener = ml;
}

public void showPath(Iterator i){
while(i.hasNext()){
Point p=(Point)i.next();
int row=(int)p.getX();
int col=(int)p.getY();
theMaze[row][col] |= (byte)0x10;
repaint();
}
}

public byte getMazeData(int r,int c){
return(theMaze[r][c]);
}

// -------------------------
// Maze Generation Entry
// -------------------------
public boolean generate(int rows, int columns){
// initialize: all walls up, path=false => 0x0f
theMaze = new byte[rows][columns];
for (int r=0;r<rows;r++){
for (int c=0;c<columns;c++){
theMaze[r][c]=0x0f;
}
}

// pick a start point
int startR=(int)Math.floor(Math.random()*rows);
int startC=(int)Math.floor(Math.random()*rows);
count = 0;

// and generate
boolean done = false;
try{
generateRec(startR,startC,0);
// set exit point to 0,0
theMaze[0][0] |= 0x20;      // 0x20: exit
mazePanel = new MyPanel();      // create and add new panel
done = true;
}
catch(Exception er){
mazePanel = new JPanel();
mazePanel.setPreferredSize(new Dimension(500,300));
mazePanel.add(new Label("Sorry, size is too big: Stack Overflow"));
done = false;
}
finally{
if (mazePanel != null){
cp.remove(mazePanel);
}
pack();
repaint();
}
return false;
}

// -------------------------
// Recursive Maze Generation
// -------------------------
private void generateRec(int r, int c, int direction){
// tear down wall towards source direction
switch(direction){
case 1: theMaze[r][c] -= 4;break;
case 2: theMaze[r][c] -= 8;break;
case 4: theMaze[r][c] -= 1;break;
case 8: theMaze[r][c] -= 2;break;
}
count++;        // another chamber processed.

// where to go now ?
int noRows=theMaze.length;
int noColumns=theMaze[0].length;

// base case 1: all chambers finished
if (count == noRows*noColumns){
return;
}

// recursive case: while there are walkable directions: walk
while (true){
// find walkable directions
boolean dir1,dir2,dir4,dir8;
dir1=dir2=dir4=dir8=false;
if (r>0 && (theMaze[r-1][c]==0x0f)) dir1=true;
if (c>0 && (theMaze[r][c-1]==0x0f)) dir2=true;
if (r<noRows-1 && (theMaze[r+1][c]==0x0f)) dir4=true;
if (c<noColumns-1 && (theMaze[r][c+1]==0x0f)) dir8=true;

// base case 2: no walkable directions left
if ((dir1 | dir2 | dir4 | dir8) == false)
break;

boolean picked=false;
do{
int d=(int)Math.floor(Math.random()*4); // direction 0-3
switch(d){
case 0: if (dir1){
picked=true;
theMaze[r][c] -= 1;
generateRec(r-1,c,1);
dir1=false;
break;
}
case 1: if (dir2){
picked=true;
theMaze[r][c] -= 2;
generateRec(r,c-1,2);
dir2=false;
break;
}
case 2:if (dir4){
picked=true;
theMaze[r][c] -= 4;
generateRec(r+1,c,4);
dir4=false;
break;
}
case 3:if (dir8){
picked=true;
theMaze[r][c] -= 8;
generateRec(r,c+1,8);
dir8=false;
break;
}
}
}while(!picked);
}
// base case2n cont'd: no more walkable directions left
return;
}

// ---------------------------
// toString: returns maze data
// ---------------------------
public String toString(){
int noRows=theMaze.length;
int noColumns=theMaze[0].length;

String s="";
for (int r=0;r<noRows;r++){
for (int c=0;c<noColumns;c++){
s=s + theMaze[r][c] + " ";
}
s=s+"\n";
}
return(s);
}

// ---------------------------------
// Action Performed
// --------------------------------
public void actionPerformed(ActionEvent e) {
int noRows=theMaze.length;
int noColumns=theMaze[0].length;
generate(noRows,noColumns);
}
}

package maze;

public interface MazeListener {
public void MazeClicked(int row, int col);
}

```

Is This A Good Question/Topic? 0

## Replies To: solve a maze recursively

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12147
• Posts: 45,157
• Joined: 27-December 08

## Re: solve a maze recursively

Posted 27 February 2012 - 07:10 AM

Are you familiar with Backtracking as an approach to solving a maze? That's a good place to start.

### #3 CrossChatter

Reputation: 0
• Posts: 2
• Joined: 27-February 12

## Re: solve a maze recursively

Posted 27 February 2012 - 07:16 AM

macosxnerd101, on 27 February 2012 - 07:10 AM, said:

Are you familiar with Backtracking as an approach to solving a maze? That's a good place to start.

I am not, but I will take a look at the tutorial link, thanks man.

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12147
• Posts: 45,157
• Joined: 27-December 08

## Re: solve a maze recursively

Posted 27 February 2012 - 07:17 AM