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

Tutorial: Generate six mazes side by side, one step per frame, and watch each algorithm work.

Tutorial: Generate six mazes side by side, one step per frame, and watch each algorithm work.This tutorial introduces the maze API: the representation in maze.h, which holds cells and the passages between them, and the builders in maze_builder.h, which carve those passages. The six built-in algorithms run at once on identical grids, so their habits show up next to each other.

What you'll learn

Prerequisites

You've worked through start.c (window + draw callback) and drawing_2d.c (drawing primitives into a bitmap).

Walkthrough

1. A maze is not a picture

bj_create_maze_ortho2d gives a grid of cells with every wall standing. It holds no pixels, no colours and no notion of size on screen — only which cells exist, which of them are neighbours, and which walls have come down. Everything you see here is this program's interpretation; draw_maze is the whole of it.

Cells are plain indices. This example keeps its per-maze state in a small table rather than inside the maze, which is the intended way to work: anything you want to remember about a cell is your own array, indexed by the cell.

2. One step per frame

A builder does not run the algorithm; it lets you run it. bj_step_maze_builder does one unit of work and returns BJ_TRUE if it did something, so the loop here spends one step per frame and redraws only what moved. ANIMATION_HZ is therefore the speed of the animation, and bj_run_maze_builder is what you'd call instead if you only wanted the finished maze.

The six builders are stepped independently and finish at their own pace: the binary tree is done in one pass over the cells, while Aldous-Broder wanders for a long time before it is through.

3. Marks are what the maze cannot say

Most of what you want to draw is already in the maze — a cell with no passage has not been reached yet. What the maze cannot tell you is where the algorithm is standing and what it is still undecided about, which is what bj_maze_marks are for.

This program creates them, hands them to the builder, and reads them back with bj_maze_cell_marks. The algorithm writes through them without knowing who is watching, and passing NULL instead would run exactly the same generation with nothing recorded. Watch Wilson: the yellow path is a walk it has not committed to, and it vanishes when the walk loops back on itself. Watch Hunt-and-Kill instead and the red cursor stops wandering and starts sweeping the grid row by row: that is its hunt looking for somewhere to resume. Backtracker uses the same yellow for the corridor it is currently down, which grows as it presses on and retreats cell by cell whenever it walls itself in.

4. Drawing takes two passes

A cell is MAZE_PIXEL_PER_CELL pixels wide plus a 1px band for its wall, and that band is shared with the next cell along. Filling and walling a cell at a time would rub out the wall its neighbour just drew, so draw_maze lays down every floor first and every wall second.

5. Starting over

SPACE regenerates. bj_reset_maze_builder puts the algorithm back to its beginning but deliberately leaves the maze alone — a builder does not own it. Closing it up with bj_maze_close_all is this program's job, and skipping it would carve a second maze over the first and leave loops in it.

#include <banjo/app.h>
#include <banjo/bitmap.h>
#include <banjo/draw.h>
#include <banjo/event.h>
#include <banjo/log.h>
#include <banjo/main.h>
#include <banjo/maze.h>
#include <banjo/pixel.h>
#include <banjo/random.h>
#include <banjo/system.h>
#include <banjo/time.h>
#include <banjo/window.h>
#define WINDOW_W 800
#define WINDOW_H 600
// Every maze is a square grid of this many cells per side.
#define MAZE_CELL_PER_SIDE 15
// A cell is drawn this many pixels wide, plus the 1px band its walls live
// in, which it shares with the next cell along.
#define MAZE_PIXEL_PER_CELL 5
#define MAZE_BMP_SIZE (MAZE_CELL_PER_SIDE * MAZE_PIXEL_PER_CELL + (MAZE_CELL_PER_SIDE + 1))
#define MAZE_MARGIN 10
#define LABEL_H 32
#define LABEL_FONT_H 18
// One build step runs per frame, so this is the speed of the animation:
// MAZE_CELL_PER_SIDE^2 cells at this many per second.
#define ANIMATION_HZ 30
// Kept from the resize callback so the header can span the window.
static int window_w = 0;
// One entry per algorithm on show. Each gets its own grid, its own builder
// and its own bitmap, so the six generations run side by side and
// independently. Nothing here lives inside the maze: a maze holds cells and
// passages, and everything else about them is the program's own.
static struct {
const char* name;
struct bj_maze_algorithm (*algorithm)(void);
bj_maze* maze;
struct bj_maze_marks* marks; // What the algorithm is doing, for colour
bj_maze_builder* builder;
bj_bitmap* bitmap; // The maze drawn at 1:1, stretched on blit
bj_rect blit_dest;
} mazes[] = {
{.name = "B-Tree", .algorithm = bj_maze_algorithm_btree},
{.name = "Sidewinder", .algorithm = bj_maze_algorithm_sidewinder},
{.name = "Aldous-Broder", .algorithm = bj_maze_algorithm_aldous_broder},
{.name = "Wilson", .algorithm = bj_maze_algorithm_wilson},
{.name = "Hunt-and-Kill", .algorithm = bj_maze_algorithm_hunt_and_kill},
{.name = "Backtracker", .algorithm = bj_maze_algorithm_backtracker},
};
static const size_t n_mazes = sizeof(mazes) / sizeof(mazes[0]);
// Turns a maze into pixels. This is the only place in the program that
// decides what a maze looks like; the API decides nothing of the sort.
static void draw_maze(
bj_bitmap* target,
const bj_maze* maze,
const struct bj_maze_marks* marks
) {
bj_clear_bitmap(target);
// Walls have to read against the floor, so the cell an algorithm has
// reached cannot wear the wall's own grey: it takes the dark blue the
// corridors used to sit on. Ground never reached stays black.
const uint32_t wall_c = bj_pack_bitmap_rgb(target, 0xAA, 0xAA, 0xAA);
const uint32_t visited_c = bj_pack_bitmap_rgb(target, 0x33, 0x33, 0x55);
const uint32_t unseen_c = bj_pack_bitmap_rgb(target, 0x00, 0x00, 0x00);
const uint32_t head_c = bj_pack_bitmap_rgb(target, 0xFF, 0x30, 0x30);
const uint32_t path_c = bj_pack_bitmap_rgb(target, 0xF0, 0xD0, 0x30);
// Two passes. A cell's square covers the 1px band its walls are drawn
// in, which is what stops an unwalled side showing the background
// through; but that band is shared with the next cell, so filling and
// walling in one pass would rub out the wall the previous cell just
// drew.
//
// Pass 1: the floors.
for(size_t r = 0 ; r < MAZE_CELL_PER_SIDE ; ++r) {
for(size_t c = 0 ; c < MAZE_CELL_PER_SIDE ; ++c) {
const uint32_t cell = bj_maze_ortho2d_cell(maze, r, c);
const uint8_t state = bj_maze_cell_marks(marks, cell);
// No passage at all: solid rock, in the wall's own colour. The
// two marks the algorithm is holding win over it, since a cell
// is stood on before it is carved out of.
const bj_bool rock =
const bj_rect fill = {
.x = (int16_t)((MAZE_PIXEL_PER_CELL + 1) * c),
.y = (int16_t)((MAZE_PIXEL_PER_CELL + 1) * r),
};
bj_draw_filled_rectangle(target, &fill,
(state & BJ_MAZE_MARK_HEAD) ? head_c
: (state & BJ_MAZE_MARK_PATH) ? path_c
: rock ? wall_c
: (state & BJ_MAZE_MARK_VISITED) ? visited_c
: unseen_c);
}
}
// Pass 2: the walls. A wall stands wherever a cell has no passage, which
// is the only question the maze is ever asked here. Both sides of a wall
// agree, so drawing it twice is harmless.
for(size_t r = 0 ; r < MAZE_CELL_PER_SIDE ; ++r) {
for(size_t c = 0 ; c < MAZE_CELL_PER_SIDE ; ++c) {
const uint32_t cell = bj_maze_ortho2d_cell(maze, r, c);
int x1 = (MAZE_PIXEL_PER_CELL + 1) * c;
int y1 = (MAZE_PIXEL_PER_CELL + 1) * r;
int w = MAZE_PIXEL_PER_CELL + 1;
int x2 = x1 + w;
int y2 = y1 + w;
bj_draw_line(target, x1, y1, x2, y1, wall_c);
}
bj_draw_line(target, x1, y1, x1, y2, wall_c);
}
bj_draw_line(target, x1, y2, x2, y2, wall_c);
}
bj_draw_line(target, x2, y1, x2, y2, wall_c);
}
}
}
}
static void on_draw(
struct bj_window* w,
struct bj_render_target* target,
const struct bj_rect* dirty,
void* user_data
) {
(void)w; (void)dirty; (void)user_data;
bj_bitmap* render_target = bj_render_target_bitmap(target);
const uint32_t label_color = bj_pack_bitmap_rgb(render_target, 0xDD, 0xDD, 0xDD);
// The layout keeps a band of LABEL_H at the top of the window for this.
const bj_rect header_area = {
.x = 2 * MAZE_MARGIN,
.w = (uint16_t)(window_w - 4 * MAZE_MARGIN),
.h = LABEL_H,
};
bj_draw_text(render_target, LABEL_FONT_H, header_area,
label_color, "SPACE: generate again ESC: quit");
for(size_t m = 0 ; m < n_mazes ; ++m) {
bj_blit_bitmap_stretched(mazes[m].bitmap, 0, render_target, &mazes[m].blit_dest, BJ_BLIT_OP_COPY);
// The layout leaves LABEL_H pixels free under each maze; the name
// goes there, centred on the maze it belongs to.
const bj_rect label_area = {
.x = mazes[m].blit_dest.x,
.y = (int16_t)(mazes[m].blit_dest.y + mazes[m].blit_dest.h),
.w = mazes[m].blit_dest.w,
.h = LABEL_H,
};
bj_draw_text(render_target, LABEL_FONT_H, label_area,
label_color, mazes[m].name);
}
}
// Lays maze n out in a grid filling a win_w by win_h window, under a band
// of LABEL_H left free at the top for the instructions. Deliberately terse:
// it is window arithmetic, not the point of this example.
static struct bj_rect grid_rect_place(int n, int win_w, int win_h) {
struct bj_rect out = {0, 0, 0, 0};
if (n_mazes == 0 || n < 0 || (size_t)n >= n_mazes) return out;
int iw = win_w - 4 * MAZE_MARGIN, ih = win_h - 4 * MAZE_MARGIN - LABEL_H, cols = 1, s = 0;
for (int c = 1; c <= (int)n_mazes; c++) {
int r = ((int)n_mazes + c - 1) / c, sw = (iw - (c - 1) * MAZE_MARGIN) / c, sh = (ih - (r - 1) * MAZE_MARGIN - r * LABEL_H) / r, cs = sw < sh ? sw : sh;
if (cs > s) { s = cs; cols = c; }
}
int rows = ((int)n_mazes + cols - 1) / cols, row = n / cols, col = n % cols;
int iir = row == rows - 1 ? (int)n_mazes - row * cols : cols;
int rw = iir * s + (iir - 1) * MAZE_MARGIN, bh = rows * (s + LABEL_H) + (rows - 1) * MAZE_MARGIN;
out.x = 2 * MAZE_MARGIN + (iw - rw) / 2 + col * (s + MAZE_MARGIN);
out.y = 2 * MAZE_MARGIN + LABEL_H + (ih - bh) / 2 + row * (s + LABEL_H + MAZE_MARGIN);
out.w = s; out.h = s;
return out;
}
// Banjo calls this once when the callback is registered, then on every
// resize, so it is the only place the layout is computed.
static void on_resize(
struct bj_window* w,
int width,
int height,
void* user_data
) {
(void)w; (void)user_data;
window_w = width;
for(size_t m = 0 ; m < n_mazes ; ++m) {
mazes[m].blit_dest = grid_rect_place((int)m, width, height);
}
}
// SPACE lands here. Resetting a builder rewinds the algorithm and nothing
// else: a builder does not own its maze, so closing the passages back up is
// this program's job. Skipping it would carve a second maze over the first
// and leave loops in what should be a spanning tree.
static void regenerate(void) {
for(size_t m = 0 ; m < n_mazes ; ++m) {
bj_reset_maze_builder(mazes[m].builder, 0);
draw_maze(mazes[m].bitmap, mazes[m].maze, mazes[m].marks);
}
}
static void on_key(
struct bj_window* w,
const struct bj_key_event* event,
void* user_data
) {
if(event->action == BJ_EVENT_ACTION_PRESS && event->key == BJ_KEY_SPACE) {
}
bj_close_on_escape(w, event, user_data);
}
static void* setup(struct bj_app* app, void* init_data) {
(void)init_data;
bj_quit_app(app, 1);
return 0;
}
// The builders draw from the global engine, so seeding it once here is
// what makes every run differ.
bj_srand((unsigned int)bj_get_time());
for(size_t m = 0 ; m < n_mazes ; ++m) {
// The marks are the caller's: the builder only writes through them,
// and this program is the one that wants to see them.
mazes[m].marks = bj_create_maze_marks(mazes[m].maze, 0);
mazes[m].builder = bj_create_maze_builder(mazes[m].maze, mazes[m].algorithm(),
mazes[m].marks, 0, 0, 0);
const uint32_t clear_color = bj_pack_bitmap_rgb(mazes[m].bitmap, 0x33, 0x33, 0x55);
bj_set_bitmap_clear_color(mazes[m].bitmap, clear_color);
}
window = bj_create_window("Maze Generation", 100, 100, WINDOW_W, WINDOW_H,
// Registering fires one immediate call, which does the initial layout.
return 0;
}
static void step(struct bj_app* app, struct bj_tick_info tick, void* user_data) {
(void)tick;
(void)user_data;
// One step per maze per frame. A step reports whether it did anything,
// so a maze that is finished costs a call and no redraw, and the four
// generations are free to end at different times.
for(size_t m = 0 ; m < n_mazes ; ++m) {
if(bj_step_maze_builder(mazes[m].builder)) {
draw_maze(mazes[m].bitmap, mazes[m].maze, mazes[m].marks);
}
}
bj_quit_app(app, 0);
}
}
static void teardown(struct bj_app* app, void* user_data) {
(void)user_data;
for(size_t m = 0 ; m < n_mazes ; ++m) {
}
bj_end();
}
int main(int argc, char* argv[]) {
(void)argc; (void)argv;
return bj_run_app(setup, step, 0, teardown, 0);
}
Application lifecycle: callback-driven setup, step, and teardown.
static void step(struct bj_app *app, struct bj_tick_info tick, void *user_data)
Definition audio_pcm.c:142
static void teardown(struct bj_app *app, void *user_data)
Definition audio_pcm.c:168
static void * setup(struct bj_app *app, void *init_data)
Definition audio_pcm.c:107
Header file for Bitmap type.
static void on_draw(struct bj_window *w, struct bj_render_target *target, const struct bj_rect *dirty, void *user_data)
Definition bitmap_blit.c:32
#define WINDOW_W
Definition bitmap_blit.c:21
bj_window * window
Definition bitmap_blit.c:24
#define WINDOW_H
Definition bitmap_blit.c:22
Header file for Bitmap drawing functions.
Sytem event management API.
int bj_run_app(bj_app_setup_fn setup, bj_app_step_fn step, bj_app_fixed_step_fn fixed_step, bj_app_teardown_fn teardown, void *init_data)
Drive the application lifecycle.
void bj_set_frame_rate(struct bj_app *app, int hz)
Cap the run loop to at most hz iterations per second.
void bj_quit_app(struct bj_app *app, int exit_code)
Signal the given application to exit on the next iteration.
Timing snapshot handed to the step and fixed-step callbacks.
Definition app.h:107
void bj_clear_bitmap(struct bj_bitmap *bitmap)
Fills the entire bitmap with the clear colour.
bj_bool bj_blit_bitmap_stretched(const struct bj_bitmap *src, const struct bj_rect *src_area, struct bj_bitmap *dst, const struct bj_rect *dst_area, enum bj_blit_op op)
Stretched bitmap blitting (nearest neighbor).
void bj_set_bitmap_clear_color(struct bj_bitmap *bitmap, uint32_t color)
Set the colour bj_clear_bitmap fills with.
uint32_t bj_pack_bitmap_rgb(struct bj_bitmap *bitmap, uint8_t red, uint8_t green, uint8_t blue)
Pack an (R, G, B) triple into the bitmap's native pixel format.
struct bj_bitmap * bj_create_bitmap(size_t width, size_t height, enum bj_pixel_mode mode, size_t stride)
Creates a new struct bj_bitmap with the specified width and height.
void bj_draw_text(struct bj_bitmap *dst, unsigned height, struct bj_rect area, bj_text_halign halign, bj_text_valign valign, uint32_t fg_native, const char *text)
Prints text in a foreground colour over a transparent background.
void bj_destroy_bitmap(struct bj_bitmap *bitmap)
Deletes a struct bj_bitmap object and releases associated memory.
@ BJ_BLIT_OP_COPY
Copy source to destination (fast path when formats match)
Definition bitmap.h:99
@ BJ_TEXT_HALIGN_CENTER
Center text horizontally within the area.
Definition bitmap.h:719
@ BJ_TEXT_VALIGN_CENTER
Center text vertically within the area.
Definition bitmap.h:728
struct bj_maze bj_maze
Definition api.h:363
struct bj_render_target bj_render_target
Definition api.h:369
uint32_t bj_bool
Boolean type used throughout the Banjo API.
Definition api.h:264
struct bj_bitmap bj_bitmap
Definition api.h:340
struct bj_maze_builder bj_maze_builder
Definition api.h:364
struct bj_window bj_window
Definition api.h:384
struct bj_rect bj_rect
Definition api.h:368
void bj_draw_filled_rectangle(struct bj_bitmap *bitmap, const struct bj_rect *area, uint32_t pixel)
Draws a filled rectangle in the given bitmap.
void bj_draw_line(struct bj_bitmap *bitmap, int x0, int y0, int x1, int y1, uint32_t pixel)
Draws a line of pixels in the given bitmap.
enum bj_event_action action
Action (press/release/repeat)
Definition event.h:456
enum bj_key key
Key identifier.
Definition event.h:454
void bj_dispatch_events(void)
Poll and dispatch all pending events.
void bj_close_on_escape(struct bj_window *window, const struct bj_key_event *event, void *user_data)
Handle the ESC key to close a window.
bj_key_callback_fn bj_set_key_callback(bj_key_callback_fn callback, void *user_data)
Set the global callback for keyboard key events.
@ BJ_KEY_SPACE
Spacebar key.
Definition event.h:182
@ BJ_EVENT_ACTION_PRESS
The key or button was pressed.
Definition event.h:395
Represent a keyboard key event.
Definition event.h:453
uint16_t w
Width in pixels.
Definition rect.h:36
uint16_t h
Height in pixels.
Definition rect.h:37
int16_t y
Y coordinate of the top-left corner (pixels, can be negative).
Definition rect.h:35
int16_t x
X coordinate of the top-left corner (pixels, can be negative).
Definition rect.h:34
Axis-aligned rectangle: a top-left corner plus a width and height.
Definition rect.h:33
void bj_maze_close_all(struct bj_maze *maze)
Close every passage, leaving the maze as it came out of its constructor.
struct bj_maze_algorithm bj_maze_algorithm_wilson(void)
Wilson's algorithm.
void bj_destroy_maze_builder(struct bj_maze_builder *builder)
Destroy a builder and release the algorithm state it accumulated.
bj_bool bj_step_maze_builder(struct bj_maze_builder *builder)
Perform one step of generation.
struct bj_maze_algorithm bj_maze_algorithm_backtracker(void)
The backtracker, known in the literature as the recursive backtracker.
bj_bool bj_reset_maze_builder(struct bj_maze_builder *builder, struct bj_error **error)
Start the algorithm over.
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.
struct bj_maze_algorithm bj_maze_algorithm_sidewinder(void)
The sidewinder algorithm.
struct bj_maze_algorithm bj_maze_algorithm_hunt_and_kill(void)
The hunt-and-kill algorithm.
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.
uint8_t bj_maze_cell_marks(const struct bj_maze_marks *marks, uint32_t cell)
Read what is recorded about a cell.
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.
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.
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_destroy_maze_marks(struct bj_maze_marks *marks)
Release marks.
struct bj_maze_algorithm bj_maze_algorithm_aldous_broder(void)
The Aldous-Broder algorithm.
@ BJ_MAZE_MARK_PATH
On the route currently under consideration.
@ BJ_MAZE_MARK_VISITED
The algorithm is done with this cell.
@ BJ_MAZE_MARK_HEAD
Where the algorithm is working now.
@ BJ_MAZE_DIR_NORTH
Towards the top of the grid.
Definition maze.h:107
@ BJ_MAZE_DIR_EAST
Towards the right of the grid.
Definition maze.h:110
@ BJ_MAZE_DIR_SOUTH
Towards the bottom of the grid.
Definition maze.h:109
@ BJ_MAZE_DIR_WEST
Towards the left of the grid.
Definition maze.h:108
A maze generation algorithm.
@ BJ_PIXEL_MODE_XRGB8888
32bpp RGB
Definition pixel.h:94
void bj_srand(unsigned int seed)
Seed the standard PRNG.
bj_bool bj_begin(int systems, struct bj_error **error)
Initialises the system.
void bj_end(void)
De-initialises the system.
@ BJ_VIDEO_SYSTEM
Definition system.h:81
uint64_t bj_get_time(void)
Get the current system time in seconds since the Unix epoch.
static void bj_invalidate_window(struct bj_window *window)
Mark the whole window as needing a repaint.
Definition window.h:513
bj_bool bj_window_should_close(struct bj_window *window)
Report whether a window's close flag is set.
struct bj_window * bj_create_window(const char *title, uint16_t x, uint16_t y, uint16_t width, uint16_t height, uint8_t flags, struct bj_error **error)
Create a window with the given attributes.
void bj_set_window_draw_callback(struct bj_window *window, bj_window_draw_fn fn, void *user_data)
Register the redraw callback for window.
struct bj_bitmap * bj_render_target_bitmap(struct bj_render_target *target)
Reach the software framebuffer behind a render target.
void bj_set_window_resize_callback(struct bj_window *window, bj_window_resize_fn fn, void *user_data)
Register the resize callback for window.
void bj_destroy_window(struct bj_window *window)
Destroy a window and release its resources.
@ BJ_WINDOW_FLAG_RESIZABLE
User may resize the window.
Definition window.h:196
Logging utility functions.
Portable main() replacement with platform-aware entry shim.
static void on_resize(struct bj_window *w, int width, int height, void *user_data)
Definition maze.c:298
static void regenerate(void)
Definition maze.c:317
#define LABEL_H
Definition maze.c:119
static int window_w
Definition maze.c:129
#define MAZE_MARGIN
Definition maze.c:118
#define ANIMATION_HZ
Definition maze.c:124
static struct bj_rect grid_rect_place(int n, int win_w, int win_h)
Definition maze.c:279
static void draw_maze(bj_bitmap *target, const bj_maze *maze, const struct bj_maze_marks *marks)
Definition maze.c:155
#define MAZE_BMP_SIZE
Definition maze.c:116
#define MAZE_PIXEL_PER_CELL
Definition maze.c:115
#define MAZE_CELL_PER_SIDE
Definition maze.c:111
static struct @056016103232074337222244202315226141072276235164 mazes[]
static void on_key(struct bj_window *w, const struct bj_key_event *event, void *user_data)
Definition maze.c:326
#define LABEL_FONT_H
Definition maze.c:120
static const size_t n_mazes
Definition maze.c:151
Header file for Maze representation.
Header file for Maze generation.
Header file for general pixel manipulation facilities.
Pseudo-random number generation API.
Header file for system interactions.
int main(void)
Header file for time manipulation utilities.
Header file for bj_window type.