puzzles: resync with upstream

This brings the upstream version to b3da238 (though some of my own
changes are included on top of that).

Change-Id: Ida73e8cd86765413147ce891af3cc2b7aeda2b2a

1 files changed, 4661 insertions, 0 deletions

diff --git a/apps/plugins/puzzles/src/HACKING b/apps/plugins/puzzles/src/HACKING
new file mode 100644
index 0000000..e877280
--- /dev/null
+++ b/apps/plugins/puzzles/src/HACKING
@@ -0,0 +1,4661 @@
+#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 `Puzzles'), for
+use by anyone attempting to implement a new puzzle or port to a new
+platform.
+
+This guide is believed correct as of r6190. 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.
+
+#1. Introduction
+
+The Puzzles code base is divided into four parts: a set of
+interchangeable front ends, a set of interchangeable back ends, a
+universal `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.
+
+#1.1. 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 current front ends in the main code base are for Windows, GTK and
+MacOS X; I also know of a third-party front end for PalmOS.
+
+The front end contains 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
+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 _do_
+want the same menu layout on more than one platform, I have to edit
+two 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 X 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 OS X 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 chapter 3; the other miscellaneous front end API functions are
+documented in section 4.34.
+
+#1.2. Back end
+
+A `back end', in this collection, is synonymous with a `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 chapter 2.
+
+#1.3. Middle end
+
+Puzzles has a single and universal `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:
+
+ -  Maintaining a list of game state structures and moving back and
+    forth along that list to provide Undo and Redo.
+
+ -  Handling timers (for move animations, flashes on completion, and in
+    some cases actually timing the game).
+
+ -  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.
+
+ -  Handling standard keystrokes and menu commands, such as `New Game',
+    `Restart Game' and `Quit'.
+
+ -  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).
+
+ -  Handling the dialog boxes which ask the user for a game ID.
+
+ -  Handling serialisation of entire games (for loading and saving a
+    half-finished game to a disk file, or for handling application
+    shutdown and restart on platforms such as PalmOS where state is
+    expected to be saved).
+
+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 chapter 4.
+
+#1.4. 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 chapter 5.
+
+#1.5. 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, chapter
+6 discusses how to design new games, with some general design thoughts
+and tips.
+
+#2. 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 `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:
+
+ -  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, `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.
+
+ -  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 `list.c'
+    (constructed automatically by the same Perl script that builds the
+    Makefiles) which contains a complete list of those game structures.
+
+On the latter type of platform, source files may assume that the
+preprocessor symbol `COMBINED' has been defined. Thus, the usual code to
+declare the game structure looks something like this:
+
+  #ifdef COMBINED
+  #define thegame net    /* or whatever this game is called */
+  #endif
+  
+  const struct game thegame = {
+      /* lots of structure initialisation in here */
+  };
+
+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.
+
+#2.1. 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.
+
+#2.1.1. `game_params'
+
+The `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
+`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
+`game_params' is: would the user expect to be able to control this data
+item from either the preset-game-types menu or the `Custom' game type
+configuration? If so, it's part of `game_params'.
+
+`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 `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.)
+
+`game_params' is also the only structure which the game's 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 must be stored in
+`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.)
+
+#2.1.2. `game_state'
+
+While the user is actually playing a puzzle, the `game_state' structure
+stores all the data corresponding to the current state of play.
+
+The mid-end keeps `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
+`game_state' is: would a player expect that data item to be restored on
+undo? If so, put it in `game_state', and this will automatically happen
+without you having to lift a finger. If not - for example, the deaths
+counter in Mines is precisely something that does _not_ want to be reset
+to its previous state on an undo - then you might have found a data item
+that needs to go in `game_ui' instead.
+
+During play, `game_state's are often passed around without an
+accompanying `game_params' structure. Therefore, any information in
+`game_params' which is important during play (such as the grid size)
+must be duplicated within the `game_state'. One simple method of doing
+this is to have the `game_state' structure _contain_ a `game_params'
+structure as one of its members, although this isn't obligatory if you
+prefer to do it another way.
+
+#2.1.3. `game_drawstate'
+
+`game_drawstate' carries persistent state relating to the current
+graphical contents of the puzzle window. The same `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 `game_drawstate' is to have an array mirroring the
+array of grid squares in the `game_state'; then every time the redraw
+function was passed a `game_state', it would loop over all the squares,
+and physically redraw any whose description in the `game_state' (i.e.
+what the square needs to look like when the redraw is completed) did
+not match its description in the `game_drawstate' (i.e. what the square
+currently looks like).
+
+`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 `game_drawstate' which is _not_ related to the
+state of the puzzle window, because it might be unexpectedly destroyed.
+
+The back end provides functions to create and destroy `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 `game_drawstate' is a
+`blitter'; see section 3.1.13 for more on this subject.
+
+#2.1.4. `game_ui'
+
+`game_ui' contains whatever doesn't fit into the above three structures!
+
+A new `game_ui' is created when the user begins playing a new instance
+of a puzzle (i.e. during `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, `Restart Game' does _not_
+destroy the `game_ui'.
+
+`game_ui' is useful for implementing user-interface state which is not
+part of `game_state'. Common examples are keyboard control (you wouldn't
+want to have to separately Undo through every cursor motion) and mouse
+dragging. See section 6.3.2 and section 6.3.3, respectively, for more
+details.
+
+Another use for `game_ui' is to store highly persistent data such as
+the Mines death counter. This is conceptually rather different: where
+the Net cursor position was _not important enough_ to preserve for the
+player to restore by Undo, the Mines death counter is _too important_ to
+permit the player to revert by Undo!
+
+A final use for `game_ui' is to pass information to the redraw function
+about recent changes to the game state. This is used in Mines, for
+example, to indicate whether a requested `flash' should be a white flash
+for victory or a red flash for defeat; see section 6.3.5.
+
+#2.2. 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.
+
+#2.2.1. `name'
+
+  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.
+
+#2.2.2. `winhelp_topic'
+
+  const char *winhelp_topic;
+
+This member is 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 `Help' from the
+menu, the program needs to open the help file and jump to the chapter
+describing that particular puzzle.
+
+Therefore, each chapter in `puzzles.but' is labelled with a _help topic_
+name, similar to this:
+
+  \cfg{winhelp-topic}{games.net}
+
+And then the corresponding game back end encodes the topic string (here
+`games.net') in the `winhelp_topic' element of the game structure.
+
+#2.3. Handling game parameter sets
+
+In this section I present the various functions which handle the
+`game_params' structure.
+
+#2.3.1. default_params()
+
+  game_params *(*default_params)(void);
+
+This function allocates a new `game_params' structure, fills it with the
+default values, and returns a pointer to it.
+
+#2.3.2. fetch_preset()
+
+  int (*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 `Type' menu, which provides a list of conveniently accessible preset
+parameters for most games.
+
+The function is called with `i' equal to the index of the preset
+required (numbering from zero). It returns FALSE if that preset does
+not exist (if `i' is less than zero or greater than the largest preset
+index). Otherwise, it sets `*params' to point at a newly allocated
+`game_params' structure containing the preset information, sets `*name'
+to point at a newly allocated C string containing the preset title (to
+go on the `Type' menu), and returns TRUE.
+
+If the game does not wish to support any presets at all, this function
+is permitted to return 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 NULL, and instead fill in the alternative
+function pointer preset_menu (section 2.3.3).
+
+#2.3.3. preset_menu()
+
+  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 `struct preset_menu' (see section 4.15) and further submenus (if
+it wishes) dangling off it. There are utility functions described in
+section 5.2 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 fetch_preset() function (see section 2.3.2).
+
+The game need not fill in the `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.
+
+#2.3.4. encode_params()
+
+  char *(*encode_params)(const game_params *params, int full);
+
+The job of this function is to take a `game_params', and encode it in
+a string form for use in game IDs. The return value must be a newly
+allocated C string, and _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 _somebody_.
+
+(At the time of writing this, all 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 `x'.)
+
+If the `full' parameter is TRUE, this function should encode absolutely
+everything in the `game_params', such that a subsequent call to
+decode_params() (section 2.3.5) will yield an identical structure.
+If `full' is FALSE, however, you should leave out anything which
+is not necessary to describe a _specific puzzle instance_, i.e.
+anything which only takes effect when a new puzzle is _generated_.
+For example, the Solo `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 _knowing_ what its difficulty level is in
+Solo's terminology.) Therefore, Solo's encode_params() only encodes the
+difficulty level if `full' is set.
+
+#2.3.5. decode_params()
+
+  void (*decode_params)(game_params *params, char const *string);
+
+This function is the inverse of encode_params() (section 2.3.4). It
+parses the supplied string and fills in the supplied `game_params'
+structure. Note that the structure will _already_ have been allocated:
+this function is not expected to create a _new_ `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 encode_params() with its `full' parameter set
+to 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 `game_params' is
+almost always subsequently passed to validate_params() (section 2.3.11),
+so if you really want to signal parse errors, you could always have a
+`char *' in your parameters structure which stored an error message, and
+have validate_params() return it if it is non-NULL.
+
+#2.3.6. free_params()
+
+  void (*free_params)(game_params *params);
+
+This function frees a `game_params' structure, and any subsidiary
+allocations contained within it.
+
+#2.3.7. dup_params()
+
+  game_params *(*dup_params)(const game_params *params);
+
+This function allocates a new `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.
+
+#2.3.8. `can_configure'
+
+  int can_configure;
+
+This boolean data element is set to TRUE if the back end supports
+custom parameter configuration via a dialog box. If it is TRUE, then
+the functions configure() and custom_params() are expected to work. See
+section 2.3.9 and section 2.3.10 for more details.
+
+#2.3.9. configure()
+
+  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
+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 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
+custom_params() (see section 2.3.10).
+
+The config_item structure contains the following elements:
+
+  char *name;
+  int type;
+  union { /* type-specific fields */ } u;
+
+`name' is an ASCII string giving the textual label for a GUI control. It
+is _not_ expected to be dynamically allocated.
+
+`type' contains one of a small number of `enum' values defining what
+type of control is being described. The usable member of the union field
+`u' depends on `type'. The valid type values are:
+
+`C_STRING'
+
+    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.)
+
+    For controls of this type, `u.string' contains a single field
+
+      char *sval;
+
+    which stores a dynamically allocated string representing the
+    contents of the input box.
+
+`C_BOOLEAN'
+
+    Describes a simple checkbox.
+
+    For controls of this type, `u.boolean' contains a single field
+
+      int bval;
+
+    which is either TRUE or FALSE.
+
+`C_CHOICES'
+
+    Describes a drop-down list presenting one of a small number of fixed
+    choices.
+
+    For controls of this type, `u.choices' contains two fields:
+
+      const char *choicenames;
+      int selected;
+
+    `choicenames' contains a list of strings describing the choices.
+    The very first character of `sval' is used as a delimiter when
+    processing the rest (so that the strings `:zero:one:two',
+    `!zero!one!two' and `xzeroxonextwo' all define a three-element list
+    containing `zero', `one' and `two').
+
+    `selected' contains the index of the currently selected element,
+    numbering from zero (so that in the above example, 0 would mean
+    `zero' and 2 would mean `two').
+
+    Note that `u.choices.choicenames' is _not_ dynamically allocated,
+    unlike `u.string.sval'.
+
+`C_END'
+
+    Marks the end of the array of `config_item's. There is no associated
+    member of the union field `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 `game_params'
+structure.
+
+If the game's `can_configure' flag is set to FALSE, this function is
+never called and need not do anything at all.
+
+#2.3.10. custom_params()
+
+  game_params *(*custom_params)(const config_item *cfg);
+
+This function is the counterpart to configure() (section 2.3.9). It
+receives as input an array of `config_item's which was originally
+created by 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 `game_params'
+structure representing the user's chosen parameter set.
+
+(The front end will have modified the controls' _values_, but there will
+still always be the same set of controls, in the same order, as provided
+by configure(). It is not necessary to check the `name' and `type'
+fields, although you could use assert() if you were feeling energetic.)
+
+This function is not expected to (and indeed _must not_) free the input
+`config_item' array. (If the parameters fail to validate, the dialog box
+will stay open.)
+
+If the game's `can_configure' flag is set to FALSE, this function is
+never called and need not do anything at all.
+
+#2.3.11. validate_params()
+
+  const char *(*validate_params)(const game_params *params,
+                                 int full);
+
+This function takes a `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 NULL if no problems were found, or alternatively a (non-
+dynamically-allocated) ASCII string describing the error in human-
+readable form.
+
+If the `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 `full' is _not_ set, the implication is that
+these parameters are not going to be used for _generating_ a puzzle; so
+parameters which can't even sensibly _describe_ a valid puzzle should
+still be faulted, but parameters which only affect puzzle generation
+should not be.
+
+(The `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 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 _non_-unique wrapping width-2 puzzle, then
+validate_params() will be passed a `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
+`full' is not set during this call, so Net ignores the inconsistency.
+The resulting `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.)
+
+#2.4. 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.
+
+#2.4.1. new_desc()
+
+  char *(*new_desc)(const game_params *params, random_state *rs,
+                    char **aux, int 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 `game_params' structure and a random state
+(see section 5.1 for the random number API). It must invent a puzzle
+instance, encode it in string form, and return a dynamically allocated C
+string containing that encoding.
+
+Additionally, it may return a second dynamically allocated string
+in `*aux'. (If it doesn't want to, then it can leave that parameter
+completely alone; it isn't required to set it to NULL, although doing
+so is harmless.) That string, if present, will be passed to solve()
+(section 2.7.4) 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 `*aux' for solve() to use.
+
+The `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
+_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
+_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 `game_params' it was generated with, so any
+information contained in that structure need not be encoded again in the
+game description.
+
+#2.4.2. validate_desc()
+
+  const char *(*validate_desc)(const game_params *params,
+                               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
+`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 validate_desc() _must not_ subsequently cause a crash
+or an assertion failure when fed to new_game() and thence to the rest of
+the back end.
+
+The return value is NULL on success, or a non-dynamically-allocated C
+string containing an error message.
+
+#2.4.3. new_game()
+
+  game_state *(*new_game)(midend *me, const game_params *params,
+                          const char *desc);
+
+This function takes a game description as input, together with its
+accompanying `game_params', and constructs a `game_state' describing the
+initial state of the puzzle. It returns a newly allocated `game_state'
+structure.
+
+Almost all puzzles should ignore the `me' parameter. It is required by
+Mines, which needs it for later passing to midend_supersede_game_desc()
+(see section 2.11.2) 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 `interactive'
+parameter in new_desc() (section 2.4.1), if you think you have a reason
+to need this parameter, please try very hard to think of an alternative
+approach!
+
+#2.5. Handling game states
+
+This section describes the functions which create and destroy
+`game_state' structures.
+
+(Well, except new_game(), which is in section 2.4.3 instead of under
+here; but it deals with game descriptions _and_ game states and it had
+to go in one section or the other.)
+
+#2.5.1. dup_game()
+
+  game_state *(*dup_game)(const game_state *state);
+
+This function allocates a new `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.
+
+#2.5.2. free_game()
+
+  void (*free_game)(game_state *state);
+
+This function frees a `game_state' structure, and any subsidiary
+allocations contained within it.
+
+#2.6. Handling `game_ui'
+
+#2.6.1. new_ui()
+
+  game_ui *(*new_ui)(const game_state *state);
+
+This function allocates and returns a new `game_ui' structure for
+playing a particular puzzle. It is passed a pointer to the initial
+`game_state', in case it needs to refer to that when setting up the
+initial values for the new game.
+
+#2.6.2. free_ui()
+
+  void (*free_ui)(game_ui *ui);
+
+This function frees a `game_ui' structure, and any subsidiary
+allocations contained within it.
+
+#2.6.3. encode_ui()
+
+  char *(*encode_ui)(const game_ui *ui);
+
+This function encodes any _important_ data in a `game_ui' structure in
+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 `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 _feature_.
+
+A typical thing that _would_ be worth encoding in this function is the
+Mines death counter: it's in the `game_ui' rather than the `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 _that_ determined to cheat, they could just
+as easily modify the game's source.)
+
+#2.6.4. decode_ui()
+
+  void (*decode_ui)(game_ui *ui, const char *encoding);
+
+This function parses a string previously output by encode_ui(), and
+writes the decoded data back into the provided `game_ui' structure.
+
+#2.6.5. changed_state()
+
+  void (*changed_state)(game_ui *ui, const game_state *oldstate,
+                        const game_state *newstate);
+
+This function is called by the mid-end whenever the current game state
+changes, for any reason. Those reasons include:
+
+ -  a fresh move being made by interpret_move() and execute_move()
+
+ -  a solve operation being performed by solve() and execute_move()
+
+ -  the user moving back and forth along the undo list by means of the
+    Undo and Redo operations
+
+ -  the user selecting Restart to go back to the initial game state.
+
+The job of changed_state() is to update the `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
+`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 changed_state() function clears the
+current selection whenever it is called.
+
+When anim_length() or flash_length() are called, you can be sure that
+there has been a previous call to changed_state(). So changed_state()
+can set up data in the `game_ui' which will be read by anim_length() and
+flash_length(), and those functions will not have to worry about being
+called without the data having been initialised.
+
+#2.7. 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 `game_state's.
+
+#2.7.1. interpret_move()
+
+  char *(*interpret_move)(const game_state *state, game_ui *ui,
+                          const game_drawstate *ds,
+                          int x, int y, int button);
+
+This function receives user input and processes it. Its input parameters
+are the current `game_state', the current `game_ui' and the current
+`game_drawstate', plus details of the input event. `button' is either
+an ASCII value or a special code (listed below) indicating an arrow or
+function key or a mouse event; when `button' is a mouse event, `x' and
+`y' contain the pixel coordinates of the mouse pointer relative to the
+top left of the puzzle's drawing area.
+
+(The pointer to the `game_drawstate' is marked `const', because
+`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.)
+
+interpret_move() may return in three different ways:
+
+ -  Returning NULL indicates that no action whatsoever occurred in
+    response to the input event; the puzzle was not interested in it at
+    all.
+
+ -  Returning the special value UI_UPDATE indicates that the input event
+    has resulted in a change being made to the `game_ui' which will
+    require a redraw of the game window, but that no actual _move_ was
+    made (i.e. no new `game_state' needs to be created).
+
+ -  Returning anything else indicates that a move was made and that
+    a new `game_state' must be created. However, instead of actually
+    constructing a new `game_state' itself, this function is required to
+    return a string description of the details of the move. This string
+    will be passed to execute_move() (section 2.7.2) to actually create
+    the new `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 execute_move() again on reloading.)
+
+The return value from interpret_move() is expected to be dynamically
+allocated if and only if it is not either NULL _or_ the special string
+constant `UI_UPDATE'.
+
+After this function is called, the back end is permitted to rely on some
+subsequent operations happening in sequence:
+
+ -  execute_move() will be called to convert this move description into
+    a new `game_state'
+
+ -  changed_state() will be called with the new `game_state'.
+
+This means that if interpret_move() needs to do updates to the `game_ui'
+which are easier to perform by referring to the new `game_state', it can
+safely leave them to be done in changed_state() and not worry about them
+failing to happen.
+
+(Note, however, that execute_move() may _also_ be called in other
+circumstances. It is only interpret_move() which can rely on a
+subsequent call to changed_state().)
+
+The special key codes supported by this function are:
+
+LEFT_BUTTON, MIDDLE_BUTTON, RIGHT_BUTTON
+
+    Indicate that one of the mouse buttons was pressed down.
+
+LEFT_DRAG, MIDDLE_DRAG, RIGHT_DRAG
+
+    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.
+
+LEFT_RELEASE, MIDDLE_RELEASE, RIGHT_RELEASE
+
+    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.
+
+CURSOR_UP, CURSOR_DOWN, CURSOR_LEFT, CURSOR_RIGHT
+
+    Indicate that an arrow key was pressed.
+
+CURSOR_SELECT
+
+    On platforms which have a prominent `select' button alongside their
+    cursor keys, indicates that that button was pressed.
+
+In addition, there are some modifiers which can be bitwise-ORed into the
+`button' parameter:
+
+MOD_CTRL, MOD_SHFT
+
+    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.
+
+MOD_NUM_KEYPAD
+
+    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).
+
+MOD_MASK
+
+    This mask is the bitwise OR of all the available modifiers; you can
+    bitwise-AND with ~MOD_MASK to strip all the modifiers off any input
+    value.
+
+#2.7.2. execute_move()
+
+  game_state *(*execute_move)(const game_state *state, char *move);
+
+This function takes an input `game_state' and a move string as output
+from interpret_move(). It returns a newly allocated `game_state' which
+contains the result of applying the specified move to the input game
+state.
+
+This function may return 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 NULL for any move string that really was output from
+interpret_move(): this is punishable by assertion failure in the mid-
+end.
+
+#2.7.3. `can_solve'
+
+  int can_solve;
+
+This boolean field is set to TRUE if the game's solve() function does
+something. If it's set to FALSE, the game will not even offer the
+`Solve' menu option.
+
+#2.7.4. solve()
+
+  char *(*solve)(const game_state *orig, const game_state *curr,
+                 const char *aux, const char **error);
+
+This function is called when the user selects the `Solve' option from
+the menu.
+
+It is passed two input game states: `orig' is the game state from the
+very start of the puzzle, and `curr' is the current one. (Different
+games find one or other or both of these convenient.) It is also passed
+the `aux' string saved by new_desc() (section 2.4.1), 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 `aux' string for) then it may return NULL. If it
+does this, it must also set `*error' to an error message to be presented
+to the user (such as `Solution not known for this puzzle'); that error
+message is not expected to be dynamically allocated.
+
+If this function _does_ produce a solution, it returns a move string
+suitable for feeding to execute_move() (section 2.7.2). Like a (non-
+empty) string returned from interpret_move(), the returned string should
+be dynamically allocated.
+
+#2.8. Drawing the game graphics
+
+This section discusses the back end functions that deal with drawing.
+
+#2.8.1. new_drawstate()
+
+  game_drawstate *(*new_drawstate)(drawing *dr,
+                                   const game_state *state);
+
+This function allocates and returns a new `game_drawstate' structure for
+drawing a particular puzzle. It is passed a pointer to a `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 `dr' is a drawing object (see chapter 3) 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 set_size() is called, because that way you can tailor it to the
+scale at which the puzzle is being drawn.)
+
+#2.8.2. free_drawstate()
+
+  void (*free_drawstate)(drawing *dr, game_drawstate *ds);
+
+This function frees a `game_drawstate' structure, and any subsidiary
+allocations contained within it.
+
+The parameter `dr' is a drawing object (see chapter 3), which might be
+required if you are freeing a blitter.
+
+#2.8.3. `preferred_tilesize'
+
+  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 `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 `tile
+size' be proportional to the game window size. Window size is required
+to increase monotonically with `tile size', however.
+
+The data element `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, or the user explicitly requesting a resize
+if that ever gets implemented).
+
+#2.8.4. compute_size()
+
+  void (*compute_size)(const game_params *params, int tilesize,
+                       int *x, int *y);
+
+This function is passed a `game_params' structure and a tile size. It
+returns, in `*x' and `*y', the size in pixels of the drawing area that
+would be required to render a puzzle with those parameters at that tile
+size.
+
+#2.8.5. set_size()
+
+  void (*set_size)(drawing *dr, game_drawstate *ds,
+                   const game_params *params, int tilesize);
+
+This function is responsible for setting up a `game_drawstate' to draw
+at a given tile size. Typically this will simply involve copying the
+supplied `tilesize' parameter into a `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 section
+3.1.13).
+
+The parameter `dr' is a drawing object (see chapter 3), 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 `game_drawstate'. If a puzzle needs
+to be redrawn at a different size, the mid-end will create a fresh
+drawstate.
+
+#2.8.6. colours()
+
+  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 `*ncolours', and the return
+value from the function itself is a dynamically allocated array of three
+times that many `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 frontend_default_colour() (see section 4.39)
+or the utility function called game_mkhighlight() (see section 5.5.7).
+(The latter is a wrapper on the former, so front end implementors only
+need to provide frontend_default_colour().) This allows 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.
+
+Note that the colours returned from this function are for _drawing_,
+not for printing. Printing has an entirely different colour allocation
+policy.
+
+#2.8.7. anim_length()
+
+  float (*anim_length)(const game_state *oldstate,
+                       const game_state *newstate,
+                       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 `game_state', and its job is to decide whether
+the transition between the two needs to be animated or can be instant.
+
+`oldstate' is the state that was current until this call; `newstate'
+is the state that will be current after it. `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 `newstate' is the
+later of the two moves), whereas if it is negative then the transition
+is the result of an undo (so that `newstate' is the _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 `flags' (section 2.10.7).
+
+The function is also passed a pointer to the local `game_ui'. It may
+refer to information in here to help with its decision (see section
+6.3.7 for an example of this), and/or it may _write_ information about
+the nature of the animation which will be read later by redraw().
+
+When this function is called, it may rely on changed_state() having been
+called previously, so if anim_length() needs to refer to information in
+the `game_ui', then 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.
+
+#2.8.8. flash_length()
+
+  float (*flash_length)(const game_state *oldstate,
+                        const game_state *newstate,
+                        int dir, game_ui *ui);
+
+This function is called when a move is completed. (`Completed'
+means that not only has the move been made, but any animation which
+accompanied it has finished.) It decides whether the transition from
+`oldstate' to `newstate' merits a `flash'.
+
+A flash is much like a move animation, but it is _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 - 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 _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 `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 flash_length() are exactly the same as the ones
+to anim_length().
+
+Just like anim_length(), when this function is called, it may rely on
+changed_state() having been called previously, so if it needs to refer
+to information in the `game_ui' then 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 flash_length() function has to store a flag in the `game_ui' to
+indicate which flash type is required.)
+
+#2.8.9. status()
+
+  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 midend_status() (section 4.26).
+
+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 _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.)
+
+#2.8.10. redraw()
+
+  void (*redraw)(drawing *dr, game_drawstate *ds,
+                 const game_state *oldstate,
+                 const game_state *newstate,
+                 int dir, const game_ui *ui,
+                 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
+`game_ui' changes.
+
+The parameter `dr' is a drawing object which may be passed to the
+drawing API functions (see chapter 3 for documentation of the drawing
+API). This function may not save `dr' and use it elsewhere; it must only
+use it for calling back to the drawing API functions within its own
+lifetime.
+
+`ds' is the local `game_drawstate', of course, and `ui' is the local
+`game_ui'.
+
+`newstate' is the semantically-current game state, and is always non-
+NULL. If `oldstate' is also non-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, `anim_time'
+will give the length of time (in seconds) that the animation has already
+been running. If `oldstate' is NULL, then `anim_time' is unused (and
+will hopefully be set to zero to avoid confusion).
+
+`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
+section 2.8.8 for general discussion of flashes.
+
+The very first time this function is called for a new `game_drawstate',
+it is expected to redraw the _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 `first time'
+flag in the draw state, and resetting it after the first redraw.
+
+When this function (or any subfunction) calls the drawing API, it is
+expected to pass colour indices which were previously defined by the
+colours() function.
+
+#2.9. Printing functions
+
+This section discusses the back end functions that deal with printing
+puzzles out on paper.
+
+#2.9.1. `can_print'
+
+  int can_print;
+
+This flag is set to 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 FALSE, then the functions print_size() and print() will
+never be called.
+
+#2.9.2. `can_print_in_colour'
+
+  int can_print_in_colour;
+
+This flag is set to TRUE if the puzzle is capable of printing itself
+differently when colour is available. For example, Map can actually
+print coloured regions in different _colours_ rather than resorting to
+cross-hatching.
+
+If the `can_print' flag is FALSE, then this flag will be ignored.
+
+#2.9.3. print_size()
+
+  void (*print_size)(const game_params *params, float *x, float *y);
+
+This function is passed a `game_params' structure and a tile size. It
+returns, in `*x' and `*y', the preferred size in _millimetres_ of that
+puzzle if it were to be printed out on paper.
+
+If the `can_print' flag is FALSE, this function will never be called.
+
+#2.9.4. print()
+
+  void (*print)(drawing *dr, const game_state *state, int tilesize);
+
+This function is called when a puzzle is to be printed out on paper. It
+should use the drawing API functions (see chapter 3) to print itself.
+
+This function is separate from redraw() because it is often very
+different:
+
+ -  The printing function may not depend on pixel accuracy, since
+    printer resolution is variable. Draw as if your canvas had infinite
+    resolution.
+
+ -  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.
+
+ -  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 print_*_colour() functions within this execution of print(). This is
+very different from the fixed small number of colours used in 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 `ink' colour and use it for all drawing; others might
+wish to allocate _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 _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 print_*_colour() are guaranteed to be in
+increasing order from zero. So if you have declared an `enum' defining
+three colours COL_BACKGROUND, COL_THIS and COL_THAT, you might then
+write
+
+  int c;
+  c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
+  c = print_mono_colour(dr, 0); assert(c == COL_THIS);
+  c = print_mono_colour(dr, 0); assert(c == COL_THAT);
+
+If the `can_print' flag is FALSE, this function will never be called.
+
+#2.10. Miscellaneous
+
+#2.10.1. `can_format_as_text_ever'
+
+  int can_format_as_text_ever;
+
+This boolean field is 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 FALSE, front ends will not
+offer the `Copy' command at all.
+
+If this field is TRUE, the game does not necessarily have to support
+text formatting for _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 FALSE, the functions can_format_as_text_now() (section
+2.10.2) and text_format() (section 2.10.3) are never called.
+
+#2.10.2. `can_format_as_text_now()'
+
+  int (*can_format_as_text_now)(const game_params *params);
+
+This function is passed a `game_params' and returns a boolean, which is
+TRUE if the game can support ASCII text output for this particular game
+type. If it returns FALSE, front ends will grey out or otherwise disable
+the `Copy' command.
+
+Games may enable and disable the copy-and-paste function for different
+game _parameters_, but are currently constrained to return the same
+answer from this function for all game _states_ sharing the same
+parameters. In other words, the `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 encode_params() (section 2.3.4)
+when the `full' parameter is set to FALSE. Such parameters will not
+necessarily match up between a call to this function and a subsequent
+call to text_format() itself. (For instance, game _difficulty_ should
+not affect whether the game can be copied to the clipboard. Only the
+actual visible _shape_ of the game can affect that.)
+
+#2.10.3. text_format()
+
+  char *(*text_format)(const game_state *state);
+
+This function is passed a `game_state', and returns a newly allocated C
+string containing an ASCII representation of that game state. It is used
+to implement the `Copy' operation in many front ends.
+
+This function will only ever be called if the back end field
+`can_format_as_text_ever' (section 2.10.1) is TRUE _and_ the function
+can_format_as_text_now() (section 2.10.2) has returned TRUE for the
+currently selected game parameters.
+
+The returned string may contain line endings (and will probably want
+to), using the normal C internal `\n' convention. For consistency
+between puzzles, all multi-line textual puzzle representations should
+_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.)
+
+#2.10.4. wants_statusbar
+
+  int wants_statusbar;
+
+This boolean field is set to TRUE if the puzzle has a use for a textual
+status line (to display score, completion status, currently active
+tiles, etc).
+
+#2.10.5. `is_timed'
+
+  int is_timed;
+
+This boolean field is 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 FALSE, then timing_state() will never be called and
+need not do anything.
+
+#2.10.6. timing_state()
+
+  int (*timing_state)(const game_state *state, game_ui *ui);
+
+This function is passed the current `game_state' and the local
+`game_ui'; it returns TRUE if the game timer should currently be
+running.
+
+A typical use for the `game_ui' in this function is to note when the
+game was first completed (by setting a flag in changed_state() - see
+section 2.6.5), and freeze the timer thereafter so that the user can
+undo back through their solution process without altering their time.
+
+#2.10.7. `flags'
+
+  int flags;
+
+This field contains miscellaneous per-backend flags. It consists of the
+bitwise OR of some combination of the following:
+
+BUTTON_BEATS(x,y)
+
+    Given any x and y from the set {LEFT_BUTTON, MIDDLE_BUTTON,
+    RIGHT_BUTTON}, this macro evaluates to a bit flag which indicates
+    that when buttons x and y are both pressed simultaneously, the mid-
+    end should consider 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.)
+
+SOLVE_ANIMATES
+
+    This flag indicates that moves generated by solve() (section 2.7.4)
+    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 anim_length() (section 2.8.7), 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.
+
+REQUIRE_RBUTTON
+
+    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 _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.)
+
+REQUIRE_NUMPAD
+
+    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
+    REQUIRE_RBUTTON, a puzzle need not specify this simply if its use of
+    the number keys is not critical.
+
+#2.11. 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.
+
+#2.11.1. Create a random state
+
+If a back end needs random numbers at some point during normal play, it
+can create a fresh `random_state' by first calling `get_random_seed'
+(section 4.35) and then passing the returned seed data to 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 `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 `jumble'
+command, which sets every unlocked tile to a new random orientation.
+This randomness _is_ a reasonable use of the feature, because it's non-
+adversarial - there's no advantage to the user in getting different
+random numbers.
+
+#2.11.2. Supersede its own game description
+
+In response to a move, a back end is (reluctantly) permitted to call
+midend_supersede_game_desc():
+
+  void midend_supersede_game_desc(midend *me,
+                                  char *desc, char *privdesc);
+
+When the user selects `New Game', the mid-end calls new_desc()
+(section 2.4.1) 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. `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 `Restart'. `privdesc' is a `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; new_desc() does almost no
+work in interactive mode, and simply returns a string encoding the
+`random_state'. When the user first clicks to open a tile, _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 _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.
+
+#3. The drawing API
+
+The back end function redraw() (section 2.8.10) is required to draw
+the puzzle's graphics on the window's drawing area, or on paper if the
+puzzle is printable. To do this portably, it 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 `drawing' structure (a
+`drawing object'). These objects are supplied as parameters to the back
+end's redraw() and print() functions.
+
+In fact these global functions are not implemented directly by the front
+end; instead, they are implemented centrally in `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 `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
+_possible_ to write a single (say) 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 (0,0) and the bottom right pixel (w-1,h-
+1), where `w' and `h' are the width and height values returned by the
+back end function compute_size() (section 2.8.4).
+
+When printing, the puzzle's print area is indexed in exactly the same
+way (with an arbitrary tile size provided by the printing module
+`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.
+
+_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
+draw_update() (section 3.1.11).
+
+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 _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 `ink' and the boundary appears to `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 clip() function (section 3.1.9) 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 _almost_ identical function-pointer form seen by
+the front end.
+
+#3.1. Drawing API as seen by the back end
+
+This section documents the back-end drawing API, in the form of
+functions which take a `drawing' object as an argument.
+
+#3.1.1. draw_rect()
+
+  void draw_rect(drawing *dr, int x, int y, int w, int h,
+                 int colour);
+
+Draws a filled rectangle in the puzzle window.
+
+`x' and `y' give the coordinates of the top left pixel of the rectangle.
+`w' and `h' give its width and height. Thus, the horizontal extent of
+the rectangle runs from `x' to `x+w-1' inclusive, and the vertical
+extent from `y' to `y+h-1' inclusive.
+
+`colour' is an integer index into the colours array returned by the back
+end function colours() (section 2.8.6).
+
+There is no separate pixel-plotting function. If you want to plot a
+single pixel, the approved method is to use 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.
+
+#3.1.2. draw_rect_outline()
+
+  void draw_rect_outline(drawing *dr, int x, int y, int w, int h,
+                         int colour);
+
+Draws an outline rectangle in the puzzle window.
+
+`x' and `y' give the coordinates of the top left pixel of the rectangle.
+`w' and `h' give its width and height. Thus, the horizontal extent of
+the rectangle runs from `x' to `x+w-1' inclusive, and the vertical
+extent from `y' to `y+h-1' inclusive.
+
+`colour' is an integer index into the colours array returned by the back
+end function colours() (section 2.8.6).
+
+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 misc.c) as a wrapper
+on draw_polygon().
+
+This function may be used for both drawing and printing.
+
+#3.1.3. draw_line()
+
+  void draw_line(drawing *dr, int x1, int y1, int x2, int y2,
+                 int colour);
+
+Draws a straight line in the puzzle window.
+
+`x1' and `y1' give the coordinates of one end of the line. `x2' and `y2'
+give the coordinates of the other end. The line drawn includes both
+those points.
+
+`colour' is an integer index into the colours array returned by the back
+end function colours() (section 2.8.6).
+
+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.
+
+#3.1.4. draw_polygon()
+
+  void draw_polygon(drawing *dr, int *coords, int npoints,
+                    int fillcolour, int outlinecolour);
+
+Draws an outlined or filled polygon in the puzzle window.
+
+`coords' is an array of (2*npoints) integers, containing the `x' and `y'
+coordinates of `npoints' vertices.
+
+`fillcolour' and `outlinecolour' are integer indices into the colours
+array returned by the back end function colours() (section 2.8.6).
+`fillcolour' may also be -1 to indicate that the polygon should be
+outlined only.
+
+The polygon defined by the specified list of vertices is first filled in
+`fillcolour', if specified, and then outlined in `outlinecolour'.
+
+`outlinecolour' may _not_ be -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 _only_ a filled polygon would
+have non-portable effects. If you want your filled polygon not to
+have a visible outline, you must set `outlinecolour' to the same as
+`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 clip() (section 3.1.9). You can rely
+on horizontal and vertical lines not being anti-aliased.
+
+This function may be used for both drawing and printing.
+
+#3.1.5. draw_circle()
+
+  void draw_circle(drawing *dr, int cx, int cy, int radius,
+                   int fillcolour, int outlinecolour);
+
+Draws an outlined or filled circle in the puzzle window.
+
+`cx' and `cy' give the coordinates of the centre of the circle. `radius'
+gives its radius. The total horizontal pixel extent of the circle is
+from `cx-radius+1' to `cx+radius-1' inclusive, and the vertical extent
+similarly around `cy'.
+
+`fillcolour' and `outlinecolour' are integer indices into the colours
+array returned by the back end function colours() (section 2.8.6).
+`fillcolour' may also be -1 to indicate that the circle should be
+outlined only.
+
+The circle is first filled in `fillcolour', if specified, and then
+outlined in `outlinecolour'.
+
+`outlinecolour' may _not_ be -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 _only_ a filled circle would
+have non-portable effects. If you want your filled circle not to
+have a visible outline, you must set `outlinecolour' to the same as
+`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 clip() (section 3.1.9).
+
+This function may be used for both drawing and printing.
+
+#3.1.6. draw_thick_line()
+
+  void draw_thick_line(drawing *dr, float thickness,
+                       float x1, float y1, float x2, float y2,
+                       int colour)
+
+Draws a line in the puzzle window, giving control over the line's
+thickness.
+
+`x1' and `y1' give the coordinates of one end of the line. `x2' and `y2'
+give the coordinates of the other end. `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.
+
+#3.1.7. draw_text()
+
+  void draw_text(drawing *dr, int x, int y, int fonttype,
+                 int fontsize, int align, int colour,
+                 const char *text);
+
+Draws text in the puzzle window.
+
+`x' and `y' give the coordinates of a point. The relation of this point
+to the location of the text is specified by `align', which is a bitwise
+OR of horizontal and vertical alignment flags:
+
+ALIGN_VNORMAL
+
+    Indicates that `y' is aligned with the baseline of the text.
+
+ALIGN_VCENTRE
+
+    Indicates that `y' is aligned with the vertical centre of the
+    text. (In fact, it's aligned with the vertical centre of normal
+    _capitalised_ text: displaying two pieces of text with ALIGN_VCENTRE
+    at the same y-coordinate will cause their baselines to be aligned
+    with one another, even if one is an ascender and the other a
+    descender.)
+
+ALIGN_HLEFT
+
+    Indicates that `x' is aligned with the left-hand end of the text.
+
+ALIGN_HCENTRE
+
+    Indicates that `x' is aligned with the horizontal centre of the
+    text.
+
+ALIGN_HRIGHT
+
+    Indicates that `x' is aligned with the right-hand end of the text.
+
+`fonttype' is either FONT_FIXED or 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.)
+
+`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.
+
+`colour' is an integer index into the colours array returned by the back
+end function colours() (section 2.8.6).
+
+This function may be used for both drawing and printing.
+
+The character set used to encode the text passed to this function is
+specified _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 text_fallback() function (section 3.1.8) to query the
+drawing object for an appropriate representation of the characters it
+wants.
+
+#3.1.8. text_fallback()
+
+  char *text_fallback(drawing *dr, const char *const *strings,
+                      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 draw_text().
+
+The input is a list of strings encoded in UTF-8: nstrings gives the
+number of strings in the list, and strings[0], strings[1], ...,
+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
+draw_text().
+
+Drawing implementations are not required to handle anything outside
+ASCII, but are permitted to assume that _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:
+
+  static const char *const times_signs[] = { "\xC3\x97", "x" };
+  char *times_sign = text_fallback(dr, times_signs, 2);
+  sprintf(buffer, "%d%s%d", width, times_sign, height);
+  draw_text(dr, x, y, font, size, align, colour, buffer);
+  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 `x' where there was no
+alternative.
+
+#3.1.9. clip()
+
+  void clip(drawing *dr, int x, int y, int w, int h);
+
+Establishes a clipping rectangle in the puzzle window.
+
+`x' and `y' give the coordinates of the top left pixel of the clipping
+rectangle. `w' and `h' give its width and height. Thus, the horizontal
+extent of the rectangle runs from `x' to `x+w-1' inclusive, and the
+vertical extent from `y' to `y+h-1' inclusive. (These are exactly the
+same semantics as draw_rect().)
+
+After this call, no drawing operation will affect anything outside the
+specified rectangle. The effect can be reversed by calling unclip()
+(section 3.1.10). 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 unclip().
+
+This function may be used for both drawing and printing.
+
+#3.1.10. unclip()
+
+  void unclip(drawing *dr);
+
+Reverts the effect of a previous call to 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.
+
+#3.1.11. draw_update()
+
+  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.
+
+`x' and `y' give the coordinates of the top left pixel of the update
+rectangle. `w' and `h' give its width and height. Thus, the horizontal
+extent of the rectangle runs from `x' to `x+w-1' inclusive, and the
+vertical extent from `y' to `y+h-1' inclusive. (These are exactly the
+same semantics as draw_rect().)
+
+The back end redraw function _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 draw_update().)
+
+#3.1.12. status_bar()
+
+  void status_bar(drawing *dr, const char *text);
+
+Sets the text in the game's status bar to `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 _drawing_ function, but it shares with
+the drawing API the property that it may only be called from within the
+back end redraw function, so this is as good a place as any 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.
+
+#3.1.13. 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 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
+redraw() the first thing it does is to restore the background.
+
+The front end defines an opaque type called a `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.
+
+#3.1.13.1. blitter_new()
+
+  blitter *blitter_new(drawing *dr, int w, int h);
+
+Creates a new blitter object which stores a rectangle of size `w' by `h'
+pixels. Returns a pointer to the blitter object.
+
+Blitter objects are best stored in the `game_drawstate'. A good time to
+create them is in the set_size() function (section 2.8.5), since it is
+at this point that you first know how big a rectangle they will need to
+save.
+
+#3.1.13.2. blitter_free()
+
+  void blitter_free(drawing *dr, blitter *bl);
+
+Disposes of a blitter object. Best called in free_drawstate(). (However,
+check that the blitter object is not NULL before attempting to free it;
+it is possible that a draw state might be created and freed without ever
+having set_size() called on it in between.)
+
+#3.1.13.3. blitter_save()
+
+  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.
+
+`x' and `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 `x' and `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.)
+
+#3.1.13.4. blitter_load()
+
+  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.
+
+`x' and `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 `x' and `y' as the special value
+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 `x' and
+`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.
+
+#3.1.14. print_mono_colour()
+
+  int print_mono_colour(drawing *dr, int grey);
+
+This function allocates a colour index for a simple monochrome colour
+during printing.
+
+`grey' must be 0 or 1. If `grey' is 0, the colour returned is black; if
+`grey' is 1, the colour is white.
+
+#3.1.15. print_grey_colour()
+
+  int print_grey_colour(drawing *dr, float grey);
+
+This function allocates a colour index for a grey-scale colour during
+printing.
+
+`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.
+
+#3.1.16. print_hatched_colour()
+
+  int print_hatched_colour(drawing *dr, int hatch);
+
+This function allocates a colour index which does not represent a
+literal _colour_. Instead, regions shaded in this colour will be hatched
+with parallel lines. The `hatch' parameter defines what type of hatching
+should be used in place of this colour:
+
+HATCH_SLASH
+
+    This colour will be hatched by lines slanting to the right at 45
+    degrees.
+
+HATCH_BACKSLASH
+
+    This colour will be hatched by lines slanting to the left at 45
+    degrees.
+
+HATCH_HORIZ
+
+    This colour will be hatched by horizontal lines.
+
+HATCH_VERT
+
+    This colour will be hatched by vertical lines.
+
+HATCH_PLUS
+
+    This colour will be hatched by criss-crossing horizontal and
+    vertical lines.
+
+HATCH_X
+
+    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 `fillcolour' parameter to draw_circle() and draw_polygon(),
+and as the colour parameter to draw_rect(), but may not be used as the
+`outlinecolour' parameter to draw_circle() or draw_polygon(), or with
+draw_line() or draw_text().
+
+#3.1.17. print_rgb_mono_colour()
+
+  int print_rgb_mono_colour(drawing *dr, float r, float g,
+                            float b, float grey);
+
+This function allocates a colour index for a fully specified RGB colour
+during printing.
+
+`r', `g' and `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
+`grey' parameter. (The fallback colour is the same as the one which
+would be allocated by print_mono_colour(grey).)
+
+#3.1.18. print_rgb_grey_colour()
+
+  int print_rgb_grey_colour(drawing *dr, float r, float g,
+                            float b, float grey);
+
+This function allocates a colour index for a fully specified RGB colour
+during printing.
+
+`r', `g' and `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 `grey' parameter will be used instead.
+(The fallback colour is the same as the one which would be allocated by
+print_grey_colour(grey).)
+
+#3.1.19. print_rgb_hatched_colour()
+
+  int print_rgb_hatched_colour(drawing *dr, float r, float g,
+                               float b, float hatched);
+
+This function allocates a colour index for a fully specified RGB colour
+during printing.
+
+`r', `g' and `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 `hatch' parameter will be used
+instead; see section 3.1.16 for the possible values of this parameter.
+(The fallback colour is the same as the one which would be allocated by
+print_hatched_colour(hatch).)
+
+#3.1.20. print_line_width()
+
+  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 draw_line(),
+draw_circle and 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.
+
+#3.1.21. print_line_dotted()
+
+  void print_line_dotted(drawing *dr, int dotted);
+
+This function is called to toggle the drawing of dotted lines during
+printing. It is not supported during drawing.
+
+The parameter `dotted' is a boolean; TRUE means that future lines drawn
+by draw_line(), draw_circle and draw_polygon() will be dotted, and 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.
+
+#3.2. 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 `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 `drawing_api'. Each of the functions takes a `void *'
+context pointer, which it should internally cast back to a more useful
+type. Thus, a drawing _object_ (`drawing *)' suitable for passing to
+the back end redraw or printing functions is constructed by passing a
+`drawing_api' and a `void *' to the function drawing_new() (see section
+3.3.1).
+
+#3.2.1. draw_text()
+
+  void (*draw_text)(void *handle, int x, int y, int fonttype,
+                    int fontsize, int align, int colour,
+                    const char *text);
+
+This function behaves exactly like the back end draw_text() function;
+see section 3.1.7.
+
+#3.2.2. draw_rect()
+
+  void (*draw_rect)(void *handle, int x, int y, int w, int h,
+                    int colour);
+
+This function behaves exactly like the back end draw_rect() function;
+see section 3.1.1.
+
+#3.2.3. draw_line()
+
+  void (*draw_line)(void *handle, int x1, int y1, int x2, int y2,
+                    int colour);
+
+This function behaves exactly like the back end draw_line() function;
+see section 3.1.3.
+
+#3.2.4. draw_polygon()
+
+  void (*draw_polygon)(void *handle, int *coords, int npoints,
+                       int fillcolour, int outlinecolour);
+
+This function behaves exactly like the back end draw_polygon() function;
+see section 3.1.4.
+
+#3.2.5. draw_circle()
+
+  void (*draw_circle)(void *handle, int cx, int cy, int radius,
+                      int fillcolour, int outlinecolour);
+
+This function behaves exactly like the back end draw_circle() function;
+see section 3.1.5.
+
+#3.2.6. draw_thick_line()
+
+  void draw_thick_line(drawing *dr, float thickness,
+                       float x1, float y1, float x2, float y2,
+                       int colour)
+
+This function behaves exactly like the back end draw_thick_line()
+function; see section 3.1.6.
+
+An implementation of this API which doesn't provide high-quality
+rendering of thick lines is permitted to define this function pointer
+to be NULL. The middleware in drawing.c will notice and provide a low-
+quality alternative using draw_polygon().
+
+#3.2.7. draw_update()
+
+  void (*draw_update)(void *handle, int x, int y, int w, int h);
+
+This function behaves exactly like the back end draw_update() function;
+see section 3.1.11.
+
+An implementation of this API which only supports printing is permitted
+to define this function pointer to be NULL rather than bothering to
+define an empty function. The middleware in drawing.c will notice and
+avoid calling it.
+
+#3.2.8. clip()
+
+  void (*clip)(void *handle, int x, int y, int w, int h);
+
+This function behaves exactly like the back end clip() function; see
+section 3.1.9.
+
+#3.2.9. unclip()
+
+  void (*unclip)(void *handle);
+
+This function behaves exactly like the back end unclip() function; see
+section 3.1.10.
+
+#3.2.10. start_draw()
+
+  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 NULL; it will never be called unless
+drawing is attempted.
+
+#3.2.11. end_draw()
+
+  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 NULL; it will never be called unless
+drawing is attempted.
+
+#3.2.12. status_bar()
+
+  void (*status_bar)(void *handle, const char *text);
+
+This function behaves exactly like the back end status_bar() function;
+see section 3.1.12.
+
+Front ends implementing this function need not worry about it
+being called repeatedly with the same text; the middleware code in
+status_bar() will take care of this.
+
+Implementations of this API which do not provide drawing services may
+define this function pointer to be NULL; it will never be called unless
+drawing is attempted.
+
+#3.2.13. blitter_new()
+
+  blitter *(*blitter_new)(void *handle, int w, int h);
+
+This function behaves exactly like the back end blitter_new() function;
+see section 3.1.13.1.
+
+Implementations of this API which do not provide drawing services may
+define this function pointer to be NULL; it will never be called unless
+drawing is attempted.
+
+#3.2.14. blitter_free()
+
+  void (*blitter_free)(void *handle, blitter *bl);
+
+This function behaves exactly like the back end blitter_free() function;
+see section 3.1.13.2.
+
+Implementations of this API which do not provide drawing services may
+define this function pointer to be NULL; it will never be called unless
+drawing is attempted.
+
+#3.2.15. blitter_save()
+
+  void (*blitter_save)(void *handle, blitter *bl, int x, int y);
+
+This function behaves exactly like the back end blitter_save() function;
+see section 3.1.13.3.
+
+Implementations of this API which do not provide drawing services may
+define this function pointer to be NULL; it will never be called unless
+drawing is attempted.
+
+#3.2.16. blitter_load()
+
+  void (*blitter_load)(void *handle, blitter *bl, int x, int y);
+
+This function behaves exactly like the back end blitter_load() function;
+see section 3.1.13.4.
+
+Implementations of this API which do not provide drawing services may
+define this function pointer to be NULL; it will never be called unless
+drawing is attempted.
+
+#3.2.17. begin_doc()
+
+  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 NULL; it will never be called unless
+printing is attempted.
+
+#3.2.18. begin_page()
+
+  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 NULL; it will never be called unless
+printing is attempted.
+
+#3.2.19. begin_puzzle()
+
+  void (*begin_puzzle)(void *handle, float xm, float xc,
+                       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.
+
+`xm' and `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 `xm', add `xc' (measured in millimetres), and
+use the resulting x-coordinate as the left edge of the puzzle.
+
+Similarly, `ym' and `yc' specify the vertical position of the puzzle as
+a function of the page height: the page height times `ym', plus `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 `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.)
+
+pw and 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 pw by ph units is available to draw the puzzle on.
+
+Finally, 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 wmm*ph/pw.)
+
+Implementations of this API which do not provide printing services may
+define this function pointer to be NULL; it will never be called unless
+printing is attempted.
+
+#3.2.20. end_puzzle()
+
+  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 NULL; it will never be called unless
+printing is attempted.
+
+#3.2.21. end_page()
+
+  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 NULL; it will never be called unless
+printing is attempted.
+
+#3.2.22. end_doc()
+
+  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 NULL; it will never be called unless
+printing is attempted.
+
+#3.2.23. line_width()
+
+  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 float here, where it was an int as seen by the
+back end. This is because 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 NULL; it will never be called unless
+printing is attempted.
+
+#3.2.24. text_fallback()
+
+  char *(*text_fallback)(void *handle, const char *const *strings,
+                         int nstrings);
+
+This function behaves exactly like the back end text_fallback()
+function; see section 3.1.8.
+
+Implementations of this API which do not support any characters outside
+ASCII may define this function pointer to be NULL, in which case the
+central code in drawing.c will provide a default implementation.
+
+#3.3. The drawing API as called by the front end
+
+There are a small number of functions provided in drawing.c which the
+front end needs to _call_, rather than helping to implement. They are
+described in this section.
+
+#3.3.1. drawing_new()
+
+  drawing *drawing_new(const drawing_api *api, midend *me,
+                       void *handle);
+
+This function creates a drawing object. It is passed a `drawing_api',
+which is a structure containing nothing but function pointers; and also
+a `void *' handle. The handle is passed back to each function pointer
+when it is called.
+
+The `midend' parameter is used for rewriting the status bar contents:
+status_bar() (see section 3.1.12) 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
+status_bar(), this parameter may be NULL.
+
+#3.3.2. drawing_free()
+
+  void drawing_free(drawing *dr);
+
+This function frees a drawing object. Note that the `void *' handle is
+not freed; if that needs cleaning up it must be done by the front end.
+
+#3.3.3. print_get_colour()
+
+  void print_get_colour(drawing *dr, int colour, int printincolour,
+                        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.
+
+`printincolour' is 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, `*hatch' is filled with
+the type of hatching desired. See section 3.1.15 for details of the
+values this integer can take.
+
+If the colour should be rendered as solid colour, `*hatch' is given a
+negative value, and `*r', `*g' and `*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).
+
+#4. 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
+`midend' structure, to facilitate having multiple mid-ends in any
+port which supports multiple puzzle windows open simultaneously. Each
+`midend' is intended to handle the contents of a single puzzle window.
+
+#4.1. midend_new()
+
+  midend *midend_new(frontend *fe, const game *ourgame,
+                     const drawing_api *drapi, void *drhandle)
+
+Allocates and returns a new mid-end structure.
+
+The `fe' argument is stored in the mid-end. It will be used when calling
+back to functions such as activate_timer() (section 4.36), and will be
+passed on to the back end function colours() (section 2.8.6).
+
+The parameters `drapi' and `drhandle' are passed to drawing_new()
+(section 3.3.1) to construct a drawing object which will be passed to
+the back end function redraw() (section 2.8.10). Hence, all drawing-
+related function pointers defined in `drapi' can expect to be called
+with `drhandle' as their first argument.
+
+The `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...)
+
+#4.2. midend_free()
+
+  void midend_free(midend *me);
+
+Frees a mid-end structure and all its associated data.
+
+#4.3. midend_tilesize()
+
+  int midend_tilesize(midend *me);
+
+Returns the `tilesize' parameter being used to display the current
+puzzle (section 2.8.3).
+
+#4.4. midend_set_params()
+
+  void midend_set_params(midend *me, game_params *params);
+
+Sets the current game parameters for a mid-end. Subsequent games
+generated by midend_new_game() (section 4.8) will use these parameters
+until further notice.
+
+The usual way in which the front end will have an actual `game_params'
+structure to pass to this function is if it had previously got it from
+midend_get_presets() (section 4.15). Thus, this function is usually
+called in response to the user making a selection from the presets menu.
+
+#4.5. midend_get_params()
+
+  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 free_params() function
+(see section 2.3.6).
+
+#4.6. midend_size()
+
+  void midend_size(midend *me, int *x, int *y, int user_size);
+
+Tells the mid-end to figure out its window size.
+
+On input, `*x' and `*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 compute_size() (section 2.8.4), searching for a tile
+size that best satisfies the requirements. On exit, `*x' and `*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 `user_size' to indicate whether `*x' and `*y' are a requested size,
+or just a maximum size.
+
+If `user_size' is set to TRUE, the mid-end will treat the input size as
+a request, and will pick a tile size which approximates it _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 `user_size' is set to 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 `*x' and `*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 _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 INT_MAX
+as input to this function. You should probably not do that _and_ set the
+`user_size' flag, though!
+
+The midend relies on the frontend calling midend_new_game() (section
+4.8) before calling midend_size().
+
+#4.7. midend_reset_tilesize()
+
+  void midend_reset_tilesize(midend *me);
+
+This function resets the midend's preferred tile size to that of the
+standard puzzle.
+
+As discussed in section 4.6, 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 _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 midend_size()
+(which, in turn, you would probably call with `user_size' set to FALSE).
+
+#4.8. midend_new_game()
+
+  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
+midend_game_id() or midend_set_config(), the game generated might be
+dictated by the results of those functions. (In particular, you _must_
+call midend_new_game() after calling either of those functions, or else
+no immediate effect will be visible.)
+
+You will probably need to call 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 _haven't_ changed, you don't need to do this.)
+
+This function will create a new `game_drawstate', but does not actually
+perform a redraw (since you often need to call midend_size() before
+the redraw can be done). So after calling this function and after
+calling midend_size(), you should then call midend_redraw(). (It is not
+necessary to call 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.)
+
+#4.9. midend_restart_game()
+
+  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 _within_ a call to this
+function. Some back ends require that midend_size() (section 4.6) is
+called before midend_restart_game().
+
+#4.10. midend_force_redraw()
+
+  void midend_force_redraw(midend *me);
+
+Forces a complete redraw of the puzzle window, by means of discarding
+the current `game_drawstate' and creating a new one from scratch before
+calling the game's 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 midend_size() (section
+4.6) is called before midend_force_redraw().
+
+#4.11. midend_redraw()
+
+  void midend_redraw(midend *me);
+
+Causes a partial redraw of the puzzle window, by means of simply calling
+the game's 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 midend_size() (section
+4.6) is called before midend_redraw().
+
+#4.12. midend_process_key()
+
+  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 `x', `y' and `button' are almost identical to the ones
+passed to the back end function interpret_move() (section 2.7.1), except
+that the front end is _not_ required to provide the 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, LEFT_DRAG events
+and start receiving RIGHT_DRAGs, 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 _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 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 _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 activate_timer() (section 4.36).
+
+The return value from midend_process_key() is non-zero, unless the
+effect of the keypress was to request termination of the program. A
+front end should shut down the puzzle in response to a zero return.
+
+#4.13. midend_colours()
+
+  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 colours()
+(section 2.8.6). 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.)
+
+#4.14. midend_timer()
+
+  void midend_timer(midend *me, float tplus);
+
+If the mid-end has called activate_timer() (section 4.36) 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
+`tplus' gives the time, in seconds, since the last time either this
+function was called or 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.
+
+#4.15. midend_get_presets()
+
+  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):
+
+  struct preset_menu {
+      int n_entries;
+      struct preset_menu_entry *entries;
+      /* and other things */
+  };
+
+Those fields describe the intended contents of one particular menu in
+the hierarchy. `entries' points to an array of `n_entries' items, each
+of which is a structure containing the following fields:
+
+  struct preset_menu_entry {
+      char *title;
+      game_params *params;
+      struct preset_menu *submenu;
+      int id;
+  };
+
+Of these fields, `title' and `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 `midend_which_preset' (section 4.16), when that preset is the one
+selected.
+
+The other two fields are mutually exclusive. Each
+`struct preset_menu_entry' will have one of those fields NULL and the
+other one non-null. If the menu item is an actual preset, then `params'
+will point to the set of game parameters that go with the name; if it's
+a submenu, then `submenu' instead will be non-null, and will point at a
+subsidiary `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 `id_limit'
+to midend_get_presets as the address of an `int' variable, into which
+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.
+
+#4.16. midend_which_preset()
+
+  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 `Custom' option if the return value is
+less than zero).
+
+The returned index value (if non-negative) will match the `id'
+field of the corresponding struct preset_menu_entry returned by
+`midend_get_presets()' (section 4.15).
+
+#4.17. midend_wants_statusbar()
+
+  int midend_wants_statusbar(midend *me);
+
+This function returns 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.
+
+#4.18. midend_get_config()
+
+  config_item *midend_get_config(midend *me, int which,
+                                 char **wintitle);
+
+Returns a dialog box description for user configuration.
+
+On input, which should be set to one of three values, which select which
+of the various dialog box descriptions is returned:
+
+CFG_SETTINGS
+
+    Requests the GUI parameter configuration box generated by the puzzle
+    itself. This should be used when the user selects `Custom' from the
+    game types menu (or equivalent). The mid-end passes this request on
+    to the back end function configure() (section 2.3.9).
+
+CFG_DESC
+
+    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
+    `Specific' from the game menu (or equivalent).
+
+CFG_SEED
+
+    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
+    `Random Seed' from the game menu (or equivalent).
+
+The returned value is an array of config_items, exactly as described
+in section 2.3.9. Another returned value is an ASCII string giving a
+suitable title for the configuration window, in `*wintitle'.
+
+Both returned values are dynamically allocated and will need to be
+freed. The window title can be freed in the obvious way; the config_item
+array is a slightly complex structure, so a utility function free_cfg()
+is provided to free it for you. See section 5.3.6.
+
+(Of course, you will probably not want to free the config_item array
+until the dialog box is dismissed, because before then you will probably
+need to pass it to midend_set_config.)
+
+#4.19. midend_set_config()
+
+  const char *midend_set_config(midend *me, int which,
+                                config_item *cfg);
+
+Passes the mid-end the results of a configuration dialog box. `which'
+should have the same value which it had when midend_get_config() was
+called; `cfg' should be the array of `config_item's returned from
+midend_get_config(), modified to contain the results of the user's
+editing operations.
+
+This function returns 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 midend_new_game(), and probably also
+re-think the window size using midend_size() and eventually perform a
+refresh using midend_redraw().
+
+#4.20. midend_game_id()
+
+  const char *midend_game_id(midend *me, const char *id);
+
+Passes the mid-end a string game ID (of any of the valid forms `params',
+`params:description' or `params#seed') which the mid-end will process
+and use for the next generated game.
+
+This function returns 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 midend_new_game(), and probably
+also re-think the window size using midend_size() and eventually case a
+refresh using midend_redraw().
+
+#4.21. midend_get_game_id()
+
+  char *midend_get_game_id(midend *me)
+
+Returns a descriptive game ID (i.e. one in the form
+`params:description') describing the game currently active in the mid-
+end. The returned string is dynamically allocated.
+
+#4.22. midend_get_random_seed()
+
+  char *midend_get_random_seed(midend *me)
+
+Returns a random game ID (i.e. one in the form `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 NULL.
+
+The returned string, if it is non-NULL, is dynamically allocated.
+
+#4.23. midend_can_format_as_text_now()
+
+  int midend_can_format_as_text_now(midend *me);
+
+Returns TRUE if the game code is capable of formatting puzzles of the
+currently selected game type as ASCII.
+
+If this returns FALSE, then midend_text_format() (section 4.24) will
+return NULL.
+
+#4.24. midend_text_format()
+
+  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 `can_format_as_text_ever' flag is FALSE, or if its
+can_format_as_text_now() function returns FALSE, then this function will
+return NULL.
+
+If the returned string contains multiple lines (which is likely), it
+will use the normal C line ending convention (\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.
+
+#4.25. midend_solve()
+
+  const char *midend_solve(midend *me);
+
+Requests the mid-end to perform a Solve operation.
+
+On success, 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 activate_timer() to be
+called from within a call to this function. Some back ends require that
+midend_size() (section 4.6) is called before midend_solve().
+
+#4.26. midend_status()
+
+  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 status() function.
+Front ends may wish to use this as a cue to proactively offer the option
+of starting a new game.
+
+(See section 2.8.9 for more detail about the back end's status()
+function and discussion of what should count as which status code.)
+
+#4.27. midend_can_undo()
+
+  int midend_can_undo(midend *me);
+
+Returns 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.
+
+#4.28. midend_can_redo()
+
+  int midend_can_redo(midend *me);
+
+Returns 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.
+
+#4.29. midend_serialise()
+
+  void midend_serialise(midend *me,
+      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 `write' function.
+
+Desktop implementations can use this function to save a game in any
+state (including half-finished) to a disk file, by supplying a `write'
+function which is a wrapper on 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 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 `write' function a number
+of times, with the first parameter (`ctx') equal to `wctx', and the
+other two parameters pointing at a piece of the output string.
+
+#4.30. midend_deserialise()
+
+  const char *midend_deserialise(midend *me,
+      int (*read)(void *ctx, void *buf, int len), void *rctx);
+
+This function is the counterpart to midend_serialise(). It calls the
+supplied read function repeatedly to read a quantity of data, and
+attempts to interpret that data as a serialised mid-end as output by
+midend_serialise().
+
+The read function is called with the first parameter (`ctx') equal
+to `rctx', and should attempt to read `len' bytes of data into the
+buffer pointed to by `buf'. It should return FALSE on failure or 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, `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 NULL
+will be returned. Otherwise, the mid-end's state will be completely
+unchanged and an error message (typically some variation on `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 midend_size(), and probably cause a refresh using
+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 section 4.31 for a
+helper function which will allow you to identify a save file before you
+instantiate your mid-end in the first place.
+
+#4.31. identify_game()
+
+  const char *identify_game(char **name,
+      int (*read)(void *ctx, void *buf, int len), void *rctx);
+
+This function examines a serialised midend stream, of the same kind used
+by midend_serialise() and midend_deserialise(), and returns the 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 gamelist (section 4.33) looking for a game
+structure whose 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 NULL, and the game name
+string is written into *name. The caller should free that string after
+using it.
+
+On failure, *name is 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 _before_
+deciding what kind of midend you wanted to instantiate.)
+
+#4.32. midend_request_id_changes()
+
+  void midend_request_id_changes(midend *me,
+                                 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 section
+2.11.2). After this function is called, any change of the game ids will
+cause the mid-end to call 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.
+
+#4.33. Direct reference to the back end structure by the front end
+
+Although _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
+
+ -  passing the game back end as a parameter to 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:
+
+ -  fetching the `name' field to use in window titles and similar
+
+ -  reading the `can_configure', `can_solve' and
+    `can_format_as_text_ever' fields to decide whether to add those
+    items to the menu bar or equivalent
+
+ -  reading the `winhelp_topic' field (Windows only)
+
+ -  the GTK front end provides a `--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:
+
+ -  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 `thegame':
+
+      extern const game thegame;
+
+ -  If the front end is compiled as a monolithic application containing
+    all the puzzles together (in which case the preprocessor symbol
+    COMBINED must be defined when compiling most of the code base), then
+    there will be two global variables defined:
+
+      extern const game *gamelist[];
+      extern const int gamecount;
+
+    `gamelist' will be an array of `gamecount' game structures, declared
+    in the automatically constructed source module `list.c'. The
+    application should search that array for the game it wants, probably
+    by reaching into each game structure and looking at its `name'
+    field.
+
+#4.34. 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.
+
+#4.35. get_random_seed()
+
+  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 `random_state'.
+
+On exit, `*randseed' should be set to point at a newly allocated piece
+of memory containing some seed data, and `*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.
+
+#4.36. activate_timer()
+
+  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 midend_timer() on a regular basis.
+
+#4.37. deactivate_timer()
+
+  void deactivate_timer(frontend *fe);
+
+This is called by the mid-end to request that the front end stop calling
+midend_timer().
+
+#4.38. fatal()
+
+  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 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.
+
+#4.39. frontend_default_colour()
+
+  void frontend_default_colour(frontend *fe, float *output);
+
+This function expects to be passed a pointer to an array of three
+floats. It returns the platform's local preferred background colour
+in those three floats, as red, green and blue values (in that order)
+ranging from 0.0 to 1.0.
+
+This function should only ever be called by the back end function
+colours() (section 2.8.6). (Thus, it isn't a _midend_-to-frontend
+function as such, but there didn't seem to be anywhere else particularly
+good to put it. Sorry.)
+
+#5. Utility APIs
+
+This chapter documents a variety of utility APIs provided for the
+general use of the rest of the Puzzles code.
+
+#5.1. 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 rand() function, the Puzzles random number generator
+has an _explicit_ state object called a `random_state'. One of these
+is managed by each mid-end, for example, and passed to the back end to
+generate a game with.
+
+#5.1.1. random_new()
+
+  random_state *random_new(char *seed, int len);
+
+Allocates, initialises and returns a new `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.
+
+#5.1.2. random_copy()
+
+  random_state *random_copy(random_state *tocopy);
+
+Allocates a new `random_state', copies the contents of another
+`random_state' into it, and returns the new state. If exactly the
+same sequence of functions is subseqently 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.
+
+#5.1.3. random_free()
+
+  void random_free(random_state *state);
+
+Frees a `random_state'.
+
+#5.1.4. random_bits()
+
+  unsigned long random_bits(random_state *state, int bits);
+
+Returns a random number from 0 to 2^bits-1 inclusive. `bits' should be
+between 1 and 32 inclusive.
+
+#5.1.5. random_upto()
+
+  unsigned long random_upto(random_state *state, unsigned long limit);
+
+Returns a random number from 0 to limit-1 inclusive.
+
+#5.1.6. random_state_encode()
+
+  char *random_state_encode(random_state *state);
+
+Encodes the entire contents of a `random_state' in printable ASCII.
+Returns a dynamically allocated string containing that encoding. This
+can subsequently be passed to random_state_decode() to reconstruct the
+same `random_state'.
+
+#5.1.7. random_state_decode()
+
+  random_state *random_state_decode(char *input);
+
+Decodes a string generated by random_state_encode() and reconstructs an
+equivalent `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.
+
+#5.1.8. shuffle()
+
+  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
+qsort(), except that there's no need for a compare function.
+
+`array' is a pointer to the first element of the array. `nelts' is the
+number of elements in the array; `eltsize' is the size of a single
+element (typically measured using `sizeof'). `rs' is a `random_state'
+used to generate all the random numbers for the shuffling process.
+
+#5.2. Presets menu management
+
+The function `midend_get_presets()' (section 4.15) 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.
+
+#5.2.1. preset_menu_new()
+
+  struct preset_menu *preset_menu_new(void);
+
+Allocates a new `struct preset_menu', and initialises it to hold no menu
+items.
+
+#5.2.2. preset_menu_add_submenu()
+
+  struct preset_menu *preset_menu_add_submenu
+      (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 `struct preset_menu' describing the
+submenu.
+
+The string parameter `title' must be dynamically allocated by the
+caller. The preset-menu structure will take ownership of it, so the
+caller must not free it.
+
+#5.2.3. preset_menu_add_preset()
+
+  void preset_menu_add_preset
+      (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 `title' and the game parameter structure
+`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.
+
+#5.2.4. preset_menu_lookup_by_id()
+
+  game_params *preset_menu_lookup_by_id
+      (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 `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.
+
+#5.3. 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 NULL returns from
+allocation.
+
+#5.3.1. snew()
+
+  var = snew(type);
+
+This macro takes a single argument which is a _type name_. It allocates
+space for one object of that type. If allocation fails it will call
+fatal() and not return; so if it does return, you can be confident that
+its return value is non-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!).
+
+#5.3.2. snewn()
+
+  var = snewn(n, type);
+
+This macro is the array form of 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-NULL
+pointer just as snew() does.
+
+#5.3.3. sresize()
+
+  var = sresize(var, n, type);
+
+This macro is a type-checked form of 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-NULL pointer,
+like snew() and snewn().
+
+The input memory block can be NULL, in which case this function will
+behave exactly like snewn(). (In principle any ANSI-compliant realloc()
+implementation ought to cope with this, but I've never quite trusted it
+to work everywhere.)
+
+#5.3.4. sfree()
+
+  void sfree(void *p);
+
+This function is pretty much equivalent to free(). It is provided with a
+dynamically allocated block, and frees it.
+
+The input memory block can be NULL, in which case this function will do
+nothing. (In principle any ANSI-compliant free() implementation ought to
+cope with this, but I've never quite trusted it to work everywhere.)
+
+#5.3.5. dupstr()
+
+  char *dupstr(const char *s);
+
+This function dynamically allocates a duplicate of a C string. Like the
+snew() functions, it guarantees to return non-NULL or not return at all.
+
+(Many platforms provide the function strdup(). As well as guaranteeing
+never to return NULL, my version has the advantage of being defined
+_everywhere_, rather than inconveniently not quite everywhere.)
+
+#5.3.6. free_cfg()
+
+  void free_cfg(config_item *cfg);
+
+This function correctly frees an array of `config_item's, including
+walking the array until it gets to the end and freeing any subsidiary
+data items in each `u' sub-union which are expected to be dynamically
+allocated.
+
+(See section 2.3.9 for details of the `config_item' structure.)
+
+#5.4. 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 O(log N) time.)
+
+All these functions expect you to be storing a tree of `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
+`maps' (associative arrays), by defining each element of a tree to be a
+(key, value) pair.
+
+#5.4.1. newtree234()
+
+  tree234 *newtree234(cmpfn234 cmp);
+
+Creates a new empty tree, and returns a pointer to it.
+
+The parameter `cmp' determines the sorting criterion on the tree. Its
+prototype is
+
+  typedef int (*cmpfn234)(void *, void *);
+
+If you want a sorted tree, you should provide a function matching this
+prototype, which returns like 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 addpos234() will not be
+usable on your tree (because all insertions must respect the sorting
+order).
+
+If you want an unsorted tree, pass NULL. In this case you will not be
+able to use either add234() or del234(), or any other function such
+as 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.
+
+#5.4.2. freetree234()
+
+  void freetree234(tree234 *t);
+
+Frees a tree. This function will not free the _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 freetree234(), by means
+of code along the lines of
+
+  while ((element = delpos234(tree, 0)) != NULL)
+      sfree(element); /* or some more complicated free function */
+
+#5.4.3. add234()
+
+  void *add234(tree234 *t, void *e);
+
+Inserts a new element `e' into the tree `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 `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 `e' is returned.
+
+#5.4.4. addpos234()
+
+  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 `index' to zero puts the new element right at the
+start of the list; setting `index' to the current number of elements in
+the tree puts the new element at the end.
+
+Return value is `e', in line with 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).
+
+#5.4.5. index234()
+
+  void *index234(tree234 *t, int index);
+
+Returns a pointer to the `index'th element of the tree, or NULL if
+`index' is out of range. Elements of the tree are numbered from zero.
+
+#5.4.6. find234()
+
+  void *find234(tree234 *t, void *e, cmpfn234 cmp);
+
+Searches for an element comparing equal to `e' in a sorted tree.
+
+If `cmp' is 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
+`char *' name field, and you want to find the element with a given name.
+You _could_ achieve this by constructing a fake element structure,
+setting its name field appropriately, and passing it to find234(),
+but you might find it more convenient to pass _just_ a name string to
+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 `cmp' is not NULL, then it will be used to compare `e' to
+elements of the tree. The first argument passed to `cmp' will always be
+`e'; the second will be an element of the tree.
+
+(See section 5.4.1 for the definition of the `cmpfn234' function pointer
+type.)
+
+The returned value is the element found, or NULL if the search is
+unsuccessful.
+
+#5.4.7. findrel234()
+
+  void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);
+
+This function is like find234(), but has the additional ability to do a
+_relative_ search. The additional parameter `relation' can be one of the
+following values:
+
+REL234_EQ
+
+    Find only an element that compares equal to `e'. This is exactly the
+    behaviour of find234().
+
+REL234_LT
+
+    Find the greatest element that compares strictly less than `e'. `e'
+    may be NULL, in which case it finds the greatest element in the
+    whole tree (which could also be done by index234(t, count234(t)-1)).
+
+REL234_LE
+
+    Find the greatest element that compares less than or equal to `e'.
+    (That is, find an element that compares equal to `e' if possible,
+    but failing that settle for something just less than it.)
+
+REL234_GT
+
+    Find the smallest element that compares strictly greater than `e'.
+    `e' may be NULL, in which case it finds the smallest element in the
+    whole tree (which could also be done by index234(t, 0)).
+
+REL234_GE
+
+    Find the smallest element that compares greater than or equal
+    to `e'. (That is, find an element that compares equal to `e' if
+    possible, but failing that settle for something just bigger than
+    it.)
+
+Return value, as before, is the element found or NULL if no element
+satisfied the search criterion.
+
+#5.4.8. findpos234()
+
+  void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);
+
+This function is like find234(), but has the additional feature of
+returning the index of the element found in the tree; that index is
+written to `*index' in the event of a successful search (a non-NULL
+return value).
+
+`index' may be NULL, in which case this function behaves exactly like
+find234().
+
+#5.4.9. findrelpos234()
+
+  void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
+                      int *index);
+
+This function combines all the features of findrel234() and
+findpos234().
+
+#5.4.10. del234()
+
+  void *del234(tree234 *t, void *e);
+
+Finds an element comparing equal to `e' in the tree, deletes it, and
+returns it.
+
+The input tree must be sorted.
+
+The element found might be `e' itself, or might merely compare equal to
+it.
+
+Return value is NULL if no such element is found.
+
+#5.4.11. delpos234()
+
+  void *delpos234(tree234 *t, int index);
+
+Deletes the element at position `index' in the tree, and returns it.
+
+Return value is NULL if the index is out of range.
+
+#5.4.12. count234()
+
+  int count234(tree234 *t);
+
+Returns the number of elements currently in the tree.
+
+#5.4.13. splitpos234()
+
+  tree234 *splitpos234(tree234 *t, int index, int 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 `before' is TRUE, then all the items at or after position `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
+`index' are moved into the new tree, and those before that point are
+left in the old one.
+
+If `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 `index' is further out of range in either direction, the
+operation will fail completely and return NULL.
+
+This operation completes in O(log N) time, no matter how large the tree
+or how balanced or unbalanced the split.
+
+#5.4.14. split234()
+
+  tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);
+
+Splits a sorted tree according to its sort order.
+
+`rel' can be any of the relation constants described in section 5.4.7,
+_except_ for REL234_EQ. All the elements having that relation to `e'
+will be transferred into the new tree; the rest will be left in the old
+one.
+
+The parameter `cmp' has the same semantics as it does in find234(): if
+it is not NULL, it will be used in place of the tree's own comparison
+function when comparing elements to `e', in such a way that `e' itself
+is always the first of its two operands.
+
+Again, this operation completes in O(log N) time, no matter how large
+the tree or how balanced or unbalanced the split.
+
+#5.4.15. join234()
+
+  tree234 *join234(tree234 *t1, tree234 *t2);
+
+Joins two trees together by concatenating the lists they represent. All
+the elements of `t2' are moved into `t1', in such a way that they appear
+_after_ the elements of `t1'. The tree `t2' is freed; the return value
+is `t1'.
+
+If you apply this function to a sorted tree and it violates the sort
+order (i.e. the smallest element in `t2' is smaller than or equal to the
+largest element in `t1'), the operation will fail and return NULL.
+
+This operation completes in O(log N) time, no matter how large the trees
+being joined together.
+
+#5.4.16. join234r()
+
+  tree234 *join234r(tree234 *t1, tree234 *t2);
+
+Joins two trees together in exactly the same way as join234(), but this
+time the combined tree is returned in `t2', and `t1' is destroyed. The
+elements in `t1' still appear before those in `t2'.
+
+Again, this operation completes in O(log N) time, no matter how large
+the trees being joined together.
+
+#5.4.17. copytree234()
+
+  tree234 *copytree234(tree234 *t, copyfn234 copyfn,
+                       void *copyfnstate);
+
+Makes a copy of an entire tree.
+
+If `copyfn' is 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 `copyfn' which makes a copy of each element.
+That function has the prototype
+
+  typedef void *(*copyfn234)(void *state, void *element);
+
+and every time it is called, the `state' parameter will be set to the
+value you passed in as `copyfnstate'.
+
+#5.5. Miscellaneous utility functions and macros
+
+This section contains all the utility functions which didn't sensibly
+fit anywhere else.
+
+#5.5.1. TRUE and FALSE
+
+The main Puzzles header file defines the macros TRUE and FALSE, which
+are used throughout the code in place of 1 and 0 (respectively) to
+indicate that the values are in a boolean context. For code base
+consistency, I'd prefer it if submissions of new code followed this
+convention as well.
+
+#5.5.2. max() and min()
+
+The main Puzzles header file defines the pretty standard macros max()
+and 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.
+
+#5.5.3. PI
+
+The main Puzzles header file defines a macro PI which expands to a
+floating-point constant representing pi.
+
+(I've never understood why ANSI's <math.h> doesn't define this. It'd be
+so useful!)
+
+#5.5.4. obfuscate_bitmap()
+
+  void obfuscate_bitmap(unsigned char *bmp, int bits, int 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
+_accidentally_ spoiling their own fun.
+
+The input argument `bmp' points at a piece of memory to be obfuscated.
+`bits' gives the length of the data. Note that that length is in _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 `bits' to 10 will cover the whole
+of bmp[0] and the _top two_ bits of bmp[1]. The remainder of a partially
+used byte is undefined (i.e. it may be corrupted by the function).
+
+The parameter `decode' is FALSE for an encoding operation, and 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.
+
+#5.5.5. bin2hex()
+
+  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 obfuscate_bitmap() in
+printable ASCII for use in game IDs.
+
+#5.5.6. hex2bin()
+
+  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 `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 bin2hex().
+
+#5.5.7. game_mkhighlight()
+
+  void game_mkhighlight(frontend *fe, float *ret,
+                        int background, int highlight, int lowlight);
+
+It's reasonably common for a puzzle game's graphics to use highlights
+and lowlights to indicate `raised' or `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 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
+colours() routine (section 2.8.6). You pass it your front end handle, a
+pointer to the start of your return array, and three colour indices. It
+will:
+
+ -  call frontend_default_colour() (section 4.39) to fetch the front
+    end's default background colour
+
+ -  alter the brightness of that colour if it's unsuitable
+
+ -  define brighter and darker variants of the colour to be used as
+    highlights and lowlights
+
+ -  write those results into the relevant positions in the `ret' array.
+
+Thus, ret[background*3] to ret[background*3+2] will be set to RGB values
+defining a sensible background colour, and similary `highlight' and
+`lowlight' will be set to sensible colours.
+
+#6. 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.
+
+#6.1. 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 _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 _fair_.
+A fair game is one which a player can only fail to complete through
+demonstrable lack of skill - that is, such that a better player in the
+same situation would have _known_ to do something different.
+
+For a start, that means every game presented to the user must have _at
+least one solution_. Giving the unsuspecting user a puzzle which is
+actually impossible is not acceptable. (There is an exception: if the
+user has selected some non-default option which is clearly labelled as
+potentially unfair, _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.)
+
+Also, this actually _rules out_ games such as Klondike, or the normal
+form of Mahjong Solitaire. Those games have the property that even if
+there is a solution (i.e. some sequence of moves which will get from
+the start state to the solved state), the player doesn't necessarily
+have enough information to _find_ that solution. In both games, it is
+possible to reach a dead end because you had an arbitrary choice to make
+and made it the wrong way. This violates the fairness criterion, because
+a better player couldn't have known they needed to make the other
+choice.
+
+(GNOME has a variant on Mahjong Solitaire which makes it fair: there
+is a Shuffle operation which randomly permutes all the remaining tiles
+without changing their positions, which allows you to get out of a
+sticky situation. Using this operation adds a 60-second penalty to your
+solution time, so it's to the player's advantage to try to minimise
+the chance of having to use it. It's still possible to render the game
+uncompletable if you end up with only two tiles vertically stacked,
+but that's easy to foresee and avoid using a shuffle operation. This
+form of the game _is_ fair. Implementing it in Puzzles would require
+an infrastructure change so that the back end could communicate time
+penalties to the mid-end, but that would be easy enough.)
+
+Providing a _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 _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 _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 _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 _in theory_ to find that solution without having to guess.
+
+#6.2. Getting started
+
+The simplest way to start writing a new puzzle is to copy `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 `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 Makefiles, in order to
+compile it conveniently. _Do not edit the Makefiles_: they are created
+automatically by the script `mkfiles.pl', from the file called `Recipe'.
+Edit `Recipe', and then re-run `mkfiles.pl'.
+
+Also, don't forget to add your puzzle to `list.c': if you don't, then it
+will still run fine on platforms which build each puzzle separately, but
+Mac OS X and other monolithic platforms will not include your new puzzle
+in their single binary.
+
+Once your source file is building, you can move on to the fun bit.
+
+#6.2.1. 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 _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 `nullgame.c', and start adding code to
+new_game_desc() which tries to generate a puzzle instance and print it
+out using printf(). Once that's working, _then_ I start connecting it up
+to the return value of new_game_desc(), populating other structures like
+`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 _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: _every_ possible
+arrangement of the blue squares and the cube's starting position is
+soluble!
+
+Another option is to redefine what you mean by `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 _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 _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 _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 - you have to find a way to fill the grid up _completely_.
+
+The other way to generate a puzzle that's soluble is to start from the
+other end, and actually write a _solver_. This tends to ensure that a
+puzzle has a _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 _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 _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 _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 _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 (`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 _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 _cannot_ fail - 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
+_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 _at least_ a given level of difficulty is rather harder; if
+you go for _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 _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 _before_ it's
+placed any of the numbers - 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 _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 _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 _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 _not_
+to test it initially on a grid that's square (i.e. w==h), because if the
+grid is square then you won't notice if you mistakenly write `h' instead
+of `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.
+
+#6.2.2. 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 `x' to
+specify the grid dimensions (`10x10' or `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 decode_params() can handle
+the suffixes appearing in any order, even if 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.
+
+#6.3. 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.
+
+#6.3.1. Drawing objects at only one position
+
+A common phenomenon is to have an object described in the `game_state'
+or the `game_ui' which can only be at one position. A cursor - probably
+specified in the `game_ui' - is a good example.
+
+In the `game_ui', it would _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 `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
+`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 _is_ probably the right thing to have a cursor flag
+for every position in the grid. You probably have an array for the whole
+grid in the drawstate already (stating what is currently displayed in
+the window at each position); the sensible approach is to add a `cursor'
+flag to each element of that array. Then the main redraw loop will look
+something like this (pseudo-code):
+
+  for (y = 0; y < h; y++) {
+      for (x = 0; x < w; x++) {
+          int value = state->symbol_at_position[y][x];
+          if (x == ui->cursor_x && y == ui->cursor_y)
+              value |= CURSOR;
+          if (ds->symbol_at_position[y][x] != value) {
+              symbol_drawing_subroutine(dr, ds, x, y, value);
+              ds->symbol_at_position[y][x] = value;
+          }
+      }
+  }
+
+This loop is very simple, pretty hard to get wrong, and _automatically_
+deals both with erasing the previous cursor and drawing the new one,
+with no special case code required.
+
+This type of loop is generally a sensible way to write a redraw
+function, in fact. The best thing is to ensure that the information
+stored in the draw state for each position tells you _everything_ about
+what was drawn there. A good way to ensure that is to pass precisely
+the same information, and _only_ that information, to a subroutine that
+does the actual drawing; then you know there's no additional information
+which affects the drawing but which you don't notice changes in.
+
+#6.3.2. 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 `game_ui' (since if it were in the
+`game_state' then the user would have to separately undo every cursor
+move operation). So the procedure would be:
+
+ -  Put cursor position fields in the `game_ui'.
+
+ -  interpret_move() responds to arrow keys by modifying the cursor
+    position fields and returning "".
+
+ -  interpret_move() responds to some sort of fire button by actually
+    performing a move based on the current cursor location.
+
+ -  You might want an additional `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).
+
+ -  You might also want to automatically hide the cursor in
+    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).
+
+ -  redraw() draws the cursor using the technique described in section
+    6.3.1.
+
+#6.3.3. 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
+section 3.1.13 for the blitter API) to save the background underneath
+it. The typical scenario goes:
+
+ -  Have a blitter field in the `game_drawstate'.
+
+ -  Set the blitter field to NULL in the game's new_drawstate()
+    function, since you don't yet know how big the piece of saved
+    background needs to be.
+
+ -  In the game's 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.
+
+ -  In free_drawstate(), free the blitter if it's not NULL.
+
+ -  In interpret_move(), respond to mouse-down and mouse-drag events by
+    updating some fields in the game_ui which indicate that a drag is in
+    progress.
+
+ -  At the _very end_ of 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 unclip().
+    Finally, set a flag in the game_drawstate that indicates that the
+    blitter needs restoring.
+
+ -  At the very start of redraw(), before doing anything else at all,
+    check the flag in the 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.
+
+#6.3.4. 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 _could_ dynamically allocate a copy of that array in every
+`game_state', and have dup_game() make a fresh copy of it for every new
+`game_state'; but it would waste memory and time. A more efficient way
+is to use a reference-counted structure.
+
+ -  Define a structure type containing the data in question, and also
+    containing an integer reference count.
+
+ -  Have a field in `game_state' which is a pointer to this structure.
+
+ -  In 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.
+
+ -  In 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.
+
+ -  In 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; _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.)
+
+#6.3.5. 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:
+
+ -  Have a field in the `game_ui' which describes the type of flash.
+
+ -  In 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 `game_ui' field whenever you return non-zero.
+
+ -  In redraw(), when you detect that `flash_time' is non-zero, examine
+    the field in `game_ui' to decide which type of flash to draw.
+
+redraw() will never be called with `flash_time' non-zero unless
+flash_length() was first called to tell the mid-end that a flash was
+required; so whenever redraw() notices that `flash_time' is non-zero,
+you can be sure that the field in `game_ui' is correctly set.
+
+#6.3.6. 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
+redraw() is called with `oldstate' non-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.
+
+ -  Add a `last move' field to the `game_state' (or two or more fields
+    if the move is complex enough to need them).
+
+ -  new_game() initialises this field to a null value for a new game
+    state.
+
+ -  execute_move() sets up the field to reflect the move it just
+    performed.
+
+ -  redraw() now needs to examine its `dir' parameter. If `dir' is
+    positive, it determines the move being animated by looking at the
+    last-move field in `newstate'; but if `dir' is negative, it has to
+    look at the last-move field in `oldstate', and invert whatever move
+    it finds there.
+
+Note also that Sixteen needs to store the _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 _another_ move to the right.)
+
+#6.3.7. 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 `game_ui' which inhibits
+move animation, and to set that flag in interpret_move(). The question
+is, when would the flag be reset again? The obvious place to do so
+is changed_state(), which will be called once per move. But it will
+be called _before_ anim_length(), so if it resets the flag then
+anim_length() will never see the flag set at all.
+
+The solution is to have _two_ flags in a queue.
+
+ -  Define two flags in `game_ui'; let's call them `current' and `next'.
+
+ -  Set both to FALSE in `new_ui()'.
+
+ -  When a drag operation completes in interpret_move(), set the `next'
+    flag to TRUE.
+
+ -  Every time changed_state() is called, set the value of `current' to
+    the value in `next', and then set the value of `next' to FALSE.
+
+ -  That way, `current' will be TRUE _after_ a call to changed_state()
+    if and only if that call to changed_state() was the result of a
+    drag operation processed by interpret_move(). Any other call to
+    changed_state(), due to an Undo or a Redo or a Restart or a Solve,
+    will leave `current' FALSE.
+
+ -  So now anim_length() can request a move animation if and only if the
+    `current' flag is _not_ set.
+
+#6.3.8. 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:
+
+ -  Add a `cheated' flag to the `game_state'.
+
+ -  Set this flag to FALSE in new_game().
+
+ -  Have solve() return a move description string which clearly
+    identifies the move as a solve operation.
+
+ -  Have execute_move() respond to that clear identification by setting
+    the `cheated' flag in the returned `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.
+
+ -  flash_length() now returns non-zero if `oldstate' is not completed
+    and `newstate' is, _and_ neither state has the `cheated' flag set.
+
+#6.4. 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 _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
+make_move() function performing the jobs of both interpret_move() and
+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 - which would have meant you'd
+have to test game saving _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
+`game_ui'. Most games do not store anything permanent in the `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.
+