Java
Maze

This maze was the final assignment in the object oriented based java programming class I took this fall called Fundamentals of Computer Science 2.

Instructions

  • Construct random mazes using Kruskal’s algorithm and Union/Find
  • Display the maze graphically and animate the search
  • Allow the user to choose one of two algorithms for finding the path: Breadth-First Search or Depth-First Search
  • Provide an option for designing a new random maze
  • Allow the user to traverse the maze manually - using the keys to select the next move, preventing illegal moves and notifying the user of completion of the game
  • Display the solution path connecting the start and end, once it’s found (either automatically or by the user)

Bells & Whistles

Whistles:

  • Provide an option to toggle the viewing of the visited paths
  • Allow the user the ability to start a new maze without restarting the program
  • Keep the score of wrong moves

Bells:

  • In addition to animating the solution of the maze, also animate the construction of the maze: on each tick, show a single wall being knocked down
  • (Tricky) Construct mazes with a bias in a particular direction — a preference for horizontal or vertical corridors
  • (Tricky) Construct two intertwined mazes, and allow two players to race from their starting points to their ending points

Depth First & Breadth First Search

Depth-first search (DFS) is an algorithm for traversing or searching graph data structures. It starts at the root and explores as far as possible along each branch before backtracking.

Breadth-first search (BFS) is an algorithm for traversing or searching graph data structures. It starts at theroot and explores the neighbor nodes first, before the next level neighbors.

// for each edge, if search is depth first add cell to the beginning of the list (a stack)
// otherwise search is breadth first and cell is added to the end of the list (a queue)	
 for (Edge e : current.edges) {
    if (dfs) {
      if (e.to.equals(current)) {
        worklist.addAtHead(e.from);
      }
      else {
       worklist.addAtHead(e.to);
      }
    }
    else {
      if (e.to.equals(current)) {
        worklist.addAtTail(e.from);
      }
      else {
        worklist.addAtTail(e.to);
      }
    }

Player Modes

Single player mode allows the user to navigate the maze using the arrow keys.

2 player mode allows 2 users to navigate the maze, racing to opposite corners.

  // Determines how to move the character in the maze given depending Key Presses
  // EFFECT: moves the player, changes which cell it occupies
  void movePlayer(String key) {
    boolean canMoveUp = false;
    boolean canMoveDown = false;
    boolean canMoveRight = false;
    boolean canMoveLeft = false;

    if (this.player.equals(this.end)) {
      this.complete = true;
    }

Checks each edge coming out of the cell the player is currently in and determines which way the player should be able to move

    for (Edge e : this.player.edges) {
      Cell other;
      if (e.to.equals(this.player)) {
        other = e.from;
      }
      else {
        other = e.to;
      }
      if (other.id == this.player.id - WIDTH) {
        canMoveUp = true;
      }
      else if (other.id == this.player.id + WIDTH) {
        canMoveDown = true;
      }
      else if (other.id == this.player.id + 1) {
        canMoveRight = true;
      }
      else if (other.id == this.player.id - 1) {
        canMoveLeft = true;
      }
    }
    visited.add(player);

    if (!path.contains(player)) {
      score = score + 1;
    }

Reassign the player to the cell in the direction the user moves

    if (key.equals("up") && canMoveUp) {
      this.player = this.idMap.get(this.player.id - WIDTH);
    }
    if (key.equals("down") && canMoveDown) {
      this.player = this.idMap.get(this.player.id + WIDTH);
    }
    if (key.equals("right") && canMoveRight) {
      this.player = this.idMap.get(this.player.id + 1);
    }
    if (key.equals("left") && canMoveLeft) {
      this.player = this.idMap.get(this.player.id - 1);
    }
  }

Maze Bias

Adding a horitzontal bias creates a maze more likely to have rows than columns.

Adding a vertical bias creates a maze more likely to have columns than rows.

Assign a positive or negative bias based on a boolean flag

  // initializes edges
  // EFFECT: edges contains all edges in the maze
  void initEdges() {
    int bias = 0;
    if (horizontalBias) {
      bias = 70;
    }
    else if (verticalBias) {
      bias = -70;
    }

Cells are initialized with a weight on each edge, which is then used to determine which edges are kept in order to create one path through the maze. Typically the edge weight is random, but in the case of a bias the weight is artifically increased or lowered.

    // look at each cell in the list of all cells in the world
    for (Cell c : cells) {
      int randomWeight;

      // if this cell is in the bottom row, but its not the rightmost corner
      if (c.y == HEIGHT - 1 && c.x != WIDTH - 1) {
        // give it only right pointing edges
        randomWeight = rand.nextInt(100) + 0;
        Edge edgeRight = new Edge(c, this.idMap.get(c.id + 1), randomWeight);
        edges.add(edgeRight);
      }

      // if this cell is in the right column, but not at the bottom
      if (c.x == WIDTH - 1 && c.y != HEIGHT - 1) {
        // give it only down pointing edges
        randomWeight = rand.nextInt(100) + 0;
        Edge edgeDown = new Edge(c, this.idMap.get(c.id + WIDTH), randomWeight);
        edges.add(edgeDown);
      }

      // if this cell is not the rightmost bottom-most corner
      if (c.x != WIDTH - 1 && c.y != HEIGHT - 1) {
        // give it right pointing edges and down pointing edges
        randomWeight = rand.nextInt(100) + bias;
        Edge edgeD = new Edge(c, this.idMap.get(c.id + WIDTH), randomWeight);
        // make a new random weight for this edge
        randomWeight = rand.nextInt(100);
        Edge edgeR = new Edge(c, this.idMap.get(c.id + 1), randomWeight);
        edges.add(edgeD);
        edges.add(edgeR);
      }
    }
  }

Code

/* +---------------------------------------------------------------+
 * +---------------------------------------------------------------+
 * | HOW TO PLAY:                                                  |
 * | maze is drawn on launch                                       |
 * | press h or v to drawn a maze with horizontal or vertical bias |
 * | press enter to go to player mode                              |
 * | press b to see breadth first search                           |
 * | press d to see depth first search                             |
 * | press 2 to play 2 player - a new maze is drawn and each       |
 * | player races to the opposite diagonal corner (p2 use ijkl)    |
 * | press f to display the path the player has traversed          |
 * +---------------------------------------------------------------+
 * +---------------------------------------------------------------+
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import tester.*;
import javalib.impworld.*;
import java.awt.Color;
import javalib.worldimages.*;
import java.util.HashMap;
import java.util.Random;

Represents each indvidual cell, which is comprised of its x and y position, as well as its ID number, the list of edges attached to it, and the cell that is its "leader" in the union span tree. Contains methods to find the leader of the entire span, as well as render methods for different types of cells.

//a class to represent Cells
class Cell {
  int x;
  int y;
  int id;
  ArrayList< Edge > edges;
  Cell leader;

  Cell(int x, int y, int id, ArrayList e) {
    this.x = x;
    this.y = y;
    this.id = id;
    this.edges = e;
    this.leader = this;
  }

  // find the top most leader (representative) of this cell
  Cell findLeader() {
    if (this.leader.id == this.id) {
      return this;
    }
    else {
      return this.leader.findLeader();
    }
  }

  // draw the center dot of the cells
  void render(WorldScene bg) {
    bg.placeImageXY(
        new RectangleImage(MazeWorld.CELLSIZE, MazeWorld.CELLSIZE,
         "outline", Color.black),
        this.x * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2,
        this.y * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2);

  }

  void renderExplore(WorldScene bg) {
    bg.placeImageXY(
        new RectangleImage(MazeWorld.CELLSIZE - 2,
         MazeWorld.CELLSIZE - 2, "solid",
            new Color(181, 119, 243)),
        this.x * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2,
        this.y * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2);
  }

  void renderEnd(WorldScene bg) {
    bg.placeImageXY(
        new RectangleImage(MazeWorld.CELLSIZE - 1, 
        MazeWorld.CELLSIZE - 1, "solid", Color.green),
        this.x * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2,
        this.y * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2);
  }

  void renderStart(WorldScene bg) {
    bg.placeImageXY(
        new RectangleImage(MazeWorld.CELLSIZE - 1, 
        MazeWorld.CELLSIZE - 1, "solid", Color.red),
        this.x * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2,
        this.y * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2);
  }

  void renderPath(WorldScene bg) {
    bg.placeImageXY(
        new RectangleImage(MazeWorld.CELLSIZE - 1, MazeWorld.CELLSIZE - 1, "solid",
            new Color(24, 59, 129)),
        this.x * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2,
        this.y * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2);
  }

  void renderPlayer(WorldScene bg) {
    bg.placeImageXY(
        new RectangleImage(MazeWorld.CELLSIZE - 1, MazeWorld.CELLSIZE - 1, "solid",
            new Color(107, 202, 226)),
        this.x * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2,
        this.y * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2);
  }
}

Represents each indvidual edge, which contains the cell it extends from and the one it goes to, as well as a weight. Contains methods to compare the weight of one cell to another and render methods.

// a class to represent edges
class Edge implements Comparable< Edge > {
  Cell from;
  Cell to;
  int weight;

  Edge(Cell f, Cell t, int w) {
    this.from = f;
    this.to = t;
    this.weight = w;
  }

  // compares the weight of this edge to that edge
  public int compareTo(Edge e) {
    int compareWeight = e.weight;
    return this.weight - compareWeight;
  }

  // draw a line cell to cell
  void render(WorldScene bg) {
    int fromX = this.from.x * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2;
    int toX = this.to.x * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2;
    int fromY = this.from.y * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2;
    int toY = this.to.y * MazeWorld.CELLSIZE + MazeWorld.CELLSIZE / 2;
    int midpointX = (fromX + toX) / 2;
    int midpointY = (fromY + toY) / 2;
    Posn endPoint = new Posn(0, 0);

    if (this.from.x != this.to.x) {
      endPoint.x = 0;
      endPoint.y = MazeWorld.CELLSIZE - 2;
    }
    else {
      endPoint.x = MazeWorld.CELLSIZE - 2;
      endPoint.y = 0;
    }

    WorldImage image = new LineImage(endPoint, Color.LIGHT_GRAY);
    bg.placeImageXY(image, midpointX, midpointY);

  }
}

Represents everything that happens in the mazeworld

// a class to represent the maze in a world image
class MazeWorld extends World {
  // defines a width constant
  final static int WIDTH = 30;
  // defines a height constant
  final static int HEIGHT = 20;
  // defines a cell size constant to render
  final static int CELLSIZE = 20;
  // world scene
  WorldScene background;
  // represents a list of all edges in the world
  ArrayList< Edge > edges = new ArrayList< Edge >();
  // represents a list of all Cells in the world
  ArrayList< Cell > cells = new ArrayList< Cell >();
  // HashMap to represent ids and nodes
  HashMap< Integer, Cell > idMap = new HashMap< Integer, Cell >();
  // random object
  Random rand = new Random();
  // represents all good edges
  ArrayList< Edge > goodEdges = new ArrayList< Edge >();
  // is this depth first search?
  boolean dfs = true;
  // cells yet to be searched
  Deque< Cell > worklist = new Deque< Cell >();
  // cells already seen
  ArrayList< Cell > seen = new ArrayList< Cell >();
  // is the path complete?
  Boolean complete = false;
  // Represents the final cell in the maze
  Cell end;
  // Represents the starting cell in the maze
  Cell start;
  // a HashMap to represent the relationship between child and parent nodes
  HashMap< Cell, Cell > childParent = new HashMap< Cell, Cell >();
  // Represents the cells along the completed maze path
  ArrayList< Cell > path = new ArrayList< Cell >();
  // have the edges been initialized?
  boolean edgesDone = false;
  // Represents all good edges - for animation purposes
  ArrayList< Edge > animateEdges = new ArrayList< Edge >();
  // for the purpose of counting indices in on tick
  int i = 0;
  // has the maze been rendered?
  boolean mazeDrawn = false;
  // is there a vertical bias?
  boolean verticalBias = false;
  // is there a horizontal bias?
  boolean horizontalBias = false;
  // represents the player 2 starting point
  Cell start2;
  // is this a 2 player game?
  boolean twoPlayer = false;
  // represents the player 2 end point
  Cell end2;
  // can the player control traversal?
  boolean playerControl = false;
  // Represents the Cell that the player is currently on
  Cell player;
  // Represents the Cell that the second player is currently on
  Cell player2;
  // Represents the cells that the player has visited
  ArrayList< Cell > visited = new ArrayList< Cell >();
  // is the start method done drawing everything?
  boolean search = false;
  // should the search path be drawn?
  boolean draw = false;
  // count the number of incorrect moves
  int score = 0;
  // draw the path for each cell the player has visited?
  boolean drawPath = true;

  MazeWorld() {
    initCells();
    initEdges();
    kruskal();

    end = cells.get(cells.size() - 1);
    // worklist starts with starting cell in it
    start = cells.get(0);
    worklist.addAtHead(start);
    this.player = start;

  }

Represents everything that happens on tick. Once Kruskal's algorithm has created a list of good edges (the final edges that will comprise the maze), on each tick one item from that list is added to a new list, which is what's drawn in order to animate each edge being "knocked down."

  // Advances any changes in the maze on tick
  // EFFECT: adds items to animateEdges, adds items to seen, adds items to
  // childParent
  public void onTick() {
    if (edgesDone) {
      if (animateEdges.size() != goodEdges.size()) {
        animateEdges.add(goodEdges.get(i));
        i += 1;
      }
      else {
        mazeDrawn = true;
      }
      if (this.player.equals(this.end)) {
        this.complete = true;
      }
    } 

This part occurs once the maze has been fully constructed and drawn. On each tick we check if the worklist still has items in it. If it does, the current cell is taken from the from of the list and evaluated. The key difference between breadth first and depth first search is whether the current cells neighbors are added to the beginning of the work list or to the end.

    if (mazeDrawn && search) {
      if (worklist.size() > 0) {
        Cell current = worklist.removeFromHead();
        // if current cell is the last cell
        if (current.equals(end)) {
          seen.add(current);
          // end the maze
          complete = true;
          // find the reverse path
          findPath();
        }
        else if (!seen.contains(current) && !complete) {
          for (Edge e : current.edges) {
            if (dfs) {
              if (e.to.equals(current)) {
                worklist.addAtHead(e.from);
              }
              else {
                worklist.addAtHead(e.to);
              }
            }
            else {
              if (e.to.equals(current)) {
                worklist.addAtTail(e.from);
              }
              else {
                worklist.addAtTail(e.to);
              }
            }

A hashmap is populated where the key is the child and the item is its parent, which will ultimately be used to find the one path from the end back to the start. The current cell is also added the list of cells that have already been seen (to make sure the same cell is not evaluated more than once.)

            if (!childParent.containsKey(e.to) || !childParent.containsKey(e.from)) {
              if (e.to.equals(current)) {
                childParent.put(e.from, current);
              }
              else {
                childParent.put(e.to, current);
              }
            }

          }
          seen.add(current);
        }
      }
    }
  } 

Solve maze does the exact same thing as what happens in on tick, except "silently." Aka it leaves no visual evidence of its search.

  // traverses the maze from start to finish
  // EFFECT: populate childParent
  public void solveMaze() {
    Deque< Cell > noDrawWorklist = new Deque< Cell >();
    noDrawWorklist.addAtHead(start);
    ArrayList< Cell > noDrawSeen = new ArrayList< Cell >();
    boolean noDrawComplete = false;

    while (noDrawWorklist.size() > 0) {
      Cell current = noDrawWorklist.removeFromHead();
      // if current cell is the last cell
      if (current.equals(end)) {
        noDrawSeen.add(current);
        // end the maze
        noDrawComplete = true;
        // find the reverse path
        findPath();
      }
      else if (!noDrawSeen.contains(current) && !noDrawComplete) {

        for (Edge e : current.edges) {
          if (e.to.equals(current)) {
            noDrawWorklist.addAtHead(e.from);
          }
          else {
            noDrawWorklist.addAtHead(e.to);
          }

          if (!childParent.containsKey(e.to) || !childParent.containsKey(e.from)) {
            if (e.to.equals(current)) {
              childParent.put(e.from, current);
            }
            else {
              childParent.put(e.to, current);
            }
          }

        }
        noDrawSeen.add(current);
      }
    }
  }

The hashmap for children and their parents is used to find the path from end to finish by tracing back each parent to its child until we reach the very first cell. There will only be one path through.

  // find the path from end to start
  // EFFECT: edit list of cells that constitute path from end to start
  public void findPath() {
    Cell current = end;
    // while we haven't reached the beginning of the maze
    while (!current.equals(start)) {
      Cell next = childParent.get(current);
      path.add(current);
      current = next;
    }
  }

Cells are initialized with an ID value counting up from 100 by 1 and with an empty ArrayList of Edges. They are also added to a hashmap linking their ID and the cell.

  // initializes Cells
  // EFFECT: Cells contains all Cells in the maze
  void initCells() {
    int idVal = 100;
    for (int i = 0; i < HEIGHT; i += 1) {
      for (int j = 0; j < WIDTH; j += 1) {
        Cell newCell = new Cell(j, i, idVal, new ArrayList< Edge >());
        cells.add(newCell);
        idMap.put(idVal, newCell);
        idVal = idVal + 1;
      }
    }
  }

Each cell has up to 2 edges assigned to it. At most a cell has an edge pointing to the right and an edge pointing down if it is anywhere except the far right column or bottom row. Right column cells have an edge facing down and bottom row cells have an edge facing to the right. Edges are initialized with a random weight.

  // initializes edges
  // EFFECT: edges contains all edges in the maze
  void initEdges() {
    int bias = 0;
    if (horizontalBias) {
      bias = 70;
    }
    else if (verticalBias) {
      bias = -70;
    }
    // look at each cell in the list of all cells in the world
    for (Cell c : cells) {
      int randomWeight;

      // if this cell is in the bottom row, but its not the rightmost corner
      if (c.y == HEIGHT - 1 && c.x != WIDTH - 1) {
        // give it only right pointing edges
        randomWeight = rand.nextInt(100) + 0;
        Edge edgeRight = new Edge(c, this.idMap.get(c.id + 1), randomWeight);
        edges.add(edgeRight);
      }

      // if this cell is in the right column, but not at the bottom
      if (c.x == WIDTH - 1 && c.y != HEIGHT - 1) {
        // give it only down pointing edges
        randomWeight = rand.nextInt(100) + 0;
        Edge edgeDown = new Edge(c, this.idMap.get(c.id + WIDTH), randomWeight);
        edges.add(edgeDown);
      }

      // if this cell is not the rightmost bottom-most corner
      if (c.x != WIDTH - 1 && c.y != HEIGHT - 1) {
        // give it right pointing edges and down pointing edges
        randomWeight = rand.nextInt(100) + bias;
        Edge edgeD = new Edge(c, this.idMap.get(c.id + WIDTH), randomWeight);
        // make a new random weight for this edge
        randomWeight = rand.nextInt(100);
        Edge edgeR = new Edge(c, this.idMap.get(c.id + 1), randomWeight);
        edges.add(edgeD);
        edges.add(edgeR);
      }
    }
  }

Kruskal's algorithm removes "bad" edges in order to create one path through the maze. The total number of good edges will be one less than the total number of cells. The edges are sorted from lowest weight to heighest weight and then the cells at the ends of each edge are examined. Any edges that would create a complete loop are discarded.

  // makes random path
  // EFFECT: removes edges that create bad loops
  void kruskal() {
    Collections.sort(edges);
    int i = 0;
    while (goodEdges.size() < cells.size() - 1) {
      Edge currEdge = edges.get(i);
      Cell fromLeader = currEdge.from.findLeader();
      Cell toLeader = currEdge.to.findLeader();

      // if they don't have the same leader
      if (fromLeader.id != toLeader.id) {
        // update the leader of the to link
        currEdge.from.findLeader().leader = currEdge.to.findLeader();
        // add this edge to good edges
        goodEdges.add(currEdge);
        currEdge.from.edges.add(currEdge);
        currEdge.to.edges.add(currEdge);
      }
      i = i + 1;
    }
    edgesDone = true;
  }

The scene is rendered

  // draw the scene
  public WorldScene makeScene() {
    this.background = new WorldScene(WIDTH * CELLSIZE, HEIGHT * CELLSIZE);
    this.background.placeImageXY(
        new RectangleImage(WIDTH * CELLSIZE, 
        HEIGHT * CELLSIZE, "solid", Color.LIGHT_GRAY),
        WIDTH * CELLSIZE / 2, HEIGHT * CELLSIZE / 2);
    for (Cell c : this.cells) {
      c.render(this.background);
    }
    for (Edge e : this.animateEdges) {
      e.render(this.background);
    }
    if (draw) {
      for (Cell c : this.seen) {
        c.renderExplore(this.background);
      }
    }
    start.renderStart(this.background);
    end.renderEnd(this.background);

    if (this.complete) {
      for (Cell c : this.path) {
        c.renderPath(this.background);
        start.renderPath(this.background);
      }
    }
    if (twoPlayer) {
      start2.renderStart(this.background);
      end2.renderEnd(this.background);
      this.player.renderPlayer(this.background);
      this.player2.renderPlayer(this.background);
    }
    if (this.playerControl) {
      if (this.drawPath) {
        for (Cell c : this.visited) {
          c.renderPath(this.background);
        }
      }
      this.player.renderPlayer(this.background);
    }
    return this.background;
  }

Keys allow for different behaivor in the application

  public void onKeyEvent(String key) {
    if (key.equals("v")) {
      reset();
      this.verticalBias = true;

      start();
      search();
    }
    if (key.equals("h")) {
      reset();
      this.horizontalBias = true;

      start();
      search();
    }

    if (key.equals("r")) {
      reset();
      start();
    }
    if (key.equals("enter")) {
      this.draw = false;
      this.playerControl = true;
      search();
      solveMaze();
      this.draw = true;
    }
    if (key.equals("2")) {
      reset();
      this.drawPath = false;
      this.twoPlayer = true;
      twoPlayer();
      search();
    }
    if (key.equals("b")) {
      this.draw = true;
      this.search = true;
      this.dfs = false;
      search();
    }

    if (key.equals("d")) {
      this.search = true;
      this.dfs = true;
      this.draw = true;
      search();
    }

    if (key.equals("f")) {
      if (drawPath) {
        this.drawPath = false;
      }
      else {
        this.drawPath = true;
      }
    }

    if (playerControl) {
      movePlayer(key);
    }

    if (twoPlayer) {
      movePlayer(key);
      movePlayer2(key);
    }
  }

Determines which way the user can move based on the edges extending from the cell the player currently occupies

  // Determines how to move the character in the maze given depending Key Presses
  // EFFECT: moves the player, changes which cell it occupies
  void movePlayer(String key) {
    boolean canMoveUp = false;
    boolean canMoveDown = false;
    boolean canMoveRight = false;
    boolean canMoveLeft = false;

    if (this.player.equals(this.end)) {
      this.complete = true;
    }

    for (Edge e : this.player.edges) {
      Cell other;
      if (e.to.equals(this.player)) {
        other = e.from;
      }
      else {
        other = e.to;
      }
      if (other.id == this.player.id - WIDTH) {
        canMoveUp = true;
      }
      else if (other.id == this.player.id + WIDTH) {
        canMoveDown = true;
      }
      else if (other.id == this.player.id + 1) {
        canMoveRight = true;
      }
      else if (other.id == this.player.id - 1) {
        canMoveLeft = true;
      }
    }
    visited.add(player);

    if (!path.contains(player)) {
      score = score + 1;
    }

    if (key.equals("up") && canMoveUp) {
      this.player = this.idMap.get(this.player.id - WIDTH);
    }
    if (key.equals("down") && canMoveDown) {
      this.player = this.idMap.get(this.player.id + WIDTH);
    }
    if (key.equals("right") && canMoveRight) {
      this.player = this.idMap.get(this.player.id + 1);
    }
    if (key.equals("left") && canMoveLeft) {
      this.player = this.idMap.get(this.player.id - 1);
    }
  }

  // Determines how to move the character in the maze given depending Key Presses
  // EFFECT: moves the player, changes which cell it occupies
  void movePlayer2(String key) {
    boolean canMoveUp = false;
    boolean canMoveDown = false;
    boolean canMoveRight = false;
    boolean canMoveLeft = false;

    for (Edge e : this.player2.edges) {
      Cell other;
      if (e.to.equals(this.player2)) {
        other = e.from;
      }
      else {
        other = e.to;
      }
      if (other.id == this.player2.id - WIDTH) {
        canMoveUp = true;
      }
      else if (other.id == this.player2.id + WIDTH) {
        canMoveDown = true;
      }
      else if (other.id == this.player2.id + 1) {
        canMoveRight = true;
      }
      else if (other.id == this.player2.id - 1) {
        canMoveLeft = true;
      }
    }
    visited.add(player2);

    if (!path.contains(player2)) {
      score = score + 1;
    }

    if (key.equals("i") && canMoveUp) {
      this.player2 = this.idMap.get(this.player2.id - WIDTH);
    }
    if (key.equals("k") && canMoveDown) {
      this.player2 = this.idMap.get(this.player2.id + WIDTH);
    }
    if (key.equals("l") && canMoveRight) {
      this.player2 = this.idMap.get(this.player2.id + 1);
    }
    if (key.equals("j") && canMoveLeft) {
      this.player2 = this.idMap.get(this.player2.id - 1);
    }
  }
  // allows two players to navigate the maze at the same time
  // Effect: sets up the maze for two player racing
  void twoPlayer() {
    initCells();
    initEdges();
    kruskal();

    this.end2 = this.cells.get(cells.size() - WIDTH);
    this.start2 = this.cells.get(WIDTH - 1);
    this.player2 = this.start2;
  }

Reset resets the variables in the maze to create a new one. Start draws the maze and search begins traversing it

  // reset the maze
  // Effect: Resets the maze entirely
  void reset() {
    this.cells = new ArrayList< Cell >();
    this.edges = new ArrayList< Edge >();
    this.goodEdges = new ArrayList< Edge >();
    this.animateEdges = new ArrayList< Edge >();
    this.childParent = new HashMap< Cell, Cell >();
    this.seen = new ArrayList< Cell >();
    this.complete = false;
    this.edgesDone = false;
    this.idMap = new HashMap< Integer, Cell >();
    this.worklist = new Deque< Cell >();
    this.path = new ArrayList< Cell >();
    this.i = 0;
    this.mazeDrawn = false;
    this.verticalBias = false;
    this.horizontalBias = false;
    this.twoPlayer = false;
    this.playerControl = false;
    this.search = false;
    this.visited = new ArrayList< Cell >();
    this.draw = false;
    this.score = 0;
  }

  // initializes the starting conditions of the maze
  // Effect: starts the maze
  void start() {
    initCells();
    initEdges();
    kruskal();
    edgesDone = true;
    if (playerControl) {
      this.player = this.cells.get(0);
    }
  }

  // begin searching through the maze
  // EFFECT: start searching
  void search() {
    if (playerControl) {
      this.player = this.cells.get(0);
    }
    end = cells.get(cells.size() - 1);
    start = cells.get(0);
    worklist.addAtHead(start);
  }
}