Package com.csse3200.game.minigames.maze

Class Maze

java.lang.Object
com.csse3200.game.minigames.maze.Maze
public class Maze extends Object
Represents a maze on a 2d grid. Allows for generation of random mazes, finding reasonable spawn locations of objects in the maze and querying shortest paths.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    class 
    Maze.BreadthFirstSearch
    Class for bfs, used for finding paths in the maze (including the angular fish path to the player)

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    final List<com.badlogic.gdx.math.GridPoint2>[][]
    adjacency
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    Maze(int size)
     
    Maze(int width, int height)
     
    Maze(com.badlogic.gdx.math.GridPoint2 size)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    breakWalls(int count)
    Break some walls in the maze to create cycles and multiple paths between cells.
    void
    connect(com.badlogic.gdx.math.GridPoint2 u, com.badlogic.gdx.math.GridPoint2 v)
    Connect two cells by breaking the wall between then.
    List<com.badlogic.gdx.math.GridPoint2>
    getAdjacent(com.badlogic.gdx.math.GridPoint2 cell)
    Method to get the grid cells adjacent to a specific cell (ignoring maze walls)
    int
    getHeight()
    Get the maze height
    List<com.badlogic.gdx.math.GridPoint2>
    getMazeAdjacent(int x, int y)
    Method to get the grid cells adjacent to a specific cell (taking into account maze walls)
    List<com.badlogic.gdx.math.GridPoint2>
    getMazeAdjacent(com.badlogic.gdx.math.GridPoint2 cell)
     
    com.badlogic.gdx.math.GridPoint2
    getNextStartLocation()
    Find a new start location that is reasonably well spaced from all other start locations.
    List<com.badlogic.gdx.math.GridPoint2>
    getNotMazeAdjacent(com.badlogic.gdx.math.GridPoint2 cell)
    Method to get the grid cells not adjacent to a specific cell (taking into account walls)
    com.badlogic.gdx.math.GridPoint2
    getRandomCell()
     
    int
    getWidth()
    Get the maze width
    boolean
    inBounds(int x, int y)
    Determines a position is in bounds of the maze
    boolean
    inBounds(com.badlogic.gdx.math.GridPoint2 cell)
     
    boolean
    isWall(int x, int y, com.badlogic.gdx.math.GridPoint2 direction)
     
    boolean
    isWall(com.badlogic.gdx.math.GridPoint2 cell, com.badlogic.gdx.math.GridPoint2 direction)
    Method to check if moving 1 cell in a given direction from a grid cell will run into a wall.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • adjacency

      public final List<com.badlogic.gdx.math.GridPoint2>[][] adjacency

  • Constructor Details

    • Maze

      public Maze(int size)

    • Maze

      public Maze(com.badlogic.gdx.math.GridPoint2 size)

    • Maze

      public Maze(int width, int height)

  • Method Details

    • getMazeAdjacent

      public List<com.badlogic.gdx.math.GridPoint2> getMazeAdjacent(int x, int y)
      Method to get the grid cells adjacent to a specific cell (taking into account maze walls)
      Parameters:
      x - x-position/column
      y - y-position/row
      Returns:
      the cell of the maze at the coordinate

    • getMazeAdjacent

      public List<com.badlogic.gdx.math.GridPoint2> getMazeAdjacent(com.badlogic.gdx.math.GridPoint2 cell)

    • getNotMazeAdjacent

      public List<com.badlogic.gdx.math.GridPoint2> getNotMazeAdjacent(com.badlogic.gdx.math.GridPoint2 cell)
      Method to get the grid cells not adjacent to a specific cell (taking into account walls)
      Parameters:
      cell - Grid cell
      Returns:
      the cell of the maze at the coordinate

    • isWall

      public boolean isWall(int x, int y, com.badlogic.gdx.math.GridPoint2 direction)

    • isWall

      public boolean isWall(com.badlogic.gdx.math.GridPoint2 cell, com.badlogic.gdx.math.GridPoint2 direction)
      Method to check if moving 1 cell in a given direction from a grid cell will run into a wall.
      Parameters:
      cell - Grid cell
      direction - Direction to check
      Returns:
      whether there is a wall in that direction from this grid cell.

    • inBounds

      public boolean inBounds(int x, int y)
      Determines a position is in bounds of the maze
      Parameters:
      x - x-position/column
      y - y-position/row
      Returns:
      true if not in bounds, otherwise false

    • inBounds

      public boolean inBounds(com.badlogic.gdx.math.GridPoint2 cell)

    • getAdjacent

      public List<com.badlogic.gdx.math.GridPoint2> getAdjacent(com.badlogic.gdx.math.GridPoint2 cell)
      Method to get the grid cells adjacent to a specific cell (ignoring maze walls)
      Parameters:
      cell - Grid cell
      Returns:
      the cell of the maze at the coordinate

    • connect

      public void connect(com.badlogic.gdx.math.GridPoint2 u, com.badlogic.gdx.math.GridPoint2 v)
      Connect two cells by breaking the wall between then. Assumes they are not already connected.
      Parameters:
      u - first cell
      v - second cell

    • getRandomCell

      public com.badlogic.gdx.math.GridPoint2 getRandomCell()
      Returns:
      A random maze cell

    • getNextStartLocation

      public com.badlogic.gdx.math.GridPoint2 getNextStartLocation()
      Find a new start location that is reasonably well spaced from all other start locations. Maintains a spanning tree connecting the current set of start locations. Then uses BFS to find the most distant cell from this spanning tree and returns it. I think I have a proof this approach constructs the set of n starting locations that maximises the minimum time to walk between every location for a tree graph, but since our maze has cycles, this is not guaranteed.
      Returns:
      The starting location grid cell

    • breakWalls

      public void breakWalls(int count)
      Break some walls in the maze to create cycles and multiple paths between cells.
      Parameters:
      count - the number of walls to break

    • getWidth

      public int getWidth()
      Get the maze width
      Returns:
      the maze width

    • getHeight

      public int getHeight()
      Get the maze height
      Returns:
      the maze height