sgt-puzzles/devel.but

\cfg{text-indent}{0}
\cfg{text-width}{72}
\cfg{text-title-align}{left}
\cfg{text-chapter-align}{left}
\cfg{text-chapter-numeric}{true}
\cfg{text-chapter-suffix}{. }
\cfg{text-chapter-underline}{-}
\cfg{text-section-align}{0}{left}
\cfg{text-section-numeric}{0}{true}
\cfg{text-section-suffix}{0}{. }
\cfg{text-section-underline}{0}{-}
\cfg{text-section-align}{1}{left}
\cfg{text-section-numeric}{1}{true}
\cfg{text-section-suffix}{1}{. }
\cfg{text-section-underline}{1}{-}
\cfg{text-versionid}{0}

\cfg{html-contents-filename}{index.html}
\cfg{html-template-filename}{%k.html}
\cfg{html-index-filename}{docindex.html}
\cfg{html-leaf-level}{1}
\cfg{html-contents-depth-0}{1}
\cfg{html-contents-depth-1}{3}
\cfg{html-leaf-contains-contents}{true}

\define{dash} \u2013{-}

\title Developer documentation for Simon Tatham's puzzle collection

This is a guide to the internal structure of Simon Tatham's Portable
Puzzle Collection (henceforth referred to simply as \q{Puzzles}),
for use by anyone attempting to implement a new puzzle or port to a
new platform.

This guide is believed correct as of \cw{git} commit
\cw{a2212e82aa2f4b9a4ee22783d6fed2761c213432}. Hopefully it will be
updated along with the code in future, but if not, I've at least left
this version number in here so you can figure out what's changed by
tracking commit comments from there onwards.

\C{intro} Introduction

The Puzzles code base is divided into four parts: a set of
interchangeable front ends, a set of interchangeable back ends, a
universal \q{middle end} which acts as a buffer between the two, and
a bunch of miscellaneous utility functions. In the following
sections I give some general discussion of each of these parts.

\H{intro-frontend} Front end

The front end is the non-portable part of the code: it's the bit
that you replace completely when you port to a different platform.
So it's responsible for all system calls, all GUI interaction, and
anything else platform-specific.

The front end contains \cw{main()} or the local platform's
equivalent. Top-level control over the application's execution flow
belongs to the front end (it isn't, for example, a set of functions
called by a universal \cw{main()} somewhere else).

The front end has complete freedom to design the GUI for any given
port of Puzzles. There is no centralised mechanism for maintaining the
menu layout, for example. This has a cost in consistency (when I
\e{do} want the same menu layout on more than one platform, I have to
edit N pieces of code in parallel every time I make a change), but the
advantage is that local GUI conventions can be conformed to and local
constraints adapted to. For example, MacOS has strict human interface
guidelines which specify a different menu layout from the one I've
used on Windows and GTK; there's nothing stopping the MacOS front end
from providing a menu layout consistent with those guidelines.

Although the front end is mostly caller rather than the callee in
its interactions with other parts of the code, it is required to
implement a small API for other modules to call, mostly of drawing
functions for games to use when drawing their graphics. The drawing
API is documented in \k{drawing}; the other miscellaneous front end
API functions are documented in \k{frontend-api}.

\H{intro-backend} Back end

A \q{back end}, in this collection, is synonymous with a \q{puzzle}.
Each back end implements a different game.

At the top level, a back end is simply a data structure, containing
a few constants (flag words, preferred pixel size) and a large
number of function pointers. Back ends are almost invariably callee
rather than caller, which means there's a limitation on what a back
end can do on its own initiative.

The persistent state in a back end is divided into a number of data
structures, which are used for different purposes and therefore
likely to be switched around, changed without notice, and otherwise
updated by the rest of the code. It is important when designing a
back end to put the right pieces of data into the right structures,
or standard midend-provided features (such as Undo) may fail to
work.

The functions and variables provided in the back end data structure
are documented in \k{backend}.

\H{intro-midend} Middle end

Puzzles has a single and universal \q{middle end}. This code is
common to all platforms and all games; it sits in between the front
end and the back end and provides standard functionality everywhere.

People adding new back ends or new front ends should generally not
need to edit the middle end. On rare occasions there might be a
change that can be made to the middle end to permit a new game to do
something not currently anticipated by the middle end's present
design; however, this is terribly easy to get wrong and should
probably not be undertaken without consulting the primary maintainer
(me). Patch submissions containing unannounced mid-end changes will
be treated on their merits like any other patch; this is just a
friendly warning that mid-end changes will need quite a lot of
merits to make them acceptable.

Functionality provided by the mid-end includes:

\b Maintaining a list of game state structures and moving back and
forth along that list to provide Undo and Redo.

\b Handling timers (for move animations, flashes on completion, and
in some cases actually timing the game).

\b Handling the container format of game IDs: receiving them,
picking them apart into parameters, description and/or random seed,
and so on. The game back end need only handle the individual parts
of a game ID (encoded parameters and encoded game description);
everything else is handled centrally by the mid-end.

\b Handling standard keystrokes and menu commands, such as \q{New
Game}, \q{Restart Game} and \q{Quit}.

\b Pre-processing mouse events so that the game back ends can rely
on them arriving in a sensible order (no missing button-release
events, no sudden changes of which button is currently pressed,
etc).

\b Handling the dialog boxes which ask the user for a game ID.

\b Handling serialisation of entire games (for loading and saving a
half-finished game to a disk file; for handling application shutdown
and restart on platforms such as PalmOS where state is expected to be
saved; for storing the previous game in order to undo and redo across
a New Game event).

Thus, there's a lot of work done once by the mid-end so that
individual back ends don't have to worry about it. All the back end
has to do is cooperate in ensuring the mid-end can do its work
properly.

The API of functions provided by the mid-end to be called by the
front end is documented in \k{midend}.

\H{intro-utils} Miscellaneous utilities

In addition to these three major structural components, the Puzzles
code also contains a variety of utility modules usable by all of the
above components. There is a set of functions to provide
platform-independent random number generation; functions to make
memory allocation easier; functions which implement a balanced tree
structure to be used as necessary in complex algorithms; and a few
other miscellaneous functions. All of these are documented in
\k{utils}.

\H{intro-structure} Structure of this guide

There are a number of function call interfaces within Puzzles, and
this guide will discuss each one in a chapter of its own. After
that, \k{writing} discusses how to design new games, with some
general design thoughts and tips.

\C{backend} Interface to the back end

This chapter gives a detailed discussion of the interface that each
back end must implement.

At the top level, each back end source file exports a single global
symbol, which is a \c{const struct game} containing a large number
of function pointers and a small amount of constant data. This
structure is called by different names depending on what kind of
platform the puzzle set is being compiled on:

\b On platforms such as Windows and GTK, which build a separate
binary for each puzzle, the game structure in every back end has the
same name, \cq{thegame}; the front end refers directly to this name,
so that compiling the same front end module against a different back
end module builds a different puzzle.

\b On platforms such as MacOS X and PalmOS, which build all the
puzzles into a single monolithic binary, the game structure in each
back end must have a different name, and there's a helper module
\c{list.c} which constructs a complete list of those game structures
from a header file generated by CMake.

On the latter type of platform, source files may assume that the
preprocessor symbol \c{COMBINED} has been defined. Thus, the usual
code to declare the game structure looks something like this:

\c #ifdef COMBINED
\c #define thegame net    /* or whatever this game is called */
\e                 iii    iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
\c #endif
\c 
\c const struct game thegame = {
\c     /* lots of structure initialisation in here */
\e     iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
\c };

Game back ends must also internally define a number of data
structures, for storing their various persistent state. This chapter
will first discuss the nature and use of those structures, and then
go on to give details of every element of the game structure.

\H{backend-structs} Data structures

Each game is required to define four separate data structures. This
section discusses each one and suggests what sorts of things need to
be put in it.

\S{backend-game-params} \c{game_params}

The \c{game_params} structure contains anything which affects the
automatic generation of new puzzles. So if puzzle generation is
parametrised in any way, those parameters need to be stored in
\c{game_params}.

Most puzzles currently in this collection are played on a grid of
squares, meaning that the most obvious parameter is the grid size.
Many puzzles have additional parameters; for example, Mines allows
you to control the number of mines in the grid independently of its
size, Net can be wrapping or non-wrapping, Solo has difficulty
levels and symmetry settings, and so on.

A simple rule for deciding whether a data item needs to go in
\c{game_params} is: would the user expect to be able to control this
data item from either the preset-game-types menu or the \q{Custom}
game type configuration? If so, it's part of \c{game_params}.

\c{game_params} structures are permitted to contain pointers to
subsidiary data if they need to. The back end is required to provide
functions to create and destroy \c{game_params}, and those functions
can allocate and free additional memory if necessary. (It has not
yet been necessary to do this in any puzzle so far, but the
capability is there just in case.)

\c{game_params} is also the only structure which the game's
\cw{compute_size()} function may refer to; this means that any aspect
of the game which affects the size of the window it needs to be drawn
in (other than the magnification level) must be stored in
\c{game_params}. In particular, this imposes the fundamental
limitation that random game generation may not have a random effect on
the window size: game generation algorithms are constrained to work by
starting from the grid size rather than generating it as an emergent
phenomenon. (Although this is a restriction in theory, it has not yet
seemed to be a problem.)

\S{backend-game-state} \c{game_state}

While the user is actually playing a puzzle, the \c{game_state}
structure stores all the data corresponding to the current state of
play.

The mid-end keeps \c{game_state}s in a list, and adds to the list
every time the player makes a move; the Undo and Redo functions step
back and forth through that list.

Therefore, a good means of deciding whether a data item needs to go in
\c{game_state} is: would a player expect that data item to be restored
on undo? If so, put it in \c{game_state}, and this will automatically
happen without you having to lift a finger. If not, then you might
have found a data item that needs to go in \c{game_ui} instead.

Two quite different examples of this:

\b if the game provides an interface for making moves by moving a
cursor around the grid with the keyboard and pressing some other key
when you get to a square you want to change, then the location of that
cursor belongs in \c{game_ui}, because the player will want to undo
one \e{square change} at a time, not one \e{cursor movement} at a
time.

\b Mines tracks the number of times you opened a mine square and died.
Every time you do that, you can only continue the game by pressing
Undo. So the deaths counter belongs in \c{game_ui}, because otherwise,
it would revert to 0 every time you undid your mistaken move.

During play, \c{game_state}s are often passed around without an
accompanying \c{game_params} structure. Therefore, any information
in \c{game_params} which is important during play (such as the grid
size) must be duplicated within the \c{game_state}. One simple
method of doing this is to have the \c{game_state} structure
\e{contain} a \c{game_params} structure as one of its members,
although this isn't obligatory if you prefer to do it another way.

\S{backend-game-drawstate} \c{game_drawstate}

\c{game_drawstate} carries persistent state relating to the current
graphical contents of the puzzle window. The same \c{game_drawstate}
is passed to every call to the game redraw function, so that it can
remember what it has already drawn and what needs redrawing.

A typical use for a \c{game_drawstate} is to have an array mirroring
the array of grid squares in the \c{game_state}, but describing what
was drawn in the window on the most recent redraw. This is used to
identify the squares that need redrawing next time, by deciding what
the new value in that array should be, and comparing it to what was
drawn last time. See \k{writing-howto-redraw} for more on this
subject.

\c{game_drawstate} is occasionally completely torn down and
reconstructed by the mid-end, if the user somehow forces a full
redraw. Therefore, no data should be stored in \c{game_drawstate}
which is \e{not} related to the state of the puzzle window, because
it might be unexpectedly destroyed.

The back end provides functions to create and destroy
\c{game_drawstate}, which means it can contain pointers to
subsidiary allocated data if it needs to. A common thing to want to
allocate in a \c{game_drawstate} is a \c{blitter}; see
\k{drawing-blitter} for more on this subject.

\S{backend-game-ui} \c{game_ui}

\c{game_ui} contains whatever doesn't fit into the above three
structures!

A new \c{game_ui} is created when the user begins playing a new
instance of a puzzle (i.e. during \q{New Game} or after entering a
game ID etc). It persists until the user finishes playing that game
and begins another one (or closes the window); in particular,
\q{Restart Game} does \e{not} destroy the \c{game_ui}.

There are various things that you might store in \c{game_ui}, which
are conceptually different from each other, but I haven't yet found a
need to split them out into smaller sub-structures for different
purposes:

\dt Transient UI state:

\dd Storing a piece of UI state in \c{game_state} means that you can
only update it by appending a move to the undo chain. Some UI state
shouldn't really be treated this way. For example, if your puzzle has
a keyboard-controlled cursor, you probably don't want every cursor
movement to be an undoable action, because the history of where the
cursor went just isn't interesting. More likely the cursor should just
move freely, and the only undoable actions are the ones where you
modify the element under the cursor. So you'd store the cursor
position in \c{game_ui} rather than \c{game_state}. See
\k{writing-keyboard-cursor} for more details.

\lcont{ Another example of this is the state of an ongoing mouse drag.
If there's an undoable action involved, it will probably occur when
the drag is released. In between, you still need to store state that
the redraw function will use to update the display \dash and that can
live in \c{game_ui}. See \k{writing-howto-dragging} for more details
of this. }

\dt Persistent UI state:

\dd An example of this is the counter of deaths in Mines or Inertia.
This shouldn't be reverted by pressing Undo, for the opposite reason
to the cursor position: the cursor position is too boring to store the
history of, but the deaths counter is too \e{important}!

\dt Information about recent changes to the game state:

\dd This is used in Mines, for example, to indicate whether a
requested \q{flash} should be a white flash for victory or a red flash
for defeat; see \k{writing-flash-types}.

\dt User preferences:

\dd Any user preference about display or UI handled by
\cw{get_prefs()} and \cw{set_prefs()} will need to live in
\c{game_ui}, because that's the structure that those functions access.

\H{backend-simple} Simple data in the back end

In this section I begin to discuss each individual element in the
back end structure. To begin with, here are some simple
self-contained data elements.

\S{backend-name} \c{name}

\c const char *name;

This is a simple ASCII string giving the name of the puzzle. This
name will be used in window titles, in game selection menus on
monolithic platforms, and anywhere else that the front end needs to
know the name of a game.

\S{backend-winhelp} \c{winhelp_topic} and \c{htmlhelp_topic}

\c const char *winhelp_topic, *htmlhelp_topic;

These members are used on Windows only, to provide online help.
Although the Windows front end provides a separate binary for each
puzzle, it has a single monolithic help file; so when a user selects
\q{Help} from the menu, the program needs to open the help file and
jump to the chapter describing that particular puzzle.

This code base still supports the legacy \cw{.HLP} Windows Help format
as well as the less old \cw{.CHM} HTML Help format. The two use
different methods of identifying topics, so you have to specify both.

Each chapter about a puzzle in \c{puzzles.but} is labelled with a
\e{help topic} name for Windows Help, which typically appears just
after the \cw{\\C} chapter title paragraph, similar to this:

\c \C{net} \i{Net}
\c
\c \cfg{winhelp-topic}{games.net}

But HTML Help is able to use the Halibut identifier for the chapter
itself, i.e. the keyword that appears in braces immediatey after the
\cw{\\C}.

So the corresponding game back end encodes the \c{winhelp-topic}
string (here \cq{games.net}) in the \c{winhelp_topic} element of the
game structure, and puts the chapter identifier (here \cq{net}) in the
\c{htmlhelp_topic} element. For example:

\c const struct game thegame = {
\c    "Net", "games.net", "net",
\c    // ...
\c };

\H{backend-params} Handling game parameter sets

In this section I present the various functions which handle the
\c{game_params} structure.

\S{backend-default-params} \cw{default_params()}

\c game_params *(*default_params)(void);

This function allocates a new \c{game_params} structure, fills it
with the default values, and returns a pointer to it.

\S{backend-fetch-preset} \cw{fetch_preset()}

\c bool (*fetch_preset)(int i, char **name, game_params **params);

This function is one of the two APIs a back end can provide to
populate the \q{Type} menu, which provides a list of conveniently
accessible preset parameters for most games.

The function is called with \c{i} equal to the index of the preset
required (numbering from zero). It returns \cw{false} if that preset
does not exist (if \c{i} is less than zero or greater than the
largest preset index). Otherwise, it sets \c{*params} to point at a
newly allocated \c{game_params} structure containing the preset
information, sets \c{*name} to point at a newly allocated C string
containing the preset title (to go on the \q{Type} menu), and
returns \cw{true}.

If the game does not wish to support any presets at all, this
function is permitted to return \cw{false} always.

If the game wants to return presets in the form of a hierarchical menu
instead of a flat list (and, indeed, even if it doesn't), then it may
set this function pointer to \cw{NULL}, and instead fill in the
alternative function pointer \cw{preset_menu}
(\k{backend-preset-menu}).

\S{backend-preset-menu} \cw{preset_menu()}

\c struct preset_menu *(*preset_menu)(void);

This function is the more flexible of the two APIs by which a back end
can define a collection of preset game parameters.

This function simply returns a complete menu hierarchy, in the form of
a \c{struct preset_menu} (see \k{midend-get-presets}) and further
submenus (if it wishes) dangling off it. There are utility functions
described in \k{utils-presets} to make it easy for the back end to
construct this menu.

If the game has no need to return a hierarchy of menus, it may instead
opt to implement the \cw{fetch_preset()} function (see
\k{backend-fetch-preset}).

The game need not fill in the \c{id} fields in the preset menu
structures. The mid-end will do that after it receives the structure
from the game, and before passing it on to the front end.

\S{backend-encode-params} \cw{encode_params()}

\c char *(*encode_params)(const game_params *params, bool full);

The job of this function is to take a \c{game_params}, and encode it
in a printable ASCII string form for use in game IDs. The return value must
be a newly allocated C string, and \e{must} not contain a colon or a hash
(since those characters are used to mark the end of the parameter
section in a game ID).

Ideally, it should also not contain any other potentially
controversial punctuation; bear in mind when designing a string
parameter format that it will probably be used on both Windows and
Unix command lines under a variety of exciting shell quoting and
metacharacter rules. Sticking entirely to alphanumerics is the
safest thing; if you really need punctuation, you can probably get
away with commas, periods or underscores without causing anybody any
major inconvenience. If you venture far beyond that, you're likely
to irritate \e{somebody}.

(At the time of writing this, most existing games have purely
alphanumeric string parameter formats. Usually these involve a
letter denoting a parameter, followed optionally by a number giving
the value of that parameter, with a few mandatory parts at the
beginning such as numeric width and height separated by \cq{x}.)

If the \c{full} parameter is \cw{true}, this function should encode
absolutely everything in the \c{game_params}, such that a subsequent
call to \cw{decode_params()} (\k{backend-decode-params}) will yield
an identical structure. If \c{full} is \cw{false}, however, you
should leave out anything which is not necessary to describe a
\e{specific puzzle instance}, i.e. anything which only takes effect
when a new puzzle is \e{generated}.

For example, the Solo \c{game_params} includes a difficulty rating
used when constructing new puzzles; but a Solo game ID need not
explicitly include the difficulty, since to describe a puzzle once
generated it's sufficient to give the grid dimensions and the location
and contents of the clue squares. (Indeed, one might very easily type
in a puzzle out of a newspaper without \e{knowing} what its difficulty
level is in Solo's terminology.) Therefore, Solo's
\cw{encode_params()} only encodes the difficulty level if \c{full} is
set.

\S{backend-decode-params} \cw{decode_params()}

\c void (*decode_params)(game_params *params, char const *string);

This function is the inverse of \cw{encode_params()}
(\k{backend-encode-params}). It parses the supplied string and fills
in the supplied \c{game_params} structure. Note that the structure
will \e{already} have been allocated: this function is not expected
to create a \e{new} \c{game_params}, but to modify an existing one.

This function can receive a string which only encodes a subset of
the parameters. The most obvious way in which this can happen is if
the string was constructed by \cw{encode_params()} with its \c{full}
parameter set to \cw{false}; however, it could also happen if the
user typed in a parameter set manually and missed something out. Be
prepared to deal with a wide range of possibilities.

When dealing with a parameter which is not specified in the input
string, what to do requires a judgment call on the part of the
programmer. Sometimes it makes sense to adjust other parameters to
bring them into line with the new ones. In Mines, for example, you
would probably not want to keep the same mine count if the user
dropped the grid size and didn't specify one, since you might easily
end up with more mines than would actually fit in the grid! On the
other hand, sometimes it makes sense to leave the parameter alone: a
Solo player might reasonably expect to be able to configure size and
difficulty independently of one another.

This function currently has no direct means of returning an error if
the string cannot be parsed at all. However, the returned
\c{game_params} is almost always subsequently passed to
\cw{validate_params()} (\k{backend-validate-params}), so if you
really want to signal parse errors, you could always have a \c{char
*} in your parameters structure which stored an error message, and
have \cw{validate_params()} return it if it is non-\cw{NULL}.

\S{backend-free-params} \cw{free_params()}

\c void (*free_params)(game_params *params);

This function frees a \c{game_params} structure, and any subsidiary
allocations contained within it.

\S{backend-dup-params} \cw{dup_params()}

\c game_params *(*dup_params)(const game_params *params);

This function allocates a new \c{game_params} structure and
initialises it with an exact copy of the information in the one
provided as input. It returns a pointer to the new duplicate.

\S{backend-can-configure} \c{can_configure}

\c bool can_configure;

This data element is set to \cw{true} if the back end supports custom
parameter configuration via a dialog box. If it is \cw{true}, then the
functions \cw{configure()} and \cw{custom_params()} are expected to
work. See \k{backend-configure} and \k{backend-custom-params} for more
details.

\S{backend-configure} \cw{configure()}

\c config_item *(*configure)(const game_params *params);

This function is called when the user requests a dialog box for
custom parameter configuration. It returns a newly allocated array
of \cw{config_item} structures, describing the GUI elements required
in the dialog box. The array should have one more element than the
number of controls, since it is terminated with a \cw{C_END} marker
(see below). Each array element describes the control together with
its initial value; the front end will modify the value fields and
return the updated array to \cw{custom_params()} (see
\k{backend-custom-params}).

The \cw{config_item} structure contains the following elements used by
this function:

\c const char *name;
\c int type;
\c union { /* type-specific fields */ } u;
\e         iiiiiiiiiiiiiiiiiiiiiiiiii

\c{name} is an ASCII string giving the textual label for a GUI
control. It is \e{not} expected to be dynamically allocated.

\c{type} contains one of a small number of \c{enum} values defining
what type of control is being described. The usable member of the
union field \c{u} depends on \c{type}. The valid type values are:

\dt \c{C_STRING}

\dd Describes a text input box. (This is also used for numeric
input. The back end does not bother informing the front end that the
box is numeric rather than textual; some front ends do have the
capacity to take this into account, but I decided it wasn't worth
the extra complexity in the interface.)

\lcont{

For controls of this type, \c{u.string} contains a single field

\c char *sval;

which stores a dynamically allocated string representing the contents
of the input box.

}

\dt \c{C_BOOLEAN}

\dd Describes a simple checkbox.

\lcont{

For controls of this type, \c{u.boolean} contains a single field

\c bool bval;

}

\dt \c{C_CHOICES}

\dd Describes a drop-down list presenting one of a small number of
fixed choices.

\lcont{

For controls of this type, \c{u.choices} contains two fields:

\c const char *choicenames;
\c int selected;

\c{choicenames} contains a list of strings describing the choices. The
very first character of \c{sval} is used as a delimiter when
processing the rest (so that the strings \cq{:zero:one:two},
\cq{!zero!one!two} and \cq{xzeroxonextwo} all define a three-element
list containing \cq{zero}, \cq{one} and \cq{two}).

\c{selected} contains the index of the currently selected element,
numbering from zero (so that in the above example, 0 would mean
\cq{zero} and 2 would mean \cq{two}).

Note that \c{u.choices.choicenames} is \e{not} dynamically allocated,
unlike \c{u.string.sval}.

}

\dt \c{C_END}

\dd Marks the end of the array of \c{config_item}s. There is no
associated member of the union field \c{u} for this type.

The array returned from this function is expected to have filled in
the initial values of all the controls according to the input
\c{game_params} structure.

If the game's \c{can_configure} flag is set to \cw{false}, this
function is never called and can be \cw{NULL}.

\S{backend-custom-params} \cw{custom_params()}

\c game_params *(*custom_params)(const config_item *cfg);

This function is the counterpart to \cw{configure()}
(\k{backend-configure}). It receives as input an array of
\c{config_item}s which was originally created by \cw{configure()},
but in which the control values have since been changed in
accordance with user input. Its function is to read the new values
out of the controls and return a newly allocated \c{game_params}
structure representing the user's chosen parameter set.

(The front end will have modified the controls' \e{values}, but
there will still always be the same set of controls, in the same
order, as provided by \cw{configure()}. It is not necessary to check
the \c{name} and \c{type} fields, although you could use
\cw{assert()} if you were feeling energetic.)

This function is not expected to (and indeed \e{must not}) free the
input \c{config_item} array. (If the parameters fail to validate,
the dialog box will stay open.)

If the game's \c{can_configure} flag is set to \cw{false}, this
function is never called and can be \cw{NULL}.

\S{backend-get-prefs} \cw{get_prefs()}

\c config_item *(*get_prefs)(game_ui *ui);

This function works very like \cw{configure()}, but instead of
receiving a \c{game_params} and returning GUI elements describing the
data in it, this function receives a \c{game_ui} and returns GUI
elements describing any user preferences stored in that.

This function should only deal with fields of \c{game_ui} that are
user-settable preferences. In-game state like cursor position and
mouse drags, or per-game state like death counters, are nothing to do
with this function.

If there are no user preferences, you can set both this function
pointer and \c{set_prefs} to \cw{NULL}.

If you implement these functions, you must also ensure that your
game's \cw{new_ui()} function can be called with a null \c{game_state}
pointer. (See \k{backend-new-ui}.)

In every \c{config_item} returned from this function, you must set an
additional field beyond the ones described in \k{backend-configure}:

\c const char *kw;

This should be an identifying keyword for the user preference in
question, suitable for use in configuration files. That means it
should remain stable, even if the user-facing wording in the \c{name}
field is reworded for clarity. If it doesn't stay stable, old
configuration files will not be read correctly.

For \c{config_item}s of type \cw{C_CHOICES}, you must also set an
extra field in \c{u.choices}:

\c const char *choicekws;

This has the same structure as the \c{choicenames} field (a list of
values delimited by the first character in the whole string), and it
provides an identifying keyword for each individual choice in the
list, in the same order as the entries of \c{choicenames}.

\S{backend-set-prefs} \cw{set_prefs()}

\c void (*set_prefs)(game_ui *ui, const config_item *cfg);

This function is the counterpart to \cw{set_prefs()}, as
\cw{custom_params()} is to \cw{configure()}. It receives an array of
\c{config_item}s which was originally created by \cw{get_prefs()},
with the controls' values updated from user input, and it should
transcribe the new settings into the provided \c{game_ui}.

If there are no user preferences, you can set both this function
pointer and \c{get_prefs} to \cw{NULL}.

\S{backend-validate-params} \cw{validate_params()}

\c const char *(*validate_params)(const game_params *params,
\c                                bool full);

This function takes a \c{game_params} structure as input, and checks
that the parameters described in it fall within sensible limits. (At
the very least, grid dimensions should almost certainly be strictly
positive, for example.)

Return value is \cw{NULL} if no problems were found, or
alternatively a (non-dynamically-allocated) ASCII string describing
the error in human-readable form.

If the \c{full} parameter is set, full validation should be
performed: any set of parameters which would not permit generation
of a sensible puzzle should be faulted. If \c{full} is \e{not} set,
the implication is that these parameters are not going to be used
for \e{generating} a puzzle; so parameters which can't even sensibly
\e{describe} a valid puzzle should still be faulted, but parameters
which only affect puzzle generation should not be.

(The \c{full} option makes a difference when parameter combinations
are non-orthogonal. For example, Net has a boolean option
controlling whether it enforces a unique solution; it turns out that
it's impossible to generate a uniquely soluble puzzle with wrapping
walls and width 2, so \cw{validate_params()} will complain if you
ask for one. However, if the user had just been playing a unique
wrapping puzzle of a more sensible width, and then pastes in a game
ID acquired from somebody else which happens to describe a
\e{non}-unique wrapping width-2 puzzle, then \cw{validate_params()}
will be passed a \c{game_params} containing the width and wrapping
settings from the new game ID and the uniqueness setting from the
old one. This would be faulted, if it weren't for the fact that
\c{full} is not set during this call, so Net ignores the
inconsistency. The resulting \c{game_params} is never subsequently
used to generate a puzzle; this is a promise made by the mid-end
when it asks for a non-full validation.)

\H{backend-descs} Handling game descriptions

In this section I present the functions that deal with a textual
description of a puzzle, i.e. the part that comes after the colon in
a descriptive-format game ID.

\S{backend-new-desc} \cw{new_desc()}

\c char *(*new_desc)(const game_params *params, random_state *rs,
\c                   char **aux, bool interactive);

This function is where all the really hard work gets done. This is
the function whose job is to randomly generate a new puzzle,
ensuring solubility and uniqueness as appropriate.

As input it is given a \c{game_params} structure and a random state
(see \k{utils-random} for the random number API). It must invent a
puzzle instance, encode it in printable ASCII string form, and
return a dynamically allocated C string containing that encoding.

Additionally, it may return a second dynamically allocated string in
\c{*aux}. (If it doesn't want to, then it can leave that parameter
completely alone; it isn't required to set it to \cw{NULL}, although
doing so is harmless.) That string, if present, will be passed to
\cw{solve()} (\k{backend-solve}) later on; so if the puzzle is
generated in such a way that a solution is known, then information
about that solution can be saved in \c{*aux} for \cw{solve()} to
use.

The \c{interactive} parameter should be ignored by almost all
puzzles. Its purpose is to distinguish between generating a puzzle
within a GUI context for immediate play, and generating a puzzle in
a command-line context for saving to be played later. The only
puzzle that currently uses this distinction (and, I fervently hope,
the only one which will \e{ever} need to use it) is Mines, which
chooses a random first-click location when generating puzzles
non-interactively, but which waits for the user to place the first
click when interactive. If you think you have come up with another
puzzle which needs to make use of this parameter, please think for
at least ten minutes about whether there is \e{any} alternative!

Note that game description strings are not required to contain an
encoding of parameters such as grid size; a game description is
never separated from the \c{game_params} it was generated with, so
any information contained in that structure need not be encoded
again in the game description.

\S{backend-validate-desc} \cw{validate_desc()}

\c const char *(*validate_desc)(const game_params *params,
\c                              const char *desc);

This function is given a game description, and its job is to
validate that it describes a puzzle which makes sense.

To some extent it's up to the user exactly how far they take the
phrase \q{makes sense}; there are no particularly strict rules about
how hard the user is permitted to shoot themself in the foot when
typing in a bogus game description by hand. (For example, Rectangles
will not verify that the sum of all the numbers in the grid equals
the grid's area. So a user could enter a puzzle which was provably
not soluble, and the program wouldn't complain; there just wouldn't
happen to be any sequence of moves which solved it.)

The one non-negotiable criterion is that any game description which
makes it through \cw{validate_desc()} \e{must not} subsequently
cause a crash or an assertion failure when fed to \cw{new_game()}
and thence to the rest of the back end.

The return value is \cw{NULL} on success, or a
non-dynamically-allocated C string containing an error message.

\S{backend-new-game} \cw{new_game()}

\c game_state *(*new_game)(midend *me, const game_params *params,
\c                         const char *desc);

This function takes a game description as input, together with its
accompanying \c{game_params}, and constructs a \c{game_state}
describing the initial state of the puzzle. It returns a newly
allocated \c{game_state} structure.

Almost all puzzles should ignore the \c{me} parameter. It is
required by Mines, which needs it for later passing to
\cw{midend_supersede_game_desc()} (see \k{backend-supersede}) once
the user has placed the first click. I fervently hope that no other
puzzle will be awkward enough to require it, so everybody else
should ignore it. As with the \c{interactive} parameter in
\cw{new_desc()} (\k{backend-new-desc}), if you think you have a
reason to need this parameter, please try very hard to think of an
alternative approach!

\H{backend-states} Handling game states

This section describes the functions which create and destroy
\c{game_state} structures.

(Well, except \cw{new_game()}, which is in \k{backend-new-game}
instead of under here; but it deals with game descriptions \e{and}
game states and it had to go in one section or the other.)

\S{backend-dup-game} \cw{dup_game()}

\c game_state *(*dup_game)(const game_state *state);

This function allocates a new \c{game_state} structure and
initialises it with an exact copy of the information in the one
provided as input. It returns a pointer to the new duplicate.

\S{backend-free-game} \cw{free_game()}

\c void (*free_game)(game_state *state);

This function frees a \c{game_state} structure, and any subsidiary
allocations contained within it.

\H{backend-ui} Handling \c{game_ui}

\S{backend-new-ui} \cw{new_ui()}

\c game_ui *(*new_ui)(const game_state *state);

This function allocates and returns a new \c{game_ui} structure for
playing a particular puzzle.

Usually, this function is passed a pointer to the initial
\c{game_state}, in case it needs to refer to that when setting up the
initial values for the new game.

However, if the puzzle defines \c{get_prefs()} and \c{set_prefs()}
functions, then this function may also be called with
\cw{state==NULL}. In this situation it must still allocate a
\c{game_ui} which can be used by \c{get_prefs()} and \c{set_prefs()},
although it need not be usable for actually playing a game.

\S{backend-free-ui} \cw{free_ui()}

\c void (*free_ui)(game_ui *ui);

This function frees a \c{game_ui} structure, and any subsidiary
allocations contained within it.

\S{backend-encode-ui} \cw{encode_ui()}

\c char *(*encode_ui)(const game_ui *ui);

This function encodes any \e{important} data in a \c{game_ui}
structure in printable ASCII string form. It is only called when
saving a half-finished game to a file.

It should be used sparingly. Almost all data in a \c{game_ui} is not
important enough to save. The location of the keyboard-controlled
cursor, for example, can be reset to a default position on reloading
the game without impacting the user experience. If the user should
somehow manage to save a game while a mouse drag was in progress,
then discarding that mouse drag would be an outright \e{feature}.

A typical thing that \e{would} be worth encoding in this function is
the Mines death counter: it's in the \c{game_ui} rather than the
\c{game_state} because it's too important to allow the user to
revert it by using Undo, and therefore it's also too important to
allow the user to revert it by saving and reloading. (Of course, the
user could edit the save file by hand... But if the user is \e{that}
determined to cheat, they could just as easily modify the game's
source.)

The \cw{encode_ui()} function is optional.  If a back-end doesn't need
this function it can just set the pointer to \cw{NULL}.

\S{backend-decode-ui} \cw{decode_ui()}

\c void (*decode_ui)(game_ui *ui, const char *encoding,
\c                   const game_state *state);

This function parses a string previously output by \cw{encode_ui()},
and writes the decoded data back into the freshly-created \c{game_ui}
structure provided.  If the string is invalid, the function should do
the best it can, which might just mean not changing the \c{game_ui}
structure at all.  This might happen if a save file is corrupted, or
simply from a newer version that encodes more \c{game_ui} data.  The
current \c{game_state} is provided in case the function needs to
refer to it for validation.

Like \cw{encode_ui()}, \cw{decode_ui()} is optional.  If a back-end
doesn't need this function it can just set the pointer to \cw{NULL}.

\S{backend-changed-state} \cw{changed_state()}

\c void (*changed_state)(game_ui *ui, const game_state *oldstate,
\c                       const game_state *newstate);

This function is called by the mid-end whenever the current game
state changes, for any reason. Those reasons include:

\b a fresh move being made by \cw{interpret_move()} and
\cw{execute_move()}

\b a solve operation being performed by \cw{solve()} and
\cw{execute_move()}

\b the user moving back and forth along the undo list by means of
the Undo and Redo operations

\b the user selecting Restart to go back to the initial game state.

The job of \cw{changed_state()} is to update the \c{game_ui} for
consistency with the new game state, if any update is necessary. For
example, Same Game stores data about the currently selected tile
group in its \c{game_ui}, and this data is intrinsically related to
the game state it was derived from. So it's very likely to become
invalid when the game state changes; thus, Same Game's
\cw{changed_state()} function clears the current selection whenever
it is called.

When \cw{anim_length()} or \cw{flash_length()} are called, you can
be sure that there has been a previous call to \cw{changed_state()}.
So \cw{changed_state()} can set up data in the \c{game_ui} which will
be read by \cw{anim_length()} and \cw{flash_length()}, and those
functions will not have to worry about being called without the data
having been initialised.

\H{backend-moves} Making moves

This section describes the functions which actually make moves in
the game: that is, the functions which process user input and end up
producing new \c{game_state}s.

\S{backend-interpret-move} \cw{interpret_move()}

\c char *(*interpret_move)(const game_state *state, game_ui *ui,
\c                         const game_drawstate *ds,
\c                         int x, int y, int button);

This function receives user input and processes it. Its input
parameters are the current \c{game_state}, the current \c{game_ui}
and the current \c{game_drawstate}, plus details of the input event.
\c{button} is either an ASCII value or a special code (listed below)
indicating an arrow or function key or a mouse event; when
\c{button} is a mouse event, \c{x} and \c{y} contain the pixel
coordinates of the mouse pointer relative to the top left of the
puzzle's drawing area.

(The pointer to the \c{game_drawstate} is marked \c{const}, because
\c{interpret_move} should not write to it. The normal use of that
pointer will be to read the game's tile size parameter in order to
divide mouse coordinates by it.)

\cw{interpret_move()} may return in four different ways:

\b Returning \cw{MOVE_UNUSED} or \cw{MOVE_NO_EFFECT} indicates that no
action whatsoever occurred in response to the input event; the puzzle
was not interested in it at all.  The distinction between this is that
\cw{MOVE_NO_EFFECT} implies that the state of the game is what makes
the event uninteresting, while \cw{MOVE_NO_EFFECT} means that the
event is intrinsically uninteresting.  For example, a mouse click on
an already-revealed square in Mines might return \cw{MOVE_NO_EFFECT}
while a click outside the board would return \cw{MOVE_UNUSED}.

\b Returning the special value \cw{MOVE_UI_UPDATE} indicates that the input
event has resulted in a change being made to the \c{game_ui} which
will require a redraw of the game window, but that no actual \e{move}
was made (i.e. no new \c{game_state} needs to be created).

\b Returning anything else indicates that a move was made and that a
new \c{game_state} must be created. However, instead of actually
constructing a new \c{game_state} itself, this function is required
to return a printable ASCII string description of the details of the
move. This string will be passed to \cw{execute_move()}
(\k{backend-execute-move}) to actually create the new
\c{game_state}. (Encoding moves as strings in this way means that
the mid-end can keep the strings as well as the game states, and the
strings can be written to disk when saving the game and fed to
\cw{execute_move()} again on reloading.)

The return value from \cw{interpret_move()} is expected to be
dynamically allocated if and only if it is not either \cw{NULL}
\e{or} one of the special string constants \cw{MOVE_UNUSED},
\cw{MOVE_NO_EFFECT}, or \cw{MOVE_UI_UPDATE}.

After this function is called, the back end is permitted to rely on
some subsequent operations happening in sequence:

\b \cw{execute_move()} will be called to convert this move
description into a new \c{game_state}

\b \cw{changed_state()} will be called with the new \c{game_state}.

This means that if \cw{interpret_move()} needs to do updates to the
\c{game_ui} which are easier to perform by referring to the new
\c{game_state}, it can safely leave them to be done in
\cw{changed_state()} and not worry about them failing to happen.

(Note, however, that \cw{execute_move()} may \e{also} be called in
other circumstances. It is only \cw{interpret_move()} which can rely
on a subsequent call to \cw{changed_state()}.)

The special key codes supported by this function are:

\dt \cw{LEFT_BUTTON}, \cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}

\dd Indicate that one of the mouse buttons was pressed down.

\dt \cw{LEFT_DRAG}, \cw{MIDDLE_DRAG}, \cw{RIGHT_DRAG}

\dd Indicate that the mouse was moved while one of the mouse buttons
was still down. The mid-end guarantees that when one of these events
is received, it will always have been preceded by a button-down
event (and possibly other drag events) for the same mouse button,
and no event involving another mouse button will have appeared in
between.

\dt \cw{LEFT_RELEASE}, \cw{MIDDLE_RELEASE}, \cw{RIGHT_RELEASE}

\dd Indicate that a mouse button was released.  The mid-end
guarantees that when one of these events is received, it will always
have been preceded by a button-down event (and possibly some drag
events) for the same mouse button, and no event involving another
mouse button will have appeared in between.

\dt \cw{CURSOR_UP}, \cw{CURSOR_DOWN}, \cw{CURSOR_LEFT},
\cw{CURSOR_RIGHT}

\dd Indicate that an arrow key was pressed.

\dt \cw{CURSOR_SELECT}, \cw{CURSOR_SELECT2}

\dd On platforms which have one or two prominent \q{select} button
alongside their cursor keys, indicates that one of those buttons was
pressed.  On other platforms, these represent the Enter (or Return)
and Space keys respectively.

In addition, there are some modifiers which can be bitwise-ORed into
the \c{button} parameter:

\dt \cw{MOD_CTRL}, \cw{MOD_SHFT}

\dd These indicate that the Control or Shift key was pressed
alongside the key. They only apply to the cursor keys, not to mouse
buttons or anything else.

\dt \cw{MOD_NUM_KEYPAD}

\dd This applies to some ASCII values, and indicates that the key
code was input via the numeric keypad rather than the main keyboard.
Some puzzles may wish to treat this differently (for example, a
puzzle might want to use the numeric keypad as an eight-way
directional pad), whereas others might not (a game involving numeric
input probably just wants to treat the numeric keypad as numbers).

\dt \cw{MOD_MASK}

\dd This mask is the bitwise OR of all the available modifiers; you
can bitwise-AND with \cw{~MOD_MASK} to strip all the modifiers off
any input value.

\S{backend-execute-move} \cw{execute_move()}

\c game_state *(*execute_move)(const game_state *state, char *move);

This function takes an input \c{game_state} and a move string as
output from \cw{interpret_move()}. It returns a newly allocated
\c{game_state} which contains the result of applying the specified
move to the input game state.

This function may return \cw{NULL} if it cannot parse the move
string (and this is definitely preferable to crashing or failing an
assertion, since one way this can happen is if loading a corrupt
save file). However, it must not return \cw{NULL} for any move
string that really was output from \cw{interpret_move()}: this is
punishable by assertion failure in the mid-end.

\S{backend-can-solve} \c{can_solve}

\c bool can_solve;

This field is set to \cw{true} if the game's \cw{solve()} function
does something. If it's set to \cw{false}, the game will not even
offer the \q{Solve} menu option.

\S{backend-solve} \cw{solve()}

\c char *(*solve)(const game_state *orig, const game_state *curr,
\c                const char *aux, const char **error);

This function is called when the user selects the \q{Solve} option
from the menu.  If \cw{can_solve} is \cw{false} then it will never
be called and can be \cw{NULL}.

It is passed two input game states: \c{orig} is the game state from
the very start of the puzzle, and \c{curr} is the current one.
(Different games find one or other or both of these convenient.) It
is also passed the \c{aux} string saved by \cw{new_desc()}
(\k{backend-new-desc}), in case that encodes important information
needed to provide the solution.

If this function is unable to produce a solution (perhaps, for
example, the game has no in-built solver so it can only solve
puzzles it invented internally and has an \c{aux} string for) then
it may return \cw{NULL}. If it does this, it must also set
\c{*error} to an error message to be presented to the user (such as
\q{Solution not known for this puzzle}); that error message is not
expected to be dynamically allocated.

If this function \e{does} produce a solution, it returns a printable
ASCII move string suitable for feeding to \cw{execute_move()}
(\k{backend-execute-move}). Like a (non-empty) string returned from
\cw{interpret_move()}, the returned string should be dynamically
allocated.

\H{backend-drawing} Drawing the game graphics

This section discusses the back end functions that deal with
drawing.

\S{backend-new-drawstate} \cw{new_drawstate()}

\c game_drawstate *(*new_drawstate)(drawing *dr,
\c                                  const game_state *state);

This function allocates and returns a new \c{game_drawstate}
structure for drawing a particular puzzle. It is passed a pointer to
a \c{game_state}, in case it needs to refer to that when setting up
any initial data.

This function may not rely on the puzzle having been newly started;
a new draw state can be constructed at any time if the front end
requests a forced redraw. For games like Pattern, in which initial
game states are much simpler than general ones, this might be
important to keep in mind.

The parameter \c{dr} is a drawing object (see \k{drawing}) which the
function might need to use to allocate blitters. (However, this
isn't recommended; it's usually more sensible to wait to allocate a
blitter until \cw{set_size()} is called, because that way you can
tailor it to the scale at which the puzzle is being drawn.)

\S{backend-free-drawstate} \cw{free_drawstate()}

\c void (*free_drawstate)(drawing *dr, game_drawstate *ds);

This function frees a \c{game_drawstate} structure, and any
subsidiary allocations contained within it.

The parameter \c{dr} is a drawing object (see \k{drawing}), which
might be required if you are freeing a blitter.

\S{backend-preferred-tilesize} \c{preferred_tilesize}

\c int preferred_tilesize;

Each game is required to define a single integer parameter which
expresses, in some sense, the scale at which it is drawn. This is
described in the APIs as \cq{tilesize}, since most puzzles are on a
square (or possibly triangular or hexagonal) grid and hence a
sensible interpretation of this parameter is to define it as the
size of one grid tile in pixels; however, there's no actual
requirement that the \q{tile size} be proportional to the game
window size. Window size is required to increase monotonically with
\q{tile size}, however.

The data element \c{preferred_tilesize} indicates the tile size which
should be used in the absence of a good reason to do otherwise (such
as the screen being too small to fit the whole puzzle, or the user
explicitly requesting a resize).

\S{backend-compute-size} \cw{compute_size()}

\c void (*compute_size)(const game_params *params, int tilesize,
\c                      const game_ui *ui, int *x, int *y);

This function is passed a \c{game_params} structure and a tile size.
It returns, in \c{*x} and \c{*y}, the size in pixels of the drawing
area that would be required to render a puzzle with those parameters
at that tile size.

\S{backend-set-size} \cw{set_size()}

\c void (*set_size)(drawing *dr, game_drawstate *ds,
\c                  const game_params *params, int tilesize);

This function is responsible for setting up a \c{game_drawstate} to
draw at a given tile size. Typically this will simply involve
copying the supplied \c{tilesize} parameter into a \c{tilesize}
field inside the draw state; for some more complex games it might
also involve setting up other dimension fields, or possibly
allocating a blitter (see \k{drawing-blitter}).

The parameter \c{dr} is a drawing object (see \k{drawing}), which is
required if a blitter needs to be allocated.

Back ends may assume (and may enforce by assertion) that this
function will be called at most once for any \c{game_drawstate}. If
a puzzle needs to be redrawn at a different size, the mid-end will
create a fresh drawstate.

\S{backend-colours} \cw{colours()}

\c float *(*colours)(frontend *fe, int *ncolours);

This function is responsible for telling the front end what colours
the puzzle will need to draw itself.

It returns the number of colours required in \c{*ncolours}, and the
return value from the function itself is a dynamically allocated
array of three times that many \c{float}s, containing the red, green
and blue components of each colour respectively as numbers in the
range [0,1].

The second parameter passed to this function is a front end handle.
The only things it is permitted to do with this handle are to call
the front-end function called \cw{frontend_default_colour()} (see
\k{frontend-default-colour}) or the utility function called
\cw{game_mkhighlight()} (see \k{utils-game-mkhighlight}). (The
latter is a wrapper on the former, so front end implementors only
need to provide \cw{frontend_default_colour()}.) This allows
\cw{colours()} to take local configuration into account when
deciding on its own colour allocations. Most games use the front
end's default colour as their background, apart from a few which
depend on drawing relief highlights so they adjust the background
colour if it's too light for highlights to show up against it.

The first colour in the list is slightly special. The mid-end fills
the drawing area with it before the first call to \cw{redraw()} (see
\k{backend-redraw}).  Some front ends also use it fill the part of the
puzzle window outside the puzzle.  This means that it is usually
sensible to make colour 0 the background colour for the puzzle.

Note that the colours returned from this function are for
\e{drawing}, not for printing. Printing has an entirely different
colour allocation policy.

\S{backend-anim-length} \cw{anim_length()}

\c float (*anim_length)(const game_state *oldstate,
\c                      const game_state *newstate,
\c                      int dir, game_ui *ui);

This function is called when a move is made, undone or redone. It is
given the old and the new \c{game_state}, and its job is to decide
whether the transition between the two needs to be animated or can
be instant.

\c{oldstate} is the state that was current until this call;
\c{newstate} is the state that will be current after it. \c{dir}
specifies the chronological order of those states: if it is
positive, then the transition is the result of a move or a redo (and
so \c{newstate} is the later of the two moves), whereas if it is
negative then the transition is the result of an undo (so that
\c{newstate} is the \e{earlier} move).

If this function decides the transition should be animated, it
returns the desired length of the animation in seconds. If not, it
returns zero.

State changes as a result of a Restart operation are never animated;
the mid-end will handle them internally and never consult this
function at all. State changes as a result of Solve operations are
also not animated by default, although you can change this for a
particular game by setting a flag in \c{flags} (\k{backend-flags}).

The function is also passed a pointer to the local \c{game_ui}. It
may refer to information in here to help with its decision (see
\k{writing-conditional-anim} for an example of this), and/or it may
\e{write} information about the nature of the animation which will
be read later by \cw{redraw()}.

When this function is called, it may rely on \cw{changed_state()}
having been called previously, so if \cw{anim_length()} needs to
refer to information in the \c{game_ui}, then \cw{changed_state()}
is a reliable place to have set that information up.

Move animations do not inhibit further input events. If the user
continues playing before a move animation is complete, the animation
will be abandoned and the display will jump straight to the final
state.

\S{backend-flash-length} \cw{flash_length()}

\c float (*flash_length)(const game_state *oldstate,
\c                       const game_state *newstate,
\c                       int dir, game_ui *ui);

This function is called when a move is completed. (\q{Completed}
means that not only has the move been made, but any animation which
accompanied it has finished.) It decides whether the transition from
\c{oldstate} to \c{newstate} merits a \q{flash}.

A flash is much like a move animation, but it is \e{not} interrupted
by further user interface activity; it runs to completion in
parallel with whatever else might be going on on the display. The
only thing which will rush a flash to completion is another flash.

The purpose of flashes is to indicate that the game has been
completed. They were introduced as a separate concept from move
animations because of Net: the habit of most Net players (and
certainly me) is to rotate a tile into place and immediately lock
it, then move on to another tile. When you make your last move, at
the instant the final tile is rotated into place the screen starts
to flash to indicate victory \dash but if you then press the lock
button out of habit, then the move animation is cancelled, and the
victory flash does not complete. (And if you \e{don't} press the
lock button, the completed grid will look untidy because there will
be one unlocked square.) Therefore, I introduced a specific concept
of a \q{flash} which is separate from a move animation and can
proceed in parallel with move animations and any other display
activity, so that the victory flash in Net is not cancelled by that
final locking move.

The input parameters to \cw{flash_length()} are exactly the same as
the ones to \cw{anim_length()}: see \k{backend-anim-length}.

Just like \cw{anim_length()}, when this function is called, it may
rely on \cw{changed_state()} having been called previously, so if it
needs to refer to information in the \c{game_ui} then
\cw{changed_state()} is a reliable place to have set that
information up.

(Some games use flashes to indicate defeat as well as victory;
Mines, for example, flashes in a different colour when you tread on
a mine from the colour it uses when you complete the game. In order
to achieve this, its \cw{flash_length()} function has to store a
flag in the \c{game_ui} to indicate which flash type is required.)

\S{backend-get-cursor-location} \cw{get_cursor_location()}

\c void (*get_cursor_location)(const game_ui *ui,
\c                             const game_drawstate *ds,
\c                             const game_state *state,
\c                             const game_params *params,
\c                             int *x, int *y,
\c                             int *w, int *h);

This function queries the backend for the rectangular region
containing the cursor (in games that have one), or other region of
interest.

This function is called by only
\cw{midend_get_cursor_location()} (\k{midend-get-cursor-location}). Its
purpose is to allow front ends to query the location of the backend's
cursor. With knowledge of this location, a front end can, for example,
ensure that the region of interest remains visible if the puzzle is
too big to fit on the screen at once.

On returning, \cw{*x}, \cw{*y} should be set to the X and Y
coordinates of the upper-left corner of the rectangular region of
interest, and \cw{*w} and \cw{*h} should be the width and height of
that region, respectively. In the event that a cursor is not visible
on screen, this function should return and leave the return parameters
untouched \dash the midend will notice this. The backend need not
bother checking that \cw{x}, \cw{y}, \cw{w} and \cw{h} are
non-\cw{NULL} \dash the midend guarantees that they will not be.

Defining what constitutes a \q{region of interest} is left up to the
backend. If a game provides a conventional cursor \dash such as Mines,
Solo, or any of the other grid-based games \dash the most logical
choice is of course the location of the cursor itself. However, in
other cases such as Cube or Inertia, there is no \q{cursor} in the
conventional sense \dash the player instead controls an object moving
around the screen. In these cases, it makes sense to define the region
of interest as the bounding box of the player object or another
sensible region \dash such as the grid square the player is sitting on
in Cube.

If a backend does not provide a cursor mechanism at all, the backend
is free to provide an empty implementation of this function, or a
\cw{NULL} pointer in the \cw{game} structure \dash the midend will
notice either of these cases and behave appropriately.

\S{backend-status} \cw{status()}

\c int (*status)(const game_state *state);

This function returns a status value indicating whether the current
game is still in play, or has been won, or has been conclusively lost.
The mid-end uses this to implement \cw{midend_status()}
(\k{midend-status}).

The return value should be +1 if the game has been successfully
solved. If the game has been lost in a situation where further play is
unlikely, the return value should be -1. If neither is true (so play
is still ongoing), return zero.

Front ends may wish to use a non-zero status as a cue to proactively
offer the option of starting a new game. Therefore, back ends should
not return -1 if the game has been \e{technically} lost but undoing
and continuing is still a realistic possibility.

(For instance, games with hidden information such as Guess or Mines
might well return a non-zero status whenever they reveal the solution,
whether or not the player guessed it correctly, on the grounds that a
player would be unlikely to hide the solution and continue playing
after the answer was spoiled. On the other hand, games where you can
merely get into a dead end such as Same Game or Inertia might choose
to return 0 in that situation, on the grounds that the player would
quite likely press Undo and carry on playing.)

\S{backend-redraw} \cw{redraw()}

\c void (*redraw)(drawing *dr, game_drawstate *ds,
\c                const game_state *oldstate,
\c                const game_state *newstate,
\c                int dir, const game_ui *ui,
\c                float anim_time, float flash_time);

This function is responsible for actually drawing the contents of
the game window, and for redrawing every time the game state or the
\c{game_ui} changes.

The parameter \c{dr} is a drawing object which may be passed to the
drawing API functions (see \k{drawing} for documentation of the
drawing API). This function may not save \c{dr} and use it
elsewhere; it must only use it for calling back to the drawing API
functions within its own lifetime.

\c{ds} is the local \c{game_drawstate}, of course, and \c{ui} is the
local \c{game_ui}.

\c{newstate} is the semantically-current game state, and is always
non-\cw{NULL}. If \c{oldstate} is also non-\cw{NULL}, it means that
a move has recently been made and the game is still in the process
of displaying an animation linking the old and new states; in this
situation, \c{anim_time} will give the length of time (in seconds)
that the animation has already been running. If \c{oldstate} is
\cw{NULL}, then \c{anim_time} is unused (and will hopefully be set
to zero to avoid confusion).

\c{dir} specifies the chronological order of those states: if it is
positive, then the transition is the result of a move or a redo (and
so \c{newstate} is the later of the two moves), whereas if it is
negative then the transition is the result of an undo (so that
\c{newstate} is the \e{earlier} move). This allows move animations
that are not time-symmetric (such as Inertia, where gems are consumed
during the animation) to be drawn the right way round.

\c{flash_time}, if it is is non-zero, denotes that the game is in
the middle of a flash, and gives the time since the start of the
flash. See \k{backend-flash-length} for general discussion of
flashes.

The very first time this function is called for a new
\c{game_drawstate}, it is expected to redraw the \e{entire} drawing
area. Since this often involves drawing visual furniture which is
never subsequently altered, it is often simplest to arrange this by
having a special \q{first time} flag in the draw state, and
resetting it after the first redraw.  This function can assume that
the mid-end has filled the drawing area with colour 0 before the first
call.

When this function (or any subfunction) calls the drawing API, it is
expected to pass colour indices which were previously defined by the
\cw{colours()} function.

\H{backend-printing} Printing functions

This section discusses the back end functions that deal with
printing puzzles out on paper.

\S{backend-can-print} \c{can_print}

\c bool can_print;

This flag is set to \cw{true} if the puzzle is capable of printing
itself on paper. (This makes sense for some puzzles, such as Solo,
which can be filled in with a pencil. Other puzzles, such as
Twiddle, inherently involve moving things around and so would not
make sense to print.)

If this flag is \cw{false}, then the functions \cw{print_size()}
and \cw{print()} will never be called and can be \cw{NULL}.

\S{backend-can-print-in-colour} \c{can_print_in_colour}

\c bool can_print_in_colour;

This flag is set to \cw{true} if the puzzle is capable of printing
itself differently when colour is available. For example, Map can
actually print coloured regions in different \e{colours} rather than
resorting to cross-hatching.

If the \c{can_print} flag is \cw{false}, then this flag will be
ignored.

\S{backend-print-size} \cw{print_size()}

\c void (*print_size)(const game_params *params, const game_ui *ui,
\c                    float *x, float *y);

This function is passed a \c{game_params} structure and a tile size.
It returns, in \c{*x} and \c{*y}, the preferred size in
\e{millimetres} of that puzzle if it were to be printed out on paper.

If the \c{can_print} flag is \cw{false}, this function will never be
called.

\S{backend-print} \cw{print()}

\c void (*print)(drawing *dr, const game_state *state,
\c               const game_ui *ui, int tilesize);

This function is called when a puzzle is to be printed out on paper.
It should use the drawing API functions (see \k{drawing}) to print
itself.

This function is separate from \cw{redraw()} because it is often
very different:

\b The printing function may not depend on pixel accuracy, since
printer resolution is variable. Draw as if your canvas had infinite
resolution.

\b The printing function sometimes needs to display things in a
completely different style. Net, for example, is very different as
an on-screen puzzle and as a printed one.

\b The printing function is often much simpler since it has no need
to deal with repeated partial redraws.

However, there's no reason the printing and redraw functions can't
share some code if they want to.

When this function (or any subfunction) calls the drawing API, the
colour indices it passes should be colours which have been allocated
by the \cw{print_*_colour()} functions within this execution of
\cw{print()}. This is very different from the fixed small number of
colours used in \cw{redraw()}, because printers do not have a
limitation on the total number of colours that may be used. Some
puzzles' printing functions might wish to allocate only one \q{ink}
colour and use it for all drawing; others might wish to allocate
\e{more} colours than are used on screen.

One possible colour policy worth mentioning specifically is that a
puzzle's printing function might want to allocate the \e{same}
colour indices as are used by the redraw function, so that code
shared between drawing and printing does not have to keep switching
its colour indices. In order to do this, the simplest thing is to
make use of the fact that colour indices returned from
\cw{print_*_colour()} are guaranteed to be in increasing order from
zero. So if you have declared an \c{enum} defining three colours
\cw{COL_BACKGROUND}, \cw{COL_THIS} and \cw{COL_THAT}, you might then
write

\c int c;
\c c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
\c c = print_mono_colour(dr, 0); assert(c == COL_THIS);
\c c = print_mono_colour(dr, 0); assert(c == COL_THAT);

If the \c{can_print} flag is \cw{false}, this function will never be
called.

\H{backend-misc} Miscellaneous

\S{backend-can-format-as-text-ever} \c{can_format_as_text_ever}

\c bool can_format_as_text_ever;

This field is \cw{true} if the game supports formatting a
game state as ASCII text (typically ASCII art) for copying to the
clipboard and pasting into other applications. If it is \cw{false},
front ends will not offer the \q{Copy} command at all.

If this field is \cw{true}, the game does not necessarily have to
support text formatting for \e{all} games: e.g. a game which can be
played on a square grid or a triangular one might only support copy
and paste for the former, because triangular grids in ASCII art are
just too difficult.

If this field is \cw{false}, the functions
\cw{can_format_as_text_now()} (\k{backend-can-format-as-text-now})
and \cw{text_format()} (\k{backend-text-format}) are never called
and can be \cw{NULL}.

\S{backend-can-format-as-text-now} \c{can_format_as_text_now()}

\c bool (*can_format_as_text_now)(const game_params *params);

This function is passed a \c{game_params}, and returns \cw{true} if
the game can support ASCII text output for this particular game type.
If it returns \cw{false}, front ends will grey out or otherwise
disable the \q{Copy} command.

Games may enable and disable the copy-and-paste function for
different game \e{parameters}, but are currently constrained to
return the same answer from this function for all game \e{states}
sharing the same parameters. In other words, the \q{Copy} function
may enable or disable itself when the player changes game preset,
but will never change during play of a single game or when another
game of exactly the same type is generated.

This function should not take into account aspects of the game
parameters which are not encoded by \cw{encode_params()}
(\k{backend-encode-params}) when the \c{full} parameter is set to
\cw{false}. Such parameters will not necessarily match up between a
call to this function and a subsequent call to \cw{text_format()}
itself. (For instance, game \e{difficulty} should not affect whether
the game can be copied to the clipboard. Only the actual visible
\e{shape} of the game can affect that.)

\S{backend-text-format} \cw{text_format()}

\c char *(*text_format)(const game_state *state);

This function is passed a \c{game_state}, and returns a newly
allocated C string containing an ASCII representation of that game
state. It is used to implement the \q{Copy} operation in many front
ends.

This function will only ever be called if the back end field
\c{can_format_as_text_ever} (\k{backend-can-format-as-text-ever}) is
\cw{true} \e{and} the function \cw{can_format_as_text_now()}
(\k{backend-can-format-as-text-now}) has returned \cw{true} for the
currently selected game parameters.

The returned string may contain line endings (and will probably want
to), using the normal C internal \cq{\\n} convention. For
consistency between puzzles, all multi-line textual puzzle
representations should \e{end} with a newline as well as containing
them internally. (There are currently no puzzles which have a
one-line ASCII representation, so there's no precedent yet for
whether that should come with a newline or not.)

\S{backend-wants-statusbar} \cw{wants_statusbar}

\c bool wants_statusbar;

This field is set to \cw{true} if the puzzle has a use for a textual
status line (to display score, completion status, currently active
tiles, etc). If the \c{redraw()} function ever intends to call
\c{status_bar()} in the drawing API (\k{drawing-status-bar}), then it
should set this flag to \c{true}.

\S{backend-is-timed} \c{is_timed}

\c bool is_timed;

This field is \cw{true} if the puzzle is time-critical. If
so, the mid-end will maintain a game timer while the user plays.

If this field is \cw{false}, then \cw{timing_state()} will never be
called and can be \cw{NULL}.

\S{backend-timing-state} \cw{timing_state()}

\c bool (*timing_state)(const game_state *state, game_ui *ui);

This function is passed the current \c{game_state} and the local
\c{game_ui}; it returns \cw{true} if the game timer should currently
be running.

A typical use for the \c{game_ui} in this function is to note when
the game was first completed (by setting a flag in
\cw{changed_state()} \dash see \k{backend-changed-state}), and
freeze the timer thereafter so that the user can undo back through
their solution process without altering their time.

\S{backend-request-keys} \cw{request_keys()}

\c key_label *(*request_keys)(const game_params *params, int *nkeys);

This function returns a dynamically allocated array of \cw{key_label}
items containing the buttons the back end deems absolutely
\e{necessary} for gameplay, not an exhaustive list of every button the
back end could accept. For example, Keen only returns the digits up to
the game size and the backspace character, \cw{\\b}, even though it
\e{could} accept \cw{M}, as only these buttons are actually needed to
play the game. Each \cw{key_label} item contains the following fields:

\c struct key_label {
\c     char *label; /* label for frontend use */
\c     int button; /* button to pass to midend */
\c } key_label;

The \cw{label} field of this structure can (and often will) be set by
the backend to \cw{NULL}, in which case the midend will instead call
\c{button2label()} (\k{utils-button2label}) and fill in a generic
label. The \cw{button} field is the associated code that can be passed
to the midend when the frontend deems appropriate.

If \cw{label} is not \cw{NULL}, then it's a dynamically allocated
string. Therefore, freeing an array of these structures needs more
than just a single free operatio. The function \c{free_keys()}
(\k{utils-free-keys}) can be used to free a whole array of these
structures conveniently.

The backend should set \cw{*nkeys} to the number of elements in the
returned array.

The field for this function point in the \cw{game} structure might be
set to \cw{NULL} (and indeed it is for the majority of the games) to
indicate that no additional buttons (apart from the cursor keys) are
required to play the game.

This function should not be called directly by frontends. Instead,
frontends should use \cw{midend_request_keys()}
(\k{midend-request-keys}).

\S{backend-current-key-label} \cw{current_key_label()}

\c const char *(*current_key_label)(const game_ui *ui,
\c                                  const game_state *state,
\c                                  int button);

This function is called to ask the back-end how certain keys should be
labelled on platforms (such a feature phones) where this is
conventional.
These labels are expected to reflect what the keys will do right now,
so they can change depending on the game and UI state.

The \c{ui} and \c{state} arguments describe the state of the game for
which key labels are required.
The \c{button} argument is the same as the one passed to
\cw{interpret_move()}.
At present, the only values of \c{button} that can be passed to
\cw{current_key_label()} are \cw{CURSOR_SELECT} and \cw{CURSOR_SELECT2}.
The return value is a short string describing what the requested key
will do if pressed.
Usually the string should be a static string constant.
If it's really necessary to use a dynamically-allocated string, it
should remain valid until the next call to \cw{current_key_label()} or
\cw{free_ui()} with the same \cw{game_ui} (so it can be referenced from
the \cw{game_ui} and freed at the next one of those calls).

There's no fixed upper limit on the length of string that this
function can return, but more than about 12 characters is likely to
cause problems for front-ends.  If two buttons have the same effect,
their labels should be identical so that the front end can detect
this.  Similarly, keys that do different things should have different
labels.  The label should be an empty string (\cw{""}) if the key does
nothing.

Like \cw{request_keys()}, the \cw{current_key_label} pointer in the
\c{game} structure is allowed to be \cw{NULL}, in which case the
mid-end will treat it as though it always returned \cw{""}.

\S{backend-flags} \c{flags}

\c int flags;

This field contains miscellaneous per-backend flags. It consists of
the bitwise OR of some combination of the following:

\dt \cw{BUTTON_BEATS(x,y)}

\dd Given any \cw{x} and \cw{y} from the set \{\cw{LEFT_BUTTON},
\cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}\}, this macro evaluates to a
bit flag which indicates that when buttons \cw{x} and \cw{y} are
both pressed simultaneously, the mid-end should consider \cw{x} to
have priority. (In the absence of any such flags, the mid-end will
always consider the most recently pressed button to have priority.)

\dt \cw{SOLVE_ANIMATES}

\dd This flag indicates that moves generated by \cw{solve()}
(\k{backend-solve}) are candidates for animation just like any other
move. For most games, solve moves should not be animated, so the
mid-end doesn't even bother calling \cw{anim_length()}
(\k{backend-anim-length}), thus saving some special-case code in
each game. On the rare occasion that animated solve moves are
actually required, you can set this flag.

\dt \cw{REQUIRE_RBUTTON}

\dd This flag indicates that the puzzle cannot be usefully played
without the use of mouse buttons other than the left one. On some
PDA platforms, this flag is used by the front end to enable
right-button emulation through an appropriate gesture. Note that a
puzzle is not required to set this just because it \e{uses} the
right button, but only if its use of the right button is critical to
playing the game. (Slant, for example, uses the right button to
cycle through the three square states in the opposite order from the
left button, and hence can manage fine without it.)

\dt \cw{REQUIRE_NUMPAD}

\dd This flag indicates that the puzzle cannot be usefully played
without the use of number-key input. On some PDA platforms it causes
an emulated number pad to appear on the screen. Similarly to
\cw{REQUIRE_RBUTTON}, a puzzle need not specify this simply if its
use of the number keys is not critical.

\H{backend-initiative} Things a back end may do on its own initiative

This section describes a couple of things that a back end may choose
to do by calling functions elsewhere in the program, which would not
otherwise be obvious.

\S{backend-newrs} Create a random state

If a back end needs random numbers at some point during normal play,
it can create a fresh \c{random_state} by first calling
\c{get_random_seed} (\k{frontend-get-random-seed}) and then passing
the returned seed data to \cw{random_new()}.

This is likely not to be what you want. If a puzzle needs randomness
in the middle of play, it's likely to be more sensible to store some
sort of random state within the \c{game_state}, so that the random
numbers are tied to the particular game state and hence the player
can't simply keep undoing their move until they get numbers they
like better.

This facility is currently used only in Net, to implement the
\q{jumble} command, which sets every unlocked tile to a new random
orientation. This randomness \e{is} a reasonable use of the feature,
because it's non-adversarial \dash there's no advantage to the user
in getting different random numbers.

\S{backend-supersede} Supersede its own game description

In response to a move, a back end is (reluctantly) permitted to call
\cw{midend_supersede_game_desc()}:

\c void midend_supersede_game_desc(midend *me,
\c                                 char *desc, char *privdesc);

When the user selects \q{New Game}, the mid-end calls
\cw{new_desc()} (\k{backend-new-desc}) to get a new game
description, and (as well as using that to generate an initial game
state) stores it for the save file and for telling to the user. The
function above overwrites that game description, and also splits it
in two. \c{desc} becomes the new game description which is provided
to the user on request, and is also the one used to construct a new
initial game state if the user selects \q{Restart}. \c{privdesc} is
a \q{private} game description, used to reconstruct the game's
initial state when reloading.

The distinction between the two, as well as the need for this
function at all, comes from Mines. Mines begins with a blank grid
and no idea of where the mines actually are; \cw{new_desc()} does
almost no work in interactive mode, and simply returns a string
encoding the \c{random_state}. When the user first clicks to open a
tile, \e{then} Mines generates the mine positions, in such a way
that the game is soluble from that starting point. Then it uses this
function to supersede the random-state game description with a
proper one. But it needs two: one containing the initial click
location (because that's what you want to happen if you restart the
game, and also what you want to send to a friend so that they play
\e{the same game} as you), and one without the initial click
location (because when you save and reload the game, you expect to
see the same blank initial state as you had before saving).

I should stress again that this function is a horrid hack. Nobody
should use it if they're not Mines; if you think you need to use it,
think again repeatedly in the hope of finding a better way to do
whatever it was you needed to do.

\C{drawing} The drawing API

The back end function \cw{redraw()} (\k{backend-redraw}) is required
to draw the puzzle's graphics on the window's drawing area. The back
end function \cw{print()} similarly draws the puzzle on paper, if the
puzzle is printable. To do this portably, the back end is provided
with a drawing API allowing it to talk directly to the front end. In
this chapter I document that API, both for the benefit of back end
authors trying to use it and for front end authors trying to implement
it.

The drawing API as seen by the back end is a collection of global
functions, each of which takes a pointer to a \c{drawing} structure
(a \q{drawing object}). These objects are supplied as parameters to
the back end's \cw{redraw()} and \cw{print()} functions.

In fact these global functions are not implemented directly by the
front end; instead, they are implemented centrally in \c{drawing.c}
and form a small piece of middleware. The drawing API as supplied by
the front end is a structure containing a set of function pointers,
plus a \cq{void *} handle which is passed to each of those
functions. This enables a single front end to switch between
multiple implementations of the drawing API if necessary. For
example, the Windows API supplies a printing mechanism integrated
into the same GDI which deals with drawing in windows, and therefore
the same API implementation can handle both drawing and printing;
but on Unix, the most common way for applications to print is by
producing PostScript output directly, and although it would be
\e{possible} to write a single (say) \cw{draw_rect()} function which
checked a global flag to decide whether to do GTK drawing operations
or output PostScript to a file, it's much nicer to have two separate
functions and switch between them as appropriate.

When drawing, the puzzle window is indexed by pixel coordinates,
with the top left pixel defined as \cw{(0,0)} and the bottom right
pixel \cw{(w-1,h-1)}, where \c{w} and \c{h} are the width and height
values returned by the back end function \cw{compute_size()}
(\k{backend-compute-size}).

When printing, the puzzle's print area is indexed in exactly the
same way (with an arbitrary tile size provided by the printing
module \c{printing.c}), to facilitate sharing of code between the
drawing and printing routines. However, when printing, puzzles may
no longer assume that the coordinate unit has any relationship to a
pixel; the printer's actual resolution might very well not even be
known at print time, so the coordinate unit might be smaller or
larger than a pixel. Puzzles' print functions should restrict
themselves to drawing geometric shapes rather than fiddly pixel
manipulation.

\e{Puzzles' redraw functions may assume that the surface they draw
on is persistent}. It is the responsibility of every front end to
preserve the puzzle's window contents in the face of GUI window
expose issues and similar. It is not permissible to request that the
back end redraw any part of a window that it has already drawn,
unless something has actually changed as a result of making moves in
the puzzle.

Most front ends accomplish this by having the drawing routines draw
on a stored bitmap rather than directly on the window, and copying
the bitmap to the window every time a part of the window needs to be
redrawn. Therefore, it is vitally important that whenever the back
end does any drawing it informs the front end of which parts of the
window it has accessed, and hence which parts need repainting. This
is done by calling \cw{draw_update()} (\k{drawing-draw-update}).

Persistence of old drawing is convenient. However, a puzzle should
be very careful about how it updates its drawing area. The problem
is that some front ends do anti-aliased drawing: rather than simply
choosing between leaving each pixel untouched or painting it a
specified colour, an antialiased drawing function will \e{blend} the
original and new colours in pixels at a figure's boundary according
to the proportion of the pixel occupied by the figure (probably
modified by some heuristic fudge factors). All of this produces a
smoother appearance for curves and diagonal lines.

An unfortunate effect of drawing an anti-aliased figure repeatedly
is that the pixels around the figure's boundary come steadily more
saturated with \q{ink} and the boundary appears to \q{spread out}.
Worse, redrawing a figure in a different colour won't fully paint
over the old boundary pixels, so the end result is a rather ugly
smudge.

A good strategy to avoid unpleasant anti-aliasing artifacts is to
identify a number of rectangular areas which need to be redrawn,
clear them to the background colour, and then redraw their contents
from scratch, being careful all the while not to stray beyond the
boundaries of the original rectangles. The \cw{clip()} function
(\k{drawing-clip}) comes in very handy here. Games based on a square
grid can often do this fairly easily. Other games may need to be
somewhat more careful. For example, Loopy's redraw function first
identifies portions of the display which need to be updated. Then,
if the changes are fairly well localised, it clears and redraws a
rectangle containing each changed area. Otherwise, it gives up and
redraws the entire grid from scratch.

It is possible to avoid clearing to background and redrawing from
scratch if one is very careful about which drawing functions one
uses: if a function is documented as not anti-aliasing under some
circumstances, you can rely on each pixel in a drawing either being
left entirely alone or being set to the requested colour, with no
blending being performed.

In the following sections I first discuss the drawing API as seen by
the back end, and then the \e{almost} identical function-pointer
form seen by the front end.

\H{drawing-backend} Drawing API as seen by the back end

This section documents the back-end drawing API, in the form of
functions which take a \c{drawing} object as an argument.

\S{drawing-draw-rect} \cw{draw_rect()}

\c void draw_rect(drawing *dr, int x, int y, int w, int h,
\c                int colour);

Draws a filled rectangle in the puzzle window.

\c{x} and \c{y} give the coordinates of the top left pixel of the
rectangle. \c{w} and \c{h} give its width and height. Thus, the
horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
inclusive, and the vertical extent from \c{y} to \c{y+h-1}
inclusive.

\c{colour} is an integer index into the colours array returned by
the back end function \cw{colours()} (\k{backend-colours}).

There is no separate pixel-plotting function. If you want to plot a
single pixel, the approved method is to use \cw{draw_rect()} with
width and height set to 1.

Unlike many of the other drawing functions, this function is
guaranteed to be pixel-perfect: the rectangle will be sharply
defined and not anti-aliased or anything like that.

This function may be used for both drawing and printing.

\S{drawing-draw-rect-outline} \cw{draw_rect_outline()}

\c void draw_rect_outline(drawing *dr, int x, int y, int w, int h,
\c                        int colour);

Draws an outline rectangle in the puzzle window.

\c{x} and \c{y} give the coordinates of the top left pixel of the
rectangle. \c{w} and \c{h} give its width and height. Thus, the
horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
inclusive, and the vertical extent from \c{y} to \c{y+h-1}
inclusive.

\c{colour} is an integer index into the colours array returned by
the back end function \cw{colours()} (\k{backend-colours}).

From a back end perspective, this function may be considered to be
part of the drawing API. However, front ends are not required to
implement it, since it is actually implemented centrally (in
\cw{misc.c}) as a wrapper on \cw{draw_polygon()}.

This function may be used for both drawing and printing.

\S{drawing-draw-rect-corner} \cw{draw_rect_corners()}

\c void draw_rect_corners(drawing *dr, int cx, int cy, int r, int col);

Draws four L-shapes at the corners of a square, in the manner of a
target reticule. This is a convenience function for back ends to use
to display a keyboard cursor (if they want one in that style).

\c{cx} and \c{cy} give the coordinates of the centre of the square.
\c{r} is half the side length of the square, so that the corners are
at \cw{(cx-r,cy-r)}, \cw{(cx+r,cy-r)}, \cw{(cx-r,cy+r)} and
\cw{(cx+r,cy+r)}.

\c{colour} is an integer index into the colours array returned by
the back end function \cw{colours()} (\k{backend-colours}).

\S{drawing-draw-line} \cw{draw_line()}

\c void draw_line(drawing *dr, int x1, int y1, int x2, int y2,
\c                int colour);

Draws a straight line in the puzzle window.

\c{x1} and \c{y1} give the coordinates of one end of the line.
\c{x2} and \c{y2} give the coordinates of the other end. The line
drawn includes both those points.

\c{colour} is an integer index into the colours array returned by
the back end function \cw{colours()} (\k{backend-colours}).

Some platforms may perform anti-aliasing on this function.
Therefore, do not assume that you can erase a line by drawing the
same line over it in the background colour; anti-aliasing might lead
to perceptible ghost artefacts around the vanished line. Horizontal
and vertical lines, however, are pixel-perfect and not anti-aliased.

This function may be used for both drawing and printing.

\S{drawing-draw-polygon} \cw{draw_polygon()}

\c void draw_polygon(drawing *dr, const int *coords, int npoints,
\c                   int fillcolour, int outlinecolour);

Draws an outlined or filled polygon in the puzzle window.

\c{coords} is an array of \cw{(2*npoints)} integers, containing the
\c{x} and \c{y} coordinates of \c{npoints} vertices.

\c{fillcolour} and \c{outlinecolour} are integer indices into the
colours array returned by the back end function \cw{colours()}
(\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
indicate that the polygon should be outlined only.

The polygon defined by the specified list of vertices is first
filled in \c{fillcolour}, if specified, and then outlined in
\c{outlinecolour}.

\c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
(and front ends are permitted to enforce this by assertion). This is
because different platforms disagree on whether a filled polygon
should include its boundary line or not, so drawing \e{only} a
filled polygon would have non-portable effects. If you want your
filled polygon not to have a visible outline, you must set
\c{outlinecolour} to the same as \c{fillcolour}.

Some platforms may perform anti-aliasing on this function.
Therefore, do not assume that you can erase a polygon by drawing the
same polygon over it in the background colour. Also, be prepared for
the polygon to extend a pixel beyond its obvious bounding box as a
result of this; if you really need it not to do this to avoid
interfering with other delicate graphics, you should probably use
\cw{clip()} (\k{drawing-clip}). You can rely on horizontal and
vertical lines not being anti-aliased.

This function may be used for both drawing and printing.

\S{drawing-draw-circle} \cw{draw_circle()}

\c void draw_circle(drawing *dr, int cx, int cy, int radius,
\c                  int fillcolour, int outlinecolour);

Draws an outlined or filled circle in the puzzle window.

\c{cx} and \c{cy} give the coordinates of the centre of the circle.
\c{radius} gives its radius. The total horizontal pixel extent of
the circle is from \c{cx-radius+1} to \c{cx+radius-1} inclusive, and
the vertical extent similarly around \c{cy}.

\c{fillcolour} and \c{outlinecolour} are integer indices into the
colours array returned by the back end function \cw{colours()}
(\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
indicate that the circle should be outlined only.

The circle is first filled in \c{fillcolour}, if specified, and then
outlined in \c{outlinecolour}.

\c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
(and front ends are permitted to enforce this by assertion). This is
because different platforms disagree on whether a filled circle
should include its boundary line or not, so drawing \e{only} a
filled circle would have non-portable effects. If you want your
filled circle not to have a visible outline, you must set
\c{outlinecolour} to the same as \c{fillcolour}.

Some platforms may perform anti-aliasing on this function.
Therefore, do not assume that you can erase a circle by drawing the
same circle over it in the background colour. Also, be prepared for
the circle to extend a pixel beyond its obvious bounding box as a
result of this; if you really need it not to do this to avoid
interfering with other delicate graphics, you should probably use
\cw{clip()} (\k{drawing-clip}).

This function may be used for both drawing and printing.

\S{drawing-draw-thick-line} \cw{draw_thick_line()}

\c void draw_thick_line(drawing *dr, float thickness,
\c                      float x1, float y1, float x2, float y2,
\c                      int colour)

Draws a line in the puzzle window, giving control over the line's
thickness.

\c{x1} and \c{y1} give the coordinates of one end of the line.
\c{x2} and \c{y2} give the coordinates of the other end.
\c{thickness} gives the thickness of the line, in pixels.

Note that the coordinates and thickness are floating-point: the
continuous coordinate system is in effect here. It's important to
be able to address points with better-than-pixel precision in this
case, because one can't otherwise properly express the endpoints of
lines with both odd and even thicknesses.

Some platforms may perform anti-aliasing on this function. The
precise pixels affected by a thick-line drawing operation may vary
between platforms, and no particular guarantees are provided.
Indeed, even horizontal or vertical lines may be anti-aliased.

This function may be used for both drawing and printing.

If the specified thickness is less than 1.0, 1.0 is used.
This ensures that thin lines are visible even at small scales.

\S{drawing-draw-text} \cw{draw_text()}

\c void draw_text(drawing *dr, int x, int y, int fonttype,
\c                int fontsize, int align, int colour,
\c                const char *text);

Draws text in the puzzle window.

\c{x} and \c{y} give the coordinates of a point. The relation of
this point to the location of the text is specified by \c{align},
which is a bitwise OR of horizontal and vertical alignment flags:

\dt \cw{ALIGN_VNORMAL}

\dd Indicates that \c{y} is aligned with the baseline of the text.

\dt \cw{ALIGN_VCENTRE}

\dd Indicates that \c{y} is aligned with the vertical centre of the
text. (In fact, it's aligned with the vertical centre of normal
\e{capitalised} text: displaying two pieces of text with
\cw{ALIGN_VCENTRE} at the same \cw{y}-coordinate will cause their
baselines to be aligned with one another, even if one is an ascender
and the other a descender.)

\dt \cw{ALIGN_HLEFT}

\dd Indicates that \c{x} is aligned with the left-hand end of the
text.

\dt \cw{ALIGN_HCENTRE}

\dd Indicates that \c{x} is aligned with the horizontal centre of
the text.

\dt \cw{ALIGN_HRIGHT}

\dd Indicates that \c{x} is aligned with the right-hand end of the
text.

\c{fonttype} is either \cw{FONT_FIXED} or \cw{FONT_VARIABLE}, for a
monospaced or proportional font respectively. (No more detail than
that may be specified; it would only lead to portability issues
between different platforms.)

\c{fontsize} is the desired size, in pixels, of the text. This size
corresponds to the overall point size of the text, not to any
internal dimension such as the cap-height.

\c{colour} is an integer index into the colours array returned by
the back end function \cw{colours()} (\k{backend-colours}).

This function may be used for both drawing and printing.

The character set used to encode the text passed to this function is
specified \e{by the drawing object}, although it must be a superset
of ASCII. If a puzzle wants to display text that is not contained in
ASCII, it should use the \cw{text_fallback()} function
(\k{drawing-text-fallback}) to query the drawing object for an
appropriate representation of the characters it wants.

\S{drawing-text-fallback} \cw{text_fallback()}

\c char *text_fallback(drawing *dr, const char *const *strings,
\c                     int nstrings);

This function is used to request a translation of UTF-8 text into
whatever character encoding is expected by the drawing object's
implementation of \cw{draw_text()}.

The input is a list of strings encoded in UTF-8: \cw{nstrings} gives
the number of strings in the list, and \cw{strings[0]},
\cw{strings[1]}, ..., \cw{strings[nstrings-1]} are the strings
themselves.

The returned string (which is dynamically allocated and must be
freed when finished with) is derived from the first string in the
list that the drawing object expects to be able to display reliably;
it will consist of that string translated into the character set
expected by \cw{draw_text()}.

Drawing implementations are not required to handle anything outside
ASCII, but are permitted to assume that \e{some} string will be
successfully translated. So every call to this function must include
a string somewhere in the list (presumably the last element) which
consists of nothing but ASCII, to be used by any front end which
cannot handle anything else.

For example, if a puzzle wished to display a string including a
multiplication sign (U+00D7 in Unicode, represented by the bytes C3
97 in UTF-8), it might do something like this:

\c static const char *const times_signs[] = { "\xC3\x97", "x" };
\c char *times_sign = text_fallback(dr, times_signs, 2);
\c sprintf(buffer, "%d%s%d", width, times_sign, height);
\c sfree(times_sign);
\c draw_text(dr, x, y, font, size, align, colour, buffer);
\c sfree(buffer);

which would draw a string with a times sign in the middle on
platforms that support it, and fall back to a simple ASCII \cq{x}
where there was no alternative.

\S{drawing-clip} \cw{clip()}

\c void clip(drawing *dr, int x, int y, int w, int h);

Establishes a clipping rectangle in the puzzle window.

\c{x} and \c{y} give the coordinates of the top left pixel of the
clipping rectangle. \c{w} and \c{h} give its width and height. Thus,
the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
inclusive, and the vertical extent from \c{y} to \c{y+h-1}
inclusive. (These are exactly the same semantics as
\cw{draw_rect()}.)

After this call, no drawing operation will affect anything outside
the specified rectangle. The effect can be reversed by calling
\cw{unclip()} (\k{drawing-unclip}). The clipping rectangle is
pixel-perfect: pixels within the rectangle are affected as usual by
drawing functions; pixels outside are completely untouched.

Back ends should not assume that a clipping rectangle will be
automatically cleared up by the front end if it's left lying around;
that might work on current front ends, but shouldn't be relied upon.
Always explicitly call \cw{unclip()}.

This function may be used for both drawing and printing.

\S{drawing-unclip} \cw{unclip()}

\c void unclip(drawing *dr);

Reverts the effect of a previous call to \cw{clip()}. After this
call, all drawing operations will be able to affect the entire
puzzle window again.

This function may be used for both drawing and printing.

\S{drawing-draw-update} \cw{draw_update()}

\c void draw_update(drawing *dr, int x, int y, int w, int h);

Informs the front end that a rectangular portion of the puzzle
window has been drawn on and needs to be updated.

\c{x} and \c{y} give the coordinates of the top left pixel of the
update rectangle. \c{w} and \c{h} give its width and height. Thus,
the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
inclusive, and the vertical extent from \c{y} to \c{y+h-1}
inclusive. (These are exactly the same semantics as
\cw{draw_rect()}.)

The back end redraw function \e{must} call this function to report
any changes it has made to the window. Otherwise, those changes may
not become immediately visible, and may then appear at an
unpredictable subsequent time such as the next time the window is
covered and re-exposed.

This function is only important when drawing. It may be called when
printing as well, but doing so is not compulsory, and has no effect.
(So if you have a shared piece of code between the drawing and
printing routines, that code may safely call \cw{draw_update()}.)

\S{drawing-status-bar} \cw{status_bar()}

\c void status_bar(drawing *dr, const char *text);

Sets the text in the game's status bar to \c{text}. The text is copied
from the supplied buffer, so the caller is free to deallocate or
modify the buffer after use.

(This function is not exactly a \e{drawing} function, but it shares
with the drawing API the property that it may only be called from
within the back end redraw function. And it's implemented by front
ends via the \c{drawing_api} function pointer table. So this is the
best place to document it.)

The supplied text is filtered through the mid-end for optional
rewriting before being passed on to the front end; the mid-end will
prepend the current game time if the game is timed (and may in
future perform other rewriting if it seems like a good idea).

This function is for drawing only; it must never be called during
printing.

\S{drawing-blitter} Blitter functions

This section describes a group of related functions which save and
restore a section of the puzzle window. This is most commonly used
to implement user interfaces involving dragging a puzzle element
around the window: at the end of each call to \cw{redraw()}, if an
object is currently being dragged, the back end saves the window
contents under that location and then draws the dragged object, and
at the start of the next \cw{redraw()} the first thing it does is to
restore the background.

The front end defines an opaque type called a \c{blitter}, which is
capable of storing a rectangular area of a specified size.

Blitter functions are for drawing only; they must never be called
during printing.

\S2{drawing-blitter-new} \cw{blitter_new()}

\c blitter *blitter_new(drawing *dr, int w, int h);

Creates a new blitter object which stores a rectangle of size \c{w}
by \c{h} pixels. Returns a pointer to the blitter object.

Blitter objects are best stored in the \c{game_drawstate}. A good
time to create them is in the \cw{set_size()} function
(\k{backend-set-size}), since it is at this point that you first
know how big a rectangle they will need to save.

\S2{drawing-blitter-free} \cw{blitter_free()}

\c void blitter_free(drawing *dr, blitter *bl);

Disposes of a blitter object. Best called in \cw{free_drawstate()}.
(However, check that the blitter object is not \cw{NULL} before
attempting to free it; it is possible that a draw state might be
created and freed without ever having \cw{set_size()} called on it
in between.)

\S2{drawing-blitter-save} \cw{blitter_save()}

\c void blitter_save(drawing *dr, blitter *bl, int x, int y);

This is a true drawing API function, in that it may only be called
from within the game redraw routine. It saves a rectangular portion
of the puzzle window into the specified blitter object.

\c{x} and \c{y} give the coordinates of the top left corner of the
saved rectangle. The rectangle's width and height are the ones
specified when the blitter object was created.

This function is required to cope and do the right thing if \c{x}
and \c{y} are out of range. (The right thing probably means saving
whatever part of the blitter rectangle overlaps with the visible
area of the puzzle window.)

\S2{drawing-blitter-load} \cw{blitter_load()}

\c void blitter_load(drawing *dr, blitter *bl, int x, int y);

This is a true drawing API function, in that it may only be called
from within the game redraw routine. It restores a rectangular
portion of the puzzle window from the specified blitter object.

\c{x} and \c{y} give the coordinates of the top left corner of the
rectangle to be restored. The rectangle's width and height are the
ones specified when the blitter object was created.

Alternatively, you can specify both \c{x} and \c{y} as the special
value \cw{BLITTER_FROMSAVED}, in which case the rectangle will be
restored to exactly where it was saved from. (This is probably what
you want to do almost all the time, if you're using blitters to
implement draggable puzzle elements.)

This function is required to cope and do the right thing if \c{x}
and \c{y} (or the equivalent ones saved in the blitter) are out of
range. (The right thing probably means restoring whatever part of
the blitter rectangle overlaps with the visible area of the puzzle
window.)

If this function is called on a blitter which had previously been
saved from a partially out-of-range rectangle, then the parts of the
saved bitmap which were not visible at save time are undefined. If
the blitter is restored to a different position so as to make those
parts visible, the effect on the drawing area is undefined.

\S{print-mono-colour} \cw{print_mono_colour()}

\c int print_mono_colour(drawing *dr, int grey);

This function allocates a colour index for a simple monochrome
colour during printing.

\c{grey} must be 0 or 1. If \c{grey} is 0, the colour returned is
black; if \c{grey} is 1, the colour is white.

\S{print-grey-colour} \cw{print_grey_colour()}

\c int print_grey_colour(drawing *dr, float grey);

This function allocates a colour index for a grey-scale colour
during printing.

\c{grey} may be any number between 0 (black) and 1 (white); for
example, 0.5 indicates a medium grey.

The chosen colour will be rendered to the limits of the printer's
halftoning capability.

\S{print-hatched-colour} \cw{print_hatched_colour()}

\c int print_hatched_colour(drawing *dr, int hatch);

This function allocates a colour index which does not represent a
literal \e{colour}. Instead, regions shaded in this colour will be
hatched with parallel lines. The \c{hatch} parameter defines what
type of hatching should be used in place of this colour:

\dt \cw{HATCH_SLASH}

\dd This colour will be hatched by lines slanting to the right at 45
degrees. 

\dt \cw{HATCH_BACKSLASH}

\dd This colour will be hatched by lines slanting to the left at 45
degrees.

\dt \cw{HATCH_HORIZ}

\dd This colour will be hatched by horizontal lines.

\dt \cw{HATCH_VERT}

\dd This colour will be hatched by vertical lines.

\dt \cw{HATCH_PLUS}

\dd This colour will be hatched by criss-crossing horizontal and
vertical lines.

\dt \cw{HATCH_X}

\dd This colour will be hatched by criss-crossing diagonal lines.

Colours defined to use hatching may not be used for drawing lines or
text; they may only be used for filling areas. That is, they may be
used as the \c{fillcolour} parameter to \cw{draw_circle()} and
\cw{draw_polygon()}, and as the colour parameter to
\cw{draw_rect()}, but may not be used as the \c{outlinecolour}
parameter to \cw{draw_circle()} or \cw{draw_polygon()}, or with
\cw{draw_line()} or \cw{draw_text()}.

\S{print-rgb-mono-colour} \cw{print_rgb_mono_colour()}

\c int print_rgb_mono_colour(drawing *dr, float r, float g,
\c                           float b, float grey);

This function allocates a colour index for a fully specified RGB
colour during printing.

\c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.

If printing in black and white only, these values will be ignored,
and either pure black or pure white will be used instead, according
to the \q{grey} parameter. (The fallback colour is the same as the
one which would be allocated by \cw{print_mono_colour(grey)}.)

\S{print-rgb-grey-colour} \cw{print_rgb_grey_colour()}

\c int print_rgb_grey_colour(drawing *dr, float r, float g,
\c                           float b, float grey);

This function allocates a colour index for a fully specified RGB
colour during printing.

\c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.

If printing in black and white only, these values will be ignored,
and a shade of grey given by the \c{grey} parameter will be used
instead. (The fallback colour is the same as the one which would be
allocated by \cw{print_grey_colour(grey)}.)

\S{print-rgb-hatched-colour} \cw{print_rgb_hatched_colour()}

\c int print_rgb_hatched_colour(drawing *dr, float r, float g,
\c                              float b, float hatched);

This function allocates a colour index for a fully specified RGB
colour during printing.

\c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.

If printing in black and white only, these values will be ignored,
and a form of cross-hatching given by the \c{hatch} parameter will
be used instead; see \k{print-hatched-colour} for the possible
values of this parameter. (The fallback colour is the same as the
one which would be allocated by \cw{print_hatched_colour(hatch)}.)

\S{print-line-width} \cw{print_line_width()}

\c void print_line_width(drawing *dr, int width);

This function is called to set the thickness of lines drawn during
printing. It is meaningless in drawing: all lines drawn by
\cw{draw_line()}, \cw{draw_circle} and \cw{draw_polygon()} are one
pixel in thickness. However, in printing there is no clear
definition of a pixel and so line widths must be explicitly
specified.

The line width is specified in the usual coordinate system. Note,
however, that it is a hint only: the central printing system may
choose to vary line thicknesses at user request or due to printer
capabilities.

\S{print-line-dotted} \cw{print_line_dotted()}

\c void print_line_dotted(drawing *dr, bool dotted);

This function is called to toggle the drawing of dotted lines during
printing. It is not supported during drawing.

Setting \cq{dotted} to \cw{true} means that future lines drawn by
\cw{draw_line()}, \cw{draw_circle} and \cw{draw_polygon()} will be
dotted. Setting it to \cw{false} means that they will be solid.

Some front ends may impose restrictions on the width of dotted
lines. Asking for a dotted line via this front end will override any
line width request if the front end requires it.

\H{drawing-frontend} The drawing API as implemented by the front end

This section describes the drawing API in the function-pointer form
in which it is implemented by a front end.

(It isn't only platform-specific front ends which implement this
API; the platform-independent module \c{ps.c} also provides an
implementation of it which outputs PostScript. Thus, any platform
which wants to do PS printing can do so with minimum fuss.)

The following entries all describe function pointer fields in a
structure called \c{drawing_api}. Each of the functions takes a
\cq{void *} context pointer, which it should internally cast back to
a more useful type. Thus, a drawing \e{object} (\c{drawing *)}
suitable for passing to the back end redraw or printing functions
is constructed by passing a \c{drawing_api} and a \cq{void *} to the
function \cw{drawing_new()} (see \k{drawing-new}).

\S{drawingapi-draw-text} \cw{draw_text()}

\c void (*draw_text)(void *handle, int x, int y, int fonttype,
\c                   int fontsize, int align, int colour,
\c                   const char *text);

This function behaves exactly like the back end \cw{draw_text()}
function; see \k{drawing-draw-text}.

\S{drawingapi-draw-rect} \cw{draw_rect()}

\c void (*draw_rect)(void *handle, int x, int y, int w, int h,
\c                   int colour);

This function behaves exactly like the back end \cw{draw_rect()}
function; see \k{drawing-draw-rect}.

\S{drawingapi-draw-line} \cw{draw_line()}

\c void (*draw_line)(void *handle, int x1, int y1, int x2, int y2,
\c                   int colour);

This function behaves exactly like the back end \cw{draw_line()}
function; see \k{drawing-draw-line}.

\S{drawingapi-draw-polygon} \cw{draw_polygon()}

\c void (*draw_polygon)(void *handle, const int *coords, int npoints,
\c                      int fillcolour, int outlinecolour);

This function behaves exactly like the back end \cw{draw_polygon()}
function; see \k{drawing-draw-polygon}.

\S{drawingapi-draw-circle} \cw{draw_circle()}

\c void (*draw_circle)(void *handle, int cx, int cy, int radius,
\c                     int fillcolour, int outlinecolour);

This function behaves exactly like the back end \cw{draw_circle()}
function; see \k{drawing-draw-circle}.

\S{drawingapi-draw-thick-line} \cw{draw_thick_line()}

\c void draw_thick_line(drawing *dr, float thickness,
\c                      float x1, float y1, float x2, float y2,
\c                      int colour)

This function behaves exactly like the back end
\cw{draw_thick_line()} function; see \k{drawing-draw-thick-line}.

An implementation of this API which doesn't provide high-quality
rendering of thick lines is permitted to define this function
pointer to be \cw{NULL}. The middleware in \cw{drawing.c} will notice
and provide a low-quality alternative using \cw{draw_polygon()}.

\S{drawingapi-draw-update} \cw{draw_update()}

\c void (*draw_update)(void *handle, int x, int y, int w, int h);

This function behaves exactly like the back end \cw{draw_update()}
function; see \k{drawing-draw-update}.

An implementation of this API which only supports printing is
permitted to define this function pointer to be \cw{NULL} rather
than bothering to define an empty function. The middleware in
\cw{drawing.c} will notice and avoid calling it.

\S{drawingapi-clip} \cw{clip()}

\c void (*clip)(void *handle, int x, int y, int w, int h);

This function behaves exactly like the back end \cw{clip()}
function; see \k{drawing-clip}.

\S{drawingapi-unclip} \cw{unclip()}

\c void (*unclip)(void *handle);

This function behaves exactly like the back end \cw{unclip()}
function; see \k{drawing-unclip}.

\S{drawingapi-start-draw} \cw{start_draw()}

\c void (*start_draw)(void *handle);

This function is called at the start of drawing. It allows the front
end to initialise any temporary data required to draw with, such as
device contexts.

Implementations of this API which do not provide drawing services
may define this function pointer to be \cw{NULL}; it will never be
called unless drawing is attempted.

\S{drawingapi-end-draw} \cw{end_draw()}

\c void (*end_draw)(void *handle);

This function is called at the end of drawing. It allows the front
end to do cleanup tasks such as deallocating device contexts and
scheduling appropriate GUI redraw events.

Implementations of this API which do not provide drawing services
may define this function pointer to be \cw{NULL}; it will never be
called unless drawing is attempted.

\S{drawingapi-status-bar} \cw{status_bar()}

\c void (*status_bar)(void *handle, const char *text);

This function behaves exactly like the back end \cw{status_bar()}
function; see \k{drawing-status-bar}.

Front ends implementing this function need not worry about it being
called repeatedly with the same text; the middleware code in
\cw{status_bar()} will take care of this.

Implementations of this API which do not provide drawing services
may define this function pointer to be \cw{NULL}; it will never be
called unless drawing is attempted.

\S{drawingapi-blitter-new} \cw{blitter_new()}

\c blitter *(*blitter_new)(void *handle, int w, int h);

This function behaves exactly like the back end \cw{blitter_new()}
function; see \k{drawing-blitter-new}.

Implementations of this API which do not provide drawing services
may define this function pointer to be \cw{NULL}; it will never be
called unless drawing is attempted.

\S{drawingapi-blitter-free} \cw{blitter_free()}

\c void (*blitter_free)(void *handle, blitter *bl);

This function behaves exactly like the back end \cw{blitter_free()}
function; see \k{drawing-blitter-free}.

Implementations of this API which do not provide drawing services
may define this function pointer to be \cw{NULL}; it will never be
called unless drawing is attempted.

\S{drawingapi-blitter-save} \cw{blitter_save()}

\c void (*blitter_save)(void *handle, blitter *bl, int x, int y);

This function behaves exactly like the back end \cw{blitter_save()}
function; see \k{drawing-blitter-save}.

Implementations of this API which do not provide drawing services
may define this function pointer to be \cw{NULL}; it will never be
called unless drawing is attempted.

\S{drawingapi-blitter-load} \cw{blitter_load()}

\c void (*blitter_load)(void *handle, blitter *bl, int x, int y);

This function behaves exactly like the back end \cw{blitter_load()}
function; see \k{drawing-blitter-load}.

Implementations of this API which do not provide drawing services
may define this function pointer to be \cw{NULL}; it will never be
called unless drawing is attempted.

\S{drawingapi-begin-doc} \cw{begin_doc()}

\c void (*begin_doc)(void *handle, int pages);

This function is called at the beginning of a printing run. It gives
the front end an opportunity to initialise any required printing
subsystem. It also provides the number of pages in advance.

Implementations of this API which do not provide printing services
may define this function pointer to be \cw{NULL}; it will never be
called unless printing is attempted.

\S{drawingapi-begin-page} \cw{begin_page()}

\c void (*begin_page)(void *handle, int number);

This function is called during printing, at the beginning of each
page. It gives the page number (numbered from 1 rather than 0, so
suitable for use in user-visible contexts).

Implementations of this API which do not provide printing services
may define this function pointer to be \cw{NULL}; it will never be
called unless printing is attempted.

\S{drawingapi-begin-puzzle} \cw{begin_puzzle()}

\c void (*begin_puzzle)(void *handle, float xm, float xc,
\c                      float ym, float yc, int pw, int ph, float wmm);

This function is called during printing, just before printing a
single puzzle on a page. It specifies the size and location of the
puzzle on the page.

\c{xm} and \c{xc} specify the horizontal position of the puzzle on
the page, as a linear function of the page width. The front end is
expected to multiply the page width by \c{xm}, add \c{xc} (measured
in millimetres), and use the resulting x-coordinate as the left edge
of the puzzle.

Similarly, \c{ym} and \c{yc} specify the vertical position of the
puzzle as a function of the page height: the page height times
\c{ym}, plus \c{yc} millimetres, equals the desired distance from
the top of the page to the top of the puzzle.

(This unwieldy mechanism is required because not all printing
systems can communicate the page size back to the software. The
PostScript back end, for example, writes out PS which determines the
page size at print time by means of calling \cq{clippath}, and
centres the puzzles within that. Thus, exactly the same PS file
works on A4 or on US Letter paper without needing local
configuration, which simplifies matters.)

\cw{pw} and \cw{ph} give the size of the puzzle in drawing API
coordinates. The printing system will subsequently call the puzzle's
own print function, which will in turn call drawing API functions in
the expectation that an area \cw{pw} by \cw{ph} units is available
to draw the puzzle on.

Finally, \cw{wmm} gives the desired width of the puzzle in
millimetres. (The aspect ratio is expected to be preserved, so if
the desired puzzle height is also needed then it can be computed as
\cw{wmm*ph/pw}.)

Implementations of this API which do not provide printing services
may define this function pointer to be \cw{NULL}; it will never be
called unless printing is attempted.

\S{drawingapi-end-puzzle} \cw{end_puzzle()}

\c void (*end_puzzle)(void *handle);

This function is called after the printing of a specific puzzle is
complete.

Implementations of this API which do not provide printing services
may define this function pointer to be \cw{NULL}; it will never be
called unless printing is attempted.

\S{drawingapi-end-page} \cw{end_page()}

\c void (*end_page)(void *handle, int number);

This function is called after the printing of a page is finished.

Implementations of this API which do not provide printing services
may define this function pointer to be \cw{NULL}; it will never be
called unless printing is attempted.

\S{drawingapi-end-doc} \cw{end_doc()}

\c void (*end_doc)(void *handle);

This function is called after the printing of the entire document is
finished. This is the moment to close files, send things to the
print spooler, or whatever the local convention is.

Implementations of this API which do not provide printing services
may define this function pointer to be \cw{NULL}; it will never be
called unless printing is attempted.

\S{drawingapi-line-width} \cw{line_width()}

\c void (*line_width)(void *handle, float width);

This function is called to set the line thickness, during printing
only. Note that the width is a \cw{float} here, where it was an
\cw{int} as seen by the back end. This is because \cw{drawing.c} may
have scaled it on the way past.

However, the width is still specified in the same coordinate system
as the rest of the drawing.

Implementations of this API which do not provide printing services
may define this function pointer to be \cw{NULL}; it will never be
called unless printing is attempted.

\S{drawingapi-line-dotted} \cw{line_dotted()}

\c void (*line_dotted)(void *handle, bool dotted);

This function is called to toggle drawing of dotted lines, during
printing only.

Implementations of this API which do not provide printing services
may define this function pointer to be \cw{NULL}; it will never be
called unless printing is attempted.

\S{drawingapi-text-fallback} \cw{text_fallback()}

\c char *(*text_fallback)(void *handle, const char *const *strings,
\c                        int nstrings);

This function behaves exactly like the back end \cw{text_fallback()}
function; see \k{drawing-text-fallback}.

Implementations of this API which do not support any characters
outside ASCII may define this function pointer to be \cw{NULL}, in
which case the central code in \cw{drawing.c} will provide a default
implementation.

\H{drawingapi-frontend} The drawing API as called by the front end

There are a small number of functions provided in \cw{drawing.c}
which the front end needs to \e{call}, rather than helping to
implement. They are described in this section.

\S{drawing-new} \cw{drawing_new()}

\c drawing *drawing_new(const drawing_api *api, midend *me,
\c                      void *handle);

This function creates a drawing object. It is passed a
\c{drawing_api}, which is a structure containing nothing but
function pointers; and also a \cq{void *} handle. The handle is
passed back to each function pointer when it is called.

The \c{midend} parameter is used for rewriting the status bar
contents: \cw{status_bar()} (see \k{drawing-status-bar}) has to call
a function in the mid-end which might rewrite the status bar text.
If the drawing object is to be used only for printing, or if the
game is known not to call \cw{status_bar()}, this parameter may be
\cw{NULL}.

\S{drawing-free} \cw{drawing_free()}

\c void drawing_free(drawing *dr);

This function frees a drawing object. Note that the \cq{void *}
handle is not freed; if that needs cleaning up it must be done by
the front end.

\S{drawing-print-get-colour} \cw{print_get_colour()}

\c void print_get_colour(drawing *dr, int colour,
\c                       bool printing_in_colour,
\c                       int *hatch, float *r, float *g, float *b);

This function is called by the implementations of the drawing API
functions when they are called in a printing context. It takes a
colour index as input, and returns the description of the colour as
requested by the back end.

\c{printing_in_colour} is \cw{true} iff the implementation is printing
in colour. This will alter the results returned if the colour in
question was specified with a black-and-white fallback value.

If the colour should be rendered by hatching, \c{*hatch} is filled
with the type of hatching desired. See \k{print-grey-colour} for
details of the values this integer can take.

If the colour should be rendered as solid colour, \c{*hatch} is
given a negative value, and \c{*r}, \c{*g} and \c{*b} are filled
with the RGB values of the desired colour (if printing in colour),
or all filled with the grey-scale value (if printing in black and
white).

\C{midend} The API provided by the mid-end

This chapter documents the API provided by the mid-end to be called
by the front end. You probably only need to read this if you are a
front end implementor, i.e. you are porting Puzzles to a new
platform. If you're only interested in writing new puzzles, you can
safely skip this chapter.

All the persistent state in the mid-end is encapsulated within a
\c{midend} structure, to facilitate having multiple mid-ends in any
port which supports multiple puzzle windows open simultaneously.
Each \c{midend} is intended to handle the contents of a single
puzzle window.

\H{midend-new} \cw{midend_new()}

\c midend *midend_new(frontend *fe, const game *ourgame,
\c                    const drawing_api *drapi, void *drhandle);

Allocates and returns a new mid-end structure.

The \c{fe} argument is stored in the mid-end. It will be used when
calling back to functions such as \cw{activate_timer()}
(\k{frontend-activate-timer}), and will be passed on to the back end
function \cw{colours()} (\k{backend-colours}).

The parameters \c{drapi} and \c{drhandle} are passed to
\cw{drawing_new()} (\k{drawing-new}) to construct a drawing object
which will be passed to the back end function \cw{redraw()}
(\k{backend-redraw}). Hence, all drawing-related function pointers
defined in \c{drapi} can expect to be called with \c{drhandle} as
their first argument.

The \c{ourgame} argument points to a container structure describing
a game back end. The mid-end thus created will only be capable of
handling that one game. (So even in a monolithic front end
containing all the games, this imposes the constraint that any
individual puzzle window is tied to a single game. Unless, of
course, you feel brave enough to change the mid-end for the window
without closing the window...)

\H{midend-free} \cw{midend_free()}

\c void midend_free(midend *me);

Frees a mid-end structure and all its associated data.

\H{midend-tilesize} \cw{midend_tilesize()}

\c int midend_tilesize(midend *me);

Returns the \cq{tilesize} parameter being used to display the
current puzzle (\k{backend-preferred-tilesize}).

\H{midend-set-params} \cw{midend_set_params()}

\c void midend_set_params(midend *me, game_params *params);

Sets the current game parameters for a mid-end. Subsequent games
generated by \cw{midend_new_game()} (\k{midend-new-game}) will use
these parameters until further notice.

The usual way in which the front end will have an actual
\c{game_params} structure to pass to this function is if it had
previously got it from \cw{midend_get_presets()}
(\k{midend-get-presets}). Thus, this function is usually called in
response to the user making a selection from the presets menu.

\H{midend-get-params} \cw{midend_get_params()}

\c game_params *midend_get_params(midend *me);

Returns the current game parameters stored in this mid-end.

The returned value is dynamically allocated, and should be freed
when finished with by passing it to the game's own
\cw{free_params()} function (see \k{backend-free-params}).

\H{midend-size} \cw{midend_size()}

\c void midend_size(midend *me, int *x, int *y,
\c                  bool user_size, double device_pixel_ratio);

Tells the mid-end to figure out its window size.

On input, \c{*x} and \c{*y} should contain the maximum or requested
size for the window. (Typically this will be the size of the screen
that the window has to fit on, or similar.) The mid-end will
repeatedly call the back end function \cw{compute_size()}
(\k{backend-compute-size}), searching for a tile size that best
satisfies the requirements. On exit, \c{*x} and \c{*y} will contain
the size needed for the puzzle window's drawing area. (It is of
course up to the front end to adjust this for any additional window
furniture such as menu bars and window borders, if necessary. The
status bar is also not included in this size.)

Use \c{user_size} to indicate whether \c{*x} and \c{*y} are a
requested size, or just a maximum size.

If \c{user_size} is set to \cw{true}, the mid-end will treat the
input size as a request, and will pick a tile size which
approximates it \e{as closely as possible}, going over the game's
preferred tile size if necessary to achieve this. The mid-end will
also use the resulting tile size as its preferred one until further
notice, on the assumption that this size was explicitly requested
by the user. Use this option if you want your front end to support
dynamic resizing of the puzzle window with automatic scaling of the
puzzle to fit.

If \c{user_size} is set to \cw{false}, then the game's tile size
will never go over its preferred one, although it may go under in
order to fit within the maximum bounds specified by \c{*x} and
\c{*y}. This is the recommended approach when opening a new window
at default size: the game will use its preferred size unless it has
to use a smaller one to fit on the screen. If the tile size is
shrunk for this reason, the change will not persist; if a smaller
grid is subsequently chosen, the tile size will recover.

The mid-end will try as hard as it can to return a size which is
less than or equal to the input size, in both dimensions. In extreme
circumstances it may fail (if even the lowest possible tile size
gives window dimensions greater than the input), in which case it
will return a size greater than the input size. Front ends should be
prepared for this to happen (i.e. don't crash or fail an assertion),
but may handle it in any way they see fit: by rejecting the game
parameters which caused the problem, by opening a window larger than
the screen regardless of inconvenience, by introducing scroll bars
on the window, by drawing on a large bitmap and scaling it into a
smaller window, or by any other means you can think of. It is likely
that when the tile size is that small the game will be unplayable
anyway, so don't put \e{too} much effort into handling it
creatively.

If your platform has no limit on window size (or if you're planning
to use scroll bars for large puzzles), you can pass dimensions of
\cw{INT_MAX} as input to this function. You should probably not do
that \e{and} set the \c{user_size} flag, though!

The \cw{device_pixel_ratio} allows the front end to specify that its
pixels are unusually large or small (or should be treated as such).
The mid-end uses this to adjust the tile size, both at startup (if the
ratio is not 1) and if the ratio changes.

A \cw{device_pixel_ratio} of 1 indicates normal-sized pixels.
\q{Normal} is not precisely defined, but it's about 4 pixels per
millimetre on a screen designed to be viewed from a metre away, or a
size such that text 15 pixels high is comfortably readable.  Some
platforms have a concept of a logical pixel that this can be mapped
onto.  For instance, Cascading Style Sheets (CSS) has a unit called
\cq{px} that only matches physical pixels at a \cw{device_pixel_ratio}
of 1.

The \cw{device_pixel_ratio} indicates the number of physical pixels in
a normal-sized pixel, so values less than 1 indicate unusually large
pixels and values greater than 1 indicate unusually small pixels.

The midend relies on the frontend calling \cw{midend_new_game()}
(\k{midend-new-game}) before calling \cw{midend_size()}.

\H{midend-reset-tilesize} \cw{midend_reset_tilesize()}

\c void midend_reset_tilesize(midend *me);

This function resets the midend's preferred tile size to that of the
standard puzzle.

As discussed in \k{midend-size}, puzzle resizes are typically
'sticky', in that once the user has dragged the puzzle to a different
window size, the resulting tile size will be remembered and used when
the puzzle configuration changes. If you \e{don't} want that, e.g. if
you want to provide a command to explicitly reset the puzzle size back
to its default, then you can call this just before calling
\cw{midend_size()} (which, in turn, you would probably call with
\c{user_size} set to \cw{false}).

\H{midend-new-game} \cw{midend_new_game()}

\c void midend_new_game(midend *me);

Causes the mid-end to begin a new game. Normally the game will be a
new randomly generated puzzle. However, if you have previously
called \cw{midend_game_id()} or \cw{midend_set_config()}, the game
generated might be dictated by the results of those functions. (In
particular, you \e{must} call \cw{midend_new_game()} after calling
either of those functions, or else no immediate effect will be
visible.)

You will probably need to call \cw{midend_size()} after calling this
function, because if the game parameters have been changed since the
last new game then the window size might need to change. (If you
know the parameters \e{haven't} changed, you don't need to do this.)

This function will create a new \c{game_drawstate}, but does not
actually perform a redraw (since you often need to call
\cw{midend_size()} before the redraw can be done). So after calling
this function and after calling \cw{midend_size()}, you should then
call \cw{midend_redraw()}. (It is not necessary to call
\cw{midend_force_redraw()}; that will discard the draw state and
create a fresh one, which is unnecessary in this case since there's
a fresh one already. It would work, but it's usually excessive.)

\H{midend-restart-game} \cw{midend_restart_game()}

\c void midend_restart_game(midend *me);

This function causes the current game to be restarted. This is done
by placing a new copy of the original game state on the end of the
undo list (so that an accidental restart can be undone).

This function automatically causes a redraw, i.e. the front end can
expect its drawing API to be called from \e{within} a call to this
function. Some back ends require that \cw{midend_size()}
(\k{midend-size}) is called before \cw{midend_restart_game()}.

\H{midend-force-redraw} \cw{midend_force_redraw()}

\c void midend_force_redraw(midend *me);

Forces a complete redraw of the puzzle window, by means of
discarding the current \c{game_drawstate} and creating a new one
from scratch before calling the game's \cw{redraw()} function.

The front end can expect its drawing API to be called from within a
call to this function. Some back ends require that \cw{midend_size()}
(\k{midend-size}) is called before \cw{midend_force_redraw()}.

\H{midend-redraw} \cw{midend_redraw()}

\c void midend_redraw(midend *me);

Causes a partial redraw of the puzzle window, by means of simply
calling the game's \cw{redraw()} function. (That is, the only things
redrawn will be things that have changed since the last redraw.)

The front end can expect its drawing API to be called from within a
call to this function. Some back ends require that \cw{midend_size()}
(\k{midend-size}) is called before \cw{midend_redraw()}.

\H{midend-process-key} \cw{midend_process_key()}

\c int midend_process_key(midend *me, int x, int y, int button)

The front end calls this function to report a mouse or keyboard event.
The parameters \c{x} and \c{y} are identical to the ones passed to the
back end function \cw{interpret_move()} (\k{backend-interpret-move}).

\c{button} is similar to the parameter passed to
\cw{interpret_move()}. However, the midend is more relaxed about
values passed to in, and some additional special button values
are defined for the front end to pass to the midend (see below).

Also, the front end is \e{not} required to provide guarantees about
mouse event ordering. The mid-end will sort out multiple simultaneous
button presses and changes of button; the front end's responsibility
is simply to pass on the mouse events it receives as accurately as
possible.

(Some platforms may need to emulate absent mouse buttons by means of
using a modifier key such as Shift with another mouse button. This
tends to mean that if Shift is pressed or released in the middle of
a mouse drag, the mid-end will suddenly stop receiving, say,
\cw{LEFT_DRAG} events and start receiving \cw{RIGHT_DRAG}s, with no
intervening button release or press events. This too is something
which the mid-end will sort out for you; the front end has no
obligation to maintain sanity in this area.)

The front end \e{should}, however, always eventually send some kind
of button release. On some platforms this requires special effort:
Windows, for example, requires a call to the system API function
\cw{SetCapture()} in order to ensure that your window receives a
mouse-up event even if the pointer has left the window by the time
the mouse button is released. On any platform that requires this
sort of thing, the front end \e{is} responsible for doing it.

Calling this function is very likely to result in calls back to the
front end's drawing API and/or \cw{activate_timer()}
(\k{frontend-activate-timer}).

The return value from \cw{midend_process_key()} is one of the
following constants:

\dt \cw{PKR_QUIT}

\dd Means that the effect of the keypress was to request termination
of the program.  A front end should shut down the puzzle in response
to a \cw{PKR_QUIT} return.

\dt \cw{PKR_SOME_EFFECT}

\dd The keypress had some other effect, either in the mid-end or in
the puzzle itself.

\dt \cw{PKR_NO_EFFECT}

\dd The keypress had no effect, but might have had an effect in
slightly different circumstances.  For instance it requested a move
that wasn't possible.

\dt \cw{PKR_UNUSED}

\dd The key was one that neither the mid-end nor the back-end has any
use for at all.

A front end might respond to the last value by passing the key on to
something else that might be interested in it.

The following additional values of \c{button} are permitted to be
passed to this function by the front end, but are never passed on to
the back end. They indicate front-end specific UI operations, such as
selecting an option from a drop-down menu. (Otherwise the front end
would have to translate the \q{New Game} menu item into an \cq{n}
keypress, for example.)

\dt \cw{UI_NEWGAME}

\dd Indicates that the user requested a new game, similar to pressing
\cq{n}.

\dt \cw{UI_SOLVE}

\dd Indicates that the user requested the solution of the current game.

\dt \cw{UI_UNDO}

\dd Indicates that the user attempted to undo a move.

\dt \cw{UI_REDO}

\dd Indicates that the user attempted to redo an undone move.

\dt \cw{UI_QUIT}

\dd Indicates that the user asked to quit the game. (Of course, a
front end might perfectly well handle this on its own. But including
it in this enumeration allows the front end to treat all these menu
items the same, by translating each of them into a button code passed
to the midend, and handle quitting by noticing the \c{false} return
value from \cw{midend_process_key()}.)

The midend tolerates any modifier being set on any key and removes
them as necessary before passing the key on to the backend.  It will
also handle translating printable characters combined with
\cw{MOD_CTRL} into control characters.

\H{midend-request-keys} \cw{midend_request_keys()}

\c key_label *midend_request_keys(midend *me, int *nkeys);

This function behaves similarly to the backend's \cw{request_keys()}
function (\k{backend-request-keys}). If the backend does not provide
\cw{request_keys()}, this function will return \cw{NULL} and set
\cw{*nkeys} to zero. Otherwise, this function will fill in the generic
labels (i.e. the \cw{key_label} items that have their \cw{label}
fields set to \cw{NULL}) by using \cw{button2label()}
(\k{utils-button2label}).

\H{midend-current-key-label} \cw{midend_current_key_label()}

\c const char *midend_current_key_label(midend *me, int button);

This is a thin wrapper around the backend's \cw{current_key_label()}
function (\k{backend-current-key-label}).  Front ends that need to
label \cw{CURSOR_SELECT} or \cw{CURSOR_SELECT2} should call this
function after each move (at least after each call to
\cw{midend_process_key()}) to get the current labels.  The front end
should arrange to copy the returned string somewhere before the next
call to the mid-end, just in case it's dynamically allocated.  If the
button supplied does nothing, the label returned will be an empty
string.

\H{midend-colours} \cw{midend_colours()}

\c float *midend_colours(midend *me, int *ncolours);

Returns an array of the colours required by the game, in exactly the
same format as that returned by the back end function \cw{colours()}
(\k{backend-colours}). Front ends should call this function rather
than calling the back end's version directly, since the mid-end adds
standard customisation facilities. (At the time of writing, those
customisation facilities are implemented hackily by means of
environment variables, but it's not impossible that they may become
more full and formal in future.)

\H{midend-timer} \cw{midend_timer()}

\c void midend_timer(midend *me, float tplus);

If the mid-end has called \cw{activate_timer()}
(\k{frontend-activate-timer}) to request regular callbacks for
purposes of animation or timing, this is the function the front end
should call on a regular basis. The argument \c{tplus} gives the
time, in seconds, since the last time either this function was
called or \cw{activate_timer()} was invoked.

One of the major purposes of timing in the mid-end is to perform
move animation. Therefore, calling this function is very likely to
result in calls back to the front end's drawing API.

\H{midend-get-presets} \cw{midend_get_presets()}

\c struct preset_menu *midend_get_presets(midend *me, int *id_limit);

Returns a data structure describing this game's collection of preset
game parameters, organised into a hierarchical structure of menus and
submenus.

The return value is a pointer to a data structure containing the
following fields (among others, which are not intended for front end
use):

\c struct preset_menu {
\c     int n_entries;
\c     struct preset_menu_entry *entries;
\c     /* and other things */
\e     iiiiiiiiiiiiiiiiiiiiii
\c };

Those fields describe the intended contents of one particular menu in
the hierarchy. \cq{entries} points to an array of \cq{n_entries}
items, each of which is a structure containing the following fields:

\c struct preset_menu_entry {
\c     char *title;
\c     game_params *params;
\c     struct preset_menu *submenu;
\c     int id;
\c };

Of these fields, \cq{title} and \cq{id} are present in every entry,
giving (respectively) the textual name of the menu item and an integer
identifier for it. The integer id will correspond to the one returned
by \c{midend_which_preset} (\k{midend-which-preset}), when that preset
is the one selected.

The other two fields are mutually exclusive. Each \c{struct
preset_menu_entry} will have one of those fields \cw{NULL} and the
other one non-null. If the menu item is an actual preset, then
\cq{params} will point to the set of game parameters that go with the
name; if it's a submenu, then \cq{submenu} instead will be non-null,
and will point at a subsidiary \c{struct preset_menu}.

The complete hierarchy of these structures is owned by the mid-end,
and will be freed when the mid-end is freed. The front end should not
attempt to free any of it.

The integer identifiers will be allocated densely from 0 upwards, so
that it's reasonable for the front end to allocate an array which uses
them as indices, if it needs to store information per preset menu
item. For this purpose, the front end may pass the second parameter
\cq{id_limit} to \cw{midend_get_presets} as the address of an \c{int}
variable, into which \cw{midend_get_presets} will write an integer one
larger than the largest id number actually used (i.e. the number of
elements the front end would need in the array).

Submenu-type entries also have integer identifiers.

\H{midend-which-preset} \cw{midend_which_preset()}

\c int midend_which_preset(midend *me);

Returns the numeric index of the preset game parameter structure
which matches the current game parameters, or a negative number if
no preset matches. Front ends could use this to maintain a tick
beside one of the items in the menu (or tick the \q{Custom} option
if the return value is less than zero).

The returned index value (if non-negative) will match the \c{id} field
of the corresponding \cw{struct preset_menu_entry} returned by
\c{midend_get_presets()} (\k{midend-get-presets}).

\H{midend-wants-statusbar} \cw{midend_wants_statusbar()}

\c bool midend_wants_statusbar(midend *me);

This function returns \cw{true} if the puzzle has a use for a
textual status line (to display score, completion status, currently
active tiles, time, or anything else).

Front ends should call this function rather than talking directly to
the back end.

\H{midend-get-config} \cw{midend_get_config()}

\c config_item *midend_get_config(midend *me, int which,
\c                                char **wintitle);

Returns a dialog box description for user configuration.

On input, \cw{which} should be set to one of three values, which
select which of the various dialog box descriptions is returned:

\dt \cw{CFG_SETTINGS}

\dd Requests the GUI parameter configuration box generated by the
puzzle itself. This should be used when the user selects \q{Custom}
from the game types menu (or equivalent). The mid-end passes this
request on to the back end function \cw{configure()}
(\k{backend-configure}).

\dt \cw{CFG_DESC}

\dd Requests a box suitable for entering a descriptive game ID (and
viewing the existing one). The mid-end generates this dialog box
description itself. This should be used when the user selects
\q{Specific} from the game menu (or equivalent).

\dt \cw{CFG_SEED}

\dd Requests a box suitable for entering a random-seed game ID (and
viewing the existing one). The mid-end generates this dialog box
description itself. This should be used when the user selects
\q{Random Seed} from the game menu (or equivalent).

\dt \cw{CFG_PREFS}

\dd Requests a box suitable for configuring user preferences.

(An additional value \cw{CFG_FRONTEND_SPECIFIC} is provided in this
enumeration, so that frontends can extend it for their own internal
use. For example, you might wrap this function with a
\cw{frontend_get_config} which handles some values of \c{which} itself
and hands others on to the midend, depending on whether \cw{which <
CFG_FRONTEND_SPECIFIC}.)

The returned value is an array of \cw{config_item}s, exactly as
described in \k{backend-configure}. Another returned value is an
ASCII string giving a suitable title for the configuration window,
in \c{*wintitle}.

Both returned values are dynamically allocated and will need to be
freed. The window title can be freed in the obvious way; the
\cw{config_item} array is a slightly complex structure, so a utility
function \cw{free_cfg()} is provided to free it for you. See
\k{utils-free-cfg}.

(Of course, you will probably not want to free the \cw{config_item}
array until the dialog box is dismissed, because before then you
will probably need to pass it to \cw{midend_set_config}.)

\H{midend-set-config} \cw{midend_set_config()}

\c const char *midend_set_config(midend *me, int which,
\c                               config_item *cfg);

Passes the mid-end the results of a configuration dialog box.
\c{which} should have the same value which it had when
\cw{midend_get_config()} was called; \c{cfg} should be the array of
\c{config_item}s returned from \cw{midend_get_config()}, modified to
contain the results of the user's editing operations.

This function returns \cw{NULL} on success, or otherwise (if the
configuration data was in some way invalid) an ASCII string
containing an error message suitable for showing to the user.

If the function succeeds, it is likely that the game parameters will
have been changed and it is certain that a new game will be
requested. The front end should therefore call
\cw{midend_new_game()}, and probably also re-think the window size
using \cw{midend_size()} and eventually perform a refresh using
\cw{midend_redraw()}.

\H{midend-game-id} \cw{midend_game_id()}

\c const char *midend_game_id(midend *me, const char *id);

Passes the mid-end a string game ID (of any of the valid forms
\cq{params}, \cq{params:description} or \cq{params#seed}) which the
mid-end will process and use for the next generated game.

This function returns \cw{NULL} on success, or otherwise (if the
configuration data was in some way invalid) an ASCII string
containing an error message (not dynamically allocated) suitable for
showing to the user. In the event of an error, the mid-end's
internal state will be left exactly as it was before the call.

If the function succeeds, it is likely that the game parameters will
have been changed and it is certain that a new game will be
requested. The front end should therefore call
\cw{midend_new_game()}, and probably also re-think the window size
using \cw{midend_size()} and eventually case a refresh using
\cw{midend_redraw()}.

\H{midend-get-game-id} \cw{midend_get_game_id()}

\c char *midend_get_game_id(midend *me);

Returns a descriptive game ID (i.e. one in the form
\cq{params:description}) describing the game currently active in the
mid-end. The returned string is dynamically allocated.

\H{midend-get-random-seed} \cw{midend_get_random_seed()}

\c char *midend_get_random_seed(midend *me);

Returns a random game ID (i.e. one in the form \cq{params#seedstring})
describing the game currently active in the mid-end, if there is one.
If the game was created by entering a description, no random seed will
currently exist and this function will return \cw{NULL}.

The returned string, if it is non-\cw{NULL}, is dynamically allocated.

Unlike the descriptive game ID, the random seed can contain characters
outside the printable ASCII set.

\H{midend-can-format-as-text-now} \cw{midend_can_format_as_text_now()}

\c bool midend_can_format_as_text_now(midend *me);

Returns \cw{true} if the game code is capable of formatting puzzles
of the currently selected game type as ASCII.

If this returns \cw{false}, then \cw{midend_text_format()}
(\k{midend-text-format}) will return \cw{NULL}.

\H{midend-text-format} \cw{midend_text_format()}

\c char *midend_text_format(midend *me);

Formats the current game's current state as ASCII text suitable for
copying to the clipboard. The returned string is dynamically
allocated.

If the game's \c{can_format_as_text_ever} flag is \cw{false}, or if
its \cw{can_format_as_text_now()} function returns \cw{false}, then
this function will return \cw{NULL}.

If the returned string contains multiple lines (which is likely), it
will use the normal C line ending convention (\cw{\\n} only). On
platforms which use a different line ending convention for data in
the clipboard, it is the front end's responsibility to perform the
conversion.

\H{midend-solve} \cw{midend_solve()}

\c const char *midend_solve(midend *me);

Requests the mid-end to perform a Solve operation.

On success, \cw{NULL} is returned. On failure, an error message (not
dynamically allocated) is returned, suitable for showing to the
user.

The front end can expect its drawing API and/or
\cw{activate_timer()} to be called from within a call to this
function.  Some back ends require that \cw{midend_size()}
(\k{midend-size}) is called before \cw{midend_solve()}.

\H{midend-get-cursor-location} \cw{midend_get_cursor_location()}

\c bool midend_get_cursor_location(midend *me,
\c                                 int *x, int *y,
\c                                 int *w, int *h);

This function requests the location of the back end's on-screen cursor
or other region of interest.

What exactly this region contains is up to the backend, but in general
the region will be an area that the player is controlling with the
cursor keys \dash such as the player location in Cube and Inertia, or
the cursor in any of the conventional grid-based games. With knowledge
of this location, a front end can, for example, ensure that the region
of interest remains visible even if the entire puzzle is too big to
fit on the screen.

On success, this function returns \cw{true}, and the locations pointed
to by \cw{x}, \cw{y}, \cw{w} and \cw{h} are updated to describe the
cursor region, which has an upper-left corner located at \cw{(*x,*y)}
and a size of \cw{*w} pixels wide by \cw{*h} pixels tall. The caller
may pass \cw{NULL} for any number of these pointers, which will be
ignored.

On failure, this function returns \cw{false}. Failure can occur if
there is currently no active cursor region, or if the back end lacks
cursor support.

\H{midend-status} \cw{midend_status()}

\c int midend_status(midend *me);

This function returns +1 if the midend is currently displaying a game
in a solved state, -1 if the game is in a permanently lost state, or 0
otherwise. This function just calls the back end's \cw{status()}
function. Front ends may wish to use this as a cue to proactively
offer the option of starting a new game.

(See \k{backend-status} for more detail about the back end's
\cw{status()} function and discussion of what should count as which
status code.)

\H{midend-can-undo} \cw{midend_can_undo()}

\c bool midend_can_undo(midend *me);

Returns \cw{true} if the midend is currently in a state where the undo
operation is meaningful (i.e. at least one position exists on the undo
chain before the present one). Front ends may wish to use this to
visually activate and deactivate an undo button.

\H{midend-can-redo} \cw{midend_can_redo()}

\c bool midend_can_redo(midend *me);

Returns \cw{true} if the midend is currently in a state where the redo
operation is meaningful (i.e. at least one position exists on the redo
chain after the present one). Front ends may wish to use this to
visually activate and deactivate a redo button.

\H{midend-serialise} \cw{midend_serialise()}

\c void midend_serialise(midend *me,
\c     void (*write)(void *ctx, const void *buf, int len), void *wctx);

Calling this function causes the mid-end to convert its entire
internal state into a long ASCII text string, and to pass that
string (piece by piece) to the supplied \c{write} function.
The string will consist of printable ASCII characters and line
feeds.

Desktop implementations can use this function to save a game in any
state (including half-finished) to a disk file, by supplying a
\c{write} function which is a wrapper on \cw{fwrite()} (or local
equivalent). Other implementations may find other uses for it, such
as compressing the large and sprawling mid-end state into a
manageable amount of memory when a palmtop application is suspended
so that another one can run; in this case \cw{write} might want to
write to a memory buffer rather than a file. There may be other uses
for it as well.

This function will call back to the supplied \c{write} function a
number of times, with the first parameter (\c{ctx}) equal to
\c{wctx}, and the other two parameters pointing at a piece of the
output string.

\H{midend-deserialise} \cw{midend_deserialise()}

\c const char *midend_deserialise(midend *me,
\c     bool (*read)(void *ctx, void *buf, int len), void *rctx);

This function is the counterpart to \cw{midend_serialise()}. It
calls the supplied \cw{read} function repeatedly to read a quantity
of data, and attempts to interpret that data as a serialised mid-end
as output by \cw{midend_serialise()}.

The \cw{read} function is called with the first parameter (\c{ctx})
equal to \c{rctx}, and should attempt to read \c{len} bytes of data
into the buffer pointed to by \c{buf}. It should return \cw{false}
on failure or \cw{true} on success. It should not report success
unless it has filled the entire buffer; on platforms which might be
reading from a pipe or other blocking data source, \c{read} is
responsible for looping until the whole buffer has been filled.

If the de-serialisation operation is successful, the mid-end's
internal data structures will be replaced by the results of the
load, and \cw{NULL} will be returned. Otherwise, the mid-end's state
will be completely unchanged and an error message (typically some
variation on \q{save file is corrupt}) will be returned. As usual,
the error message string is not dynamically allocated.

If this function succeeds, it is likely that the game parameters
will have been changed. The front end should therefore probably
re-think the window size using \cw{midend_size()}, and probably
cause a refresh using \cw{midend_redraw()}.

Because each mid-end is tied to a specific game back end, this
function will fail if you attempt to read in a save file generated by
a different game from the one configured in this mid-end, even if your
application is a monolithic one containing all the puzzles. See
\k{identify-game} for a helper function which will allow you to
identify a save file before you instantiate your mid-end in the first
place.

\H{midend-save-prefs} \cw{midend_save_prefs()}

\c void midend_save_prefs(
\c     midend *me, void (*write)(void *ctx, const void *buf, int len),
\c     void *wctx);

Calling this function causes the mid-end to write out the states of
all user-settable preference options, including its own cross-platform
preferences and ones exported by a particular game via
\cw{get_prefs()} and \cw{set_prefs()} (\k{backend-get-prefs},
\k{backend-set-prefs}). The output is a textual format suitable for
writing into a configuration file on disk.

The \c{write} and \c{wctx} parameters have the same semantics as for
\cw{midend_serialise()} (\k{midend-serialise}).

\H{midend-load-prefs} \cw{midend_load_prefs()}

\c const char *midend_load_prefs(
\c     midend *me, bool (*read)(void *ctx, void *buf, int len),
\c     void *rctx);

This function is used to load a configuration file in the same format
emitted by \cw{midend_save_prefs()}, and import all the preferences
described in the file into the current mid-end.

\H{identify-game} \cw{identify_game()}

\c const char *identify_game(char **name,
\c     bool (*read)(void *ctx, void *buf, int len), void *rctx);

This function examines a serialised midend stream, of the same kind
used by \cw{midend_serialise()} and \cw{midend_deserialise()}, and
returns the \cw{name} field of the game back end from which it was
saved.

You might want this if your front end was a monolithic one containing
all the puzzles, and you wanted to be able to load an arbitrary save
file and automatically switch to the right game. Probably your next
step would be to iterate through \cw{gamelist} (\k{frontend-backend})
looking for a game structure whose \cw{name} field matched the
returned string, and give an error if you didn't find one.

On success, the return value of this function is \cw{NULL}, and the
game name string is written into \cw{*name}. The caller should free
that string after using it.

On failure, \cw{*name} is \cw{NULL}, and the return value is an error
message (which does not need freeing at all).

(This isn't strictly speaking a midend function, since it doesn't
accept or return a pointer to a midend. You'd probably call it just
\e{before} deciding what kind of midend you wanted to instantiate.)

\H{midend-request-id-changes} \cw{midend_request_id_changes()}

\c void midend_request_id_changes(midend *me,
\c                                void (*notify)(void *), void *ctx);

This function is called by the front end to request notification by
the mid-end when the current game IDs (either descriptive or
random-seed) change. This can occur as a result of keypresses ('n' for
New Game, for example) or when a puzzle supersedes its game
description (see \k{backend-supersede}). After this function is
called, any change of the game ids will cause the mid-end to call
\cw{notify(ctx)} after the change.

This is for use by puzzles which want to present the game description
to the user constantly (e.g. as an HTML hyperlink) instead of only
showing it when the user explicitly requests it.

This is a function I anticipate few front ends needing to implement,
so I make it a callback rather than a static function in order to
relieve most front ends of the need to provide an empty
implementation.

\H{midend-which-game} \cw{midend_which_game()}

\c const game *midend_which_preset(midend *me);

This function returns the \c{game} structure for the puzzle type this
midend is committed to.

\H{frontend-backend} Direct reference to the back end structure by
the front end

Although \e{most} things the front end needs done should be done by
calling the mid-end, there are a few situations in which the front
end needs to refer directly to the game back end structure.

The most obvious of these is

\b passing the game back end as a parameter to \cw{midend_new()}.

There are a few other back end features which are not wrapped by the
mid-end because there didn't seem much point in doing so:

\b fetching the \c{name} field to use in window titles and similar

\b reading the \c{can_configure}, \c{can_solve} and
\c{can_format_as_text_ever} fields to decide whether to add those
items to the menu bar or equivalent

\b reading the \c{winhelp_topic} field (Windows only)

\b the GTK front end provides a \cq{--generate} command-line option
which directly calls the back end to do most of its work. This is
not really part of the main front end code, though, and I'm not sure
it counts.

In order to find the game back end structure, the front end does one
of two things:

\b If the particular front end is compiling a separate binary per
game, then the back end structure is a global variable with the
standard name \cq{thegame}:

\lcont{

\c extern const game thegame;

}

\b If the front end is compiled as a monolithic application
containing all the puzzles together (in which case the preprocessor
symbol \cw{COMBINED} must be defined when compiling most of the code
base), then there will be two global variables defined:

\lcont{

\c extern const game *gamelist[];
\c extern const int gamecount;

\c{gamelist} will be an array of \c{gamecount} game structures,
declared in the automatically constructed source module \c{list.c}.
The application should search that array for the game it wants,
probably by reaching into each game structure and looking at its
\c{name} field.

}

\H{frontend-api} Mid-end to front-end calls

This section describes the small number of functions which a front
end must provide to be called by the mid-end or other standard
utility modules.

\H{frontend-get-random-seed} \cw{get_random_seed()}

\c void get_random_seed(void **randseed, int *randseedsize);

This function is called by a new mid-end, and also occasionally by
game back ends. Its job is to return a piece of data suitable for
using as a seed for initialisation of a new \c{random_state}.

On exit, \c{*randseed} should be set to point at a newly allocated
piece of memory containing some seed data, and \c{*randseedsize}
should be set to the length of that data.

A simple and entirely adequate implementation is to return a piece
of data containing the current system time at the highest
conveniently available resolution.

\H{frontend-activate-timer} \cw{activate_timer()}

\c void activate_timer(frontend *fe);

This is called by the mid-end to request that the front end begin
calling it back at regular intervals.

The timeout interval is left up to the front end; the finer it is,
the smoother move animations will be, but the more CPU time will be
used. Current front ends use values around 20ms (i.e. 50Hz).

After this function is called, the mid-end will expect to receive
calls to \cw{midend_timer()} on a regular basis.

\H{frontend-deactivate-timer} \cw{deactivate_timer()}

\c void deactivate_timer(frontend *fe);

This is called by the mid-end to request that the front end stop
calling \cw{midend_timer()}.

\H{frontend-fatal} \cw{fatal()}

\c void fatal(const char *fmt, ...);

This is called by some utility functions if they encounter a
genuinely fatal error such as running out of memory. It is a
variadic function in the style of \cw{printf()}, and is expected to
show the formatted error message to the user any way it can and then
terminate the application. It must not return.

\H{frontend-default-colour} \cw{frontend_default_colour()}

\c void frontend_default_colour(frontend *fe, float *output);

This function expects to be passed a pointer to an array of three
\cw{float}s. It returns the platform's local preferred background
colour in those three floats, as red, green and blue values (in that
order) ranging from \cw{0.0} to \cw{1.0}.

This function should only ever be called by the back end function
\cw{colours()} (\k{backend-colours}). (Thus, it isn't a
\e{midend}-to-frontend function as such, but there didn't seem to be
anywhere else particularly good to put it. Sorry.)

\C{utils} Utility APIs

This chapter documents a variety of utility APIs provided for the
general use of the rest of the Puzzles code.

\H{utils-random} Random number generation

Platforms' local random number generators vary widely in quality and
seed size. Puzzles therefore supplies its own high-quality random
number generator, with the additional advantage of giving the same
results if fed the same seed data on different platforms. This
allows game random seeds to be exchanged between different ports of
Puzzles and still generate the same games.

Unlike the ANSI C \cw{rand()} function, the Puzzles random number
generator has an \e{explicit} state object called a
\c{random_state}. One of these is managed by each mid-end, for
example, and passed to the back end to generate a game with.

\S{utils-random-init} \cw{random_new()}

\c random_state *random_new(char *seed, int len);

Allocates, initialises and returns a new \c{random_state}. The input
data is used as the seed for the random number stream (i.e. using
the same seed at a later time will generate the same stream).

The seed data can be any data at all; there is no requirement to use
printable ASCII, or NUL-terminated strings, or anything like that.

\S{utils-random-copy} \cw{random_copy()}

\c random_state *random_copy(random_state *tocopy);

Allocates a new \c{random_state}, copies the contents of another
\c{random_state} into it, and returns the new state.  If exactly the
same sequence of functions is subsequently called on both the copy and
the original, the results will be identical.  This may be useful for
speculatively performing some operation using a given random state,
and later replaying that operation precisely.

\S{utils-random-free} \cw{random_free()}

\c void random_free(random_state *state);

Frees a \c{random_state}.

\S{utils-random-bits} \cw{random_bits()}

\c unsigned long random_bits(random_state *state, int bits);

Returns a random number from 0 to \cw{2^bits-1} inclusive. \c{bits}
should be between 1 and 32 inclusive.

\S{utils-random-upto} \cw{random_upto()}

\c unsigned long random_upto(random_state *state, unsigned long limit);

Returns a random number from 0 to \cw{limit-1} inclusive. \c{limit}
may not be zero.

\S{utils-random-state-encode} \cw{random_state_encode()}

\c char *random_state_encode(random_state *state);

Encodes the entire contents of a \c{random_state} in printable
ASCII. Returns a dynamically allocated string containing that
encoding. This can subsequently be passed to
\cw{random_state_decode()} to reconstruct the same \c{random_state}.

\S{utils-random-state-decode} \cw{random_state_decode()}

\c random_state *random_state_decode(char *input);

Decodes a string generated by \cw{random_state_encode()} and
reconstructs an equivalent \c{random_state} to the one encoded, i.e.
it should produce the same stream of random numbers.

This function has no error reporting; if you pass it an invalid
string it will simply generate an arbitrary random state, which may
turn out to be noticeably non-random.

\S{utils-shuffle} \cw{shuffle()}

\c void shuffle(void *array, int nelts, int eltsize, random_state *rs);

Shuffles an array into a random order. The interface is much like
ANSI C \cw{qsort()}, except that there's no need for a compare
function.

\c{array} is a pointer to the first element of the array. \c{nelts}
is the number of elements in the array; \c{eltsize} is the size of a
single element (typically measured using \c{sizeof}). \c{rs} is a
\c{random_state} used to generate all the random numbers for the
shuffling process.

\H{utils-presets} Presets menu management

The function \c{midend_get_presets()} (\k{midend-get-presets}) returns
a data structure describing a menu hierarchy. Back ends can also
choose to provide such a structure to the mid-end, if they want to
group their presets hierarchically. To make this easy, there are a few
utility functions to construct preset menu structures, and also one
intended for front-end use.

\S{utils-preset-menu-new} \cw{preset_menu_new()}

\c struct preset_menu *preset_menu_new(void);

Allocates a new \c{struct preset_menu}, and initialises it to hold no
menu items.

\S{utils-preset-menu-add_submenu} \cw{preset_menu_add_submenu()}

\c struct preset_menu *preset_menu_add_submenu
\c     (struct preset_menu *parent, char *title);

Adds a new submenu to the end of an existing preset menu, and returns
a pointer to a newly allocated \c{struct preset_menu} describing the
submenu.

The string parameter \cq{title} must be dynamically allocated by the
caller. The preset-menu structure will take ownership of it, so the
caller must not free it.

\S{utils-preset-menu-add-preset} \cw{preset_menu_add_preset()}

\c void preset_menu_add_preset
\c     (struct preset_menu *menu, char *title, game_params *params);

Adds a preset game configuration to the end of a preset menu.

Both the string parameter \cq{title} and the game parameter structure
\cq{params} itself must be dynamically allocated by the caller. The
preset-menu structure will take ownership of it, so the caller must
not free it.

\S{utils-preset-menu-lookup-by-id} \cw{preset_menu_lookup_by_id()}

\c game_params *preset_menu_lookup_by_id
\c     (struct preset_menu *menu, int id);

Given a numeric index, searches recursively through a preset menu
hierarchy to find the corresponding menu entry, and returns a pointer
to its existing \c{game_params} structure.

This function is intended for front end use (but front ends need not
use it if they prefer to do things another way). If a front end finds
it inconvenient to store anything more than a numeric index alongside
each menu item, then this function provides an easy way for the front
end to get back the actual game parameters corresponding to a menu
item that the user has selected.

\H{utils-alloc} Memory allocation

Puzzles has some central wrappers on the standard memory allocation
functions, which provide compile-time type checking, and run-time
error checking by means of quitting the application if it runs out
of memory. This doesn't provide the best possible recovery from
memory shortage, but on the other hand it greatly simplifies the
rest of the code, because nothing else anywhere needs to worry about
\cw{NULL} returns from allocation.

\S{utils-snew} \cw{snew()}

\c var = snew(type);
\e iii        iiii

This macro takes a single argument which is a \e{type name}. It
allocates space for one object of that type. If allocation fails it
will call \cw{fatal()} and not return; so if it does return, you can
be confident that its return value is non-\cw{NULL}.

The return value is cast to the specified type, so that the compiler
will type-check it against the variable you assign it into. Thus,
this ensures you don't accidentally allocate memory the size of the
wrong type and assign it into a variable of the right one (or vice
versa!).

\S{utils-snewn} \cw{snewn()}

\c var = snewn(n, type);
\e iii         i  iiii

This macro is the array form of \cw{snew()}. It takes two arguments;
the first is a number, and the second is a type name. It allocates
space for that many objects of that type, and returns a type-checked
non-\cw{NULL} pointer just as \cw{snew()} does.

\S{utils-sresize} \cw{sresize()}

\c var = sresize(var, n, type);
\e iii           iii  i  iiii

This macro is a type-checked form of \cw{realloc()}. It takes three
arguments: an input memory block, a new size in elements, and a
type. It re-sizes the input memory block to a size sufficient to
contain that many elements of that type. It returns a type-checked
non-\cw{NULL} pointer, like \cw{snew()} and \cw{snewn()}.

The input memory block can be \cw{NULL}, in which case this function
will behave exactly like \cw{snewn()}. (In principle any
ANSI-compliant \cw{realloc()} implementation ought to cope with
this, but I've never quite trusted it to work everywhere.)

\S{utils-sfree} \cw{sfree()}

\c void sfree(void *p);

This function is pretty much equivalent to \cw{free()}. It is
provided with a dynamically allocated block, and frees it.

The input memory block can be \cw{NULL}, in which case this function
will do nothing. (In principle any ANSI-compliant \cw{free()}
implementation ought to cope with this, but I've never quite trusted
it to work everywhere.)

\S{utils-dupstr} \cw{dupstr()}

\c char *dupstr(const char *s);

This function dynamically allocates a duplicate of a C string. Like
the \cw{snew()} functions, it guarantees to return non-\cw{NULL} or
not return at all.

(Many platforms provide the function \cw{strdup()}. As well as
guaranteeing never to return \cw{NULL}, my version has the advantage
of being defined \e{everywhere}, rather than inconveniently not
quite everywhere.)

\S{utils-free-cfg} \cw{free_cfg()}

\c void free_cfg(config_item *cfg);

This function correctly frees an array of \c{config_item}s, including
walking the array until it gets to the end and freeing any subsidiary
data items in each \c{u} sub-union which are expected to be
dynamically allocated.

(See \k{backend-configure} for details of the \c{config_item}
structure.)

\S{utils-free-keys} \cw{free_keys()}

\c void free_keys(key_label *keys, int nkeys);

This function correctly frees an array of \c{key_label}s, including
the dynamically allocated label string for each key.

(See \k{backend-request-keys} for details of the \c{key_label}
structure.)

\H{utils-tree234} Sorted and counted tree functions

Many games require complex algorithms for generating random puzzles,
and some require moderately complex algorithms even during play. A
common requirement during these algorithms is for a means of
maintaining sorted or unsorted lists of items, such that items can
be removed and added conveniently.

For general use, Puzzles provides the following set of functions
which maintain 2-3-4 trees in memory. (A 2-3-4 tree is a balanced
tree structure, with the property that all lookups, insertions,
deletions, splits and joins can be done in \cw{O(log N)} time.)

All these functions expect you to be storing a tree of \c{void *}
pointers. You can put anything you like in those pointers.

By the use of per-node element counts, these tree structures have
the slightly unusual ability to look elements up by their numeric
index within the list represented by the tree. This means that they
can be used to store an unsorted list (in which case, every time you
insert a new element, you must explicitly specify the position where
you wish to insert it). They can also do numeric lookups in a sorted
tree, which might be useful for (for example) tracking the median of
a changing data set.

As well as storing sorted lists, these functions can be used for
storing \q{maps} (associative arrays), by defining each element of a
tree to be a (key, value) pair.

\S{utils-newtree234} \cw{newtree234()}

\c tree234 *newtree234(cmpfn234 cmp);

Creates a new empty tree, and returns a pointer to it.

The parameter \c{cmp} determines the sorting criterion on the tree.
Its prototype is

\c typedef int (*cmpfn234)(void *, void *);

If you want a sorted tree, you should provide a function matching
this prototype, which returns like \cw{strcmp()} does (negative if
the first argument is smaller than the second, positive if it is
bigger, zero if they compare equal). In this case, the function
\cw{addpos234()} will not be usable on your tree (because all
insertions must respect the sorting order).

If you want an unsorted tree, pass \cw{NULL}. In this case you will
not be able to use either \cw{add234()} or \cw{del234()}, or any
other function such as \cw{find234()} which depends on a sorting
order. Your tree will become something more like an array, except
that it will efficiently support insertion and deletion as well as
lookups by numeric index.

\S{utils-freetree234} \cw{freetree234()}

\c void freetree234(tree234 *t);

Frees a tree. This function will not free the \e{elements} of the
tree (because they might not be dynamically allocated, or you might
be storing the same set of elements in more than one tree); it will
just free the tree structure itself. If you want to free all the
elements of a tree, you should empty it before passing it to
\cw{freetree234()}, by means of code along the lines of

\c while ((element = delpos234(tree, 0)) != NULL)
\c     sfree(element); /* or some more complicated free function */
\e                     iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

\S{utils-add234} \cw{add234()}

\c void *add234(tree234 *t, void *e);

Inserts a new element \c{e} into the tree \c{t}. This function
expects the tree to be sorted; the new element is inserted according
to the sort order.

If an element comparing equal to \c{e} is already in the tree, then
the insertion will fail, and the return value will be the existing
element. Otherwise, the insertion succeeds, and \c{e} is returned.

\S{utils-addpos234} \cw{addpos234()}

\c void *addpos234(tree234 *t, void *e, int index);

Inserts a new element into an unsorted tree. Since there is no
sorting order to dictate where the new element goes, you must
specify where you want it to go. Setting \c{index} to zero puts the
new element right at the start of the list; setting \c{index} to the
current number of elements in the tree puts the new element at the
end.

Return value is \c{e}, in line with \cw{add234()} (although this
function cannot fail except by running out of memory, in which case
it will bomb out and die rather than returning an error indication).

\S{utils-index234} \cw{index234()}

\c void *index234(tree234 *t, int index);

Returns a pointer to the \c{index}th element of the tree, or
\cw{NULL} if \c{index} is out of range. Elements of the tree are
numbered from zero.

\S{utils-find234} \cw{find234()}

\c void *find234(tree234 *t, void *e, cmpfn234 cmp);

Searches for an element comparing equal to \c{e} in a sorted tree.

If \c{cmp} is \cw{NULL}, the tree's ordinary comparison function
will be used to perform the search. However, sometimes you don't
want that; suppose, for example, each of your elements is a big
structure containing a \c{char *} name field, and you want to find
the element with a given name. You \e{could} achieve this by
constructing a fake element structure, setting its name field
appropriately, and passing it to \cw{find234()}, but you might find
it more convenient to pass \e{just} a name string to \cw{find234()},
supplying an alternative comparison function which expects one of
its arguments to be a bare name and the other to be a large
structure containing a name field.

Therefore, if \c{cmp} is not \cw{NULL}, then it will be used to
compare \c{e} to elements of the tree. The first argument passed to
\c{cmp} will always be \c{e}; the second will be an element of the
tree.

(See \k{utils-newtree234} for the definition of the \c{cmpfn234}
function pointer type.)

The returned value is the element found, or \cw{NULL} if the search
is unsuccessful.

\S{utils-findrel234} \cw{findrel234()}

\c void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);

This function is like \cw{find234()}, but has the additional ability
to do a \e{relative} search. The additional parameter \c{relation}
can be one of the following values:

\dt \cw{REL234_EQ}

\dd Find only an element that compares equal to \c{e}. This is
exactly the behaviour of \cw{find234()}.

\dt \cw{REL234_LT}

\dd Find the greatest element that compares strictly less than
\c{e}. \c{e} may be \cw{NULL}, in which case it finds the greatest
element in the whole tree (which could also be done by
\cw{index234(t, count234(t)-1)}).

\dt \cw{REL234_LE}

\dd Find the greatest element that compares less than or equal to
\c{e}. (That is, find an element that compares equal to \c{e} if
possible, but failing that settle for something just less than it.)

\dt \cw{REL234_GT}

\dd Find the smallest element that compares strictly greater than
\c{e}. \c{e} may be \cw{NULL}, in which case it finds the smallest
element in the whole tree (which could also be done by
\cw{index234(t, 0)}).

\dt \cw{REL234_GE}

\dd Find the smallest element that compares greater than or equal to
\c{e}. (That is, find an element that compares equal to \c{e} if
possible, but failing that settle for something just bigger than
it.)

Return value, as before, is the element found or \cw{NULL} if no
element satisfied the search criterion.

\S{utils-findpos234} \cw{findpos234()}

\c void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);

This function is like \cw{find234()}, but has the additional feature
of returning the index of the element found in the tree; that index
is written to \c{*index} in the event of a successful search (a
non-\cw{NULL} return value).

\c{index} may be \cw{NULL}, in which case this function behaves
exactly like \cw{find234()}.

\S{utils-findrelpos234} \cw{findrelpos234()}

\c void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
\c                     int *index);

This function combines all the features of \cw{findrel234()} and
\cw{findpos234()}.

\S{utils-del234} \cw{del234()}

\c void *del234(tree234 *t, void *e);

Finds an element comparing equal to \c{e} in the tree, deletes it,
and returns it.

The input tree must be sorted.

The element found might be \c{e} itself, or might merely compare
equal to it.

Return value is \cw{NULL} if no such element is found.

\S{utils-delpos234} \cw{delpos234()}

\c void *delpos234(tree234 *t, int index);

Deletes the element at position \c{index} in the tree, and returns
it.

Return value is \cw{NULL} if the index is out of range.

\S{utils-count234} \cw{count234()}

\c int count234(tree234 *t);

Returns the number of elements currently in the tree.

\S{utils-splitpos234} \cw{splitpos234()}

\c tree234 *splitpos234(tree234 *t, int index, bool before);

Splits the input tree into two pieces at a given position, and
creates a new tree containing all the elements on one side of that
position.

If \c{before} is \cw{true}, then all the items at or after position
\c{index} are left in the input tree, and the items before that
point are returned in the new tree. Otherwise, the reverse happens:
all the items at or after \c{index} are moved into the new tree, and
those before that point are left in the old one.

If \c{index} is equal to 0 or to the number of elements in the input
tree, then one of the two trees will end up empty (and this is not
an error condition). If \c{index} is further out of range in either
direction, the operation will fail completely and return \cw{NULL}.

This operation completes in \cw{O(log N)} time, no matter how large
the tree or how balanced or unbalanced the split.

\S{utils-split234} \cw{split234()}

\c tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);

Splits a sorted tree according to its sort order.

\c{rel} can be any of the relation constants described in
\k{utils-findrel234}, \e{except} for \cw{REL234_EQ}. All the
elements having that relation to \c{e} will be transferred into the
new tree; the rest will be left in the old one.

The parameter \c{cmp} has the same semantics as it does in
\cw{find234()}: if it is not \cw{NULL}, it will be used in place of
the tree's own comparison function when comparing elements to \c{e},
in such a way that \c{e} itself is always the first of its two
operands.

Again, this operation completes in \cw{O(log N)} time, no matter how
large the tree or how balanced or unbalanced the split.

\S{utils-join234} \cw{join234()}

\c tree234 *join234(tree234 *t1, tree234 *t2);

Joins two trees together by concatenating the lists they represent.
All the elements of \c{t2} are moved into \c{t1}, in such a way that
they appear \e{after} the elements of \c{t1}. The tree \c{t2} is
freed; the return value is \c{t1}.

If you apply this function to a sorted tree and it violates the sort
order (i.e. the smallest element in \c{t2} is smaller than or equal
to the largest element in \c{t1}), the operation will fail and
return \cw{NULL}.

This operation completes in \cw{O(log N)} time, no matter how large
the trees being joined together.

\S{utils-join234r} \cw{join234r()}

\c tree234 *join234r(tree234 *t1, tree234 *t2);

Joins two trees together in exactly the same way as \cw{join234()},
but this time the combined tree is returned in \c{t2}, and \c{t1} is
destroyed. The elements in \c{t1} still appear before those in
\c{t2}.

Again, this operation completes in \cw{O(log N)} time, no matter how
large the trees being joined together.

\S{utils-copytree234} \cw{copytree234()}

\c tree234 *copytree234(tree234 *t, copyfn234 copyfn,
\c                      void *copyfnstate);

Makes a copy of an entire tree.

If \c{copyfn} is \cw{NULL}, the tree will be copied but the elements
will not be; i.e. the new tree will contain pointers to exactly the
same physical elements as the old one.

If you want to copy each actual element during the operation, you
can instead pass a function in \c{copyfn} which makes a copy of each
element. That function has the prototype

\c typedef void *(*copyfn234)(void *state, void *element);

and every time it is called, the \c{state} parameter will be set to
the value you passed in as \c{copyfnstate}.

\H{utils-dsf} Disjoint set forests

This section describes a set of functions implementing the data
structure variously known as \q{union-find} or \q{Tarjan's disjoint
set forest}. In this code base, it's universally abbreviated as a
\q{dsf}.

A dsf represents a collection of elements partitioned into
\q{equivalence classes}, in circumstances where equivalences are added
incrementally. That is, all elements start off considered to be
different, and you gradually declare more and more of them to be equal
via the \cw{dsf_merge()} operation, which says that two particular
elements should be regarded as equal from now on.

For example, if I start off with A,B,U,V all distinct, and I merge A
with B and merge U with V, then the structure will tell me that A and
U are not equivalent. But if I then merge B with V, then after that,
the structure will tell me that A and U \e{are} equivalent, by
following the transitive chain of equivalences it knows about.

The dsf data structure is therefore ideal for tracking incremental
connectivity in an undirected graph (again, \q{incremental} meaning
that you only ever add edges, never delete them), and other
applications in which you gradually acquire knowledge you didn't
previously have about what things are the same as each other. It's
used extensively in puzzle solver and generator algorithms, and
sometimes during gameplay as well.

The time complexity of dsf operations is not \e{quite} constant time,
in theory, but it's so close to it as to make no difference in
practice. In particular, any time a dsf has to do non-trivial work, it
updates the structure so that that work won't be needed a second time.
Use dsf operations without worrying about how long they take!

For some puzzle-game applications, it's useful to augment this data
structure with extra information about how the elements of an
equivalence class relate to each other. There's more than one way you
might do this; the one supported here is useful in cases where the
objects you're tracking are going to end up in one of two states (say,
black/white, or on/off), and for any two objects you either know that
they're in the same one of those states, or you know they're in
opposite states, or you don't know which yet. Puzzles calls this a
\q{flip dsf}: it tracks whether objects in the same equivalence class
are flipped relative to each other.

As well as querying whether two elements are equivalent, this dsf
implementation also allows you to ask for the number of elements in a
given equivalence class, and the smallest element in the class. (The
latter is used, for example, to decide which square to print the clue
in each region of a Keen puzzle.)

\S{utils-dsf-new} \cw{dsf_new()}, \cw{dsf_new_flip()}, \cw{dsf_new_min()}

\c DSF *dsf_new(int size);
\c DSF *dsf_new_flip(int size);
\c DSF *dsf_new_min(int size);

Each of these functions allocates space for a dsf describing \c{size}
elements, and initialises it so that every element is in an
equivalence class by itself.

The elements described by the dsf are represented by the integers from
\cw{0} to \cw{size-1} inclusive.

\cw{dsf_new_flip()} will create a dsf which has the extra ability to
track whether objects in the same equivalence class are flipped
relative to each other.

\cw{dsf_new_min()} will create a dsf which has the extra ability to
track the smallest element of each equivalence class.

The returned object from any of these functions must be freed using
\cw{dsf_free()}.

\S{utils-dsf-free} \cw{dsf_free()}

\c void dsf_free(DSF *dsf);

Frees a dsf allocated by any of the \cw{dsf_new()} functions.

\S{utils-dsf-reinit} \cw{dsf_reinit()}

\c void dsf_reinit(DSF *dsf);

Reinitialises an existing dsf to the state in which all elements are
distinct, without having to free and reallocate it.

\S{utils-dsf-copy} \cw{dsf_copy()}

\c void dsf_copy(DSF *to, DSF *from);

Copies the contents of one dsf over the top of another. Everything
previously stored in \c{to} is overwritten.

The two dsfs must have been created with the same size, and the
destination dsf may not have any extra information that the source dsf
does not have.

\S{utils-dsf-merge} \cw{dsf_merge()}

\c void dsf_merge(DSF *dsf, int v1, int v2);

Updates a dsf so that elements \c{v1} and \c{v2} will now be
considered to be in the same equivalence class. If they were already
in the same class, this function will safely do nothing.

This function may not be called on a flip dsf. Use \cw{dsf_merge_flip}
instead.

\S{utils-dsf-canonify} \cw{dsf_canonify()}

\c int dsf_canonify(DSF *dsf, int val);

Returns the \q{canonical} element of the equivalence class in the dsf
containing \c{val}. This will be some element of the same equivalence
class. So in order to determine whether two elements are in the same
equivalence class, you can call \cw{dsf_canonify} on both of them, and
compare the results.

Canonical elements don't necessarily stay the same if the dsf is
mutated via \c{dsf_merge}. But between two calls to \c{dsf_merge},
they stay the same.

\S{utils-dsf-size} \cw{dsf_size()}

\c int dsf_size(DSF *dsf, int val);

Returns the number of elements currently in the equivalence class
containing \c{val}.

\c{val} itself counts, so in a newly created dsf, the return value
will be 1.

\S{utils-dsf-merge-flip} \cw{dsf_merge_flip()}

\c void edsf_merge(DSF *dsf, int v1, int v2, bool flip);

Updates a flip dsf so that elements \c{v1} and \c{v2} are in the same
equivalence class. If \c{flip} is \cw{false}, they will be regarded as
in the same state as each other; if \c{flip} is \cw{true} then they
will be regarded as being in opposite states.

If \c{v1} and \c{v2} were already in the same equivalence class, then
the new value of \c{flip} will be checked against what the edsf
previously believed, and an assertion failure will occur if you
contradict that.

For example, if you start from a blank flip dsf and do this:

\c dsf_merge_flip(dsf, 0, 1, false);
\c dsf_merge_flip(dsf, 1, 2, true);

then it will create a dsf in which elements 0,1,2 are all in the same
class, with 0,1 in the same state as each other and 2 in the opposite
state from both. And then this call will do nothing, because it agrees
with what the dsf already knew:

\c dsf_merge_flip(dsf, 0, 2, true);

But this call will fail an assertion:

\c dsf_merge_flip(dsf, 0, 2, false);

\S{utils-dsf-canonify-flip} \cw{dsf_canonify_flip()}

\c int dsf_canonify_flip(DSF *dsf, int val, bool *inverse);

Like \c{dsf_canonify()}, this returns the canonical element of the
equivalence class of a dsf containing \c{val}.

However, it may only be called on a flip dsf, and it also fills in
\c{*flip} with a flag indicating whether \c{val} and the canonical
element are in opposite states: \cw{true} if they are in opposite
states, or \cw{false} if they're in the same state.

So if you want to know the relationship between \c{v1} and \c{v2}, you
can do this:

\c bool inv1, inv2;
\c int canon1 = dsf_canonify_flip(dsf, v1, &inv1);
\c int canon2 = dsf_canonify_flip(dsf, v2, &inv2);
\c if (canon1 != canon2) {
\c     // v1 and v2 have no known relation
\c } else if (inv1 == inv2) {
\c     // v1 and v2 are known to be in the same state as each other
\c } else {
\c     // v1 and v2 are known to be in opposite states
\c }

\S{utils-dsf-minimal} \cw{dsf_minimal()}

\c int dsf_minimal(DSF *dsf, int val);

Returns the smallest element of the equivalence class in the dsf
containing \c{val}.

For this function to work, the dsf must have been created using
\cw{dsf_new_min()}.

\H{utils-tdq} To-do queues

This section describes a set of functions implementing a \q{to-do
queue}, a simple de-duplicating to-do list mechanism. The code calls
this a \q{tdq}.

A tdq can store integers up to a given size (specified at creation
time). But it can't store the same integer more than once. So you can
quickly \e{make sure} an integer is in the queue (which will do
nothing if it's already there), and you can quickly pop an integer
from the queue and return it, both in constant time.

The idea is that you might use this in a game solver, in the kind of
game where updating your knowledge about one square of a grid means
there's a specific other set of squares (such as its neighbours) where
it's now worth attempting further deductions. So you keep a tdq of all
the grid squares you plan to look at next, and every time you make a
deduction in one square, you add the neighbouring squares to the tdq
to make sure they get looked at again after that.

In solvers where deductions are mostly localised, this avoids the
slowdown of having to find the next thing to do every time by looping
over the whole grid: instead, you can keep checking the tdq for
\e{specific} squares to look at, until you run out.

However, it's common to have games in which \e{most} deductions are
localised, but not all. In that situation, when your tdq is empty, you
can re-fill it with every square in the grid using \cw{tdq_fill()},
which will force an iteration over everything again. And then if the
tdq becomes empty \e{again} without you having made any progress, give
up.

\S{utils-tdq-new} \cw{tdq_new()}

\c tdq *tdq_new(int n);

Allocates space for a tdq that tracks items from \cw{0} to \cw{size-1}
inclusive.

\S{utils-tdq-free} \cw{tdq_free()}

\c void tdq_free(tdq *tdq);

Frees a tdq.

\S{utils-tdq-add} \cw{tdq_add()}

\c void tdq_add(tdq *tdq, int k);

Adds the value \c{k} to a tdq. If \c{k} was already in the to-do list,
does nothing.

\S{utils-tdq-remove} \cw{tdq_remove()}

\c int tdq_remove(tdq *tdq);

Removes one item from the tdq, and returns it. If the tdq is empty,
returns \cw{-1}.

\S{utils-tdq-fill} \cw{tdq_fill()}

\c void tdq_fill(tdq *tdq);

Fills a tdq with every element it can possibly keep track of.

\H{utils-findloop} Finding loops in graphs and grids

Many puzzles played on grids or graphs have a common gameplay element
of connecting things together into paths in such a way that you need
to avoid making loops (or, perhaps, making the \e{wrong} kind of
loop).

Just determining \e{whether} a loop exists in a graph is easy, using a
dsf tracking connectivity between the vertices. Simply iterate over
each edge of the graph, merging the two vertices at each end of the
edge \dash but before you do that, check whether those vertices are
\e{already} known to be connected to each other, and if they are, then
the new edge is about to complete a loop.

But if you also want to identify \e{exactly} the set of edges that are
part of any loop, e.g. to highlight the whole loop red during
gameplay, then that's a harder problem. This API is provided here for
all puzzles to use for that purpose.

\S{utils-findloop-new-state} \cw{findloop_new_state()}

\c struct findloopstate *findloop_new_state(int nvertices);

Allocates a new state structure for the findloop algorithm, capable of
handling a graph with up to \c{nvertices} vertices. The vertices will
be represented by integers between \c{0} and \c{nvertices-1} inclusive.

\S{utils-findloop-free-state} \cw{findloop_free_state()}

\c void findloop_free_state(struct findloopstate *state);

Frees a state structure allocated by \cw{findloop_new_state()}.

\S{utils-findloop-run} \cw{findloop_run()}

\c bool findloop_run(struct findloopstate *state, int nvertices,
\c                   neighbour_fn_t neighbour, void *ctx);

Runs the loop-finding algorithm, which will explore the graph and
identify whether each edge is or is not part of any loop.

The algorithm will call the provided function \c{neighbour} to list
the neighbouring vertices of each vertex. It should have this
prototype:

\c int neighbour(int vertex, void *ctx);

In this callback, \c{vertex} will be the index of a vertex when the
algorithm \e{first} calls it for a given vertex. The function should
return the index of one of that vertex's neighbours, or a negative
number if there are none.

If the function returned a vertex, the algorithm will then call
\c{neighbour} again with a \e{negative} number as the \c{vertex}
parameter, which means \q{please give me another neighbour of the same
vertex as last time}. Again, the function should return a vertex
index, or a negative number to indicate that there are no more
vertices.

The \c{ctx} parameter passed to \cw{findloop_run()} is passed on
unchanged to \c{neighbour}, so you can point that at your game state
or solver state or whatever.

The return value is \cw{true} if at least one loop exists in the
graph, and \cw{false} if no loop exists. Also, the algorithm state
will have been filled in with information that the following query
functions can use to ask about individual graph edges.

\S{utils-findloop-is-loop-edge} \cw{findloop_is_loop_edge()}

\c bool findloop_is_loop_edge(struct findloopstate *state,
\c                            int u, int v);

Queries whether the graph edge between vertices \c{u} and \c{v} is
part of a loop. If so, the return value is \cw{true}, otherwise
\cw{false}.

\S{utils-findloop-is-bridge} \cw{findloop_is_bridge()}

\c bool findloop_is_bridge(struct findloopstate *pv,
\c     int u, int v, int *u_vertices, int *v_vertices);

Queries whether the graph edge between vertices \c{u} and \c{v} is a
\q{bridge}, i.e. an edge which would break the graph into (more)
disconnected components if it were removed.

This is the exact inverse of the \q{loop edge} criterion: a vertex
returns \cw{true} from \cw{findloop_is_loop_edge()} if and only if it
returns \cw{false} from \cw{findloop_is_bridge()}, and vice versa.

However, \cw{findloop_is_bridge()} returns more information. If it
returns \cw{true}, then it also fills in \c{*u_vertices} and
\c{*v_vertices} with the number of vertices connected to the \c{u} and
\c{v} sides of the bridge respectively.

For example, if you have three vertices A,B,C all connected to each
other, and four vertices U,V,W,X all connected to each other, and a
single edge between A and V, then calling \cw{findloop_is_bridge()} on
the pair A,V will return true (removing that edge would separate the
two sets from each other), and will report that there are three
vertices on the A side and four on the V side.

\H{utils-combi} Choosing r things out of n

This section describes a small API for iterating over all combinations
of r things out of n.

For example, if you asked for all combinations of 3 things out of 5,
you'd get back the sets \{0,1,2\}, \{0,1,3\}, \{0,1,4\}, \{0,2,3\},
\{0,2,4\}, \{0,3,4\}, \{1,2,3\}, \{1,2,4\}, \{1,3,4\}, and \{2,3,4\}.

These functions use a structure called a \c{combi_ctx}, which contains
an element \c{int *a} holding each returned combination, plus other
fields for implementation use only.

\S{utils-combi-new} \cw{new_combi()}

\c combi_ctx *new_combi(int r, int n);

Allocates a new \c{combi_ctx} structure for enumerating r things out
of n.

\S{utils-combi-free} \cw{free_combi()}

\c void free_combi(combi_ctx *combi);

Frees a \c{combi_ctx} structure.

\S{utils-combi-reset} \cw{reset_combi()}

\c void reset_combi(combi_ctx *combi);

Resets an existing \c{combi_ctx} structure to the start of its
iteration

\S{utils-combi-next} \cw{next_combi()}

\c combi_ctx *next_combi(combi_ctx *combi);

Requests a combination from a \c{combi_ctx}.

If there are none left to return, the return value is \cw{NULL}.
Otherwise, it returns the input structure \c{combi}, indicating that
it has filled in \cw{combi->a[0]}, \cw{combi->a[1]}, ...,
\cw{combi->a[r-1]} with an increasing sequence of distinct integers
from \cw{0} to \cw{n-1} inclusive.

\H{utils-misc} Miscellaneous utility functions and macros

This section contains all the utility functions which didn't
sensibly fit anywhere else.

\S{utils-maxmin} \cw{max()} and \cw{min()}

The main Puzzles header file defines the pretty standard macros
\cw{max()} and \cw{min()}, each of which is given two arguments and
returns the one which compares greater or less respectively.

These macros may evaluate their arguments multiple times. Avoid side
effects.

\S{utils-max-digits} \cw{MAX_DIGITS()}

The \cw{MAX_DIGITS()} macro, defined in the main Puzzles header file,
takes a type (or a variable of that type) and expands to an integer
constant representing a reasonable upper bound on the number of
characters that a number of that type could expand to when formatted
as a decimal number using the \c{%u} or \c{%d} format of
\cw{printf()}.  This is useful for allocating a fixed-size buffer
that's guaranteed to be big enough to \cw{sprintf()} a value into.
Don't forget to add one for the trailing \cw{'\\0'}!

\S{utils-pi} \cw{PI}

The main Puzzles header file defines a macro \cw{PI} which expands
to a floating-point constant representing pi.

(I've never understood why ANSI's \cw{<math.h>} doesn't define this.
It'd be so useful!)

\S{utils-obfuscate-bitmap} \cw{obfuscate_bitmap()}

\c void obfuscate_bitmap(unsigned char *bmp, int bits, bool decode);

This function obscures the contents of a piece of data, by
cryptographic methods. It is useful for games of hidden information
(such as Mines, Guess or Black Box), in which the game ID
theoretically reveals all the information the player is supposed to
be trying to guess. So in order that players should be able to send
game IDs to one another without accidentally spoiling the resulting
game by looking at them, these games obfuscate their game IDs using
this function.

Although the obfuscation function is cryptographic, it cannot
properly be called encryption because it has no key. Therefore,
anybody motivated enough can re-implement it, or hack it out of the
Puzzles source, and strip the obfuscation off one of these game IDs
to see what lies beneath. (Indeed, they could usually do it much
more easily than that, by entering the game ID into their own copy
of the puzzle and hitting Solve.) The aim is not to protect against
a determined attacker; the aim is simply to protect people who
wanted to play the game honestly from \e{accidentally} spoiling
their own fun.

The input argument \c{bmp} points at a piece of memory to be
obfuscated. \c{bits} gives the length of the data. Note that that
length is in \e{bits} rather than bytes: if you ask for obfuscation
of a partial number of bytes, then you will get it. Bytes are
considered to be used from the top down: thus, for example, setting
\c{bits} to 10 will cover the whole of \cw{bmp[0]} and the \e{top
two} bits of \cw{bmp[1]}. The remainder of a partially used byte is
undefined (i.e. it may be corrupted by the function).

The parameter \c{decode} is \cw{false} for an encoding operation,
and \cw{true} for a decoding operation. Each is the inverse of the
other. (There's no particular reason you shouldn't obfuscate by
decoding and restore cleartext by encoding, if you really wanted to;
it should still work.)

The input bitmap is processed in place.

\S{utils-bin2hex} \cw{bin2hex()}

\c char *bin2hex(const unsigned char *in, int inlen);

This function takes an input byte array and converts it into an
ASCII string encoding those bytes in (lower-case) hex. It returns a
dynamically allocated string containing that encoding.

This function is useful for encoding the result of
\cw{obfuscate_bitmap()} in printable ASCII for use in game IDs.

\S{utils-hex2bin} \cw{hex2bin()}

\c unsigned char *hex2bin(const char *in, int outlen);

This function takes an ASCII string containing hex digits, and
converts it back into a byte array of length \c{outlen}. If there
aren't enough hex digits in the string, the contents of the
resulting array will be undefined.

This function is the inverse of \cw{bin2hex()}.

\S{utils-fgetline} \cw{fgetline()}

\c char *fgetline(FILE *fp);

This function reads a single line of text from a standard C input
stream, and returns it as a dynamically allocated string. The returned
string still has a newline on the end.

\S{utils-arraysort} \cw{arraysort()}

Sorts an array, with slightly more flexibility than the standard C
\cw{qsort()}.

This function is really implemented as a macro, so it doesn't have a
prototype as such. But you could imagine it having a prototype like
this:

\c void arraysort(element_t *array, size_t nmemb,
\c                arraysort_cmpfn_t cmp, void *ctx);

in which \c{element_t} is an unspecified type.

(Really, there's an underlying function that takes an extra parameter
giving the size of each array element. But callers are encouraged to
use this macro version, which fills that in automatically using
\c{sizeof}.)

This function behaves essentially like \cw{qsort()}: it expects
\c{array} to point to an array of \c{nmemb} elements, and it will sort
them in place into the order specified by the comparison function
\c{cmp}.

The comparison function should have this prototype:

\c int cmp(const void *a, const void *b, void *ctx);

in which \c{a} and \c{b} point at the two elements to be compared, and
the return value is negative if \cw{a<b} (that is, \c{a} should appear
before \c{b} in the output array), positive if \cw{a>b}, or zero if
\c{a=b}.

The \c{ctx} parameter to \cw{arraysort()} is passed directly to the
comparison function. This is the feature that makes \cw{arraysort()}
more flexible than standard \cw{qsort()}: it lets you vary the sorting
criterion in a dynamic manner without having to write global variables
in the caller for the compare function to read.

\S{utils-colour-mix} \cw{colour_mix()}

\c void colour_mix(const float src1[3], const float src2[3], float p,
\c                 float dst[3]);

This function mixes the colours \c{src1} and \c{src2} in specified
proportions, producing \c{dst}.  \c{p} is the proportion of \c{src2}
in the result.  So if \c{p} is \cw{1.0}, \cw{dst} will be the same as
\c{src2}.  If \c{p} is \cw{0.0}, \cw{dst} will be the same as
\c{src1}.  And if \c{p} is somewhere in between, so will \c{dst} be.
\c{p} is not restricted to the range \cw{0.0} to \cw{1.0}.  Values
outside that range will produce extrapolated colours, which may be
useful for some purposes, but may also produce impossible colours.

\S{utils-game-mkhighlight} \cw{game_mkhighlight()}

\c void game_mkhighlight(frontend *fe, float *ret,
\c                       int background, int highlight, int lowlight);

It's reasonably common for a puzzle game's graphics to use
highlights and lowlights to indicate \q{raised} or \q{lowered}
sections. Fifteen, Sixteen and Twiddle are good examples of this.

Puzzles using this graphical style are running a risk if they just
use whatever background colour is supplied to them by the front end,
because that background colour might be too light or dark to see any
highlights on at all. (In particular, it's not unheard of for the
front end to specify a default background colour of white.)

Therefore, such puzzles can call this utility function from their
\cw{colours()} routine (\k{backend-colours}). You pass it your front
end handle, a pointer to the start of your return array, and three
colour indices. It will:

\b call \cw{frontend_default_colour()} (\k{frontend-default-colour})
to fetch the front end's default background colour

\b alter the brightness of that colour if it's unsuitable

\b define brighter and darker variants of the colour to be used as
highlights and lowlights

\b write those results into the relevant positions in the \c{ret}
array.

Thus, \cw{ret[background*3]} to \cw{ret[background*3+2]} will be set
to RGB values defining a sensible background colour, and similary
\c{highlight} and \c{lowlight} will be set to sensible colours.

Either \c{highlight} or \c{lowlight} may be passed in as \cw{-1} to
indicate that the back-end does not require a highlight or lowlight
colour, respectively.

\S{utils-game-mkhighlight-specific} \cw{game_mkhighlight_specific()}

\c void game_mkhighlight_specific(frontend *fe, float *ret,
\c     int background, int highlight, int lowlight);

This function behaves exactly like \cw{game_mkhighlight()}, except
that it expects the background colour to have been filled in
\e{already} in the elements \cw{ret[background*3]} to
\cw{ret[background*3+2]}. It will fill in the other two colours as
brighter and darker versions of that.

This is useful if you want to show relief sections of a puzzle in more
than one base colour.

\S{utils-button2label} \cw{button2label()}

\c char *button2label(int button);

This function generates a descriptive text label for \cw{button},
which should be a button code that can be passed to the midend. For
example, calling this function with \cw{CURSOR_UP} will result in the
string \cw{"Up"}. This function should only be called when the
\cw{key_label} item returned by a backend's \cw{request_keys()}
(\k{backend-request-keys}) function has its \cw{label} field set to
\cw{NULL}; in this case, the corresponding \cw{button} field can be
passed to this function to obtain an appropriate label. If, however,
the field is not \cw{NULL}, this function should not be called with
the corresponding \cw{button} field.

The returned string is dynamically allocated and should be
\cw{sfree}'d by the caller.

\S{utils-move-cursor} \cw{move_cursor()}

\c void move_cursor(int button, int *x, int *y, int w, int h,
\c                  bool wrap);

This function can be called by \cw{interpret_move()} to implement the
default keyboard API for moving a cursor around a grid.

\c{button} is the same value passed in to \cw{interpret_move()}. If
it's not any of \cw{CURSOR_UP}, \cw{CURSOR_DOWN}, \cw{CURSOR_LEFT} or
\cw{CURSOR_RIGHT}, the function will do nothing.

\c{x} and \c{y} point to two integers which on input give the current
location of a cursor in a square grid. \c{w} and \c{h} give the
dimensions of the grid. On return, \c{x} and \c{y} are updated to give
the cursor's new position according to which arrow key was pressed.

This function assumes that the grid coordinates run from \cw{0} to
\cw{w-1} inclusive (left to right), and from \cw{0} to \cw{h-1}
inclusive (top to bottom).

If \c{wrap} is \cw{true}, then trying to move the cursor off any edge
of the grid will result in it wrapping round to the corresponding
square on the opposite edge. If \c{wrap} is \cw{false}, such a move
will have no effect.

\S{utils-divvy-rectangle} \cw{divvy_rectangle()}

\c int *divvy_rectangle(int w, int h, int k, random_state *rs);

Invents a random division of a rectangle into same-sized polyominoes,
such as is found in the block layout of a Solo puzzle in jigsaw mode,
or the solution to a Palisade puzzle.

\c{w} and \c{h} are the dimensions of the rectangle. \c{k} is the size
of polyomino desired. It must be a factor of \c{w*h}.

\c{rs} is a \cw{random_state} used to supply the random numbers to
select a random division of the rectangle.

The return value is a dsf (see \k{utils-dsf}) whose equivalence
classes correspond to the polyominoes that the rectangle is divided
into. The indices of the dsf are of the form \c{y*w+x}, for the cell
with coordinates \cw{x,y}.

\S{utils-domino-layout} \cw{domino_layout()}

\c int *domino_layout(int w, int h, random_state *rs);

Invents a random tiling of a rectangle with dominoes.

\c{w} and \c{h} are the dimensions of the rectangle. If they are both
odd, then one square will be left untiled.

\c{rs} is a \cw{random_state} used to supply the random numbers to
select a random division of the rectangle.

The return value is an array in which element \c{y*w+x} represents the
cell with coordinates \cw{x,y}. Each element of the array gives the
index (in the same representation) of the other end of its domino. If
there's a left-over square, then that element contains its own index.

\S{utils-domino-layout-prealloc} \cw{domino_layout_prealloc()}

\c void domino_layout_prealloc(int w, int h, random_state *rs,
\c                             int *grid, int *grid2, int *list);

Just like \cw{domino_layout()}, but does no memory allocation. You can
use this to save allocator overhead if you expect to need to generate
many domino tilings of the same grid.

\c{grid} and \c{grid2} should each have space for \cw{w*h} ints.
\c{list} should have space for \c{2*w*h} ints.

The returned array is delivered in \c{grid}.

\C{writing} How to write a new puzzle

This chapter gives a guide to how to actually write a new puzzle:
where to start, what to do first, how to solve common problems.

The previous chapters have been largely composed of facts. This one
is mostly advice.

\H{writing-editorial} Choosing a puzzle

Before you start writing a puzzle, you have to choose one. Your
taste in puzzle games is up to you, of course; and, in fact, you're
probably reading this guide because you've \e{already} thought of a
game you want to write. But if you want to get it accepted into the
official Puzzles distribution, then there's a criterion it has to
meet.

The current Puzzles editorial policy is that all games should be
\e{fair}. A fair game is one which a player can only fail to complete
through demonstrable lack of skill \dash that is, such that a better
player presented with the same game state would have \e{known} to do
something different.

For a start, that means every game presented to the user must have
\e{at least one solution}. Giving the unsuspecting user a puzzle which
is actually impossible is not acceptable.

(An exception to this: if the user has selected some non-default
option which is clearly labelled as potentially unfair, \e{then}
you're allowed to generate possibly insoluble puzzles, because the
user isn't unsuspecting any more. Same Game and Mines both have
options of this type.)

Secondly, if the game includes hidden information, then it must be
possible to deduce a correct move at every stage from the currently
available information. It's not enough that there should exist some
sequence of moves which will get from the start state to the solved
state, if the player doesn't necessarily have enough information to
\e{find} that solution. For example, in the card solitaire game
Klondike, it's possible to reach a dead end because you had an
arbitrary choice to make on no information, and made it the wrong way,
which violates the fairness criterion, because a better player
couldn't have known they needed to make the other choice.

(Of course, games in this collection always have an Undo function, so
if you did take the wrong route through a Klondike game, you could use
Undo to back up and try a different choice. This doesn't count. In a
fair game, you should be able to determine a correct move from the
information visible \e{now}, without having to make moves to get more
information that you can then back up and use.)

Sometimes you can adjust the rules of an unfair puzzle to make it meet
this definition of fairness. For example, more than one implementation
of solitaire-style games (including card solitaires and Mahjong
Solitaire) include a UI action to shuffle the remaining cards or tiles
without changing their position; this action might be available at any
time with a time or points penalty, or it might be illegal to use
unless you have no other possible move. Adding an option like this
would make a game \e{technically} fair, but it's better to avoid even
that if you can.

Providing a \e{unique} solution is a little more negotiable; it
depends on the puzzle. Solo would have been of unacceptably low
quality if it didn't always have a unique solution, whereas Twiddle
inherently has multiple solutions by its very nature and it would
have been meaningless to even \e{suggest} making it uniquely
soluble. Somewhere in between, Flip could reasonably be made to have
unique solutions (by enforcing a zero-dimension kernel in every
generated matrix) but it doesn't seem like a serious quality problem
that it doesn't.

Of course, you don't \e{have} to care about all this. There's
nothing stopping you implementing any puzzle you want to if you're
happy to maintain your puzzle yourself, distribute it from your own
web site, fork the Puzzles code completely, or anything like that.
It's free software; you can do what you like with it. But any game
that you want to be accepted into \e{my} Puzzles code base has to
satisfy the fairness criterion, which means all randomly generated
puzzles must have a solution (unless the user has deliberately
chosen otherwise) and it must be possible \e{in theory} to find that
solution without having to guess.

\H{writing-gs} Getting started

The simplest way to start writing a new puzzle is to copy
\c{nullgame.c}. This is a template puzzle source file which does
almost nothing, but which contains all the back end function
prototypes and declares the back end data structure correctly. It is
built every time the rest of Puzzles is built, to ensure that it
doesn't get out of sync with the code and remains buildable.

So start by copying \c{nullgame.c} into your new source file. Then
you'll gradually add functionality until the very boring Null Game
turns into your real game.

Next you'll need to add your puzzle to the build scripts, in order to
compile it conveniently. Puzzles is a CMake project, so you do this by
adding a \cw{puzzle()} statement to CMakeLists.txt. Look at the
existing ones to see what those look like, and add one that looks
similar.

Once your source file is building, you can move on to the fun bit.

\S{writing-generation} Puzzle generation

Randomly generating instances of your puzzle is almost certain to be
the most difficult part of the code, and also the task with the
highest chance of turning out to be completely infeasible. Therefore
I strongly recommend doing it \e{first}, so that if it all goes
horribly wrong you haven't wasted any more time than you absolutely
had to. What I usually do is to take an unmodified \c{nullgame.c},
and start adding code to \cw{new_game_desc()} which tries to
generate a puzzle instance and print it out using \cw{printf()}.
Once that's working, \e{then} I start connecting it up to the return
value of \cw{new_game_desc()}, populating other structures like
\c{game_params}, and generally writing the rest of the source file.

There are many ways to generate a puzzle which is known to be
soluble. In this section I list all the methods I currently know of,
in case any of them can be applied to your puzzle. (Not all of these
methods will work, or in some cases even make sense, for all
puzzles.)

Some puzzles are mathematically tractable, meaning you can work out
in advance which instances are soluble. Sixteen, for example, has a
parity constraint in some settings which renders exactly half the
game space unreachable, but it can be mathematically proved that any
position not in that half \e{is} reachable. Therefore, Sixteen's
grid generation simply consists of selecting at random from a well
defined subset of the game space. Cube in its default state is even
easier: \e{every} possible arrangement of the blue squares and the
cube's starting position is soluble!

Another option is to redefine what you mean by \q{soluble}. Black
Box takes this approach. There are layouts of balls in the box which
are completely indistinguishable from one another no matter how many
beams you fire into the box from which angles, which would normally
be grounds for declaring those layouts unfair; but fortunately,
detecting that indistinguishability is computationally easy. So
Black Box doesn't demand that your ball placements match its own; it
merely demands that your ball placements be \e{indistinguishable}
from the ones it was thinking of. If you have an ambiguous puzzle,
then any of the possible answers is considered to be a solution.
Having redefined the rules in that way, any puzzle is soluble again.

Those are the simple techniques. If they don't work, you have to get
cleverer.

One way to generate a soluble puzzle is to start from the solved
state and make inverse moves until you reach a starting state. Then
you know there's a solution, because you can just list the inverse
moves you made and make them in the opposite order to return to the
solved state.

This method can be simple and effective for puzzles where you get to
decide what's a starting state and what's not. In Pegs, for example,
the generator begins with one peg in the centre of the board and
makes inverse moves until it gets bored; in this puzzle, valid
inverse moves are easy to detect, and \e{any} state that's reachable
from the solved state by inverse moves is a reasonable starting
position. So Pegs just continues making inverse moves until the
board satisfies some criteria about extent and density, and then
stops and declares itself done.

For other puzzles, it can be a lot more difficult. Same Game uses
this strategy too, and it's lucky to get away with it at all: valid
inverse moves aren't easy to find (because although it's easy to
insert additional squares in a Same Game position, it's difficult to
arrange that \e{after} the insertion they aren't adjacent to any
other squares of the same colour), so you're constantly at risk of
running out of options and having to backtrack or start again. Also,
Same Game grids never start off half-empty, which means you can't
just stop when you run out of moves \dash you have to find a way to
fill the grid up \e{completely}.

The other way to generate a puzzle that's soluble is to start from
the other end, and actually write a \e{solver}. This tends to ensure
that a puzzle has a \e{unique} solution over and above having a
solution at all, so it's a good technique to apply to puzzles for
which that's important.

One theoretical drawback of generating soluble puzzles by using a
solver is that your puzzles are restricted in difficulty to those
which the solver can handle. (Most solvers are not fully general:
many sets of puzzle rules are NP-complete or otherwise nasty, so
most solvers can only handle a subset of the theoretically soluble
puzzles.) It's been my experience in practice, however, that this
usually isn't a problem; computers are good at very different things
from humans, and what the computer thinks is nice and easy might
still be pleasantly challenging for a human. For example, when
solving Dominosa puzzles I frequently find myself using a variety of
reasoning techniques that my solver doesn't know about; in
principle, therefore, I should be able to solve the puzzle using
only those techniques it \e{does} know about, but this would involve
repeatedly searching the entire grid for the one simple deduction I
can make. Computers are good at this sort of exhaustive search, but
it's been my experience that human solvers prefer to do more complex
deductions than to spend ages searching for simple ones. So in many
cases I don't find my own playing experience to be limited by the
restrictions on the solver.

(This isn't \e{always} the case. Solo is a counter-example;
generating Solo puzzles using a simple solver does lead to
qualitatively easier puzzles. Therefore I had to make the Solo
solver rather more advanced than most of them.)

There are several different ways to apply a solver to the problem of
generating a soluble puzzle. I list a few of them below.

The simplest approach is brute force: randomly generate a puzzle,
use the solver to see if it's soluble, and if not, throw it away and
try again until you get lucky. This is often a viable technique if
all else fails, but it tends not to scale well: for many puzzle
types, the probability of finding a uniquely soluble instance
decreases sharply as puzzle size goes up, so this technique might
work reasonably fast for small puzzles but take (almost) forever at
larger sizes. Still, if there's no other alternative it can be
usable: Pattern and Dominosa both use this technique. (However,
Dominosa has a means of tweaking the randomly generated grids to
increase the \e{probability} of them being soluble, by ruling out
one of the most common ambiguous cases. This improved generation
speed by over a factor of 10 on the highest preset!)

An approach which can be more scalable involves generating a grid
and then tweaking it to make it soluble. This is the technique used
by Mines and also by Net: first a random puzzle is generated, and
then the solver is run to see how far it gets. Sometimes the solver
will get stuck; when that happens, examine the area it's having
trouble with, and make a small random change in that area to allow
it to make more progress. Continue solving (possibly even without
restarting the solver), tweaking as necessary, until the solver
finishes. Then restart the solver from the beginning to ensure that
the tweaks haven't caused new problems in the process of solving old
ones (which can sometimes happen).

This strategy works well in situations where the usual solver
failure mode is to get stuck in an easily localised spot. Thus it
works well for Net and Mines, whose most common failure mode tends
to be that most of the grid is fine but there are a few widely
separated ambiguous sections; but it would work less well for
Dominosa, in which the way you get stuck is to have scoured the
whole grid and not found anything you can deduce \e{anywhere}. Also,
it relies on there being a low probability that tweaking the grid
introduces a new problem at the same time as solving the old one;
Mines and Net also have the property that most of their deductions
are local, so that it's very unlikely for a tweak to affect
something half way across the grid from the location where it was
applied. In Dominosa, by contrast, a lot of deductions use
information about half the grid (\q{out of all the sixes, only one
is next to a three}, which can depend on the values of up to 32 of
the 56 squares in the default setting!), so this tweaking strategy
would be rather less likely to work well.

A more specialised strategy is that used in Solo and Slant. These
puzzles have the property that they derive their difficulty from not
presenting all the available clues. (In Solo's case, if all the
possible clues were provided then the puzzle would already be
solved; in Slant it would still require user action to fill in the
lines, but it would present no challenge at all). Therefore, a
simple generation technique is to leave the decision of which clues
to provide until the last minute. In other words, first generate a
random \e{filled} grid with all possible clues present, and then
gradually remove clues for as long as the solver reports that it's
still soluble. Unlike the methods described above, this technique
\e{cannot} fail \dash once you've got a filled grid, nothing can
stop you from being able to convert it into a viable puzzle.
However, it wouldn't even be meaningful to apply this technique to
(say) Pattern, in which clues can never be left out, so the only way
to affect the set of clues is by altering the solution.

(Unfortunately, Solo is complicated by the need to provide puzzles
at varying difficulty levels. It's easy enough to generate a puzzle
of \e{at most} a given level of difficulty; you just have a solver
with configurable intelligence, and you set it to a given level and
apply the above technique, thus guaranteeing that the resulting grid
is solvable by someone with at most that much intelligence. However,
generating a puzzle of \e{at least} a given level of difficulty is
rather harder; if you go for \e{at most} Intermediate level, you're
likely to find that you've accidentally generated a Trivial grid a
lot of the time, because removing just one number is sufficient to
take the puzzle from Trivial straight to Ambiguous. In that
situation Solo has no remaining options but to throw the puzzle away
and start again.)

A final strategy is to use the solver \e{during} puzzle
construction: lay out a bit of the grid, run the solver to see what
it allows you to deduce, and then lay out a bit more to allow the
solver to make more progress. There are articles on the web that
recommend constructing Sudoku puzzles by this method (which is
completely the opposite way round to how Solo does it); for Sudoku
it has the advantage that you get to specify your clue squares in
advance (so you can have them make pretty patterns).

Rectangles uses a strategy along these lines. First it generates a
grid by placing the actual rectangles; then it has to decide where
in each rectangle to place a number. It uses a solver to help it
place the numbers in such a way as to ensure a unique solution. It
does this by means of running a test solver, but it runs the solver
\e{before} it's placed any of the numbers \dash which means the
solver must be capable of coping with uncertainty about exactly
where the numbers are! It runs the solver as far as it can until it
gets stuck; then it narrows down the possible positions of a number
in order to allow the solver to make more progress, and so on. Most
of the time this process terminates with the grid fully solved, at
which point any remaining number-placement decisions can be made at
random from the options not so far ruled out. Note that unlike the
Net/Mines tweaking strategy described above, this algorithm does not
require a checking run after it completes: if it finishes
successfully at all, then it has definitely produced a uniquely
soluble puzzle.

Most of the strategies described above are not 100% reliable. Each
one has a failure rate: every so often it has to throw out the whole
grid and generate a fresh one from scratch. (Solo's strategy would
be the exception, if it weren't for the need to provide configurable
difficulty levels.) Occasional failures are not a fundamental
problem in this sort of work, however: it's just a question of
dividing the grid generation time by the success rate (if it takes
10ms to generate a candidate grid and 1/5 of them work, then it will
take 50ms on average to generate a viable one), and seeing whether
the expected time taken to \e{successfully} generate a puzzle is
unacceptably slow. Dominosa's generator has a very low success rate
(about 1 out of 20 candidate grids turn out to be usable, and if you
think \e{that's} bad then go and look at the source code and find
the comment showing what the figures were before the generation-time
tweaks!), but the generator itself is very fast so this doesn't
matter. Rectangles has a slower generator, but fails well under 50%
of the time.

So don't be discouraged if you have an algorithm that doesn't always
work: if it \e{nearly} always works, that's probably good enough.
The one place where reliability is important is that your algorithm
must never produce false positives: it must not claim a puzzle is
soluble when it isn't. It can produce false negatives (failing to
notice that a puzzle is soluble), and it can fail to generate a
puzzle at all, provided it doesn't do either so often as to become
slow.

One last piece of advice: for grid-based puzzles, when writing and
testing your generation algorithm, it's almost always a good idea
\e{not} to test it initially on a grid that's square (i.e.
\cw{w==h}), because if the grid is square then you won't notice if
you mistakenly write \c{h} instead of \c{w} (or vice versa)
somewhere in the code. Use a rectangular grid for testing, and any
size of grid will be likely to work after that.

\S{writing-textformats} Designing textual description formats

Another aspect of writing a puzzle which is worth putting some
thought into is the design of the various text description formats:
the format of the game parameter encoding, the game description
encoding, and the move encoding.

The first two of these should be reasonably intuitive for a user to
type in; so provide some flexibility where possible. Suppose, for
example, your parameter format consists of two numbers separated by
an \c{x} to specify the grid dimensions (\c{10x10} or \c{20x15}),
and then has some suffixes to specify other aspects of the game
type. It's almost always a good idea in this situation to arrange
that \cw{decode_params()} can handle the suffixes appearing in any
order, even if \cw{encode_params()} only ever generates them in one
order.

These formats will also be expected to be reasonably stable: users
will expect to be able to exchange game IDs with other users who
aren't running exactly the same version of your game. So make them
robust and stable: don't build too many assumptions into the game ID
format which will have to be changed every time something subtle
changes in the puzzle code.

\H{writing-howto} Common how-to questions

This section lists some common things people want to do when writing
a puzzle, and describes how to achieve them within the Puzzles
framework.

\S{writing-howto-redraw} Redrawing just the changed parts of the window

Redrawing the entire window on every move is wasteful. If the user
makes a move changing only one square of a grid, it's better to redraw
just that square.

(Yes, computers are fast these days, but these puzzles still try to be
portable to devices at the less fast end of the spectrum, so it's
still worth saving effort where it's easy. On the other hand, some
puzzles just \e{can't} do this easily \dash Untangle is an example
that really does have no better option than to redraw everything.)

For a typical grid-oriented puzzle, a robust way to do this is:

\b Invent a data representation that describes everything about the
appearance of a grid cell in the puzzle window.

\b Have \c{game_drawstate} contain an array of those, describing the
current appearance of each cell, as it was last drawn in the window.

\b In \cw{redraw()}, loop over each cell deciding what the new
appearance should be. If it's not the same as the value stored in
\c{game_drawstate}, then redraw that cell, and update the entry in the
\c{game_drawstate} array.

Where possible, I generally make my data representation an integer
full of bit flags, to save space, and to make it easy to compare the
old and new versions. If yours needs to be bigger than that, you may
have to define a small \cw{struct} and write an equality-checking
function.

The data representation of the \e{appearance} of a square in
\c{game_drawstate} will not generally be identical to the
representation of the \e{logical state} of a square in \c{game_state},
because many things contribute to a square's appearance other than its
logical state. For example:

\b Extra information overlaid on the square by the user interface,
such as a keyboard-controlled cursor, or highlighting of squares
currently involved in a mouse drag action.

\b Error highlights marking violations of the puzzle constraints.

\b Visual intrusions into one square because of things in nearby
squares. For example, if you draw thick lines along the edges between
grid squares, then the corners of those lines will be visible in
logically unrelated squares. An entry in the \c{game_drawstate} array
should describe a specific \e{rectangular area of the screen}, so that
those areas can be erased and redrawn independently \dash so it must
represent anything that appears in that area, even if it's sticking
out from a graphic that logically lives in some other square.

\b Temporary changes to the appearance of a square because of an
ongoing completion flash.

\b The current display mode, if a game provides more than one. (For
example, the optional letters distinguishing the different coloured
pegs in Guess.)

All of this must be included in the \c{game_drawstate} representation,
but should not be in the \c{game_state} at all. \cw{redraw()} will
pull it all together from the \c{game_state}, the \c{game_ui}, and the
animation and flash parameters.

To make sure that \e{everything} affecting a square's appearance is
included in this representation, it's a good idea to have a separate
function for drawing a grid square, and deliberately \e{not} pass it a
copy of the \c{game_state} or the \c{game_ui} at all. That way, if you
want that function to draw anything differently, you \e{have} to do it
by including that information in the representation of a square's
appearance.

But of course there are a couple of exceptions to this rule. A few
things \e{don't} have to go in the \c{game_drawstate} array, and can
safely be passed separately to the redraw-square function:

\b Anything that remains completely fixed throughout the whole of a
game, such as the clues provided by the puzzle. This is safe because a
\c{game_drawstate} is never reused between puzzle instances: when you
press New Game, a new \c{game_drawstate} will always be created from
scratch. So the \c{game_drawstate} only needs to describe everything
that might \e{change} during gameplay. If you have a sub-\cw{struct}
in your \c{game_state} that describes immutable properties of the
current game, as suggested in \k{writing-ref-counting}, then it's safe
to pass \e{that substructure} to the redraw-square function, and have
it retrieve that information directly.

\b How far through a move animation the last redraw was. When
\cw{redraw()} is called multiple times during an animated move, it's
much easier to just assume that any square involved in the animation
will \e{always} need redrawing. So \c{anim_length} can safely be
passed separately to the redraw-square function \dash but you also
have to remember to redraw a square if \e{either} its appearance is
different from the last redraw \e{or} it's involved in an animation.

\S{writing-howto-cursor} Drawing an object at only one position

A common phenomenon is to have an object described in the
\c{game_state} or the \c{game_ui} which can only be at one position.
A cursor \dash probably specified in the \c{game_ui} \dash is a good
example.

In the \c{game_ui}, it would \e{obviously} be silly to have an array
covering the whole game grid with a boolean flag stating whether the
cursor was at each position. Doing that would waste space, would
make it difficult to find the cursor in order to do anything with
it, and would introduce the potential for synchronisation bugs in
which you ended up with two cursors or none. The obviously sensible
way to store a cursor in the \c{game_ui} is to have fields directly
encoding the cursor's coordinates.

However, it is a mistake to assume that the same logic applies to the
\c{game_drawstate}. If you replicate the cursor position fields in the
draw state, the redraw code will get very complicated. In the draw
state, in fact, it \e{is} probably the right thing to have a cursor
flag for every position in the grid, and make it part of the
representation of each square's appearance, as described in
\k{writing-howto-redraw}. So when you iterate over each square in
\c{redraw()} working out its position, you set the \q{cursor here}
flag in the representation of the square's appearance, if its
coordinates match the cursor coordinates stored in the \c{game_ui}.
This will automatically ensure that when the cursor moves, the redraw
loop will redraw the square that \e{previously} contained the cursor
and doesn't any more, and the one that now contains the cursor.

\S{writing-keyboard-cursor} Implementing a keyboard-controlled cursor

It is often useful to provide a keyboard control method in a
basically mouse-controlled game. A keyboard-controlled cursor is
best implemented by storing its location in the \c{game_ui} (since
if it were in the \c{game_state} then the user would have to
separately undo every cursor move operation). So the procedure would
be:

\b Put cursor position fields in the \c{game_ui}.

\b \cw{interpret_move()} responds to arrow keys by modifying the
cursor position fields and returning \cw{MOVE_UI_UPDATE}.

\b \cw{interpret_move()} responds to some other button \dash either
\cw{CURSOR_SELECT} or some more specific thing like a number key \dash
by actually performing a move based on the current cursor location.

\b You might want an additional \c{game_ui} field stating whether
the cursor is currently visible, and having it disappear when a
mouse action occurs (so that it doesn't clutter the display when not
actually in use).

\b You might also want to automatically hide the cursor in
\cw{changed_state()} when the current game state changes to one in
which there is no move to make (which is the case in some types of
completed game).

\b \cw{redraw()} draws the cursor using the technique described in
\k{writing-howto-cursor}.

\S{writing-howto-dragging} Implementing draggable sprites

Some games have a user interface which involves dragging some sort
of game element around using the mouse. If you need to show a
graphic moving smoothly over the top of other graphics, use a
blitter (see \k{drawing-blitter} for the blitter API) to save the
background underneath it. The typical scenario goes:

\b Have a blitter field in the \c{game_drawstate}.

\b Set the blitter field to \cw{NULL} in the game's
\cw{new_drawstate()} function, since you don't yet know how big the
piece of saved background needs to be.

\b In the game's \cw{set_size()} function, once you know the size of
the object you'll be dragging around the display and hence the
required size of the blitter, actually allocate the blitter.

\b In \cw{free_drawstate()}, free the blitter if it's not \cw{NULL}.

\b In \cw{interpret_move()}, respond to mouse-down and mouse-drag
events by updating some fields in the \cw{game_ui} which indicate
that a drag is in progress.

\b At the \e{very end} of \cw{redraw()}, after all other drawing has
been done, draw the moving object if there is one. First save the
background under the object in the blitter; then set a clip
rectangle covering precisely the area you just saved (just in case
anti-aliasing or some other error causes your drawing to go beyond
the area you saved). Then draw the object, and call \cw{unclip()}.
Finally, set a flag in the \cw{game_drawstate} that indicates that
the blitter needs restoring.

\b At the very start of \cw{redraw()}, before doing anything else at
all, check the flag in the \cw{game_drawstate}, and if it says the
blitter needs restoring then restore it. (Then clear the flag, so
that this won't happen again in the next redraw if no moving object
is drawn this time.)

This way, you will be able to write the rest of the redraw function
completely ignoring the dragged object, as if it were floating above
your bitmap and being completely separate.

\S{writing-ref-counting} Sharing large invariant data between all
game states

In some puzzles, there is a large amount of data which never changes
between game states. The array of numbers in Dominosa is a good
example.

You \e{could} dynamically allocate a copy of that array in every
\c{game_state}, and have \cw{dup_game()} make a fresh copy of it for
every new \c{game_state}; but it would waste memory and time. A
more efficient way is to use a reference-counted structure.

\b Define a structure type containing the data in question, and also
containing an integer reference count.

\b Have a field in \c{game_state} which is a pointer to this
structure.

\b In \cw{new_game()}, when creating a fresh game state at the start
of a new game, create an instance of this structure, initialise it
with the invariant data, and set its reference count to 1.

\b In \cw{dup_game()}, rather than making a copy of the structure
for the new game state, simply set the new game state to point at
the same copy of the structure, and increment its reference count.

\b In \cw{free_game()}, decrement the reference count in the
structure pointed to by the game state; if the count reaches zero,
free the structure.

This way, the invariant data will persist for only as long as it's
genuinely needed; \e{as soon} as the last game state for a
particular puzzle instance is freed, the invariant data for that
puzzle will vanish as well. Reference counting is a very efficient
form of garbage collection, when it works at all. (Which it does in
this instance, of course, because there's no possibility of circular
references.)

\S{writing-flash-types} Implementing multiple types of flash

In some games you need to flash in more than one different way.
Mines, for example, flashes white when you win, and flashes red when
you tread on a mine and die.

The simple way to do this is:

\b Have a field in the \c{game_ui} which describes the type of flash.

\b In \cw{flash_length()}, examine the old and new game states to
decide whether a flash is required and what type. Write the type of
flash to the \c{game_ui} field whenever you return non-zero.

\b In \cw{redraw()}, when you detect that \c{flash_time} is
non-zero, examine the field in \c{game_ui} to decide which type of
flash to draw.

\cw{redraw()} will never be called with \c{flash_time} non-zero
unless \cw{flash_length()} was first called to tell the mid-end that
a flash was required; so whenever \cw{redraw()} notices that
\c{flash_time} is non-zero, you can be sure that the field in
\c{game_ui} is correctly set.

\S{writing-move-anim} Animating game moves

A number of puzzle types benefit from a quick animation of each move
you make.

For some games, such as Fifteen, this is particularly easy. Whenever
\cw{redraw()} is called with \c{oldstate} non-\cw{NULL}, Fifteen
simply compares the position of each tile in the two game states,
and if the tile is not in the same place then it draws it some
fraction of the way from its old position to its new position. This
method copes automatically with undo.

Other games are less obvious. In Sixteen, for example, you can't
just draw each tile a fraction of the way from its old to its new
position: if you did that, the end tile would zip very rapidly past
all the others to get to the other end and that would look silly.
(Worse, it would look inconsistent if the end tile was drawn on top
going one way and on the bottom going the other way.)

A useful trick here is to define a field or two in the game state
that indicates what the last move was.

\b Add a \q{last move} field to the \c{game_state} (or two or more
fields if the move is complex enough to need them).

\b \cw{new_game()} initialises this field to a null value for a new
game state.

\b \cw{execute_move()} sets up the field to reflect the move it just
performed.

\b \cw{redraw()} now needs to examine its \c{dir} parameter. If
\c{dir} is positive, it determines the move being animated by
looking at the last-move field in \c{newstate}; but if \c{dir} is
negative, it has to look at the last-move field in \c{oldstate}, and
invert whatever move it finds there.

Note also that Sixteen needs to store the \e{direction} of the move,
because you can't quite determine it by examining the row or column
in question. You can in almost all cases, but when the row is
precisely two squares long it doesn't work since a move in either
direction looks the same. (You could argue that since moving a
2-element row left and right has the same effect, it doesn't matter
which one you animate; but in fact it's very disorienting to click
the arrow left and find the row moving right, and almost as bad to
undo a move to the right and find the game animating \e{another}
move to the right.)

\S{writing-conditional-anim} Animating drag operations

In Untangle, moves are made by dragging a node from an old position
to a new position. Therefore, at the time when the move is initially
made, it should not be animated, because the node has already been
dragged to the right place and doesn't need moving there. However,
it's nice to animate the same move if it's later undone or redone.
This requires a bit of fiddling.

The obvious approach is to have a flag in the \c{game_ui} which
inhibits move animation, and to set that flag in
\cw{interpret_move()}. The question is, when would the flag be reset
again? The obvious place to do so is \cw{changed_state()}, which
will be called once per move. But it will be called \e{before}
\cw{anim_length()}, so if it resets the flag then \cw{anim_length()}
will never see the flag set at all.

The solution is to have \e{two} flags in a queue.

\b Define two flags in \c{game_ui}; let's call them \q{current} and
\q{next}.

\b Set both to \cw{false} in \c{new_ui()}.

\b When a drag operation completes in \cw{interpret_move()}, set the
\q{next} flag to \cw{true}.

\b Every time \cw{changed_state()} is called, set the value of
\q{current} to the value in \q{next}, and then set the value of
\q{next} to \cw{false}.

\b That way, \q{current} will be \cw{true} \e{after} a call to
\cw{changed_state()} if and only if that call to
\cw{changed_state()} was the result of a drag operation processed by
\cw{interpret_move()}. Any other call to \cw{changed_state()}, due
to an Undo or a Redo or a Restart or a Solve, will leave \q{current}
\cw{false}.

\b So now \cw{anim_length()} can request a move animation if and
only if the \q{current} flag is \e{not} set.

\S{writing-cheating} Inhibiting the victory flash when Solve is used

Many games flash when you complete them, as a visual congratulation
for having got to the end of the puzzle. It often seems like a good
idea to disable that flash when the puzzle is brought to a solved
state by means of the Solve operation.

This is easily done:

\b Add a \q{cheated} flag to the \c{game_state}.

\b Set this flag to \cw{false} in \cw{new_game()}.

\b Have \cw{solve()} return a move description string which clearly
identifies the move as a solve operation.

\b Have \cw{execute_move()} respond to that clear identification by
setting the \q{cheated} flag in the returned \c{game_state}. The
flag will then be propagated to all subsequent game states, even if
the user continues fiddling with the game after it is solved.

\b \cw{flash_length()} now returns non-zero if \c{oldstate} is not
completed and \c{newstate} is, \e{and} neither state has the
\q{cheated} flag set.

\H{writing-testing} Things to test once your puzzle is written

Puzzle implementations written in this framework are self-testing as
far as I could make them.

Textual game and move descriptions, for example, are generated and
parsed as part of the normal process of play. Therefore, if you can
make moves in the game \e{at all} you can be reasonably confident
that the mid-end serialisation interface will function correctly and
you will be able to save your game. (By contrast, if I'd stuck with
a single \cw{make_move()} function performing the jobs of both
\cw{interpret_move()} and \cw{execute_move()}, and had separate
functions to encode and decode a game state in string form, then
those functions would not be used during normal play; so they could
have been completely broken, and you'd never know it until you tried
to save the game \dash which would have meant you'd have to test
game saving \e{extensively} and make sure to test every possible
type of game state. As an added bonus, doing it the way I did leads
to smaller save files.)

There is one exception to this, which is the string encoding of the
\c{game_ui}. Most games do not store anything permanent in the
\c{game_ui}, and hence do not need to put anything in its encode and
decode functions; but if there is anything in there, you do need to
test game loading and saving to ensure those functions work
properly.

It's also worth testing undo and redo of all operations, to ensure
that the redraw and the animations (if any) work properly. Failing
to animate undo properly seems to be a common error.

Other than that, just use your common sense.