Generates perfect mazes on H3 hexagonal grids. More...

#include <h3MazeGenerator.h>

Inheritance diagram for H3MazeGenerator:

Collaboration diagram for H3MazeGenerator:

Classes
struct	H3IndexHash
	Hash function for H3Index in unordered containers. More...

struct	MazeResult
	Result structure containing generated maze data. More...

Public Member Functions
	H3MazeGenerator (QObject *parent=nullptr)
	Constructs an H3MazeGenerator.

	~H3MazeGenerator () override=default
	Default destructor.

std::unordered_set< H3Index >	generateMaze (H3Index centerCell, int radius)
	Generates a maze centered at the given cell.

MazeResult	generateMazeWithEntrances (H3Index centerCell, int radius)
	Generates a maze with entrance and exit points.

void	mazeGenerated (const std::unordered_set< H3Index > &walls)
	Emitted when maze generation is complete.

Public Attributes
	: void generationProgress(int percent)

Private Member Functions
std::array< H3Index, 6 >	getNeighbors (H3Index cell)
	Gets the 6 neighbors of a hexagonal cell.

std::unordered_set< H3Index, H3IndexHash >	createRoomGrid (const std::unordered_set< H3Index, H3IndexHash > &allCells)
	Creates a sparse room grid with minimum 2-cell spacing.

std::optional< H3Index >	findWallBetween (H3Index room1, H3Index room2)
	Finds the wall cell between two rooms.

std::unordered_set< H3Index, H3IndexHash >	generateMazePrim (const std::unordered_set< H3Index, H3IndexHash > &rooms)
	Generates maze passages using randomized Prim's algorithm.

H3Index	findFarthestRoom (H3Index start, const std::unordered_set< H3Index, H3IndexHash > &passages)
	Finds the room farthest from the start using BFS.

Static Private Member Functions
static std::unordered_set< H3Index, H3IndexHash >	getCellsInRadius (H3Index center, int radius)
	Gets all cells within a radius of the center.

static std::vector< H3Index >	getRoomNeighbors (H3Index room, const std::unordered_set< H3Index, H3IndexHash > &rooms)
	Gets rooms that are neighbors at distance 2.

static bool	isOnBorder (H3Index cell, H3Index center, int radius)
	Checks if a cell is on the border of the maze area.

Private Attributes
std::mt19937	rng_
	Random number generator for maze randomization.

std::array< H3Index, 6 >	neighbors_ {}
	Temporary storage for neighbor cells.

Detailed Description

Generates perfect mazes on H3 hexagonal grids.

The H3MazeGenerator uses a modified Prim's algorithm to create perfect mazes (mazes with exactly one solution path) on hexagonal grids.

Algorithm Overview

Create a room grid with minimum 2-cell spacing
Initialize with a random room
Add walls to frontier
Randomly select walls and connect rooms
Repeat until all rooms are connected

Example Usage: H3MazeGenerator generator;

// Generate maze centered at a cell with radius 20

auto result = generator.generateMazeWithEntrances(centerCell, 20);

// result.walls contains all wall cells

// result.entrance is the maze entry point

// result.exit is the maze exit point

H3MazeGenerator
Generates perfect mazes on H3 hexagonal grids.
Definition h3MazeGenerator.h:45

H3MazeGenerator::generateMazeWithEntrances
MazeResult generateMazeWithEntrances(H3Index centerCell, int radius)
Generates a maze with entrance and exit points.
Definition h3MazeGenerator.cpp:244

See also: H3AStar for pathfinding through the maze; H3MazeAdapter for async maze generation

Definition at line 45 of file h3MazeGenerator.h.

Class Documentation

◆ H3MazeGenerator::MazeResult

struct H3MazeGenerator::MazeResult

Result structure containing generated maze data.

Definition at line 72 of file h3MazeGenerator.h.

Collaboration diagram for H3MazeGenerator::MazeResult:

Class Members
H3Index	entrance	Entry point cell index.
H3Index	exit	Exit point cell index.
unordered_set< H3Index >	walls	Set of wall cell indices.

Constructor & Destructor Documentation

◆ H3MazeGenerator()

H3MazeGenerator::H3MazeGenerator ( QObject * parent = nullptr )

explicit

Constructs an H3MazeGenerator.

Parameters

parent Optional parent QObject for memory management.

Definition at line 5 of file h3MazeGenerator.cpp.

◆ ~H3MazeGenerator()

H3MazeGenerator::~H3MazeGenerator ( )

overridedefault

Default destructor.

Member Function Documentation

◆ createRoomGrid()

std::unordered_set< H3Index, H3MazeGenerator::H3IndexHash > H3MazeGenerator::createRoomGrid ( const std::unordered_set< H3Index, H3IndexHash > & allCells )

private

Creates a sparse room grid with minimum 2-cell spacing.

Rooms are the passable cells in the maze. This method ensures rooms are separated by at least 2 cells to allow walls between them.

Parameters

allCells Set of all available cells.

Returns: Set of room cell indices.

Definition at line 59 of file h3MazeGenerator.cpp.

References getNeighbors().

Referenced by generateMazeWithEntrances().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findFarthestRoom()

H3Index H3MazeGenerator::findFarthestRoom	(	H3Index	start,
		const std::unordered_set< H3Index, H3IndexHash > &	passages
	)

private

Finds the room farthest from the start using BFS.

Used to determine optimal entrance/exit placement.

Parameters

start	Starting room cell.
passages	Set of all passable cells.

Returns: The farthest room from start.

Definition at line 199 of file h3MazeGenerator.cpp.

References getNeighbors().

Referenced by generateMazeWithEntrances().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ findWallBetween()

std::optional< H3Index > H3MazeGenerator::findWallBetween	(	H3Index	room1,
		H3Index	room2
	)

private

Finds the wall cell between two rooms.

Rooms are at distance 2 from each other; this finds the intermediate cell that acts as a wall.

Parameters

room1	First room cell.
room2	Second room cell.

Returns: The wall cell, or nullopt if rooms aren't neighbors.

Definition at line 115 of file h3MazeGenerator.cpp.

References getNeighbors().

Referenced by generateMazePrim().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ generateMaze()

std::unordered_set< H3Index > H3MazeGenerator::generateMaze	(	H3Index	centerCell,
		int	radius
	)

Generates a maze centered at the given cell.

Parameters

centerCell	The H3 cell index at the maze center.
radius	The maze radius in cells.

Returns: Set of H3 cell indices representing maze walls.

Note: For entrance/exit information, use generateMazeWithEntrances().

Definition at line 305 of file h3MazeGenerator.cpp.

References generateMazeWithEntrances().

Referenced by H3MazeAdapter::generateMaze().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ generateMazePrim()

std::unordered_set< H3Index, H3MazeGenerator::H3IndexHash > H3MazeGenerator::generateMazePrim ( const std::unordered_set< H3Index, H3IndexHash > & rooms )

private

Generates maze passages using randomized Prim's algorithm.

Parameters

rooms Set of room cells.

Returns: Set of passage cells (rooms + connecting corridors).

Definition at line 131 of file h3MazeGenerator.cpp.

References findWallBetween(), getRoomNeighbors(), and rng_.

Referenced by generateMazeWithEntrances().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ generateMazeWithEntrances()

H3MazeGenerator::MazeResult H3MazeGenerator::generateMazeWithEntrances	(	H3Index	centerCell,
		int	radius
	)

Generates a maze with entrance and exit points.

Creates a perfect maze with identified entry and exit points. The entrance and exit are placed at the farthest points from each other within the maze.

Parameters

centerCell	The H3 cell index at the maze center.
radius	The maze radius in cells.

Returns: MazeResult containing walls, entrance, and exit.

Algorithm Details

Rooms are placed with minimum 2-cell spacing
Walls fill the gaps between rooms
BFS is used to find the farthest room pair for entrance/exit

Definition at line 244 of file h3MazeGenerator.cpp.

References createRoomGrid(), findFarthestRoom(), generateMazePrim(), getCellsInRadius(), isOnBorder(), mazeGenerated(), and rng_.

Referenced by generateMaze().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getCellsInRadius()

std::unordered_set< H3Index, H3MazeGenerator::H3IndexHash > H3MazeGenerator::getCellsInRadius	(	H3Index	center,
		int	radius
	)

staticprivate

Gets all cells within a radius of the center.

Parameters

center	The center cell.
radius	The radius in cells.

Returns: Set of all cells within the radius (excluding pentagons).

Definition at line 27 of file h3MazeGenerator.cpp.

Referenced by generateMazeWithEntrances().

Here is the caller graph for this function:

◆ getNeighbors()

std::array< H3Index, 6 > H3MazeGenerator::getNeighbors ( H3Index cell )

private

Gets the 6 neighbors of a hexagonal cell.

Parameters

cell	The cell to get neighbors for.

Returns: Array of 6 neighbor indices.

Definition at line 7 of file h3MazeGenerator.cpp.

References neighbors_.

Referenced by createRoomGrid(), findFarthestRoom(), and findWallBetween().

Here is the caller graph for this function:

◆ getRoomNeighbors()

std::vector< H3Index > H3MazeGenerator::getRoomNeighbors	(	H3Index	room,
		const std::unordered_set< H3Index, H3IndexHash > &	rooms
	)

staticprivate

Gets rooms that are neighbors at distance 2.

Parameters

room	The room to find neighbors for.
rooms	Set of all rooms.

Returns: Vector of neighboring room indices.

Definition at line 83 of file h3MazeGenerator.cpp.

Referenced by generateMazePrim().

Here is the caller graph for this function:

◆ isOnBorder()

bool H3MazeGenerator::isOnBorder	(	H3Index	cell,
		H3Index	center,
		int	radius
	)

staticprivate

Checks if a cell is on the border of the maze area.

Parameters

cell	The cell to check.
center	The maze center cell.
radius	The maze radius.

Returns: true if the cell is on the border.

Definition at line 233 of file h3MazeGenerator.cpp.

Referenced by generateMazeWithEntrances().

Here is the caller graph for this function:

◆ mazeGenerated()

void H3MazeGenerator::mazeGenerated ( const std::unordered_set< H3Index > & walls )

Emitted when maze generation is complete.

Parameters

walls Set of wall cell indices.

Referenced by generateMazeWithEntrances().

Here is the caller graph for this function:

Member Data Documentation

◆ pad0

H3MazeGenerator::__pad0__

Definition at line 105 of file h3MazeGenerator.h.

◆ neighbors_

std::array<H3Index, 6> H3MazeGenerator::neighbors_ {}

private

Temporary storage for neighbor cells.

Definition at line 125 of file h3MazeGenerator.h.

Referenced by getNeighbors().

◆ rng_

std::mt19937 H3MazeGenerator::rng_

private

Random number generator for maze randomization.

Definition at line 122 of file h3MazeGenerator.h.

Referenced by generateMazePrim(), and generateMazeWithEntrances().

The documentation for this class was generated from the following files:

src/models/h3MazeGenerator.h
src/models/h3MazeGenerator.cpp

Classes

Public Member Functions

Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Class Documentation

◆ H3MazeGenerator::MazeResult

Constructor & Destructor Documentation

◆ H3MazeGenerator()

◆ ~H3MazeGenerator()

Member Function Documentation

◆ createRoomGrid()

◆ findFarthestRoom()

◆ findWallBetween()

◆ generateMaze()

◆ generateMazePrim()

◆ generateMazeWithEntrances()

◆ getCellsInRadius()

◆ getNeighbors()

◆ getRoomNeighbors()

◆ isOnBorder()

◆ mazeGenerated()

Member Data Documentation

◆ __pad0__

◆ neighbors_

◆ rng_

◆ pad0