Introduction to LevelMap

    LevelMap is a simple C library for generating small dungeons and
    similar levels for turn-based games. Makefiles are provided for
    OpenWatcom C and for the Gnu C Compiler.

    Features included in the library include:
    - Dimensions can be developer-set or random.
    - Generates both rooms and corridors.
    - Generates data for connected textures.

    Limitations of the library:
    - Levels can be no more than 256 blocks in total.
    - LevelMap doesn't handle the graphics, only the level data.
    - LevelMap doesn't generate level inhabitants or furniture.

    So far, LevelMap has been used in Star Cadre: Combat Class and
    Star Cadre: Team Command, a pair of science fiction squad combat
    games, and in The Chambers Beneath, a fantasy roguelike RPG. Squad
    combat games and role-playing games are the primary use case for
    this library.

Licence

    This library, its associated programs and utilities, and its
    documentation have been released into the public domain by its
    author Damian Gareth Walker.

How It Works

    A level map, of C type LevelMap or alternatively, struct levelmap,
    consists of the dimensions of the map, and a pointer to an array
    of bytes, each byte defining one location on the map. The function
    pointers in the structure approximate methods in object-oriented
    programming, and allow parameters to be set, the map to be
    generated, and the locations examined.

    The smallest unit on the map is the Block, corresponding to a
    single tile on a display, a location where one player character or
    monster might reside. There can be up to 256 of these on the map.

    Before generation, the developer can set various parameters, such
    as the map dimensions, the size and shape of chambers, and the
    presence or absence of doors.

    During generation, a unit called the Cell is used. A cell
    corresponds to a chamber or a section of corridor that might
    branch in any of the four cardinal directions. The number of cells
    varies according to the map dimensions. A 16x16 map will typically
    be split up into a grid of 3x3 cells, while a 28x9 map will be 6x2
    cells.

    First, the cells are connected to each other. The cell order is
    shuffled like cards in a deck, and each cell is connected to the
    next in the shuffled deck, by a path that might cross over other
    cells in between. This guarantees that all cells are reachable,
    and that there are no isolated cells or groups of cells on the
    map.

    Then the cells are randomly determined to be chambers or
    corridors. Any dead-end cell with only one way out is
    automatically deemed a chamber, in order that no dead-end
    corridors are created.

    With the arrangement of cells determined, the map is filled with
    wall, and then each cell is carved out of the solid wall creating
    open floor. Corridors are 1 block wide, branching off towards each
    connected adjacent cell. Chambers are square or rectangular, with
    connections to adjacent cells optionally sealed with a door.

    Once the arrangement of walls, doors and open floor is generated,
    large masses of wall between corridors and chambers and the edge
    of the map can be hollowed out with voids, if the developer
    desires.

    Levelmap can then create entrances around the edge of the map
    area, sealing them with a door if desired. The developer can do
    this multiple times to create multiple entrances around the edge.

    Finally, if the game is to show the map blocks as connected
    textures, the data for determining which connected variant tile is
    shown for each block can be calculated.

    At the end of the process, the map structure should among other
    things contain a pointer to the block data, each block represented
    by a byte whose bits are as follows:

	TTTTNWSE
	Bits 7, 6, 5 and 4 are the block type:
	    00: void
	    01: open (floor)
	    02: wall
	    03: door
	    higher values are for the developer to use.
	Bits 3, 2, 1 and 0 specify whether the block is connected to
	adjacent blocks in the four cardinal directions.

Binary Package Contents

    The LevelMap binary package for DOS contains the following
    directory structure and files:

    LEVELMAP\ is the main directory.
        BIN\ contains binaries.
	    DEMO.EXE is the demonstration program.
	DOC\ contains the documentation.
	    LEVELMAP.TXT is this document.
	INC\ contains the include files.
	    LEVELMAP.H is the only include file.
	LIB\ contains the library files.
	    LEVELMAP.LIB is the sole library.

Source Package Contents

    The LevelMap source package contains the following directory
    structure and files (DOS format shown):

    levelmap\ is the main directory.
        bin\ is the directory for binaries.
	doc\ contains the documentation.
	    levelmap.txt is this document.
	inc\ contains the include files.
	    levelmap.h is the sole include file.
	lib\ is the directory for the library files.
	obj\ is the directory for the compiled object files.
	src\ is the source code directory.
	    demo.c is the code for the demonstration program.
	    levelmap.c is the code for the library.
	makefile.gcc is the makefile for Gnu C.
	makefile.wcc is the makefile for OpenWatcom C.

Building a Project with LevelMap

    To use LevelMap's functions in your project, you need to do the
    following two things. Firstly, you need to include the
    "levelmap.h" header in your own project's source:

	#include "levelmap.h"

    You can copy this header into your project's header directory, but
    a better idea is to add LevelMap's include folder to your include
    path on compilation, like this:

	C:\PROJECT\> wcc project.c -I=\levelmap\inc

    This assumes that LevelMap is installed in a directory called
    \levelmap. When you link your object file into an executable, you
    need to link it also with the LEVELMAP.LIB file, like this:

	C:\PROJECT\> wcl project.obj \levelmap\lib\levelmap.lib

Rebuilding LevelMap

    You might want to rebuild LevelMap from its sources, particularly
    if you've made a customised version of it. Two makefiles are
    provided to simplify this process. In DOS, assuming you unpacked
    the source files into the \levelmap directory, you can build the
    project like this:

	C:\LEVELMAP\> wmake -f makefile.wcc

    This builds the library for the large menu model. If you want to
    build for other memory models, you need to edit the makefile,
    replacing occurrences of '-ml' with the compiler switch for
    another memory model, e.g. '-ms' for small.

    If you're building with gcc under Linux or Unix, you can build the
    project with the following command instead:

	$ make -f makefile.gcc

    In Unix-like operating systems, the library will be called
    liblevelmap.a, and is included in your own projects by linking
    that file with your own:

	$ ld project.o -L./levelmap/lib -llevelmap -o project

    This assumes your current working directory is your project's
    directory, and the levelmap source package is held within that in
    the levelmap directory.

Summary of Functions, Methods and Attributes

    typedef struct levelmap LevelMap;
    LevelMap *new_LevelMap (void);
    struct levelmap {
	int width;
	int height;
	unsigned char *blocks;
	void (*destroy) (LevelMap *map);
	int (*write) (LevelMap *map, FILE *output);
	int (*read) (LevelMap *map, FILE *input);
	int (*setwidth) (LevelMap *map, int width);
	int (*setheight) (LevelMap *map, int height);
	int (*setcorridor) (int chance);
	int (*setcombined) (int chance);
	int (*setcellsize) (int minimum);
	int (*setnatural) (int natural);
	int (*setdoors) (int doors);
	int (*setconnected) (int connected, int edges);
	int (*generate) (LevelMap *map);
	int (*entrance) (LevelMap *map, int direction);
	int (*openvoids) (LevelMap *map);
	int (*connecttextures) (LevelMap *map);
	int (*getblock) (LevelMap *map, int x, int y);
    }

new_LevelMap ()

    Declaration:
    LevelMap *new_LevelMap (void);

    Example:
    /* create a new levelmap */
    LevelMap *map;
    map = new_LevelMap ();
    /* ... do things with map ... */
    map->destroy (map);

    This creates a new level map. It will be blank, and have no
    blocks. The level map needs to be initialised and generated before
    the blocks can be examined. The function returns a pointer to the
    new level map, or NULL if it failed to create one.

destroy ()

    Declaration:
    void (*destroy) (LevelMap *map);

    Example:
    /* show the levelmap life cycle */
    LevelMap *map;
    map = new_LevelMap ();
    /* ... do things with map ... */
    map->destroy (map);

    This destroys a level map when it is no longer needed. An
    object-oriented syntax is used, as destroy () is a method of the
    LevelMap object.

write ()

    Declaration:
    int (*write) (LevelMap *map, FILE *output);

    Example:
    /* save a level map */
    LevelMap *map;
    FILE *fp;
    /* ... create and generate the level map ... */
    fp = fopen ("example.map", "wb");
    map->write (map, fp);
    fclose (fp);

    Writes the generated level map to an already open file. The method
    requires you to open the file and specify the file pointer, rather
    than taking a filename, as this allows you to combine map data in
    the same file as other game data. The method returns 1 if
    successful or 0 if not.

read ()

    Declaration:
    int (*read) (LevelMap *map, FILE *input);

    Example:
    /* load a level map */
    LevelMap *map;
    FILE *fp;
    map = new_LevelMap ();
    fp = fopen ("example.map", "rb");
    map->read (map, fp);
    fclose (fp);

    Reads a level map from an already open file. As with the write ()
    method, a file pointer is taken rather than a filename, so that
    maps can be loaded from an asset or game save file that might
    contain other related data. The method returns 1 if successful or
    0 if not.

setwidth () and setheight ();

    Declarations:
    int (*setwidth) (LevelMap *map, int width);
    int (*setheight) (LevelMap *map, int height);

    Example:
    /* generate a level map of precise dimensions */
    LevelMap *map;
    map = new_LevelMap ();
    map->setwidth (map, 16);
    map->setheight (map, 16);
    map->generate (map);
    /* ... do things with the map ... */
    map->destroy (map);

    Sets a width or height for the level map before generating it. If
    both are set, then the map is generated with exacly these
    dimensions. If only one of them is set, then the largest map is
    generated that does not exceed 256 blocks and retains the
    specified dimension; e.g. setting width to 17 would generate a
    17x15 map of 255 blocks.

    If neither dimension is set, then a map is generated of random
    dimensions, that comes as close to 256 blocks as possible. This
    could be any set of dimensions from 9x28, through 16x16, to 28x9
    blocks.

    The only way to generate a map that is not as large as possible is
    to set both dimensions to a smaller number, e.g. setting width and
    height to 9 for a 9x9 map.

    The method returns 1 if successful or 0 if not. It will fail if
    you set a dimension outside of the allowed values of 9..28, or if
    you try to set two dimensions that amount to more than 256 blocks.

setcorridor ()

    Declaration:
    int (*setcorridor) (int chance);

    Example:
    /* generate a map with only rooms, not corridors */
    LevelMap *map;
    map = new_LevelMap ();
    map->setcorridor (0);
    map->generate (map);
    /* ... use the map ... */
    map->destroy (map);

    Sets the percentage chance of each cell in the level being a
    corridor, rather than a chamber. The chance parameter must be an
    integer between 0 and 100. By default, 50% of cells in a map are
    corridors, with one caveat. The method returns 1 if successful or
    0 if not.

    When generating a map, the library does not create dead-end
    corridors. So if a cell has only one exit, it is automatically
    generated as a chamber. So even if you set the corridor chance to
    100%, there might still be the occasional chamber in your
    generated level map.

setcombined ()

    Declaration:
    int (*setcombined) (int chance);

    Example:
    /* ensure adjacent connected chambers are always combined. */
    LevelMap *map;
    map = new_LevelMap ();
    map->setcombined (100);
    map->generate (map);
    /* ... use the map ... */
    map->destroy (map);

    This controls the chance that two adjacent connected chambers are
    combined into one. Normally there is a 50% chance that two
    adjacent connected chambers are combined. Note that adjacent
    connected corridors are always joined up into a single long
    corridor, regardless of thiss setting. The method returns 1 if
    successful or 0 if not.

setcellsize ()

    Declaration:
    int (*setcellsize) (int minimum);

    Example:
    /* allow 1x1 chambers */
    LevelMap *map;
    map = new_LevelMap ();
    map->setcellsize (1);
    map->generate (map);
    /* ... use the map ... */
    map->destroy (map);

    This sets the minimum height and width of cells on the
    levelmap. Normally this is 2, to ensure that rooms look like rooms
    and not corridors. It should be set to a value between 1 and
    3. The method returns 1 if successful or 0 if not.

setnatural ()

    Declaration:
    int (*setnatural) (int natural);

    Example:
    /* generate naturalistic corners */
    LevelMap *map;
    map = new_LevelMap ();
    map->setnatural (1);
    map->generate (map);
    /* ... use the map ... */
    map->destroy (map);

    This activates a setting that generates maps for more naturalistic
    environments. Some corners in chambers and corridors become
    rounded by having the corners filled in with wall blocks. This is
    intended for places like forests and caves. A paramater of 1
    switches sets this option, 0 switches it off for 90-degree corners
    everywhere. The default is off.

setdoors ()

    Declaration:
    int (*setdoors) (int doors);

    Example:
    /* generate an open level without doors */
    LevelMap *map;
    map = new_LevelMap ();
    map->setnatural (1);
    map->generate (map);
    /* ... use the map ... */
    map->destroy (map);

    Enables or disables the generation of doors at chamber
    openings. The default is enabled. If disabled, the exits to
    chambers will be open.

setconnected ()

    Declaration:
    int (*setconnected) (int connected, int edges);

    Example:
    /* generate a map with walls connected to the map edge */
    LevelMap *map;
    map = new_LevelMap ();
    map->setconnected (0xc, 0xc);
    map->generate (map);
    /* ... use the map ... */
    map->destroy (map);

    This gives the developer some control over which blocks are
    connected to other blocks by the connecttextures()
    function. Connected textures are indications to a game's map
    display functionality, of whether each block has a visible
    connection to adjacent blocks in each direction, allowing things
    like continuous walls to be displayed without real-time
    calculations by the host game.

    Each of the parameters is a bit field of 16 bits, defining which
    of the block types connect: bit 0 represents the voids, bit 1 the
    open spaces, bit 2 walls, bit 3 doors. Higher order bits control
    other block types generated by the host game between calls to the
    generate() and connecttextures() functions.

    The "connected" parameter defines which of the blocks are
    connected to adjacent blocks of the same type. The "edges"
    parameter indicates which blocks are connected to the edge of the
    map.

    By default, all block types are connected to adjacent blocks of
    the same type. All blocks except walls and doors are additionally
    connected to the edge of the map. A quirk of walls and doors is
    that, if both have their "connected" bit set, they also connect to
    each other.

generate ()

    Declaration:
    int (*generate) (LevelMap *map);

    Example:
    /* simple random generation */
    LevelMap *map;
    map = new_LevelMap ();
    map->generate (map);
    /* ... use the map ... */
    map->destroy (map);

    This is the method that generates the level map, taking into
    account any parameters that you have set with the aforementioned
    methods. It returns 1 if successful or 0 if not.

    When generated, map->blocks will contain a pointer to the block
    bytes of the map. Bits 4 and 5 of each block byte represent the
    block type at that location. The valid values are:

	0x00 (0):  Void (see openvoids () below)
	0x10 (16): Open floor
	0x20 (32): Wall
	0x30 (48): Door

entrance ()

    Declaration:
    int (*entrance) (LevelMap *map, int direction);

    Example:
    /* attempt to open an entrance in one direction */
    LevelMap *map;
    map = new_LevelMap ();
    map->generate (map);
    while (! map->entrance (map, rand () % 4));
    /* ... use the map ... */
    map->destroy (map);

    This function, called after generation, opens up an entrance to
    the map on the edge specified by direction. The direction
    parameter is one of the following:

	0: east
	1: south
	2: west
	3: north

    The algorithm used to find a suitable place on the edge is very
    simple: a place must currently have a wall on the map edge, and an
    adjacent open block heading inwards. If no such place exists along
    that edge, the function returns 0 to indicate failure. Otherwise
    the function turns the chosen location into a door or a wall,
    according to the setdoors() setting, and returns 1 to indicate
    success.

openvoids ()

    Declaration:
    int (*openvoids) (LevelMap *map);

    Example:
    /* generate a map with open voids */
    LevelMap *map;
    map = new_LevelMap ();
    map->generate (map);
    map->openvoids (map);
    /* ... use the map ... */
    map->destroy (map);

    When first generated, corridors are padded with masses of wall
    blocks. This function will look for those, and change them into
    void blocks. Void blocks within and around a building might be
    represented as outdoor terrain, while void blocks in and around a
    space ship or space station might be represented as space.

connecttextures ()

    Declaration:
    int (*connecttextures) (LevelMap *map);

    Example:
    /* generate a map with connected textures */
    LevelMap *map;
    map = new_LevelMap ();
    map->generate (map);
    map->connecttextures (map);
    /* ... use the map ... */
    map->destroy (map);

    This fills in the map data with connections between the blocks,
    helping the host project to determine which precise block tiles to
    use in displaying the map. Connections are represented by the four
    least significant bits of each block byte:

	1: east
	2: south
	4: west
	8: north

    The setconnected () method specifies which blocks are connected to
    one another. By default, all blocks connect to blocks of the same
    type.

getblock ()

    Declaration:
    int (*getblock) (LevelMap *map, int x, int y);

    Example:
    LevelMap *map;
    map = new_LevelMap ();
    map->generate (map);
    for (y = 0; y < map->height) {
        for (x = 0; x < map->width)
	    printf ("%1d", map->getblock (map, x, y));
	printf ("\n");
    }
    map->destroy (map);

    Returns the block byte at a particular x/y coordinate of the level
    map. While these blocks can be accessed directly in the
    map->blocks array, the getblock () method has bounds checking to
    ensure that the coordinates are within the map's dimensions (and
    that the map has been generated). getblock () will return 0, for a
    void, if there is no block at (x, y).

History of LevelMap

    LevelMap was developed from the dungeon level generation of
    Ossuary, a simple Roguelike originally developed for the 16kb
    Sinclair ZX Spectrum and later ported to MS-DOS. Ossuary's maps
    were of fixed dimensions, 16x16 blocks, with cells of 4x4 blocks
    in a grid of 9x9.

    To this were added the features of LevelMap: variable dimensions,
    variable width cells, doors, voids and connected textures. At the
    time of writing, LevelMap has been used in the Star Cadre games
    and The Chambers Beneath.

    The structure may also be used for maps that are not procedurally
    generated; hand-crafted maps can use the LevelMap structure but
    not the map generation facilities.
