Banjo API 1.1.0-alpha
Low-level C99 game development API
Loading...
Searching...
No Matches
Maze

Data Structures

struct  bj_maze_build_context
struct  bj_maze_algorithm

Macros

#define BJ_MAZE_NO_CELL   ((uint32_t)-1)
#define BJ_MAZE_NORTH   BJ_MAZE_DIR_NORTH
#define BJ_MAZE_WEST   BJ_MAZE_DIR_WEST
#define BJ_MAZE_SOUTH   BJ_MAZE_DIR_SOUTH
#define BJ_MAZE_EAST   BJ_MAZE_DIR_EAST

Typedefs

typedef void *(* bj_maze_setup_fn) (const struct bj_maze_build_context *context, struct bj_error **error)
typedef bj_bool(* bj_maze_step_fn) (struct bj_maze_build_context *context)
typedef void(* bj_maze_teardown_fn) (void *data)

Enumerations

enum  bj_maze_dir { BJ_MAZE_DIR_NORTH = 0 , BJ_MAZE_DIR_WEST = 1 , BJ_MAZE_DIR_SOUTH = 2 , BJ_MAZE_DIR_EAST = 3 }
enum  bj_maze_mark { BJ_MAZE_MARK_VISITED = 1u << 0 , BJ_MAZE_MARK_HEAD = 1u << 1 , BJ_MAZE_MARK_PATH = 1u << 2 , BJ_MAZE_MARK_USER = 1u << 3 }

Functions

struct bj_maze * bj_create_maze_ortho2d (size_t width, size_t height, struct bj_error **error)
void bj_destroy_maze (struct bj_maze *maze)
uint32_t bj_maze_ortho2d_cell (const struct bj_maze *maze, size_t row, size_t col)
uint32_t bj_open_maze_cell (struct bj_maze *maze, uint32_t cell, enum bj_maze_dir dir)
uint32_t bj_close_maze_cell (struct bj_maze *maze, uint32_t cell, enum bj_maze_dir dir)
bj_bool bj_maze_cell_is_open (const struct bj_maze *maze, uint32_t cell, enum bj_maze_dir dir)
void bj_maze_close_all (struct bj_maze *maze)
void bj_maze_open_all (struct bj_maze *maze)
uint32_t bj_maze_cell_count (const struct bj_maze *maze)
uint8_t bj_maze_degree (const struct bj_maze *maze)
uint32_t bj_maze_adjacent_cell (const struct bj_maze *maze, uint32_t cell, enum bj_maze_dir dir)
bj_bool bj_maze_cell_opened (const struct bj_maze *maze, uint32_t cell, enum bj_maze_dir dir)
void bj_close_maze (struct bj_maze *maze)
void bj_open_maze (struct bj_maze *maze)
uint32_t bj_maze_adjacent (const struct bj_maze *maze, uint32_t cell, enum bj_maze_dir dir)
struct bj_maze_marks * bj_create_maze_marks (const struct bj_maze *maze, struct bj_error **error)
void bj_destroy_maze_marks (struct bj_maze_marks *marks)
void bj_clear_maze_marks (struct bj_maze_marks *marks)
uint8_t bj_maze_cell_marks (const struct bj_maze_marks *marks, uint32_t cell)
void bj_mark_maze_cell (struct bj_maze_marks *marks, uint32_t cell, uint8_t bits)
void bj_unmark_maze_cell (struct bj_maze_marks *marks, uint32_t cell, uint8_t bits)
struct bj_maze_algorithm bj_maze_algorithm_btree (void)
struct bj_maze_algorithm bj_maze_algorithm_sidewinder (void)
struct bj_maze_algorithm bj_maze_algorithm_aldous_broder (void)
struct bj_maze_algorithm bj_maze_algorithm_wilson (void)
struct bj_maze_algorithm bj_maze_algorithm_hunt_and_kill (void)
struct bj_maze_algorithm bj_maze_algorithm_backtracker (void)
struct bj_maze_builder * bj_create_maze_builder (struct bj_maze *maze, struct bj_maze_algorithm algorithm, struct bj_maze_marks *marks, bj_random_u32_fn next, void *rng_state, struct bj_error **error)
void bj_destroy_maze_builder (struct bj_maze_builder *builder)
bj_bool bj_step_maze_builder (struct bj_maze_builder *builder)
void bj_run_maze_builder (struct bj_maze_builder *builder)
bj_bool bj_reset_maze_builder (struct bj_maze_builder *builder, struct bj_error **error)
bj_bool bj_maze_builder_is_complete (const struct bj_maze_builder *builder)
bj_bool bj_maze_builder_completed (const struct bj_maze_builder *builder)

Detailed Description

Grids of cells with walls between them, and the algorithms that knock the walls down.

A maze here is a set of cells and the passages between them. That is all it is: there are no corridors, no rooms and no pixels in it, and nothing in the representation knows what a maze looks like. What you get is the shape of the thing, and a drawing routine of your own decides how to show it.

Cells are numbers

Every cell has an index, from 0 to bj_maze_cell_count minus one, with no gaps. BJ_MAZE_NO_CELL is the one value that is never a cell: it comes back from anything asked about a cell that is not there.

Numbering them densely is what keeps the rest simple. Anything you want to remember per cell — distances, weights, whether the player has been there — is an array of your own, indexed by the cell:

uint32_t* distance = bj_malloc(bj_maze_cell_count(maze) * sizeof(uint32_t));
distance[cell] = 12;
uint32_t bj_maze_cell_count(const struct bj_maze *maze)
How many cells the maze has.
void * bj_malloc(size_t size)
Allocate size bytes of memory.

The maze holds none of that and never will. It would only get in the way of the one thing it is for.

Neighbours sit in numbered slots

Each cell has a fixed number of slots — bj_maze_degree of them — and each slot either holds the index of a neighbour or holds BJ_MAZE_NO_CELL. A cell in the middle of a square grid uses all four; one against an edge leaves the outward slots empty, which is why the boundary of a maze needs nothing stored to hold it in place.

The slot number means a direction, and which direction is a matter for the family of maze: on a square grid they are the four points of bj_maze_dir. An algorithm that never names a direction, and only asks for neighbours, works on every family there is.

Passages are bits

A passage is one bit per slot, and it is the only thing about a maze that changes after it has been created. A fresh maze has every wall standing; carving is bj_open_maze_cell, and it opens both sides at once, because a wall belongs to two cells and cannot be down for one of them and up for the other.

You cannot open a slot with no neighbour behind it. A passage always leads somewhere, which is what lets a dead end be recognised by counting the passages of a cell, and what stops a walk falling off the edge of the grid.

Making one

struct bj_maze* maze = bj_create_maze_ortho2d(20, 12, 0);
const uint32_t cell = bj_maze_ortho2d_cell(maze, 3, 4);
struct bj_maze bj_maze
Definition api.h:363
struct bj_maze * bj_create_maze_ortho2d(size_t width, size_t height, struct bj_error **error)
Allocate a new orthogonal 2D maze, with every wall still standing.
void bj_destroy_maze(struct bj_maze *maze)
Deletes a struct bj_maze object and releases associated memory.
uint32_t bj_maze_ortho2d_cell(const struct bj_maze *maze, size_t row, size_t col)
Find the cell at a position of an orthogonal 2D maze.
uint32_t bj_open_maze_cell(struct bj_maze *maze, uint32_t cell, enum bj_maze_dir dir)
Carve a passage out of cell through slot dir.
@ BJ_MAZE_DIR_EAST
Towards the right of the grid.
Definition maze.h:110

A maze made this way is a grid of separate cells with nothing joining them. Turning it into a maze is the business of maze_builder.h, which carves one a step at a time.


Data Structure Documentation

◆ bj_maze_build_context

struct bj_maze_build_context

Everything a build step is given to work with.

One of these is handed to the build callback on every step. All fields but data belong to the builder and must be left alone; data is the algorithm's own.

Definition at line 227 of file maze_builder.h.

Data Fields
void * data Algorithm state. See bj_maze_step_fn.
struct bj_maze_marks * marks Where to record progress, or NULL.
struct bj_maze * maze The maze being carved. Never NULL.
bj_random_u32_fn next RNG callback. Never NULL.
void * rng_state Opaque state to pass to next.

◆ bj_maze_algorithm

struct bj_maze_algorithm

A maze generation algorithm.

The built-in algorithms and your own are described the same way, so anything the library can run, your code can supply:

static bj_bool sweep_step(struct bj_maze_build_context* context) { ... }
const struct bj_maze_algorithm sweep = { .step = sweep_step };
maze, sweep, 0, bj_pcg32_generator, &rng, 0);
uint32_t bj_bool
Boolean type used throughout the Banjo API.
Definition api.h:264
struct bj_maze_builder bj_maze_builder
Definition api.h:364
struct bj_maze_builder * bj_create_maze_builder(struct bj_maze *maze, struct bj_maze_algorithm algorithm, struct bj_maze_marks *marks, bj_random_u32_fn next, void *rng_state, struct bj_error **error)
Create a builder that carves maze with algorithm.
A maze generation algorithm.
Everything a build step is given to work with.
static uint32_t bj_pcg32_generator(void *state)
Adapter for distribution API (void* state).
Definition random.h:185

bj_create_maze_builder takes one of these by value, so a description assembled at the call site needs no name and no lifetime.

Only step is required. Leave setup and teardown NULL for an algorithm with nothing to remember between steps; supply both otherwise.

Examples
maze.c.

Definition at line 332 of file maze_builder.h.

Collaboration diagram for bj_maze_algorithm:
Data Fields
bj_maze_setup_fn setup Prepares the state, or NULL.
bj_maze_step_fn step Does one step. Required.
bj_maze_teardown_fn teardown Releases the state, or NULL.

Macro Definition Documentation

◆ BJ_MAZE_EAST

#define BJ_MAZE_EAST   BJ_MAZE_DIR_EAST
Deprecated
Renamed to BJ_MAZE_DIR_EAST. Removed in 2.0.

Definition at line 120 of file maze.h.

◆ BJ_MAZE_NO_CELL

#define BJ_MAZE_NO_CELL   ((uint32_t)-1)

The answer when there is no cell.

An empty neighbour slot, a position outside the grid, a call that could not do what was asked: all of them come back as this. It is the largest value a cell index can hold, and a maze is refused if it would need that many cells, so it can never be mistaken for one.

Definition at line 92 of file maze.h.

◆ BJ_MAZE_NORTH

#define BJ_MAZE_NORTH   BJ_MAZE_DIR_NORTH
Deprecated
Renamed to BJ_MAZE_DIR_NORTH. Removed in 2.0.

Definition at line 114 of file maze.h.

◆ BJ_MAZE_SOUTH

#define BJ_MAZE_SOUTH   BJ_MAZE_DIR_SOUTH
Deprecated
Renamed to BJ_MAZE_DIR_SOUTH. Removed in 2.0.

Definition at line 118 of file maze.h.

◆ BJ_MAZE_WEST

#define BJ_MAZE_WEST   BJ_MAZE_DIR_WEST
Deprecated
Renamed to BJ_MAZE_DIR_WEST. Removed in 2.0.

Definition at line 116 of file maze.h.

Typedef Documentation

◆ bj_maze_setup_fn

typedef void *(* bj_maze_setup_fn) (const struct bj_maze_build_context *context, struct bj_error **error)

Prepares whatever an algorithm needs to remember between steps.

Called once by bj_create_maze_builder, before any step runs, and only when the algorithm declares one. Whatever it returns is handed back to every step as context->data, and to bj_maze_teardown_fn at the end.

The context is the one the steps will see, minus its data: the maze is there to size anything that scales with the cell count, and so is the engine.

Returning NULL aborts creation, so an algorithm that cannot get what it needs makes bj_create_maze_builder fail and report why — something a step could not do, since it runs too often to afford the error system.

Parameters
contextBuild context, with data still NULL. Never NULL.
errorError location, or NULL. Set one when returning NULL.
Returns
The algorithm's state, or NULL to abort creation.

Definition at line 257 of file maze_builder.h.

◆ bj_maze_step_fn

typedef bj_bool(* bj_maze_step_fn) (struct bj_maze_build_context *context)

One step of a maze generation algorithm.

Called repeatedly for as long as it asks to be. Each call should do a small, bounded amount of work — visit one cell, take one step of a walk — so that a caller stepping the builder by hand stays responsive.

context->data holds whatever bj_maze_setup_fn returned, already there on the very first call.

A call reports whether it did anything, rather than whether it is finished. Generation therefore ends on a call that finds nothing left and does nothing: the step that carves the last cell still reports having worked, and the one after it reports the end. That costs one extra call per generation and buys a caller the guarantee that a BJ_TRUE means the maze moved on and is worth looking at again.

It also fails in the right direction: a callback returning nothing in particular ends generation early instead of looping forever.

"Did anything" is not the same as "carved a passage". An algorithm that wanders before it commits — walking, backtracking, discarding a path — reports BJ_TRUE for those steps too. Only being out of work reports BJ_FALSE.

Parameters
contextBuild context. Never NULL.
Returns
BJ_TRUE if this call did something, BJ_FALSE if there was nothing left to do.

Definition at line 292 of file maze_builder.h.

◆ bj_maze_teardown_fn

typedef void(* bj_maze_teardown_fn) (void *data)

Releases what bj_maze_setup_fn produced.

Called once by bj_destroy_maze_builder, whether generation finished or was abandoned halfway, so an algorithm's state is never leaked and never freed twice. Whoever allocated it frees it: the builder itself never looks inside.

Parameters
dataWhatever the setup returned. Never NULL.

Definition at line 307 of file maze_builder.h.

Enumeration Type Documentation

◆ bj_maze_dir

The four neighbour slots of a cell on a square grid.

These name the slots of the orthogonal family, and only of it: a maze cut some other way numbers its slots to suit itself. Anything that takes a direction takes a slot number, so an algorithm free of compass points is free of the family too.

Opposites are two apart, which on a square grid makes dir ^ 2 the way back. Do not carry that over to another family: it holds because these four are in this order, not because it is a law of mazes.

Enumerator
BJ_MAZE_DIR_NORTH 

Towards the top of the grid.

BJ_MAZE_DIR_WEST 

Towards the left of the grid.

BJ_MAZE_DIR_SOUTH 

Towards the bottom of the grid.

BJ_MAZE_DIR_EAST 

Towards the right of the grid.

Definition at line 106 of file maze.h.

◆ bj_maze_mark

What an algorithm can record about a cell as it works.

The first three have a fixed meaning so that a renderer can rely on them whatever algorithm is running. The remaining bits, from BJ_MAZE_MARK_USER upwards, belong to the algorithm and mean whatever it decides.

Much of what one might want to show is already in the maze: a cell with no passage has not been reached yet. Marks are for what the maze cannot say — chiefly where the algorithm is, and what it is still undecided about.

Enumerator
BJ_MAZE_MARK_VISITED 

The algorithm is done with this cell.

BJ_MAZE_MARK_HEAD 

Where the algorithm is working now.

BJ_MAZE_MARK_PATH 

On the route currently under consideration.

BJ_MAZE_MARK_USER 

First bit an algorithm may use as it likes.

Definition at line 111 of file maze_builder.h.

Function Documentation

◆ bj_clear_maze_marks()

void bj_clear_maze_marks ( struct bj_maze_marks * marks)

Take every mark off every cell.

Parameters
marksMarks to clear, or NULL.

◆ bj_close_maze()

void bj_close_maze ( struct bj_maze * maze)
Deprecated
Renamed to bj_maze_close_all. Removed in 2.0.

◆ bj_close_maze_cell()

uint32_t bj_close_maze_cell ( struct bj_maze * maze,
uint32_t cell,
enum bj_maze_dir dir )

Put the wall back between cell and its neighbour through dir.

The mirror of bj_open_maze_cell in every way, closing both sides and reporting the neighbour it closed against. Wall-adding algorithms live on this: they start from a maze with everything open and build their way to one.

Parameters
mazeMaze to change, or NULL, which closes nothing.
cellCell to wall in.
dirSlot to close.
Returns
The neighbour now cut off, which an already closed slot returns unchanged, or BJ_MAZE_NO_CELL when the slot faces no cell.

◆ bj_create_maze_builder()

struct bj_maze_builder * bj_create_maze_builder ( struct bj_maze * maze,
struct bj_maze_algorithm algorithm,
struct bj_maze_marks * marks,
bj_random_u32_fn next,
void * rng_state,
struct bj_error ** error )

Create a builder that carves maze with algorithm.

The algorithm's own setup runs here, so an algorithm that cannot get what it needs makes this call fail rather than a later step.

algorithm arrives by value, so a description assembled at the call site needs no name. What it points at does not come along: maze and rng_state must stay alive and unchanged until the builder is destroyed.

Parameters
mazeMaze to carve. NULL fails with BJ_ERROR_INVALID_PARAMETER.
algorithmAlgorithm to run, from bj_maze_algorithm_btree or the like. Must carry a step.
marksWhere the algorithm records its progress, or NULL to have it record nothing. Must outlive the builder.
nextRNG callback, or NULL to draw from the global bj_rand engine.
rng_stateOpaque state for next; ignored when next is NULL.
errorError location, or NULL to ignore failures.
Returns
A new builder, or NULL on failure.

Fails with BJ_ERROR_INVALID_PARAMETER when maze or algorithm is unusable, with BJ_ERROR_INVALID_DOMAIN when algorithm names a family the algorithm does not carve, with BJ_ERROR_CANNOT_ALLOCATE when memory runs out, and with whatever the algorithm's setup reports.

Build steps themselves report nothing: they run once per cell, and the error system allocates. A step that cannot continue logs and ends generation, leaving the maze partly carved.

Examples
maze.c.

Referenced by setup().

◆ bj_create_maze_marks()

struct bj_maze_marks * bj_create_maze_marks ( const struct bj_maze * maze,
struct bj_error ** error )

Allocate marks for every cell of maze, all clear.

Parameters
mazeMaze to size the marks from. NULL fails with BJ_ERROR_INVALID_PARAMETER.
errorError location, or NULL to ignore failures.
Returns
New marks, or NULL on failure.
Examples
maze.c.

Referenced by setup().

◆ bj_create_maze_ortho2d()

struct bj_maze * bj_create_maze_ortho2d ( size_t width,
size_t height,
struct bj_error ** error )

Allocate a new orthogonal 2D maze, with every wall still standing.

The grid is width cells across and height cells down, numbered row by row, so the cell at row r and column c is r * width + c. bj_maze_ortho2d_cell does that arithmetic and checks the bounds, which is worth preferring: a maze does not carry its shape around, and a program doing the multiplication itself is one transposition away from reading the wrong cell in silence.

Parameters
widthNumber of cells in X axis
heightNumber of cells in Y axis
errorError location, or NULL to ignore failures.
Returns
A new bj_maze instance, or NULL on failure.

Fails with BJ_ERROR_INVALID_DOMAIN when either dimension is 0 or the cell count does not fit a 32-bit index, and with BJ_ERROR_CANNOT_ALLOCATE when memory runs out.

Examples
maze.c.

Referenced by setup().

◆ bj_destroy_maze()

void bj_destroy_maze ( struct bj_maze * maze)

Deletes a struct bj_maze object and releases associated memory.

Anything a program kept alongside the maze — arrays indexed by cell, marks, a builder — is its own to release; the maze knows of none of it.

Parameters
mazePointer to the struct bj_maze object to delete, or NULL.
Examples
maze.c.

Referenced by teardown().

◆ bj_destroy_maze_builder()

void bj_destroy_maze_builder ( struct bj_maze_builder * builder)

Destroy a builder and release the algorithm state it accumulated.

Safe to call at any point, finished or not. The maze itself is left untouched, in whatever state generation reached.

Parameters
builderBuilder to destroy, or NULL.
Examples
maze.c.

Referenced by teardown().

◆ bj_destroy_maze_marks()

void bj_destroy_maze_marks ( struct bj_maze_marks * marks)

Release marks.

Parameters
marksMarks to destroy, or NULL.
Examples
maze.c.

Referenced by teardown().

◆ bj_mark_maze_cell()

void bj_mark_maze_cell ( struct bj_maze_marks * marks,
uint32_t cell,
uint8_t bits )

Add marks to a cell.

Does nothing for NULL marks, so an algorithm records what it is doing without first asking whether anyone is watching.

Nothing clears BJ_MAZE_MARK_HEAD on your behalf: sweeping every cell between steps would cost more than a step, so an algorithm takes the mark off the cell it is leaving before putting it on the next. Left alone, old heads pile up and a renderer lights the whole maze.

Parameters
marksMarks to write to, or NULL.
cellCell to mark.
bitsbj_maze_mark bits to add.

◆ bj_maze_adjacent()

uint32_t bj_maze_adjacent ( const struct bj_maze * maze,
uint32_t cell,
enum bj_maze_dir dir )
Deprecated
Renamed to bj_maze_adjacent_cell. Removed in 2.0.

◆ bj_maze_adjacent_cell()

uint32_t bj_maze_adjacent_cell ( const struct bj_maze * maze,
uint32_t cell,
enum bj_maze_dir dir )

Find what sits in slot dir of cell, wall or no wall.

This is the shape of the grid, fixed when the maze was made and never changing afterwards. Whether you can get there is a separate question, for bj_maze_cell_is_open.

for(uint8_t dir = 0 ; dir < bj_maze_degree(maze) ; ++dir) {
if(!bj_maze_cell_is_open(maze, cell, dir)) {
continue;
}
const uint32_t next = bj_maze_adjacent_cell(maze, cell, dir);
/* ... walk on to next ... *&zwj;/
}
bj_bool bj_maze_cell_is_open(const struct bj_maze *maze, uint32_t cell, enum bj_maze_dir dir)
Tell whether cell has a passage through slot dir.
uint8_t bj_maze_degree(const struct bj_maze *maze)
How many neighbour slots each cell has.
uint32_t bj_maze_adjacent_cell(const struct bj_maze *maze, uint32_t cell, enum bj_maze_dir dir)
Find what sits in slot dir of cell, wall or no wall.
Parameters
mazeMaze to query, or NULL.
cellCell to query.
dirSlot to query.
Returns
The neighbour's index, or BJ_MAZE_NO_CELL when the slot is empty or the arguments are out of range.

◆ bj_maze_algorithm_aldous_broder()

struct bj_maze_algorithm bj_maze_algorithm_aldous_broder ( void )

The Aldous-Broder algorithm.

Pass the result straight to bj_create_maze_builder. Works on any family: it names no direction, only neighbours.

It wanders at random and carves the first time it reaches a cell, which makes it slow — most of its steps retread ground it already covered. What that buys is the rarest property of the lot: every maze the grid admits comes out just as often as every other.

Returns
The algorithm, ready to hand over.
Examples
maze.c.

Referenced by bj_maze_algorithm_aldous_broder().

◆ bj_maze_algorithm_backtracker()

struct bj_maze_algorithm bj_maze_algorithm_backtracker ( void )

The backtracker, known in the literature as the recursive backtracker.

Pass the result straight to bj_create_maze_builder. Works on any family: it names no direction, only neighbours.

Like bj_maze_algorithm_hunt_and_kill it is a walk that never retreads, and the two part company only over what to do at a dead end. Hunt-and-kill scans the grid for somewhere to resume; this one falls back one cell at a time along the way it came, until it finds a cell with somewhere left to go. Falling back off the cell it started from is what ends the generation.

The result is the most lopsided of the six, and the most deliberate looking: corridors longer and more winding than anything else here, and few dead ends.

Nothing here recurses, and nothing keeps a stack. Each cell records which of its slots faces the cell it was reached from, which is one byte and is all falling back needs; the cells a recursive version would be holding on its call stack are exactly the ones marked BJ_MAZE_MARK_PATH at that moment. Watching one run with marks shows that path grow and retreat, which no other algorithm here does.

Returns
The algorithm, ready to hand over.
Examples
maze.c.

Referenced by bj_maze_algorithm_backtracker().

◆ bj_maze_algorithm_btree()

struct bj_maze_algorithm bj_maze_algorithm_btree ( void )

The binary tree algorithm.

Pass the result straight to bj_create_maze_builder. Only works on orthogonal 2D mazes, since it names its directions.

It visits every cell in turn and links it north or east, drawn at random among whichever of the two exist. The result is the top row and the right column as two long open corridors, with every passage leaning towards that corner.

The cheapest algorithm of the lot, and the most biased: it remembers nothing but a cursor and never revisits a cell.

Returns
The algorithm, ready to hand over.
Examples
maze.c.

Referenced by bj_maze_algorithm_btree().

◆ bj_maze_algorithm_hunt_and_kill()

struct bj_maze_algorithm bj_maze_algorithm_hunt_and_kill ( void )

The hunt-and-kill algorithm.

Pass the result straight to bj_create_maze_builder. Works on any family: it names no direction, only neighbours.

A walk that never retreads. It carves on to a neighbour it has not stood on before, until every way out of the cell it reached leads back over its own ground; then it scans for a cell it has missed with one it has taken beside it, joins the two, and walks on from there.

Never retreading is what makes it so much quicker than bj_maze_algorithm_aldous_broder, which spends most of its steps crossing ground it already covered. It is also what costs it the even hand: steered by where it has been, it does not draw every maze of a grid equally often, and runs to long winding corridors with few dead ends — closer to something laid out on purpose than either of the even-handed two.

The hunt is stepped like anything else, one cell at a time, so a program watching with marks sees the scan sweep the grid rather than the walk simply reappearing elsewhere.

Returns
The algorithm, ready to hand over.
Examples
maze.c.

Referenced by bj_maze_algorithm_hunt_and_kill().

◆ bj_maze_algorithm_sidewinder()

struct bj_maze_algorithm bj_maze_algorithm_sidewinder ( void )

The sidewinder algorithm.

Pass the result straight to bj_create_maze_builder. Only works on orthogonal 2D mazes, since it names its directions.

It carves a run of cells eastward, then closes the run by carving once northward from one of its cells drawn at random. That leaves the top row one long corridor and nothing else lopsided.

Biased like the binary tree along one edge only, and cheap: it remembers a cursor and the run being built, whatever its length.

Returns
The algorithm, ready to hand over.
Examples
maze.c.

Referenced by bj_maze_algorithm_sidewinder().

◆ bj_maze_algorithm_wilson()

struct bj_maze_algorithm bj_maze_algorithm_wilson ( void )

Wilson's algorithm.

Pass the result straight to bj_create_maze_builder. Works on any family: it names no direction, only neighbours.

Draws its mazes as evenly as bj_maze_algorithm_aldous_broder does, and usually faster: instead of wandering until it happens to reach somewhere new, it walks from a cell outside the maze until it runs into the maze, drops whatever loops it made on the way, and carves what is left. Early walks are long, since there is little to run into; later ones are short.

It is the algorithm to watch with marks: the walk under consideration is marked as a path, and the cells a loop erases lose that mark without ever having been carved.

Returns
The algorithm, ready to hand over.
Examples
maze.c.

Referenced by bj_maze_algorithm_wilson().

◆ bj_maze_builder_completed()

bj_bool bj_maze_builder_completed ( const struct bj_maze_builder * builder)
Deprecated
Renamed to bj_maze_builder_is_complete. Removed in 2.0.

◆ bj_maze_builder_is_complete()

bj_bool bj_maze_builder_is_complete ( const struct bj_maze_builder * builder)

Tell whether generation has completed.

Parameters
builderBuilder to query, or NULL.
Returns
BJ_TRUE if the maze is complete, BJ_FALSE if not or for NULL.

◆ bj_maze_cell_count()

uint32_t bj_maze_cell_count ( const struct bj_maze * maze)

How many cells the maze has.

Cells run from 0 to one less than this, which is the length of any array a program keeps alongside the maze.

Parameters
mazeMaze to query, or NULL.
Returns
The number of cells, or 0.

◆ bj_maze_cell_is_open()

bj_bool bj_maze_cell_is_open ( const struct bj_maze * maze,
uint32_t cell,
enum bj_maze_dir dir )

Tell whether cell has a passage through slot dir.

Asking either side of a wall gives the same answer, so a program need only ask once. Walking a maze is this and bj_maze_adjacent_cell together: one says a way out exists, the other says where it goes.

Parameters
mazeMaze to query, or NULL.
cellCell to query.
dirSlot to query.
Returns
BJ_TRUE if a passage is open there.
Examples
maze.c.

Referenced by draw_maze().

◆ bj_maze_cell_marks()

uint8_t bj_maze_cell_marks ( const struct bj_maze_marks * marks,
uint32_t cell )

Read what is recorded about a cell.

Answers 0 for NULL marks and for a cell outside the maze they were made for, so a renderer can sweep every cell without asking questions first.

Parameters
marksMarks to read, or NULL.
cellCell to read.
Returns
The cell's bj_maze_mark bits, or 0.
Examples
maze.c.

Referenced by draw_maze().

◆ bj_maze_cell_opened()

bj_bool bj_maze_cell_opened ( const struct bj_maze * maze,
uint32_t cell,
enum bj_maze_dir dir )
Deprecated
Renamed to bj_maze_cell_is_open. Removed in 2.0.

◆ bj_maze_close_all()

void bj_maze_close_all ( struct bj_maze * maze)

Close every passage, leaving the maze as it came out of its constructor.

What a passage-carving algorithm wants to start from, and the way to hand a used maze back to bj_reset_maze_builder for another run. Carving a second time over a finished maze without this would add ways round to something that had exactly one route between any two cells.

Parameters
mazeMaze to close up, or NULL.
Examples
maze.c.

Referenced by regenerate().

◆ bj_maze_degree()

uint8_t bj_maze_degree ( const struct bj_maze * maze)

How many neighbour slots each cell has.

The same for every cell of a maze, and set by its family: four on a square grid. Slots run from 0 to one less than this, and a loop over them is how code reaches every way out of a cell without knowing what shape the maze is.

Parameters
mazeMaze to query, or NULL.
Returns
The number of slots per cell, or 0.

◆ bj_maze_open_all()

void bj_maze_open_all ( struct bj_maze * maze)

Open every passage there is, leaving one open field.

What a wall-adding algorithm wants to start from: it then closes its way to a maze, rather than carving one.

The outer boundary stays, and needs no keeping: cells at the edge have no neighbour to open towards, so there is nothing there to open. Only the walls between two real cells come down.

Parameters
mazeMaze to open up, or NULL.

◆ bj_maze_ortho2d_cell()

uint32_t bj_maze_ortho2d_cell ( const struct bj_maze * maze,
size_t row,
size_t col )

Find the cell at a position of an orthogonal 2D maze.

Rows count down from the top, columns across from the left, both from zero. The wider of the two axes comes second, which is worth reading twice: it is (row, col), not (x, y).

const uint32_t start = bj_maze_ortho2d_cell(maze, 0, 0);
Parameters
mazeMaze to look in, or NULL. Only a maze made by bj_create_maze_ortho2d has cells at a row and column.
rowRow of the cell, from 0 down.
colColumn of the cell, from 0 across.
Returns
The cell's index, or BJ_MAZE_NO_CELL when the position falls outside the grid, or the maze is not an orthogonal one or is NULL.
Examples
maze.c.

Referenced by draw_maze().

◆ bj_open_maze()

void bj_open_maze ( struct bj_maze * maze)
Deprecated
Renamed to bj_maze_open_all. Removed in 2.0.

◆ bj_open_maze_cell()

uint32_t bj_open_maze_cell ( struct bj_maze * maze,
uint32_t cell,
enum bj_maze_dir dir )

Carve a passage out of cell through slot dir.

Both sides open: the wall is as much the neighbour's as it is this cell's, so it comes down for both of them.

Opening a slot with no neighbour behind it does nothing and reports nothing carved. That is what keeps a passage a promise of somewhere to go, and what makes an outer wall impossible to knock through by accident. A maze wanting a way in and out is better served by leaving its boundary alone and having whatever draws it leave a gap.

Carving an already open passage is no error and changes nothing.

Parameters
mazeMaze to carve, or NULL, which carves nothing.
cellCell to carve out of.
dirSlot to carve through.
Returns
The neighbour now reachable, or BJ_MAZE_NO_CELL when nothing was carved.

◆ bj_reset_maze_builder()

bj_bool bj_reset_maze_builder ( struct bj_maze_builder * builder,
struct bj_error ** error )

Start the algorithm over.

Runs the algorithm's teardown and its setup again, which is all it takes to be back where bj_create_maze_builder left off, and cheaper than destroying the builder to make another. Running another algorithm means a new builder: the algorithm travels with it and is fixed at creation.

The maze is left exactly as it was. A builder does not own it, and running an algorithm over an already-carved maze is a legitimate thing to want. Starting a fresh maze means closing its passages first; carving a second time over the first would add loops to what should be a spanning tree.

On failure the builder survives but reports itself complete, so stepping it does nothing rather than reaching an algorithm whose state could not be prepared.

Parameters
builderBuilder to restart. NULL fails with BJ_ERROR_INVALID_PARAMETER.
errorError location, or NULL to ignore failures.
Returns
BJ_TRUE when the builder is ready to run again.
Examples
maze.c.

Referenced by regenerate().

◆ bj_run_maze_builder()

void bj_run_maze_builder ( struct bj_maze_builder * builder)

Step the builder until generation completes.

Parameters
builderBuilder to run, or NULL, which does nothing.

◆ bj_step_maze_builder()

bj_bool bj_step_maze_builder ( struct bj_maze_builder * builder)

Perform one step of generation.

Reads as an iterator: while(bj_step_maze_builder(builder)) runs the generation and stops on its own. A BJ_TRUE means the step did something and the maze is worth looking at again, which is what a caller drawing each frame wants to know. Generation ends on the first call that finds nothing to do; further calls keep saying so without reaching the algorithm.

Parameters
builderBuilder to step, or NULL, which returns BJ_FALSE.
Returns
BJ_TRUE if this step did something, BJ_FALSE if the maze is complete.
Examples
maze.c.

Referenced by step().

◆ bj_unmark_maze_cell()

void bj_unmark_maze_cell ( struct bj_maze_marks * marks,
uint32_t cell,
uint8_t bits )

Take marks off a cell.

Does nothing for NULL marks.

Parameters
marksMarks to write to, or NULL.
cellCell to unmark.
bitsbj_maze_mark bits to remove.