Banjo API 1.1.0-alpha
Low-level C99 game development API
Loading...
Searching...
No Matches
maze.c
Go to the documentation of this file.
1
93#include <banjo/app.h>
94#include <banjo/bitmap.h>
95#include <banjo/draw.h>
96#include <banjo/event.h>
97#include <banjo/log.h>
98#include <banjo/main.h>
99#include <banjo/maze.h>
100#include <banjo/maze_builder.h>
101#include <banjo/pixel.h>
102#include <banjo/random.h>
103#include <banjo/system.h>
104#include <banjo/time.h>
105#include <banjo/window.h>
106
107#define WINDOW_W 800
108#define WINDOW_H 600
109
110// Every maze is a square grid of this many cells per side.
111#define MAZE_CELL_PER_SIDE 15
112
113// A cell is drawn this many pixels wide, plus the 1px band its walls live
114// in, which it shares with the next cell along.
115#define MAZE_PIXEL_PER_CELL 5
116#define MAZE_BMP_SIZE (MAZE_CELL_PER_SIDE * MAZE_PIXEL_PER_CELL + (MAZE_CELL_PER_SIDE + 1))
117
118#define MAZE_MARGIN 10
119#define LABEL_H 32
120#define LABEL_FONT_H 18
121
122// One build step runs per frame, so this is the speed of the animation:
123// MAZE_CELL_PER_SIDE^2 cells at this many per second.
124#define ANIMATION_HZ 30
125
127
128// Kept from the resize callback so the header can span the window.
129static int window_w = 0;
130
131// One entry per algorithm on show. Each gets its own grid, its own builder
132// and its own bitmap, so the six generations run side by side and
133// independently. Nothing here lives inside the maze: a maze holds cells and
134// passages, and everything else about them is the program's own.
135static struct {
136 const char* name;
137 struct bj_maze_algorithm (*algorithm)(void);
138 bj_maze* maze;
139 struct bj_maze_marks* marks; // What the algorithm is doing, for colour
140 bj_maze_builder* builder;
141 bj_bitmap* bitmap; // The maze drawn at 1:1, stretched on blit
142 bj_rect blit_dest;
143} mazes[] = {
144 {.name = "B-Tree", .algorithm = bj_maze_algorithm_btree},
145 {.name = "Sidewinder", .algorithm = bj_maze_algorithm_sidewinder},
146 {.name = "Aldous-Broder", .algorithm = bj_maze_algorithm_aldous_broder},
147 {.name = "Wilson", .algorithm = bj_maze_algorithm_wilson},
148 {.name = "Hunt-and-Kill", .algorithm = bj_maze_algorithm_hunt_and_kill},
149 {.name = "Backtracker", .algorithm = bj_maze_algorithm_backtracker},
151static const size_t n_mazes = sizeof(mazes) / sizeof(mazes[0]);
152
153// Turns a maze into pixels. This is the only place in the program that
154// decides what a maze looks like; the API decides nothing of the sort.
155static void draw_maze(
156 bj_bitmap* target,
157 const bj_maze* maze,
158 const struct bj_maze_marks* marks
159) {
160 bj_clear_bitmap(target);
161
162 // Walls have to read against the floor, so the cell an algorithm has
163 // reached cannot wear the wall's own grey: it takes the dark blue the
164 // corridors used to sit on. Ground never reached stays black.
165 const uint32_t wall_c = bj_pack_bitmap_rgb(target, 0xAA, 0xAA, 0xAA);
166 const uint32_t visited_c = bj_pack_bitmap_rgb(target, 0x33, 0x33, 0x55);
167 const uint32_t unseen_c = bj_pack_bitmap_rgb(target, 0x00, 0x00, 0x00);
168 const uint32_t head_c = bj_pack_bitmap_rgb(target, 0xFF, 0x30, 0x30);
169 const uint32_t path_c = bj_pack_bitmap_rgb(target, 0xF0, 0xD0, 0x30);
170
171 // Two passes. A cell's square covers the 1px band its walls are drawn
172 // in, which is what stops an unwalled side showing the background
173 // through; but that band is shared with the next cell, so filling and
174 // walling in one pass would rub out the wall the previous cell just
175 // drew.
176 //
177 // Pass 1: the floors.
178 for(size_t r = 0 ; r < MAZE_CELL_PER_SIDE ; ++r) {
179 for(size_t c = 0 ; c < MAZE_CELL_PER_SIDE ; ++c) {
180 const uint32_t cell = bj_maze_ortho2d_cell(maze, r, c);
181 const uint8_t state = bj_maze_cell_marks(marks, cell);
182
183 // No passage at all: solid rock, in the wall's own colour. The
184 // two marks the algorithm is holding win over it, since a cell
185 // is stood on before it is carved out of.
186 const bj_bool rock =
190 && !bj_maze_cell_is_open(maze, cell, BJ_MAZE_DIR_EAST);
191
192 const bj_rect fill = {
193 .x = (int16_t)((MAZE_PIXEL_PER_CELL + 1) * c),
194 .y = (int16_t)((MAZE_PIXEL_PER_CELL + 1) * r),
195 .w = MAZE_PIXEL_PER_CELL + 1,
196 .h = MAZE_PIXEL_PER_CELL + 1,
197 };
198
199 bj_draw_filled_rectangle(target, &fill,
200 (state & BJ_MAZE_MARK_HEAD) ? head_c
201 : (state & BJ_MAZE_MARK_PATH) ? path_c
202 : rock ? wall_c
203 : (state & BJ_MAZE_MARK_VISITED) ? visited_c
204 : unseen_c);
205 }
206 }
207
208 // Pass 2: the walls. A wall stands wherever a cell has no passage, which
209 // is the only question the maze is ever asked here. Both sides of a wall
210 // agree, so drawing it twice is harmless.
211 for(size_t r = 0 ; r < MAZE_CELL_PER_SIDE ; ++r) {
212 for(size_t c = 0 ; c < MAZE_CELL_PER_SIDE ; ++c) {
213 const uint32_t cell = bj_maze_ortho2d_cell(maze, r, c);
214
215 int x1 = (MAZE_PIXEL_PER_CELL + 1) * c;
216 int y1 = (MAZE_PIXEL_PER_CELL + 1) * r;
217 int w = MAZE_PIXEL_PER_CELL + 1;
218 int x2 = x1 + w;
219 int y2 = y1 + w;
220
221 if(!bj_maze_cell_is_open(maze, cell, BJ_MAZE_DIR_NORTH)) {
222 bj_draw_line(target, x1, y1, x2, y1, wall_c);
223 }
224 if(!bj_maze_cell_is_open(maze, cell, BJ_MAZE_DIR_WEST)) {
225 bj_draw_line(target, x1, y1, x1, y2, wall_c);
226 }
227 if(!bj_maze_cell_is_open(maze, cell, BJ_MAZE_DIR_SOUTH)) {
228 bj_draw_line(target, x1, y2, x2, y2, wall_c);
229 }
230 if(!bj_maze_cell_is_open(maze, cell, BJ_MAZE_DIR_EAST)) {
231 bj_draw_line(target, x2, y1, x2, y2, wall_c);
232 }
233 }
234 }
235}
236
237static void on_draw(
238 struct bj_window* w,
239 struct bj_render_target* target,
240 const struct bj_rect* dirty,
241 void* user_data
242) {
243 (void)w; (void)dirty; (void)user_data;
244 bj_bitmap* render_target = bj_render_target_bitmap(target);
245
246 const uint32_t label_color = bj_pack_bitmap_rgb(render_target, 0xDD, 0xDD, 0xDD);
247
248 // The layout keeps a band of LABEL_H at the top of the window for this.
249 const bj_rect header_area = {
250 .x = 2 * MAZE_MARGIN,
251 .y = MAZE_MARGIN,
252 .w = (uint16_t)(window_w - 4 * MAZE_MARGIN),
253 .h = LABEL_H,
254 };
255 bj_draw_text(render_target, LABEL_FONT_H, header_area,
257 label_color, "SPACE: generate again ESC: quit");
258
259 for(size_t m = 0 ; m < n_mazes ; ++m) {
260 bj_blit_bitmap_stretched(mazes[m].bitmap, 0, render_target, &mazes[m].blit_dest, BJ_BLIT_OP_COPY);
261
262 // The layout leaves LABEL_H pixels free under each maze; the name
263 // goes there, centred on the maze it belongs to.
264 const bj_rect label_area = {
265 .x = mazes[m].blit_dest.x,
266 .y = (int16_t)(mazes[m].blit_dest.y + mazes[m].blit_dest.h),
267 .w = mazes[m].blit_dest.w,
268 .h = LABEL_H,
269 };
270 bj_draw_text(render_target, LABEL_FONT_H, label_area,
272 label_color, mazes[m].name);
273 }
274}
275
276// Lays maze n out in a grid filling a win_w by win_h window, under a band
277// of LABEL_H left free at the top for the instructions. Deliberately terse:
278// it is window arithmetic, not the point of this example.
279static struct bj_rect grid_rect_place(int n, int win_w, int win_h) {
280 struct bj_rect out = {0, 0, 0, 0};
281 if (n_mazes == 0 || n < 0 || (size_t)n >= n_mazes) return out;
282 int iw = win_w - 4 * MAZE_MARGIN, ih = win_h - 4 * MAZE_MARGIN - LABEL_H, cols = 1, s = 0;
283 for (int c = 1; c <= (int)n_mazes; c++) {
284 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;
285 if (cs > s) { s = cs; cols = c; }
286 }
287 int rows = ((int)n_mazes + cols - 1) / cols, row = n / cols, col = n % cols;
288 int iir = row == rows - 1 ? (int)n_mazes - row * cols : cols;
289 int rw = iir * s + (iir - 1) * MAZE_MARGIN, bh = rows * (s + LABEL_H) + (rows - 1) * MAZE_MARGIN;
290 out.x = 2 * MAZE_MARGIN + (iw - rw) / 2 + col * (s + MAZE_MARGIN);
291 out.y = 2 * MAZE_MARGIN + LABEL_H + (ih - bh) / 2 + row * (s + LABEL_H + MAZE_MARGIN);
292 out.w = s; out.h = s;
293 return out;
294}
295
296// Banjo calls this once when the callback is registered, then on every
297// resize, so it is the only place the layout is computed.
298static void on_resize(
299 struct bj_window* w,
300 int width,
301 int height,
302 void* user_data
303) {
304 (void)w; (void)user_data;
305
306 window_w = width;
307
308 for(size_t m = 0 ; m < n_mazes ; ++m) {
309 mazes[m].blit_dest = grid_rect_place((int)m, width, height);
310 }
311}
312
313// SPACE lands here. Resetting a builder rewinds the algorithm and nothing
314// else: a builder does not own its maze, so closing the passages back up is
315// this program's job. Skipping it would carve a second maze over the first
316// and leave loops in what should be a spanning tree.
317static void regenerate(void) {
318 for(size_t m = 0 ; m < n_mazes ; ++m) {
319 bj_maze_close_all(mazes[m].maze);
320 bj_reset_maze_builder(mazes[m].builder, 0);
321 draw_maze(mazes[m].bitmap, mazes[m].maze, mazes[m].marks);
322 }
324}
325
326static void on_key(
327 struct bj_window* w,
328 const struct bj_key_event* event,
329 void* user_data
330) {
331 if(event->action == BJ_EVENT_ACTION_PRESS && event->key == BJ_KEY_SPACE) {
332 regenerate();
333 }
334 bj_close_on_escape(w, event, user_data);
335}
336
337static void* setup(struct bj_app* app, void* init_data) {
338 (void)init_data;
339
340 if (!bj_begin(BJ_VIDEO_SYSTEM, 0)) {
341 bj_quit_app(app, 1);
342 return 0;
343 }
344
346
347 // The builders draw from the global engine, so seeding it once here is
348 // what makes every run differ.
349 bj_srand((unsigned int)bj_get_time());
350
351 for(size_t m = 0 ; m < n_mazes ; ++m) {
353 // The marks are the caller's: the builder only writes through them,
354 // and this program is the one that wants to see them.
355 mazes[m].marks = bj_create_maze_marks(mazes[m].maze, 0);
356 mazes[m].builder = bj_create_maze_builder(mazes[m].maze, mazes[m].algorithm(),
357 mazes[m].marks, 0, 0, 0);
359 const uint32_t clear_color = bj_pack_bitmap_rgb(mazes[m].bitmap, 0x33, 0x33, 0x55);
360 bj_set_bitmap_clear_color(mazes[m].bitmap, clear_color);
361 }
362
363 window = bj_create_window("Maze Generation", 100, 100, WINDOW_W, WINDOW_H,
365
368 // Registering fires one immediate call, which does the initial layout.
370 return 0;
371}
372
373static void step(struct bj_app* app, struct bj_tick_info tick, void* user_data) {
374 (void)tick;
375 (void)user_data;
376
377 // One step per maze per frame. A step reports whether it did anything,
378 // so a maze that is finished costs a call and no redraw, and the four
379 // generations are free to end at different times.
380 for(size_t m = 0 ; m < n_mazes ; ++m) {
381 if(bj_step_maze_builder(mazes[m].builder)) {
382 draw_maze(mazes[m].bitmap, mazes[m].maze, mazes[m].marks);
384 }
385 }
386
388
390 bj_quit_app(app, 0);
391 }
392}
393
394static void teardown(struct bj_app* app, void* user_data) {
395 (void)user_data;
396
397 for(size_t m = 0 ; m < n_mazes ; ++m) {
398 bj_destroy_maze_builder(mazes[m].builder);
400 bj_destroy_maze(mazes[m].maze);
401 bj_destroy_bitmap(mazes[m].bitmap);
402 }
403
405 bj_end();
406}
407
408int main(int argc, char* argv[]) {
409 (void)argc; (void)argv;
410 return bj_run_app(setup, step, 0, teardown, 0);
411}
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
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.