Maze, optimal path finding using stacks

Question

i have a program that generates a random maze. In the maze a red dot is displayed and the red dot flashes on by each block in the maze. all the blocks in the maze are == 1 and if the red dot goes through that block, it increments ++. the red dot goes in the direction towards the lowest number, that way it wont stay in an infinite loop by a dead end. once it reaches the end, ive solved the maze. This is where im stumped, im trying to print the red dot to find the optimal route all the way back to the beginning where it started. I used a stack class that i made to record all the y and x components of where the red dot traveled. im able to traceback every where the red dot has gone but that isnt the optimal solution.

My question is how could i print the red dot tracing back in only the optimal path. My idea of solving this would be to check and see if the coordinates of a stack where visited before, if so..find the last case where it was visited and print the red dot up until that point. that way itll never deal with the dead ends it traveled. the method solve() is what contains the traceback and solving technique for the red dot to travel through the maze and back.

Im not the greatest programmer and im still learning how to use stacks, ive been stumped for hours and dont know how to approach this. Please be kind and explain how you would do it using the stack i made. Thank you

import java.awt.*;
import java.awt.event.*;
import java.awt.Graphics;
import javax.swing.*;

public class mazedfs extends JFrame implements KeyListener
{
/* default values: */
private static int bh = 16;     // height of a graphical block
private static int bw = 16;    // width of a graphical block
private int mh = 41;    // height and width of maze
private int mw = 51;
private int ah, aw;    // height and width of graphical maze
private int yoff = 40;    // init y-cord of maze
private Graphics g;
private int dtime = 40;   // 40 ms delay time
byte[][] M;    // the array for the maze
public static final int SOUTH = 0;
public static final int EAST = 1;
public static final int NORTH = 2;
public static final int WEST = 3;

public static boolean showvalue = true; // affects drawblock

// args determine block size, maze height, and maze width
public mazedfs(int bh0, int mh0, int mw0)
 { 
   bh = bw = bh0;  mh = mh0;  mw = mw0;
   ah = bh*mh;
   aw = bw*mw;
   M = new byte[mh][mw];  // initialize maze (all  0's - walls).
   this.setBounds(0,0,aw+10,10+ah+yoff);    
   this.setVisible(true);
   this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
   try{Thread.sleep(500);} catch(Exception e) {} // Synch with system
   this.addKeyListener(this);  
   g = getGraphics();    //g.setColor(Color.red);
   setup();
 }

public void paint(Graphics g) {} // override automatic repaint

public void setup()
   { 
     g.setColor(Color.green);
     g.fill3DRect(0,yoff,aw,ah,true);  // fill raised rectangle
     g.setColor(Color.black);
     //     showStatus("Generating maze...");
     digout(mh-2,mw-2); // start digging!
     // digout exit
     M[mh-1][mw-2] = M[mh-2][mw-1] = 1;
     drawblock(mh-2,mw-1);
     solve();  // this is the function you will write for parts 1 and 2
     play();   // for part 3
   }   

    public static void main(String[] args)
    {
       int blocksize = bh, mheight = 41, mwidth = 41; // need to be odd
       if (args.length==3)
       {
           mheight=Integer.parseInt(args[0]);
           mwidth=Integer.parseInt(args[1]);
           blocksize=Integer.parseInt(args[2]);
       }
       mazedfs W = new mazedfs(blocksize,mheight,mwidth);
    }

public void drawblock(int y, int x)
    {
    g.setColor(Color.black);
    g.fillRect(x*bw,yoff+(y*bh),bw,bh);
    g.setColor(Color.yellow);
    // following line displays value of M[y][x] in the graphical maze:
    if (showvalue)
      g.drawString(""+M[y][x],(x*bw)+(bw/2-4),yoff+(y*bh)+(bh/2+6));
    }

    void drawdot(int y, int x)
    {
    g.setColor(Color.red);
    g.fillOval(x*bw,yoff+(y*bh),bw,bh);               
        try{Thread.sleep(dtime);} catch(Exception e) {} 
    }

    /////////////////////////////////////////////////////////////////////

/* function to generate random maze */
public void digout(int y, int x)
 {
     M[y][x] = 1;  // digout maze at coordinate y,x
     drawblock(y,x);  // change graphical display to reflect space dug out


     int dir = (int)(Math.random()*4);

     for (int i=0;i<4;i++){
     int [] DX = {0,0,2,-2};
     int [] DY = {-2,2,0,0};
     int newx = x + DX[dir];
     int newy = y + DY[dir];
     if(newx>=0 && newx=0 && newy0 && min>M[y-1][x] && M[y-1][x]!=0){
           min = M[y-1][x];
          DX = 0;
          DY = -1;
          }//ifNORTH
          if (y+1>0 && min>M[y+1][x] && M[y+1][x]!=0){
           min = M[y+1][x];
          DY = 1;
          DX = 0;
          }//ifSOUTH
          if (x-1>0 && min>M[y][x-1] && M[y][x-1]!=0){
          min = M[y][x-1];
          DX = -1;
          DY = 0;
          }//ifWEST
           if (x+1>0 && min>M[y][x+1] && M[y][x+1]!=0){
          min = M[y][x+1];
          DX = 1;
          DY = 0;
          }//ifEAST
           M[y][x]++;
           drawblock(y,x); 
           x = x+DX;
           y = y+DY;
           drawdot(y,x); 
           yourstack = new Stack(y,x,yourstack); // creates new stack for each coordinate travelled
          }//while

      while(yourstack != null){
            yourstack = yourstack.tail;
            drawdot(yourstack.y,yourstack.x); // this will traceback every box ive been through
      }//while
  } // solve

class Stack{
    int x;
    int y;
    Stack tail;
    public Stack(int a, int b, Stack t){
        y = a;
        x=b;
        tail=t;
    }

}//stackclass



    ///////////////////////////////////////////////////////////////
    /// For part three (save a copy of part 2 version first!), you
    // need to implement the KeyListener interface.

    public void play() // for part 3
    {
    // code to setup game
    }
    // for part 3 you may also define some other instance vars outside of
    // the play function.

   // for KeyListener interface
   public void keyReleased(KeyEvent e) {}
   public void keyTyped(KeyEvent e) {}
   public void keyPressed(KeyEvent e) // change this one
    {
    int key = e.getKeyCode();       // code for key pressed      
    System.out.println("YOU JUST PRESSED KEY "+key);
    }

} // mazedfs


////////////
// define additional classes (stack) you may need here.

Maze, optimal path finding using stacks

Answers (1)

Related Questions