libdrunkard by jabb

A Drunk Introduction

If you're looking to procedurally generate 2D maps, libdrunkard may be what you're looking for. This C library uses a fine tuned drunkard's walk alogirithm (see: http://en.wikipedia.org/wiki/Random_walk). Basically, you'll have a walker (or a drunk, as this library calls it) who walks around the map carving tunnels and various other structures.

Here are some good examples of what you can create (quite simply too! see examples/screen_shotter):

Compiling Drunkard

On most systems, you can simply do cmake . && make && make install to get the library working on your computer. The library itself is very small, ~62kb with debug symbols.

If libdrunkard fails to compile on your system, feel free to contact me at my GitHub: @jabb.

Using Drunkard

A Brief Example

In order to use libdrunkard, all you need to do is include the header file <dunkard.h> and link against the library by passing -ldrunkard to GCC, or some other compiler. After that you need to have your map already defined and then you can create your drunk. The map needs to be an array or multidimensional array of unsigned numbers, if multidimensional, height must be indexed first, like below:

unsigned map[MAP_HEIGHT][MAP_WIDTH] = {{0}};
/* Create the drunk. */
struct drunkard *drunk = drunkard_create((void *)map, MAP_WIDTH, MAP_HEIGHT);

/* Carve out a random map. */
/* ... */

/* Destroy the drunk. */
drunkard_destroy(drunk);

Some technical notes:

libdrunkard uses it's own internal random number generator (CMWC) which is seeded automatically. You can get the current seed with drunkard_get_seed and set it manually with drunkard_seed.
libdrunkard recognizes numbers passing a certain threshold as open (walkable) tiles. This threshold can be set manually with drunkard_set_opened_threshold. The default is 1, so only a tile that has the value of 0 can't be walked upon.
libdrunkard keeps a list of tiles that have been opened and tiles that might be opened after a flush, the latter are called marks. "Marking" tiles is the preferable way to set tiles during a carving process, that way any tiles that open up don't confuse the drunkard into thinking he's found the main tunnel system. There are various marking functions, but only one way to flush them: drunkard_flush_marks. Flush only when you're absolutely sure you've connected with the rest of your walkable area, or you know you can get back to the disconnected area.
libdrunkard's marks tiles only relative to the current position and target of the drunk. When you're carving, at some point you should always target a random open tile and head towards it. There are always exceptions of course, but this is a good rule so you can be sure your drunk connects to a walkable area.
libdrunkard's main stepping function uses a weight to calculate how stumbly the drunk will be. The weight is on a scale from 0.0 to 1.0. A value of 0.0 means the drunk will move directly away from his target, a value of 1.0 will mean directory towards, and a value of 0.5 means he'll just randomly walk around. I like values between 0.6 and 0.9 to be sure the drunk reaches his target.

Function Documentation

Drunk Creation/Destruction

struct drunkard *drunkard_create(unsigned *tiles, unsigned width, unsigned height);
void drunkard_destroy(struct drunkard *drunk);

In order to use the drunk, you have to create him. He takes a pointer to an array of unsigned integers. These integers will mostly likely be key-lookups to table of your real tiles. drunkard_create returns NULL only if there is no memory left. After you're done, be sure to destroy it, freeing any resources.

Core Functions

bool drunkard_is_opened(struct drunkard *drunk, int x, int y);
void drunkard_set_open_threshold(struct drunkard *drunk, unsigned threshold);
void drunkard_mark(struct drunkard *drunk, int x, int y, unsigned tile);
void drunkard_flush_marks(struct drunkard *drunk);
void drunkard_set_border(struct drunkard *drunk, bool tf);

drunkard_is_opened checks the tile at x, y and returns true if it is opened (walkable).

drunkard_set_open_threshold sets the threshold for open tiles. Anything greater than or equal to this number are considered by the drunk walkable.

drunkard_mark marks a tile. If the tile is an open one (walkable), it is added to the list of marked tiles. If the tile is closed (unwalkable), it is removed from the list of open tiles and list marked tiles.

drunkard_flush_marks flushes all the marked tiles to the list of open tiles. The marked list is then cleared.

drunkard_set_border if set to true, pads the generator so it doesn't touch the outer walls.

Querying Functions

unsigned drunkard_count_opened(struct drunkard *drunk);
double drunkard_percent_opened(struct drunkard *drunk);
void drunkard_random_opened(struct drunkard *drunk, unsigned *x, unsigned *y);

int drunkard_get_x(struct drunkard *drunk);
int drunkard_get_y(struct drunkard *drunk);
int drunkard_get_target_x(struct drunkard *drunk);
int drunkard_get_target_y(struct drunkard *drunk);
int drunkard_get_dx_to_target(struct drunkard *drunk);
int drunkard_get_dy_to_target(struct drunkard *drunk);

drunkard_count_opened returns the number of opened tiles on the map. (Doesn't include marked.)

drunkard_percent_opened returns the percent of the tiles opened on the map. Half the map opened would be 0.5.

drunkard_random_opened sets x and y to a random opened point on the map. (Doesn't include marked.)

The rest of the functions should be self explanatory.

Random Number Generation

unsigned drunkard_get_seed(struct drunkard *drunk);
void drunkard_seed(struct drunkard *drunk, unsigned s);
double drunkard_rng_uniform(struct drunkard *drunk);
double drunkard_rng_under(struct drunkard *drunk, unsigned limit);
int drunkard_rng_range(struct drunkard *drunk, int low, int high);
bool drunkard_rng_chance(struct drunkard *drunk, double d);

drunkard_get_seed returns the current seed.

drunkard_seed sets the current seed.

drunkard_rng_uniform returns a double in the range [0, 1).

drunkard_rng_under returns a double in the range [0, limit).

drunkard_rng_range returns an int in the range [low, high].

drunkard_rng_chance returns true d percent of the time.

Starting/Targeting Functions

void drunkard_start_fixed(struct drunkard *drunk, int x, int y);
void drunkard_start_random(struct drunkard *drunk);
void drunkard_start_random_west(struct drunkard *drunk);
void drunkard_start_random_east(struct drunkard *drunk);
void drunkard_start_random_north(struct drunkard *drunk);
void drunkard_start_random_south(struct drunkard *drunk);
void drunkard_start_random_west_edge(struct drunkard *drunk);
void drunkard_start_random_east_edge(struct drunkard *drunk);
void drunkard_start_random_north_edge(struct drunkard *drunk);
void drunkard_start_random_south_edge(struct drunkard *drunk);
void drunkard_start_random_westeast_edge(struct drunkard *drunk);
void drunkard_start_random_northsouth_edge(struct drunkard *drunk);
void drunkard_start_random_edge(struct drunkard *drunk);
void drunkard_start_random_opened(struct drunkard *drunk);

void drunkard_target_fixed(struct drunkard *drunk, int x, int y);
void drunkard_target_random_west_edge(struct drunkard *drunk);
void drunkard_target_random_east_edge(struct drunkard *drunk);
void drunkard_target_random_north_edge(struct drunkard *drunk);
void drunkard_target_random_south_edge(struct drunkard *drunk);
void drunkard_target_random_westeast_edge(struct drunkard *drunk);
void drunkard_target_random_northsouth_edge(struct drunkard *drunk);
void drunkard_target_random_edge(struct drunkard *drunk);
void drunkard_target_random_opened(struct drunkard *drunk);

drunkard_start_* functions set the x, y location of the drunk. drunkard_start_random_west sets the drunk's x, y location to a random location on the west side of the map (x >= WIDTH/2). *_edge functions are on the outermost edge of the map.

drunkard_target_* functions behave exactly like the drunkard_start_* functions, except the set the drunk's target location. Note: drunkard_target_random_opened is probably the most important since you always want to try to connect to the rest of your carved area.

Marking Functions

void drunkard_mark_all(struct drunkard *drunk, unsigned tile);
void drunkard_mark_1(struct drunkard *drunk, unsigned tile);
void drunkard_mark_plus(struct drunkard *drunk, unsigned tile);
void drunkard_mark_x(struct drunkard *drunk, unsigned tile);
void drunkard_mark_rect(struct drunkard *drunk, int hw, int hh, unsigned tile);
void drunkard_mark_circle(struct drunkard *drunk, int r, unsigned tile);

drunkard_mark_all marks every tile on the map. The locations on the map are set to tile.

drunkard_mark_1 marks the tile the drunk is standing on. The location on the map are set to tile.

drunkard_mark_plus marks a plus sign at the drunk's location. A plus sign is the current tile the drunk is standing on and four additional tiles in each cardinal direction from the origin. The locations on the map are set to tile.

drunkard_mark_x marks an X at the drunk's location. An X is the current tile the drunk is standing on and four addition tiles in each intermediate direction from the origin. The locations on the map are set to tile. The locations on the map are set to tile.

drunk_mark_rect marks a rectangle, where the center is at the drunk's location. It's important to note that the integers passed are half the width and height. So passing 3, 3 results in a 7x7 rectangle. The locations on the map are set to tile.

drunk_mark_circle marks a circle, where the center is at the drunk's location. The locations on the map are set to tile.

Stepping Functions

void drunkard_step_by(struct drunkard *drunk, int dx, int dy);
void drunkard_step_random(struct drunkard *drunk);
void drunkard_step_to_target(struct drunkard *drunk, double weight);

void drunkard_line_path_to_target(struct drunkard *drunk);
void drunkard_tunnel_path_to_target(struct drunkard *drunk);
bool drunkard_walk_path(struct drunkard *drunk);

When the drunk has a starting location and a target, he needs a way to get there. Stepping functions help. There are even pathing functions to plan out a very specific path to the target. All the stepping only occurs in four directions, six and eight-directional support is planned.

drunkard_step_by has the drunk step by delta x and delta y values.

drunkard_step_random just steps randomly in four directions.

drunkard_step_to_target a weighted step towards the target. Only moves in four directions.

Pathing functions:

drunkard_line_path_to_target plans a straight line to the target.

drunkard_tunnel_path_to_target the classic corridor. The choice between going horizontal or vertical first is random (50/50 chance).

drunkard_walk_path walks along the planned path. Returns false when the drunk is at the end, or in other words: on the target.

Checking Functions

bool drunkard_is_on_opened(struct drunkard *drunk);
bool drunkard_is_opened_on_rect(struct drunkard *drunk, unsigned hw, unsigned hh);
bool drunkard_is_opened_on_circle(struct drunkard *drunk, unsigned r);
bool drunkard_is_on_target(struct drunkard *drunk);
bool drunkard_is_on_fixed(struct drunkard *drunk, int x, int y);
bool drunkard_is_on_fixed_x(struct drunkard *drunk, int x);
bool drunkard_is_on_fixed_y(struct drunkard *drunk, int y);

These are good for breaking out of loops or checking an area to see if it's clear before building on it.

drunkard_is_on_opened returns true if the drunk is standing on an open tile (walkable).

drunkard_is_opened_on_rect returns true if any of the tiles in a rectangle area around the drunk are open.

drunkard_is_opened_on_circle return true if any of the tiles on a circle area around the drunk are open.

drunkard_is_on_target returns true when the drunkard's x, y location is equal to the drunk's target x, target y location.

drunkard_is_on_fixed returns true when the drunkard's x, y location is equal to the passed location.

drunkard_is_on_fixed_x returns true when the drunkard's x location is equal to the passed x location.

drunkard_is_on_fixed_y returns true when the drunkard's y location is equal to the passed y location.