Package util

Class MazeGenerator

java.lang.Object

util.MazeGenerator

public class MazeGenerator
extends Object

Used to generate a "Pac-Man style" maze on which the game is played.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static final record	MazeGenerator.Cell	Connected components of Cells model wall segments in our generator algorithm.
private static final record	MazeGenerator.CellBoundary	Edges represent the boundaries of cells.
private static enum	MazeGenerator.Orientation	The direction of this edge.
static enum	MazeGenerator.TileType	Each tile (i.e.

Field Summary

Fields

Modifier and Type	Field	Description
(package private) final int	height	The height of the mazes (i.e., number of path rows) produced by this generator.
(package private) final Random	rng
(package private) final int	width	The width of the mazes (i.e., number of path columns) produced by this generator.

Constructor Summary

Constructors

Constructor	Description
MazeGenerator(int width, int height, Random rng)	Construct a maze generator that produces mazes of size `3*width+2 x 3*height+2`.

Method Summary

Modifier and Type	Method	Description
private void	fillAssignedTileTypes(MazeGenerator.TileType[][] tiles, boolean[][] horizontalEdges, boolean[][] verticalEdges)	Use the horizontal and vertical edge assignments to determine the remaining tile types.
private void	fillKnownTileTypes(MazeGenerator.TileType[][] tiles)	Fill in the types of tiles that are not randomly generated.
private void	fixGhostBox(MazeGenerator.TileType[][] tiles)	Reassign the types of tiles within the ghost box.
MazeGenerator.TileType[][]	generateMaze()	Returns a randomly generated maze, which a 2D array of dimension `3*width+2` by `3*height+2` of either wall or path tiles.
private HashMap<MazeGenerator.Cell,HashSet<MazeGenerator.Cell>>	initializeCellComponents(int w, int h)	Return a hashmap associating each cell with its connected component.
private List<MazeGenerator.CellBoundary>	initializeEdges(boolean[][] horizontalEdges, boolean[][] verticalEdges)	Initialize the edges that must be present/absent in the graph.
private void	randomlyAssignEdges(boolean[][] horizontalEdges, boolean[][] verticalEdges, List<MazeGenerator.CellBoundary> assignableCellBoundaries, HashMap<MazeGenerator.Cell,HashSet<MazeGenerator.Cell>> components)	Iterate over the assignable edges in a random order to determine whether to include them.
private static <T> void	shuffle(List<T> list, Random rng)	Shuffle the contents of `list` in place.

Methods inherited from class java.lang.Object

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

Field Details

width

final int width

The width of the mazes (i.e., number of path columns) produced by this generator.

height

final int height

The height of the mazes (i.e., number of path rows) produced by this generator.

rng

final Random rng

Constructor Details

MazeGenerator

public MazeGenerator(int width,
 int height,
 Random rng)

Construct a maze generator that produces mazes of size `3*width+2 x 3*height+2`.

Method Details

generateMaze

public MazeGenerator.TileType[][] generateMaze()

Returns a randomly generated maze, which a 2D array of dimension `3*width+2` by `3*height+2` of either wall or path tiles. Guarantees that all path tiles (except for the ghost's starting box) will be connected. Requires `width >= 4` and `height >= 3`.

fillKnownTileTypes

private void fillKnownTileTypes(MazeGenerator.TileType[][] tiles)

Fill in the types of tiles that are not randomly generated.

initializeCellComponents

private HashMap<MazeGenerator.Cell,HashSet<MazeGenerator.Cell>> initializeCellComponents(int w,
 int h)

Return a hashmap associating each cell with its connected component. Initially, a cells connected component is the singleton set containing that cell.

initializeEdges

private List<MazeGenerator.CellBoundary> initializeEdges(boolean[][] horizontalEdges,
 boolean[][] verticalEdges)

Initialize the edges that must be present/absent in the graph. Return a list of the edges that can be randomly determined.

randomlyAssignEdges

private void randomlyAssignEdges(boolean[][] horizontalEdges,
 boolean[][] verticalEdges,
 List<MazeGenerator.CellBoundary> assignableCellBoundaries,
 HashMap<MazeGenerator.Cell,HashSet<MazeGenerator.Cell>> components)

Iterate over the assignable edges in a random order to determine whether to include them. An edge is deleted as long as it does not introduce a connected component that is too large or create a dead-end in the maze.

fillAssignedTileTypes

private void fillAssignedTileTypes(MazeGenerator.TileType[][] tiles,
 boolean[][] horizontalEdges,
 boolean[][] verticalEdges)

Use the horizontal and vertical edge assignments to determine the remaining tile types.

fixGhostBox

private void fixGhostBox(MazeGenerator.TileType[][] tiles)

Reassign the types of tiles within the ghost box.

shuffle

private static <T> void shuffle(List<T> list,
 Random rng)

Shuffle the contents of `list` in place. Each element has a uniform probability of being placed at any index in the list. The resulting order depends on the sequence of random integers provided by `rng`.