puzzles: resync with upstream

This brings the source to upstream commit 506b073 (though I have made some
extra commits on top of that). Notably this includes a fix for a double-free
bug that I myself introduced upstream.

Change-Id: I02671586bbc34d63e05398ee971271fed42538cf

1 files changed, 0 insertions, 4661 deletions

diff --git a/apps/plugins/puzzles/src/HACKING b/apps/plugins/puzzles/src/HACKING
deleted file mode 100644
index e877280..0000000
--- a/apps/plugins/puzzles/src/HACKING
+++ /dev/null
@@ -1,4661 +0,0 @@
-#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.
-