Banjo API 1.1.0-alpha
Low-level C99 game development API
Loading...
Searching...
No Matches
maze_builder.h File Reference
#include <banjo/api.h>
#include <banjo/maze.h>
#include <banjo/random.h>
Include dependency graph for maze_builder.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  bj_maze_build_context
struct  bj_maze_algorithm

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_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_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

Header file for Maze generation.

A builder carves passages into a maze made by maze.h, one step at a time. Nothing here decides what a maze looks like; it decides which walls come down.

One step at a time

Generation is driven by the caller rather than run to completion behind its back. bj_step_maze_builder does a single unit of work and returns, so a program can spread a generation over frames and draw the maze as it appears:

struct bj_pcg32 rng;
bj_seed_pcg32(&rng, 1234, 1);
struct bj_maze* maze = bj_create_maze_ortho2d(20, 12, 0);
while(bj_step_maze_builder(builder)) {
/* draw the maze, wait a frame, ... *&zwj;/
}
bj_destroy_maze_builder(builder);
bj_destroy_maze(maze);
struct bj_maze bj_maze
Definition api.h:363
struct bj_maze_builder bj_maze_builder
Definition api.h:364
bj_bool bj_step_maze_builder(struct bj_maze_builder *builder)
Perform one step of generation.
struct bj_maze_algorithm bj_maze_algorithm_btree(void)
The binary tree algorithm.
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.
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.
void bj_seed_pcg32(struct bj_pcg32 *generator, uint64_t seed, uint64_t seq)
Set the generator state from seed and sequence.
static uint32_t bj_pcg32_generator(void *state)
Adapter for distribution API (void* state).
Definition random.h:185
PCG32 generator state.
Definition random.h:117

bj_run_maze_builder is the shortcut for a caller that only wants the finished maze and has no interest in watching it happen.

A step reports whether it did something, not whether it is finished, and the difference matters. A generation ends on a step that finds nothing left to do, which costs one extra call and buys the guarantee that a BJ_TRUE means the maze moved on and is worth drawing again. It also fails in the useful direction: an algorithm that loses track of itself stops early rather than spinning forever.

Which algorithm

An algorithm is a bj_maze_algorithm — a setup, a step and a teardown, handed over together. The built-in ones and your own are the same kind of thing, so anything the library can run, your code can supply.

None of them takes any settings. The two that name directions could be pointed at another corner, but every pair gives the same maze turned or mirrored, which is the business of whatever transforms a finished grid rather than of the algorithm that carved it.

Six come with the library:

Algorithm Family Character
bj_maze_algorithm_btree orthogonal The cheapest, and the most lopsided
bj_maze_algorithm_sidewinder orthogonal Lopsided along one edge only
bj_maze_algorithm_aldous_broder any Even-handed, and slow about it
bj_maze_algorithm_wilson any Even-handed, usually quicker
bj_maze_algorithm_hunt_and_kill any Long winding corridors, quick, uneven
bj_maze_algorithm_backtracker any The longest, windingest corridors of all

The two that name directions only make sense on a grid that has them. The four that ask for neighbours and nothing else work on any family there is, or ever will be.

Where the randomness comes from

Passing NULL for the RNG callback draws from the global engine seeded by bj_srand, which is convenient but not reproducible: two mazes from the same seed only match if nothing else drew from that engine in between. Pass bj_pcg32_generator with your own bj_pcg32 whenever the same seed must give the same maze.

Watching it work

Hand bj_create_maze_builder a set of bj_maze_marks and the algorithm records what it is doing as it goes: which cells it has reached, where it is standing, what it is still weighing up. A program can then colour a generation in progress without knowing which algorithm is running. Hand it NULL instead and nothing is recorded, nothing is allocated, and every algorithm still runs the same.

Definition in file maze_builder.h.