1 files changed, 0 insertions, 5061 deletions
diff --git a/apps/plugins/puzzles/src/devel.but b/apps/plugins/puzzles/src/devel.but
deleted file mode 100644
index 7521596df9..0000000000
--- a/apps/plugins/puzzles/src/devel.but
+++ /dev/null
@@ -1,5061 +0,0 @@
-\cfg{text-indent}{0}
-\cfg{text-width}{72}
-\cfg{text-title-align}{left}
-\cfg{text-chapter-align}{left}
-\cfg{text-chapter-numeric}{true}
-\cfg{text-chapter-suffix}{. }
-\cfg{text-chapter-underline}{-}
-\cfg{text-section-align}{0}{left}
-\cfg{text-section-numeric}{0}{true}
-\cfg{text-section-suffix}{0}{. }
-\cfg{text-section-underline}{0}{-}
-\cfg{text-section-align}{1}{left}
-\cfg{text-section-numeric}{1}{true}
-\cfg{text-section-suffix}{1}{. }
-\cfg{text-section-underline}{1}{-}
-\cfg{text-versionid}{0}
-\cfg{html-contents-filename}{index.html}
-\cfg{html-template-filename}{%k.html}
-\cfg{html-index-filename}{docindex.html}
-\cfg{html-leaf-level}{1}
-\cfg{html-contents-depth-0}{1}
-\cfg{html-contents-depth-1}{3}
-\cfg{html-leaf-contains-contents}{true}
-\define{dash} \u2013{-}
-\title Developer documentation for Simon Tatham's puzzle collection
-This is a guide to the internal structure of Simon Tatham's Portable
-Puzzle Collection (henceforth referred to simply as \q{Puzzles}),
-for use by anyone attempting to implement a new puzzle or port to a
-new platform.
-This guide is believed correct as of 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.
-\C{intro} Introduction
-The Puzzles code base is divided into four parts: a set of
-interchangeable front ends, a set of interchangeable back ends, a
-universal \q{middle end} which acts as a buffer between the two, and
-a bunch of miscellaneous utility functions. In the following
-sections I give some general discussion of each of these parts.
-\H{intro-frontend} Front end
-The front end is the non-portable part of the code: it's the bit
-that you replace completely when you port to a different platform.
-So it's responsible for all system calls, all GUI interaction, and
-anything else platform-specific.
-The 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 \cw{main()} or the local platform's
-equivalent. Top-level control over the application's execution flow
-belongs to the front end (it isn't, for example, a set of functions
-called by a universal \cw{main()} somewhere else).
-The front end has complete freedom to design the GUI for any given
-port of Puzzles. There is no centralised mechanism for maintaining
-the menu layout, for example. This has a cost in consistency (when I
-\e{do} want the same menu layout on more than one platform, I have
-to edit 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 \k{drawing}; the other miscellaneous front end
-API functions are documented in \k{frontend-api}.
-\H{intro-backend} Back end
-A \q{back end}, in this collection, is synonymous with a \q{puzzle}.
-Each back end implements a different game.
-At the top level, a back end is simply a data structure, containing
-a few constants (flag words, preferred pixel size) and a large
-number of function pointers. Back ends are almost invariably callee
-rather than caller, which means there's a limitation on what a back
-end can do on its own initiative.
-The persistent state in a back end is divided into a number of data
-structures, which are used for different purposes and therefore
-likely to be switched around, changed without notice, and otherwise
-updated by the rest of the code. It is important when designing a
-back end to put the right pieces of data into the right structures,
-or standard midend-provided features (such as Undo) may fail to
-work.
-The functions and variables provided in the back end data structure
-are documented in \k{backend}.
-\H{intro-midend} Middle end
-Puzzles has a single and universal \q{middle end}. This code is
-common to all platforms and all games; it sits in between the front
-end and the back end and provides standard functionality everywhere.
-People adding new back ends or new front ends should generally not
-need to edit the middle end. On rare occasions there might be a
-change that can be made to the middle end to permit a new game to do
-something not currently anticipated by the middle end's present
-design; however, this is terribly easy to get wrong and should
-probably not be undertaken without consulting the primary maintainer
-(me). Patch submissions containing unannounced mid-end changes will
-be treated on their merits like any other patch; this is just a
-friendly warning that mid-end changes will need quite a lot of
-merits to make them acceptable.
-Functionality provided by the mid-end includes:
-\b Maintaining a list of game state structures and moving back and
-forth along that list to provide Undo and Redo.
-\b Handling timers (for move animations, flashes on completion, and
-in some cases actually timing the game).
-\b Handling the container format of game IDs: receiving them,
-picking them apart into parameters, description and/or random seed,
-and so on. The game back end need only handle the individual parts
-of a game ID (encoded parameters and encoded game description);
-everything else is handled centrally by the mid-end.
-\b Handling standard keystrokes and menu commands, such as \q{New
-Game}, \q{Restart Game} and \q{Quit}.
-\b Pre-processing mouse events so that the game back ends can rely
-on them arriving in a sensible order (no missing button-release
-events, no sudden changes of which button is currently pressed,
-etc).
-\b Handling the dialog boxes which ask the user for a game ID.
-\b Handling serialisation of entire games (for loading and saving a
-half-finished game to a disk file, 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 \k{midend}.
-\H{intro-utils} Miscellaneous utilities
-In addition to these three major structural components, the Puzzles
-code also contains a variety of utility modules usable by all of the
-above components. There is a set of functions to provide
-platform-independent random number generation; functions to make
-memory allocation easier; functions which implement a balanced tree
-structure to be used as necessary in complex algorithms; and a few
-other miscellaneous functions. All of these are documented in
-\k{utils}.
-\H{intro-structure} Structure of this guide
-There are a number of function call interfaces within Puzzles, and
-this guide will discuss each one in a chapter of its own. After
-that, \k{writing} discusses how to design new games, with some
-general design thoughts and tips.
-\C{backend} Interface to the back end
-This chapter gives a detailed discussion of the interface that each
-back end must implement.
-At the top level, each back end source file exports a single global
-symbol, which is a \c{const struct game} containing a large number
-of function pointers and a small amount of constant data. This
-structure is called by different names depending on what kind of
-platform the puzzle set is being compiled on:
-\b On platforms such as Windows and GTK, which build a separate
-binary for each puzzle, the game structure in every back end has the
-same name, \cq{thegame}; the front end refers directly to this name,
-so that compiling the same front end module against a different back
-end module builds a different puzzle.
-\b On platforms such as MacOS X and PalmOS, which build all the
-puzzles into a single monolithic binary, the game structure in each
-back end must have a different name, and there's a helper module
-\c{list.c} (constructed automatically by the same Perl script that
-builds the \cw{Makefile}s) which contains a complete list of those
-game structures.
-On the latter type of platform, source files may assume that the
-preprocessor symbol \c{COMBINED} has been defined. Thus, the usual
-code to declare the game structure looks something like this:
-\c #ifdef COMBINED
-\c #define thegame net    /* or whatever this game is called */
-\e                 iii    iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
-\c #endif
-\c 
-\c const struct game thegame = {
-\c     /* lots of structure initialisation in here */
-\e     iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
-\c };
-Game back ends must also internally define a number of data
-structures, for storing their various persistent state. This chapter
-will first discuss the nature and use of those structures, and then
-go on to give details of every element of the game structure.
-\H{backend-structs} Data structures
-Each game is required to define four separate data structures. This
-section discusses each one and suggests what sorts of things need to
-be put in it.
-\S{backend-game-params} \c{game_params}
-The \c{game_params} structure contains anything which affects the
-automatic generation of new puzzles. So if puzzle generation is
-parametrised in any way, those parameters need to be stored in
-\c{game_params}.
-Most puzzles currently in this collection are played on a grid of
-squares, meaning that the most obvious parameter is the grid size.
-Many puzzles have additional parameters; for example, Mines allows
-you to control the number of mines in the grid independently of its
-size, Net can be wrapping or non-wrapping, Solo has difficulty
-levels and symmetry settings, and so on.
-A simple rule for deciding whether a data item needs to go in
-\c{game_params} is: would the user expect to be able to control this
-data item from either the preset-game-types menu or the \q{Custom}
-game type configuration? If so, it's part of \c{game_params}.
-\c{game_params} structures are permitted to contain pointers to
-subsidiary data if they need to. The back end is required to provide
-functions to create and destroy \c{game_params}, and those functions
-can allocate and free additional memory if necessary. (It has not
-yet been necessary to do this in any puzzle so far, but the
-capability is there just in case.)
-\c{game_params} is also the only structure which the game's
-\cw{compute_size()} function may refer to; this means that any
-aspect of the game which affects the size of the window it needs to
-be drawn in must be stored in \c{game_params}. In particular, this
-imposes the fundamental limitation that random game generation may
-not have a random effect on the window size: game generation
-algorithms are constrained to work by starting from the grid size
-rather than generating it as an emergent phenomenon. (Although this
-is a restriction in theory, it has not yet seemed to be a problem.)
-\S{backend-game-state} \c{game_state}
-While the user is actually playing a puzzle, the \c{game_state}
-structure stores all the data corresponding to the current state of
-play.
-The mid-end keeps \c{game_state}s in a list, and adds to the list
-every time the player makes a move; the Undo and Redo functions step
-back and forth through that list.
-Therefore, a good means of deciding whether a data item needs to go
-in \c{game_state} is: would a player expect that data item to be
-restored on undo? If so, put it in \c{game_state}, and this will
-automatically happen without you having to lift a finger. If not
-\dash for example, the deaths counter in Mines is precisely
-something that does \e{not} want to be reset to its previous state
-on an undo \dash then you might have found a data item that needs to
-go in \c{game_ui} instead.
-During play, \c{game_state}s are often passed around without an
-accompanying \c{game_params} structure. Therefore, any information
-in \c{game_params} which is important during play (such as the grid
-size) must be duplicated within the \c{game_state}. One simple
-method of doing this is to have the \c{game_state} structure
-\e{contain} a \c{game_params} structure as one of its members,
-although this isn't obligatory if you prefer to do it another way.
-\S{backend-game-drawstate} \c{game_drawstate}
-\c{game_drawstate} carries persistent state relating to the current
-graphical contents of the puzzle window. The same \c{game_drawstate}
-is passed to every call to the game redraw function, so that it can
-remember what it has already drawn and what needs redrawing.
-A typical use for a \c{game_drawstate} is to have an array mirroring
-the array of grid squares in the \c{game_state}; then every time the
-redraw function was passed a \c{game_state}, it would loop over all
-the squares, and physically redraw any whose description in the
-\c{game_state} (i.e. what the square needs to look like when the
-redraw is completed) did not match its description in the
-\c{game_drawstate} (i.e. what the square currently looks like).
-\c{game_drawstate} is occasionally completely torn down and
-reconstructed by the mid-end, if the user somehow forces a full
-redraw. Therefore, no data should be stored in \c{game_drawstate}
-which is \e{not} related to the state of the puzzle window, because
-it might be unexpectedly destroyed.
-The back end provides functions to create and destroy
-\c{game_drawstate}, which means it can contain pointers to
-subsidiary allocated data if it needs to. A common thing to want to
-allocate in a \c{game_drawstate} is a \c{blitter}; see
-\k{drawing-blitter} for more on this subject.
-\S{backend-game-ui} \c{game_ui}
-\c{game_ui} contains whatever doesn't fit into the above three
-structures!
-A new \c{game_ui} is created when the user begins playing a new
-instance of a puzzle (i.e. during \q{New Game} or after entering a
-game ID etc). It persists until the user finishes playing that game
-and begins another one (or closes the window); in particular,
-\q{Restart Game} does \e{not} destroy the \c{game_ui}.
-\c{game_ui} is useful for implementing user-interface state which is
-not part of \c{game_state}. Common examples are keyboard control
-(you wouldn't want to have to separately Undo through every cursor
-motion) and mouse dragging. See \k{writing-keyboard-cursor} and
-\k{writing-howto-dragging}, respectively, for more details.
-Another use for \c{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 \e{not important enough} to
-preserve for the player to restore by Undo, the Mines death counter
-is \e{too important} to permit the player to revert by Undo!
-A final use for \c{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 \q{flash} should
-be a white flash for victory or a red flash for defeat; see
-\k{writing-flash-types}.
-\H{backend-simple} Simple data in the back end
-In this section I begin to discuss each individual element in the
-back end structure. To begin with, here are some simple
-self-contained data elements.
-\S{backend-name} \c{name}
-\c const char *name;
-This is a simple ASCII string giving the name of the puzzle. This
-name will be used in window titles, in game selection menus on
-monolithic platforms, and anywhere else that the front end needs to
-know the name of a game.
-\S{backend-winhelp} \c{winhelp_topic}
-\c 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
-\q{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 \c{puzzles.but} is labelled with a
-\e{help topic} name, similar to this:
-\c \cfg{winhelp-topic}{games.net}
-And then the corresponding game back end encodes the topic string
-(here \cq{games.net}) in the \c{winhelp_topic} element of the game
-structure.
-\H{backend-params} Handling game parameter sets
-In this section I present the various functions which handle the
-\c{game_params} structure.
-\S{backend-default-params} \cw{default_params()}
-\c game_params *(*default_params)(void);
-This function allocates a new \c{game_params} structure, fills it
-with the default values, and returns a pointer to it.
-\S{backend-fetch-preset} \cw{fetch_preset()}
-\c bool (*fetch_preset)(int i, char **name, game_params **params);
-This function is one of the two APIs a back end can provide to
-populate the \q{Type} menu, which provides a list of conveniently
-accessible preset parameters for most games.
-The function is called with \c{i} equal to the index of the preset
-required (numbering from zero). It returns \cw{false} if that preset
-does not exist (if \c{i} is less than zero or greater than the
-largest preset index). Otherwise, it sets \c{*params} to point at a
-newly allocated \c{game_params} structure containing the preset
-information, sets \c{*name} to point at a newly allocated C string
-containing the preset title (to go on the \q{Type} menu), and
-returns \cw{true}.
-If the game does not wish to support any presets at all, this
-function is permitted to return \cw{false} always.
-If the game wants to return presets in the form of a hierarchical menu
-instead of a flat list (and, indeed, even if it doesn't), then it may
-set this function pointer to \cw{NULL}, and instead fill in the
-alternative function pointer \cw{preset_menu}
-(\k{backend-preset-menu}).
-\S{backend-preset-menu} \cw{preset_menu()}
-\c struct preset_menu *(*preset_menu)(void);
-This function is the more flexible of the two APIs by which a back end
-can define a collection of preset game parameters.
-This function simply returns a complete menu hierarchy, in the form of
-a \c{struct preset_menu} (see \k{midend-get-presets}) and further
-submenus (if it wishes) dangling off it. There are utility functions
-described in \k{utils-presets} to make it easy for the back end to
-construct this menu.
-If the game has no need to return a hierarchy of menus, it may instead
-opt to implement the \cw{fetch_preset()} function (see
-\k{backend-fetch-preset}).
-The game need not fill in the \c{id} fields in the preset menu
-structures. The mid-end will do that after it receives the structure
-from the game, and before passing it on to the front end.
-\S{backend-encode-params} \cw{encode_params()}
-\c char *(*encode_params)(const game_params *params, bool full);
-The job of this function is to take a \c{game_params}, and encode it
-in a string form for use in game IDs. The return value must be a
-newly allocated C string, and \e{must} not contain a colon or a hash
-(since those characters are used to mark the end of the parameter
-section in a game ID).
-Ideally, it should also not contain any other potentially
-controversial punctuation; bear in mind when designing a string
-parameter format that it will probably be used on both Windows and
-Unix command lines under a variety of exciting shell quoting and
-metacharacter rules. Sticking entirely to alphanumerics is the
-safest thing; if you really need punctuation, you can probably get
-away with commas, periods or underscores without causing anybody any
-major inconvenience. If you venture far beyond that, you're likely
-to irritate \e{somebody}.
-(At the time of writing this, 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 \cq{x}.)
-If the \c{full} parameter is \cw{true}, this function should encode
-absolutely everything in the \c{game_params}, such that a subsequent
-call to \cw{decode_params()} (\k{backend-decode-params}) will yield
-an identical structure. If \c{full} is \cw{false}, however, you
-should leave out anything which is not necessary to describe a
-\e{specific puzzle instance}, i.e. anything which only takes effect
-when a new puzzle is \e{generated}. For example, the Solo
-\c{game_params} includes a difficulty rating used when constructing
-new puzzles; but a Solo game ID need not explicitly include the
-difficulty, since to describe a puzzle once generated it's
-sufficient to give the grid dimensions and the location and contents
-of the clue squares. (Indeed, one might very easily type in a puzzle
-out of a newspaper without \e{knowing} what its difficulty level is
-in Solo's terminology.) Therefore, Solo's \cw{encode_params()} only
-encodes the difficulty level if \c{full} is set.
-\S{backend-decode-params} \cw{decode_params()}
-\c void (*decode_params)(game_params *params, char const *string);
-This function is the inverse of \cw{encode_params()}
-(\k{backend-encode-params}). It parses the supplied string and fills
-in the supplied \c{game_params} structure. Note that the structure
-will \e{already} have been allocated: this function is not expected
-to create a \e{new} \c{game_params}, but to modify an existing one.
-This function can receive a string which only encodes a subset of
-the parameters. The most obvious way in which this can happen is if
-the string was constructed by \cw{encode_params()} with its \c{full}
-parameter set to \cw{FALSE}; however, it could also happen if the
-user typed in a parameter set manually and missed something out. Be
-prepared to deal with a wide range of possibilities.
-When dealing with a parameter which is not specified in the input
-string, what to do requires a judgment call on the part of the
-programmer. Sometimes it makes sense to adjust other parameters to
-bring them into line with the new ones. In Mines, for example, you
-would probably not want to keep the same mine count if the user
-dropped the grid size and didn't specify one, since you might easily
-end up with more mines than would actually fit in the grid! On the
-other hand, sometimes it makes sense to leave the parameter alone: a
-Solo player might reasonably expect to be able to configure size and
-difficulty independently of one another.
-This function currently has no direct means of returning an error if
-the string cannot be parsed at all. However, the returned
-\c{game_params} is almost always subsequently passed to
-\cw{validate_params()} (\k{backend-validate-params}), so if you
-really want to signal parse errors, you could always have a \c{char
-*} in your parameters structure which stored an error message, and
-have \cw{validate_params()} return it if it is non-\cw{NULL}.
-\S{backend-free-params} \cw{free_params()}
-\c void (*free_params)(game_params *params);
-This function frees a \c{game_params} structure, and any subsidiary
-allocations contained within it.
-\S{backend-dup-params} \cw{dup_params()}
-\c game_params *(*dup_params)(const game_params *params);
-This function allocates a new \c{game_params} structure and
-initialises it with an exact copy of the information in the one
-provided as input. It returns a pointer to the new duplicate.
-\S{backend-can-configure} \c{can_configure}
-\c bool can_configure;
-This data element is set to \cw{true} if the back end supports custom
-parameter configuration via a dialog box. If it is \cw{true}, then the
-functions \cw{configure()} and \cw{custom_params()} are expected to
-work. See \k{backend-configure} and \k{backend-custom-params} for more
-details.
-\S{backend-configure} \cw{configure()}
-\c config_item *(*configure)(const game_params *params);
-This function is called when the user requests a dialog box for
-custom parameter configuration. It returns a newly allocated array
-of \cw{config_item} structures, describing the GUI elements required
-in the dialog box. The array should have one more element than the
-number of controls, since it is terminated with a \cw{C_END} marker
-(see below). Each array element describes the control together with
-its initial value; the front end will modify the value fields and
-return the updated array to \cw{custom_params()} (see
-\k{backend-custom-params}).
-The \cw{config_item} structure contains the following elements:
-\c char *name;
-\c int type;
-\c union { /* type-specific fields */ } u;
-\e         iiiiiiiiiiiiiiiiiiiiiiiiii
-\c{name} is an ASCII string giving the textual label for a GUI
-control. It is \e{not} expected to be dynamically allocated.
-\c{type} contains one of a small number of \c{enum} values defining
-what type of control is being described. The usable member of the
-union field \c{u} depends on \c{type}. The valid type values are:
-\dt \c{C_STRING}
-\dd Describes a text input box. (This is also used for numeric
-input. The back end does not bother informing the front end that the
-box is numeric rather than textual; some front ends do have the
-capacity to take this into account, but I decided it wasn't worth
-the extra complexity in the interface.)
-\lcont{
-For controls of this type, \c{u.string} contains a single field
-\c char *sval;
-which stores a dynamically allocated string representing the contents
-of the input box.
-}
-\dt \c{C_BOOLEAN}
-\dd Describes a simple checkbox.
-\lcont{
-For controls of this type, \c{u.boolean} contains a single field
-\c int bval;
-which is either \cw{TRUE} or \cw{FALSE}.
-}
-\dt \c{C_CHOICES}
-\dd Describes a drop-down list presenting one of a small number of
-fixed choices.
-\lcont{
-For controls of this type, \c{u.choices} contains two fields:
-\c const char *choicenames;
-\c int selected;
-\c{choicenames} contains a list of strings describing the choices. The
-very first character of \c{sval} is used as a delimiter when
-processing the rest (so that the strings \cq{:zero:one:two},
-\cq{!zero!one!two} and \cq{xzeroxonextwo} all define a three-element
-list containing \cq{zero}, \cq{one} and \cq{two}).
-\c{selected} contains the index of the currently selected element,
-numbering from zero (so that in the above example, 0 would mean
-\cq{zero} and 2 would mean \cq{two}).
-Note that \c{u.choices.choicenames} is \e{not} dynamically allocated,
-unlike \c{u.string.sval}.
-}
-\dt \c{C_END}
-\dd Marks the end of the array of \c{config_item}s. There is no
-associated member of the union field \c{u} for this type.
-The array returned from this function is expected to have filled in
-the initial values of all the controls according to the input
-\c{game_params} structure.
-If the game's \c{can_configure} flag is set to \cw{FALSE}, this
-function is never called and need not do anything at all.
-\S{backend-custom-params} \cw{custom_params()}
-\c game_params *(*custom_params)(const config_item *cfg);
-This function is the counterpart to \cw{configure()}
-(\k{backend-configure}). It receives as input an array of
-\c{config_item}s which was originally created by \cw{configure()},
-but in which the control values have since been changed in
-accordance with user input. Its function is to read the new values
-out of the controls and return a newly allocated \c{game_params}
-structure representing the user's chosen parameter set.
-(The front end will have modified the controls' \e{values}, but
-there will still always be the same set of controls, in the same
-order, as provided by \cw{configure()}. It is not necessary to check
-the \c{name} and \c{type} fields, although you could use
-\cw{assert()} if you were feeling energetic.)
-This function is not expected to (and indeed \e{must not}) free the
-input \c{config_item} array. (If the parameters fail to validate,
-the dialog box will stay open.)
-If the game's \c{can_configure} flag is set to \cw{FALSE}, this
-function is never called and need not do anything at all.
-\S{backend-validate-params} \cw{validate_params()}
-\c const char *(*validate_params)(const game_params *params,
-\c                                bool full);
-This function takes a \c{game_params} structure as input, and checks
-that the parameters described in it fall within sensible limits. (At
-the very least, grid dimensions should almost certainly be strictly
-positive, for example.)
-Return value is \cw{NULL} if no problems were found, or
-alternatively a (non-dynamically-allocated) ASCII string describing
-the error in human-readable form.
-If the \c{full} parameter is set, full validation should be
-performed: any set of parameters which would not permit generation
-of a sensible puzzle should be faulted. If \c{full} is \e{not} set,
-the implication is that these parameters are not going to be used
-for \e{generating} a puzzle; so parameters which can't even sensibly
-\e{describe} a valid puzzle should still be faulted, but parameters
-which only affect puzzle generation should not be.
-(The \c{full} option makes a difference when parameter combinations
-are non-orthogonal. For example, Net has a boolean option
-controlling whether it enforces a unique solution; it turns out that
-it's impossible to generate a uniquely soluble puzzle with wrapping
-walls and width 2, so \cw{validate_params()} will complain if you
-ask for one. However, if the user had just been playing a unique
-wrapping puzzle of a more sensible width, and then pastes in a game
-ID acquired from somebody else which happens to describe a
-\e{non}-unique wrapping width-2 puzzle, then \cw{validate_params()}
-will be passed a \c{game_params} containing the width and wrapping
-settings from the new game ID and the uniqueness setting from the
-old one. This would be faulted, if it weren't for the fact that
-\c{full} is not set during this call, so Net ignores the
-inconsistency. The resulting \c{game_params} is never subsequently
-used to generate a puzzle; this is a promise made by the mid-end
-when it asks for a non-full validation.)
-\H{backend-descs} Handling game descriptions
-In this section I present the functions that deal with a textual
-description of a puzzle, i.e. the part that comes after the colon in
-a descriptive-format game ID.
-\S{backend-new-desc} \cw{new_desc()}
-\c char *(*new_desc)(const game_params *params, random_state *rs,
-\c                   char **aux, bool interactive);
-This function is where all the really hard work gets done. This is
-the function whose job is to randomly generate a new puzzle,
-ensuring solubility and uniqueness as appropriate.
-As input it is given a \c{game_params} structure and a random state
-(see \k{utils-random} for the random number API). It must invent a
-puzzle instance, encode it in string form, and return a dynamically
-allocated C string containing that encoding.
-Additionally, it may return a second dynamically allocated string in
-\c{*aux}. (If it doesn't want to, then it can leave that parameter
-completely alone; it isn't required to set it to \cw{NULL}, although
-doing so is harmless.) That string, if present, will be passed to
-\cw{solve()} (\k{backend-solve}) later on; so if the puzzle is
-generated in such a way that a solution is known, then information
-about that solution can be saved in \c{*aux} for \cw{solve()} to
-use.
-The \c{interactive} parameter should be ignored by almost all
-puzzles. Its purpose is to distinguish between generating a puzzle
-within a GUI context for immediate play, and generating a puzzle in
-a command-line context for saving to be played later. The only
-puzzle that currently uses this distinction (and, I fervently hope,
-the only one which will \e{ever} need to use it) is Mines, which
-chooses a random first-click location when generating puzzles
-non-interactively, but which waits for the user to place the first
-click when interactive. If you think you have come up with another
-puzzle which needs to make use of this parameter, please think for
-at least ten minutes about whether there is \e{any} alternative!
-Note that game description strings are not required to contain an
-encoding of parameters such as grid size; a game description is
-never separated from the \c{game_params} it was generated with, so
-any information contained in that structure need not be encoded
-again in the game description.
-\S{backend-validate-desc} \cw{validate_desc()}
-\c const char *(*validate_desc)(const game_params *params,
-\c                              const char *desc);
-This function is given a game description, and its job is to
-validate that it describes a puzzle which makes sense.
-To some extent it's up to the user exactly how far they take the
-phrase \q{makes sense}; there are no particularly strict rules about
-how hard the user is permitted to shoot themself in the foot when
-typing in a bogus game description by hand. (For example, Rectangles
-will not verify that the sum of all the numbers in the grid equals
-the grid's area. So a user could enter a puzzle which was provably
-not soluble, and the program wouldn't complain; there just wouldn't
-happen to be any sequence of moves which solved it.)
-The one non-negotiable criterion is that any game description which
-makes it through \cw{validate_desc()} \e{must not} subsequently
-cause a crash or an assertion failure when fed to \cw{new_game()}
-and thence to the rest of the back end.
-The return value is \cw{NULL} on success, or a
-non-dynamically-allocated C string containing an error message.
-\S{backend-new-game} \cw{new_game()}
-\c game_state *(*new_game)(midend *me, const game_params *params,
-\c                         const char *desc);
-This function takes a game description as input, together with its
-accompanying \c{game_params}, and constructs a \c{game_state}
-describing the initial state of the puzzle. It returns a newly
-allocated \c{game_state} structure.
-Almost all puzzles should ignore the \c{me} parameter. It is
-required by Mines, which needs it for later passing to
-\cw{midend_supersede_game_desc()} (see \k{backend-supersede}) once
-the user has placed the first click. I fervently hope that no other
-puzzle will be awkward enough to require it, so everybody else
-should ignore it. As with the \c{interactive} parameter in
-\cw{new_desc()} (\k{backend-new-desc}), if you think you have a
-reason to need this parameter, please try very hard to think of an
-alternative approach!
-\H{backend-states} Handling game states
-This section describes the functions which create and destroy
-\c{game_state} structures.
-(Well, except \cw{new_game()}, which is in \k{backend-new-game}
-instead of under here; but it deals with game descriptions \e{and}
-game states and it had to go in one section or the other.)
-\S{backend-dup-game} \cw{dup_game()}
-\c game_state *(*dup_game)(const game_state *state);
-This function allocates a new \c{game_state} structure and
-initialises it with an exact copy of the information in the one
-provided as input. It returns a pointer to the new duplicate.
-\S{backend-free-game} \cw{free_game()}
-\c void (*free_game)(game_state *state);
-This function frees a \c{game_state} structure, and any subsidiary
-allocations contained within it.
-\H{backend-ui} Handling \c{game_ui}
-\S{backend-new-ui} \cw{new_ui()}
-\c game_ui *(*new_ui)(const game_state *state);
-This function allocates and returns a new \c{game_ui} structure for
-playing a particular puzzle. It is passed a pointer to the initial
-\c{game_state}, in case it needs to refer to that when setting up
-the initial values for the new game.
-\S{backend-free-ui} \cw{free_ui()}
-\c void (*free_ui)(game_ui *ui);
-This function frees a \c{game_ui} structure, and any subsidiary
-allocations contained within it.
-\S{backend-encode-ui} \cw{encode_ui()}
-\c char *(*encode_ui)(const game_ui *ui);
-This function encodes any \e{important} data in a \c{game_ui}
-structure in string form. It is only called when saving a
-half-finished game to a file.
-It should be used sparingly. Almost all data in a \c{game_ui} is not
-important enough to save. The location of the keyboard-controlled
-cursor, for example, can be reset to a default position on reloading
-the game without impacting the user experience. If the user should
-somehow manage to save a game while a mouse drag was in progress,
-then discarding that mouse drag would be an outright \e{feature}.
-A typical thing that \e{would} be worth encoding in this function is
-the Mines death counter: it's in the \c{game_ui} rather than the
-\c{game_state} because it's too important to allow the user to
-revert it by using Undo, and therefore it's also too important to
-allow the user to revert it by saving and reloading. (Of course, the
-user could edit the save file by hand... But if the user is \e{that}
-determined to cheat, they could just as easily modify the game's
-source.)
-\S{backend-decode-ui} \cw{decode_ui()}
-\c void (*decode_ui)(game_ui *ui, const char *encoding);
-This function parses a string previously output by \cw{encode_ui()},
-and writes the decoded data back into the provided \c{game_ui}
-structure.
-\S{backend-changed-state} \cw{changed_state()}
-\c void (*changed_state)(game_ui *ui, const game_state *oldstate,
-\c                       const game_state *newstate);
-This function is called by the mid-end whenever the current game
-state changes, for any reason. Those reasons include:
-\b a fresh move being made by \cw{interpret_move()} and
-\cw{execute_move()}
-\b a solve operation being performed by \cw{solve()} and
-\cw{execute_move()}
-\b the user moving back and forth along the undo list by means of
-the Undo and Redo operations
-\b the user selecting Restart to go back to the initial game state.
-The job of \cw{changed_state()} is to update the \c{game_ui} for
-consistency with the new game state, if any update is necessary. For
-example, Same Game stores data about the currently selected tile
-group in its \c{game_ui}, and this data is intrinsically related to
-the game state it was derived from. So it's very likely to become
-invalid when the game state changes; thus, Same Game's
-\cw{changed_state()} function clears the current selection whenever
-it is called.
-When \cw{anim_length()} or \cw{flash_length()} are called, you can
-be sure that there has been a previous call to \cw{changed_state()}.
-So \cw{changed_state()} can set up data in the \c{game_ui} which will
-be read by \cw{anim_length()} and \cw{flash_length()}, and those
-functions will not have to worry about being called without the data
-having been initialised.
-\H{backend-moves} Making moves
-This section describes the functions which actually make moves in
-the game: that is, the functions which process user input and end up
-producing new \c{game_state}s.
-\S{backend-interpret-move} \cw{interpret_move()}
-\c char *(*interpret_move)(const game_state *state, game_ui *ui,
-\c                         const game_drawstate *ds,
-\c                         int x, int y, int button);
-This function receives user input and processes it. Its input
-parameters are the current \c{game_state}, the current \c{game_ui}
-and the current \c{game_drawstate}, plus details of the input event.
-\c{button} is either an ASCII value or a special code (listed below)
-indicating an arrow or function key or a mouse event; when
-\c{button} is a mouse event, \c{x} and \c{y} contain the pixel
-coordinates of the mouse pointer relative to the top left of the
-puzzle's drawing area.
-(The pointer to the \c{game_drawstate} is marked \c{const}, because
-\c{interpret_move} should not write to it. The normal use of that
-pointer will be to read the game's tile size parameter in order to
-divide mouse coordinates by it.)
-\cw{interpret_move()} may return in three different ways:
-\b Returning \cw{NULL} indicates that no action whatsoever occurred
-in response to the input event; the puzzle was not interested in it
-at all.
-\b Returning the special value \cw{UI_UPDATE} indicates that the input
-event has resulted in a change being made to the \c{game_ui} which
-will require a redraw of the game window, but that no actual \e{move}
-was made (i.e. no new \c{game_state} needs to be created).
-\b Returning anything else indicates that a move was made and that a
-new \c{game_state} must be created. However, instead of actually
-constructing a new \c{game_state} itself, this function is required
-to return a string description of the details of the move. This
-string will be passed to \cw{execute_move()}
-(\k{backend-execute-move}) to actually create the new
-\c{game_state}. (Encoding moves as strings in this way means that
-the mid-end can keep the strings as well as the game states, and the
-strings can be written to disk when saving the game and fed to
-\cw{execute_move()} again on reloading.)
-The return value from \cw{interpret_move()} is expected to be
-dynamically allocated if and only if it is not either \cw{NULL}
-\e{or} the special string constant \c{UI_UPDATE}.
-After this function is called, the back end is permitted to rely on
-some subsequent operations happening in sequence:
-\b \cw{execute_move()} will be called to convert this move
-description into a new \c{game_state}
-\b \cw{changed_state()} will be called with the new \c{game_state}.
-This means that if \cw{interpret_move()} needs to do updates to the
-\c{game_ui} which are easier to perform by referring to the new
-\c{game_state}, it can safely leave them to be done in
-\cw{changed_state()} and not worry about them failing to happen.
-(Note, however, that \cw{execute_move()} may \e{also} be called in
-other circumstances. It is only \cw{interpret_move()} which can rely
-on a subsequent call to \cw{changed_state()}.)
-The special key codes supported by this function are:
-\dt \cw{LEFT_BUTTON}, \cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}
-\dd Indicate that one of the mouse buttons was pressed down.
-\dt \cw{LEFT_DRAG}, \cw{MIDDLE_DRAG}, \cw{RIGHT_DRAG}
-\dd Indicate that the mouse was moved while one of the mouse buttons
-was still down. The mid-end guarantees that when one of these events
-is received, it will always have been preceded by a button-down
-event (and possibly other drag events) for the same mouse button,
-and no event involving another mouse button will have appeared in
-between.
-\dt \cw{LEFT_RELEASE}, \cw{MIDDLE_RELEASE}, \cw{RIGHT_RELEASE}
-\dd Indicate that a mouse button was released.  The mid-end
-guarantees that when one of these events is received, it will always
-have been preceded by a button-down event (and possibly some drag
-events) for the same mouse button, and no event involving another
-mouse button will have appeared in between.
-\dt \cw{CURSOR_UP}, \cw{CURSOR_DOWN}, \cw{CURSOR_LEFT},
-\cw{CURSOR_RIGHT}
-\dd Indicate that an arrow key was pressed.
-\dt \cw{CURSOR_SELECT}
-\dd On platforms which have a prominent \q{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 \c{button} parameter:
-\dt \cw{MOD_CTRL}, \cw{MOD_SHFT}
-\dd These indicate that the Control or Shift key was pressed
-alongside the key. They only apply to the cursor keys, not to mouse
-buttons or anything else.
-\dt \cw{MOD_NUM_KEYPAD}
-\dd This applies to some ASCII values, and indicates that the key
-code was input via the numeric keypad rather than the main keyboard.
-Some puzzles may wish to treat this differently (for example, a
-puzzle might want to use the numeric keypad as an eight-way
-directional pad), whereas others might not (a game involving numeric
-input probably just wants to treat the numeric keypad as numbers).
-\dt \cw{MOD_MASK}
-\dd This mask is the bitwise OR of all the available modifiers; you
-can bitwise-AND with \cw{~MOD_MASK} to strip all the modifiers off
-any input value.
-\S{backend-execute-move} \cw{execute_move()}
-\c game_state *(*execute_move)(const game_state *state, char *move);
-This function takes an input \c{game_state} and a move string as
-output from \cw{interpret_move()}. It returns a newly allocated
-\c{game_state} which contains the result of applying the specified
-move to the input game state.
-This function may return \cw{NULL} if it cannot parse the move
-string (and this is definitely preferable to crashing or failing an
-assertion, since one way this can happen is if loading a corrupt
-save file). However, it must not return \cw{NULL} for any move
-string that really was output from \cw{interpret_move()}: this is
-punishable by assertion failure in the mid-end.
-\S{backend-can-solve} \c{can_solve}
-\c bool can_solve;
-This field is set to \cw{true} if the game's \cw{solve()} function
-does something. If it's set to \cw{false}, the game will not even
-offer the \q{Solve} menu option.
-\S{backend-solve} \cw{solve()}
-\c char *(*solve)(const game_state *orig, const game_state *curr,
-\c                const char *aux, const char **error);
-This function is called when the user selects the \q{Solve} option
-from the menu.
-It is passed two input game states: \c{orig} is the game state from
-the very start of the puzzle, and \c{curr} is the current one.
-(Different games find one or other or both of these convenient.) It
-is also passed the \c{aux} string saved by \cw{new_desc()}
-(\k{backend-new-desc}), in case that encodes important information
-needed to provide the solution.
-If this function is unable to produce a solution (perhaps, for
-example, the game has no in-built solver so it can only solve
-puzzles it invented internally and has an \c{aux} string for) then
-it may return \cw{NULL}. If it does this, it must also set
-\c{*error} to an error message to be presented to the user (such as
-\q{Solution not known for this puzzle}); that error message is not
-expected to be dynamically allocated.
-If this function \e{does} produce a solution, it returns a move string
-suitable for feeding to \cw{execute_move()}
-(\k{backend-execute-move}). Like a (non-empty) string returned from
-\cw{interpret_move()}, the returned string should be dynamically
-allocated.
-\H{backend-drawing} Drawing the game graphics
-This section discusses the back end functions that deal with
-drawing.
-\S{backend-new-drawstate} \cw{new_drawstate()}
-\c game_drawstate *(*new_drawstate)(drawing *dr,
-\c                                  const game_state *state);
-This function allocates and returns a new \c{game_drawstate}
-structure for drawing a particular puzzle. It is passed a pointer to
-a \c{game_state}, in case it needs to refer to that when setting up
-any initial data.
-This function may not rely on the puzzle having been newly started;
-a new draw state can be constructed at any time if the front end
-requests a forced redraw. For games like Pattern, in which initial
-game states are much simpler than general ones, this might be
-important to keep in mind.
-The parameter \c{dr} is a drawing object (see \k{drawing}) which the
-function might need to use to allocate blitters. (However, this
-isn't recommended; it's usually more sensible to wait to allocate a
-blitter until \cw{set_size()} is called, because that way you can
-tailor it to the scale at which the puzzle is being drawn.)
-\S{backend-free-drawstate} \cw{free_drawstate()}
-\c void (*free_drawstate)(drawing *dr, game_drawstate *ds);
-This function frees a \c{game_drawstate} structure, and any
-subsidiary allocations contained within it.
-The parameter \c{dr} is a drawing object (see \k{drawing}), which
-might be required if you are freeing a blitter.
-\S{backend-preferred-tilesize} \c{preferred_tilesize}
-\c int preferred_tilesize;
-Each game is required to define a single integer parameter which
-expresses, in some sense, the scale at which it is drawn. This is
-described in the APIs as \cq{tilesize}, since most puzzles are on a
-square (or possibly triangular or hexagonal) grid and hence a
-sensible interpretation of this parameter is to define it as the
-size of one grid tile in pixels; however, there's no actual
-requirement that the \q{tile size} be proportional to the game
-window size. Window size is required to increase monotonically with
-\q{tile size}, however.
-The data element \c{preferred_tilesize} indicates the tile size
-which should be used in the absence of a good reason to do otherwise
-(such as the screen being too small, or the user explicitly
-requesting a resize if that ever gets implemented).
-\S{backend-compute-size} \cw{compute_size()}
-\c void (*compute_size)(const game_params *params, int tilesize,
-\c                      int *x, int *y);
-This function is passed a \c{game_params} structure and a tile size.
-It returns, in \c{*x} and \c{*y}, the size in pixels of the drawing
-area that would be required to render a puzzle with those parameters
-at that tile size.
-\S{backend-set-size} \cw{set_size()}
-\c void (*set_size)(drawing *dr, game_drawstate *ds,
-\c                  const game_params *params, int tilesize);
-This function is responsible for setting up a \c{game_drawstate} to
-draw at a given tile size. Typically this will simply involve
-copying the supplied \c{tilesize} parameter into a \c{tilesize}
-field inside the draw state; for some more complex games it might
-also involve setting up other dimension fields, or possibly
-allocating a blitter (see \k{drawing-blitter}).
-The parameter \c{dr} is a drawing object (see \k{drawing}), which is
-required if a blitter needs to be allocated.
-Back ends may assume (and may enforce by assertion) that this
-function will be called at most once for any \c{game_drawstate}. If
-a puzzle needs to be redrawn at a different size, the mid-end will
-create a fresh drawstate.
-\S{backend-colours} \cw{colours()}
-\c float *(*colours)(frontend *fe, int *ncolours);
-This function is responsible for telling the front end what colours
-the puzzle will need to draw itself.
-It returns the number of colours required in \c{*ncolours}, and the
-return value from the function itself is a dynamically allocated
-array of three times that many \c{float}s, containing the red, green
-and blue components of each colour respectively as numbers in the
-range [0,1].
-The second parameter passed to this function is a front end handle.
-The only things it is permitted to do with this handle are to call
-the front-end function called \cw{frontend_default_colour()} (see
-\k{frontend-default-colour}) or the utility function called
-\cw{game_mkhighlight()} (see \k{utils-game-mkhighlight}). (The
-latter is a wrapper on the former, so front end implementors only
-need to provide \cw{frontend_default_colour()}.) This allows
-\cw{colours()} to take local configuration into account when
-deciding on its own colour allocations. Most games use the front
-end's default colour as their background, apart from a few which
-depend on drawing relief highlights so they adjust the background
-colour if it's too light for highlights to show up against it.
-Note that the colours returned from this function are for
-\e{drawing}, not for printing. Printing has an entirely different
-colour allocation policy.
-\S{backend-anim-length} \cw{anim_length()}
-\c float (*anim_length)(const game_state *oldstate,
-\c                      const game_state *newstate,
-\c                      int dir, game_ui *ui);
-This function is called when a move is made, undone or redone. It is
-given the old and the new \c{game_state}, and its job is to decide
-whether the transition between the two needs to be animated or can
-be instant.
-\c{oldstate} is the state that was current until this call;
-\c{newstate} is the state that will be current after it. \c{dir}
-specifies the chronological order of those states: if it is
-positive, then the transition is the result of a move or a redo (and
-so \c{newstate} is the later of the two moves), whereas if it is
-negative then the transition is the result of an undo (so that
-\c{newstate} is the \e{earlier} move).
-If this function decides the transition should be animated, it
-returns the desired length of the animation in seconds. If not, it
-returns zero.
-State changes as a result of a Restart operation are never animated;
-the mid-end will handle them internally and never consult this
-function at all. State changes as a result of Solve operations are
-also not animated by default, although you can change this for a
-particular game by setting a flag in \c{flags} (\k{backend-flags}).
-The function is also passed a pointer to the local \c{game_ui}. It
-may refer to information in here to help with its decision (see
-\k{writing-conditional-anim} for an example of this), and/or it may
-\e{write} information about the nature of the animation which will
-be read later by \cw{redraw()}.
-When this function is called, it may rely on \cw{changed_state()}
-having been called previously, so if \cw{anim_length()} needs to
-refer to information in the \c{game_ui}, then \cw{changed_state()}
-is a reliable place to have set that information up.
-Move animations do not inhibit further input events. If the user
-continues playing before a move animation is complete, the animation
-will be abandoned and the display will jump straight to the final
-state.
-\S{backend-flash-length} \cw{flash_length()}
-\c float (*flash_length)(const game_state *oldstate,
-\c                       const game_state *newstate,
-\c                       int dir, game_ui *ui);
-This function is called when a move is completed. (\q{Completed}
-means that not only has the move been made, but any animation which
-accompanied it has finished.) It decides whether the transition from
-\c{oldstate} to \c{newstate} merits a \q{flash}.
-A flash is much like a move animation, but it is \e{not} interrupted
-by further user interface activity; it runs to completion in
-parallel with whatever else might be going on on the display. The
-only thing which will rush a flash to completion is another flash.
-The purpose of flashes is to indicate that the game has been
-completed. They were introduced as a separate concept from move
-animations because of Net: the habit of most Net players (and
-certainly me) is to rotate a tile into place and immediately lock
-it, then move on to another tile. When you make your last move, at
-the instant the final tile is rotated into place the screen starts
-to flash to indicate victory \dash but if you then press the lock
-button out of habit, then the move animation is cancelled, and the
-victory flash does not complete. (And if you \e{don't} press the
-lock button, the completed grid will look untidy because there will
-be one unlocked square.) Therefore, I introduced a specific concept
-of a \q{flash} which is separate from a move animation and can
-proceed in parallel with move animations and any other display
-activity, so that the victory flash in Net is not cancelled by that
-final locking move.
-The input parameters to \cw{flash_length()} are exactly the same as
-the ones to \cw{anim_length()}.
-Just like \cw{anim_length()}, when this function is called, it may
-rely on \cw{changed_state()} having been called previously, so if it
-needs to refer to information in the \c{game_ui} then
-\cw{changed_state()} is a reliable place to have set that
-information up.
-(Some games use flashes to indicate defeat as well as victory;
-Mines, for example, flashes in a different colour when you tread on
-a mine from the colour it uses when you complete the game. In order
-to achieve this, its \cw{flash_length()} function has to store a
-flag in the \c{game_ui} to indicate which flash type is required.)
-\S{backend-get-cursor-location} \cw{get_cursor_location()}
-\c void (*get_cursor_location)(const game_ui *ui,
-\c                             const game_drawstate *ds,
-\c                             const game_state *state,
-\c                             const game_params *params,
-\c                             int *x, int *y,
-\c                             int *w, int *h);
-This function queries the backend for the rectangular region
-containing the cursor (in games that have one), or other region of
-interest.
-This function is called by only
-\cw{midend_get_cursor_location()}(\k{midend-get-cursor-location}). Its
-purpose is to allow front ends to query the location of the backend's
-cursor. With knowledge of this location, a front end can, for example,
-ensure that the region of interest remains visible if the puzzle is
-too big to fit on the screen at once.
-On returning, \cw{*x}, \cw{*y} should be set to the X and Y
-coordinates of the upper-left corner of the rectangular region of
-interest, and \cw{*w} and \cw{*h} should be the width and height of
-that region, respectively. In the event that a cursor is not visible
-on screen, this function should return and leave the return parameters
-untouched \dash the midend will notice this. The backend need not
-bother checking that \cw{x}, \cw{y}, \cw{w} and \cw{h} are
-non-\cw{NULL} \dash the midend guarantees that they will not be.
-Defining what constitutes a \q{region of interest} is left up to the
-backend. If a game provides a conventional cursor \dash such as Mines,
-Solo, or any of the other grid-based games \dash the most logical
-choice is of course the location of the cursor itself. However, in
-other cases such as Cube or Inertia, there is no \q{cursor} in the
-conventional sense \dash the player instead controls an object moving
-around the screen. In these cases, it makes sense to define the region
-of interest as the bounding box of the player object or another
-sensible region \dash such as the grid square the player is sitting on
-in Cube.
-If a backend does not provide a cursor mechanism at all, the backend
-is free to provide an empty implementation of this function, or a
-\cw{NULL} pointer in the \cw{game} structure \dash the midend will
-notice either of these cases and behave appropriately.
-\S{backend-status} \cw{status()}
-\c int (*status)(const game_state *state);
-This function returns a status value indicating whether the current
-game is still in play, or has been won, or has been conclusively lost.
-The mid-end uses this to implement \cw{midend_status()}
-(\k{midend-status}).
-The return value should be +1 if the game has been successfully
-solved. If the game has been lost in a situation where further play is
-unlikely, the return value should be -1. If neither is true (so play
-is still ongoing), return zero.
-Front ends may wish to use a non-zero status as a cue to proactively
-offer the option of starting a new game. Therefore, back ends should
-not return -1 if the game has been \e{technically} lost but undoing
-and continuing is still a realistic possibility.
-(For instance, games with hidden information such as Guess or Mines
-might well return a non-zero status whenever they reveal the solution,
-whether or not the player guessed it correctly, on the grounds that a
-player would be unlikely to hide the solution and continue playing
-after the answer was spoiled. On the other hand, games where you can
-merely get into a dead end such as Same Game or Inertia might choose
-to return 0 in that situation, on the grounds that the player would
-quite likely press Undo and carry on playing.)
-\S{backend-redraw} \cw{redraw()}
-\c void (*redraw)(drawing *dr, game_drawstate *ds,
-\c                const game_state *oldstate,
-\c                const game_state *newstate,
-\c                int dir, const game_ui *ui,
-\c                float anim_time, float flash_time);
-This function is responsible for actually drawing the contents of
-the game window, and for redrawing every time the game state or the
-\c{game_ui} changes.
-The parameter \c{dr} is a drawing object which may be passed to the
-drawing API functions (see \k{drawing} for documentation of the
-drawing API). This function may not save \c{dr} and use it
-elsewhere; it must only use it for calling back to the drawing API
-functions within its own lifetime.
-\c{ds} is the local \c{game_drawstate}, of course, and \c{ui} is the
-local \c{game_ui}.
-\c{newstate} is the semantically-current game state, and is always
-non-\cw{NULL}. If \c{oldstate} is also non-\cw{NULL}, it means that
-a move has recently been made and the game is still in the process
-of displaying an animation linking the old and new states; in this
-situation, \c{anim_time} will give the length of time (in seconds)
-that the animation has already been running. If \c{oldstate} is
-\cw{NULL}, then \c{anim_time} is unused (and will hopefully be set
-to zero to avoid confusion).
-\c{flash_time}, if it is is non-zero, denotes that the game is in
-the middle of a flash, and gives the time since the start of the
-flash. See \k{backend-flash-length} for general discussion of
-flashes.
-The very first time this function is called for a new
-\c{game_drawstate}, it is expected to redraw the \e{entire} drawing
-area. Since this often involves drawing visual furniture which is
-never subsequently altered, it is often simplest to arrange this by
-having a special \q{first time} flag in the draw state, and
-resetting it after the first redraw.
-When this function (or any subfunction) calls the drawing API, it is
-expected to pass colour indices which were previously defined by the
-\cw{colours()} function.
-\H{backend-printing} Printing functions
-This section discusses the back end functions that deal with
-printing puzzles out on paper.
-\S{backend-can-print} \c{can_print}
-\c bool can_print;
-This flag is set to \cw{true} if the puzzle is capable of printing
-itself on paper. (This makes sense for some puzzles, such as Solo,
-which can be filled in with a pencil. Other puzzles, such as
-Twiddle, inherently involve moving things around and so would not
-make sense to print.)
-If this flag is \cw{false}, then the functions \cw{print_size()}
-and \cw{print()} will never be called.
-\S{backend-can-print-in-colour} \c{can_print_in_colour}
-\c bool can_print_in_colour;
-This flag is set to \cw{true} if the puzzle is capable of printing
-itself differently when colour is available. For example, Map can
-actually print coloured regions in different \e{colours} rather than
-resorting to cross-hatching.
-If the \c{can_print} flag is \cw{false}, then this flag will be
-ignored.
-\S{backend-print-size} \cw{print_size()}
-\c void (*print_size)(const game_params *params, float *x, float *y);
-This function is passed a \c{game_params} structure and a tile size.
-It returns, in \c{*x} and \c{*y}, the preferred size in
-\e{millimetres} of that puzzle if it were to be printed out on paper.
-If the \c{can_print} flag is \cw{FALSE}, this function will never be
-called.
-\S{backend-print} \cw{print()}
-\c void (*print)(drawing *dr, const game_state *state, int tilesize);
-This function is called when a puzzle is to be printed out on paper.
-It should use the drawing API functions (see \k{drawing}) to print
-itself.
-This function is separate from \cw{redraw()} because it is often
-very different:
-\b The printing function may not depend on pixel accuracy, since
-printer resolution is variable. Draw as if your canvas had infinite
-resolution.
-\b The printing function sometimes needs to display things in a
-completely different style. Net, for example, is very different as
-an on-screen puzzle and as a printed one.
-\b The printing function is often much simpler since it has no need
-to deal with repeated partial redraws.
-However, there's no reason the printing and redraw functions can't
-share some code if they want to.
-When this function (or any subfunction) calls the drawing API, the
-colour indices it passes should be colours which have been allocated
-by the \cw{print_*_colour()} functions within this execution of
-\cw{print()}. This is very different from the fixed small number of
-colours used in \cw{redraw()}, because printers do not have a
-limitation on the total number of colours that may be used. Some
-puzzles' printing functions might wish to allocate only one \q{ink}
-colour and use it for all drawing; others might wish to allocate
-\e{more} colours than are used on screen.
-One possible colour policy worth mentioning specifically is that a
-puzzle's printing function might want to allocate the \e{same}
-colour indices as are used by the redraw function, so that code
-shared between drawing and printing does not have to keep switching
-its colour indices. In order to do this, the simplest thing is to
-make use of the fact that colour indices returned from
-\cw{print_*_colour()} are guaranteed to be in increasing order from
-zero. So if you have declared an \c{enum} defining three colours
-\cw{COL_BACKGROUND}, \cw{COL_THIS} and \cw{COL_THAT}, you might then
-write
-\c int c;
-\c c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
-\c c = print_mono_colour(dr, 0); assert(c == COL_THIS);
-\c c = print_mono_colour(dr, 0); assert(c == COL_THAT);
-If the \c{can_print} flag is \cw{FALSE}, this function will never be
-called.
-\H{backend-misc} Miscellaneous
-\S{backend-can-format-as-text-ever} \c{can_format_as_text_ever}
-\c bool can_format_as_text_ever;
-This field is \cw{true} if the game supports formatting a
-game state as ASCII text (typically ASCII art) for copying to the
-clipboard and pasting into other applications. If it is \cw{false},
-front ends will not offer the \q{Copy} command at all.
-If this field is \cw{true}, the game does not necessarily have to
-support text formatting for \e{all} games: e.g. a game which can be
-played on a square grid or a triangular one might only support copy
-and paste for the former, because triangular grids in ASCII art are
-just too difficult.
-If this field is \cw{false}, the functions
-\cw{can_format_as_text_now()} (\k{backend-can-format-as-text-now})
-and \cw{text_format()} (\k{backend-text-format}) are never called.
-\S{backend-can-format-as-text-now} \c{can_format_as_text_now()}
-\c bool (*can_format_as_text_now)(const game_params *params);
-This function is passed a \c{game_params}, and returns \cw{true} if
-the game can support ASCII text output for this particular game type.
-If it returns \cw{false}, front ends will grey out or otherwise
-disable the \q{Copy} command.
-Games may enable and disable the copy-and-paste function for
-different game \e{parameters}, but are currently constrained to
-return the same answer from this function for all game \e{states}
-sharing the same parameters. In other words, the \q{Copy} function
-may enable or disable itself when the player changes game preset,
-but will never change during play of a single game or when another
-game of exactly the same type is generated.
-This function should not take into account aspects of the game
-parameters which are not encoded by \cw{encode_params()}
-(\k{backend-encode-params}) when the \c{full} parameter is set to
-\cw{FALSE}. Such parameters will not necessarily match up between a
-call to this function and a subsequent call to \cw{text_format()}
-itself. (For instance, game \e{difficulty} should not affect whether
-the game can be copied to the clipboard. Only the actual visible
-\e{shape} of the game can affect that.)
-\S{backend-text-format} \cw{text_format()}
-\c char *(*text_format)(const game_state *state);
-This function is passed a \c{game_state}, and returns a newly
-allocated C string containing an ASCII representation of that game
-state. It is used to implement the \q{Copy} operation in many front
-ends.
-This function will only ever be called if the back end field
-\c{can_format_as_text_ever} (\k{backend-can-format-as-text-ever}) is
-\cw{TRUE} \e{and} the function \cw{can_format_as_text_now()}
-(\k{backend-can-format-as-text-now}) has returned \cw{TRUE} for the
-currently selected game parameters.
-The returned string may contain line endings (and will probably want
-to), using the normal C internal \cq{\\n} convention. For
-consistency between puzzles, all multi-line textual puzzle
-representations should \e{end} with a newline as well as containing
-them internally. (There are currently no puzzles which have a
-one-line ASCII representation, so there's no precedent yet for
-whether that should come with a newline or not.)
-\S{backend-wants-statusbar} \cw{wants_statusbar}
-\c bool wants_statusbar;
-This field is set to \cw{true} if the puzzle has a use for a textual
-status line (to display score, completion status, currently active
-tiles, etc).
-\S{backend-is-timed} \c{is_timed}
-\c bool is_timed;
-This field is \cw{true} if the puzzle is time-critical. If
-so, the mid-end will maintain a game timer while the user plays.
-If this field is \cw{false}, then \cw{timing_state()} will never be
-called and need not do anything.
-\S{backend-timing-state} \cw{timing_state()}
-\c bool (*timing_state)(const game_state *state, game_ui *ui);
-This function is passed the current \c{game_state} and the local
-\c{game_ui}; it returns \cw{true} if the game timer should currently
-be running.
-A typical use for the \c{game_ui} in this function is to note when
-the game was first completed (by setting a flag in
-\cw{changed_state()} \dash see \k{backend-changed-state}), and
-freeze the timer thereafter so that the user can undo back through
-their solution process without altering their time.
-\S{backend-request-keys} \cw{request_keys()}
-\c key_label *(*request_keys)(const game_params *params, int *nkeys);
-This function returns a dynamically allocated array of \cw{key_label}
-items containing the buttons the back end deems absolutely
-\e{necessary} for gameplay, not an exhaustive list of every button the
-back end could accept. For example, Keen only returns the digits up to
-the game size and the backspace character, \cw{\\b}, even though it
-\e{could} accept \cw{M}, as only these buttons are actually needed to
-play the game. Each \cw{key_label} item contains the following fields:
-\c struct key_label {
-\c     const char *label; /* label for frontend use */
-\c     int button; /* button to pass to midend */
-\c } key_label;
-The \cw{label} field of this structure can (and often will) be set by
-the backend to \cw{NULL}, in which case the midend will instead call
-\c{button2label()} (\k{utils-button2label}) and fill in a generic
-label. The \cw{button} field is the associated code that can be passed
-to the midend when the frontend deems appropriate.
-The backend should set \cw{*nkeys} to the number of elements in the
-returned array.
-The field for this function pointer in the \cw{game} structure might
-be set to \cw{NULL} (and indeed it is for the majority of the games)
-to indicate that no additional buttons (apart from the cursor keys)
-are required to play the game.
-This function should not be called directly by frontends. Instead,
-frontends should use \cw{midend_request_keys()}
-(\k{midend-request-keys}).
-\S{backend-flags} \c{flags}
-\c int flags;
-This field contains miscellaneous per-backend flags. It consists of
-the bitwise OR of some combination of the following:
-\dt \cw{BUTTON_BEATS(x,y)}
-\dd Given any \cw{x} and \cw{y} from the set \{\cw{LEFT_BUTTON},
-\cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}\}, this macro evaluates to a
-bit flag which indicates that when buttons \cw{x} and \cw{y} are
-both pressed simultaneously, the mid-end should consider \cw{x} to
-have priority. (In the absence of any such flags, the mid-end will
-always consider the most recently pressed button to have priority.)
-\dt \cw{SOLVE_ANIMATES}
-\dd This flag indicates that moves generated by \cw{solve()}
-(\k{backend-solve}) are candidates for animation just like any other
-move. For most games, solve moves should not be animated, so the
-mid-end doesn't even bother calling \cw{anim_length()}
-(\k{backend-anim-length}), thus saving some special-case code in
-each game. On the rare occasion that animated solve moves are
-actually required, you can set this flag.
-\dt \cw{REQUIRE_RBUTTON}
-\dd This flag indicates that the puzzle cannot be usefully played
-without the use of mouse buttons other than the left one. On some
-PDA platforms, this flag is used by the front end to enable
-right-button emulation through an appropriate gesture. Note that a
-puzzle is not required to set this just because it \e{uses} the
-right button, but only if its use of the right button is critical to
-playing the game. (Slant, for example, uses the right button to
-cycle through the three square states in the opposite order from the
-left button, and hence can manage fine without it.)
-\dt \cw{REQUIRE_NUMPAD}
-\dd This flag indicates that the puzzle cannot be usefully played
-without the use of number-key input. On some PDA platforms it causes
-an emulated number pad to appear on the screen. Similarly to
-\cw{REQUIRE_RBUTTON}, a puzzle need not specify this simply if its
-use of the number keys is not critical.
-\H{backend-initiative} Things a back end may do on its own initiative
-This section describes a couple of things that a back end may choose
-to do by calling functions elsewhere in the program, which would not
-otherwise be obvious.
-\S{backend-newrs} Create a random state
-If a back end needs random numbers at some point during normal play,
-it can create a fresh \c{random_state} by first calling
-\c{get_random_seed} (\k{frontend-get-random-seed}) and then passing
-the returned seed data to \cw{random_new()}.
-This is likely not to be what you want. If a puzzle needs randomness
-in the middle of play, it's likely to be more sensible to store some
-sort of random state within the \c{game_state}, so that the random
-numbers are tied to the particular game state and hence the player
-can't simply keep undoing their move until they get numbers they
-like better.
-This facility is currently used only in Net, to implement the
-\q{jumble} command, which sets every unlocked tile to a new random
-orientation. This randomness \e{is} a reasonable use of the feature,
-because it's non-adversarial \dash there's no advantage to the user
-in getting different random numbers.
-\S{backend-supersede} Supersede its own game description
-In response to a move, a back end is (reluctantly) permitted to call
-\cw{midend_supersede_game_desc()}:
-\c void midend_supersede_game_desc(midend *me,
-\c                                 char *desc, char *privdesc);
-When the user selects \q{New Game}, the mid-end calls
-\cw{new_desc()} (\k{backend-new-desc}) to get a new game
-description, and (as well as using that to generate an initial game
-state) stores it for the save file and for telling to the user. The
-function above overwrites that game description, and also splits it
-in two. \c{desc} becomes the new game description which is provided
-to the user on request, and is also the one used to construct a new
-initial game state if the user selects \q{Restart}. \c{privdesc} is
-a \q{private} game description, used to reconstruct the game's
-initial state when reloading.
-The distinction between the two, as well as the need for this
-function at all, comes from Mines. Mines begins with a blank grid
-and no idea of where the mines actually are; \cw{new_desc()} does
-almost no work in interactive mode, and simply returns a string
-encoding the \c{random_state}. When the user first clicks to open a
-tile, \e{then} Mines generates the mine positions, in such a way
-that the game is soluble from that starting point. Then it uses this
-function to supersede the random-state game description with a
-proper one. But it needs two: one containing the initial click
-location (because that's what you want to happen if you restart the
-game, and also what you want to send to a friend so that they play
-\e{the same game} as you), and one without the initial click
-location (because when you save and reload the game, you expect to
-see the same blank initial state as you had before saving).
-I should stress again that this function is a horrid hack. Nobody
-should use it if they're not Mines; if you think you need to use it,
-think again repeatedly in the hope of finding a better way to do
-whatever it was you needed to do.
-\C{drawing} The drawing API
-The back end function \cw{redraw()} (\k{backend-redraw}) is required
-to draw the puzzle's graphics on the window's drawing area, 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 \c{drawing} structure
-(a \q{drawing object}). These objects are supplied as parameters to
-the back end's \cw{redraw()} and \cw{print()} functions.
-In fact these global functions are not implemented directly by the
-front end; instead, they are implemented centrally in \c{drawing.c}
-and form a small piece of middleware. The drawing API as supplied by
-the front end is a structure containing a set of function pointers,
-plus a \cq{void *} handle which is passed to each of those
-functions. This enables a single front end to switch between
-multiple implementations of the drawing API if necessary. For
-example, the Windows API supplies a printing mechanism integrated
-into the same GDI which deals with drawing in windows, and therefore
-the same API implementation can handle both drawing and printing;
-but on Unix, the most common way for applications to print is by
-producing PostScript output directly, and although it would be
-\e{possible} to write a single (say) \cw{draw_rect()} function which
-checked a global flag to decide whether to do GTK drawing operations
-or output PostScript to a file, it's much nicer to have two separate
-functions and switch between them as appropriate.
-When drawing, the puzzle window is indexed by pixel coordinates,
-with the top left pixel defined as \cw{(0,0)} and the bottom right
-pixel \cw{(w-1,h-1)}, where \c{w} and \c{h} are the width and height
-values returned by the back end function \cw{compute_size()}
-(\k{backend-compute-size}).
-When printing, the puzzle's print area is indexed in exactly the
-same way (with an arbitrary tile size provided by the printing
-module \c{printing.c}), to facilitate sharing of code between the
-drawing and printing routines. However, when printing, puzzles may
-no longer assume that the coordinate unit has any relationship to a
-pixel; the printer's actual resolution might very well not even be
-known at print time, so the coordinate unit might be smaller or
-larger than a pixel. Puzzles' print functions should restrict
-themselves to drawing geometric shapes rather than fiddly pixel
-manipulation.
-\e{Puzzles' redraw functions may assume that the surface they draw
-on is persistent}. It is the responsibility of every front end to
-preserve the puzzle's window contents in the face of GUI window
-expose issues and similar. It is not permissible to request that the
-back end redraw any part of a window that it has already drawn,
-unless something has actually changed as a result of making moves in
-the puzzle.
-Most front ends accomplish this by having the drawing routines draw
-on a stored bitmap rather than directly on the window, and copying
-the bitmap to the window every time a part of the window needs to be
-redrawn. Therefore, it is vitally important that whenever the back
-end does any drawing it informs the front end of which parts of the
-window it has accessed, and hence which parts need repainting. This
-is done by calling \cw{draw_update()} (\k{drawing-draw-update}).
-Persistence of old drawing is convenient. However, a puzzle should
-be very careful about how it updates its drawing area. The problem
-is that some front ends do anti-aliased drawing: rather than simply
-choosing between leaving each pixel untouched or painting it a
-specified colour, an antialiased drawing function will \e{blend} the
-original and new colours in pixels at a figure's boundary according
-to the proportion of the pixel occupied by the figure (probably
-modified by some heuristic fudge factors). All of this produces a
-smoother appearance for curves and diagonal lines.
-An unfortunate effect of drawing an anti-aliased figure repeatedly
-is that the pixels around the figure's boundary come steadily more
-saturated with \q{ink} and the boundary appears to \q{spread out}.
-Worse, redrawing a figure in a different colour won't fully paint
-over the old boundary pixels, so the end result is a rather ugly
-smudge.
-A good strategy to avoid unpleasant anti-aliasing artifacts is to
-identify a number of rectangular areas which need to be redrawn,
-clear them to the background colour, and then redraw their contents
-from scratch, being careful all the while not to stray beyond the
-boundaries of the original rectangles. The \cw{clip()} function
-(\k{drawing-clip}) comes in very handy here. Games based on a square
-grid can often do this fairly easily. Other games may need to be
-somewhat more careful. For example, Loopy's redraw function first
-identifies portions of the display which need to be updated. Then,
-if the changes are fairly well localised, it clears and redraws a
-rectangle containing each changed area. Otherwise, it gives up and
-redraws the entire grid from scratch.
-It is possible to avoid clearing to background and redrawing from
-scratch if one is very careful about which drawing functions one
-uses: if a function is documented as not anti-aliasing under some
-circumstances, you can rely on each pixel in a drawing either being
-left entirely alone or being set to the requested colour, with no
-blending being performed.
-In the following sections I first discuss the drawing API as seen by
-the back end, and then the \e{almost} identical function-pointer
-form seen by the front end.
-\H{drawing-backend} Drawing API as seen by the back end
-This section documents the back-end drawing API, in the form of
-functions which take a \c{drawing} object as an argument.
-\S{drawing-draw-rect} \cw{draw_rect()}
-\c void draw_rect(drawing *dr, int x, int y, int w, int h,
-\c                int colour);
-Draws a filled rectangle in the puzzle window.
-\c{x} and \c{y} give the coordinates of the top left pixel of the
-rectangle. \c{w} and \c{h} give its width and height. Thus, the
-horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
-inclusive, and the vertical extent from \c{y} to \c{y+h-1}
-inclusive.
-\c{colour} is an integer index into the colours array returned by
-the back end function \cw{colours()} (\k{backend-colours}).
-There is no separate pixel-plotting function. If you want to plot a
-single pixel, the approved method is to use \cw{draw_rect()} with
-width and height set to 1.
-Unlike many of the other drawing functions, this function is
-guaranteed to be pixel-perfect: the rectangle will be sharply
-defined and not anti-aliased or anything like that.
-This function may be used for both drawing and printing.
-\S{drawing-draw-rect-outline} \cw{draw_rect_outline()}
-\c void draw_rect_outline(drawing *dr, int x, int y, int w, int h,
-\c                        int colour);
-Draws an outline rectangle in the puzzle window.
-\c{x} and \c{y} give the coordinates of the top left pixel of the
-rectangle. \c{w} and \c{h} give its width and height. Thus, the
-horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
-inclusive, and the vertical extent from \c{y} to \c{y+h-1}
-inclusive.
-\c{colour} is an integer index into the colours array returned by
-the back end function \cw{colours()} (\k{backend-colours}).
-From a back end perspective, this function may be considered to be
-part of the drawing API. However, front ends are not required to
-implement it, since it is actually implemented centrally (in
-\cw{misc.c}) as a wrapper on \cw{draw_polygon()}.
-This function may be used for both drawing and printing.
-\S{drawing-draw-line} \cw{draw_line()}
-\c void draw_line(drawing *dr, int x1, int y1, int x2, int y2,
-\c                int colour);
-Draws a straight line in the puzzle window.
-\c{x1} and \c{y1} give the coordinates of one end of the line.
-\c{x2} and \c{y2} give the coordinates of the other end. The line
-drawn includes both those points.
-\c{colour} is an integer index into the colours array returned by
-the back end function \cw{colours()} (\k{backend-colours}).
-Some platforms may perform anti-aliasing on this function.
-Therefore, do not assume that you can erase a line by drawing the
-same line over it in the background colour; anti-aliasing might lead
-to perceptible ghost artefacts around the vanished line. Horizontal
-and vertical lines, however, are pixel-perfect and not anti-aliased.
-This function may be used for both drawing and printing.
-\S{drawing-draw-polygon} \cw{draw_polygon()}
-\c void draw_polygon(drawing *dr, int *coords, int npoints,
-\c                   int fillcolour, int outlinecolour);
-Draws an outlined or filled polygon in the puzzle window.
-\c{coords} is an array of \cw{(2*npoints)} integers, containing the
-\c{x} and \c{y} coordinates of \c{npoints} vertices.
-\c{fillcolour} and \c{outlinecolour} are integer indices into the
-colours array returned by the back end function \cw{colours()}
-(\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
-indicate that the polygon should be outlined only.
-The polygon defined by the specified list of vertices is first
-filled in \c{fillcolour}, if specified, and then outlined in
-\c{outlinecolour}.
-\c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
-(and front ends are permitted to enforce this by assertion). This is
-because different platforms disagree on whether a filled polygon
-should include its boundary line or not, so drawing \e{only} a
-filled polygon would have non-portable effects. If you want your
-filled polygon not to have a visible outline, you must set
-\c{outlinecolour} to the same as \c{fillcolour}.
-Some platforms may perform anti-aliasing on this function.
-Therefore, do not assume that you can erase a polygon by drawing the
-same polygon over it in the background colour. Also, be prepared for
-the polygon to extend a pixel beyond its obvious bounding box as a
-result of this; if you really need it not to do this to avoid
-interfering with other delicate graphics, you should probably use
-\cw{clip()} (\k{drawing-clip}). You can rely on horizontal and
-vertical lines not being anti-aliased.
-This function may be used for both drawing and printing.
-\S{drawing-draw-circle} \cw{draw_circle()}
-\c void draw_circle(drawing *dr, int cx, int cy, int radius,
-\c                  int fillcolour, int outlinecolour);
-Draws an outlined or filled circle in the puzzle window.
-\c{cx} and \c{cy} give the coordinates of the centre of the circle.
-\c{radius} gives its radius. The total horizontal pixel extent of
-the circle is from \c{cx-radius+1} to \c{cx+radius-1} inclusive, and
-the vertical extent similarly around \c{cy}.
-\c{fillcolour} and \c{outlinecolour} are integer indices into the
-colours array returned by the back end function \cw{colours()}
-(\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
-indicate that the circle should be outlined only.
-The circle is first filled in \c{fillcolour}, if specified, and then
-outlined in \c{outlinecolour}.
-\c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
-(and front ends are permitted to enforce this by assertion). This is
-because different platforms disagree on whether a filled circle
-should include its boundary line or not, so drawing \e{only} a
-filled circle would have non-portable effects. If you want your
-filled circle not to have a visible outline, you must set
-\c{outlinecolour} to the same as \c{fillcolour}.
-Some platforms may perform anti-aliasing on this function.
-Therefore, do not assume that you can erase a circle by drawing the
-same circle over it in the background colour. Also, be prepared for
-the circle to extend a pixel beyond its obvious bounding box as a
-result of this; if you really need it not to do this to avoid
-interfering with other delicate graphics, you should probably use
-\cw{clip()} (\k{drawing-clip}).
-This function may be used for both drawing and printing.
-\S{drawing-draw-thick-line} \cw{draw_thick_line()}
-\c void draw_thick_line(drawing *dr, float thickness,
-\c                      float x1, float y1, float x2, float y2,
-\c                      int colour)
-Draws a line in the puzzle window, giving control over the line's
-thickness.
-\c{x1} and \c{y1} give the coordinates of one end of the line.
-\c{x2} and \c{y2} give the coordinates of the other end.
-\c{thickness} gives the thickness of the line, in pixels.
-Note that the coordinates and thickness are floating-point: the
-continuous coordinate system is in effect here. It's important to
-be able to address points with better-than-pixel precision in this
-case, because one can't otherwise properly express the endpoints of
-lines with both odd and even thicknesses.
-Some platforms may perform anti-aliasing on this function. The
-precise pixels affected by a thick-line drawing operation may vary
-between platforms, and no particular guarantees are provided.
-Indeed, even horizontal or vertical lines may be anti-aliased.
-This function may be used for both drawing and printing.
-If the specified thickness is less than 1.0, 1.0 is used.
-This ensures that thin lines are visible even at small scales.
-\S{drawing-draw-text} \cw{draw_text()}
-\c void draw_text(drawing *dr, int x, int y, int fonttype,
-\c                int fontsize, int align, int colour,
-\c                const char *text);
-Draws text in the puzzle window.
-\c{x} and \c{y} give the coordinates of a point. The relation of
-this point to the location of the text is specified by \c{align},
-which is a bitwise OR of horizontal and vertical alignment flags:
-\dt \cw{ALIGN_VNORMAL}
-\dd Indicates that \c{y} is aligned with the baseline of the text.
-\dt \cw{ALIGN_VCENTRE}
-\dd Indicates that \c{y} is aligned with the vertical centre of the
-text. (In fact, it's aligned with the vertical centre of normal
-\e{capitalised} text: displaying two pieces of text with
-\cw{ALIGN_VCENTRE} at the same \cw{y}-coordinate will cause their
-baselines to be aligned with one another, even if one is an ascender
-and the other a descender.)
-\dt \cw{ALIGN_HLEFT}
-\dd Indicates that \c{x} is aligned with the left-hand end of the
-text.
-\dt \cw{ALIGN_HCENTRE}
-\dd Indicates that \c{x} is aligned with the horizontal centre of
-the text.
-\dt \cw{ALIGN_HRIGHT}
-\dd Indicates that \c{x} is aligned with the right-hand end of the
-text.
-\c{fonttype} is either \cw{FONT_FIXED} or \cw{FONT_VARIABLE}, for a
-monospaced or proportional font respectively. (No more detail than
-that may be specified; it would only lead to portability issues
-between different platforms.)
-\c{fontsize} is the desired size, in pixels, of the text. This size
-corresponds to the overall point size of the text, not to any
-internal dimension such as the cap-height.
-\c{colour} is an integer index into the colours array returned by
-the back end function \cw{colours()} (\k{backend-colours}).
-This function may be used for both drawing and printing.
-The character set used to encode the text passed to this function is
-specified \e{by the drawing object}, although it must be a superset
-of ASCII. If a puzzle wants to display text that is not contained in
-ASCII, it should use the \cw{text_fallback()} function
-(\k{drawing-text-fallback}) to query the drawing object for an
-appropriate representation of the characters it wants.
-\S{drawing-text-fallback} \cw{text_fallback()}
-\c char *text_fallback(drawing *dr, const char *const *strings,
-\c                     int nstrings);
-This function is used to request a translation of UTF-8 text into
-whatever character encoding is expected by the drawing object's
-implementation of \cw{draw_text()}.
-The input is a list of strings encoded in UTF-8: \cw{nstrings} gives
-the number of strings in the list, and \cw{strings[0]},
-\cw{strings[1]}, ..., \cw{strings[nstrings-1]} are the strings
-themselves.
-The returned string (which is dynamically allocated and must be
-freed when finished with) is derived from the first string in the
-list that the drawing object expects to be able to display reliably;
-it will consist of that string translated into the character set
-expected by \cw{draw_text()}.
-Drawing implementations are not required to handle anything outside
-ASCII, but are permitted to assume that \e{some} string will be
-successfully translated. So every call to this function must include
-a string somewhere in the list (presumably the last element) which
-consists of nothing but ASCII, to be used by any front end which
-cannot handle anything else.
-For example, if a puzzle wished to display a string including a
-multiplication sign (U+00D7 in Unicode, represented by the bytes C3
-97 in UTF-8), it might do something like this:
-\c static const char *const times_signs[] = { "\xC3\x97", "x" };
-\c char *times_sign = text_fallback(dr, times_signs, 2);
-\c sprintf(buffer, "%d%s%d", width, times_sign, height);
-\c draw_text(dr, x, y, font, size, align, colour, buffer);
-\c sfree(buffer);
-which would draw a string with a times sign in the middle on
-platforms that support it, and fall back to a simple ASCII \cq{x}
-where there was no alternative.
-\S{drawing-clip} \cw{clip()}
-\c void clip(drawing *dr, int x, int y, int w, int h);
-Establishes a clipping rectangle in the puzzle window.
-\c{x} and \c{y} give the coordinates of the top left pixel of the
-clipping rectangle. \c{w} and \c{h} give its width and height. Thus,
-the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
-inclusive, and the vertical extent from \c{y} to \c{y+h-1}
-inclusive. (These are exactly the same semantics as
-\cw{draw_rect()}.)
-After this call, no drawing operation will affect anything outside
-the specified rectangle. The effect can be reversed by calling
-\cw{unclip()} (\k{drawing-unclip}). The clipping rectangle is
-pixel-perfect: pixels within the rectangle are affected as usual by
-drawing functions; pixels outside are completely untouched.
-Back ends should not assume that a clipping rectangle will be
-automatically cleared up by the front end if it's left lying around;
-that might work on current front ends, but shouldn't be relied upon.
-Always explicitly call \cw{unclip()}.
-This function may be used for both drawing and printing.
-\S{drawing-unclip} \cw{unclip()}
-\c void unclip(drawing *dr);
-Reverts the effect of a previous call to \cw{clip()}. After this
-call, all drawing operations will be able to affect the entire
-puzzle window again.
-This function may be used for both drawing and printing.
-\S{drawing-draw-update} \cw{draw_update()}
-\c void draw_update(drawing *dr, int x, int y, int w, int h);
-Informs the front end that a rectangular portion of the puzzle
-window has been drawn on and needs to be updated.
-\c{x} and \c{y} give the coordinates of the top left pixel of the
-update rectangle. \c{w} and \c{h} give its width and height. Thus,
-the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
-inclusive, and the vertical extent from \c{y} to \c{y+h-1}
-inclusive. (These are exactly the same semantics as
-\cw{draw_rect()}.)
-The back end redraw function \e{must} call this function to report
-any changes it has made to the window. Otherwise, those changes may
-not become immediately visible, and may then appear at an
-unpredictable subsequent time such as the next time the window is
-covered and re-exposed.
-This function is only important when drawing. It may be called when
-printing as well, but doing so is not compulsory, and has no effect.
-(So if you have a shared piece of code between the drawing and
-printing routines, that code may safely call \cw{draw_update()}.)
-\S{drawing-status-bar} \cw{status_bar()}
-\c void status_bar(drawing *dr, const char *text);
-Sets the text in the game's status bar to \c{text}. The text is copied
-from the supplied buffer, so the caller is free to deallocate or
-modify the buffer after use.
-(This function is not exactly a \e{drawing} function, but it shares
-with the drawing API the property that it may only be called from
-within the back end redraw function, 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.
-\S{drawing-blitter} Blitter functions
-This section describes a group of related functions which save and
-restore a section of the puzzle window. This is most commonly used
-to implement user interfaces involving dragging a puzzle element
-around the window: at the end of each call to \cw{redraw()}, if an
-object is currently being dragged, the back end saves the window
-contents under that location and then draws the dragged object, and
-at the start of the next \cw{redraw()} the first thing it does is to
-restore the background.
-The front end defines an opaque type called a \c{blitter}, which is
-capable of storing a rectangular area of a specified size.
-Blitter functions are for drawing only; they must never be called
-during printing.
-\S2{drawing-blitter-new} \cw{blitter_new()}
-\c blitter *blitter_new(drawing *dr, int w, int h);
-Creates a new blitter object which stores a rectangle of size \c{w}
-by \c{h} pixels. Returns a pointer to the blitter object.
-Blitter objects are best stored in the \c{game_drawstate}. A good
-time to create them is in the \cw{set_size()} function
-(\k{backend-set-size}), since it is at this point that you first
-know how big a rectangle they will need to save.
-\S2{drawing-blitter-free} \cw{blitter_free()}
-\c void blitter_free(drawing *dr, blitter *bl);
-Disposes of a blitter object. Best called in \cw{free_drawstate()}.
-(However, check that the blitter object is not \cw{NULL} before
-attempting to free it; it is possible that a draw state might be
-created and freed without ever having \cw{set_size()} called on it
-in between.)
-\S2{drawing-blitter-save} \cw{blitter_save()}
-\c void blitter_save(drawing *dr, blitter *bl, int x, int y);
-This is a true drawing API function, in that it may only be called
-from within the game redraw routine. It saves a rectangular portion
-of the puzzle window into the specified blitter object.
-\c{x} and \c{y} give the coordinates of the top left corner of the
-saved rectangle. The rectangle's width and height are the ones
-specified when the blitter object was created.
-This function is required to cope and do the right thing if \c{x}
-and \c{y} are out of range. (The right thing probably means saving
-whatever part of the blitter rectangle overlaps with the visible
-area of the puzzle window.)
-\S2{drawing-blitter-load} \cw{blitter_load()}
-\c void blitter_load(drawing *dr, blitter *bl, int x, int y);
-This is a true drawing API function, in that it may only be called
-from within the game redraw routine. It restores a rectangular
-portion of the puzzle window from the specified blitter object.
-\c{x} and \c{y} give the coordinates of the top left corner of the
-rectangle to be restored. The rectangle's width and height are the
-ones specified when the blitter object was created.
-Alternatively, you can specify both \c{x} and \c{y} as the special
-value \cw{BLITTER_FROMSAVED}, in which case the rectangle will be
-restored to exactly where it was saved from. (This is probably what
-you want to do almost all the time, if you're using blitters to
-implement draggable puzzle elements.)
-This function is required to cope and do the right thing if \c{x}
-and \c{y} (or the equivalent ones saved in the blitter) are out of
-range. (The right thing probably means restoring whatever part of
-the blitter rectangle overlaps with the visible area of the puzzle
-window.)
-If this function is called on a blitter which had previously been
-saved from a partially out-of-range rectangle, then the parts of the
-saved bitmap which were not visible at save time are undefined. If
-the blitter is restored to a different position so as to make those
-parts visible, the effect on the drawing area is undefined.
-\S{print-mono-colour} \cw{print_mono_colour()}
-\c int print_mono_colour(drawing *dr, int grey);
-This function allocates a colour index for a simple monochrome
-colour during printing.
-\c{grey} must be 0 or 1. If \c{grey} is 0, the colour returned is
-black; if \c{grey} is 1, the colour is white.
-\S{print-grey-colour} \cw{print_grey_colour()}
-\c int print_grey_colour(drawing *dr, float grey);
-This function allocates a colour index for a grey-scale colour
-during printing.
-\c{grey} may be any number between 0 (black) and 1 (white); for
-example, 0.5 indicates a medium grey.
-The chosen colour will be rendered to the limits of the printer's
-halftoning capability.
-\S{print-hatched-colour} \cw{print_hatched_colour()}
-\c int print_hatched_colour(drawing *dr, int hatch);
-This function allocates a colour index which does not represent a
-literal \e{colour}. Instead, regions shaded in this colour will be
-hatched with parallel lines. The \c{hatch} parameter defines what
-type of hatching should be used in place of this colour:
-\dt \cw{HATCH_SLASH}
-\dd This colour will be hatched by lines slanting to the right at 45
-degrees. 
-\dt \cw{HATCH_BACKSLASH}
-\dd This colour will be hatched by lines slanting to the left at 45
-degrees.
-\dt \cw{HATCH_HORIZ}
-\dd This colour will be hatched by horizontal lines.
-\dt \cw{HATCH_VERT}
-\dd This colour will be hatched by vertical lines.
-\dt \cw{HATCH_PLUS}
-\dd This colour will be hatched by criss-crossing horizontal and
-vertical lines.
-\dt \cw{HATCH_X}
-\dd This colour will be hatched by criss-crossing diagonal lines.
-Colours defined to use hatching may not be used for drawing lines or
-text; they may only be used for filling areas. That is, they may be
-used as the \c{fillcolour} parameter to \cw{draw_circle()} and
-\cw{draw_polygon()}, and as the colour parameter to
-\cw{draw_rect()}, but may not be used as the \c{outlinecolour}
-parameter to \cw{draw_circle()} or \cw{draw_polygon()}, or with
-\cw{draw_line()} or \cw{draw_text()}.
-\S{print-rgb-mono-colour} \cw{print_rgb_mono_colour()}
-\c int print_rgb_mono_colour(drawing *dr, float r, float g,
-\c                           float b, float grey);
-This function allocates a colour index for a fully specified RGB
-colour during printing.
-\c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.
-If printing in black and white only, these values will be ignored,
-and either pure black or pure white will be used instead, according
-to the \q{grey} parameter. (The fallback colour is the same as the
-one which would be allocated by \cw{print_mono_colour(grey)}.)
-\S{print-rgb-grey-colour} \cw{print_rgb_grey_colour()}
-\c int print_rgb_grey_colour(drawing *dr, float r, float g,
-\c                           float b, float grey);
-This function allocates a colour index for a fully specified RGB
-colour during printing.
-\c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.
-If printing in black and white only, these values will be ignored,
-and a shade of grey given by the \c{grey} parameter will be used
-instead. (The fallback colour is the same as the one which would be
-allocated by \cw{print_grey_colour(grey)}.)
-\S{print-rgb-hatched-colour} \cw{print_rgb_hatched_colour()}
-\c int print_rgb_hatched_colour(drawing *dr, float r, float g,
-\c                              float b, float hatched);
-This function allocates a colour index for a fully specified RGB
-colour during printing.
-\c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.
-If printing in black and white only, these values will be ignored,
-and a form of cross-hatching given by the \c{hatch} parameter will
-be used instead; see \k{print-hatched-colour} for the possible
-values of this parameter. (The fallback colour is the same as the
-one which would be allocated by \cw{print_hatched_colour(hatch)}.)
-\S{print-line-width} \cw{print_line_width()}
-\c void print_line_width(drawing *dr, int width);
-This function is called to set the thickness of lines drawn during
-printing. It is meaningless in drawing: all lines drawn by
-\cw{draw_line()}, \cw{draw_circle} and \cw{draw_polygon()} are one
-pixel in thickness. However, in printing there is no clear
-definition of a pixel and so line widths must be explicitly
-specified.
-The line width is specified in the usual coordinate system. Note,
-however, that it is a hint only: the central printing system may
-choose to vary line thicknesses at user request or due to printer
-capabilities.
-\S{print-line-dotted} \cw{print_line_dotted()}
-\c void print_line_dotted(drawing *dr, bool dotted);
-This function is called to toggle the drawing of dotted lines during
-printing. It is not supported during drawing.
-Setting \cq{dotted} to \cw{true} means that future lines drawn by
-\cw{draw_line()}, \cw{draw_circle} and \cw{draw_polygon()} will be
-dotted. Setting it to \cw{false} means that they will be solid.
-Some front ends may impose restrictions on the width of dotted
-lines. Asking for a dotted line via this front end will override any
-line width request if the front end requires it.
-\H{drawing-frontend} The drawing API as implemented by the front end
-This section describes the drawing API in the function-pointer form
-in which it is implemented by a front end.
-(It isn't only platform-specific front ends which implement this
-API; the platform-independent module \c{ps.c} also provides an
-implementation of it which outputs PostScript. Thus, any platform
-which wants to do PS printing can do so with minimum fuss.)
-The following entries all describe function pointer fields in a
-structure called \c{drawing_api}. Each of the functions takes a
-\cq{void *} context pointer, which it should internally cast back to
-a more useful type. Thus, a drawing \e{object} (\c{drawing *)}
-suitable for passing to the back end redraw or printing functions
-is constructed by passing a \c{drawing_api} and a \cq{void *} to the
-function \cw{drawing_new()} (see \k{drawing-new}).
-\S{drawingapi-draw-text} \cw{draw_text()}
-\c void (*draw_text)(void *handle, int x, int y, int fonttype,
-\c                   int fontsize, int align, int colour,
-\c                   const char *text);
-This function behaves exactly like the back end \cw{draw_text()}
-function; see \k{drawing-draw-text}.
-\S{drawingapi-draw-rect} \cw{draw_rect()}
-\c void (*draw_rect)(void *handle, int x, int y, int w, int h,
-\c                   int colour);
-This function behaves exactly like the back end \cw{draw_rect()}
-function; see \k{drawing-draw-rect}.
-\S{drawingapi-draw-line} \cw{draw_line()}
-\c void (*draw_line)(void *handle, int x1, int y1, int x2, int y2,
-\c                   int colour);
-This function behaves exactly like the back end \cw{draw_line()}
-function; see \k{drawing-draw-line}.
-\S{drawingapi-draw-polygon} \cw{draw_polygon()}
-\c void (*draw_polygon)(void *handle, int *coords, int npoints,
-\c                      int fillcolour, int outlinecolour);
-This function behaves exactly like the back end \cw{draw_polygon()}
-function; see \k{drawing-draw-polygon}.
-\S{drawingapi-draw-circle} \cw{draw_circle()}
-\c void (*draw_circle)(void *handle, int cx, int cy, int radius,
-\c                     int fillcolour, int outlinecolour);
-This function behaves exactly like the back end \cw{draw_circle()}
-function; see \k{drawing-draw-circle}.
-\S{drawingapi-draw-thick-line} \cw{draw_thick_line()}
-\c void draw_thick_line(drawing *dr, float thickness,
-\c                      float x1, float y1, float x2, float y2,
-\c                      int colour)
-This function behaves exactly like the back end
-\cw{draw_thick_line()} function; see \k{drawing-draw-thick-line}.
-An implementation of this API which doesn't provide high-quality
-rendering of thick lines is permitted to define this function
-pointer to be \cw{NULL}. The middleware in \cw{drawing.c} will notice
-and provide a low-quality alternative using \cw{draw_polygon()}.
-\S{drawingapi-draw-update} \cw{draw_update()}
-\c void (*draw_update)(void *handle, int x, int y, int w, int h);
-This function behaves exactly like the back end \cw{draw_update()}
-function; see \k{drawing-draw-update}.
-An implementation of this API which only supports printing is
-permitted to define this function pointer to be \cw{NULL} rather
-than bothering to define an empty function. The middleware in
-\cw{drawing.c} will notice and avoid calling it.
-\S{drawingapi-clip} \cw{clip()}
-\c void (*clip)(void *handle, int x, int y, int w, int h);
-This function behaves exactly like the back end \cw{clip()}
-function; see \k{drawing-clip}.
-\S{drawingapi-unclip} \cw{unclip()}
-\c void (*unclip)(void *handle);
-This function behaves exactly like the back end \cw{unclip()}
-function; see \k{drawing-unclip}.
-\S{drawingapi-start-draw} \cw{start_draw()}
-\c void (*start_draw)(void *handle);
-This function is called at the start of drawing. It allows the front
-end to initialise any temporary data required to draw with, such as
-device contexts.
-Implementations of this API which do not provide drawing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless drawing is attempted.
-\S{drawingapi-end-draw} \cw{end_draw()}
-\c void (*end_draw)(void *handle);
-This function is called at the end of drawing. It allows the front
-end to do cleanup tasks such as deallocating device contexts and
-scheduling appropriate GUI redraw events.
-Implementations of this API which do not provide drawing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless drawing is attempted.
-\S{drawingapi-status-bar} \cw{status_bar()}
-\c void (*status_bar)(void *handle, const char *text);
-This function behaves exactly like the back end \cw{status_bar()}
-function; see \k{drawing-status-bar}.
-Front ends implementing this function need not worry about it being
-called repeatedly with the same text; the middleware code in
-\cw{status_bar()} will take care of this.
-Implementations of this API which do not provide drawing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless drawing is attempted.
-\S{drawingapi-blitter-new} \cw{blitter_new()}
-\c blitter *(*blitter_new)(void *handle, int w, int h);
-This function behaves exactly like the back end \cw{blitter_new()}
-function; see \k{drawing-blitter-new}.
-Implementations of this API which do not provide drawing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless drawing is attempted.
-\S{drawingapi-blitter-free} \cw{blitter_free()}
-\c void (*blitter_free)(void *handle, blitter *bl);
-This function behaves exactly like the back end \cw{blitter_free()}
-function; see \k{drawing-blitter-free}.
-Implementations of this API which do not provide drawing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless drawing is attempted.
-\S{drawingapi-blitter-save} \cw{blitter_save()}
-\c void (*blitter_save)(void *handle, blitter *bl, int x, int y);
-This function behaves exactly like the back end \cw{blitter_save()}
-function; see \k{drawing-blitter-save}.
-Implementations of this API which do not provide drawing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless drawing is attempted.
-\S{drawingapi-blitter-load} \cw{blitter_load()}
-\c void (*blitter_load)(void *handle, blitter *bl, int x, int y);
-This function behaves exactly like the back end \cw{blitter_load()}
-function; see \k{drawing-blitter-load}.
-Implementations of this API which do not provide drawing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless drawing is attempted.
-\S{drawingapi-begin-doc} \cw{begin_doc()}
-\c void (*begin_doc)(void *handle, int pages);
-This function is called at the beginning of a printing run. It gives
-the front end an opportunity to initialise any required printing
-subsystem. It also provides the number of pages in advance.
-Implementations of this API which do not provide printing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless printing is attempted.
-\S{drawingapi-begin-page} \cw{begin_page()}
-\c void (*begin_page)(void *handle, int number);
-This function is called during printing, at the beginning of each
-page. It gives the page number (numbered from 1 rather than 0, so
-suitable for use in user-visible contexts).
-Implementations of this API which do not provide printing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless printing is attempted.
-\S{drawingapi-begin-puzzle} \cw{begin_puzzle()}
-\c void (*begin_puzzle)(void *handle, float xm, float xc,
-\c                      float ym, float yc, int pw, int ph, float wmm);
-This function is called during printing, just before printing a
-single puzzle on a page. It specifies the size and location of the
-puzzle on the page.
-\c{xm} and \c{xc} specify the horizontal position of the puzzle on
-the page, as a linear function of the page width. The front end is
-expected to multiply the page width by \c{xm}, add \c{xc} (measured
-in millimetres), and use the resulting x-coordinate as the left edge
-of the puzzle.
-Similarly, \c{ym} and \c{yc} specify the vertical position of the
-puzzle as a function of the page height: the page height times
-\c{ym}, plus \c{yc} millimetres, equals the desired distance from
-the top of the page to the top of the puzzle.
-(This unwieldy mechanism is required because not all printing
-systems can communicate the page size back to the software. The
-PostScript back end, for example, writes out PS which determines the
-page size at print time by means of calling \cq{clippath}, and
-centres the puzzles within that. Thus, exactly the same PS file
-works on A4 or on US Letter paper without needing local
-configuration, which simplifies matters.)
-\cw{pw} and \cw{ph} give the size of the puzzle in drawing API
-coordinates. The printing system will subsequently call the puzzle's
-own print function, which will in turn call drawing API functions in
-the expectation that an area \cw{pw} by \cw{ph} units is available
-to draw the puzzle on.
-Finally, \cw{wmm} gives the desired width of the puzzle in
-millimetres. (The aspect ratio is expected to be preserved, so if
-the desired puzzle height is also needed then it can be computed as
-\cw{wmm*ph/pw}.)
-Implementations of this API which do not provide printing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless printing is attempted.
-\S{drawingapi-end-puzzle} \cw{end_puzzle()}
-\c void (*end_puzzle)(void *handle);
-This function is called after the printing of a specific puzzle is
-complete.
-Implementations of this API which do not provide printing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless printing is attempted.
-\S{drawingapi-end-page} \cw{end_page()}
-\c void (*end_page)(void *handle, int number);
-This function is called after the printing of a page is finished.
-Implementations of this API which do not provide printing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless printing is attempted.
-\S{drawingapi-end-doc} \cw{end_doc()}
-\c void (*end_doc)(void *handle);
-This function is called after the printing of the entire document is
-finished. This is the moment to close files, send things to the
-print spooler, or whatever the local convention is.
-Implementations of this API which do not provide printing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless printing is attempted.
-\S{drawingapi-line-width} \cw{line_width()}
-\c void (*line_width)(void *handle, float width);
-This function is called to set the line thickness, during printing
-only. Note that the width is a \cw{float} here, where it was an
-\cw{int} as seen by the back end. This is because \cw{drawing.c} may
-have scaled it on the way past.
-However, the width is still specified in the same coordinate system
-as the rest of the drawing.
-Implementations of this API which do not provide printing services
-may define this function pointer to be \cw{NULL}; it will never be
-called unless printing is attempted.
-\S{drawingapi-text-fallback} \cw{text_fallback()}
-\c char *(*text_fallback)(void *handle, const char *const *strings,
-\c                        int nstrings);
-This function behaves exactly like the back end \cw{text_fallback()}
-function; see \k{drawing-text-fallback}.
-Implementations of this API which do not support any characters
-outside ASCII may define this function pointer to be \cw{NULL}, in
-which case the central code in \cw{drawing.c} will provide a default
-implementation.
-\H{drawingapi-frontend} The drawing API as called by the front end
-There are a small number of functions provided in \cw{drawing.c}
-which the front end needs to \e{call}, rather than helping to
-implement. They are described in this section.
-\S{drawing-new} \cw{drawing_new()}
-\c drawing *drawing_new(const drawing_api *api, midend *me,
-\c                      void *handle);
-This function creates a drawing object. It is passed a
-\c{drawing_api}, which is a structure containing nothing but
-function pointers; and also a \cq{void *} handle. The handle is
-passed back to each function pointer when it is called.
-The \c{midend} parameter is used for rewriting the status bar
-contents: \cw{status_bar()} (see \k{drawing-status-bar}) has to call
-a function in the mid-end which might rewrite the status bar text.
-If the drawing object is to be used only for printing, or if the
-game is known not to call \cw{status_bar()}, this parameter may be
-\cw{NULL}.
-\S{drawing-free} \cw{drawing_free()}
-\c void drawing_free(drawing *dr);
-This function frees a drawing object. Note that the \cq{void *}
-handle is not freed; if that needs cleaning up it must be done by
-the front end.
-\S{drawing-print-get-colour} \cw{print_get_colour()}
-\c void print_get_colour(drawing *dr, int colour, int printincolour,
-\c                       int *hatch, float *r, float *g, float *b)
-This function is called by the implementations of the drawing API
-functions when they are called in a printing context. It takes a
-colour index as input, and returns the description of the colour as
-requested by the back end.
-\c{printincolour} is \cw{TRUE} iff the implementation is printing in
-colour. This will alter the results returned if the colour in
-question was specified with a black-and-white fallback value.
-If the colour should be rendered by hatching, \c{*hatch} is filled
-with the type of hatching desired. See \k{print-grey-colour} for
-details of the values this integer can take.
-If the colour should be rendered as solid colour, \c{*hatch} is
-given a negative value, and \c{*r}, \c{*g} and \c{*b} are filled
-with the RGB values of the desired colour (if printing in colour),
-or all filled with the grey-scale value (if printing in black and
-white).
-\C{midend} The API provided by the mid-end
-This chapter documents the API provided by the mid-end to be called
-by the front end. You probably only need to read this if you are a
-front end implementor, i.e. you are porting Puzzles to a new
-platform. If you're only interested in writing new puzzles, you can
-safely skip this chapter.
-All the persistent state in the mid-end is encapsulated within a
-\c{midend} structure, to facilitate having multiple mid-ends in any
-port which supports multiple puzzle windows open simultaneously.
-Each \c{midend} is intended to handle the contents of a single
-puzzle window.
-\H{midend-new} \cw{midend_new()}
-\c midend *midend_new(frontend *fe, const game *ourgame,
-\c                    const drawing_api *drapi, void *drhandle)
-Allocates and returns a new mid-end structure.
-The \c{fe} argument is stored in the mid-end. It will be used when
-calling back to functions such as \cw{activate_timer()}
-(\k{frontend-activate-timer}), and will be passed on to the back end
-function \cw{colours()} (\k{backend-colours}).
-The parameters \c{drapi} and \c{drhandle} are passed to
-\cw{drawing_new()} (\k{drawing-new}) to construct a drawing object
-which will be passed to the back end function \cw{redraw()}
-(\k{backend-redraw}). Hence, all drawing-related function pointers
-defined in \c{drapi} can expect to be called with \c{drhandle} as
-their first argument.
-The \c{ourgame} argument points to a container structure describing
-a game back end. The mid-end thus created will only be capable of
-handling that one game. (So even in a monolithic front end
-containing all the games, this imposes the constraint that any
-individual puzzle window is tied to a single game. Unless, of
-course, you feel brave enough to change the mid-end for the window
-without closing the window...)
-\H{midend-free} \cw{midend_free()}
-\c void midend_free(midend *me);
-Frees a mid-end structure and all its associated data.
-\H{midend-tilesize} \cw{midend_tilesize()}
-\c int midend_tilesize(midend *me);
-Returns the \cq{tilesize} parameter being used to display the
-current puzzle (\k{backend-preferred-tilesize}).
-\H{midend-set-params} \cw{midend_set_params()}
-\c void midend_set_params(midend *me, game_params *params);
-Sets the current game parameters for a mid-end. Subsequent games
-generated by \cw{midend_new_game()} (\k{midend-new-game}) will use
-these parameters until further notice.
-The usual way in which the front end will have an actual
-\c{game_params} structure to pass to this function is if it had
-previously got it from \cw{midend_get_presets()}
-(\k{midend-get-presets}). Thus, this function is usually called in
-response to the user making a selection from the presets menu.
-\H{midend-get-params} \cw{midend_get_params()}
-\c game_params *midend_get_params(midend *me);
-Returns the current game parameters stored in this mid-end.
-The returned value is dynamically allocated, and should be freed
-when finished with by passing it to the game's own
-\cw{free_params()} function (see \k{backend-free-params}).
-\H{midend-size} \cw{midend_size()}
-\c void midend_size(midend *me, int *x, int *y, bool user_size);
-Tells the mid-end to figure out its window size.
-On input, \c{*x} and \c{*y} should contain the maximum or requested
-size for the window. (Typically this will be the size of the screen
-that the window has to fit on, or similar.) The mid-end will
-repeatedly call the back end function \cw{compute_size()}
-(\k{backend-compute-size}), searching for a tile size that best
-satisfies the requirements. On exit, \c{*x} and \c{*y} will contain
-the size needed for the puzzle window's drawing area. (It is of
-course up to the front end to adjust this for any additional window
-furniture such as menu bars and window borders, if necessary. The
-status bar is also not included in this size.)
-Use \c{user_size} to indicate whether \c{*x} and \c{*y} are a
-requested size, or just a maximum size.
-If \c{user_size} is set to \cw{true}, the mid-end will treat the
-input size as a request, and will pick a tile size which
-approximates it \e{as closely as possible}, going over the game's
-preferred tile size if necessary to achieve this. The mid-end will
-also use the resulting tile size as its preferred one until further
-notice, on the assumption that this size was explicitly requested
-by the user. Use this option if you want your front end to support
-dynamic resizing of the puzzle window with automatic scaling of the
-puzzle to fit.
-If \c{user_size} is set to \cw{FALSE}, then the game's tile size
-will never go over its preferred one, although it may go under in
-order to fit within the maximum bounds specified by \c{*x} and
-\c{*y}. This is the recommended approach when opening a new window
-at default size: the game will use its preferred size unless it has
-to use a smaller one to fit on the screen. If the tile size is
-shrunk for this reason, the change will not persist; if a smaller
-grid is subsequently chosen, the tile size will recover.
-The mid-end will try as hard as it can to return a size which is
-less than or equal to the input size, in both dimensions. In extreme
-circumstances it may fail (if even the lowest possible tile size
-gives window dimensions greater than the input), in which case it
-will return a size greater than the input size. Front ends should be
-prepared for this to happen (i.e. don't crash or fail an assertion),
-but may handle it in any way they see fit: by rejecting the game
-parameters which caused the problem, by opening a window larger than
-the screen regardless of inconvenience, by introducing scroll bars
-on the window, by drawing on a large bitmap and scaling it into a
-smaller window, or by any other means you can think of. It is likely
-that when the tile size is that small the game will be unplayable
-anyway, so don't put \e{too} much effort into handling it
-creatively.
-If your platform has no limit on window size (or if you're planning
-to use scroll bars for large puzzles), you can pass dimensions of
-\cw{INT_MAX} as input to this function. You should probably not do
-that \e{and} set the \c{user_size} flag, though!
-The midend relies on the frontend calling \cw{midend_new_game()}
-(\k{midend-new-game}) before calling \cw{midend_size()}.
-\H{midend-reset-tilesize} \cw{midend_reset_tilesize()}
-\c void midend_reset_tilesize(midend *me);
-This function resets the midend's preferred tile size to that of the
-standard puzzle.
-As discussed in \k{midend-size}, puzzle resizes are typically
-'sticky', in that once the user has dragged the puzzle to a different
-window size, the resulting tile size will be remembered and used when
-the puzzle configuration changes. If you \e{don't} want that, e.g. if
-you want to provide a command to explicitly reset the puzzle size back
-to its default, then you can call this just before calling
-\cw{midend_size()} (which, in turn, you would probably call with
-\c{user_size} set to \cw{FALSE}).
-\H{midend-new-game} \cw{midend_new_game()}
-\c void midend_new_game(midend *me);
-Causes the mid-end to begin a new game. Normally the game will be a
-new randomly generated puzzle. However, if you have previously
-called \cw{midend_game_id()} or \cw{midend_set_config()}, the game
-generated might be dictated by the results of those functions. (In
-particular, you \e{must} call \cw{midend_new_game()} after calling
-either of those functions, or else no immediate effect will be
-visible.)
-You will probably need to call \cw{midend_size()} after calling this
-function, because if the game parameters have been changed since the
-last new game then the window size might need to change. (If you
-know the parameters \e{haven't} changed, you don't need to do this.)
-This function will create a new \c{game_drawstate}, but does not
-actually perform a redraw (since you often need to call
-\cw{midend_size()} before the redraw can be done). So after calling
-this function and after calling \cw{midend_size()}, you should then
-call \cw{midend_redraw()}. (It is not necessary to call
-\cw{midend_force_redraw()}; that will discard the draw state and
-create a fresh one, which is unnecessary in this case since there's
-a fresh one already. It would work, but it's usually excessive.)
-\H{midend-restart-game} \cw{midend_restart_game()}
-\c void midend_restart_game(midend *me);
-This function causes the current game to be restarted. This is done
-by placing a new copy of the original game state on the end of the
-undo list (so that an accidental restart can be undone).
-This function automatically causes a redraw, i.e. the front end can
-expect its drawing API to be called from \e{within} a call to this
-function. Some back ends require that \cw{midend_size()}
-(\k{midend-size}) is called before \cw{midend_restart_game()}.
-\H{midend-force-redraw} \cw{midend_force_redraw()}
-\c void midend_force_redraw(midend *me);
-Forces a complete redraw of the puzzle window, by means of
-discarding the current \c{game_drawstate} and creating a new one
-from scratch before calling the game's \cw{redraw()} function.
-The front end can expect its drawing API to be called from within a
-call to this function. Some back ends require that \cw{midend_size()}
-(\k{midend-size}) is called before \cw{midend_force_redraw()}.
-\H{midend-redraw} \cw{midend_redraw()}
-\c void midend_redraw(midend *me);
-Causes a partial redraw of the puzzle window, by means of simply
-calling the game's \cw{redraw()} function. (That is, the only things
-redrawn will be things that have changed since the last redraw.)
-The front end can expect its drawing API to be called from within a
-call to this function. Some back ends require that \cw{midend_size()}
-(\k{midend-size}) is called before \cw{midend_redraw()}.
-\H{midend-process-key} \cw{midend_process_key()}
-\c bool midend_process_key(midend *me, int x, int y, int button);
-The front end calls this function to report a mouse or keyboard
-event. The parameters \c{x}, \c{y} and \c{button} are almost
-identical to the ones passed to the back end function
-\cw{interpret_move()} (\k{backend-interpret-move}), except that the
-front end is \e{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,
-\cw{LEFT_DRAG} events and start receiving \cw{RIGHT_DRAG}s, with no
-intervening button release or press events. This too is something
-which the mid-end will sort out for you; the front end has no
-obligation to maintain sanity in this area.)
-The front end \e{should}, however, always eventually send some kind
-of button release. On some platforms this requires special effort:
-Windows, for example, requires a call to the system API function
-\cw{SetCapture()} in order to ensure that your window receives a
-mouse-up event even if the pointer has left the window by the time
-the mouse button is released. On any platform that requires this
-sort of thing, the front end \e{is} responsible for doing it.
-Calling this function is very likely to result in calls back to the
-front end's drawing API and/or \cw{activate_timer()}
-(\k{frontend-activate-timer}).
-The return value from \cw{midend_process_key()} is \cw{true} 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 \cw{false}
-return.
-\H{midend-request-keys} \cw{midend_request_keys()}
-\c key_label *midend_request_keys(midend *me, int *nkeys);
-This function behaves similarly to the backend's \cw{request_keys()}
-function (\k{backend-request-keys}). If the backend does not provide
-\cw{request_keys()}, this function will return \cw{NULL} and set
-\cw{*nkeys} to zero. Otherwise, this function will fill in the generic
-labels (i.e. the \cw{key_label} items that have their \cw{label}
-fields set to \cw{NULL}) by using \cw{button2label()}
-(\k{utils-button2label}).
-\H{midend-colours} \cw{midend_colours()}
-\c float *midend_colours(midend *me, int *ncolours);
-Returns an array of the colours required by the game, in exactly the
-same format as that returned by the back end function \cw{colours()}
-(\k{backend-colours}). Front ends should call this function rather
-than calling the back end's version directly, since the mid-end adds
-standard customisation facilities. (At the time of writing, those
-customisation facilities are implemented hackily by means of
-environment variables, but it's not impossible that they may become
-more full and formal in future.)
-\H{midend-timer} \cw{midend_timer()}
-\c void midend_timer(midend *me, float tplus);
-If the mid-end has called \cw{activate_timer()}
-(\k{frontend-activate-timer}) to request regular callbacks for
-purposes of animation or timing, this is the function the front end
-should call on a regular basis. The argument \c{tplus} gives the
-time, in seconds, since the last time either this function was
-called or \cw{activate_timer()} was invoked.
-One of the major purposes of timing in the mid-end is to perform
-move animation. Therefore, calling this function is very likely to
-result in calls back to the front end's drawing API.
-\H{midend-get-presets} \cw{midend_get_presets()}
-\c struct preset_menu *midend_get_presets(midend *me, int *id_limit);
-Returns a data structure describing this game's collection of preset
-game parameters, organised into a hierarchical structure of menus and
-submenus.
-The return value is a pointer to a data structure containing the
-following fields (among others, which are not intended for front end
-use):
-\c struct preset_menu {
-\c     int n_entries;
-\c     struct preset_menu_entry *entries;
-\c     /* and other things */
-\e     iiiiiiiiiiiiiiiiiiiiii
-\c };
-Those fields describe the intended contents of one particular menu in
-the hierarchy. \cq{entries} points to an array of \cq{n_entries}
-items, each of which is a structure containing the following fields:
-\c struct preset_menu_entry {
-\c     char *title;
-\c     game_params *params;
-\c     struct preset_menu *submenu;
-\c     int id;
-\c };
-Of these fields, \cq{title} and \cq{id} are present in every entry,
-giving (respectively) the textual name of the menu item and an integer
-identifier for it. The integer id will correspond to the one returned
-by \c{midend_which_preset} (\k{midend-which-preset}), when that preset
-is the one selected.
-The other two fields are mutually exclusive. Each \c{struct
-preset_menu_entry} will have one of those fields \cw{NULL} and the
-other one non-null. If the menu item is an actual preset, then
-\cq{params} will point to the set of game parameters that go with the
-name; if it's a submenu, then \cq{submenu} instead will be non-null,
-and will point at a subsidiary \c{struct preset_menu}.
-The complete hierarchy of these structures is owned by the mid-end,
-and will be freed when the mid-end is freed. The front end should not
-attempt to free any of it.
-The integer identifiers will be allocated densely from 0 upwards, so
-that it's reasonable for the front end to allocate an array which uses
-them as indices, if it needs to store information per preset menu
-item. For this purpose, the front end may pass the second parameter
-\cq{id_limit} to \cw{midend_get_presets} as the address of an \c{int}
-variable, into which \cw{midend_get_presets} will write an integer one
-larger than the largest id number actually used (i.e. the number of
-elements the front end would need in the array).
-Submenu-type entries also have integer identifiers.
-\H{midend-which-preset} \cw{midend_which_preset()}
-\c int midend_which_preset(midend *me);
-Returns the numeric index of the preset game parameter structure
-which matches the current game parameters, or a negative number if
-no preset matches. Front ends could use this to maintain a tick
-beside one of the items in the menu (or tick the \q{Custom} option
-if the return value is less than zero).
-The returned index value (if non-negative) will match the \c{id} field
-of the corresponding \cw{struct preset_menu_entry} returned by
-\c{midend_get_presets()} (\k{midend-get-presets}).
-\H{midend-wants-statusbar} \cw{midend_wants_statusbar()}
-\c bool midend_wants_statusbar(midend *me);
-This function returns \cw{true} if the puzzle has a use for a
-textual status line (to display score, completion status, currently
-active tiles, time, or anything else).
-Front ends should call this function rather than talking directly to
-the back end.
-\H{midend-get-config} \cw{midend_get_config()}
-\c config_item *midend_get_config(midend *me, int which,
-\c                                char **wintitle);
-Returns a dialog box description for user configuration.
-On input, \cw{which} should be set to one of three values, which
-select which of the various dialog box descriptions is returned:
-\dt \cw{CFG_SETTINGS}
-\dd Requests the GUI parameter configuration box generated by the
-puzzle itself. This should be used when the user selects \q{Custom}
-from the game types menu (or equivalent). The mid-end passes this
-request on to the back end function \cw{configure()}
-(\k{backend-configure}).
-\dt \cw{CFG_DESC}
-\dd Requests a box suitable for entering a descriptive game ID (and
-viewing the existing one). The mid-end generates this dialog box
-description itself. This should be used when the user selects
-\q{Specific} from the game menu (or equivalent).
-\dt \cw{CFG_SEED}
-\dd Requests a box suitable for entering a random-seed game ID (and
-viewing the existing one). The mid-end generates this dialog box
-description itself. This should be used when the user selects
-\q{Random Seed} from the game menu (or equivalent).
-The returned value is an array of \cw{config_item}s, exactly as
-described in \k{backend-configure}. Another returned value is an
-ASCII string giving a suitable title for the configuration window,
-in \c{*wintitle}.
-Both returned values are dynamically allocated and will need to be
-freed. The window title can be freed in the obvious way; the
-\cw{config_item} array is a slightly complex structure, so a utility
-function \cw{free_cfg()} is provided to free it for you. See
-\k{utils-free-cfg}.
-(Of course, you will probably not want to free the \cw{config_item}
-array until the dialog box is dismissed, because before then you
-will probably need to pass it to \cw{midend_set_config}.)
-\H{midend-set-config} \cw{midend_set_config()}
-\c const char *midend_set_config(midend *me, int which,
-\c                               config_item *cfg);
-Passes the mid-end the results of a configuration dialog box.
-\c{which} should have the same value which it had when
-\cw{midend_get_config()} was called; \c{cfg} should be the array of
-\c{config_item}s returned from \cw{midend_get_config()}, modified to
-contain the results of the user's editing operations.
-This function returns \cw{NULL} on success, or otherwise (if the
-configuration data was in some way invalid) an ASCII string
-containing an error message suitable for showing to the user.
-If the function succeeds, it is likely that the game parameters will
-have been changed and it is certain that a new game will be
-requested. The front end should therefore call
-\cw{midend_new_game()}, and probably also re-think the window size
-using \cw{midend_size()} and eventually perform a refresh using
-\cw{midend_redraw()}.
-\H{midend-game-id} \cw{midend_game_id()}
-\c const char *midend_game_id(midend *me, const char *id);
-Passes the mid-end a string game ID (of any of the valid forms
-\cq{params}, \cq{params:description} or \cq{params#seed}) which the
-mid-end will process and use for the next generated game.
-This function returns \cw{NULL} on success, or otherwise (if the
-configuration data was in some way invalid) an ASCII string
-containing an error message (not dynamically allocated) suitable for
-showing to the user. In the event of an error, the mid-end's
-internal state will be left exactly as it was before the call.
-If the function succeeds, it is likely that the game parameters will
-have been changed and it is certain that a new game will be
-requested. The front end should therefore call
-\cw{midend_new_game()}, and probably also re-think the window size
-using \cw{midend_size()} and eventually case a refresh using
-\cw{midend_redraw()}.
-\H{midend-get-game-id} \cw{midend_get_game_id()}
-\c char *midend_get_game_id(midend *me)
-Returns a descriptive game ID (i.e. one in the form
-\cq{params:description}) describing the game currently active in the
-mid-end. The returned string is dynamically allocated.
-\H{midend-get-random-seed} \cw{midend_get_random_seed()}
-\c char *midend_get_random_seed(midend *me)
-Returns a random game ID (i.e. one in the form \cq{params#seedstring})
-describing the game currently active in the mid-end, if there is one.
-If the game was created by entering a description, no random seed will
-currently exist and this function will return \cw{NULL}.
-The returned string, if it is non-\cw{NULL}, is dynamically allocated.
-\H{midend-can-format-as-text-now} \cw{midend_can_format_as_text_now()}
-\c bool midend_can_format_as_text_now(midend *me);
-Returns \cw{true} if the game code is capable of formatting puzzles
-of the currently selected game type as ASCII.
-If this returns \cw{false}, then \cw{midend_text_format()}
-(\k{midend-text-format}) will return \cw{NULL}.
-\H{midend-text-format} \cw{midend_text_format()}
-\c char *midend_text_format(midend *me);
-Formats the current game's current state as ASCII text suitable for
-copying to the clipboard. The returned string is dynamically
-allocated.
-If the game's \c{can_format_as_text_ever} flag is \cw{FALSE}, or if
-its \cw{can_format_as_text_now()} function returns \cw{FALSE}, then
-this function will return \cw{NULL}.
-If the returned string contains multiple lines (which is likely), it
-will use the normal C line ending convention (\cw{\\n} only). On
-platforms which use a different line ending convention for data in
-the clipboard, it is the front end's responsibility to perform the
-conversion.
-\H{midend-solve} \cw{midend_solve()}
-\c const char *midend_solve(midend *me);
-Requests the mid-end to perform a Solve operation.
-On success, \cw{NULL} is returned. On failure, an error message (not
-dynamically allocated) is returned, suitable for showing to the
-user.
-The front end can expect its drawing API and/or
-\cw{activate_timer()} to be called from within a call to this
-function.  Some back ends require that \cw{midend_size()}
-(\k{midend-size}) is called before \cw{midend_solve()}.
-\H{midend-get-cursor-location} \cw{midend_get_cursor_location()}
-\c bool midend_get_cursor_location(midend *me,
-\c                                 int *x, int *y,
-\c                                 int *w, int *h);
-This function requests the location of the back end's on-screen cursor
-or other region of interest.
-What exactly this region contains is up to the backend, but in general
-the region will be an area that the player is controlling with the
-cursor keys \dash such as the player location in Cube and Inertia, or
-the cursor in any of the conventional grid-based games. With knowledge
-of this location, a front end can, for example, ensure that the region
-of interest remains visible even if the entire puzzle is too big to
-fit on the screen.
-On success, this function returns \cw{true}, and the locations pointed
-to by \cw{x}, \cw{y}, \cw{w} and \cw{h} are updated to describe the
-cursor region, which has an upper-left corner located at \cw{(*x,*y)}
-and a size of \cw{*w} pixels wide by \cw{*h} pixels tall. The caller
-may pass \cw{NULL} for any number of these pointers, which will be
-ignored.
-On failure, this function returns \cw{false}. Failure can occur if
-there is currently no active cursor region, or if the back end lacks
-cursor support.
-\H{midend-status} \cw{midend_status()}
-\c int midend_status(midend *me);
-This function returns +1 if the midend is currently displaying a game
-in a solved state, -1 if the game is in a permanently lost state, or 0
-otherwise. This function just calls the back end's \cw{status()}
-function. Front ends may wish to use this as a cue to proactively
-offer the option of starting a new game.
-(See \k{backend-status} for more detail about the back end's
-\cw{status()} function and discussion of what should count as which
-status code.)
-\H{midend-can-undo} \cw{midend_can_undo()}
-\c bool midend_can_undo(midend *me);
-Returns \cw{true} if the midend is currently in a state where the undo
-operation is meaningful (i.e. at least one position exists on the undo
-chain before the present one). Front ends may wish to use this to
-visually activate and deactivate an undo button.
-\H{midend-can-redo} \cw{midend_can_redo()}
-\c bool midend_can_redo(midend *me);
-Returns \cw{true} if the midend is currently in a state where the redo
-operation is meaningful (i.e. at least one position exists on the redo
-chain after the present one). Front ends may wish to use this to
-visually activate and deactivate a redo button.
-\H{midend-serialise} \cw{midend_serialise()}
-\c void midend_serialise(midend *me,
-\c     void (*write)(void *ctx, const void *buf, int len), void *wctx);
-Calling this function causes the mid-end to convert its entire
-internal state into a long ASCII text string, and to pass that
-string (piece by piece) to the supplied \c{write} function.
-Desktop implementations can use this function to save a game in any
-state (including half-finished) to a disk file, by supplying a
-\c{write} function which is a wrapper on \cw{fwrite()} (or local
-equivalent). Other implementations may find other uses for it, such
-as compressing the large and sprawling mid-end state into a
-manageable amount of memory when a palmtop application is suspended
-so that another one can run; in this case \cw{write} might want to
-write to a memory buffer rather than a file. There may be other uses
-for it as well.
-This function will call back to the supplied \c{write} function a
-number of times, with the first parameter (\c{ctx}) equal to
-\c{wctx}, and the other two parameters pointing at a piece of the
-output string.
-\H{midend-deserialise} \cw{midend_deserialise()}
-\c const char *midend_deserialise(midend *me,
-\c     bool (*read)(void *ctx, void *buf, int len), void *rctx);
-This function is the counterpart to \cw{midend_serialise()}. It
-calls the supplied \cw{read} function repeatedly to read a quantity
-of data, and attempts to interpret that data as a serialised mid-end
-as output by \cw{midend_serialise()}.
-The \cw{read} function is called with the first parameter (\c{ctx})
-equal to \c{rctx}, and should attempt to read \c{len} bytes of data
-into the buffer pointed to by \c{buf}. It should return \cw{false}
-on failure or \cw{true} on success. It should not report success
-unless it has filled the entire buffer; on platforms which might be
-reading from a pipe or other blocking data source, \c{read} is
-responsible for looping until the whole buffer has been filled.
-If the de-serialisation operation is successful, the mid-end's
-internal data structures will be replaced by the results of the
-load, and \cw{NULL} will be returned. Otherwise, the mid-end's state
-will be completely unchanged and an error message (typically some
-variation on \q{save file is corrupt}) will be returned. As usual,
-the error message string is not dynamically allocated.
-If this function succeeds, it is likely that the game parameters
-will have been changed. The front end should therefore probably
-re-think the window size using \cw{midend_size()}, and probably
-cause a refresh using \cw{midend_redraw()}.
-Because each mid-end is tied to a specific game back end, this
-function will fail if you attempt to read in a save file generated by
-a different game from the one configured in this mid-end, even if your
-application is a monolithic one containing all the puzzles. See
-\k{identify-game} for a helper function which will allow you to
-identify a save file before you instantiate your mid-end in the first
-place.
-\H{identify-game} \cw{identify_game()}
-\c const char *identify_game(char **name,
-\c     bool (*read)(void *ctx, void *buf, int len), void *rctx);
-This function examines a serialised midend stream, of the same kind
-used by \cw{midend_serialise()} and \cw{midend_deserialise()}, and
-returns the \cw{name} field of the game back end from which it was
-saved.
-You might want this if your front end was a monolithic one containing
-all the puzzles, and you wanted to be able to load an arbitrary save
-file and automatically switch to the right game. Probably your next
-step would be to iterate through \cw{gamelist} (\k{frontend-backend})
-looking for a game structure whose \cw{name} field matched the
-returned string, and give an error if you didn't find one.
-On success, the return value of this function is \cw{NULL}, and the
-game name string is written into \cw{*name}. The caller should free
-that string after using it.
-On failure, \cw{*name} is \cw{NULL}, and the return value is an error
-message (which does not need freeing at all).
-(This isn't strictly speaking a midend function, since it doesn't
-accept or return a pointer to a midend. You'd probably call it just
-\e{before} deciding what kind of midend you wanted to instantiate.)
-\H{midend-request-id-changes} \cw{midend_request_id_changes()}
-\c void midend_request_id_changes(midend *me,
-\c                                void (*notify)(void *), void *ctx);
-This function is called by the front end to request notification by
-the mid-end when the current game IDs (either descriptive or
-random-seed) change. This can occur as a result of keypresses ('n' for
-New Game, for example) or when a puzzle supersedes its game
-description (see \k{backend-supersede}). After this function is
-called, any change of the game ids will cause the mid-end to call
-\cw{notify(ctx)} after the change.
-This is for use by puzzles which want to present the game description
-to the user constantly (e.g. as an HTML hyperlink) instead of only
-showing it when the user explicitly requests it.
-This is a function I anticipate few front ends needing to implement,
-so I make it a callback rather than a static function in order to
-relieve most front ends of the need to provide an empty
-implementation.
-\H{frontend-backend} Direct reference to the back end structure by
-the front end
-Although \e{most} things the front end needs done should be done by
-calling the mid-end, there are a few situations in which the front
-end needs to refer directly to the game back end structure.
-The most obvious of these is
-\b passing the game back end as a parameter to \cw{midend_new()}.
-There are a few other back end features which are not wrapped by the
-mid-end because there didn't seem much point in doing so:
-\b fetching the \c{name} field to use in window titles and similar
-\b reading the \c{can_configure}, \c{can_solve} and
-\c{can_format_as_text_ever} fields to decide whether to add those
-items to the menu bar or equivalent
-\b reading the \c{winhelp_topic} field (Windows only)
-\b the GTK front end provides a \cq{--generate} command-line option
-which directly calls the back end to do most of its work. This is
-not really part of the main front end code, though, and I'm not sure
-it counts.
-In order to find the game back end structure, the front end does one
-of two things:
-\b If the particular front end is compiling a separate binary per
-game, then the back end structure is a global variable with the
-standard name \cq{thegame}:
-\lcont{
-\c extern const game thegame;
-}
-\b If the front end is compiled as a monolithic application
-containing all the puzzles together (in which case the preprocessor
-symbol \cw{COMBINED} must be defined when compiling most of the code
-base), then there will be two global variables defined:
-\lcont{
-\c extern const game *gamelist[];
-\c extern const int gamecount;
-\c{gamelist} will be an array of \c{gamecount} game structures,
-declared in the automatically constructed source module \c{list.c}.
-The application should search that array for the game it wants,
-probably by reaching into each game structure and looking at its
-\c{name} field.
-}
-\H{frontend-api} Mid-end to front-end calls
-This section describes the small number of functions which a front
-end must provide to be called by the mid-end or other standard
-utility modules.
-\H{frontend-get-random-seed} \cw{get_random_seed()}
-\c void get_random_seed(void **randseed, int *randseedsize);
-This function is called by a new mid-end, and also occasionally by
-game back ends. Its job is to return a piece of data suitable for
-using as a seed for initialisation of a new \c{random_state}.
-On exit, \c{*randseed} should be set to point at a newly allocated
-piece of memory containing some seed data, and \c{*randseedsize}
-should be set to the length of that data.
-A simple and entirely adequate implementation is to return a piece
-of data containing the current system time at the highest
-conveniently available resolution.
-\H{frontend-activate-timer} \cw{activate_timer()}
-\c void activate_timer(frontend *fe);
-This is called by the mid-end to request that the front end begin
-calling it back at regular intervals.
-The timeout interval is left up to the front end; the finer it is,
-the smoother move animations will be, but the more CPU time will be
-used. Current front ends use values around 20ms (i.e. 50Hz).
-After this function is called, the mid-end will expect to receive
-calls to \cw{midend_timer()} on a regular basis.
-\H{frontend-deactivate-timer} \cw{deactivate_timer()}
-\c void deactivate_timer(frontend *fe);
-This is called by the mid-end to request that the front end stop
-calling \cw{midend_timer()}.
-\H{frontend-fatal} \cw{fatal()}
-\c void fatal(const char *fmt, ...);
-This is called by some utility functions if they encounter a
-genuinely fatal error such as running out of memory. It is a
-variadic function in the style of \cw{printf()}, and is expected to
-show the formatted error message to the user any way it can and then
-terminate the application. It must not return.
-\H{frontend-default-colour} \cw{frontend_default_colour()}
-\c void frontend_default_colour(frontend *fe, float *output);
-This function expects to be passed a pointer to an array of three
-\cw{float}s. It returns the platform's local preferred background
-colour in those three floats, as red, green and blue values (in that
-order) ranging from \cw{0.0} to \cw{1.0}.
-This function should only ever be called by the back end function
-\cw{colours()} (\k{backend-colours}). (Thus, it isn't a
-\e{midend}-to-frontend function as such, but there didn't seem to be
-anywhere else particularly good to put it. Sorry.)
-\C{utils} Utility APIs
-This chapter documents a variety of utility APIs provided for the
-general use of the rest of the Puzzles code.
-\H{utils-random} Random number generation
-Platforms' local random number generators vary widely in quality and
-seed size. Puzzles therefore supplies its own high-quality random
-number generator, with the additional advantage of giving the same
-results if fed the same seed data on different platforms. This
-allows game random seeds to be exchanged between different ports of
-Puzzles and still generate the same games.
-Unlike the ANSI C \cw{rand()} function, the Puzzles random number
-generator has an \e{explicit} state object called a
-\c{random_state}. One of these is managed by each mid-end, for
-example, and passed to the back end to generate a game with.
-\S{utils-random-init} \cw{random_new()}
-\c random_state *random_new(char *seed, int len);
-Allocates, initialises and returns a new \c{random_state}. The input
-data is used as the seed for the random number stream (i.e. using
-the same seed at a later time will generate the same stream).
-The seed data can be any data at all; there is no requirement to use
-printable ASCII, or NUL-terminated strings, or anything like that.
-\S{utils-random-copy} \cw{random_copy()}
-\c random_state *random_copy(random_state *tocopy);
-Allocates a new \c{random_state}, copies the contents of another
-\c{random_state} into it, and returns the new state.  If exactly the
-same sequence of functions is 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.
-\S{utils-random-free} \cw{random_free()}
-\c void random_free(random_state *state);
-Frees a \c{random_state}.
-\S{utils-random-bits} \cw{random_bits()}
-\c unsigned long random_bits(random_state *state, int bits);
-Returns a random number from 0 to \cw{2^bits-1} inclusive. \c{bits}
-should be between 1 and 32 inclusive.
-\S{utils-random-upto} \cw{random_upto()}
-\c unsigned long random_upto(random_state *state, unsigned long limit);
-Returns a random number from 0 to \cw{limit-1} inclusive.
-\S{utils-random-state-encode} \cw{random_state_encode()}
-\c char *random_state_encode(random_state *state);
-Encodes the entire contents of a \c{random_state} in printable
-ASCII. Returns a dynamically allocated string containing that
-encoding. This can subsequently be passed to
-\cw{random_state_decode()} to reconstruct the same \c{random_state}.
-\S{utils-random-state-decode} \cw{random_state_decode()}
-\c random_state *random_state_decode(char *input);
-Decodes a string generated by \cw{random_state_encode()} and
-reconstructs an equivalent \c{random_state} to the one encoded, i.e.
-it should produce the same stream of random numbers.
-This function has no error reporting; if you pass it an invalid
-string it will simply generate an arbitrary random state, which may
-turn out to be noticeably non-random.
-\S{utils-shuffle} \cw{shuffle()}
-\c void shuffle(void *array, int nelts, int eltsize, random_state *rs);
-Shuffles an array into a random order. The interface is much like
-ANSI C \cw{qsort()}, except that there's no need for a compare
-function.
-\c{array} is a pointer to the first element of the array. \c{nelts}
-is the number of elements in the array; \c{eltsize} is the size of a
-single element (typically measured using \c{sizeof}). \c{rs} is a
-\c{random_state} used to generate all the random numbers for the
-shuffling process.
-\H{utils-presets} Presets menu management
-The function \c{midend_get_presets()} (\k{midend-get-presets}) returns
-a data structure describing a menu hierarchy. Back ends can also
-choose to provide such a structure to the mid-end, if they want to
-group their presets hierarchically. To make this easy, there are a few
-utility functions to construct preset menu structures, and also one
-intended for front-end use.
-\S{utils-preset-menu-new} \cw{preset_menu_new()}
-\c struct preset_menu *preset_menu_new(void);
-Allocates a new \c{struct preset_menu}, and initialises it to hold no
-menu items.
-\S{utils-preset-menu-add_submenu} \cw{preset_menu_add_submenu()}
-\c struct preset_menu *preset_menu_add_submenu
-\c     (struct preset_menu *parent, char *title);
-Adds a new submenu to the end of an existing preset menu, and returns
-a pointer to a newly allocated \c{struct preset_menu} describing the
-submenu.
-The string parameter \cq{title} must be dynamically allocated by the
-caller. The preset-menu structure will take ownership of it, so the
-caller must not free it.
-\S{utils-preset-menu-add-preset} \cw{preset_menu_add_preset()}
-\c void preset_menu_add_preset
-\c     (struct preset_menu *menu, char *title, game_params *params);
-Adds a preset game configuration to the end of a preset menu.
-Both the string parameter \cq{title} and the game parameter structure
-\cq{params} itself must be dynamically allocated by the caller. The
-preset-menu structure will take ownership of it, so the caller must
-not free it.
-\S{utils-preset-menu-lookup-by-id} \cw{preset_menu_lookup_by_id()}
-\c game_params *preset_menu_lookup_by_id
-\c     (struct preset_menu *menu, int id);
-Given a numeric index, searches recursively through a preset menu
-hierarchy to find the corresponding menu entry, and returns a pointer
-to its existing \c{game_params} structure.
-This function is intended for front end use (but front ends need not
-use it if they prefer to do things another way). If a front end finds
-it inconvenient to store anything more than a numeric index alongside
-each menu item, then this function provides an easy way for the front
-end to get back the actual game parameters corresponding to a menu
-item that the user has selected.
-\H{utils-alloc} Memory allocation
-Puzzles has some central wrappers on the standard memory allocation
-functions, which provide compile-time type checking, and run-time
-error checking by means of quitting the application if it runs out
-of memory. This doesn't provide the best possible recovery from
-memory shortage, but on the other hand it greatly simplifies the
-rest of the code, because nothing else anywhere needs to worry about
-\cw{NULL} returns from allocation.
-\S{utils-snew} \cw{snew()}
-\c var = snew(type);
-\e iii        iiii
-This macro takes a single argument which is a \e{type name}. It
-allocates space for one object of that type. If allocation fails it
-will call \cw{fatal()} and not return; so if it does return, you can
-be confident that its return value is non-\cw{NULL}.
-The return value is cast to the specified type, so that the compiler
-will type-check it against the variable you assign it into. Thus,
-this ensures you don't accidentally allocate memory the size of the
-wrong type and assign it into a variable of the right one (or vice
-versa!).
-\S{utils-snewn} \cw{snewn()}
-\c var = snewn(n, type);
-\e iii         i  iiii
-This macro is the array form of \cw{snew()}. It takes two arguments;
-the first is a number, and the second is a type name. It allocates
-space for that many objects of that type, and returns a type-checked
-non-\cw{NULL} pointer just as \cw{snew()} does.
-\S{utils-sresize} \cw{sresize()}
-\c var = sresize(var, n, type);
-\e iii           iii  i  iiii
-This macro is a type-checked form of \cw{realloc()}. It takes three
-arguments: an input memory block, a new size in elements, and a
-type. It re-sizes the input memory block to a size sufficient to
-contain that many elements of that type. It returns a type-checked
-non-\cw{NULL} pointer, like \cw{snew()} and \cw{snewn()}.
-The input memory block can be \cw{NULL}, in which case this function
-will behave exactly like \cw{snewn()}. (In principle any
-ANSI-compliant \cw{realloc()} implementation ought to cope with
-this, but I've never quite trusted it to work everywhere.)
-\S{utils-sfree} \cw{sfree()}
-\c void sfree(void *p);
-This function is pretty much equivalent to \cw{free()}. It is
-provided with a dynamically allocated block, and frees it.
-The input memory block can be \cw{NULL}, in which case this function
-will do nothing. (In principle any ANSI-compliant \cw{free()}
-implementation ought to cope with this, but I've never quite trusted
-it to work everywhere.)
-\S{utils-dupstr} \cw{dupstr()}
-\c char *dupstr(const char *s);
-This function dynamically allocates a duplicate of a C string. Like
-the \cw{snew()} functions, it guarantees to return non-\cw{NULL} or
-not return at all.
-(Many platforms provide the function \cw{strdup()}. As well as
-guaranteeing never to return \cw{NULL}, my version has the advantage
-of being defined \e{everywhere}, rather than inconveniently not
-quite everywhere.)
-\S{utils-free-cfg} \cw{free_cfg()}
-\c void free_cfg(config_item *cfg);
-This function correctly frees an array of \c{config_item}s, including
-walking the array until it gets to the end and freeing any subsidiary
-data items in each \c{u} sub-union which are expected to be
-dynamically allocated.
-(See \k{backend-configure} for details of the \c{config_item}
-structure.)
-\H{utils-tree234} Sorted and counted tree functions
-Many games require complex algorithms for generating random puzzles,
-and some require moderately complex algorithms even during play. A
-common requirement during these algorithms is for a means of
-maintaining sorted or unsorted lists of items, such that items can
-be removed and added conveniently.
-For general use, Puzzles provides the following set of functions
-which maintain 2-3-4 trees in memory. (A 2-3-4 tree is a balanced
-tree structure, with the property that all lookups, insertions,
-deletions, splits and joins can be done in \cw{O(log N)} time.)
-All these functions expect you to be storing a tree of \c{void *}
-pointers. You can put anything you like in those pointers.
-By the use of per-node element counts, these tree structures have
-the slightly unusual ability to look elements up by their numeric
-index within the list represented by the tree. This means that they
-can be used to store an unsorted list (in which case, every time you
-insert a new element, you must explicitly specify the position where
-you wish to insert it). They can also do numeric lookups in a sorted
-tree, which might be useful for (for example) tracking the median of
-a changing data set.
-As well as storing sorted lists, these functions can be used for
-storing \q{maps} (associative arrays), by defining each element of a
-tree to be a (key, value) pair.
-\S{utils-newtree234} \cw{newtree234()}
-\c tree234 *newtree234(cmpfn234 cmp);
-Creates a new empty tree, and returns a pointer to it.
-The parameter \c{cmp} determines the sorting criterion on the tree.
-Its prototype is
-\c typedef int (*cmpfn234)(void *, void *);
-If you want a sorted tree, you should provide a function matching
-this prototype, which returns like \cw{strcmp()} does (negative if
-the first argument is smaller than the second, positive if it is
-bigger, zero if they compare equal). In this case, the function
-\cw{addpos234()} will not be usable on your tree (because all
-insertions must respect the sorting order).
-If you want an unsorted tree, pass \cw{NULL}. In this case you will
-not be able to use either \cw{add234()} or \cw{del234()}, or any
-other function such as \cw{find234()} which depends on a sorting
-order. Your tree will become something more like an array, except
-that it will efficiently support insertion and deletion as well as
-lookups by numeric index.
-\S{utils-freetree234} \cw{freetree234()}
-\c void freetree234(tree234 *t);
-Frees a tree. This function will not free the \e{elements} of the
-tree (because they might not be dynamically allocated, or you might
-be storing the same set of elements in more than one tree); it will
-just free the tree structure itself. If you want to free all the
-elements of a tree, you should empty it before passing it to
-\cw{freetree234()}, by means of code along the lines of
-\c while ((element = delpos234(tree, 0)) != NULL)
-\c     sfree(element); /* or some more complicated free function */
-\e                     iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
-\S{utils-add234} \cw{add234()}
-\c void *add234(tree234 *t, void *e);
-Inserts a new element \c{e} into the tree \c{t}. This function
-expects the tree to be sorted; the new element is inserted according
-to the sort order.
-If an element comparing equal to \c{e} is already in the tree, then
-the insertion will fail, and the return value will be the existing
-element. Otherwise, the insertion succeeds, and \c{e} is returned.
-\S{utils-addpos234} \cw{addpos234()}
-\c void *addpos234(tree234 *t, void *e, int index);
-Inserts a new element into an unsorted tree. Since there is no
-sorting order to dictate where the new element goes, you must
-specify where you want it to go. Setting \c{index} to zero puts the
-new element right at the start of the list; setting \c{index} to the
-current number of elements in the tree puts the new element at the
-end.
-Return value is \c{e}, in line with \cw{add234()} (although this
-function cannot fail except by running out of memory, in which case
-it will bomb out and die rather than returning an error indication).
-\S{utils-index234} \cw{index234()}
-\c void *index234(tree234 *t, int index);
-Returns a pointer to the \c{index}th element of the tree, or
-\cw{NULL} if \c{index} is out of range. Elements of the tree are
-numbered from zero.
-\S{utils-find234} \cw{find234()}
-\c void *find234(tree234 *t, void *e, cmpfn234 cmp);
-Searches for an element comparing equal to \c{e} in a sorted tree.
-If \c{cmp} is \cw{NULL}, the tree's ordinary comparison function
-will be used to perform the search. However, sometimes you don't
-want that; suppose, for example, each of your elements is a big
-structure containing a \c{char *} name field, and you want to find
-the element with a given name. You \e{could} achieve this by
-constructing a fake element structure, setting its name field
-appropriately, and passing it to \cw{find234()}, but you might find
-it more convenient to pass \e{just} a name string to \cw{find234()},
-supplying an alternative comparison function which expects one of
-its arguments to be a bare name and the other to be a large
-structure containing a name field.
-Therefore, if \c{cmp} is not \cw{NULL}, then it will be used to
-compare \c{e} to elements of the tree. The first argument passed to
-\c{cmp} will always be \c{e}; the second will be an element of the
-tree.
-(See \k{utils-newtree234} for the definition of the \c{cmpfn234}
-function pointer type.)
-The returned value is the element found, or \cw{NULL} if the search
-is unsuccessful.
-\S{utils-findrel234} \cw{findrel234()}
-\c void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);
-This function is like \cw{find234()}, but has the additional ability
-to do a \e{relative} search. The additional parameter \c{relation}
-can be one of the following values:
-\dt \cw{REL234_EQ}
-\dd Find only an element that compares equal to \c{e}. This is
-exactly the behaviour of \cw{find234()}.
-\dt \cw{REL234_LT}
-\dd Find the greatest element that compares strictly less than
-\c{e}. \c{e} may be \cw{NULL}, in which case it finds the greatest
-element in the whole tree (which could also be done by
-\cw{index234(t, count234(t)-1)}).
-\dt \cw{REL234_LE}
-\dd Find the greatest element that compares less than or equal to
-\c{e}. (That is, find an element that compares equal to \c{e} if
-possible, but failing that settle for something just less than it.)
-\dt \cw{REL234_GT}
-\dd Find the smallest element that compares strictly greater than
-\c{e}. \c{e} may be \cw{NULL}, in which case it finds the smallest
-element in the whole tree (which could also be done by
-\cw{index234(t, 0)}).
-\dt \cw{REL234_GE}
-\dd Find the smallest element that compares greater than or equal to
-\c{e}. (That is, find an element that compares equal to \c{e} if
-possible, but failing that settle for something just bigger than
-it.)
-Return value, as before, is the element found or \cw{NULL} if no
-element satisfied the search criterion.
-\S{utils-findpos234} \cw{findpos234()}
-\c void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);
-This function is like \cw{find234()}, but has the additional feature
-of returning the index of the element found in the tree; that index
-is written to \c{*index} in the event of a successful search (a
-non-\cw{NULL} return value).
-\c{index} may be \cw{NULL}, in which case this function behaves
-exactly like \cw{find234()}.
-\S{utils-findrelpos234} \cw{findrelpos234()}
-\c void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
-\c                     int *index);
-This function combines all the features of \cw{findrel234()} and
-\cw{findpos234()}.
-\S{utils-del234} \cw{del234()}
-\c void *del234(tree234 *t, void *e);
-Finds an element comparing equal to \c{e} in the tree, deletes it,
-and returns it.
-The input tree must be sorted.
-The element found might be \c{e} itself, or might merely compare
-equal to it.
-Return value is \cw{NULL} if no such element is found.
-\S{utils-delpos234} \cw{delpos234()}
-\c void *delpos234(tree234 *t, int index);
-Deletes the element at position \c{index} in the tree, and returns
-it.
-Return value is \cw{NULL} if the index is out of range.
-\S{utils-count234} \cw{count234()}
-\c int count234(tree234 *t);
-Returns the number of elements currently in the tree.
-\S{utils-splitpos234} \cw{splitpos234()}
-\c tree234 *splitpos234(tree234 *t, int index, bool before);
-Splits the input tree into two pieces at a given position, and
-creates a new tree containing all the elements on one side of that
-position.
-If \c{before} is \cw{true}, then all the items at or after position
-\c{index} are left in the input tree, and the items before that
-point are returned in the new tree. Otherwise, the reverse happens:
-all the items at or after \c{index} are moved into the new tree, and
-those before that point are left in the old one.
-If \c{index} is equal to 0 or to the number of elements in the input
-tree, then one of the two trees will end up empty (and this is not
-an error condition). If \c{index} is further out of range in either
-direction, the operation will fail completely and return \cw{NULL}.
-This operation completes in \cw{O(log N)} time, no matter how large
-the tree or how balanced or unbalanced the split.
-\S{utils-split234} \cw{split234()}
-\c tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);
-Splits a sorted tree according to its sort order.
-\c{rel} can be any of the relation constants described in
-\k{utils-findrel234}, \e{except} for \cw{REL234_EQ}. All the
-elements having that relation to \c{e} will be transferred into the
-new tree; the rest will be left in the old one.
-The parameter \c{cmp} has the same semantics as it does in
-\cw{find234()}: if it is not \cw{NULL}, it will be used in place of
-the tree's own comparison function when comparing elements to \c{e},
-in such a way that \c{e} itself is always the first of its two
-operands.
-Again, this operation completes in \cw{O(log N)} time, no matter how
-large the tree or how balanced or unbalanced the split.
-\S{utils-join234} \cw{join234()}
-\c tree234 *join234(tree234 *t1, tree234 *t2);
-Joins two trees together by concatenating the lists they represent.
-All the elements of \c{t2} are moved into \c{t1}, in such a way that
-they appear \e{after} the elements of \c{t1}. The tree \c{t2} is
-freed; the return value is \c{t1}.
-If you apply this function to a sorted tree and it violates the sort
-order (i.e. the smallest element in \c{t2} is smaller than or equal
-to the largest element in \c{t1}), the operation will fail and
-return \cw{NULL}.
-This operation completes in \cw{O(log N)} time, no matter how large
-the trees being joined together.
-\S{utils-join234r} \cw{join234r()}
-\c tree234 *join234r(tree234 *t1, tree234 *t2);
-Joins two trees together in exactly the same way as \cw{join234()},
-but this time the combined tree is returned in \c{t2}, and \c{t1} is
-destroyed. The elements in \c{t1} still appear before those in
-\c{t2}.
-Again, this operation completes in \cw{O(log N)} time, no matter how
-large the trees being joined together.
-\S{utils-copytree234} \cw{copytree234()}
-\c tree234 *copytree234(tree234 *t, copyfn234 copyfn,
-\c                      void *copyfnstate);
-Makes a copy of an entire tree.
-If \c{copyfn} is \cw{NULL}, the tree will be copied but the elements
-will not be; i.e. the new tree will contain pointers to exactly the
-same physical elements as the old one.
-If you want to copy each actual element during the operation, you
-can instead pass a function in \c{copyfn} which makes a copy of each
-element. That function has the prototype
-\c typedef void *(*copyfn234)(void *state, void *element);
-and every time it is called, the \c{state} parameter will be set to
-the value you passed in as \c{copyfnstate}.
-\H{utils-misc} Miscellaneous utility functions and macros
-This section contains all the utility functions which didn't
-sensibly fit anywhere else.
-\S{utils-truefalse} \cw{TRUE} and \cw{FALSE}
-The main Puzzles header file defines the macros \cw{TRUE} and
-\cw{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.
-\S{utils-maxmin} \cw{max()} and \cw{min()}
-The main Puzzles header file defines the pretty standard macros
-\cw{max()} and \cw{min()}, each of which is given two arguments and
-returns the one which compares greater or less respectively.
-These macros may evaluate their arguments multiple times. Avoid side
-effects.
-\S{utils-pi} \cw{PI}
-The main Puzzles header file defines a macro \cw{PI} which expands
-to a floating-point constant representing pi.
-(I've never understood why ANSI's \cw{<math.h>} doesn't define this.
-It'd be so useful!)
-\S{utils-obfuscate-bitmap} \cw{obfuscate_bitmap()}
-\c void obfuscate_bitmap(unsigned char *bmp, int bits, 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 \e{accidentally} spoiling
-their own fun.
-The input argument \c{bmp} points at a piece of memory to be
-obfuscated. \c{bits} gives the length of the data. Note that that
-length is in \e{bits} rather than bytes: if you ask for obfuscation
-of a partial number of bytes, then you will get it. Bytes are
-considered to be used from the top down: thus, for example, setting
-\c{bits} to 10 will cover the whole of \cw{bmp[0]} and the \e{top
-two} bits of \cw{bmp[1]}. The remainder of a partially used byte is
-undefined (i.e. it may be corrupted by the function).
-The parameter \c{decode} is \cw{FALSE} for an encoding operation,
-and \cw{TRUE} for a decoding operation. Each is the inverse of the
-other. (There's no particular reason you shouldn't obfuscate by
-decoding and restore cleartext by encoding, if you really wanted to;
-it should still work.)
-The input bitmap is processed in place.
-\S{utils-bin2hex} \cw{bin2hex()}
-\c char *bin2hex(const unsigned char *in, int inlen);
-This function takes an input byte array and converts it into an
-ASCII string encoding those bytes in (lower-case) hex. It returns a
-dynamically allocated string containing that encoding.
-This function is useful for encoding the result of
-\cw{obfuscate_bitmap()} in printable ASCII for use in game IDs.
-\S{utils-hex2bin} \cw{hex2bin()}
-\c unsigned char *hex2bin(const char *in, int outlen);
-This function takes an ASCII string containing hex digits, and
-converts it back into a byte array of length \c{outlen}. If there
-aren't enough hex digits in the string, the contents of the
-resulting array will be undefined.
-This function is the inverse of \cw{bin2hex()}.
-\S{utils-game-mkhighlight} \cw{game_mkhighlight()}
-\c void game_mkhighlight(frontend *fe, float *ret,
-\c                       int background, int highlight, int lowlight);
-It's reasonably common for a puzzle game's graphics to use
-highlights and lowlights to indicate \q{raised} or \q{lowered}
-sections. Fifteen, Sixteen and Twiddle are good examples of this.
-Puzzles using this graphical style are running a risk if they just
-use whatever background colour is supplied to them by the front end,
-because that background colour might be too light to see any
-highlights on at all. (In particular, it's not unheard of for the
-front end to specify a default background colour of white.)
-Therefore, such puzzles can call this utility function from their
-\cw{colours()} routine (\k{backend-colours}). You pass it your front
-end handle, a pointer to the start of your return array, and three
-colour indices. It will:
-\b call \cw{frontend_default_colour()} (\k{frontend-default-colour})
-to fetch the front end's default background colour
-\b alter the brightness of that colour if it's unsuitable
-\b define brighter and darker variants of the colour to be used as
-highlights and lowlights
-\b write those results into the relevant positions in the \c{ret}
-array.
-Thus, \cw{ret[background*3]} to \cw{ret[background*3+2]} will be set
-to RGB values defining a sensible background colour, and similary
-\c{highlight} and \c{lowlight} will be set to sensible colours.
-\S{utils-button2label} \cw{button2label()}
-\c char *button2label(int button);
-This function generates a descriptive text label for \cw{button},
-which should be a button code that can be passed to the midend. For
-example, calling this function with \cw{CURSOR_UP} will result in the
-string \cw{"Up"}. This function should only be called when the
-\cw{key_label} item returned by a backend's \cw{request_keys()}
-(\k{backend-request-keys}) function has its \cw{label} field set to
-\cw{NULL}; in this case, the corresponding \cw{button} field can be
-passed to this function to obtain an appropriate label. If, however,
-the field is not \cw{NULL}, this function should not be called with
-the corresponding \cw{button} field.
-The returned string is dynamically allocated and should be
-\cw{sfree}'d by the caller.
-\C{writing} How to write a new puzzle
-This chapter gives a guide to how to actually write a new puzzle:
-where to start, what to do first, how to solve common problems.
-The previous chapters have been largely composed of facts. This one
-is mostly advice.
-\H{writing-editorial} Choosing a puzzle
-Before you start writing a puzzle, you have to choose one. Your
-taste in puzzle games is up to you, of course; and, in fact, you're
-probably reading this guide because you've \e{already} thought of a
-game you want to write. But if you want to get it accepted into the
-official Puzzles distribution, then there's a criterion it has to
-meet.
-The current Puzzles editorial policy is that all games should be
-\e{fair}. A fair game is one which a player can only fail to
-complete through demonstrable lack of skill \dash that is, such that
-a better player in the same situation would have \e{known} to do
-something different.
-For a start, that means every game presented to the user must have
-\e{at least one solution}. Giving the unsuspecting user a puzzle
-which is actually impossible is not acceptable. (There is an
-exception: if the user has selected some non-default option which is
-clearly labelled as potentially unfair, \e{then} you're allowed to
-generate possibly insoluble puzzles, because the user isn't
-unsuspecting any more. Same Game and Mines both have options of this
-type.)
-Also, this actually \e{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 \e{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 \e{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 \e{unique} solution is a little more negotiable; it
-depends on the puzzle. Solo would have been of unacceptably low
-quality if it didn't always have a unique solution, whereas Twiddle
-inherently has multiple solutions by its very nature and it would
-have been meaningless to even \e{suggest} making it uniquely
-soluble. Somewhere in between, Flip could reasonably be made to have
-unique solutions (by enforcing a zero-dimension kernel in every
-generated matrix) but it doesn't seem like a serious quality problem
-that it doesn't.
-Of course, you don't \e{have} to care about all this. There's
-nothing stopping you implementing any puzzle you want to if you're
-happy to maintain your puzzle yourself, distribute it from your own
-web site, fork the Puzzles code completely, or anything like that.
-It's free software; you can do what you like with it. But any game
-that you want to be accepted into \e{my} Puzzles code base has to
-satisfy the fairness criterion, which means all randomly generated
-puzzles must have a solution (unless the user has deliberately
-chosen otherwise) and it must be possible \e{in theory} to find that
-solution without having to guess.
-\H{writing-gs} Getting started
-The simplest way to start writing a new puzzle is to copy
-\c{nullgame.c}. This is a template puzzle source file which does
-almost nothing, but which contains all the back end function
-prototypes and declares the back end data structure correctly. It is
-built every time the rest of Puzzles is built, to ensure that it
-doesn't get out of sync with the code and remains buildable.
-So start by copying \c{nullgame.c} into your new source file. Then
-you'll gradually add functionality until the very boring Null Game
-turns into your real game.
-Next you'll need to add your puzzle to the Makefiles, in order to
-compile it conveniently. \e{Do not edit the Makefiles}: they are
-created automatically by the script \c{mkfiles.pl}, from the file
-called \c{Recipe}. Edit \c{Recipe}, and then re-run \c{mkfiles.pl}.
-Also, don't forget to add your puzzle to \c{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.
-\S{writing-generation} Puzzle generation
-Randomly generating instances of your puzzle is almost certain to be
-the most difficult part of the code, and also the task with the
-highest chance of turning out to be completely infeasible. Therefore
-I strongly recommend doing it \e{first}, so that if it all goes
-horribly wrong you haven't wasted any more time than you absolutely
-had to. What I usually do is to take an unmodified \c{nullgame.c},
-and start adding code to \cw{new_game_desc()} which tries to
-generate a puzzle instance and print it out using \cw{printf()}.
-Once that's working, \e{then} I start connecting it up to the return
-value of \cw{new_game_desc()}, populating other structures like
-\c{game_params}, and generally writing the rest of the source file.
-There are many ways to generate a puzzle which is known to be
-soluble. In this section I list all the methods I currently know of,
-in case any of them can be applied to your puzzle. (Not all of these
-methods will work, or in some cases even make sense, for all
-puzzles.)
-Some puzzles are mathematically tractable, meaning you can work out
-in advance which instances are soluble. Sixteen, for example, has a
-parity constraint in some settings which renders exactly half the
-game space unreachable, but it can be mathematically proved that any
-position not in that half \e{is} reachable. Therefore, Sixteen's
-grid generation simply consists of selecting at random from a well
-defined subset of the game space. Cube in its default state is even
-easier: \e{every} possible arrangement of the blue squares and the
-cube's starting position is soluble!
-Another option is to redefine what you mean by \q{soluble}. Black
-Box takes this approach. There are layouts of balls in the box which
-are completely indistinguishable from one another no matter how many
-beams you fire into the box from which angles, which would normally
-be grounds for declaring those layouts unfair; but fortunately,
-detecting that indistinguishability is computationally easy. So
-Black Box doesn't demand that your ball placements match its own; it
-merely demands that your ball placements be \e{indistinguishable}
-from the ones it was thinking of. If you have an ambiguous puzzle,
-then any of the possible answers is considered to be a solution.
-Having redefined the rules in that way, any puzzle is soluble again.
-Those are the simple techniques. If they don't work, you have to get
-cleverer.
-One way to generate a soluble puzzle is to start from the solved
-state and make inverse moves until you reach a starting state. Then
-you know there's a solution, because you can just list the inverse
-moves you made and make them in the opposite order to return to the
-solved state.
-This method can be simple and effective for puzzles where you get to
-decide what's a starting state and what's not. In Pegs, for example,
-the generator begins with one peg in the centre of the board and
-makes inverse moves until it gets bored; in this puzzle, valid
-inverse moves are easy to detect, and \e{any} state that's reachable
-from the solved state by inverse moves is a reasonable starting
-position. So Pegs just continues making inverse moves until the
-board satisfies some criteria about extent and density, and then
-stops and declares itself done.
-For other puzzles, it can be a lot more difficult. Same Game uses
-this strategy too, and it's lucky to get away with it at all: valid
-inverse moves aren't easy to find (because although it's easy to
-insert additional squares in a Same Game position, it's difficult to
-arrange that \e{after} the insertion they aren't adjacent to any
-other squares of the same colour), so you're constantly at risk of
-running out of options and having to backtrack or start again. Also,
-Same Game grids never start off half-empty, which means you can't
-just stop when you run out of moves \dash you have to find a way to
-fill the grid up \e{completely}.
-The other way to generate a puzzle that's soluble is to start from
-the other end, and actually write a \e{solver}. This tends to ensure
-that a puzzle has a \e{unique} solution over and above having a
-solution at all, so it's a good technique to apply to puzzles for
-which that's important.
-One theoretical drawback of generating soluble puzzles by using a
-solver is that your puzzles are restricted in difficulty to those
-which the solver can handle. (Most solvers are not fully general:
-many sets of puzzle rules are NP-complete or otherwise nasty, so
-most solvers can only handle a subset of the theoretically soluble
-puzzles.) It's been my experience in practice, however, that this
-usually isn't a problem; computers are good at very different things
-from humans, and what the computer thinks is nice and easy might
-still be pleasantly challenging for a human. For example, when
-solving Dominosa puzzles I frequently find myself using a variety of
-reasoning techniques that my solver doesn't know about; in
-principle, therefore, I should be able to solve the puzzle using
-only those techniques it \e{does} know about, but this would involve
-repeatedly searching the entire grid for the one simple deduction I
-can make. Computers are good at this sort of exhaustive search, but
-it's been my experience that human solvers prefer to do more complex
-deductions than to spend ages searching for simple ones. So in many
-cases I don't find my own playing experience to be limited by the
-restrictions on the solver.
-(This isn't \e{always} the case. Solo is a counter-example;
-generating Solo puzzles using a simple solver does lead to
-qualitatively easier puzzles. Therefore I had to make the Solo
-solver rather more advanced than most of them.)
-There are several different ways to apply a solver to the problem of
-generating a soluble puzzle. I list a few of them below.
-The simplest approach is brute force: randomly generate a puzzle,
-use the solver to see if it's soluble, and if not, throw it away and
-try again until you get lucky. This is often a viable technique if
-all else fails, but it tends not to scale well: for many puzzle
-types, the probability of finding a uniquely soluble instance
-decreases sharply as puzzle size goes up, so this technique might
-work reasonably fast for small puzzles but take (almost) forever at
-larger sizes. Still, if there's no other alternative it can be
-usable: Pattern and Dominosa both use this technique. (However,
-Dominosa has a means of tweaking the randomly generated grids to
-increase the \e{probability} of them being soluble, by ruling out
-one of the most common ambiguous cases. This improved generation
-speed by over a factor of 10 on the highest preset!)
-An approach which can be more scalable involves generating a grid
-and then tweaking it to make it soluble. This is the technique used
-by Mines and also by Net: first a random puzzle is generated, and
-then the solver is run to see how far it gets. Sometimes the solver
-will get stuck; when that happens, examine the area it's having
-trouble with, and make a small random change in that area to allow
-it to make more progress. Continue solving (possibly even without
-restarting the solver), tweaking as necessary, until the solver
-finishes. Then restart the solver from the beginning to ensure that
-the tweaks haven't caused new problems in the process of solving old
-ones (which can sometimes happen).
-This strategy works well in situations where the usual solver
-failure mode is to get stuck in an easily localised spot. Thus it
-works well for Net and Mines, whose most common failure mode tends
-to be that most of the grid is fine but there are a few widely
-separated ambiguous sections; but it would work less well for
-Dominosa, in which the way you get stuck is to have scoured the
-whole grid and not found anything you can deduce \e{anywhere}. Also,
-it relies on there being a low probability that tweaking the grid
-introduces a new problem at the same time as solving the old one;
-Mines and Net also have the property that most of their deductions
-are local, so that it's very unlikely for a tweak to affect
-something half way across the grid from the location where it was
-applied. In Dominosa, by contrast, a lot of deductions use
-information about half the grid (\q{out of all the sixes, only one
-is next to a three}, which can depend on the values of up to 32 of
-the 56 squares in the default setting!), so this tweaking strategy
-would be rather less likely to work well.
-A more specialised strategy is that used in Solo and Slant. These
-puzzles have the property that they derive their difficulty from not
-presenting all the available clues. (In Solo's case, if all the
-possible clues were provided then the puzzle would already be
-solved; in Slant it would still require user action to fill in the
-lines, but it would present no challenge at all). Therefore, a
-simple generation technique is to leave the decision of which clues
-to provide until the last minute. In other words, first generate a
-random \e{filled} grid with all possible clues present, and then
-gradually remove clues for as long as the solver reports that it's
-still soluble. Unlike the methods described above, this technique
-\e{cannot} fail \dash once you've got a filled grid, nothing can
-stop you from being able to convert it into a viable puzzle.
-However, it wouldn't even be meaningful to apply this technique to
-(say) Pattern, in which clues can never be left out, so the only way
-to affect the set of clues is by altering the solution.
-(Unfortunately, Solo is complicated by the need to provide puzzles
-at varying difficulty levels. It's easy enough to generate a puzzle
-of \e{at most} a given level of difficulty; you just have a solver
-with configurable intelligence, and you set it to a given level and
-apply the above technique, thus guaranteeing that the resulting grid
-is solvable by someone with at most that much intelligence. However,
-generating a puzzle of \e{at least} a given level of difficulty is
-rather harder; if you go for \e{at most} Intermediate level, you're
-likely to find that you've accidentally generated a Trivial grid a
-lot of the time, because removing just one number is sufficient to
-take the puzzle from Trivial straight to Ambiguous. In that
-situation Solo has no remaining options but to throw the puzzle away
-and start again.)
-A final strategy is to use the solver \e{during} puzzle
-construction: lay out a bit of the grid, run the solver to see what
-it allows you to deduce, and then lay out a bit more to allow the
-solver to make more progress. There are articles on the web that
-recommend constructing Sudoku puzzles by this method (which is
-completely the opposite way round to how Solo does it); for Sudoku
-it has the advantage that you get to specify your clue squares in
-advance (so you can have them make pretty patterns).
-Rectangles uses a strategy along these lines. First it generates a
-grid by placing the actual rectangles; then it has to decide where
-in each rectangle to place a number. It uses a solver to help it
-place the numbers in such a way as to ensure a unique solution. It
-does this by means of running a test solver, but it runs the solver
-\e{before} it's placed any of the numbers \dash which means the
-solver must be capable of coping with uncertainty about exactly
-where the numbers are! It runs the solver as far as it can until it
-gets stuck; then it narrows down the possible positions of a number
-in order to allow the solver to make more progress, and so on. Most
-of the time this process terminates with the grid fully solved, at
-which point any remaining number-placement decisions can be made at
-random from the options not so far ruled out. Note that unlike the
-Net/Mines tweaking strategy described above, this algorithm does not
-require a checking run after it completes: if it finishes
-successfully at all, then it has definitely produced a uniquely
-soluble puzzle.
-Most of the strategies described above are not 100% reliable. Each
-one has a failure rate: every so often it has to throw out the whole
-grid and generate a fresh one from scratch. (Solo's strategy would
-be the exception, if it weren't for the need to provide configurable
-difficulty levels.) Occasional failures are not a fundamental
-problem in this sort of work, however: it's just a question of
-dividing the grid generation time by the success rate (if it takes
-10ms to generate a candidate grid and 1/5 of them work, then it will
-take 50ms on average to generate a viable one), and seeing whether
-the expected time taken to \e{successfully} generate a puzzle is
-unacceptably slow. Dominosa's generator has a very low success rate
-(about 1 out of 20 candidate grids turn out to be usable, and if you
-think \e{that's} bad then go and look at the source code and find
-the comment showing what the figures were before the generation-time
-tweaks!), but the generator itself is very fast so this doesn't
-matter. Rectangles has a slower generator, but fails well under 50%
-of the time.
-So don't be discouraged if you have an algorithm that doesn't always
-work: if it \e{nearly} always works, that's probably good enough.
-The one place where reliability is important is that your algorithm
-must never produce false positives: it must not claim a puzzle is
-soluble when it isn't. It can produce false negatives (failing to
-notice that a puzzle is soluble), and it can fail to generate a
-puzzle at all, provided it doesn't do either so often as to become
-slow.
-One last piece of advice: for grid-based puzzles, when writing and
-testing your generation algorithm, it's almost always a good idea
-\e{not} to test it initially on a grid that's square (i.e.
-\cw{w==h}), because if the grid is square then you won't notice if
-you mistakenly write \c{h} instead of \c{w} (or vice versa)
-somewhere in the code. Use a rectangular grid for testing, and any
-size of grid will be likely to work after that.
-\S{writing-textformats} Designing textual description formats
-Another aspect of writing a puzzle which is worth putting some
-thought into is the design of the various text description formats:
-the format of the game parameter encoding, the game description
-encoding, and the move encoding.
-The first two of these should be reasonably intuitive for a user to
-type in; so provide some flexibility where possible. Suppose, for
-example, your parameter format consists of two numbers separated by
-an \c{x} to specify the grid dimensions (\c{10x10} or \c{20x15}),
-and then has some suffixes to specify other aspects of the game
-type. It's almost always a good idea in this situation to arrange
-that \cw{decode_params()} can handle the suffixes appearing in any
-order, even if \cw{encode_params()} only ever generates them in one
-order.
-These formats will also be expected to be reasonably stable: users
-will expect to be able to exchange game IDs with other users who
-aren't running exactly the same version of your game. So make them
-robust and stable: don't build too many assumptions into the game ID
-format which will have to be changed every time something subtle
-changes in the puzzle code.
-\H{writing-howto} Common how-to questions
-This section lists some common things people want to do when writing
-a puzzle, and describes how to achieve them within the Puzzles
-framework.
-\S{writing-howto-cursor} Drawing objects at only one position
-A common phenomenon is to have an object described in the
-\c{game_state} or the \c{game_ui} which can only be at one position.
-A cursor \dash probably specified in the \c{game_ui} \dash is a good
-example.
-In the \c{game_ui}, it would \e{obviously} be silly to have an array
-covering the whole game grid with a boolean flag stating whether the
-cursor was at each position. Doing that would waste space, would
-make it difficult to find the cursor in order to do anything with
-it, and would introduce the potential for synchronisation bugs in
-which you ended up with two cursors or none. The obviously sensible
-way to store a cursor in the \c{game_ui} is to have fields directly
-encoding the cursor's coordinates.
-However, it is a mistake to assume that the same logic applies to
-the \c{game_drawstate}. If you replicate the cursor position fields
-in the draw state, the redraw code will get very complicated. In the
-draw state, in fact, it \e{is} probably the right thing to have a
-cursor flag for every position in the grid. 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 \q{cursor} flag to each element of that array.
-Then the main redraw loop will look something like this
-(pseudo-code):
-\c for (y = 0; y < h; y++) {
-\c     for (x = 0; x < w; x++) {
-\c         int value = state->symbol_at_position[y][x];
-\c         if (x == ui->cursor_x && y == ui->cursor_y)
-\c             value |= CURSOR;
-\c         if (ds->symbol_at_position[y][x] != value) {
-\c             symbol_drawing_subroutine(dr, ds, x, y, value);
-\c             ds->symbol_at_position[y][x] = value;
-\c         }
-\c     }
-\c }
-This loop is very simple, pretty hard to get wrong, and
-\e{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 \e{everything}
-about what was drawn there. A good way to ensure that is to pass
-precisely the same information, and \e{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.
-\S{writing-keyboard-cursor} Implementing a keyboard-controlled cursor
-It is often useful to provide a keyboard control method in a
-basically mouse-controlled game. A keyboard-controlled cursor is
-best implemented by storing its location in the \c{game_ui} (since
-if it were in the \c{game_state} then the user would have to
-separately undo every cursor move operation). So the procedure would
-be:
-\b Put cursor position fields in the \c{game_ui}.
-\b \cw{interpret_move()} responds to arrow keys by modifying the
-cursor position fields and returning \cw{""}.
-\b \cw{interpret_move()} responds to some sort of fire button by
-actually performing a move based on the current cursor location.
-\b You might want an additional \c{game_ui} field stating whether
-the cursor is currently visible, and having it disappear when a
-mouse action occurs (so that it doesn't clutter the display when not
-actually in use).
-\b You might also want to automatically hide the cursor in
-\cw{changed_state()} when the current game state changes to one in
-which there is no move to make (which is the case in some types of
-completed game).
-\b \cw{redraw()} draws the cursor using the technique described in
-\k{writing-howto-cursor}.
-\S{writing-howto-dragging} Implementing draggable sprites
-Some games have a user interface which involves dragging some sort
-of game element around using the mouse. If you need to show a
-graphic moving smoothly over the top of other graphics, use a
-blitter (see \k{drawing-blitter} for the blitter API) to save the
-background underneath it. The typical scenario goes:
-\b Have a blitter field in the \c{game_drawstate}.
-\b Set the blitter field to \cw{NULL} in the game's
-\cw{new_drawstate()} function, since you don't yet know how big the
-piece of saved background needs to be.
-\b In the game's \cw{set_size()} function, once you know the size of
-the object you'll be dragging around the display and hence the
-required size of the blitter, actually allocate the blitter.
-\b In \cw{free_drawstate()}, free the blitter if it's not \cw{NULL}.
-\b In \cw{interpret_move()}, respond to mouse-down and mouse-drag
-events by updating some fields in the \cw{game_ui} which indicate
-that a drag is in progress.
-\b At the \e{very end} of \cw{redraw()}, after all other drawing has
-been done, draw the moving object if there is one. First save the
-background under the object in the blitter; then set a clip
-rectangle covering precisely the area you just saved (just in case
-anti-aliasing or some other error causes your drawing to go beyond
-the area you saved). Then draw the object, and call \cw{unclip()}.
-Finally, set a flag in the \cw{game_drawstate} that indicates that
-the blitter needs restoring.
-\b At the very start of \cw{redraw()}, before doing anything else at
-all, check the flag in the \cw{game_drawstate}, and if it says the
-blitter needs restoring then restore it. (Then clear the flag, so
-that this won't happen again in the next redraw if no moving object
-is drawn this time.)
-This way, you will be able to write the rest of the redraw function
-completely ignoring the dragged object, as if it were floating above
-your bitmap and being completely separate.
-\S{writing-ref-counting} Sharing large invariant data between all
-game states
-In some puzzles, there is a large amount of data which never changes
-between game states. The array of numbers in Dominosa is a good
-example.
-You \e{could} dynamically allocate a copy of that array in every
-\c{game_state}, and have \cw{dup_game()} make a fresh copy of it for
-every new \c{game_state}; but it would waste memory and time. A
-more efficient way is to use a reference-counted structure.
-\b Define a structure type containing the data in question, and also
-containing an integer reference count.
-\b Have a field in \c{game_state} which is a pointer to this
-structure.
-\b In \cw{new_game()}, when creating a fresh game state at the start
-of a new game, create an instance of this structure, initialise it
-with the invariant data, and set its reference count to 1.
-\b In \cw{dup_game()}, rather than making a copy of the structure
-for the new game state, simply set the new game state to point at
-the same copy of the structure, and increment its reference count.
-\b In \cw{free_game()}, decrement the reference count in the
-structure pointed to by the game state; if the count reaches zero,
-free the structure.
-This way, the invariant data will persist for only as long as it's
-genuinely needed; \e{as soon} as the last game state for a
-particular puzzle instance is freed, the invariant data for that
-puzzle will vanish as well. Reference counting is a very efficient
-form of garbage collection, when it works at all. (Which it does in
-this instance, of course, because there's no possibility of circular
-references.)
-\S{writing-flash-types} Implementing multiple types of flash
-In some games you need to flash in more than one different way.
-Mines, for example, flashes white when you win, and flashes red when
-you tread on a mine and die.
-The simple way to do this is:
-\b Have a field in the \c{game_ui} which describes the type of flash.
-\b In \cw{flash_length()}, examine the old and new game states to
-decide whether a flash is required and what type. Write the type of
-flash to the \c{game_ui} field whenever you return non-zero.
-\b In \cw{redraw()}, when you detect that \c{flash_time} is
-non-zero, examine the field in \c{game_ui} to decide which type of
-flash to draw.
-\cw{redraw()} will never be called with \c{flash_time} non-zero
-unless \cw{flash_length()} was first called to tell the mid-end that
-a flash was required; so whenever \cw{redraw()} notices that
-\c{flash_time} is non-zero, you can be sure that the field in
-\c{game_ui} is correctly set.
-\S{writing-move-anim} Animating game moves
-A number of puzzle types benefit from a quick animation of each move
-you make.
-For some games, such as Fifteen, this is particularly easy. Whenever
-\cw{redraw()} is called with \c{oldstate} non-\cw{NULL}, Fifteen
-simply compares the position of each tile in the two game states,
-and if the tile is not in the same place then it draws it some
-fraction of the way from its old position to its new position. This
-method copes automatically with undo.
-Other games are less obvious. In Sixteen, for example, you can't
-just draw each tile a fraction of the way from its old to its new
-position: if you did that, the end tile would zip very rapidly past
-all the others to get to the other end and that would look silly.
-(Worse, it would look inconsistent if the end tile was drawn on top
-going one way and on the bottom going the other way.)
-A useful trick here is to define a field or two in the game state
-that indicates what the last move was.
-\b Add a \q{last move} field to the \c{game_state} (or two or more
-fields if the move is complex enough to need them).
-\b \cw{new_game()} initialises this field to a null value for a new
-game state.
-\b \cw{execute_move()} sets up the field to reflect the move it just
-performed.
-\b \cw{redraw()} now needs to examine its \c{dir} parameter. If
-\c{dir} is positive, it determines the move being animated by
-looking at the last-move field in \c{newstate}; but if \c{dir} is
-negative, it has to look at the last-move field in \c{oldstate}, and
-invert whatever move it finds there.
-Note also that Sixteen needs to store the \e{direction} of the move,
-because you can't quite determine it by examining the row or column
-in question. You can in almost all cases, but when the row is
-precisely two squares long it doesn't work since a move in either
-direction looks the same. (You could argue that since moving a
-2-element row left and right has the same effect, it doesn't matter
-which one you animate; but in fact it's very disorienting to click
-the arrow left and find the row moving right, and almost as bad to
-undo a move to the right and find the game animating \e{another}
-move to the right.)
-\S{writing-conditional-anim} Animating drag operations
-In Untangle, moves are made by dragging a node from an old position
-to a new position. Therefore, at the time when the move is initially
-made, it should not be animated, because the node has already been
-dragged to the right place and doesn't need moving there. However,
-it's nice to animate the same move if it's later undone or redone.
-This requires a bit of fiddling.
-The obvious approach is to have a flag in the \c{game_ui} which
-inhibits move animation, and to set that flag in
-\cw{interpret_move()}. The question is, when would the flag be reset
-again? The obvious place to do so is \cw{changed_state()}, which
-will be called once per move. But it will be called \e{before}
-\cw{anim_length()}, so if it resets the flag then \cw{anim_length()}
-will never see the flag set at all.
-The solution is to have \e{two} flags in a queue.
-\b Define two flags in \c{game_ui}; let's call them \q{current} and
-\q{next}.
-\b Set both to \cw{FALSE} in \c{new_ui()}.
-\b When a drag operation completes in \cw{interpret_move()}, set the
-\q{next} flag to \cw{TRUE}.
-\b Every time \cw{changed_state()} is called, set the value of
-\q{current} to the value in \q{next}, and then set the value of
-\q{next} to \cw{FALSE}.
-\b That way, \q{current} will be \cw{TRUE} \e{after} a call to
-\cw{changed_state()} if and only if that call to
-\cw{changed_state()} was the result of a drag operation processed by
-\cw{interpret_move()}. Any other call to \cw{changed_state()}, due
-to an Undo or a Redo or a Restart or a Solve, will leave \q{current}
-\cw{FALSE}.
-\b So now \cw{anim_length()} can request a move animation if and
-only if the \q{current} flag is \e{not} set.
-\S{writing-cheating} Inhibiting the victory flash when Solve is used
-Many games flash when you complete them, as a visual congratulation
-for having got to the end of the puzzle. It often seems like a good
-idea to disable that flash when the puzzle is brought to a solved
-state by means of the Solve operation.
-This is easily done:
-\b Add a \q{cheated} flag to the \c{game_state}.
-\b Set this flag to \cw{FALSE} in \cw{new_game()}.
-\b Have \cw{solve()} return a move description string which clearly
-identifies the move as a solve operation.
-\b Have \cw{execute_move()} respond to that clear identification by
-setting the \q{cheated} flag in the returned \c{game_state}. The
-flag will then be propagated to all subsequent game states, even if
-the user continues fiddling with the game after it is solved.
-\b \cw{flash_length()} now returns non-zero if \c{oldstate} is not
-completed and \c{newstate} is, \e{and} neither state has the
-\q{cheated} flag set.
-\H{writing-testing} Things to test once your puzzle is written
-Puzzle implementations written in this framework are self-testing as
-far as I could make them.
-Textual game and move descriptions, for example, are generated and
-parsed as part of the normal process of play. Therefore, if you can
-make moves in the game \e{at all} you can be reasonably confident
-that the mid-end serialisation interface will function correctly and
-you will be able to save your game. (By contrast, if I'd stuck with
-a single \cw{make_move()} function performing the jobs of both
-\cw{interpret_move()} and \cw{execute_move()}, and had separate
-functions to encode and decode a game state in string form, then
-those functions would not be used during normal play; so they could
-have been completely broken, and you'd never know it until you tried
-to save the game \dash which would have meant you'd have to test
-game saving \e{extensively} and make sure to test every possible
-type of game state. As an added bonus, doing it the way I did leads
-to smaller save files.)
-There is one exception to this, which is the string encoding of the
-\c{game_ui}. Most games do not store anything permanent in the
-\c{game_ui}, and hence do not need to put anything in its encode and
-decode functions; but if there is anything in there, you do need to
-test game loading and saving to ensure those functions work
-properly.
-It's also worth testing undo and redo of all operations, to ensure
-that the redraw and the animations (if any) work properly. Failing
-to animate undo properly seems to be a common error.
-Other than that, just use your common sense.