6
\$\begingroup\$

I'm writing a program to build and solve a Maze using DFS and backtracking using Java Swing. The code was a mess when I have to put my logic into my JPanel in order to show animation via the call to repaint(). Here are all classes:

Point

public class Point {
    public int mX;
    public int mY;

    public Point(int x, int y) {
        mX = x;
        mY = y;
    }
}

Turtle

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.AffineTransform;


public class Turtle {
    private int mXPos;
    private int mYPos;
    private Color mColor;

    public Turtle(Color c) {
        mXPos = 0;
        mYPos = 0;
        mColor = c;
    }

    public void setPosition(int x, int y) {
        mXPos = x;
        mYPos = y;
    }

    public int getXPos() {
        return mXPos;
    }

    public int getYPos() {
        return mYPos;
    }

    public void draw(Graphics g) {
        int width = 15;
        int height = 18;
        int heading = 0;
        int xPos = mXPos;
        int yPos = mYPos;

        // cast to 2d object
        Graphics2D g2 = (Graphics2D) g;
        // save the current transformation
        AffineTransform oldTransform = g2.getTransform();

        // rotate the turtle and translate to xPos and yPos
        g2.rotate(Math.toRadians(heading),xPos,yPos);

        // determine the half width and height of the shell
        int halfWidth = (int) (width/2);        // of shell
        int halfHeight = (int) (height/2);      // of shell
        int quarterWidth = (int) (width/4);     // of shell
        int thirdHeight = (int) (height/3);     // of shell
        int thirdWidth = (int) (width/3);       // of shell

          // draw the body parts (head)
        g2.setColor(mColor);
        g2.fillOval(xPos - quarterWidth, yPos - halfHeight - (int) (height/3), halfWidth, thirdHeight);
        g2.fillOval(xPos - (2 * thirdWidth), yPos - thirdHeight, thirdWidth, thirdHeight);
        g2.fillOval(xPos - (int) (1.6 * thirdWidth), yPos + thirdHeight, thirdWidth, thirdHeight);
        g2.fillOval(xPos + (int) (1.3 * thirdWidth), yPos - thirdHeight, thirdWidth, thirdHeight);
        g2.fillOval(xPos + (int) (0.9 * thirdWidth), yPos + thirdHeight, thirdWidth, thirdHeight);

        // draw the shell
        g2.setColor(mColor);
        g2.fillOval(xPos - halfWidth, yPos - halfHeight, width, height);
        // reset the transformation matrix
        g2.setTransform(oldTransform);
    }

}

MazeBuilder

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Component;
import java.awt.FlowLayout;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.geom.AffineTransform;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;
import java.util.List;
import java.util.ArrayList;
import java.util.Scanner;

import javax.imageio.ImageIO;
import javax.swing.JFrame;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
import javax.swing.JPanel;


public class MazeBuilder extends JPanel {
    /*
     * Maze row
     */
    private static int ROW = 15;

    /*
     * Maze Column
     */
    private static int COLUMN = 15;

    /*
     * Number of vertices
     */
    private static int VERTICES = ROW * COLUMN;

    /*
     * Length of edge
     */
    private static int SPACING = 40;

    /*
     * Spacing from the top left corner (0, 0)
     */
    private static int SHIFTING = 50;

    /*
     * The goal is at the lower right corner
     */
    private int mGoalVertex = VERTICES - 1;

    /*
     * The marked drawing map
     */
    private boolean[][] mMap = new boolean[VERTICES][VERTICES];

    /*
     * Vertex information
     *      if mExplored[u] == true
     *          vertex u is already visited 
     */
    private boolean[] mExplored = new boolean[VERTICES];

    /*
     * Vertex information for solver
     *      if mExplored[u] == true
     *          vertex u is already visited 
     */
    private boolean[] mTurtleExplored = new boolean[VERTICES];

    /*
     * The waiting time for repaint
     */
    private static int BUILD_TIME = 5;

    /*
     * Delay time
     */
    private static int SOLVE_TIME = 500;

    /*
     * Parent frame
     */
    private JFrame mFrame;

    /*
     * Random generator
     */
    private Random mRandom;

    /*
     * Current position of turtle
     */
    private int mCurrentVertex = 0;

    /*
     * Solve mode
     */
    private boolean flag = false;


    /*
     * Flag variable to signify the 
     * maze have been completely built
     */
    private boolean isCompletelyBuilt = false;

    /*
     * The turtle for maze solver
     */
    private Turtle mSolver;

    /**
     * Constructor
     * 
     * @param frame
     *          the parent frame
     */
    public MazeBuilder(JFrame frame) {
        mFrame = frame;     
        // initialize random
        mRandom = new Random();

        mSolver = new Turtle(Color.red);

        initGraph();
        initExplored();
        buildMenu(mFrame);
    }

    /**
     * Delay for an amount of time
     * before redraw the panel
     */
    private void delay(int delayTime) {
        try {
            Thread.sleep(delayTime);
        } 
        catch (InterruptedException e) {
            System.err.println("Error in delay");
        }
    }

    private boolean noMoreVertices() {
        for (int i = 0; i < VERTICES; ++i) {
            if (mTurtleExplored[i] == false)
                return false;
        }
        return true;
    }

    private void solveMazeBacktracking(int u) {
        mCurrentVertex = u;
        if (u == mGoalVertex || noMoreVertices()) {
            flag = false;
            return;
        }

        mTurtleExplored[u] = true;

        // for each neighbor of u make a move
        List<Integer> neighbors = getTurtleNeighbors(u);
        for (int i = 0; i < neighbors.size(); ++i) {
            int v = neighbors.get(i);
            if (mMap[u][v] == true || mMap[v][u] == true) {
                delay(SOLVE_TIME);
                repaint();
                solveMazeBacktracking(v);
            }
        }
    }

    /**
     * Build the menu bar and add
     * it to frame f
     * 
     * @param f
     *          frame to hold menu bar
     */
    public void buildMenu(JFrame f) {
        JMenuBar bar = new JMenuBar();
        JMenu optionMenu = new JMenu("Option");
        JMenuItem item;
        item = new JMenuItem("Solve");
        item.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                flag = true;
                (new Thread() {
                    public void run() {
                        solveMazeBacktracking(0);
                    }
                }).start();
            }
        });
        optionMenu.add(item);

        item = new JMenuItem("Build");
        item.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                // repaint();
                (new Thread() {
                    public void run() {
                        buildMazeDfs(0);
                    }
                }).start();

            }
        });
        optionMenu.add(item);

        item = new JMenuItem("Reset");
        item.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                if (isCompletelyBuilt) {
                    isCompletelyBuilt = false;
                    resetMaze();
                    repaint();
                }
            }
        });
        optionMenu.add(item);

        bar.add(optionMenu);
        f.setJMenuBar(bar);
    }

    /**
     * Check if a square is in a maze
     *
     * @param x
     *          the x coordinate in JPanel
     * @param y
     *          the y coordinate in JPanel
     *
     * @return  
     *          true if it's in maze
     *          false otherwise
     */
    private boolean isInMaze(int x, int y) {
        return (x >= 0 && x < ROW && y >= 0 && y < COLUMN);
    }

    /**
     * Get the number of neighbors of a vertex 
     * 
     * @param u
     *      vertex
     * 
     * @return neighbors
     *      an array list of int    
     */
    private List<Integer> getTurtleNeighbors(int u) {
        List<Integer> neighbors = new ArrayList<Integer>();
        Point p = toPoint(u);
        int to = -1;

        // up
        if (isInMaze(p.mX - 1, p.mY)) {
            to = toVertex(p.mX - 1, p.mY);
            if (!mTurtleExplored[to])
                neighbors.add(to);
        }

        // down 
        if (isInMaze(p.mX + 1, p.mY)) {
            to = toVertex(p.mX + 1, p.mY);
            if (!mTurtleExplored[to])
                neighbors.add(to);
        }

        // left 
        if (isInMaze(p.mX,  p.mY - 1)) {
            to = toVertex(p.mX, p.mY - 1);
            if (!mTurtleExplored[to])
                neighbors.add(to);
        }

        // right 
        if (isInMaze(p.mX, p.mY + 1)) {
            to = toVertex(p.mX, p.mY + 1);
            if (!mTurtleExplored[to])
                neighbors.add(to);
        }

        return neighbors;
    }

    /**
     * Get the number of neighbors of a vertex 
     * 
     * @param u
     *      vertex
     * 
     * @return neighbors
     *      vertex neighbor of u
     */
    private List<Integer> getNeighbors(int u) {
        List<Integer> neighbors = new ArrayList<Integer>();
        Point p = toPoint(u);
        int to = -1;

        // up
        if (isInMaze(p.mX - 1, p.mY)) {
            to = toVertex(p.mX - 1, p.mY);
            if (!mExplored[to])
                neighbors.add(to);
        }

        // down 
        if (isInMaze(p.mX + 1, p.mY)) {
            to = toVertex(p.mX + 1, p.mY);
            if (!mExplored[to])
                neighbors.add(to);
        }

        // left 
        if (isInMaze(p.mX,  p.mY - 1)) {
            to = toVertex(p.mX, p.mY - 1);
            if (!mExplored[to])
                neighbors.add(to);
        }

        // right 
        if (isInMaze(p.mX, p.mY + 1)) {
            to = toVertex(p.mX, p.mY + 1);
            if (!mExplored[to])
                neighbors.add(to);
        }

        return neighbors;
    }

    /**
     * DFS algorithm to remove edges
     *
     * @param u
     *      starting vertex
     *  
     */
    private void buildMazeDfs(int u) {
        // mark that vertex as visited
        mExplored[u] = true;

        // get all neighbors
        List<Integer> neighbors = getNeighbors(u);

        int v = -1;
        // get a random vertex v
        if (neighbors.size() > 0) {
            int idx = mRandom.nextInt(neighbors.size());
            v = neighbors.get(idx);
        }

        if (v == -1) {
            System.out.println("Backtrack");
            repaint();
            isCompletelyBuilt = true;
            return; 
        }

        // remove edge from u to v
        mMap[u][v] = true;
        mMap[v][u] = true;

        // loop through all u's neighbors 
        for (int n = 0; n < neighbors.size(); ++n) {
            // get the next neighbor
            int next = neighbors.get(n);
            // if it's not explored
            if (mExplored[next] == false) {
                // delay(BUILD_TIME);
                // repaint();
                buildMazeDfs(next);
            }
        }       
    }

    /**
     * Initialize vertices
     *      false: unexplored
     *      true: explored
     */
    private void initExplored() {
        for (int i = 0; i < VERTICES; ++i) { 
            mExplored[i] = false;
            mTurtleExplored[i] = false;
        }
    }

    /**
     * Initialize all marked to true:
     *      if mGraph[x][y] = true then 
     *          draw a line from x -> y
     *
     *      neighbor coordinates
     *      -------------------------------------
     *      |           |           |           |
     *      |           | (x-1, y)  |           |           
     *      |           |           |           |
     *      -------------------------------------
     *      |           |           |           |
     *      | (x, y-1)  | (x, y)    | (x, y+1)  |           
     *      |           |           |           |
     *      -------------------------------------
     *      |           |           |           |
     *      |           | (x+1, y)  |           |           
     *      |           |           |           |
     *      -------------------------------------
     *
     */
    private void initGraph() {
        // initialize all marked to false
        int vertices = ROW * COLUMN;
        for (int u = 0; u < vertices; ++u) {
            for (int v = 0; v < vertices; ++v) {
                mMap[u][v] = false;
            }
        }
    }

    /**
     * Convert a coordinate (x, y) to a vertex on graph
     *
     *          -------------
     *          | 0 | 1 | 2 |
     *          -------------
     *          | 3 | 4 | 5 |
     *          -------------
     *          | 6 | 7 | 8 |
     *          -------------
     *
     *          1) formula: 
     *              --------------------------
     *              -  vertex = x * ROW + y  -
     *              --------------------------
     *
     *          2) check:
     *          ROW = 3, COLUMN = 3
     *          then    
     *          [0][0] = 0 * 3 + 0 = 0
     *          [0][1] = 0 * 3 + 1 = 1
     *          [0][2] = 0 * 3 + 2 = 2
     *
     *          [1][0] = 1 * 3 + 0 = 3
     *          [1][1] = 1 * 3 + 1 = 4
     *          [1][2] = 1 * 3 + 2 = 5
     *
     *          [2][0] = 2 * 3 + 0 = 6
     *          [2][1] = 2 * 3 + 1 = 7
     *          [2][2] = 2 * 3 + 2 = 8
     *
     * @param x
     *          x coordinate
     * @param y 
     *          y coordinate
     * 
     * @return 
     *      a vertex
     *
     */
    private int toVertex(int x, int y) {
        return (x * ROW + y);
    }

    /**
     * Convert from a vertex v to a pair (x, y)
     *
     *          1) formula: 
     *              -----------------
     *              -  x = v / ROW  -
     *              -  y = v % ROW  -
     *              -----------------
     *
     *          2) check:
     *              0 and [0][0]
     *                  x = 0 / 3 = 0
     *                  y = 0 % 3 = 0
     *
     *              1 and [0][1]
     *                  x = 0 / 3 = 0
     *                  y = 1 % 3 = 1
     *
     *              6 and [2][0]
     *                  x = 6 / 3 = 2
     *                  y = 0 % 3 = 0
     *
     *              8 and [0][1]
     *                  x = 8 / 3 = 2
     *                  y = 8 % 3 = 2
     *
     *  @param v
     *          vertex
     *
     *  @return
     *          a point 
     */
    private Point toPoint(int v) {
        return new Point(v / ROW, v % COLUMN);
    }

    private void resetMaze() {
        initGraph();
        initExplored();
    }

    @Override
    public void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2D = (Graphics2D) g;      
        g2D.setStroke(new BasicStroke(3f));
        g.setColor(Color.black);

        for (int x = 0; x < ROW; ++x) {
            for (int y = 0; y < COLUMN; ++y) {
                Point p = new Point(x, y);
                drawAPoint(g, p);
            }
        }

        // for each vertex u, we check its 4 neighbors
        int left;
        int right;
        int up;
        int down;

        Point from;
        Point to;

        for (int u = 0; u < VERTICES; ++u) {
            int c = u % COLUMN;
            int r = u / ROW;

            left  = -1;
            right = -1;
            up    = -1;
            down  = -1;

            from = toPoint(u);

            // left
            if (c - 1 >= 0) {
                left = r * ROW + c - 1;
            }

            // right
            if (c + 1 <= COLUMN - 1) {
                right = r * ROW + c + 1;
            }

            // down
            if (r - 1 >= 0) {
                down = (r - 1) * ROW + c;
            }

            // up
            if (r + 1 <= ROW - 1) {
                up = (r + 1) * ROW + c;
            }

            if (left != -1) {
                to = toPoint(left);
                if (mMap[u][left]) 
                    drawRemoveEdge(g, from, to);
            }

            if (right != -1) {
                to = toPoint(right);
                if (mMap[u][right]) 
                    drawRemoveEdge(g, from, to);
            }

            if (up != -1) {
                to = toPoint(up);
                if (mMap[u][up]) 
                    drawRemoveEdge(g, from, to);
            }

            if (down != -1) {
                to = toPoint(down);
                if (mMap[u][down]) 
                    drawRemoveEdge(g, from, to);
            }
            // delay(BUILD_TIME);
        }

        for (int i = 0; i < VERTICES; ++i) {
            if (mExplored[i]) {
                Point p = toPoint(i);
                g.setColor(Color.red);
                g.drawOval(p.mX * SPACING + 17 + SHIFTING, p.mY * SPACING +  17 + SHIFTING, 2, 2);
            }
        }

        if (flag) {
            Point p = toPoint(mCurrentVertex);
            mSolver.setPosition(p.mX * SPACING + 17 + SHIFTING, p.mY * SPACING + 17 + SHIFTING);
            mSolver.draw(g);

            for (int i = 0; i < VERTICES; ++i) {
                if (mTurtleExplored[i]) {
                    Point pp = toPoint(i);
                    g.setColor(Color.green);
                    g.drawOval(pp.mX * SPACING + 17 + SHIFTING, pp.mY * SPACING + 17 + SHIFTING, 2, 2);
                }
            }
        }

        // this is the only way out
        Color c = Color.decode("#EEEEEE");
        g.setColor(c);
        Point p = new Point((ROW - 1)* SPACING + SHIFTING, (COLUMN - 1) * SPACING + SHIFTING); 
        g.drawLine(p.mX + SPACING, p.mY, p.mX + SPACING, p.mY + SPACING);
    }

    /**
     * Remove an edge from to point
     * 
     * @param g
     *          graphics component
     * 
     * @param cur
     *          the current vertex
     * 
     * @param adj
     *          its neighbor
     */
    private void drawRemoveEdge(Graphics g, Point cur, Point adj) {
        Color c = Color.decode("#EEEEEE");
        g.setColor(c);
        Point p = new Point(cur.mX * SPACING + SHIFTING, cur.mY * SPACING + SHIFTING); 
        // right
        if (cur.mX + 1 == adj.mX && cur.mY == adj.mY) {
            g.drawLine(p.mX + SPACING, p.mY, p.mX + SPACING, p.mY + SPACING);
        }
        // left
        else if (cur.mX - 1 == adj.mX && cur.mY == adj.mY) {
            g.drawLine(p.mX, p.mY, p.mX, p.mY + SPACING);
        }
        // top
        else if (cur.mX == adj.mX && cur.mY - 1 == adj.mY) {
            g.drawLine(p.mX, p.mY, p.mX + SPACING, p.mY);
        }
        else if (cur.mX == adj.mX && cur.mY + 1 == adj.mY){
            g.drawLine(p.mX, p.mY + SPACING, p.mX + SPACING, p.mY + SPACING);
        }
    }

    /**
     * Draw a box around one point
     * 
     * @param g
     *          graphics component
     * 
     * @param p
     *          the point to be drawn
     */
    private void drawAPoint(Graphics g, Point p) {
        // add spacing
        p.mX = p.mX * SPACING + SHIFTING;
        p.mY = p.mY * SPACING + SHIFTING;

        // draw top
        g.drawLine(p.mX, p.mY, p.mX + SPACING, p.mY);
        // draw left
        g.drawLine(p.mX, p.mY, p.mX, p.mY + SPACING);
        // draw right
        g.drawLine(p.mX + SPACING, p.mY, p.mX + SPACING, p.mY + SPACING);
        // draw bottom
        g.drawLine(p.mX, p.mY + SPACING, p.mX + SPACING, p.mY + SPACING);
    }

    /**
     * Build entire UI
     */
    public static void buildGUI() {
        // create a container level JFrame
        JFrame frame = new JFrame("Maze Generator");

        // set up frame
        frame.setSize(800, 800);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setVisible(true);

        // create a panel
        MazeBuilder app = new MazeBuilder(frame);
        app.buildMenu(frame);
        frame.setContentPane(app);

    }
}

Program

import javax.swing.SwingUtilities;

public class Program {
    public static void main(String args[]) {
        // run on event-dispatching thread
        SwingUtilities.invokeLater(new Runnable() {
            @Override
            public void run() {
                MazeBuilder.buildGUI();
            }
        });
    }
}

I knew it was very bad when putting the logic of maze into the UI class, but I couldn't find a way to extract them out. Please help criticizing my code. Thanks.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Why did you create your own Point class? Java already has one which looks identical to yours, except with some additional functionality. I would also either use or extend from it in the Turtle class. \$\endgroup\$
    – seand
    Commented May 2, 2012 at 16:44
  • \$\begingroup\$ I'm newbie to Swing and Java, so I was not aware of that class. Thanks a lot. \$\endgroup\$
    – roxrook
    Commented May 3, 2012 at 1:08

1 Answer 1

5
\$\begingroup\$

Here's a few tips:

  • When I ran you program at first, I got a blank frame. Make sure frame.setVisible(true) is the last thing you do. Everything else should be set up before that.
  • Really, really, really avoid magic numbers. Code like this:

    public void draw(Graphics g) {
        int width = 15;
        int height = 18;
        // etc.
    }
    

    Is really hard to maintain. You have a few constants. Just add more.

  • Swing uses swing Timer and SwingWorker rather than threads. For example,

    private class MazeSolvingWorker extends SwingWorker<Void, Boolean[][]> {
    
        // Stores its own copy of the map
        private Boolean[][] map_;
    
        // Needs to get map from main program
        public MazeSolvingWorker(Boolean[][] map) {
            map_ = map;
        }
    
        // This function replaces the run method
        @Override
        protected Void doInBackground() throws Exception {
            solveMazeBacktracking(0);
            return null;
        }
    
        // Need to override when you use publish
        @Override
        protected void process(List<Boolean[][]> chunks) {
            mMap = chunks.get(chunks.size() - 1);
            repaint();
        }
    
        private void solveMazeBacktracking(int u) {
            mCurrentVertex = u;
            if (u == mGoalVertex || noMoreVertices()) {
                flag = false;
                return;
            }
    
            mTurtleExplored[u] = true;
    
            // for each neighbor of u make a move
            List<Integer> neighbors = getTurtleNeighbors(u);
            for (int i = 0; i < neighbors.size(); ++i) {
                int v = neighbors.get(i);
                if (map_[u][v] == true || map_[v][u] == true) {
                    delay(SOLVE_TIME);
                    // Thread-safe alternative to calling repaint directly
                    publish(map_);
                    solveMazeBacktracking(v);
                }
            }
        }
    
    }
    

    Now you can replace this:

    item.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            flag = true;
            (new Thread() {
                public void run() {
                    solveMazeBacktracking(0);
                }
            }).start();
        }
    });
    

    with this:

    item.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            flag = true;
            new MazeSolvingWorker(mMap).execute();
        }
    });
    

    Replacing buildMazeDfs(int) is up to you.

  • Normally, I would recommend using the entity-system framework to separate logic from data and ui, but you have a very simple program. Factor out a Maze class.

  • This is just nit-picky, but you don't need a static method in MazeBuilder to build the gui. You can move that to Program, where it makes more sense. Or you could get rid of the Program class and put main in MazeBuilder. Just a style preference though. :)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.