shithub: puzzles

Info  •  Files  •  Log  •  Branches

Update the developer documentation.

It's got a bit out of date over the years, with some changes to the
code not fully reflected in it (e.g. not all the int -> bool type
changes were documented, and TRUE and FALSE were still mentioned),
and quite a lot of new functions not added. (In particular, the dsf
API was not documented, and it certainly should have been, if only so
that people can find out what it even stands for!)

As well as correcting for factual accuracy, two content changes in the
advice chapter:

I've reworded the definition of 'fairness' to explicitly mention that
requiring the player to use Undo is cheating. That's always how I
_intended_ the definition, but I didn't say it clearly enough.

And I've added an entire new section describing the normal sensible
way to implement redraw(), via a loop of the form 'work out what this
cell should look like, check it against an array in game_drawstate of
the last state we drew it in, and if they're different, call a redraw
function'. That was mentioned in passing in two other sections, but I
know at least one developer didn't find it, so now it's less well
hidden.

--- a/devel.but

+++ b/devel.but

@@ -32,10 +32,11 @@

 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.

+This guide is believed correct as of \cw{git} commit

+\cw{b34f8b1ee33163af988c75587e6ac99739b7684f}. 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

@@ -52,9 +53,6 @@

 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

@@ -61,16 +59,15 @@

 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.

+port of Puzzles. There is no centralised mechanism for maintaining the

+menu layout, for example. This has a cost in consistency (when I

+\e{do} want the same menu layout on more than one platform, I have to

+edit N pieces of code in parallel every time I make a change), but the

+advantage is that local GUI conventions can be conformed to and local

+constraints adapted to. For example, MacOS has strict human interface

+guidelines which specify a different menu layout from the one I've

+used on Windows and GTK; there's nothing stopping the MacOS front end

+from providing a menu layout consistent with those guidelines.

 Although the front end is mostly caller rather than the callee in

 its interactions with other parts of the code, it is required to

@@ -143,9 +140,10 @@

 \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).

+half-finished game to a disk file; for handling application shutdown

+and restart on platforms such as PalmOS where state is expected to be

+saved; for storing the previous game in order to undo and redo across

+a New Game event).

 Thus, there's a lot of work done once by the mid-end so that

 individual back ends don't have to worry about it. All the back end

@@ -249,14 +247,15 @@

 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.)

+\cw{compute_size()} function may refer to; this means that any aspect

+of the game which affects the size of the window it needs to be drawn

+in (other than the magnification level) must be stored in

+\c{game_params}. In particular, this imposes the fundamental

+limitation that random game generation may not have a random effect on

+the window size: game generation algorithms are constrained to work by

+starting from the grid size rather than generating it as an emergent

+phenomenon. (Although this is a restriction in theory, it has not yet

+seemed to be a problem.)

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

@@ -268,15 +267,26 @@

 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.

+Therefore, a good means of deciding whether a data item needs to go in

+\c{game_state} is: would a player expect that data item to be restored

+on undo? If so, put it in \c{game_state}, and this will automatically

+happen without you having to lift a finger. If not, then you might

+have found a data item that needs to go in \c{game_ui} instead.

+Two quite different examples of this:

+

+\b if the game provides an interface for making moves by moving a

+cursor around the grid with the keyboard and pressing some other key

+when you get to a square you want to change, then the location of that

+cursor belongs in \c{game_ui}, because the player will want to undo

+one \e{square change} at a time, not one \e{cursor movement} at a

+time.

+

+\b Mines tracks the number of times you opened a mine square and died.

+Every time you do that, you can only continue the game by pressing

+Undo. So the deaths counter belongs in \c{game_ui}, because otherwise,

+it would revert to 0 every time you undid your mistaken move.

+

 During play, \c{game_state}s are often passed around without an

 accompanying \c{game_params} structure. Therefore, any information

 in \c{game_params} which is important during play (such as the grid

@@ -293,12 +303,12 @@

 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).

+the array of grid squares in the \c{game_state}, but describing what

+was drawn in the window on the most recent redraw. This is used to

+identify the squares that need redrawing next time, by deciding what

+the new value in that array should be, and comparing it to what was

+drawn last time. See \k{writing-howto-redraw} for more on this

+subject.

 \c{game_drawstate} is occasionally completely torn down and

 reconstructed by the mid-end, if the user somehow forces a full

@@ -356,25 +366,42 @@

 monolithic platforms, and anywhere else that the front end needs to

 know the name of a game.

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

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

-\c const char *winhelp_topic;

+\c const char *winhelp_topic, *htmlhelp_topic;

-This member is used on Windows only, to provide online help.

+These members are used on Windows only, to provide online help.

 Although the Windows front end provides a separate binary for each

 puzzle, it has a single monolithic help file; so when a user selects

 \q{Help} from the menu, the program needs to open the help file and

 jump to the chapter describing that particular puzzle.

-Therefore, each chapter in \c{puzzles.but} is labelled with a

-\e{help topic} name, similar to this:

+This code base still supports the legacy \cw{.HLP} Windows Help format

+as well as the less old \cw{.CHM} HTML Help format. The two use

+different methods of identifying topics, so you have to specify both.

+Each chapter about a puzzle in \c{puzzles.but} is labelled with a

+\e{help topic} name for Windows Help, which typically appears just

+after the \cw{\\C} chapter title paragraph, similar to this:

+

+\c \C{net} \i{Net}

+\c

 \c \cfg{winhelp-topic}{games.net}

-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.

+But HTML Help is able to use the Halibut identifier for the chapter

+itself, i.e. the keyword that appears in braces immediatey after the

+\cw{\\C}.

+So the corresponding game back end encodes the \c{winhelp-topic}

+string (here \cq{games.net}) in the \c{winhelp_topic} element of the

+game structure, and puts the chapter identifier (here \cq{net}) in the

+\c{htmlhelp_topic} element. For example:

+

+\c const struct game thegame = {

+\c    "Net", "games.net", "net",

+\c    // ...

+\c };

+

 \H{backend-params} Handling game parameter sets

 In this section I present the various functions which handle the

@@ -466,16 +493,18 @@

 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.

+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);

@@ -489,7 +518,7 @@

 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

+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.

@@ -592,10 +621,8 @@

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

-\c int bval;

+\c bool bval;

-which is either \cw{TRUE} or \cw{FALSE}.

-

 }

 \dt \c{C_CHOICES}

@@ -634,7 +661,7 @@

 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

+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()}

@@ -659,7 +686,7 @@

 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

+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()}

@@ -999,10 +1026,11 @@

 \dd Indicate that an arrow key was pressed.

-\dt \cw{CURSOR_SELECT}

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

-\dd On platforms which have a prominent \q{select} button alongside

-their cursor keys, indicates that that button was pressed.

+\dd On platforms which have one or two prominent \q{select} button

+alongside their cursor keys, indicates that one of those buttons was

+pressed.

 In addition, there are some modifiers which can be bitwise-ORed into

 the \c{button} parameter:

@@ -1132,10 +1160,10 @@

 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).

+The data element \c{preferred_tilesize} indicates the tile size which

+should be used in the absence of a good reason to do otherwise (such

+as the screen being too small to fit the whole puzzle, or the user

+explicitly requesting a resize).

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

@@ -1303,7 +1331,7 @@

 interest.

 This function is called by only

-\cw{midend_get_cursor_location()}(\k{midend-get-cursor-location}). Its

+\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

@@ -1454,7 +1482,7 @@

 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

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

 called.

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

@@ -1508,7 +1536,7 @@

 \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

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

 called.

 \H{backend-misc} Miscellaneous

@@ -1552,7 +1580,7 @@

 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

+\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

@@ -1569,8 +1597,8 @@

 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

+\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

@@ -1587,7 +1615,9 @@

 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).

+tiles, etc). If the \c{redraw()} function ever intends to call

+\c{status_bar()} in the drawing API (\k{drawing-status-bar}), then it

+should set this flag to \c{true}.

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

@@ -1626,7 +1656,7 @@

 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     char *label; /* label for frontend use */

 \c     int button; /* button to pass to midend */

 \c } key_label;

@@ -1636,6 +1666,12 @@

 label. The \cw{button} field is the associated code that can be passed

 to the midend when the frontend deems appropriate.

+If \cw{label} is not \cw{NULL}, then it's a dynamically allocated

+string. Therefore, freeing an array of these structures needs more

+than just a single free operatio. The function \c{free_keys()}

+(\k{utils-free-keys}) can be used to free a whole array of these

+structures conveniently.

+

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

 returned array.

@@ -1762,12 +1798,13 @@

 \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.

+to draw the puzzle's graphics on the window's drawing area. The back

+end function \cw{print()} similarly draws the puzzle on paper, if the

+puzzle is printable. To do this portably, the back end is provided

+with a drawing API allowing it to talk directly to the front end. In

+this chapter I document that API, both for the benefit of back end

+authors trying to use it and for front end authors trying to implement

+it.

 The drawing API as seen by the back end is a collection of global

 functions, each of which takes a pointer to a \c{drawing} structure

@@ -1919,6 +1956,22 @@

 This function may be used for both drawing and printing.

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

+

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

+

+Draws four L-shapes at the corners of a square, in the manner of a

+target reticule. This is a convenience function for back ends to use

+to display a keyboard cursor (if they want one in that style).

+

+\c{cx} and \c{cy} give the coordinates of the centre of the square.

+\c{r} is half the side length of the square, so that the corners are

+at \cw{(cx-r,cy-r)}, \cw{(cx+r,cy-r)}, \cw{(cx-r,cy+r)} and

+\cw{(cx+r,cy+r)}.

+

+\c{colour} is an integer index into the colours array returned by

+the back end function \cw{colours()} (\k{backend-colours}).

+

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

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

@@ -2141,6 +2194,7 @@

 \c static const char *const times_signs[] = { "\xC3\x97", "x" };

 \c char *times_sign = text_fallback(dr, times_signs, 2);

 \c sprintf(buffer, "%d%s%d", width, times_sign, height);

+\c sfree(times_sign);

 \c draw_text(dr, x, y, font, size, align, colour, buffer);

 \c sfree(buffer);

@@ -2219,8 +2273,9 @@

 (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.)

+within the back end redraw function. And it's implemented by front

+ends via the \c{drawing_api} function pointer table. So this is the

+best place to document it.)

 The supplied text is filtered through the mid-end for optional

 rewriting before being passed on to the front end; the mid-end will

@@ -2758,6 +2813,17 @@

 may define this function pointer to be \cw{NULL}; it will never be

 called unless printing is attempted.

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

+

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

+

+This function is called to toggle drawing of dotted lines, during

+printing only.

+

+Implementations of this API which do not provide printing services

+may define this function pointer to be \cw{NULL}; it will never be

+called unless printing is attempted.

+

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

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

@@ -2804,8 +2870,8 @@

 \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)

+\c void print_get_colour(drawing *dr, int colour, bool printing_in_colour,

+\c                       int *hatch, float *r, float *g, float *b);

 This function is called by the implementations of the drawing API

 functions when they are called in a printing context. It takes a

@@ -2812,8 +2878,8 @@

 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

+\c{printing_in_colour} is \cw{true} iff the implementation is printing

+in colour. This will alter the results returned if the colour in

 question was specified with a black-and-white fallback value.

 If the colour should be rendered by hatching, \c{*hatch} is filled

@@ -2843,7 +2909,7 @@

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

 \c midend *midend_new(frontend *fe, const game *ourgame,

-\c                    const drawing_api *drapi, void *drhandle)

+\c                    const drawing_api *drapi, void *drhandle);

 Allocates and returns a new mid-end structure.

@@ -2934,7 +3000,7 @@

 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

+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

@@ -2980,7 +3046,7 @@

 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}).

+\c{user_size} set to \cw{false}).

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

@@ -3049,12 +3115,16 @@

 \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

+The front end calls this function to report a mouse or keyboard event.

+The parameters \c{x} and \c{y} are identical to the ones passed to the

+back end function \cw{interpret_move()} (\k{backend-interpret-move}).

+

+\c{button} is \e{almost} identical to the parameter passed to

+\cw{interpret_move()}. However, some additional special button values

+are defined for the front end to pass to the midend (see below).

+

+Also, the front end is \e{not} required to provide guarantees about

+mouse event ordering. The mid-end will sort out multiple simultaneous

 button presses and changes of button; the front end's responsibility

 is simply to pass on the mouse events it receives as accurately as

 possible.

@@ -3085,6 +3155,39 @@

 A front end should shut down the puzzle in response to a \cw{false}

 return.

+The following additional values of \c{button} are permitted to be

+passed to this function by the front end, but are never passed on to

+the back end. They indicate front-end specific UI operations, such as

+selecting an option from a drop-down menu. (Otherwise the front end

+would have to translate the \q{New Game} menu item into an \cq{n}

+keypress, for example.)

+

+\dt \cw{UI_NEWGAME}

+

+\dd Indicates that the user requested a new game, similar to pressing

+\cq{n}.

+

+\dt \cw{UI_SOLVE}

+

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

+

+\dt \cw{UI_UNDO}

+

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

+

+\dt \cw{UI_REDO}

+

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

+

+\dt \cw{UI_QUIT}

+

+\dd Indicates that the user asked to quit the game. (Of course, a

+front end might perfectly well handle this on its own. But including

+it in this enumeration allows the front end to treat all these menu

+items the same, by translating each of them into a button code passed

+to the midend, and handle quitting by noticing the \c{false} return

+value from \cw{midend_process_key()}.)

+

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

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

@@ -3240,6 +3343,13 @@

 description itself. This should be used when the user selects

 \q{Random Seed} from the game menu (or equivalent).

+(A fourth value \cw{CFG_FRONTEND_SPECIFIC} is provided in this

+enumeration, so that frontends can extend it for their own internal

+use. For example, you might wrap this function with a

+\cw{frontend_get_config} which handles some values of \c{which} itself

+and hands others on to the midend, depending on whether \cw{which <

+CFG_FRONTEND_SPECIFIC}.)

+

 The returned value is an array of \cw{config_item}s, exactly as

 described in \k{backend-configure}. Another returned value is an

 ASCII string giving a suitable title for the configuration window,

@@ -3300,7 +3410,7 @@

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

-\c char *midend_get_game_id(midend *me)

+\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

@@ -3308,7 +3418,7 @@

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

-\c char *midend_get_random_seed(midend *me)

+\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.

@@ -3335,8 +3445,8 @@

 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

+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

@@ -3532,6 +3642,13 @@

 relieve most front ends of the need to provide an empty

 implementation.

+\H{midend-which-game} \cw{midend_which_game()}

+

+\c const game *midend_which_preset(midend *me);

+

+This function returns the \c{game} structure for the puzzle type this

+midend is committed to.

+

 \H{frontend-backend} Direct reference to the back end structure by

 the front end

@@ -3693,7 +3810,7 @@

 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

+same sequence of functions is subsequently called on both the copy and

 the original, the results will be identical.  This may be useful for

 speculatively performing some operation using a given random state,

 and later replaying that operation precisely.

@@ -3715,7 +3832,8 @@

 \c unsigned long random_upto(random_state *state, unsigned long limit);

-Returns a random number from 0 to \cw{limit-1} inclusive.

+Returns a random number from 0 to \cw{limit-1} inclusive. \c{limit}

+may not be zero.

 \S{utils-random-state-encode} \cw{random_state_encode()}

@@ -3898,6 +4016,16 @@

 (See \k{backend-configure} for details of the \c{config_item}

 structure.)

+\S{utils-free-keys} \cw{free_keys()}

+

+\c void free_keys(key_label *keys, int nkeys);

+

+This function correctly frees an array of \c{key_label}s, including

+the dynamically allocated label string for each key.

+

+(See \k{backend-request-keys} for details of the \c{key_label}

+structure.)

+

 \H{utils-tree234} Sorted and counted tree functions

 Many games require complex algorithms for generating random puzzles,

@@ -4214,19 +4342,386 @@

 and every time it is called, the \c{state} parameter will be set to

 the value you passed in as \c{copyfnstate}.

+\H{utils-dsf} Disjoint set forests

+

+This section describes a set of functions implementing the data

+structure variously known as \q{union-find} or \q{Tarjan's disjoint

+set forest}. In this code base, it's universally abbreviated as a

+\q{dsf}.

+

+A dsf represents a collection of elements partitioned into

+\q{equivalence classes}, in circumstances where equivalences are added

+incrementally. That is, all elements start off considered to be

+different, and you gradually declare more and more of them to be equal

+via the \cw{dsf_merge()} operation, which says that two particular

+elements should be regarded as equal from now on.

+

+For example, if I start off with A,B,U,V all distinct, and I merge A

+with B and merge U with V, then the structure will tell me that A and

+U are not equivalent. But if I then merge B with V, then after that,

+the structure will tell me that A and U \e{are} equivalent, by

+following the transitive chain of equivalences it knows about.

+

+The dsf data structure is therefore ideal for tracking incremental

+connectivity in an undirected graph (again, \q{incremental} meaning

+that you only ever add edges, never delete them), and other

+applications in which you gradually acquire knowledge you didn't

+previously have about what things are the same as each other. It's

+used extensively in puzzle solver and generator algorithms, and

+sometimes during gameplay as well.

+

+The time complexity of dsf operations is not \e{quite} constant time,

+in theory, but it's so close to it as to make no difference in

+practice. In particular, any time a dsf has to do non-trivial work, it

+updates the structure so that that work won't be needed a second time.

+Use dsf operations without worrying about how long they take!

+

+These functions also support an \q{extended} version of a dsf (spelled

+\q{edsf}), in which each equivalence class is itself partitioned into

+two sub-classes. When you merge two elements, you say whether they're

+in the same class or in opposite classes; when you test equivalence,

+you can find out whether the two elements you're asking about are in

+the same or opposite classes. For example, in a puzzle containing

+black and white squares, you might use an edsf to track the solver's

+knowledge about whether each pair of squares were (a) the same colour;

+(b) opposite colours; (c) currently not known to be related.

+

+As well as querying whether two elements are equivalent, this dsf

+implementation also allows you to ask for the number of elements in a

+given equivalence class, and the smallest element in the class. (The

+latter is used, for example, to decide which square to print the clue

+in each region of a Keen puzzle.)

+

+\S{utils-dsf-new} \cw{snew_dsf()}

+

+\c int *snew_dsf(int size);

+

+Allocates space for a dsf describing \c{size} elements, and

+initialises it so that every element is in an equivalence class by

+itself.

+

+The elements described by the dsf are represented by the integers from

+\cw{0} to \cw{size-1} inclusive.

+

+The returned memory is a single allocation, so you can free it easily

+using \cw{sfree()}.

+

+Dsfs and edsfs are represented in the same way, so this function can

+be used to allocate either kind.

+

+\S{utils-dsf-init} \cw{dsf_init()}

+

+\c void dsf_init(int *dsf, int size);

+

+Reinitialises an existing dsf to the state in which all elements are

+distinct, without having to free and reallocate it.

+

+\S{utils-dsf-merge} \cw{dsf_merge()}

+

+\c void dsf_merge(int *dsf, int v1, int v2);

+

+Updates a dsf so that elements \c{v1} and \c{v2} will now be

+considered to be in the same equivalence class. If they were already

+in the same class, this function will safely do nothing.

+

+\S{utils-dsf-canonify} \cw{dsf_canonify()}

+

+\c int dsf_canonify(int *dsf, int val);

+

+Returns the \q{canonical} element of the equivalence class in the dsf

+containing \c{val}. This will be some element of the same equivalence

+class. So in order to determine whether two elements are in the same

+equivalence class, you can call \cw{dsf_canonify} on both of them, and

+compare the results.

+

+Canonical elements don't necessarily stay the same if the dsf is

+mutated via \c{dsf_merge}. But between two calls to \c{dsf_merge},

+they stay the same.

+

+In this implementation, the canonical element is always the element

+with smallest index in the equivalence class.

+

+\S{utils-dsf-size} \cw{dsf_size()}

+

+\c int dsf_size(int *dsf, int val);

+

+Returns the number of elements currently in the equivalence class

+containing \c{val}.

+

+\c{val} itself counts, so in a newly created dsf, the return value

+will be 1.

+

+\S{utils-edsf-merge} \cw{edsf_merge()}

+

+\c void edsf_merge(int *dsf, int v1, int v2, bool inverse);

+

+Updates an edsf so that elements \c{v1} and \c{v2} are in the same

+equivalence class. If \c{inverse} is \cw{false}, they will be regarded

+as also being in the same subclass of that class; if \c{inverse} is

+\cw{true} then they will be regarded as being in opposite subclasses.

+

+If \c{v1} and \c{v2} were already in the same equivalence class, then

+the new value of \c{inverse} will be checked against what the edsf

+previously believed, and an assertion failure will occur if you

+contradict that.

+

+For example, if you start from a blank edsf and do this:

+

+\c edsf_merge(dsf, 0, 1, false);

+\c edsf_merge(dsf, 1, 2, true);

+

+then it will create a dsf in which elements 0,1,2 are all in the same

+class, with one subclasses containing 0,1 and the other containing 2.

+And then this call will do nothing, because it agrees with what the

+edsf already knew:

+

+\c edsf_merge(dsf, 0, 2, true);

+

+But this call will fail an assertion:

+

+\c edsf_merge(dsf, 0, 2, false);

+

+\S{utils-edsf-canonify} \cw{edsf_canonify()}

+

+\c int edsf_canonify(int *dsf, int val, bool *inverse);

+

+Like \c{dsf_canonify()}, this returns the canonical element of the

+equivalence class of an edsf containing \c{val}. It also fills in

+\c{*inverse} with a flag indicating whether \c{val} and the canonical

+element are in opposite subclasses: \cw{true} if they are in opposite

+subclasses, or \cw{false} if they're in the same subclass.

+

+So if you want to know the relationship between \c{v1} and \c{v2}, you

+can do this:

+

+\c bool inv1, inv2;

+\c int canon1 = edsf_canonify(dsf, v1, &inv1);

+\c int canon2 = edsf_canonify(dsf, v2, &inv2);

+\c if (canon1 != canon2) {

+\c     // v1 and v2 have no known relation

+\c } else if (inv1 == inv2) {

+\c     // v1 and v2 are in the same subclass of the same class

+\c } else {

+\c     // v1 and v2 are in opposite subclasses of the same class

+\c }

+

+\H{utils-tdq} To-do queues

+

+This section describes a set of functions implementing a \q{to-do

+queue}, a simple de-duplicating to-do list mechanism. The code calls

+this a \q{tdq}.

+

+A tdq can store integers up to a given size (specified at creation

+time). But it can't store the same integer more than once. So you can

+quickly \e{make sure} an integer is in the queue (which will do

+nothing if it's already there), and you can quickly pop an integer

+from the queue and return it, both in constant time.

+

+The idea is that you might use this in a game solver, in the kind of

+game where updating your knowledge about one square of a grid means

+there's a specific other set of squares (such as its neighbours) where

+it's now worth attempting further deductions. So you keep a tdq of all

+the grid squares you plan to look at next, and every time you make a

+deduction in one square, you add the neighbouring squares to the tdq

+to make sure they get looked at again after that.

+

+In solvers where deductions are mostly localised, this avoids the

+slowdown of having to find the next thing to do every time by looping

+over the whole grid: instead, you can keep checking the tdq for

+\e{specific} squares to look at, until you run out.

+

+However, it's common to have games in which \e{most} deductions are

+localised, but not all. In that situation, when your tdq is empty, you

+can re-fill it with every square in the grid using \cw{tdq_fill()},

+which will force an iteration over everything again. And then if the

+tdq becomes empty \e{again} without you having made any progress, give

+up.

+

+\S{utils-tdq-new} \cw{tdq_new()}

+

+\c tdq *tdq_new(int n);

+

+Allocates space for a tdq that tracks items from \cw{0} to \cw{size-1}

+inclusive.

+

+\S{utils-tdq-free} \cw{tdq_free()}

+

+\c void tdq_free(tdq *tdq);

+

+Frees a tdq.

+

+\S{utils-tdq-add} \cw{tdq_add()}

+

+\c void tdq_add(tdq *tdq, int k);

+

+Adds the value \c{k} to a tdq. If \c{k} was already in the to-do list,

+does nothing.

+

+\S{utils-tdq-remove} \cw{tdq_remove()}

+

+\c int tdq_remove(tdq *tdq);

+

+Removes one item from the tdq, and returns it. If the tdq is empty,

+returns \cw{-1}.

+

+\S{utils-tdq-fill} \cw{tdq_fill()}

+

+\c void tdq_fill(tdq *tdq);

+

+Fills a tdq with every element it can possibly keep track of.

+

+\H{utils-findloop} Finding loops in graphs and grids

+

+Many puzzles played on grids or graphs have a common gameplay element

+of connecting things together into paths in such a way that you need

+to avoid making loops (or, perhaps, making the \e{wrong} kind of

+loop).

+

+Just determining \e{whether} a loop exists in a graph is easy, using a

+dsf tracking connectivity between the vertices. Simply iterate over

+each edge of the graph, merging the two vertices at each end of the

+edge \dash but before you do that, check whether those vertices are

+\e{already} known to be connected to each other, and if they are, then

+the new edge is about to complete a loop.

+

+But if you also want to identify \e{exactly} the set of edges that are

+part of any loop, e.g. to highlight the whole loop red during

+gameplay, then that's a harder problem. This API is provided here for

+all puzzles to use for that purpose.

+

+\S{utils-findloop-new-state} \cw{findloop_new_state()}

+

+\c struct findloopstate *findloop_new_state(int nvertices);

+

+Allocates a new state structure for the findloop algorithm, capable of

+handling a graph with up to \c{nvertices} vertices. The vertices will

+be represented by integers between \c{0} and \c{nvertices-1} inclusive.

+

+\S{utils-findloop-free-state} \cw{findloop_free_state()}

+

+\c void findloop_free_state(struct findloopstate *state);

+

+Frees a state structure allocated by \cw{findloop_new_state()}.

+

+\S{utils-findloop-run} \cw{findloop_run()}

+

+\c bool findloop_run(struct findloopstate *state, int nvertices,

+\c                   neighbour_fn_t neighbour, void *ctx);

+

+Runs the loop-finding algorithm, which will explore the graph and

+identify whether each edge is or is not part of any loop.

+

+The algorithm will call the provided function \c{neighbour} to list

+the neighbouring vertices of each vertex. It should have this

+prototype:

+

+\c int neighbour(int vertex, void *ctx);

+

+In this callback, \c{vertex} will be the index of a vertex when the

+algorithm \e{first} calls it for a given vertex. The function should

+return the index of one of that vertex's neighbours, or a negative

+number if there are none.

+

+If the function returned a vertex, the algorithm will then call

+\c{neighbour} again with a \e{negative} number as the \c{vertex}

+parameter, which means \q{please give me another neighbour of the same

+vertex as last time}. Again, the function should return a vertex

+index, or a negative number to indicate that there are no more

+vertices.

+

+The \c{ctx} parameter passed to \cw{findloop_run()} is passed on

+unchanged to \c{neighbour}, so you can point that at your game state

+or solver state or whatever.

+

+The return value is \cw{true} if at least one loop exists in the

+graph, and \cw{false} if no loop exists. Also, the algorithm state

+will have been filled in with information that the following query

+functions can use to ask about individual graph edges.

+

+\S{utils-findloop-is-loop-edge} \cw{findloop_is_loop_edge()}

+

+\c bool findloop_is_loop_edge(struct findloopstate *state,

+\c                            int u, int v);

+

+Queries whether the graph edge between vertices \c{u} and \c{v} is

+part of a loop. If so, the return value is \cw{true}, otherwise

+\cw{false}.

+

+\S{utils-findloop-is-bridge} \cw{findloop_is_bridge()}

+

+\c bool findloop_is_bridge(struct findloopstate *pv,

+\c     int u, int v, int *u_vertices, int *v_vertices);

+

+Queries whether the graph edge between vertices \c{u} and \c{v} is a

+\q{bridge}, i.e. an edge which would break the graph into (more)

+disconnected components if it were removed.

+

+This is the exact inverse of the \q{loop edge} criterion: a vertex

+returns \cw{true} from \cw{findloop_is_loop_edge()} if and only if it

+returns \cw{false} from \cw{findloop_is_bridge()}, and vice versa.

+

+However, \cw{findloop_is_bridge()} returns more information. If it

+returns \cw{true}, then it also fills in \c{*u_vertices} and

+\c{*v_vertices} with the number of vertices connected to the \c{u} and

+\c{v} sides of the bridge respectively.

+

+For example, if you have three vertices A,B,C all connected to each

+other, and four vertices U,V,W,X all connected to each other, and a

+single edge between A and V, then calling \cw{findloop_is_bridge()} on

+the pair A,V will return true (removing that edge would separate the

+two sets from each other), and will report that there are three

+vertices on the A side and four on the V side.

+

+\H{utils-combi} Choosing r things out of n

+

+This section describes a small API for iterating over all combinations

+of r things out of n.

+

+For example, if you asked for all combinations of 3 things out of 5,

+you'd get back the sets \{0,1,2\}, \{0,1,3\}, \{0,1,4\}, \{0,2,3\},

+\{0,2,4\}, \{0,3,4\}, \{1,2,3\}, \{1,2,4\}, \{1,3,4\}, and \{2,3,4\}.

+

+These functions use a structure called a \c{combi_ctx}, which contains

+an element \c{int *a} holding each returned combination, plus other

+fields for implementation use only.

+

+\S{utils-combi-new} \cw{new_combi()}

+

+\c combi_ctx *new_combi(int r, int n);

+

+Allocates a new \c{combi_ctx} structure for enumerating r things out

+of n.

+

+\S{utils-combi-free} \cw{free_combi()}

+

+\c void free_combi(combi_ctx *combi);

+

+Frees a \c{combi_ctx} structure.

+

+\S{utils-combi-reset} \cw{reset_combi()}

+

+\c void reset_combi(combi_ctx *combi);

+

+Resets an existing \c{combi_ctx} structure to the start of its

+iteration

+

+\S{utils-combi-next} \cw{next_combi()}

+

+\c combi_ctx *next_combi(combi_ctx *combi);

+

+Requests a combination from a \c{combi_ctx}.

+

+If there are none left to return, the return value is \cw{NULL}.

+Otherwise, it returns the input structure \c{combi}, indicating that

+it has filled in \cw{combi->a[0]}, \cw{combi->a[1]}, ...,

+\cw{combi->a[r-1]} with an increasing sequence of distinct integers

+from \cw{0} to \cw{n-1} inclusive.

+

 \H{utils-misc} Miscellaneous utility functions and macros

 This section contains all the utility functions which didn't

 sensibly fit anywhere else.

-\S{utils-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

@@ -4246,7 +4741,7 @@

 \S{utils-obfuscate-bitmap} \cw{obfuscate_bitmap()}

-\c void obfuscate_bitmap(unsigned char *bmp, int bits, int decode);

+\c void obfuscate_bitmap(unsigned char *bmp, int bits, bool decode);

 This function obscures the contents of a piece of data, by

 cryptographic methods. It is useful for games of hidden information

@@ -4277,8 +4772,8 @@

 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

+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.)

@@ -4307,6 +4802,53 @@

 This function is the inverse of \cw{bin2hex()}.

+\S{utils-fgetline} \cw{fgetline()}

+

+\c char *fgetline(FILE *fp);

+

+This function reads a single line of text from a standard C input

+stream, and returns it as a dynamically allocated string. The returned

+string still has a newline on the end.

+

+\S{utils-arraysort} \cw{arraysort()}

+

+Sorts an array, with slightly more flexibility than the standard C

+\cw{qsort()}.

+

+This function is really implemented as a macro, so it doesn't have a

+prototype as such. But you could imagine it having a prototype like

+this:

+

+\c void arraysort(element_t *array, size_t nmemb,

+\c                arraysort_cmpfn_t cmp, void *ctx);

+

+in which \c{element_t} is an unspecified type.

+

+(Really, there's an underlying function that takes an extra parameter

+giving the size of each array element. But callers are encouraged to

+use this macro version, which fills that in automatically using

+\c{sizeof}.)

+

+This function behaves essentially like \cw{qsort()}: it expects

+\c{array} to point to an array of \c{nmemb} elements, and it will sort

+them in place into the order specified by the comparison function

+\c{cmp}.

+

+The comparison function should have this prototype:

+

+\c int cmp(const void *a, const void *b, void *ctx);

+

+in which \c{a} and \c{b} point at the two elements to be compared, and

+the return value is negative if \cw{a<b} (that is, \c{a} should appear

+before \c{b} in the output array), positive if \cw{a>b}, or zero if

+\c{a=b}.

+

+The \c{ctx} parameter to \cw{arraysort()} is passed directly to the

+comparison function. This is the feature that makes \cw{arraysort()}

+more flexible than standard \cw{qsort()}: it lets you vary the sorting

+criterion in a dynamic manner without having to write global variables

+in the caller for the compare function to read.

+

 \S{utils-game-mkhighlight} \cw{game_mkhighlight()}

 \c void game_mkhighlight(frontend *fe, float *ret,

@@ -4342,6 +4884,20 @@

 to RGB values defining a sensible background colour, and similary

 \c{highlight} and \c{lowlight} will be set to sensible colours.

+\S{utils-game-mkhighlight-specific} \cw{game_mkhighlight_specific()}

+

+\c void game_mkhighlight_specific(frontend *fe, float *ret,

+\c     int background, int highlight, int lowlight);

+

+This function behaves exactly like \cw{game_mkhighlight()}, except

+that it expects the background colour to have been filled in

+\e{already} in the elements \cw{ret[background*3]} to

+\cw{ret[background*3+2]}. It will fill in the other two colours as

+brighter and darker versions of that.

+

+This is useful if you want to show relief sections of a puzzle in more

+than one base colour.

+

 \S{utils-button2label} \cw{button2label()}

 \c char *button2label(int button);

@@ -4360,6 +4916,82 @@

 The returned string is dynamically allocated and should be

 \cw{sfree}'d by the caller.

+\S{utils-move-cursor} \cw{move_cursor()}

+

+\c void move_cursor(int button, int *x, int *y, int w, int h,

+\c                  bool wrap);

+

+This function can be called by \cw{interpret_move()} to implement the

+default keyboard API for moving a cursor around a grid.

+

+\c{button} is the same value passed in to \cw{interpret_move()}. If

+it's not any of \cw{CURSOR_UP}, \cw{CURSOR_DOWN}, \cw{CURSOR_LEFT} or

+\cw{CURSOR_RIGHT}, the function will do nothing.

+

+\c{x} and \c{y} point to two integers which on input give the current

+location of a cursor in a square grid. \c{w} and \c{h} give the

+dimensions of the grid. On return, \c{x} and \c{y} are updated to give

+the cursor's new position according to which arrow key was pressed.

+

+This function assumes that the grid coordinates run from \cw{0} to

+\cw{w-1} inclusive (left to right), and from \cw{0} to \cw{h-1}

+inclusive (top to bottom).

+

+If \c{wrap} is \cw{true}, then trying to move the cursor off any edge

+of the grid will result in it wrapping round to the corresponding

+square on the opposite edge. If \c{wrap} is \cw{false}, such a move

+will have no effect.

+

+\S{utils-divvy-rectangle} \cw{divvy_rectangle()}

+

+\c int *divvy_rectangle(int w, int h, int k, random_state *rs);

+

+Invents a random division of a rectangle into same-sized polyominoes,

+such as is found in the block layout of a Solo puzzle in jigsaw mode,

+or the solution to a Palisade puzzle.

+

+\c{w} and \c{h} are the dimensions of the rectangle. \c{k} is the size

+of polyomino desired. It must be a factor of \c{w*h}.

+

+\c{rs} is a \cw{random_state} used to supply the random numbers to

+select a random division of the rectangle.

+

+The return value is a dsf (see \k{utils-dsf}) whose equivalence

+classes correspond to the polyominoes that the rectangle is divided

+into. The indices of the dsf are of the form \c{y*w+x}, for the cell

+with coordinates \cw{x,y}.

+

+\S{utils-domino-layout} \cw{domino_layout()}

+

+\c int *domino_layout(int w, int h, random_state *rs);

+

+Invents a random tiling of a rectangle with dominoes.

+

+\c{w} and \c{h} are the dimensions of the rectangle. If they are both

+odd, then one square will be left untiled.

+

+\c{rs} is a \cw{random_state} used to supply the random numbers to

+select a random division of the rectangle.

+

+The return value is an array in which element \c{y*w+x} represents the

+cell with coordinates \cw{x,y}. Each element of the array gives the

+index (in the same representation) of the other end of its domino. If

+there's a left-over square, then that element contains its own index.

+

+\S{utils-domino-layout-prealloc} \cw{domino_layout_prealloc()}

+

+\c void domino_layout_prealloc(int w, int h, random_state *rs,

+\c                             int *grid, int *grid2, int *list);

+

+Just like \cw{domino_layout()}, but does no memory allocation. You can

+use this to save allocator overhead if you expect to need to generate

+many domino tilings of the same grid.

+

+\c{grid} and \c{grid2} should each have space for \cw{w*h} ints.

+\c{list} should have space for \c{2*w*h} ints.

+

+The returned array is delivered in \c{grid}.

+

 \C{writing} How to write a new puzzle

 This chapter gives a guide to how to actually write a new puzzle:

@@ -4378,43 +5010,49 @@

 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

+\e{fair}. A fair game is one which a player can only fail to complete

+through demonstrable lack of skill \dash that is, such that a better

+player presented with the same game state would have \e{known} to do

 something different.

 For a start, that means every game presented to the user must have

-\e{at least one solution}. Giving the unsuspecting user a puzzle

-which is actually impossible is not acceptable. (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.)

+\e{at least one solution}. Giving the unsuspecting user a puzzle which

+is actually impossible is not acceptable.

-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.

+(An exception to this: if the user has selected some non-default

+option which is clearly labelled as potentially unfair, \e{then}

+you're allowed to generate possibly insoluble puzzles, because the

+user isn't unsuspecting any more. Same Game and Mines both have

+options of this type.)

-(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.)

+Secondly, if the game includes hidden information, then it must be

+possible to deduce a correct move at every stage from the currently

+available information. It's not enough that there should exist some

+sequence of moves which will get from the start state to the solved

+state, if the player doesn't necessarily have enough information to

+\e{find} that solution. For example, in the card solitaire game

+Klondike, it's possible to reach a dead end because you had an

+arbitrary choice to make on no information, and made it the wrong way,

+which violates the fairness criterion, because a better player

+couldn't have known they needed to make the other choice.

+(Of course, games in this collection always have an Undo function, so

+if you did take the wrong route through a Klondike game, you could use

+Undo to back up and try a different choice. This doesn't count. In a

+fair game, you should be able to determine a correct move from the

+information visible \e{now}, without having to make moves to get more

+information that you can then back up and use.)

+

+Sometimes you can adjust the rules of an unfair puzzle to make it meet

+this definition of fairness. For example, more than one implementation

+of solitaire-style games (including card solitaires and Mahjong

+Solitaire) include a UI action to shuffle the remaining cards or tiles

+without changing their position; this action might be available at any

+time with a time or points penalty, or it might be illegal to use

+unless you have no other possible move. Adding an option like this

+would make a game \e{technically} fair, but it's better to avoid even

+that if you can.

+

 Providing a \e{unique} solution is a little more negotiable; it

 depends on the puzzle. Solo would have been of unacceptably low

 quality if it didn't always have a unique solution, whereas Twiddle

@@ -4730,8 +5368,103 @@

 a puzzle, and describes how to achieve them within the Puzzles

 framework.

-\S{writing-howto-cursor} Drawing objects at only one position

+\S{writing-howto-redraw} Redrawing just the changed parts of the window

+Redrawing the entire window on every move is wasteful. If the user

+makes a move changing only one square of a grid, it's better to redraw

+just that square.

+

+(Yes, computers are fast these days, but these puzzles still try to be

+portable to devices at the less fast end of the spectrum, so it's

+still worth saving effort where it's easy. On the other hand, some

+puzzles just \e{can't} do this easily \dash Untangle is an example

+that really does have no better option than to redraw everything.)

+

+For a typical grid-oriented puzzle, a robust way to do this is:

+

+\b Invent a data representation that describes everything about the

+appearance of a grid cell in the puzzle window.

+

+\b Have \c{game_drawstate} contain an array of those, describing the

+current appearance of each cell, as it was last drawn in the window.

+

+\b In \cw{redraw()}, loop over each cell deciding what the new

+appearance should be. If it's not the same as the value stored in

+\c{game_drawstate}, then redraw that cell, and update the entry in the

+\c{game_drawstate} array.

+

+Where possible, I generally make my data representation an integer

+full of bit flags, to save space, and to make it easy to compare the

+old and new versions. If yours needs to be bigger than that, you may

+have to define a small \cw{struct} and write an equality-checking

+function.

+

+The data representation of the \e{appearance} of a square in

+\c{game_drawstate} will not generally be identical to the

+representation of the \e{logical state} of a square in \c{game_state},

+because many things contribute to a square's appearance other than its

+logical state. For example:

+

+\b Extra information overlaid on the square by the user interface,

+such as a keyboard-controlled cursor, or highlighting of squares

+currently involved in a mouse drag action.

+

+\b Error highlights marking violations of the puzzle constraints.

+

+\b Visual intrusions into one square because of things in nearby

+squares. For example, if you draw thick lines along the edges between

+grid squares, then the corners of those lines will be visible in

+logically unrelated squares. An entry in the \c{game_drawstate} array

+should describe a specific \e{rectangular area of the screen}, so that

+those areas can be erased and redrawn independently \dash so it must

+represent anything that appears in that area, even if it's sticking

+out from a graphic that logically lives in some other square.

+

+\b Temporary changes to the appearance of a square because of an

+ongoing completion flash.

+

+\b The current display mode, if a game provides more than one. (For

+example, the optional letters distinguishing the different coloured

+pegs in Guess.)

+

+All of this must be included in the \c{game_drawstate} representation,

+but should not be in the \c{game_state} at all. \cw{redraw()} will

+pull it all together from the \c{game_state}, the \c{game_ui}, and the

+animation and flash parameters.

+

+To make sure that \e{everything} affecting a square's appearance is

+included in this representation, it's a good idea to have a separate

+function for drawing a grid square, and deliberately \e{not} pass it a

+copy of the \c{game_state} or the \c{game_ui} at all. That way, if you

+want that function to draw anything differently, you \e{have} to do it

+by including that information in the representation of a square's

+appearance.

+

+But of course there are a couple of exceptions to this rule. A few

+things \e{don't} have to go in the \c{game_drawstate} array, and can

+safely be passed separately to the redraw-square function:

+

+\b Anything that remains completely fixed throughout the whole of a

+game, such as the clues provided by the puzzle. This is safe because a

+\c{game_drawstate} is never reused between puzzle instances: when you

+press New Game, a new \c{game_drawstate} will always be created from

+scratch. So the \c{game_drawstate} only needs to describe everything

+that might \e{change} during gameplay. If you have a sub-\cw{struct}

+in your \c{game_state} that describes immutable properties of the

+current game, as suggested in \k{writing-ref-counting}, then it's safe

+to pass \e{that substructure} to the redraw-square function, and have

+it retrieve that information directly.

+

+\b How far through a move animation the last redraw was. When

+\cw{redraw()} is called multiple times during an animated move, it's

+much easier to just assume that any square involved in the animation

+will \e{always} need redrawing. So \c{anim_length} can safely be

+passed separately to the redraw-square function \dash but you also

+have to remember to redraw a square if \e{either} its appearance is

+different from the last redraw \e{or} it's involved in an animation.

+

+\S{writing-howto-cursor} Drawing an object at only one position

+

 A common phenomenon is to have an object described in the

 \c{game_state} or the \c{game_ui} which can only be at one position.

 A cursor \dash probably specified in the \c{game_ui} \dash is a good

@@ -4746,42 +5479,20 @@

 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):

+However, it is a mistake to assume that the same logic applies to the

+\c{game_drawstate}. If you replicate the cursor position fields in the

+draw state, the redraw code will get very complicated. In the draw

+state, in fact, it \e{is} probably the right thing to have a cursor

+flag for every position in the grid, and make it part of the

+representation of each square's appearance, as described in

+\k{writing-howto-redraw}. So when you iterate over each square in

+\c{redraw()} working out its position, you set the \q{cursor here}

+flag in the representation of the square's appearance, if its

+coordinates match the cursor coordinates stored in the \c{game_ui}.

+This will automatically ensure that when the cursor moves, the redraw

+loop will redraw the square that \e{previously} contained the cursor

+and doesn't any more, and the one that now contains the cursor.

-\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

@@ -4794,10 +5505,11 @@

 \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{""}.

+cursor position fields and returning \cw{UI_UPDATE}.

-\b \cw{interpret_move()} responds to some sort of fire button by

-actually performing a move based on the current cursor location.

+\b \cw{interpret_move()} responds to some other button \dash either

+\cw{CURSOR_SELECT} or some more specific thing like a number key \dash

+by actually performing a move based on the current cursor location.

 \b You might want an additional \c{game_ui} field stating whether

 the cursor is currently visible, and having it disappear when a

@@ -4987,21 +5699,21 @@

 \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 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}.

+\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}.

+\q{next} to \cw{false}.

-\b That way, \q{current} will be \cw{TRUE} \e{after} a call to

+\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}.

+\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.

@@ -5017,7 +5729,7 @@

 \b Add a \q{cheated} flag to the \c{game_state}.

-\b Set this flag to \cw{FALSE} in \cw{new_game()}.

+\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.