3 \cfg{text-title-align}{left}
4 \cfg{text-chapter-align}{left}
5 \cfg{text-chapter-numeric}{true}
6 \cfg{text-chapter-suffix}{. }
7 \cfg{text-chapter-underline}{-}
8 \cfg{text-section-align}{0}{left}
9 \cfg{text-section-numeric}{0}{true}
10 \cfg{text-section-suffix}{0}{. }
11 \cfg{text-section-underline}{0}{-}
12 \cfg{text-section-align}{1}{left}
13 \cfg{text-section-numeric}{1}{true}
14 \cfg{text-section-suffix}{1}{. }
15 \cfg{text-section-underline}{1}{-}
16 \cfg{text-versionid}{0}
18 \cfg{html-contents-filename}{index.html}
19 \cfg{html-template-filename}{%k.html}
20 \cfg{html-index-filename}{docindex.html}
21 \cfg{html-leaf-level}{1}
22 \cfg{html-contents-depth-0}{1}
23 \cfg{html-contents-depth-1}{3}
24 \cfg{html-leaf-contains-contents}{true}
26 \define{dash} \u2013{-}
28 \title Developer documentation for Simon Tatham's puzzle collection
30 This is a guide to the internal structure of Simon Tatham's Portable
31 Puzzle Collection (henceforth referred to simply as \q{Puzzles}),
32 for use by anyone attempting to implement a new puzzle or port to a
35 This guide is believed correct as of r6190. Hopefully it will be
36 updated along with the code in future, but if not, I've at least
37 left this version number in here so you can figure out what's
38 changed by tracking commit comments from there onwards.
40 \C{intro} Introduction
42 The Puzzles code base is divided into four parts: a set of
43 interchangeable front ends, a set of interchangeable back ends, a
44 universal \q{middle end} which acts as a buffer between the two, and
45 a bunch of miscellaneous utility functions. In the following
46 sections I give some general discussion of each of these parts.
48 \H{intro-frontend} Front end
50 The front end is the non-portable part of the code: it's the bit
51 that you replace completely when you port to a different platform.
52 So it's responsible for all system calls, all GUI interaction, and
53 anything else platform-specific.
55 The current front ends in the main code base are for Windows, GTK
56 and MacOS X; I also know of a third-party front end for PalmOS.
58 The front end contains \cw{main()} or the local platform's
59 equivalent. Top-level control over the application's execution flow
60 belongs to the front end (it isn't, for example, a set of functions
61 called by a universal \cw{main()} somewhere else).
63 The front end has complete freedom to design the GUI for any given
64 port of Puzzles. There is no centralised mechanism for maintaining
65 the menu layout, for example. This has a cost in consistency (when I
66 \e{do} want the same menu layout on more than one platform, I have
67 to edit two pieces of code in parallel every time I make a change),
68 but the advantage is that local GUI conventions can be conformed to
69 and local constraints adapted to. For example, MacOS X has strict
70 human interface guidelines which specify a different menu layout
71 from the one I've used on Windows and GTK; there's nothing stopping
72 the OS X front end from providing a menu layout consistent with
75 Although the front end is mostly caller rather than the callee in
76 its interactions with other parts of the code, it is required to
77 implement a small API for other modules to call, mostly of drawing
78 functions for games to use when drawing their graphics. The drawing
79 API is documented in \k{drawing}; the other miscellaneous front end
80 API functions are documented in \k{frontend-api}.
82 \H{intro-backend} Back end
84 A \q{back end}, in this collection, is synonymous with a \q{puzzle}.
85 Each back end implements a different game.
87 At the top level, a back end is simply a data structure, containing
88 a few constants (flag words, preferred pixel size) and a large
89 number of function pointers. Back ends are almost invariably callee
90 rather than caller, which means there's a limitation on what a back
91 end can do on its own initiative.
93 The persistent state in a back end is divided into a number of data
94 structures, which are used for different purposes and therefore
95 likely to be switched around, changed without notice, and otherwise
96 updated by the rest of the code. It is important when designing a
97 back end to put the right pieces of data into the right structures,
98 or standard midend-provided features (such as Undo) may fail to
101 The functions and variables provided in the back end data structure
102 are documented in \k{backend}.
104 \H{intro-midend} Middle end
106 Puzzles has a single and universal \q{middle end}. This code is
107 common to all platforms and all games; it sits in between the front
108 end and the back end and provides standard functionality everywhere.
110 People adding new back ends or new front ends should generally not
111 need to edit the middle end. On rare occasions there might be a
112 change that can be made to the middle end to permit a new game to do
113 something not currently anticipated by the middle end's present
114 design; however, this is terribly easy to get wrong and should
115 probably not be undertaken without consulting the primary maintainer
116 (me). Patch submissions containing unannounced mid-end changes will
117 be treated on their merits like any other patch; this is just a
118 friendly warning that mid-end changes will need quite a lot of
119 merits to make them acceptable.
121 Functionality provided by the mid-end includes:
123 \b Maintaining a list of game state structures and moving back and
124 forth along that list to provide Undo and Redo.
126 \b Handling timers (for move animations, flashes on completion, and
127 in some cases actually timing the game).
129 \b Handling the container format of game IDs: receiving them,
130 picking them apart into parameters, description and/or random seed,
131 and so on. The game back end need only handle the individual parts
132 of a game ID (encoded parameters and encoded game description);
133 everything else is handled centrally by the mid-end.
135 \b Handling standard keystrokes and menu commands, such as \q{New
136 Game}, \q{Restart Game} and \q{Quit}.
138 \b Pre-processing mouse events so that the game back ends can rely
139 on them arriving in a sensible order (no missing button-release
140 events, no sudden changes of which button is currently pressed,
143 \b Handling the dialog boxes which ask the user for a game ID.
145 \b Handling serialisation of entire games (for loading and saving a
146 half-finished game to a disk file, or for handling application
147 shutdown and restart on platforms such as PalmOS where state is
148 expected to be saved).
150 Thus, there's a lot of work done once by the mid-end so that
151 individual back ends don't have to worry about it. All the back end
152 has to do is cooperate in ensuring the mid-end can do its work
155 The API of functions provided by the mid-end to be called by the
156 front end is documented in \k{midend}.
158 \H{intro-utils} Miscellaneous utilities
160 In addition to these three major structural components, the Puzzles
161 code also contains a variety of utility modules usable by all of the
162 above components. There is a set of functions to provide
163 platform-independent random number generation; functions to make
164 memory allocation easier; functions which implement a balanced tree
165 structure to be used as necessary in complex algorithms; and a few
166 other miscellaneous functions. All of these are documented in
169 \H{intro-structure} Structure of this guide
171 There are a number of function call interfaces within Puzzles, and
172 this guide will discuss each one in a chapter of its own. After
173 that, \k{writing} discusses how to design new games, with some
174 general design thoughts and tips.
176 \C{backend} Interface to the back end
178 This chapter gives a detailed discussion of the interface that each
179 back end must implement.
181 At the top level, each back end source file exports a single global
182 symbol, which is a \c{const struct game} containing a large number
183 of function pointers and a small amount of constant data. This
184 structure is called by different names depending on what kind of
185 platform the puzzle set is being compiled on:
187 \b On platforms such as Windows and GTK, which build a separate
188 binary for each puzzle, the game structure in every back end has the
189 same name, \cq{thegame}; the front end refers directly to this name,
190 so that compiling the same front end module against a different back
191 end module builds a different puzzle.
193 \b On platforms such as MacOS X and PalmOS, which build all the
194 puzzles into a single monolithic binary, the game structure in each
195 back end must have a different name, and there's a helper module
196 \c{list.c} (constructed automatically by the same Perl script that
197 builds the \cw{Makefile}s) which contains a complete list of those
200 On the latter type of platform, source files may assume that the
201 preprocessor symbol \c{COMBINED} has been defined. Thus, the usual
202 code to declare the game structure looks something like this:
205 \c #define thegame net /* or whatever this game is called */
206 \e iii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
209 \c const struct game thegame = {
210 \c /* lots of structure initialisation in here */
211 \e iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
214 Game back ends must also internally define a number of data
215 structures, for storing their various persistent state. This chapter
216 will first discuss the nature and use of those structures, and then
217 go on to give details of every element of the game structure.
219 \H{backend-structs} Data structures
221 Each game is required to define four separate data structures. This
222 section discusses each one and suggests what sorts of things need to
225 \S{backend-game-params} \c{game_params}
227 The \c{game_params} structure contains anything which affects the
228 automatic generation of new puzzles. So if puzzle generation is
229 parametrised in any way, those parameters need to be stored in
232 Most puzzles currently in this collection are played on a grid of
233 squares, meaning that the most obvious parameter is the grid size.
234 Many puzzles have additional parameters; for example, Mines allows
235 you to control the number of mines in the grid independently of its
236 size, Net can be wrapping or non-wrapping, Solo has difficulty
237 levels and symmetry settings, and so on.
239 A simple rule for deciding whether a data item needs to go in
240 \c{game_params} is: would the user expect to be able to control this
241 data item from either the preset-game-types menu or the \q{Custom}
242 game type configuration? If so, it's part of \c{game_params}.
244 \c{game_params} structures are permitted to contain pointers to
245 subsidiary data if they need to. The back end is required to provide
246 functions to create and destroy \c{game_params}, and those functions
247 can allocate and free additional memory if necessary. (It has not
248 yet been necessary to do this in any puzzle so far, but the
249 capability is there just in case.)
251 \c{game_params} is also the only structure which the game's
252 \cw{compute_size()} function may refer to; this means that any
253 aspect of the game which affects the size of the window it needs to
254 be drawn in must be stored in \c{game_params}. In particular, this
255 imposes the fundamental limitation that random game generation may
256 not have a random effect on the window size: game generation
257 algorithms are constrained to work by starting from the grid size
258 rather than generating it as an emergent phenomenon. (Although this
259 is a restriction in theory, it has not yet seemed to be a problem.)
261 \S{backend-game-state} \c{game_state}
263 While the user is actually playing a puzzle, the \c{game_state}
264 structure stores all the data corresponding to the current state of
267 The mid-end keeps \c{game_state}s in a list, and adds to the list
268 every time the player makes a move; the Undo and Redo functions step
269 back and forth through that list.
271 Therefore, a good means of deciding whether a data item needs to go
272 in \c{game_state} is: would a player expect that data item to be
273 restored on undo? If so, put it in \c{game_state}, and this will
274 automatically happen without you having to lift a finger. If not
275 \dash for example, the deaths counter in Mines is precisely
276 something that does \e{not} want to be reset to its previous state
277 on an undo \dash then you might have found a data item that needs to
278 go in \c{game_ui} instead.
280 During play, \c{game_state}s are often passed around without an
281 accompanying \c{game_params} structure. Therefore, any information
282 in \c{game_params} which is important during play (such as the grid
283 size) must be duplicated within the \c{game_state}. One simple
284 method of doing this is to have the \c{game_state} structure
285 \e{contain} a \c{game_params} structure as one of its members,
286 although this isn't obligatory if you prefer to do it another way.
288 \S{backend-game-drawstate} \c{game_drawstate}
290 \c{game_drawstate} carries persistent state relating to the current
291 graphical contents of the puzzle window. The same \c{game_drawstate}
292 is passed to every call to the game redraw function, so that it can
293 remember what it has already drawn and what needs redrawing.
295 A typical use for a \c{game_drawstate} is to have an array mirroring
296 the array of grid squares in the \c{game_state}; then every time the
297 redraw function was passed a \c{game_state}, it would loop over all
298 the squares, and physically redraw any whose description in the
299 \c{game_state} (i.e. what the square needs to look like when the
300 redraw is completed) did not match its description in the
301 \c{game_drawstate} (i.e. what the square currently looks like).
303 \c{game_drawstate} is occasionally completely torn down and
304 reconstructed by the mid-end, if the user somehow forces a full
305 redraw. Therefore, no data should be stored in \c{game_drawstate}
306 which is \e{not} related to the state of the puzzle window, because
307 it might be unexpectedly destroyed.
309 The back end provides functions to create and destroy
310 \c{game_drawstate}, which means it can contain pointers to
311 subsidiary allocated data if it needs to. A common thing to want to
312 allocate in a \c{game_drawstate} is a \c{blitter}; see
313 \k{drawing-blitter} for more on this subject.
315 \S{backend-game-ui} \c{game_ui}
317 \c{game_ui} contains whatever doesn't fit into the above three
320 A new \c{game_ui} is created when the user begins playing a new
321 instance of a puzzle (i.e. during \q{New Game} or after entering a
322 game ID etc). It persists until the user finishes playing that game
323 and begins another one (or closes the window); in particular,
324 \q{Restart Game} does \e{not} destroy the \c{game_ui}.
326 \c{game_ui} is useful for implementing user-interface state which is
327 not part of \c{game_state}. Common examples are keyboard control
328 (you wouldn't want to have to separately Undo through every cursor
329 motion) and mouse dragging. See \k{writing-keyboard-cursor} and
330 \k{writing-howto-dragging}, respectively, for more details.
332 Another use for \c{game_ui} is to store highly persistent data such
333 as the Mines death counter. This is conceptually rather different:
334 where the Net cursor position was \e{not important enough} to
335 preserve for the player to restore by Undo, the Mines death counter
336 is \e{too important} to permit the player to revert by Undo!
338 A final use for \c{game_ui} is to pass information to the redraw
339 function about recent changes to the game state. This is used in
340 Mines, for example, to indicate whether a requested \q{flash} should
341 be a white flash for victory or a red flash for defeat; see
342 \k{writing-flash-types}.
344 \H{backend-simple} Simple data in the back end
346 In this section I begin to discuss each individual element in the
347 back end structure. To begin with, here are some simple
348 self-contained data elements.
350 \S{backend-name} \c{name}
354 This is a simple ASCII string giving the name of the puzzle. This
355 name will be used in window titles, in game selection menus on
356 monolithic platforms, and anywhere else that the front end needs to
357 know the name of a game.
359 \S{backend-winhelp} \c{winhelp_topic}
361 \c const char *winhelp_topic;
363 This member is used on Windows only, to provide online help.
364 Although the Windows front end provides a separate binary for each
365 puzzle, it has a single monolithic help file; so when a user selects
366 \q{Help} from the menu, the program needs to open the help file and
367 jump to the chapter describing that particular puzzle.
369 Therefore, each chapter in \c{puzzles.but} is labelled with a
370 \e{help topic} name, similar to this:
372 \c \cfg{winhelp-topic}{games.net}
374 And then the corresponding game back end encodes the topic string
375 (here \cq{games.net}) in the \c{winhelp_topic} element of the game
378 \H{backend-params} Handling game parameter sets
380 In this section I present the various functions which handle the
381 \c{game_params} structure.
383 \S{backend-default-params} \cw{default_params()}
385 \c game_params *(*default_params)(void);
387 This function allocates a new \c{game_params} structure, fills it
388 with the default values, and returns a pointer to it.
390 \S{backend-fetch-preset} \cw{fetch_preset()}
392 \c int (*fetch_preset)(int i, char **name, game_params **params);
394 This function is one of the two APIs a back end can provide to
395 populate the \q{Type} menu, which provides a list of conveniently
396 accessible preset parameters for most games.
398 The function is called with \c{i} equal to the index of the preset
399 required (numbering from zero). It returns \cw{FALSE} if that preset
400 does not exist (if \c{i} is less than zero or greater than the
401 largest preset index). Otherwise, it sets \c{*params} to point at a
402 newly allocated \c{game_params} structure containing the preset
403 information, sets \c{*name} to point at a newly allocated C string
404 containing the preset title (to go on the \q{Type} menu), and
407 If the game does not wish to support any presets at all, this
408 function is permitted to return \cw{FALSE} always.
410 If the game wants to return presets in the form of a hierarchical menu
411 instead of a flat list (and, indeed, even if it doesn't), then it may
412 set this function pointer to \cw{NULL}, and instead fill in the
413 alternative function pointer \cw{preset_menu}
414 (\k{backend-preset-menu}).
416 \S{backend-preset-menu} \cw{preset_menu()}
418 \c struct preset_menu *(*preset_menu)(void);
420 This function is the more flexible of the two APIs by which a back end
421 can define a collection of preset game parameters.
423 This function simply returns a complete menu hierarchy, in the form of
424 a \c{struct preset_menu} (see \k{midend-get-presets}) and further
425 submenus (if it wishes) dangling off it. There are utility functions
426 described in \k{utils-presets} to make it easy for the back end to
429 If the game has no need to return a hierarchy of menus, it may instead
430 opt to implement the \cw{fetch_preset()} function (see
431 \k{backend-fetch-preset}).
433 The game need not fill in the \c{id} fields in the preset menu
434 structures. The mid-end will do that after it receives the structure
435 from the game, and before passing it on to the front end.
437 \S{backend-encode-params} \cw{encode_params()}
439 \c char *(*encode_params)(const game_params *params, int full);
441 The job of this function is to take a \c{game_params}, and encode it
442 in a string form for use in game IDs. The return value must be a
443 newly allocated C string, and \e{must} not contain a colon or a hash
444 (since those characters are used to mark the end of the parameter
445 section in a game ID).
447 Ideally, it should also not contain any other potentially
448 controversial punctuation; bear in mind when designing a string
449 parameter format that it will probably be used on both Windows and
450 Unix command lines under a variety of exciting shell quoting and
451 metacharacter rules. Sticking entirely to alphanumerics is the
452 safest thing; if you really need punctuation, you can probably get
453 away with commas, periods or underscores without causing anybody any
454 major inconvenience. If you venture far beyond that, you're likely
455 to irritate \e{somebody}.
457 (At the time of writing this, all existing games have purely
458 alphanumeric string parameter formats. Usually these involve a
459 letter denoting a parameter, followed optionally by a number giving
460 the value of that parameter, with a few mandatory parts at the
461 beginning such as numeric width and height separated by \cq{x}.)
463 If the \c{full} parameter is \cw{TRUE}, this function should encode
464 absolutely everything in the \c{game_params}, such that a subsequent
465 call to \cw{decode_params()} (\k{backend-decode-params}) will yield
466 an identical structure. If \c{full} is \cw{FALSE}, however, you
467 should leave out anything which is not necessary to describe a
468 \e{specific puzzle instance}, i.e. anything which only takes effect
469 when a new puzzle is \e{generated}. For example, the Solo
470 \c{game_params} includes a difficulty rating used when constructing
471 new puzzles; but a Solo game ID need not explicitly include the
472 difficulty, since to describe a puzzle once generated it's
473 sufficient to give the grid dimensions and the location and contents
474 of the clue squares. (Indeed, one might very easily type in a puzzle
475 out of a newspaper without \e{knowing} what its difficulty level is
476 in Solo's terminology.) Therefore, Solo's \cw{encode_params()} only
477 encodes the difficulty level if \c{full} is set.
479 \S{backend-decode-params} \cw{decode_params()}
481 \c void (*decode_params)(game_params *params, char const *string);
483 This function is the inverse of \cw{encode_params()}
484 (\k{backend-encode-params}). It parses the supplied string and fills
485 in the supplied \c{game_params} structure. Note that the structure
486 will \e{already} have been allocated: this function is not expected
487 to create a \e{new} \c{game_params}, but to modify an existing one.
489 This function can receive a string which only encodes a subset of
490 the parameters. The most obvious way in which this can happen is if
491 the string was constructed by \cw{encode_params()} with its \c{full}
492 parameter set to \cw{FALSE}; however, it could also happen if the
493 user typed in a parameter set manually and missed something out. Be
494 prepared to deal with a wide range of possibilities.
496 When dealing with a parameter which is not specified in the input
497 string, what to do requires a judgment call on the part of the
498 programmer. Sometimes it makes sense to adjust other parameters to
499 bring them into line with the new ones. In Mines, for example, you
500 would probably not want to keep the same mine count if the user
501 dropped the grid size and didn't specify one, since you might easily
502 end up with more mines than would actually fit in the grid! On the
503 other hand, sometimes it makes sense to leave the parameter alone: a
504 Solo player might reasonably expect to be able to configure size and
505 difficulty independently of one another.
507 This function currently has no direct means of returning an error if
508 the string cannot be parsed at all. However, the returned
509 \c{game_params} is almost always subsequently passed to
510 \cw{validate_params()} (\k{backend-validate-params}), so if you
511 really want to signal parse errors, you could always have a \c{char
512 *} in your parameters structure which stored an error message, and
513 have \cw{validate_params()} return it if it is non-\cw{NULL}.
515 \S{backend-free-params} \cw{free_params()}
517 \c void (*free_params)(game_params *params);
519 This function frees a \c{game_params} structure, and any subsidiary
520 allocations contained within it.
522 \S{backend-dup-params} \cw{dup_params()}
524 \c game_params *(*dup_params)(const game_params *params);
526 This function allocates a new \c{game_params} structure and
527 initialises it with an exact copy of the information in the one
528 provided as input. It returns a pointer to the new duplicate.
530 \S{backend-can-configure} \c{can_configure}
532 \c int can_configure;
534 This boolean data element is set to \cw{TRUE} if the back end
535 supports custom parameter configuration via a dialog box. If it is
536 \cw{TRUE}, then the functions \cw{configure()} and
537 \cw{custom_params()} are expected to work. See \k{backend-configure}
538 and \k{backend-custom-params} for more details.
540 \S{backend-configure} \cw{configure()}
542 \c config_item *(*configure)(const game_params *params);
544 This function is called when the user requests a dialog box for
545 custom parameter configuration. It returns a newly allocated array
546 of \cw{config_item} structures, describing the GUI elements required
547 in the dialog box. The array should have one more element than the
548 number of controls, since it is terminated with a \cw{C_END} marker
549 (see below). Each array element describes the control together with
550 its initial value; the front end will modify the value fields and
551 return the updated array to \cw{custom_params()} (see
552 \k{backend-custom-params}).
554 The \cw{config_item} structure contains the following elements:
558 \c union { /* type-specific fields */ } u;
559 \e iiiiiiiiiiiiiiiiiiiiiiiiii
561 \c{name} is an ASCII string giving the textual label for a GUI
562 control. It is \e{not} expected to be dynamically allocated.
564 \c{type} contains one of a small number of \c{enum} values defining
565 what type of control is being described. The usable member of the
566 union field \c{u} depends on \c{type}. The valid type values are:
570 \dd Describes a text input box. (This is also used for numeric
571 input. The back end does not bother informing the front end that the
572 box is numeric rather than textual; some front ends do have the
573 capacity to take this into account, but I decided it wasn't worth
574 the extra complexity in the interface.)
578 For controls of this type, \c{u.string} contains a single field
582 which stores a dynamically allocated string representing the contents
589 \dd Describes a simple checkbox.
593 For controls of this type, \c{u.boolean} contains a single field
597 which is either \cw{TRUE} or \cw{FALSE}.
603 \dd Describes a drop-down list presenting one of a small number of
608 For controls of this type, \c{u.choices} contains two fields:
610 \c const char *choicenames;
613 \c{choicenames} contains a list of strings describing the choices. The
614 very first character of \c{sval} is used as a delimiter when
615 processing the rest (so that the strings \cq{:zero:one:two},
616 \cq{!zero!one!two} and \cq{xzeroxonextwo} all define a three-element
617 list containing \cq{zero}, \cq{one} and \cq{two}).
619 \c{selected} contains the index of the currently selected element,
620 numbering from zero (so that in the above example, 0 would mean
621 \cq{zero} and 2 would mean \cq{two}).
623 Note that \c{u.choices.choicenames} is \e{not} dynamically allocated,
624 unlike \c{u.string.sval}.
630 \dd Marks the end of the array of \c{config_item}s. There is no
631 associated member of the union field \c{u} for this type.
633 The array returned from this function is expected to have filled in
634 the initial values of all the controls according to the input
635 \c{game_params} structure.
637 If the game's \c{can_configure} flag is set to \cw{FALSE}, this
638 function is never called and need not do anything at all.
640 \S{backend-custom-params} \cw{custom_params()}
642 \c game_params *(*custom_params)(const config_item *cfg);
644 This function is the counterpart to \cw{configure()}
645 (\k{backend-configure}). It receives as input an array of
646 \c{config_item}s which was originally created by \cw{configure()},
647 but in which the control values have since been changed in
648 accordance with user input. Its function is to read the new values
649 out of the controls and return a newly allocated \c{game_params}
650 structure representing the user's chosen parameter set.
652 (The front end will have modified the controls' \e{values}, but
653 there will still always be the same set of controls, in the same
654 order, as provided by \cw{configure()}. It is not necessary to check
655 the \c{name} and \c{type} fields, although you could use
656 \cw{assert()} if you were feeling energetic.)
658 This function is not expected to (and indeed \e{must not}) free the
659 input \c{config_item} array. (If the parameters fail to validate,
660 the dialog box will stay open.)
662 If the game's \c{can_configure} flag is set to \cw{FALSE}, this
663 function is never called and need not do anything at all.
665 \S{backend-validate-params} \cw{validate_params()}
667 \c const char *(*validate_params)(const game_params *params,
670 This function takes a \c{game_params} structure as input, and checks
671 that the parameters described in it fall within sensible limits. (At
672 the very least, grid dimensions should almost certainly be strictly
673 positive, for example.)
675 Return value is \cw{NULL} if no problems were found, or
676 alternatively a (non-dynamically-allocated) ASCII string describing
677 the error in human-readable form.
679 If the \c{full} parameter is set, full validation should be
680 performed: any set of parameters which would not permit generation
681 of a sensible puzzle should be faulted. If \c{full} is \e{not} set,
682 the implication is that these parameters are not going to be used
683 for \e{generating} a puzzle; so parameters which can't even sensibly
684 \e{describe} a valid puzzle should still be faulted, but parameters
685 which only affect puzzle generation should not be.
687 (The \c{full} option makes a difference when parameter combinations
688 are non-orthogonal. For example, Net has a boolean option
689 controlling whether it enforces a unique solution; it turns out that
690 it's impossible to generate a uniquely soluble puzzle with wrapping
691 walls and width 2, so \cw{validate_params()} will complain if you
692 ask for one. However, if the user had just been playing a unique
693 wrapping puzzle of a more sensible width, and then pastes in a game
694 ID acquired from somebody else which happens to describe a
695 \e{non}-unique wrapping width-2 puzzle, then \cw{validate_params()}
696 will be passed a \c{game_params} containing the width and wrapping
697 settings from the new game ID and the uniqueness setting from the
698 old one. This would be faulted, if it weren't for the fact that
699 \c{full} is not set during this call, so Net ignores the
700 inconsistency. The resulting \c{game_params} is never subsequently
701 used to generate a puzzle; this is a promise made by the mid-end
702 when it asks for a non-full validation.)
704 \H{backend-descs} Handling game descriptions
706 In this section I present the functions that deal with a textual
707 description of a puzzle, i.e. the part that comes after the colon in
708 a descriptive-format game ID.
710 \S{backend-new-desc} \cw{new_desc()}
712 \c char *(*new_desc)(const game_params *params, random_state *rs,
713 \c char **aux, int interactive);
715 This function is where all the really hard work gets done. This is
716 the function whose job is to randomly generate a new puzzle,
717 ensuring solubility and uniqueness as appropriate.
719 As input it is given a \c{game_params} structure and a random state
720 (see \k{utils-random} for the random number API). It must invent a
721 puzzle instance, encode it in string form, and return a dynamically
722 allocated C string containing that encoding.
724 Additionally, it may return a second dynamically allocated string in
725 \c{*aux}. (If it doesn't want to, then it can leave that parameter
726 completely alone; it isn't required to set it to \cw{NULL}, although
727 doing so is harmless.) That string, if present, will be passed to
728 \cw{solve()} (\k{backend-solve}) later on; so if the puzzle is
729 generated in such a way that a solution is known, then information
730 about that solution can be saved in \c{*aux} for \cw{solve()} to
733 The \c{interactive} parameter should be ignored by almost all
734 puzzles. Its purpose is to distinguish between generating a puzzle
735 within a GUI context for immediate play, and generating a puzzle in
736 a command-line context for saving to be played later. The only
737 puzzle that currently uses this distinction (and, I fervently hope,
738 the only one which will \e{ever} need to use it) is Mines, which
739 chooses a random first-click location when generating puzzles
740 non-interactively, but which waits for the user to place the first
741 click when interactive. If you think you have come up with another
742 puzzle which needs to make use of this parameter, please think for
743 at least ten minutes about whether there is \e{any} alternative!
745 Note that game description strings are not required to contain an
746 encoding of parameters such as grid size; a game description is
747 never separated from the \c{game_params} it was generated with, so
748 any information contained in that structure need not be encoded
749 again in the game description.
751 \S{backend-validate-desc} \cw{validate_desc()}
753 \c const char *(*validate_desc)(const game_params *params,
754 \c const char *desc);
756 This function is given a game description, and its job is to
757 validate that it describes a puzzle which makes sense.
759 To some extent it's up to the user exactly how far they take the
760 phrase \q{makes sense}; there are no particularly strict rules about
761 how hard the user is permitted to shoot themself in the foot when
762 typing in a bogus game description by hand. (For example, Rectangles
763 will not verify that the sum of all the numbers in the grid equals
764 the grid's area. So a user could enter a puzzle which was provably
765 not soluble, and the program wouldn't complain; there just wouldn't
766 happen to be any sequence of moves which solved it.)
768 The one non-negotiable criterion is that any game description which
769 makes it through \cw{validate_desc()} \e{must not} subsequently
770 cause a crash or an assertion failure when fed to \cw{new_game()}
771 and thence to the rest of the back end.
773 The return value is \cw{NULL} on success, or a
774 non-dynamically-allocated C string containing an error message.
776 \S{backend-new-game} \cw{new_game()}
778 \c game_state *(*new_game)(midend *me, const game_params *params,
779 \c const char *desc);
781 This function takes a game description as input, together with its
782 accompanying \c{game_params}, and constructs a \c{game_state}
783 describing the initial state of the puzzle. It returns a newly
784 allocated \c{game_state} structure.
786 Almost all puzzles should ignore the \c{me} parameter. It is
787 required by Mines, which needs it for later passing to
788 \cw{midend_supersede_game_desc()} (see \k{backend-supersede}) once
789 the user has placed the first click. I fervently hope that no other
790 puzzle will be awkward enough to require it, so everybody else
791 should ignore it. As with the \c{interactive} parameter in
792 \cw{new_desc()} (\k{backend-new-desc}), if you think you have a
793 reason to need this parameter, please try very hard to think of an
794 alternative approach!
796 \H{backend-states} Handling game states
798 This section describes the functions which create and destroy
799 \c{game_state} structures.
801 (Well, except \cw{new_game()}, which is in \k{backend-new-game}
802 instead of under here; but it deals with game descriptions \e{and}
803 game states and it had to go in one section or the other.)
805 \S{backend-dup-game} \cw{dup_game()}
807 \c game_state *(*dup_game)(const game_state *state);
809 This function allocates a new \c{game_state} structure and
810 initialises it with an exact copy of the information in the one
811 provided as input. It returns a pointer to the new duplicate.
813 \S{backend-free-game} \cw{free_game()}
815 \c void (*free_game)(game_state *state);
817 This function frees a \c{game_state} structure, and any subsidiary
818 allocations contained within it.
820 \H{backend-ui} Handling \c{game_ui}
822 \S{backend-new-ui} \cw{new_ui()}
824 \c game_ui *(*new_ui)(const game_state *state);
826 This function allocates and returns a new \c{game_ui} structure for
827 playing a particular puzzle. It is passed a pointer to the initial
828 \c{game_state}, in case it needs to refer to that when setting up
829 the initial values for the new game.
831 \S{backend-free-ui} \cw{free_ui()}
833 \c void (*free_ui)(game_ui *ui);
835 This function frees a \c{game_ui} structure, and any subsidiary
836 allocations contained within it.
838 \S{backend-encode-ui} \cw{encode_ui()}
840 \c char *(*encode_ui)(const game_ui *ui);
842 This function encodes any \e{important} data in a \c{game_ui}
843 structure in string form. It is only called when saving a
844 half-finished game to a file.
846 It should be used sparingly. Almost all data in a \c{game_ui} is not
847 important enough to save. The location of the keyboard-controlled
848 cursor, for example, can be reset to a default position on reloading
849 the game without impacting the user experience. If the user should
850 somehow manage to save a game while a mouse drag was in progress,
851 then discarding that mouse drag would be an outright \e{feature}.
853 A typical thing that \e{would} be worth encoding in this function is
854 the Mines death counter: it's in the \c{game_ui} rather than the
855 \c{game_state} because it's too important to allow the user to
856 revert it by using Undo, and therefore it's also too important to
857 allow the user to revert it by saving and reloading. (Of course, the
858 user could edit the save file by hand... But if the user is \e{that}
859 determined to cheat, they could just as easily modify the game's
862 \S{backend-decode-ui} \cw{decode_ui()}
864 \c void (*decode_ui)(game_ui *ui, const char *encoding);
866 This function parses a string previously output by \cw{encode_ui()},
867 and writes the decoded data back into the provided \c{game_ui}
870 \S{backend-changed-state} \cw{changed_state()}
872 \c void (*changed_state)(game_ui *ui, const game_state *oldstate,
873 \c const game_state *newstate);
875 This function is called by the mid-end whenever the current game
876 state changes, for any reason. Those reasons include:
878 \b a fresh move being made by \cw{interpret_move()} and
881 \b a solve operation being performed by \cw{solve()} and
884 \b the user moving back and forth along the undo list by means of
885 the Undo and Redo operations
887 \b the user selecting Restart to go back to the initial game state.
889 The job of \cw{changed_state()} is to update the \c{game_ui} for
890 consistency with the new game state, if any update is necessary. For
891 example, Same Game stores data about the currently selected tile
892 group in its \c{game_ui}, and this data is intrinsically related to
893 the game state it was derived from. So it's very likely to become
894 invalid when the game state changes; thus, Same Game's
895 \cw{changed_state()} function clears the current selection whenever
898 When \cw{anim_length()} or \cw{flash_length()} are called, you can
899 be sure that there has been a previous call to \cw{changed_state()}.
900 So \cw{changed_state()} can set up data in the \c{game_ui} which will
901 be read by \cw{anim_length()} and \cw{flash_length()}, and those
902 functions will not have to worry about being called without the data
903 having been initialised.
905 \H{backend-moves} Making moves
907 This section describes the functions which actually make moves in
908 the game: that is, the functions which process user input and end up
909 producing new \c{game_state}s.
911 \S{backend-interpret-move} \cw{interpret_move()}
913 \c char *(*interpret_move)(const game_state *state, game_ui *ui,
914 \c const game_drawstate *ds,
915 \c int x, int y, int button);
917 This function receives user input and processes it. Its input
918 parameters are the current \c{game_state}, the current \c{game_ui}
919 and the current \c{game_drawstate}, plus details of the input event.
920 \c{button} is either an ASCII value or a special code (listed below)
921 indicating an arrow or function key or a mouse event; when
922 \c{button} is a mouse event, \c{x} and \c{y} contain the pixel
923 coordinates of the mouse pointer relative to the top left of the
924 puzzle's drawing area.
926 (The pointer to the \c{game_drawstate} is marked \c{const}, because
927 \c{interpret_move} should not write to it. The normal use of that
928 pointer will be to read the game's tile size parameter in order to
929 divide mouse coordinates by it.)
931 \cw{interpret_move()} may return in three different ways:
933 \b Returning \cw{NULL} indicates that no action whatsoever occurred
934 in response to the input event; the puzzle was not interested in it
937 \b Returning the special value \cw{UI_UPDATE} indicates that the input
938 event has resulted in a change being made to the \c{game_ui} which
939 will require a redraw of the game window, but that no actual \e{move}
940 was made (i.e. no new \c{game_state} needs to be created).
942 \b Returning anything else indicates that a move was made and that a
943 new \c{game_state} must be created. However, instead of actually
944 constructing a new \c{game_state} itself, this function is required
945 to return a string description of the details of the move. This
946 string will be passed to \cw{execute_move()}
947 (\k{backend-execute-move}) to actually create the new
948 \c{game_state}. (Encoding moves as strings in this way means that
949 the mid-end can keep the strings as well as the game states, and the
950 strings can be written to disk when saving the game and fed to
951 \cw{execute_move()} again on reloading.)
953 The return value from \cw{interpret_move()} is expected to be
954 dynamically allocated if and only if it is not either \cw{NULL}
955 \e{or} the special string constant \c{UI_UPDATE}.
957 After this function is called, the back end is permitted to rely on
958 some subsequent operations happening in sequence:
960 \b \cw{execute_move()} will be called to convert this move
961 description into a new \c{game_state}
963 \b \cw{changed_state()} will be called with the new \c{game_state}.
965 This means that if \cw{interpret_move()} needs to do updates to the
966 \c{game_ui} which are easier to perform by referring to the new
967 \c{game_state}, it can safely leave them to be done in
968 \cw{changed_state()} and not worry about them failing to happen.
970 (Note, however, that \cw{execute_move()} may \e{also} be called in
971 other circumstances. It is only \cw{interpret_move()} which can rely
972 on a subsequent call to \cw{changed_state()}.)
974 The special key codes supported by this function are:
976 \dt \cw{LEFT_BUTTON}, \cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}
978 \dd Indicate that one of the mouse buttons was pressed down.
980 \dt \cw{LEFT_DRAG}, \cw{MIDDLE_DRAG}, \cw{RIGHT_DRAG}
982 \dd Indicate that the mouse was moved while one of the mouse buttons
983 was still down. The mid-end guarantees that when one of these events
984 is received, it will always have been preceded by a button-down
985 event (and possibly other drag events) for the same mouse button,
986 and no event involving another mouse button will have appeared in
989 \dt \cw{LEFT_RELEASE}, \cw{MIDDLE_RELEASE}, \cw{RIGHT_RELEASE}
991 \dd Indicate that a mouse button was released. The mid-end
992 guarantees that when one of these events is received, it will always
993 have been preceded by a button-down event (and possibly some drag
994 events) for the same mouse button, and no event involving another
995 mouse button will have appeared in between.
997 \dt \cw{CURSOR_UP}, \cw{CURSOR_DOWN}, \cw{CURSOR_LEFT},
1000 \dd Indicate that an arrow key was pressed.
1002 \dt \cw{CURSOR_SELECT}
1004 \dd On platforms which have a prominent \q{select} button alongside
1005 their cursor keys, indicates that that button was pressed.
1007 In addition, there are some modifiers which can be bitwise-ORed into
1008 the \c{button} parameter:
1010 \dt \cw{MOD_CTRL}, \cw{MOD_SHFT}
1012 \dd These indicate that the Control or Shift key was pressed
1013 alongside the key. They only apply to the cursor keys, not to mouse
1014 buttons or anything else.
1016 \dt \cw{MOD_NUM_KEYPAD}
1018 \dd This applies to some ASCII values, and indicates that the key
1019 code was input via the numeric keypad rather than the main keyboard.
1020 Some puzzles may wish to treat this differently (for example, a
1021 puzzle might want to use the numeric keypad as an eight-way
1022 directional pad), whereas others might not (a game involving numeric
1023 input probably just wants to treat the numeric keypad as numbers).
1027 \dd This mask is the bitwise OR of all the available modifiers; you
1028 can bitwise-AND with \cw{~MOD_MASK} to strip all the modifiers off
1031 \S{backend-execute-move} \cw{execute_move()}
1033 \c game_state *(*execute_move)(const game_state *state, char *move);
1035 This function takes an input \c{game_state} and a move string as
1036 output from \cw{interpret_move()}. It returns a newly allocated
1037 \c{game_state} which contains the result of applying the specified
1038 move to the input game state.
1040 This function may return \cw{NULL} if it cannot parse the move
1041 string (and this is definitely preferable to crashing or failing an
1042 assertion, since one way this can happen is if loading a corrupt
1043 save file). However, it must not return \cw{NULL} for any move
1044 string that really was output from \cw{interpret_move()}: this is
1045 punishable by assertion failure in the mid-end.
1047 \S{backend-can-solve} \c{can_solve}
1051 This boolean field is set to \cw{TRUE} if the game's \cw{solve()}
1052 function does something. If it's set to \cw{FALSE}, the game will
1053 not even offer the \q{Solve} menu option.
1055 \S{backend-solve} \cw{solve()}
1057 \c char *(*solve)(const game_state *orig, const game_state *curr,
1058 \c const char *aux, const char **error);
1060 This function is called when the user selects the \q{Solve} option
1063 It is passed two input game states: \c{orig} is the game state from
1064 the very start of the puzzle, and \c{curr} is the current one.
1065 (Different games find one or other or both of these convenient.) It
1066 is also passed the \c{aux} string saved by \cw{new_desc()}
1067 (\k{backend-new-desc}), in case that encodes important information
1068 needed to provide the solution.
1070 If this function is unable to produce a solution (perhaps, for
1071 example, the game has no in-built solver so it can only solve
1072 puzzles it invented internally and has an \c{aux} string for) then
1073 it may return \cw{NULL}. If it does this, it must also set
1074 \c{*error} to an error message to be presented to the user (such as
1075 \q{Solution not known for this puzzle}); that error message is not
1076 expected to be dynamically allocated.
1078 If this function \e{does} produce a solution, it returns a move string
1079 suitable for feeding to \cw{execute_move()}
1080 (\k{backend-execute-move}). Like a (non-empty) string returned from
1081 \cw{interpret_move()}, the returned string should be dynamically
1084 \H{backend-drawing} Drawing the game graphics
1086 This section discusses the back end functions that deal with
1089 \S{backend-new-drawstate} \cw{new_drawstate()}
1091 \c game_drawstate *(*new_drawstate)(drawing *dr,
1092 \c const game_state *state);
1094 This function allocates and returns a new \c{game_drawstate}
1095 structure for drawing a particular puzzle. It is passed a pointer to
1096 a \c{game_state}, in case it needs to refer to that when setting up
1099 This function may not rely on the puzzle having been newly started;
1100 a new draw state can be constructed at any time if the front end
1101 requests a forced redraw. For games like Pattern, in which initial
1102 game states are much simpler than general ones, this might be
1103 important to keep in mind.
1105 The parameter \c{dr} is a drawing object (see \k{drawing}) which the
1106 function might need to use to allocate blitters. (However, this
1107 isn't recommended; it's usually more sensible to wait to allocate a
1108 blitter until \cw{set_size()} is called, because that way you can
1109 tailor it to the scale at which the puzzle is being drawn.)
1111 \S{backend-free-drawstate} \cw{free_drawstate()}
1113 \c void (*free_drawstate)(drawing *dr, game_drawstate *ds);
1115 This function frees a \c{game_drawstate} structure, and any
1116 subsidiary allocations contained within it.
1118 The parameter \c{dr} is a drawing object (see \k{drawing}), which
1119 might be required if you are freeing a blitter.
1121 \S{backend-preferred-tilesize} \c{preferred_tilesize}
1123 \c int preferred_tilesize;
1125 Each game is required to define a single integer parameter which
1126 expresses, in some sense, the scale at which it is drawn. This is
1127 described in the APIs as \cq{tilesize}, since most puzzles are on a
1128 square (or possibly triangular or hexagonal) grid and hence a
1129 sensible interpretation of this parameter is to define it as the
1130 size of one grid tile in pixels; however, there's no actual
1131 requirement that the \q{tile size} be proportional to the game
1132 window size. Window size is required to increase monotonically with
1133 \q{tile size}, however.
1135 The data element \c{preferred_tilesize} indicates the tile size
1136 which should be used in the absence of a good reason to do otherwise
1137 (such as the screen being too small, or the user explicitly
1138 requesting a resize if that ever gets implemented).
1140 \S{backend-compute-size} \cw{compute_size()}
1142 \c void (*compute_size)(const game_params *params, int tilesize,
1145 This function is passed a \c{game_params} structure and a tile size.
1146 It returns, in \c{*x} and \c{*y}, the size in pixels of the drawing
1147 area that would be required to render a puzzle with those parameters
1150 \S{backend-set-size} \cw{set_size()}
1152 \c void (*set_size)(drawing *dr, game_drawstate *ds,
1153 \c const game_params *params, int tilesize);
1155 This function is responsible for setting up a \c{game_drawstate} to
1156 draw at a given tile size. Typically this will simply involve
1157 copying the supplied \c{tilesize} parameter into a \c{tilesize}
1158 field inside the draw state; for some more complex games it might
1159 also involve setting up other dimension fields, or possibly
1160 allocating a blitter (see \k{drawing-blitter}).
1162 The parameter \c{dr} is a drawing object (see \k{drawing}), which is
1163 required if a blitter needs to be allocated.
1165 Back ends may assume (and may enforce by assertion) that this
1166 function will be called at most once for any \c{game_drawstate}. If
1167 a puzzle needs to be redrawn at a different size, the mid-end will
1168 create a fresh drawstate.
1170 \S{backend-colours} \cw{colours()}
1172 \c float *(*colours)(frontend *fe, int *ncolours);
1174 This function is responsible for telling the front end what colours
1175 the puzzle will need to draw itself.
1177 It returns the number of colours required in \c{*ncolours}, and the
1178 return value from the function itself is a dynamically allocated
1179 array of three times that many \c{float}s, containing the red, green
1180 and blue components of each colour respectively as numbers in the
1183 The second parameter passed to this function is a front end handle.
1184 The only things it is permitted to do with this handle are to call
1185 the front-end function called \cw{frontend_default_colour()} (see
1186 \k{frontend-default-colour}) or the utility function called
1187 \cw{game_mkhighlight()} (see \k{utils-game-mkhighlight}). (The
1188 latter is a wrapper on the former, so front end implementors only
1189 need to provide \cw{frontend_default_colour()}.) This allows
1190 \cw{colours()} to take local configuration into account when
1191 deciding on its own colour allocations. Most games use the front
1192 end's default colour as their background, apart from a few which
1193 depend on drawing relief highlights so they adjust the background
1194 colour if it's too light for highlights to show up against it.
1196 Note that the colours returned from this function are for
1197 \e{drawing}, not for printing. Printing has an entirely different
1198 colour allocation policy.
1200 \S{backend-anim-length} \cw{anim_length()}
1202 \c float (*anim_length)(const game_state *oldstate,
1203 \c const game_state *newstate,
1204 \c int dir, game_ui *ui);
1206 This function is called when a move is made, undone or redone. It is
1207 given the old and the new \c{game_state}, and its job is to decide
1208 whether the transition between the two needs to be animated or can
1211 \c{oldstate} is the state that was current until this call;
1212 \c{newstate} is the state that will be current after it. \c{dir}
1213 specifies the chronological order of those states: if it is
1214 positive, then the transition is the result of a move or a redo (and
1215 so \c{newstate} is the later of the two moves), whereas if it is
1216 negative then the transition is the result of an undo (so that
1217 \c{newstate} is the \e{earlier} move).
1219 If this function decides the transition should be animated, it
1220 returns the desired length of the animation in seconds. If not, it
1223 State changes as a result of a Restart operation are never animated;
1224 the mid-end will handle them internally and never consult this
1225 function at all. State changes as a result of Solve operations are
1226 also not animated by default, although you can change this for a
1227 particular game by setting a flag in \c{flags} (\k{backend-flags}).
1229 The function is also passed a pointer to the local \c{game_ui}. It
1230 may refer to information in here to help with its decision (see
1231 \k{writing-conditional-anim} for an example of this), and/or it may
1232 \e{write} information about the nature of the animation which will
1233 be read later by \cw{redraw()}.
1235 When this function is called, it may rely on \cw{changed_state()}
1236 having been called previously, so if \cw{anim_length()} needs to
1237 refer to information in the \c{game_ui}, then \cw{changed_state()}
1238 is a reliable place to have set that information up.
1240 Move animations do not inhibit further input events. If the user
1241 continues playing before a move animation is complete, the animation
1242 will be abandoned and the display will jump straight to the final
1245 \S{backend-flash-length} \cw{flash_length()}
1247 \c float (*flash_length)(const game_state *oldstate,
1248 \c const game_state *newstate,
1249 \c int dir, game_ui *ui);
1251 This function is called when a move is completed. (\q{Completed}
1252 means that not only has the move been made, but any animation which
1253 accompanied it has finished.) It decides whether the transition from
1254 \c{oldstate} to \c{newstate} merits a \q{flash}.
1256 A flash is much like a move animation, but it is \e{not} interrupted
1257 by further user interface activity; it runs to completion in
1258 parallel with whatever else might be going on on the display. The
1259 only thing which will rush a flash to completion is another flash.
1261 The purpose of flashes is to indicate that the game has been
1262 completed. They were introduced as a separate concept from move
1263 animations because of Net: the habit of most Net players (and
1264 certainly me) is to rotate a tile into place and immediately lock
1265 it, then move on to another tile. When you make your last move, at
1266 the instant the final tile is rotated into place the screen starts
1267 to flash to indicate victory \dash but if you then press the lock
1268 button out of habit, then the move animation is cancelled, and the
1269 victory flash does not complete. (And if you \e{don't} press the
1270 lock button, the completed grid will look untidy because there will
1271 be one unlocked square.) Therefore, I introduced a specific concept
1272 of a \q{flash} which is separate from a move animation and can
1273 proceed in parallel with move animations and any other display
1274 activity, so that the victory flash in Net is not cancelled by that
1277 The input parameters to \cw{flash_length()} are exactly the same as
1278 the ones to \cw{anim_length()}.
1280 Just like \cw{anim_length()}, when this function is called, it may
1281 rely on \cw{changed_state()} having been called previously, so if it
1282 needs to refer to information in the \c{game_ui} then
1283 \cw{changed_state()} is a reliable place to have set that
1286 (Some games use flashes to indicate defeat as well as victory;
1287 Mines, for example, flashes in a different colour when you tread on
1288 a mine from the colour it uses when you complete the game. In order
1289 to achieve this, its \cw{flash_length()} function has to store a
1290 flag in the \c{game_ui} to indicate which flash type is required.)
1292 \S{backend-status} \cw{status()}
1294 \c int (*status)(const game_state *state);
1296 This function returns a status value indicating whether the current
1297 game is still in play, or has been won, or has been conclusively lost.
1298 The mid-end uses this to implement \cw{midend_status()}
1299 (\k{midend-status}).
1301 The return value should be +1 if the game has been successfully
1302 solved. If the game has been lost in a situation where further play is
1303 unlikely, the return value should be -1. If neither is true (so play
1304 is still ongoing), return zero.
1306 Front ends may wish to use a non-zero status as a cue to proactively
1307 offer the option of starting a new game. Therefore, back ends should
1308 not return -1 if the game has been \e{technically} lost but undoing
1309 and continuing is still a realistic possibility.
1311 (For instance, games with hidden information such as Guess or Mines
1312 might well return a non-zero status whenever they reveal the solution,
1313 whether or not the player guessed it correctly, on the grounds that a
1314 player would be unlikely to hide the solution and continue playing
1315 after the answer was spoiled. On the other hand, games where you can
1316 merely get into a dead end such as Same Game or Inertia might choose
1317 to return 0 in that situation, on the grounds that the player would
1318 quite likely press Undo and carry on playing.)
1320 \S{backend-redraw} \cw{redraw()}
1322 \c void (*redraw)(drawing *dr, game_drawstate *ds,
1323 \c const game_state *oldstate,
1324 \c const game_state *newstate,
1325 \c int dir, const game_ui *ui,
1326 \c float anim_time, float flash_time);
1328 This function is responsible for actually drawing the contents of
1329 the game window, and for redrawing every time the game state or the
1330 \c{game_ui} changes.
1332 The parameter \c{dr} is a drawing object which may be passed to the
1333 drawing API functions (see \k{drawing} for documentation of the
1334 drawing API). This function may not save \c{dr} and use it
1335 elsewhere; it must only use it for calling back to the drawing API
1336 functions within its own lifetime.
1338 \c{ds} is the local \c{game_drawstate}, of course, and \c{ui} is the
1341 \c{newstate} is the semantically-current game state, and is always
1342 non-\cw{NULL}. If \c{oldstate} is also non-\cw{NULL}, it means that
1343 a move has recently been made and the game is still in the process
1344 of displaying an animation linking the old and new states; in this
1345 situation, \c{anim_time} will give the length of time (in seconds)
1346 that the animation has already been running. If \c{oldstate} is
1347 \cw{NULL}, then \c{anim_time} is unused (and will hopefully be set
1348 to zero to avoid confusion).
1350 \c{flash_time}, if it is is non-zero, denotes that the game is in
1351 the middle of a flash, and gives the time since the start of the
1352 flash. See \k{backend-flash-length} for general discussion of
1355 The very first time this function is called for a new
1356 \c{game_drawstate}, it is expected to redraw the \e{entire} drawing
1357 area. Since this often involves drawing visual furniture which is
1358 never subsequently altered, it is often simplest to arrange this by
1359 having a special \q{first time} flag in the draw state, and
1360 resetting it after the first redraw.
1362 When this function (or any subfunction) calls the drawing API, it is
1363 expected to pass colour indices which were previously defined by the
1364 \cw{colours()} function.
1366 \H{backend-printing} Printing functions
1368 This section discusses the back end functions that deal with
1369 printing puzzles out on paper.
1371 \S{backend-can-print} \c{can_print}
1375 This flag is set to \cw{TRUE} if the puzzle is capable of printing
1376 itself on paper. (This makes sense for some puzzles, such as Solo,
1377 which can be filled in with a pencil. Other puzzles, such as
1378 Twiddle, inherently involve moving things around and so would not
1379 make sense to print.)
1381 If this flag is \cw{FALSE}, then the functions \cw{print_size()}
1382 and \cw{print()} will never be called.
1384 \S{backend-can-print-in-colour} \c{can_print_in_colour}
1386 \c int can_print_in_colour;
1388 This flag is set to \cw{TRUE} if the puzzle is capable of printing
1389 itself differently when colour is available. For example, Map can
1390 actually print coloured regions in different \e{colours} rather than
1391 resorting to cross-hatching.
1393 If the \c{can_print} flag is \cw{FALSE}, then this flag will be
1396 \S{backend-print-size} \cw{print_size()}
1398 \c void (*print_size)(const game_params *params, float *x, float *y);
1400 This function is passed a \c{game_params} structure and a tile size.
1401 It returns, in \c{*x} and \c{*y}, the preferred size in
1402 \e{millimetres} of that puzzle if it were to be printed out on paper.
1404 If the \c{can_print} flag is \cw{FALSE}, this function will never be
1407 \S{backend-print} \cw{print()}
1409 \c void (*print)(drawing *dr, const game_state *state, int tilesize);
1411 This function is called when a puzzle is to be printed out on paper.
1412 It should use the drawing API functions (see \k{drawing}) to print
1415 This function is separate from \cw{redraw()} because it is often
1418 \b The printing function may not depend on pixel accuracy, since
1419 printer resolution is variable. Draw as if your canvas had infinite
1422 \b The printing function sometimes needs to display things in a
1423 completely different style. Net, for example, is very different as
1424 an on-screen puzzle and as a printed one.
1426 \b The printing function is often much simpler since it has no need
1427 to deal with repeated partial redraws.
1429 However, there's no reason the printing and redraw functions can't
1430 share some code if they want to.
1432 When this function (or any subfunction) calls the drawing API, the
1433 colour indices it passes should be colours which have been allocated
1434 by the \cw{print_*_colour()} functions within this execution of
1435 \cw{print()}. This is very different from the fixed small number of
1436 colours used in \cw{redraw()}, because printers do not have a
1437 limitation on the total number of colours that may be used. Some
1438 puzzles' printing functions might wish to allocate only one \q{ink}
1439 colour and use it for all drawing; others might wish to allocate
1440 \e{more} colours than are used on screen.
1442 One possible colour policy worth mentioning specifically is that a
1443 puzzle's printing function might want to allocate the \e{same}
1444 colour indices as are used by the redraw function, so that code
1445 shared between drawing and printing does not have to keep switching
1446 its colour indices. In order to do this, the simplest thing is to
1447 make use of the fact that colour indices returned from
1448 \cw{print_*_colour()} are guaranteed to be in increasing order from
1449 zero. So if you have declared an \c{enum} defining three colours
1450 \cw{COL_BACKGROUND}, \cw{COL_THIS} and \cw{COL_THAT}, you might then
1454 \c c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1455 \c c = print_mono_colour(dr, 0); assert(c == COL_THIS);
1456 \c c = print_mono_colour(dr, 0); assert(c == COL_THAT);
1458 If the \c{can_print} flag is \cw{FALSE}, this function will never be
1461 \H{backend-misc} Miscellaneous
1463 \S{backend-can-format-as-text-ever} \c{can_format_as_text_ever}
1465 \c int can_format_as_text_ever;
1467 This boolean field is \cw{TRUE} if the game supports formatting a
1468 game state as ASCII text (typically ASCII art) for copying to the
1469 clipboard and pasting into other applications. If it is \cw{FALSE},
1470 front ends will not offer the \q{Copy} command at all.
1472 If this field is \cw{TRUE}, the game does not necessarily have to
1473 support text formatting for \e{all} games: e.g. a game which can be
1474 played on a square grid or a triangular one might only support copy
1475 and paste for the former, because triangular grids in ASCII art are
1478 If this field is \cw{FALSE}, the functions
1479 \cw{can_format_as_text_now()} (\k{backend-can-format-as-text-now})
1480 and \cw{text_format()} (\k{backend-text-format}) are never called.
1482 \S{backend-can-format-as-text-now} \c{can_format_as_text_now()}
1484 \c int (*can_format_as_text_now)(const game_params *params);
1486 This function is passed a \c{game_params} and returns a boolean,
1487 which is \cw{TRUE} if the game can support ASCII text output for
1488 this particular game type. If it returns \cw{FALSE}, front ends will
1489 grey out or otherwise disable the \q{Copy} command.
1491 Games may enable and disable the copy-and-paste function for
1492 different game \e{parameters}, but are currently constrained to
1493 return the same answer from this function for all game \e{states}
1494 sharing the same parameters. In other words, the \q{Copy} function
1495 may enable or disable itself when the player changes game preset,
1496 but will never change during play of a single game or when another
1497 game of exactly the same type is generated.
1499 This function should not take into account aspects of the game
1500 parameters which are not encoded by \cw{encode_params()}
1501 (\k{backend-encode-params}) when the \c{full} parameter is set to
1502 \cw{FALSE}. Such parameters will not necessarily match up between a
1503 call to this function and a subsequent call to \cw{text_format()}
1504 itself. (For instance, game \e{difficulty} should not affect whether
1505 the game can be copied to the clipboard. Only the actual visible
1506 \e{shape} of the game can affect that.)
1508 \S{backend-text-format} \cw{text_format()}
1510 \c char *(*text_format)(const game_state *state);
1512 This function is passed a \c{game_state}, and returns a newly
1513 allocated C string containing an ASCII representation of that game
1514 state. It is used to implement the \q{Copy} operation in many front
1517 This function will only ever be called if the back end field
1518 \c{can_format_as_text_ever} (\k{backend-can-format-as-text-ever}) is
1519 \cw{TRUE} \e{and} the function \cw{can_format_as_text_now()}
1520 (\k{backend-can-format-as-text-now}) has returned \cw{TRUE} for the
1521 currently selected game parameters.
1523 The returned string may contain line endings (and will probably want
1524 to), using the normal C internal \cq{\\n} convention. For
1525 consistency between puzzles, all multi-line textual puzzle
1526 representations should \e{end} with a newline as well as containing
1527 them internally. (There are currently no puzzles which have a
1528 one-line ASCII representation, so there's no precedent yet for
1529 whether that should come with a newline or not.)
1531 \S{backend-wants-statusbar} \cw{wants_statusbar}
1533 \c int wants_statusbar;
1535 This boolean field is set to \cw{TRUE} if the puzzle has a use for a
1536 textual status line (to display score, completion status, currently
1539 \S{backend-is-timed} \c{is_timed}
1543 This boolean field is \cw{TRUE} if the puzzle is time-critical. If
1544 so, the mid-end will maintain a game timer while the user plays.
1546 If this field is \cw{FALSE}, then \cw{timing_state()} will never be
1547 called and need not do anything.
1549 \S{backend-timing-state} \cw{timing_state()}
1551 \c int (*timing_state)(const game_state *state, game_ui *ui);
1553 This function is passed the current \c{game_state} and the local
1554 \c{game_ui}; it returns \cw{TRUE} if the game timer should currently
1557 A typical use for the \c{game_ui} in this function is to note when
1558 the game was first completed (by setting a flag in
1559 \cw{changed_state()} \dash see \k{backend-changed-state}), and
1560 freeze the timer thereafter so that the user can undo back through
1561 their solution process without altering their time.
1563 \S{backend-flags} \c{flags}
1567 This field contains miscellaneous per-backend flags. It consists of
1568 the bitwise OR of some combination of the following:
1570 \dt \cw{BUTTON_BEATS(x,y)}
1572 \dd Given any \cw{x} and \cw{y} from the set \{\cw{LEFT_BUTTON},
1573 \cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}\}, this macro evaluates to a
1574 bit flag which indicates that when buttons \cw{x} and \cw{y} are
1575 both pressed simultaneously, the mid-end should consider \cw{x} to
1576 have priority. (In the absence of any such flags, the mid-end will
1577 always consider the most recently pressed button to have priority.)
1579 \dt \cw{SOLVE_ANIMATES}
1581 \dd This flag indicates that moves generated by \cw{solve()}
1582 (\k{backend-solve}) are candidates for animation just like any other
1583 move. For most games, solve moves should not be animated, so the
1584 mid-end doesn't even bother calling \cw{anim_length()}
1585 (\k{backend-anim-length}), thus saving some special-case code in
1586 each game. On the rare occasion that animated solve moves are
1587 actually required, you can set this flag.
1589 \dt \cw{REQUIRE_RBUTTON}
1591 \dd This flag indicates that the puzzle cannot be usefully played
1592 without the use of mouse buttons other than the left one. On some
1593 PDA platforms, this flag is used by the front end to enable
1594 right-button emulation through an appropriate gesture. Note that a
1595 puzzle is not required to set this just because it \e{uses} the
1596 right button, but only if its use of the right button is critical to
1597 playing the game. (Slant, for example, uses the right button to
1598 cycle through the three square states in the opposite order from the
1599 left button, and hence can manage fine without it.)
1601 \dt \cw{REQUIRE_NUMPAD}
1603 \dd This flag indicates that the puzzle cannot be usefully played
1604 without the use of number-key input. On some PDA platforms it causes
1605 an emulated number pad to appear on the screen. Similarly to
1606 \cw{REQUIRE_RBUTTON}, a puzzle need not specify this simply if its
1607 use of the number keys is not critical.
1609 \H{backend-initiative} Things a back end may do on its own initiative
1611 This section describes a couple of things that a back end may choose
1612 to do by calling functions elsewhere in the program, which would not
1613 otherwise be obvious.
1615 \S{backend-newrs} Create a random state
1617 If a back end needs random numbers at some point during normal play,
1618 it can create a fresh \c{random_state} by first calling
1619 \c{get_random_seed} (\k{frontend-get-random-seed}) and then passing
1620 the returned seed data to \cw{random_new()}.
1622 This is likely not to be what you want. If a puzzle needs randomness
1623 in the middle of play, it's likely to be more sensible to store some
1624 sort of random state within the \c{game_state}, so that the random
1625 numbers are tied to the particular game state and hence the player
1626 can't simply keep undoing their move until they get numbers they
1629 This facility is currently used only in Net, to implement the
1630 \q{jumble} command, which sets every unlocked tile to a new random
1631 orientation. This randomness \e{is} a reasonable use of the feature,
1632 because it's non-adversarial \dash there's no advantage to the user
1633 in getting different random numbers.
1635 \S{backend-supersede} Supersede its own game description
1637 In response to a move, a back end is (reluctantly) permitted to call
1638 \cw{midend_supersede_game_desc()}:
1640 \c void midend_supersede_game_desc(midend *me,
1641 \c char *desc, char *privdesc);
1643 When the user selects \q{New Game}, the mid-end calls
1644 \cw{new_desc()} (\k{backend-new-desc}) to get a new game
1645 description, and (as well as using that to generate an initial game
1646 state) stores it for the save file and for telling to the user. The
1647 function above overwrites that game description, and also splits it
1648 in two. \c{desc} becomes the new game description which is provided
1649 to the user on request, and is also the one used to construct a new
1650 initial game state if the user selects \q{Restart}. \c{privdesc} is
1651 a \q{private} game description, used to reconstruct the game's
1652 initial state when reloading.
1654 The distinction between the two, as well as the need for this
1655 function at all, comes from Mines. Mines begins with a blank grid
1656 and no idea of where the mines actually are; \cw{new_desc()} does
1657 almost no work in interactive mode, and simply returns a string
1658 encoding the \c{random_state}. When the user first clicks to open a
1659 tile, \e{then} Mines generates the mine positions, in such a way
1660 that the game is soluble from that starting point. Then it uses this
1661 function to supersede the random-state game description with a
1662 proper one. But it needs two: one containing the initial click
1663 location (because that's what you want to happen if you restart the
1664 game, and also what you want to send to a friend so that they play
1665 \e{the same game} as you), and one without the initial click
1666 location (because when you save and reload the game, you expect to
1667 see the same blank initial state as you had before saving).
1669 I should stress again that this function is a horrid hack. Nobody
1670 should use it if they're not Mines; if you think you need to use it,
1671 think again repeatedly in the hope of finding a better way to do
1672 whatever it was you needed to do.
1674 \C{drawing} The drawing API
1676 The back end function \cw{redraw()} (\k{backend-redraw}) is required
1677 to draw the puzzle's graphics on the window's drawing area, or on
1678 paper if the puzzle is printable. To do this portably, it is
1679 provided with a drawing API allowing it to talk directly to the
1680 front end. In this chapter I document that API, both for the benefit
1681 of back end authors trying to use it and for front end authors
1682 trying to implement it.
1684 The drawing API as seen by the back end is a collection of global
1685 functions, each of which takes a pointer to a \c{drawing} structure
1686 (a \q{drawing object}). These objects are supplied as parameters to
1687 the back end's \cw{redraw()} and \cw{print()} functions.
1689 In fact these global functions are not implemented directly by the
1690 front end; instead, they are implemented centrally in \c{drawing.c}
1691 and form a small piece of middleware. The drawing API as supplied by
1692 the front end is a structure containing a set of function pointers,
1693 plus a \cq{void *} handle which is passed to each of those
1694 functions. This enables a single front end to switch between
1695 multiple implementations of the drawing API if necessary. For
1696 example, the Windows API supplies a printing mechanism integrated
1697 into the same GDI which deals with drawing in windows, and therefore
1698 the same API implementation can handle both drawing and printing;
1699 but on Unix, the most common way for applications to print is by
1700 producing PostScript output directly, and although it would be
1701 \e{possible} to write a single (say) \cw{draw_rect()} function which
1702 checked a global flag to decide whether to do GTK drawing operations
1703 or output PostScript to a file, it's much nicer to have two separate
1704 functions and switch between them as appropriate.
1706 When drawing, the puzzle window is indexed by pixel coordinates,
1707 with the top left pixel defined as \cw{(0,0)} and the bottom right
1708 pixel \cw{(w-1,h-1)}, where \c{w} and \c{h} are the width and height
1709 values returned by the back end function \cw{compute_size()}
1710 (\k{backend-compute-size}).
1712 When printing, the puzzle's print area is indexed in exactly the
1713 same way (with an arbitrary tile size provided by the printing
1714 module \c{printing.c}), to facilitate sharing of code between the
1715 drawing and printing routines. However, when printing, puzzles may
1716 no longer assume that the coordinate unit has any relationship to a
1717 pixel; the printer's actual resolution might very well not even be
1718 known at print time, so the coordinate unit might be smaller or
1719 larger than a pixel. Puzzles' print functions should restrict
1720 themselves to drawing geometric shapes rather than fiddly pixel
1723 \e{Puzzles' redraw functions may assume that the surface they draw
1724 on is persistent}. It is the responsibility of every front end to
1725 preserve the puzzle's window contents in the face of GUI window
1726 expose issues and similar. It is not permissible to request that the
1727 back end redraw any part of a window that it has already drawn,
1728 unless something has actually changed as a result of making moves in
1731 Most front ends accomplish this by having the drawing routines draw
1732 on a stored bitmap rather than directly on the window, and copying
1733 the bitmap to the window every time a part of the window needs to be
1734 redrawn. Therefore, it is vitally important that whenever the back
1735 end does any drawing it informs the front end of which parts of the
1736 window it has accessed, and hence which parts need repainting. This
1737 is done by calling \cw{draw_update()} (\k{drawing-draw-update}).
1739 Persistence of old drawing is convenient. However, a puzzle should
1740 be very careful about how it updates its drawing area. The problem
1741 is that some front ends do anti-aliased drawing: rather than simply
1742 choosing between leaving each pixel untouched or painting it a
1743 specified colour, an antialiased drawing function will \e{blend} the
1744 original and new colours in pixels at a figure's boundary according
1745 to the proportion of the pixel occupied by the figure (probably
1746 modified by some heuristic fudge factors). All of this produces a
1747 smoother appearance for curves and diagonal lines.
1749 An unfortunate effect of drawing an anti-aliased figure repeatedly
1750 is that the pixels around the figure's boundary come steadily more
1751 saturated with \q{ink} and the boundary appears to \q{spread out}.
1752 Worse, redrawing a figure in a different colour won't fully paint
1753 over the old boundary pixels, so the end result is a rather ugly
1756 A good strategy to avoid unpleasant anti-aliasing artifacts is to
1757 identify a number of rectangular areas which need to be redrawn,
1758 clear them to the background colour, and then redraw their contents
1759 from scratch, being careful all the while not to stray beyond the
1760 boundaries of the original rectangles. The \cw{clip()} function
1761 (\k{drawing-clip}) comes in very handy here. Games based on a square
1762 grid can often do this fairly easily. Other games may need to be
1763 somewhat more careful. For example, Loopy's redraw function first
1764 identifies portions of the display which need to be updated. Then,
1765 if the changes are fairly well localised, it clears and redraws a
1766 rectangle containing each changed area. Otherwise, it gives up and
1767 redraws the entire grid from scratch.
1769 It is possible to avoid clearing to background and redrawing from
1770 scratch if one is very careful about which drawing functions one
1771 uses: if a function is documented as not anti-aliasing under some
1772 circumstances, you can rely on each pixel in a drawing either being
1773 left entirely alone or being set to the requested colour, with no
1774 blending being performed.
1776 In the following sections I first discuss the drawing API as seen by
1777 the back end, and then the \e{almost} identical function-pointer
1778 form seen by the front end.
1780 \H{drawing-backend} Drawing API as seen by the back end
1782 This section documents the back-end drawing API, in the form of
1783 functions which take a \c{drawing} object as an argument.
1785 \S{drawing-draw-rect} \cw{draw_rect()}
1787 \c void draw_rect(drawing *dr, int x, int y, int w, int h,
1790 Draws a filled rectangle in the puzzle window.
1792 \c{x} and \c{y} give the coordinates of the top left pixel of the
1793 rectangle. \c{w} and \c{h} give its width and height. Thus, the
1794 horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1795 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1798 \c{colour} is an integer index into the colours array returned by
1799 the back end function \cw{colours()} (\k{backend-colours}).
1801 There is no separate pixel-plotting function. If you want to plot a
1802 single pixel, the approved method is to use \cw{draw_rect()} with
1803 width and height set to 1.
1805 Unlike many of the other drawing functions, this function is
1806 guaranteed to be pixel-perfect: the rectangle will be sharply
1807 defined and not anti-aliased or anything like that.
1809 This function may be used for both drawing and printing.
1811 \S{drawing-draw-rect-outline} \cw{draw_rect_outline()}
1813 \c void draw_rect_outline(drawing *dr, int x, int y, int w, int h,
1816 Draws an outline rectangle in the puzzle window.
1818 \c{x} and \c{y} give the coordinates of the top left pixel of the
1819 rectangle. \c{w} and \c{h} give its width and height. Thus, the
1820 horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1821 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1824 \c{colour} is an integer index into the colours array returned by
1825 the back end function \cw{colours()} (\k{backend-colours}).
1827 From a back end perspective, this function may be considered to be
1828 part of the drawing API. However, front ends are not required to
1829 implement it, since it is actually implemented centrally (in
1830 \cw{misc.c}) as a wrapper on \cw{draw_polygon()}.
1832 This function may be used for both drawing and printing.
1834 \S{drawing-draw-line} \cw{draw_line()}
1836 \c void draw_line(drawing *dr, int x1, int y1, int x2, int y2,
1839 Draws a straight line in the puzzle window.
1841 \c{x1} and \c{y1} give the coordinates of one end of the line.
1842 \c{x2} and \c{y2} give the coordinates of the other end. The line
1843 drawn includes both those points.
1845 \c{colour} is an integer index into the colours array returned by
1846 the back end function \cw{colours()} (\k{backend-colours}).
1848 Some platforms may perform anti-aliasing on this function.
1849 Therefore, do not assume that you can erase a line by drawing the
1850 same line over it in the background colour; anti-aliasing might lead
1851 to perceptible ghost artefacts around the vanished line. Horizontal
1852 and vertical lines, however, are pixel-perfect and not anti-aliased.
1854 This function may be used for both drawing and printing.
1856 \S{drawing-draw-polygon} \cw{draw_polygon()}
1858 \c void draw_polygon(drawing *dr, int *coords, int npoints,
1859 \c int fillcolour, int outlinecolour);
1861 Draws an outlined or filled polygon in the puzzle window.
1863 \c{coords} is an array of \cw{(2*npoints)} integers, containing the
1864 \c{x} and \c{y} coordinates of \c{npoints} vertices.
1866 \c{fillcolour} and \c{outlinecolour} are integer indices into the
1867 colours array returned by the back end function \cw{colours()}
1868 (\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
1869 indicate that the polygon should be outlined only.
1871 The polygon defined by the specified list of vertices is first
1872 filled in \c{fillcolour}, if specified, and then outlined in
1875 \c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
1876 (and front ends are permitted to enforce this by assertion). This is
1877 because different platforms disagree on whether a filled polygon
1878 should include its boundary line or not, so drawing \e{only} a
1879 filled polygon would have non-portable effects. If you want your
1880 filled polygon not to have a visible outline, you must set
1881 \c{outlinecolour} to the same as \c{fillcolour}.
1883 Some platforms may perform anti-aliasing on this function.
1884 Therefore, do not assume that you can erase a polygon by drawing the
1885 same polygon over it in the background colour. Also, be prepared for
1886 the polygon to extend a pixel beyond its obvious bounding box as a
1887 result of this; if you really need it not to do this to avoid
1888 interfering with other delicate graphics, you should probably use
1889 \cw{clip()} (\k{drawing-clip}). You can rely on horizontal and
1890 vertical lines not being anti-aliased.
1892 This function may be used for both drawing and printing.
1894 \S{drawing-draw-circle} \cw{draw_circle()}
1896 \c void draw_circle(drawing *dr, int cx, int cy, int radius,
1897 \c int fillcolour, int outlinecolour);
1899 Draws an outlined or filled circle in the puzzle window.
1901 \c{cx} and \c{cy} give the coordinates of the centre of the circle.
1902 \c{radius} gives its radius. The total horizontal pixel extent of
1903 the circle is from \c{cx-radius+1} to \c{cx+radius-1} inclusive, and
1904 the vertical extent similarly around \c{cy}.
1906 \c{fillcolour} and \c{outlinecolour} are integer indices into the
1907 colours array returned by the back end function \cw{colours()}
1908 (\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
1909 indicate that the circle should be outlined only.
1911 The circle is first filled in \c{fillcolour}, if specified, and then
1912 outlined in \c{outlinecolour}.
1914 \c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
1915 (and front ends are permitted to enforce this by assertion). This is
1916 because different platforms disagree on whether a filled circle
1917 should include its boundary line or not, so drawing \e{only} a
1918 filled circle would have non-portable effects. If you want your
1919 filled circle not to have a visible outline, you must set
1920 \c{outlinecolour} to the same as \c{fillcolour}.
1922 Some platforms may perform anti-aliasing on this function.
1923 Therefore, do not assume that you can erase a circle by drawing the
1924 same circle over it in the background colour. Also, be prepared for
1925 the circle to extend a pixel beyond its obvious bounding box as a
1926 result of this; if you really need it not to do this to avoid
1927 interfering with other delicate graphics, you should probably use
1928 \cw{clip()} (\k{drawing-clip}).
1930 This function may be used for both drawing and printing.
1932 \S{drawing-draw-thick-line} \cw{draw_thick_line()}
1934 \c void draw_thick_line(drawing *dr, float thickness,
1935 \c float x1, float y1, float x2, float y2,
1938 Draws a line in the puzzle window, giving control over the line's
1941 \c{x1} and \c{y1} give the coordinates of one end of the line.
1942 \c{x2} and \c{y2} give the coordinates of the other end.
1943 \c{thickness} gives the thickness of the line, in pixels.
1945 Note that the coordinates and thickness are floating-point: the
1946 continuous coordinate system is in effect here. It's important to
1947 be able to address points with better-than-pixel precision in this
1948 case, because one can't otherwise properly express the endpoints of
1949 lines with both odd and even thicknesses.
1951 Some platforms may perform anti-aliasing on this function. The
1952 precise pixels affected by a thick-line drawing operation may vary
1953 between platforms, and no particular guarantees are provided.
1954 Indeed, even horizontal or vertical lines may be anti-aliased.
1956 This function may be used for both drawing and printing.
1958 If the specified thickness is less than 1.0, 1.0 is used.
1959 This ensures that thin lines are visible even at small scales.
1961 \S{drawing-draw-text} \cw{draw_text()}
1963 \c void draw_text(drawing *dr, int x, int y, int fonttype,
1964 \c int fontsize, int align, int colour,
1965 \c const char *text);
1967 Draws text in the puzzle window.
1969 \c{x} and \c{y} give the coordinates of a point. The relation of
1970 this point to the location of the text is specified by \c{align},
1971 which is a bitwise OR of horizontal and vertical alignment flags:
1973 \dt \cw{ALIGN_VNORMAL}
1975 \dd Indicates that \c{y} is aligned with the baseline of the text.
1977 \dt \cw{ALIGN_VCENTRE}
1979 \dd Indicates that \c{y} is aligned with the vertical centre of the
1980 text. (In fact, it's aligned with the vertical centre of normal
1981 \e{capitalised} text: displaying two pieces of text with
1982 \cw{ALIGN_VCENTRE} at the same \cw{y}-coordinate will cause their
1983 baselines to be aligned with one another, even if one is an ascender
1984 and the other a descender.)
1986 \dt \cw{ALIGN_HLEFT}
1988 \dd Indicates that \c{x} is aligned with the left-hand end of the
1991 \dt \cw{ALIGN_HCENTRE}
1993 \dd Indicates that \c{x} is aligned with the horizontal centre of
1996 \dt \cw{ALIGN_HRIGHT}
1998 \dd Indicates that \c{x} is aligned with the right-hand end of the
2001 \c{fonttype} is either \cw{FONT_FIXED} or \cw{FONT_VARIABLE}, for a
2002 monospaced or proportional font respectively. (No more detail than
2003 that may be specified; it would only lead to portability issues
2004 between different platforms.)
2006 \c{fontsize} is the desired size, in pixels, of the text. This size
2007 corresponds to the overall point size of the text, not to any
2008 internal dimension such as the cap-height.
2010 \c{colour} is an integer index into the colours array returned by
2011 the back end function \cw{colours()} (\k{backend-colours}).
2013 This function may be used for both drawing and printing.
2015 The character set used to encode the text passed to this function is
2016 specified \e{by the drawing object}, although it must be a superset
2017 of ASCII. If a puzzle wants to display text that is not contained in
2018 ASCII, it should use the \cw{text_fallback()} function
2019 (\k{drawing-text-fallback}) to query the drawing object for an
2020 appropriate representation of the characters it wants.
2022 \S{drawing-text-fallback} \cw{text_fallback()}
2024 \c char *text_fallback(drawing *dr, const char *const *strings,
2027 This function is used to request a translation of UTF-8 text into
2028 whatever character encoding is expected by the drawing object's
2029 implementation of \cw{draw_text()}.
2031 The input is a list of strings encoded in UTF-8: \cw{nstrings} gives
2032 the number of strings in the list, and \cw{strings[0]},
2033 \cw{strings[1]}, ..., \cw{strings[nstrings-1]} are the strings
2036 The returned string (which is dynamically allocated and must be
2037 freed when finished with) is derived from the first string in the
2038 list that the drawing object expects to be able to display reliably;
2039 it will consist of that string translated into the character set
2040 expected by \cw{draw_text()}.
2042 Drawing implementations are not required to handle anything outside
2043 ASCII, but are permitted to assume that \e{some} string will be
2044 successfully translated. So every call to this function must include
2045 a string somewhere in the list (presumably the last element) which
2046 consists of nothing but ASCII, to be used by any front end which
2047 cannot handle anything else.
2049 For example, if a puzzle wished to display a string including a
2050 multiplication sign (U+00D7 in Unicode, represented by the bytes C3
2051 97 in UTF-8), it might do something like this:
2053 \c static const char *const times_signs[] = { "\xC3\x97", "x" };
2054 \c char *times_sign = text_fallback(dr, times_signs, 2);
2055 \c sprintf(buffer, "%d%s%d", width, times_sign, height);
2056 \c draw_text(dr, x, y, font, size, align, colour, buffer);
2059 which would draw a string with a times sign in the middle on
2060 platforms that support it, and fall back to a simple ASCII \cq{x}
2061 where there was no alternative.
2063 \S{drawing-clip} \cw{clip()}
2065 \c void clip(drawing *dr, int x, int y, int w, int h);
2067 Establishes a clipping rectangle in the puzzle window.
2069 \c{x} and \c{y} give the coordinates of the top left pixel of the
2070 clipping rectangle. \c{w} and \c{h} give its width and height. Thus,
2071 the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
2072 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
2073 inclusive. (These are exactly the same semantics as
2076 After this call, no drawing operation will affect anything outside
2077 the specified rectangle. The effect can be reversed by calling
2078 \cw{unclip()} (\k{drawing-unclip}). The clipping rectangle is
2079 pixel-perfect: pixels within the rectangle are affected as usual by
2080 drawing functions; pixels outside are completely untouched.
2082 Back ends should not assume that a clipping rectangle will be
2083 automatically cleared up by the front end if it's left lying around;
2084 that might work on current front ends, but shouldn't be relied upon.
2085 Always explicitly call \cw{unclip()}.
2087 This function may be used for both drawing and printing.
2089 \S{drawing-unclip} \cw{unclip()}
2091 \c void unclip(drawing *dr);
2093 Reverts the effect of a previous call to \cw{clip()}. After this
2094 call, all drawing operations will be able to affect the entire
2095 puzzle window again.
2097 This function may be used for both drawing and printing.
2099 \S{drawing-draw-update} \cw{draw_update()}
2101 \c void draw_update(drawing *dr, int x, int y, int w, int h);
2103 Informs the front end that a rectangular portion of the puzzle
2104 window has been drawn on and needs to be updated.
2106 \c{x} and \c{y} give the coordinates of the top left pixel of the
2107 update rectangle. \c{w} and \c{h} give its width and height. Thus,
2108 the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
2109 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
2110 inclusive. (These are exactly the same semantics as
2113 The back end redraw function \e{must} call this function to report
2114 any changes it has made to the window. Otherwise, those changes may
2115 not become immediately visible, and may then appear at an
2116 unpredictable subsequent time such as the next time the window is
2117 covered and re-exposed.
2119 This function is only important when drawing. It may be called when
2120 printing as well, but doing so is not compulsory, and has no effect.
2121 (So if you have a shared piece of code between the drawing and
2122 printing routines, that code may safely call \cw{draw_update()}.)
2124 \S{drawing-status-bar} \cw{status_bar()}
2126 \c void status_bar(drawing *dr, const char *text);
2128 Sets the text in the game's status bar to \c{text}. The text is copied
2129 from the supplied buffer, so the caller is free to deallocate or
2130 modify the buffer after use.
2132 (This function is not exactly a \e{drawing} function, but it shares
2133 with the drawing API the property that it may only be called from
2134 within the back end redraw function, so this is as good a place as
2135 any to document it.)
2137 The supplied text is filtered through the mid-end for optional
2138 rewriting before being passed on to the front end; the mid-end will
2139 prepend the current game time if the game is timed (and may in
2140 future perform other rewriting if it seems like a good idea).
2142 This function is for drawing only; it must never be called during
2145 \S{drawing-blitter} Blitter functions
2147 This section describes a group of related functions which save and
2148 restore a section of the puzzle window. This is most commonly used
2149 to implement user interfaces involving dragging a puzzle element
2150 around the window: at the end of each call to \cw{redraw()}, if an
2151 object is currently being dragged, the back end saves the window
2152 contents under that location and then draws the dragged object, and
2153 at the start of the next \cw{redraw()} the first thing it does is to
2154 restore the background.
2156 The front end defines an opaque type called a \c{blitter}, which is
2157 capable of storing a rectangular area of a specified size.
2159 Blitter functions are for drawing only; they must never be called
2162 \S2{drawing-blitter-new} \cw{blitter_new()}
2164 \c blitter *blitter_new(drawing *dr, int w, int h);
2166 Creates a new blitter object which stores a rectangle of size \c{w}
2167 by \c{h} pixels. Returns a pointer to the blitter object.
2169 Blitter objects are best stored in the \c{game_drawstate}. A good
2170 time to create them is in the \cw{set_size()} function
2171 (\k{backend-set-size}), since it is at this point that you first
2172 know how big a rectangle they will need to save.
2174 \S2{drawing-blitter-free} \cw{blitter_free()}
2176 \c void blitter_free(drawing *dr, blitter *bl);
2178 Disposes of a blitter object. Best called in \cw{free_drawstate()}.
2179 (However, check that the blitter object is not \cw{NULL} before
2180 attempting to free it; it is possible that a draw state might be
2181 created and freed without ever having \cw{set_size()} called on it
2184 \S2{drawing-blitter-save} \cw{blitter_save()}
2186 \c void blitter_save(drawing *dr, blitter *bl, int x, int y);
2188 This is a true drawing API function, in that it may only be called
2189 from within the game redraw routine. It saves a rectangular portion
2190 of the puzzle window into the specified blitter object.
2192 \c{x} and \c{y} give the coordinates of the top left corner of the
2193 saved rectangle. The rectangle's width and height are the ones
2194 specified when the blitter object was created.
2196 This function is required to cope and do the right thing if \c{x}
2197 and \c{y} are out of range. (The right thing probably means saving
2198 whatever part of the blitter rectangle overlaps with the visible
2199 area of the puzzle window.)
2201 \S2{drawing-blitter-load} \cw{blitter_load()}
2203 \c void blitter_load(drawing *dr, blitter *bl, int x, int y);
2205 This is a true drawing API function, in that it may only be called
2206 from within the game redraw routine. It restores a rectangular
2207 portion of the puzzle window from the specified blitter object.
2209 \c{x} and \c{y} give the coordinates of the top left corner of the
2210 rectangle to be restored. The rectangle's width and height are the
2211 ones specified when the blitter object was created.
2213 Alternatively, you can specify both \c{x} and \c{y} as the special
2214 value \cw{BLITTER_FROMSAVED}, in which case the rectangle will be
2215 restored to exactly where it was saved from. (This is probably what
2216 you want to do almost all the time, if you're using blitters to
2217 implement draggable puzzle elements.)
2219 This function is required to cope and do the right thing if \c{x}
2220 and \c{y} (or the equivalent ones saved in the blitter) are out of
2221 range. (The right thing probably means restoring whatever part of
2222 the blitter rectangle overlaps with the visible area of the puzzle
2225 If this function is called on a blitter which had previously been
2226 saved from a partially out-of-range rectangle, then the parts of the
2227 saved bitmap which were not visible at save time are undefined. If
2228 the blitter is restored to a different position so as to make those
2229 parts visible, the effect on the drawing area is undefined.
2231 \S{print-mono-colour} \cw{print_mono_colour()}
2233 \c int print_mono_colour(drawing *dr, int grey);
2235 This function allocates a colour index for a simple monochrome
2236 colour during printing.
2238 \c{grey} must be 0 or 1. If \c{grey} is 0, the colour returned is
2239 black; if \c{grey} is 1, the colour is white.
2241 \S{print-grey-colour} \cw{print_grey_colour()}
2243 \c int print_grey_colour(drawing *dr, float grey);
2245 This function allocates a colour index for a grey-scale colour
2248 \c{grey} may be any number between 0 (black) and 1 (white); for
2249 example, 0.5 indicates a medium grey.
2251 The chosen colour will be rendered to the limits of the printer's
2252 halftoning capability.
2254 \S{print-hatched-colour} \cw{print_hatched_colour()}
2256 \c int print_hatched_colour(drawing *dr, int hatch);
2258 This function allocates a colour index which does not represent a
2259 literal \e{colour}. Instead, regions shaded in this colour will be
2260 hatched with parallel lines. The \c{hatch} parameter defines what
2261 type of hatching should be used in place of this colour:
2263 \dt \cw{HATCH_SLASH}
2265 \dd This colour will be hatched by lines slanting to the right at 45
2268 \dt \cw{HATCH_BACKSLASH}
2270 \dd This colour will be hatched by lines slanting to the left at 45
2273 \dt \cw{HATCH_HORIZ}
2275 \dd This colour will be hatched by horizontal lines.
2279 \dd This colour will be hatched by vertical lines.
2283 \dd This colour will be hatched by criss-crossing horizontal and
2288 \dd This colour will be hatched by criss-crossing diagonal lines.
2290 Colours defined to use hatching may not be used for drawing lines or
2291 text; they may only be used for filling areas. That is, they may be
2292 used as the \c{fillcolour} parameter to \cw{draw_circle()} and
2293 \cw{draw_polygon()}, and as the colour parameter to
2294 \cw{draw_rect()}, but may not be used as the \c{outlinecolour}
2295 parameter to \cw{draw_circle()} or \cw{draw_polygon()}, or with
2296 \cw{draw_line()} or \cw{draw_text()}.
2298 \S{print-rgb-mono-colour} \cw{print_rgb_mono_colour()}
2300 \c int print_rgb_mono_colour(drawing *dr, float r, float g,
2301 \c float b, float grey);
2303 This function allocates a colour index for a fully specified RGB
2304 colour during printing.
2306 \c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.
2308 If printing in black and white only, these values will be ignored,
2309 and either pure black or pure white will be used instead, according
2310 to the \q{grey} parameter. (The fallback colour is the same as the
2311 one which would be allocated by \cw{print_mono_colour(grey)}.)
2313 \S{print-rgb-grey-colour} \cw{print_rgb_grey_colour()}
2315 \c int print_rgb_grey_colour(drawing *dr, float r, float g,
2316 \c float b, float grey);
2318 This function allocates a colour index for a fully specified RGB
2319 colour during printing.
2321 \c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.
2323 If printing in black and white only, these values will be ignored,
2324 and a shade of grey given by the \c{grey} parameter will be used
2325 instead. (The fallback colour is the same as the one which would be
2326 allocated by \cw{print_grey_colour(grey)}.)
2328 \S{print-rgb-hatched-colour} \cw{print_rgb_hatched_colour()}
2330 \c int print_rgb_hatched_colour(drawing *dr, float r, float g,
2331 \c float b, float hatched);
2333 This function allocates a colour index for a fully specified RGB
2334 colour during printing.
2336 \c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.
2338 If printing in black and white only, these values will be ignored,
2339 and a form of cross-hatching given by the \c{hatch} parameter will
2340 be used instead; see \k{print-hatched-colour} for the possible
2341 values of this parameter. (The fallback colour is the same as the
2342 one which would be allocated by \cw{print_hatched_colour(hatch)}.)
2344 \S{print-line-width} \cw{print_line_width()}
2346 \c void print_line_width(drawing *dr, int width);
2348 This function is called to set the thickness of lines drawn during
2349 printing. It is meaningless in drawing: all lines drawn by
2350 \cw{draw_line()}, \cw{draw_circle} and \cw{draw_polygon()} are one
2351 pixel in thickness. However, in printing there is no clear
2352 definition of a pixel and so line widths must be explicitly
2355 The line width is specified in the usual coordinate system. Note,
2356 however, that it is a hint only: the central printing system may
2357 choose to vary line thicknesses at user request or due to printer
2360 \S{print-line-dotted} \cw{print_line_dotted()}
2362 \c void print_line_dotted(drawing *dr, int dotted);
2364 This function is called to toggle the drawing of dotted lines during
2365 printing. It is not supported during drawing.
2367 The parameter \cq{dotted} is a boolean; \cw{TRUE} means that future
2368 lines drawn by \cw{draw_line()}, \cw{draw_circle} and
2369 \cw{draw_polygon()} will be dotted, and \cw{FALSE} means that they
2372 Some front ends may impose restrictions on the width of dotted
2373 lines. Asking for a dotted line via this front end will override any
2374 line width request if the front end requires it.
2376 \H{drawing-frontend} The drawing API as implemented by the front end
2378 This section describes the drawing API in the function-pointer form
2379 in which it is implemented by a front end.
2381 (It isn't only platform-specific front ends which implement this
2382 API; the platform-independent module \c{ps.c} also provides an
2383 implementation of it which outputs PostScript. Thus, any platform
2384 which wants to do PS printing can do so with minimum fuss.)
2386 The following entries all describe function pointer fields in a
2387 structure called \c{drawing_api}. Each of the functions takes a
2388 \cq{void *} context pointer, which it should internally cast back to
2389 a more useful type. Thus, a drawing \e{object} (\c{drawing *)}
2390 suitable for passing to the back end redraw or printing functions
2391 is constructed by passing a \c{drawing_api} and a \cq{void *} to the
2392 function \cw{drawing_new()} (see \k{drawing-new}).
2394 \S{drawingapi-draw-text} \cw{draw_text()}
2396 \c void (*draw_text)(void *handle, int x, int y, int fonttype,
2397 \c int fontsize, int align, int colour,
2398 \c const char *text);
2400 This function behaves exactly like the back end \cw{draw_text()}
2401 function; see \k{drawing-draw-text}.
2403 \S{drawingapi-draw-rect} \cw{draw_rect()}
2405 \c void (*draw_rect)(void *handle, int x, int y, int w, int h,
2408 This function behaves exactly like the back end \cw{draw_rect()}
2409 function; see \k{drawing-draw-rect}.
2411 \S{drawingapi-draw-line} \cw{draw_line()}
2413 \c void (*draw_line)(void *handle, int x1, int y1, int x2, int y2,
2416 This function behaves exactly like the back end \cw{draw_line()}
2417 function; see \k{drawing-draw-line}.
2419 \S{drawingapi-draw-polygon} \cw{draw_polygon()}
2421 \c void (*draw_polygon)(void *handle, int *coords, int npoints,
2422 \c int fillcolour, int outlinecolour);
2424 This function behaves exactly like the back end \cw{draw_polygon()}
2425 function; see \k{drawing-draw-polygon}.
2427 \S{drawingapi-draw-circle} \cw{draw_circle()}
2429 \c void (*draw_circle)(void *handle, int cx, int cy, int radius,
2430 \c int fillcolour, int outlinecolour);
2432 This function behaves exactly like the back end \cw{draw_circle()}
2433 function; see \k{drawing-draw-circle}.
2435 \S{drawingapi-draw-thick-line} \cw{draw_thick_line()}
2437 \c void draw_thick_line(drawing *dr, float thickness,
2438 \c float x1, float y1, float x2, float y2,
2441 This function behaves exactly like the back end
2442 \cw{draw_thick_line()} function; see \k{drawing-draw-thick-line}.
2444 An implementation of this API which doesn't provide high-quality
2445 rendering of thick lines is permitted to define this function
2446 pointer to be \cw{NULL}. The middleware in \cw{drawing.c} will notice
2447 and provide a low-quality alternative using \cw{draw_polygon()}.
2449 \S{drawingapi-draw-update} \cw{draw_update()}
2451 \c void (*draw_update)(void *handle, int x, int y, int w, int h);
2453 This function behaves exactly like the back end \cw{draw_update()}
2454 function; see \k{drawing-draw-update}.
2456 An implementation of this API which only supports printing is
2457 permitted to define this function pointer to be \cw{NULL} rather
2458 than bothering to define an empty function. The middleware in
2459 \cw{drawing.c} will notice and avoid calling it.
2461 \S{drawingapi-clip} \cw{clip()}
2463 \c void (*clip)(void *handle, int x, int y, int w, int h);
2465 This function behaves exactly like the back end \cw{clip()}
2466 function; see \k{drawing-clip}.
2468 \S{drawingapi-unclip} \cw{unclip()}
2470 \c void (*unclip)(void *handle);
2472 This function behaves exactly like the back end \cw{unclip()}
2473 function; see \k{drawing-unclip}.
2475 \S{drawingapi-start-draw} \cw{start_draw()}
2477 \c void (*start_draw)(void *handle);
2479 This function is called at the start of drawing. It allows the front
2480 end to initialise any temporary data required to draw with, such as
2483 Implementations of this API which do not provide drawing services
2484 may define this function pointer to be \cw{NULL}; it will never be
2485 called unless drawing is attempted.
2487 \S{drawingapi-end-draw} \cw{end_draw()}
2489 \c void (*end_draw)(void *handle);
2491 This function is called at the end of drawing. It allows the front
2492 end to do cleanup tasks such as deallocating device contexts and
2493 scheduling appropriate GUI redraw events.
2495 Implementations of this API which do not provide drawing services
2496 may define this function pointer to be \cw{NULL}; it will never be
2497 called unless drawing is attempted.
2499 \S{drawingapi-status-bar} \cw{status_bar()}
2501 \c void (*status_bar)(void *handle, const char *text);
2503 This function behaves exactly like the back end \cw{status_bar()}
2504 function; see \k{drawing-status-bar}.
2506 Front ends implementing this function need not worry about it being
2507 called repeatedly with the same text; the middleware code in
2508 \cw{status_bar()} will take care of this.
2510 Implementations of this API which do not provide drawing services
2511 may define this function pointer to be \cw{NULL}; it will never be
2512 called unless drawing is attempted.
2514 \S{drawingapi-blitter-new} \cw{blitter_new()}
2516 \c blitter *(*blitter_new)(void *handle, int w, int h);
2518 This function behaves exactly like the back end \cw{blitter_new()}
2519 function; see \k{drawing-blitter-new}.
2521 Implementations of this API which do not provide drawing services
2522 may define this function pointer to be \cw{NULL}; it will never be
2523 called unless drawing is attempted.
2525 \S{drawingapi-blitter-free} \cw{blitter_free()}
2527 \c void (*blitter_free)(void *handle, blitter *bl);
2529 This function behaves exactly like the back end \cw{blitter_free()}
2530 function; see \k{drawing-blitter-free}.
2532 Implementations of this API which do not provide drawing services
2533 may define this function pointer to be \cw{NULL}; it will never be
2534 called unless drawing is attempted.
2536 \S{drawingapi-blitter-save} \cw{blitter_save()}
2538 \c void (*blitter_save)(void *handle, blitter *bl, int x, int y);
2540 This function behaves exactly like the back end \cw{blitter_save()}
2541 function; see \k{drawing-blitter-save}.
2543 Implementations of this API which do not provide drawing services
2544 may define this function pointer to be \cw{NULL}; it will never be
2545 called unless drawing is attempted.
2547 \S{drawingapi-blitter-load} \cw{blitter_load()}
2549 \c void (*blitter_load)(void *handle, blitter *bl, int x, int y);
2551 This function behaves exactly like the back end \cw{blitter_load()}
2552 function; see \k{drawing-blitter-load}.
2554 Implementations of this API which do not provide drawing services
2555 may define this function pointer to be \cw{NULL}; it will never be
2556 called unless drawing is attempted.
2558 \S{drawingapi-begin-doc} \cw{begin_doc()}
2560 \c void (*begin_doc)(void *handle, int pages);
2562 This function is called at the beginning of a printing run. It gives
2563 the front end an opportunity to initialise any required printing
2564 subsystem. It also provides the number of pages in advance.
2566 Implementations of this API which do not provide printing services
2567 may define this function pointer to be \cw{NULL}; it will never be
2568 called unless printing is attempted.
2570 \S{drawingapi-begin-page} \cw{begin_page()}
2572 \c void (*begin_page)(void *handle, int number);
2574 This function is called during printing, at the beginning of each
2575 page. It gives the page number (numbered from 1 rather than 0, so
2576 suitable for use in user-visible contexts).
2578 Implementations of this API which do not provide printing services
2579 may define this function pointer to be \cw{NULL}; it will never be
2580 called unless printing is attempted.
2582 \S{drawingapi-begin-puzzle} \cw{begin_puzzle()}
2584 \c void (*begin_puzzle)(void *handle, float xm, float xc,
2585 \c float ym, float yc, int pw, int ph, float wmm);
2587 This function is called during printing, just before printing a
2588 single puzzle on a page. It specifies the size and location of the
2591 \c{xm} and \c{xc} specify the horizontal position of the puzzle on
2592 the page, as a linear function of the page width. The front end is
2593 expected to multiply the page width by \c{xm}, add \c{xc} (measured
2594 in millimetres), and use the resulting x-coordinate as the left edge
2597 Similarly, \c{ym} and \c{yc} specify the vertical position of the
2598 puzzle as a function of the page height: the page height times
2599 \c{ym}, plus \c{yc} millimetres, equals the desired distance from
2600 the top of the page to the top of the puzzle.
2602 (This unwieldy mechanism is required because not all printing
2603 systems can communicate the page size back to the software. The
2604 PostScript back end, for example, writes out PS which determines the
2605 page size at print time by means of calling \cq{clippath}, and
2606 centres the puzzles within that. Thus, exactly the same PS file
2607 works on A4 or on US Letter paper without needing local
2608 configuration, which simplifies matters.)
2610 \cw{pw} and \cw{ph} give the size of the puzzle in drawing API
2611 coordinates. The printing system will subsequently call the puzzle's
2612 own print function, which will in turn call drawing API functions in
2613 the expectation that an area \cw{pw} by \cw{ph} units is available
2614 to draw the puzzle on.
2616 Finally, \cw{wmm} gives the desired width of the puzzle in
2617 millimetres. (The aspect ratio is expected to be preserved, so if
2618 the desired puzzle height is also needed then it can be computed as
2621 Implementations of this API which do not provide printing services
2622 may define this function pointer to be \cw{NULL}; it will never be
2623 called unless printing is attempted.
2625 \S{drawingapi-end-puzzle} \cw{end_puzzle()}
2627 \c void (*end_puzzle)(void *handle);
2629 This function is called after the printing of a specific puzzle is
2632 Implementations of this API which do not provide printing services
2633 may define this function pointer to be \cw{NULL}; it will never be
2634 called unless printing is attempted.
2636 \S{drawingapi-end-page} \cw{end_page()}
2638 \c void (*end_page)(void *handle, int number);
2640 This function is called after the printing of a page is finished.
2642 Implementations of this API which do not provide printing services
2643 may define this function pointer to be \cw{NULL}; it will never be
2644 called unless printing is attempted.
2646 \S{drawingapi-end-doc} \cw{end_doc()}
2648 \c void (*end_doc)(void *handle);
2650 This function is called after the printing of the entire document is
2651 finished. This is the moment to close files, send things to the
2652 print spooler, or whatever the local convention is.
2654 Implementations of this API which do not provide printing services
2655 may define this function pointer to be \cw{NULL}; it will never be
2656 called unless printing is attempted.
2658 \S{drawingapi-line-width} \cw{line_width()}
2660 \c void (*line_width)(void *handle, float width);
2662 This function is called to set the line thickness, during printing
2663 only. Note that the width is a \cw{float} here, where it was an
2664 \cw{int} as seen by the back end. This is because \cw{drawing.c} may
2665 have scaled it on the way past.
2667 However, the width is still specified in the same coordinate system
2668 as the rest of the drawing.
2670 Implementations of this API which do not provide printing services
2671 may define this function pointer to be \cw{NULL}; it will never be
2672 called unless printing is attempted.
2674 \S{drawingapi-text-fallback} \cw{text_fallback()}
2676 \c char *(*text_fallback)(void *handle, const char *const *strings,
2679 This function behaves exactly like the back end \cw{text_fallback()}
2680 function; see \k{drawing-text-fallback}.
2682 Implementations of this API which do not support any characters
2683 outside ASCII may define this function pointer to be \cw{NULL}, in
2684 which case the central code in \cw{drawing.c} will provide a default
2687 \H{drawingapi-frontend} The drawing API as called by the front end
2689 There are a small number of functions provided in \cw{drawing.c}
2690 which the front end needs to \e{call}, rather than helping to
2691 implement. They are described in this section.
2693 \S{drawing-new} \cw{drawing_new()}
2695 \c drawing *drawing_new(const drawing_api *api, midend *me,
2698 This function creates a drawing object. It is passed a
2699 \c{drawing_api}, which is a structure containing nothing but
2700 function pointers; and also a \cq{void *} handle. The handle is
2701 passed back to each function pointer when it is called.
2703 The \c{midend} parameter is used for rewriting the status bar
2704 contents: \cw{status_bar()} (see \k{drawing-status-bar}) has to call
2705 a function in the mid-end which might rewrite the status bar text.
2706 If the drawing object is to be used only for printing, or if the
2707 game is known not to call \cw{status_bar()}, this parameter may be
2710 \S{drawing-free} \cw{drawing_free()}
2712 \c void drawing_free(drawing *dr);
2714 This function frees a drawing object. Note that the \cq{void *}
2715 handle is not freed; if that needs cleaning up it must be done by
2718 \S{drawing-print-get-colour} \cw{print_get_colour()}
2720 \c void print_get_colour(drawing *dr, int colour, int printincolour,
2721 \c int *hatch, float *r, float *g, float *b)
2723 This function is called by the implementations of the drawing API
2724 functions when they are called in a printing context. It takes a
2725 colour index as input, and returns the description of the colour as
2726 requested by the back end.
2728 \c{printincolour} is \cw{TRUE} iff the implementation is printing in
2729 colour. This will alter the results returned if the colour in
2730 question was specified with a black-and-white fallback value.
2732 If the colour should be rendered by hatching, \c{*hatch} is filled
2733 with the type of hatching desired. See \k{print-grey-colour} for
2734 details of the values this integer can take.
2736 If the colour should be rendered as solid colour, \c{*hatch} is
2737 given a negative value, and \c{*r}, \c{*g} and \c{*b} are filled
2738 with the RGB values of the desired colour (if printing in colour),
2739 or all filled with the grey-scale value (if printing in black and
2742 \C{midend} The API provided by the mid-end
2744 This chapter documents the API provided by the mid-end to be called
2745 by the front end. You probably only need to read this if you are a
2746 front end implementor, i.e. you are porting Puzzles to a new
2747 platform. If you're only interested in writing new puzzles, you can
2748 safely skip this chapter.
2750 All the persistent state in the mid-end is encapsulated within a
2751 \c{midend} structure, to facilitate having multiple mid-ends in any
2752 port which supports multiple puzzle windows open simultaneously.
2753 Each \c{midend} is intended to handle the contents of a single
2756 \H{midend-new} \cw{midend_new()}
2758 \c midend *midend_new(frontend *fe, const game *ourgame,
2759 \c const drawing_api *drapi, void *drhandle)
2761 Allocates and returns a new mid-end structure.
2763 The \c{fe} argument is stored in the mid-end. It will be used when
2764 calling back to functions such as \cw{activate_timer()}
2765 (\k{frontend-activate-timer}), and will be passed on to the back end
2766 function \cw{colours()} (\k{backend-colours}).
2768 The parameters \c{drapi} and \c{drhandle} are passed to
2769 \cw{drawing_new()} (\k{drawing-new}) to construct a drawing object
2770 which will be passed to the back end function \cw{redraw()}
2771 (\k{backend-redraw}). Hence, all drawing-related function pointers
2772 defined in \c{drapi} can expect to be called with \c{drhandle} as
2773 their first argument.
2775 The \c{ourgame} argument points to a container structure describing
2776 a game back end. The mid-end thus created will only be capable of
2777 handling that one game. (So even in a monolithic front end
2778 containing all the games, this imposes the constraint that any
2779 individual puzzle window is tied to a single game. Unless, of
2780 course, you feel brave enough to change the mid-end for the window
2781 without closing the window...)
2783 \H{midend-free} \cw{midend_free()}
2785 \c void midend_free(midend *me);
2787 Frees a mid-end structure and all its associated data.
2789 \H{midend-tilesize} \cw{midend_tilesize()}
2791 \c int midend_tilesize(midend *me);
2793 Returns the \cq{tilesize} parameter being used to display the
2794 current puzzle (\k{backend-preferred-tilesize}).
2796 \H{midend-set-params} \cw{midend_set_params()}
2798 \c void midend_set_params(midend *me, game_params *params);
2800 Sets the current game parameters for a mid-end. Subsequent games
2801 generated by \cw{midend_new_game()} (\k{midend-new-game}) will use
2802 these parameters until further notice.
2804 The usual way in which the front end will have an actual
2805 \c{game_params} structure to pass to this function is if it had
2806 previously got it from \cw{midend_get_presets()}
2807 (\k{midend-get-presets}). Thus, this function is usually called in
2808 response to the user making a selection from the presets menu.
2810 \H{midend-get-params} \cw{midend_get_params()}
2812 \c game_params *midend_get_params(midend *me);
2814 Returns the current game parameters stored in this mid-end.
2816 The returned value is dynamically allocated, and should be freed
2817 when finished with by passing it to the game's own
2818 \cw{free_params()} function (see \k{backend-free-params}).
2820 \H{midend-size} \cw{midend_size()}
2822 \c void midend_size(midend *me, int *x, int *y, int user_size);
2824 Tells the mid-end to figure out its window size.
2826 On input, \c{*x} and \c{*y} should contain the maximum or requested
2827 size for the window. (Typically this will be the size of the screen
2828 that the window has to fit on, or similar.) The mid-end will
2829 repeatedly call the back end function \cw{compute_size()}
2830 (\k{backend-compute-size}), searching for a tile size that best
2831 satisfies the requirements. On exit, \c{*x} and \c{*y} will contain
2832 the size needed for the puzzle window's drawing area. (It is of
2833 course up to the front end to adjust this for any additional window
2834 furniture such as menu bars and window borders, if necessary. The
2835 status bar is also not included in this size.)
2837 Use \c{user_size} to indicate whether \c{*x} and \c{*y} are a
2838 requested size, or just a maximum size.
2840 If \c{user_size} is set to \cw{TRUE}, the mid-end will treat the
2841 input size as a request, and will pick a tile size which
2842 approximates it \e{as closely as possible}, going over the game's
2843 preferred tile size if necessary to achieve this. The mid-end will
2844 also use the resulting tile size as its preferred one until further
2845 notice, on the assumption that this size was explicitly requested
2846 by the user. Use this option if you want your front end to support
2847 dynamic resizing of the puzzle window with automatic scaling of the
2850 If \c{user_size} is set to \cw{FALSE}, then the game's tile size
2851 will never go over its preferred one, although it may go under in
2852 order to fit within the maximum bounds specified by \c{*x} and
2853 \c{*y}. This is the recommended approach when opening a new window
2854 at default size: the game will use its preferred size unless it has
2855 to use a smaller one to fit on the screen. If the tile size is
2856 shrunk for this reason, the change will not persist; if a smaller
2857 grid is subsequently chosen, the tile size will recover.
2859 The mid-end will try as hard as it can to return a size which is
2860 less than or equal to the input size, in both dimensions. In extreme
2861 circumstances it may fail (if even the lowest possible tile size
2862 gives window dimensions greater than the input), in which case it
2863 will return a size greater than the input size. Front ends should be
2864 prepared for this to happen (i.e. don't crash or fail an assertion),
2865 but may handle it in any way they see fit: by rejecting the game
2866 parameters which caused the problem, by opening a window larger than
2867 the screen regardless of inconvenience, by introducing scroll bars
2868 on the window, by drawing on a large bitmap and scaling it into a
2869 smaller window, or by any other means you can think of. It is likely
2870 that when the tile size is that small the game will be unplayable
2871 anyway, so don't put \e{too} much effort into handling it
2874 If your platform has no limit on window size (or if you're planning
2875 to use scroll bars for large puzzles), you can pass dimensions of
2876 \cw{INT_MAX} as input to this function. You should probably not do
2877 that \e{and} set the \c{user_size} flag, though!
2879 The midend relies on the frontend calling \cw{midend_new_game()}
2880 (\k{midend-new-game}) before calling \cw{midend_size()}.
2882 \H{midend-reset-tilesize} \cw{midend_reset_tilesize()}
2884 \c void midend_reset_tilesize(midend *me);
2886 This function resets the midend's preferred tile size to that of the
2889 As discussed in \k{midend-size}, puzzle resizes are typically
2890 'sticky', in that once the user has dragged the puzzle to a different
2891 window size, the resulting tile size will be remembered and used when
2892 the puzzle configuration changes. If you \e{don't} want that, e.g. if
2893 you want to provide a command to explicitly reset the puzzle size back
2894 to its default, then you can call this just before calling
2895 \cw{midend_size()} (which, in turn, you would probably call with
2896 \c{user_size} set to \cw{FALSE}).
2898 \H{midend-new-game} \cw{midend_new_game()}
2900 \c void midend_new_game(midend *me);
2902 Causes the mid-end to begin a new game. Normally the game will be a
2903 new randomly generated puzzle. However, if you have previously
2904 called \cw{midend_game_id()} or \cw{midend_set_config()}, the game
2905 generated might be dictated by the results of those functions. (In
2906 particular, you \e{must} call \cw{midend_new_game()} after calling
2907 either of those functions, or else no immediate effect will be
2910 You will probably need to call \cw{midend_size()} after calling this
2911 function, because if the game parameters have been changed since the
2912 last new game then the window size might need to change. (If you
2913 know the parameters \e{haven't} changed, you don't need to do this.)
2915 This function will create a new \c{game_drawstate}, but does not
2916 actually perform a redraw (since you often need to call
2917 \cw{midend_size()} before the redraw can be done). So after calling
2918 this function and after calling \cw{midend_size()}, you should then
2919 call \cw{midend_redraw()}. (It is not necessary to call
2920 \cw{midend_force_redraw()}; that will discard the draw state and
2921 create a fresh one, which is unnecessary in this case since there's
2922 a fresh one already. It would work, but it's usually excessive.)
2924 \H{midend-restart-game} \cw{midend_restart_game()}
2926 \c void midend_restart_game(midend *me);
2928 This function causes the current game to be restarted. This is done
2929 by placing a new copy of the original game state on the end of the
2930 undo list (so that an accidental restart can be undone).
2932 This function automatically causes a redraw, i.e. the front end can
2933 expect its drawing API to be called from \e{within} a call to this
2934 function. Some back ends require that \cw{midend_size()}
2935 (\k{midend-size}) is called before \cw{midend_restart_game()}.
2937 \H{midend-force-redraw} \cw{midend_force_redraw()}
2939 \c void midend_force_redraw(midend *me);
2941 Forces a complete redraw of the puzzle window, by means of
2942 discarding the current \c{game_drawstate} and creating a new one
2943 from scratch before calling the game's \cw{redraw()} function.
2945 The front end can expect its drawing API to be called from within a
2946 call to this function. Some back ends require that \cw{midend_size()}
2947 (\k{midend-size}) is called before \cw{midend_force_redraw()}.
2949 \H{midend-redraw} \cw{midend_redraw()}
2951 \c void midend_redraw(midend *me);
2953 Causes a partial redraw of the puzzle window, by means of simply
2954 calling the game's \cw{redraw()} function. (That is, the only things
2955 redrawn will be things that have changed since the last redraw.)
2957 The front end can expect its drawing API to be called from within a
2958 call to this function. Some back ends require that \cw{midend_size()}
2959 (\k{midend-size}) is called before \cw{midend_redraw()}.
2961 \H{midend-process-key} \cw{midend_process_key()}
2963 \c int midend_process_key(midend *me, int x, int y, int button);
2965 The front end calls this function to report a mouse or keyboard
2966 event. The parameters \c{x}, \c{y} and \c{button} are almost
2967 identical to the ones passed to the back end function
2968 \cw{interpret_move()} (\k{backend-interpret-move}), except that the
2969 front end is \e{not} required to provide the guarantees about mouse
2970 event ordering. The mid-end will sort out multiple simultaneous
2971 button presses and changes of button; the front end's responsibility
2972 is simply to pass on the mouse events it receives as accurately as
2975 (Some platforms may need to emulate absent mouse buttons by means of
2976 using a modifier key such as Shift with another mouse button. This
2977 tends to mean that if Shift is pressed or released in the middle of
2978 a mouse drag, the mid-end will suddenly stop receiving, say,
2979 \cw{LEFT_DRAG} events and start receiving \cw{RIGHT_DRAG}s, with no
2980 intervening button release or press events. This too is something
2981 which the mid-end will sort out for you; the front end has no
2982 obligation to maintain sanity in this area.)
2984 The front end \e{should}, however, always eventually send some kind
2985 of button release. On some platforms this requires special effort:
2986 Windows, for example, requires a call to the system API function
2987 \cw{SetCapture()} in order to ensure that your window receives a
2988 mouse-up event even if the pointer has left the window by the time
2989 the mouse button is released. On any platform that requires this
2990 sort of thing, the front end \e{is} responsible for doing it.
2992 Calling this function is very likely to result in calls back to the
2993 front end's drawing API and/or \cw{activate_timer()}
2994 (\k{frontend-activate-timer}).
2996 The return value from \cw{midend_process_key()} is non-zero, unless
2997 the effect of the keypress was to request termination of the
2998 program. A front end should shut down the puzzle in response to a
3001 \H{midend-colours} \cw{midend_colours()}
3003 \c float *midend_colours(midend *me, int *ncolours);
3005 Returns an array of the colours required by the game, in exactly the
3006 same format as that returned by the back end function \cw{colours()}
3007 (\k{backend-colours}). Front ends should call this function rather
3008 than calling the back end's version directly, since the mid-end adds
3009 standard customisation facilities. (At the time of writing, those
3010 customisation facilities are implemented hackily by means of
3011 environment variables, but it's not impossible that they may become
3012 more full and formal in future.)
3014 \H{midend-timer} \cw{midend_timer()}
3016 \c void midend_timer(midend *me, float tplus);
3018 If the mid-end has called \cw{activate_timer()}
3019 (\k{frontend-activate-timer}) to request regular callbacks for
3020 purposes of animation or timing, this is the function the front end
3021 should call on a regular basis. The argument \c{tplus} gives the
3022 time, in seconds, since the last time either this function was
3023 called or \cw{activate_timer()} was invoked.
3025 One of the major purposes of timing in the mid-end is to perform
3026 move animation. Therefore, calling this function is very likely to
3027 result in calls back to the front end's drawing API.
3029 \H{midend-get-presets} \cw{midend_get_presets()}
3031 \c struct preset_menu *midend_get_presets(midend *me, int *id_limit);
3033 Returns a data structure describing this game's collection of preset
3034 game parameters, organised into a hierarchical structure of menus and
3037 The return value is a pointer to a data structure containing the
3038 following fields (among others, which are not intended for front end
3041 \c struct preset_menu {
3043 \c struct preset_menu_entry *entries;
3044 \c /* and other things */
3045 \e iiiiiiiiiiiiiiiiiiiiii
3048 Those fields describe the intended contents of one particular menu in
3049 the hierarchy. \cq{entries} points to an array of \cq{n_entries}
3050 items, each of which is a structure containing the following fields:
3052 \c struct preset_menu_entry {
3054 \c game_params *params;
3055 \c struct preset_menu *submenu;
3059 Of these fields, \cq{title} and \cq{id} are present in every entry,
3060 giving (respectively) the textual name of the menu item and an integer
3061 identifier for it. The integer id will correspond to the one returned
3062 by \c{midend_which_preset} (\k{midend-which-preset}), when that preset
3063 is the one selected.
3065 The other two fields are mutually exclusive. Each \c{struct
3066 preset_menu_entry} will have one of those fields \cw{NULL} and the
3067 other one non-null. If the menu item is an actual preset, then
3068 \cq{params} will point to the set of game parameters that go with the
3069 name; if it's a submenu, then \cq{submenu} instead will be non-null,
3070 and will point at a subsidiary \c{struct preset_menu}.
3072 The complete hierarchy of these structures is owned by the mid-end,
3073 and will be freed when the mid-end is freed. The front end should not
3074 attempt to free any of it.
3076 The integer identifiers will be allocated densely from 0 upwards, so
3077 that it's reasonable for the front end to allocate an array which uses
3078 them as indices, if it needs to store information per preset menu
3079 item. For this purpose, the front end may pass the second parameter
3080 \cq{id_limit} to \cw{midend_get_presets} as the address of an \c{int}
3081 variable, into which \cw{midend_get_presets} will write an integer one
3082 larger than the largest id number actually used (i.e. the number of
3083 elements the front end would need in the array).
3085 Submenu-type entries also have integer identifiers.
3087 \H{midend-which-preset} \cw{midend_which_preset()}
3089 \c int midend_which_preset(midend *me);
3091 Returns the numeric index of the preset game parameter structure
3092 which matches the current game parameters, or a negative number if
3093 no preset matches. Front ends could use this to maintain a tick
3094 beside one of the items in the menu (or tick the \q{Custom} option
3095 if the return value is less than zero).
3097 The returned index value (if non-negative) will match the \c{id} field
3098 of the corresponding \cw{struct preset_menu_entry} returned by
3099 \c{midend_get_presets()} (\k{midend-get-presets}).
3101 \H{midend-wants-statusbar} \cw{midend_wants_statusbar()}
3103 \c int midend_wants_statusbar(midend *me);
3105 This function returns \cw{TRUE} if the puzzle has a use for a
3106 textual status line (to display score, completion status, currently
3107 active tiles, time, or anything else).
3109 Front ends should call this function rather than talking directly to
3112 \H{midend-get-config} \cw{midend_get_config()}
3114 \c config_item *midend_get_config(midend *me, int which,
3115 \c char **wintitle);
3117 Returns a dialog box description for user configuration.
3119 On input, \cw{which} should be set to one of three values, which
3120 select which of the various dialog box descriptions is returned:
3122 \dt \cw{CFG_SETTINGS}
3124 \dd Requests the GUI parameter configuration box generated by the
3125 puzzle itself. This should be used when the user selects \q{Custom}
3126 from the game types menu (or equivalent). The mid-end passes this
3127 request on to the back end function \cw{configure()}
3128 (\k{backend-configure}).
3132 \dd Requests a box suitable for entering a descriptive game ID (and
3133 viewing the existing one). The mid-end generates this dialog box
3134 description itself. This should be used when the user selects
3135 \q{Specific} from the game menu (or equivalent).
3139 \dd Requests a box suitable for entering a random-seed game ID (and
3140 viewing the existing one). The mid-end generates this dialog box
3141 description itself. This should be used when the user selects
3142 \q{Random Seed} from the game menu (or equivalent).
3144 The returned value is an array of \cw{config_item}s, exactly as
3145 described in \k{backend-configure}. Another returned value is an
3146 ASCII string giving a suitable title for the configuration window,
3149 Both returned values are dynamically allocated and will need to be
3150 freed. The window title can be freed in the obvious way; the
3151 \cw{config_item} array is a slightly complex structure, so a utility
3152 function \cw{free_cfg()} is provided to free it for you. See
3155 (Of course, you will probably not want to free the \cw{config_item}
3156 array until the dialog box is dismissed, because before then you
3157 will probably need to pass it to \cw{midend_set_config}.)
3159 \H{midend-set-config} \cw{midend_set_config()}
3161 \c const char *midend_set_config(midend *me, int which,
3162 \c config_item *cfg);
3164 Passes the mid-end the results of a configuration dialog box.
3165 \c{which} should have the same value which it had when
3166 \cw{midend_get_config()} was called; \c{cfg} should be the array of
3167 \c{config_item}s returned from \cw{midend_get_config()}, modified to
3168 contain the results of the user's editing operations.
3170 This function returns \cw{NULL} on success, or otherwise (if the
3171 configuration data was in some way invalid) an ASCII string
3172 containing an error message suitable for showing to the user.
3174 If the function succeeds, it is likely that the game parameters will
3175 have been changed and it is certain that a new game will be
3176 requested. The front end should therefore call
3177 \cw{midend_new_game()}, and probably also re-think the window size
3178 using \cw{midend_size()} and eventually perform a refresh using
3179 \cw{midend_redraw()}.
3181 \H{midend-game-id} \cw{midend_game_id()}
3183 \c const char *midend_game_id(midend *me, const char *id);
3185 Passes the mid-end a string game ID (of any of the valid forms
3186 \cq{params}, \cq{params:description} or \cq{params#seed}) which the
3187 mid-end will process and use for the next generated game.
3189 This function returns \cw{NULL} on success, or otherwise (if the
3190 configuration data was in some way invalid) an ASCII string
3191 containing an error message (not dynamically allocated) suitable for
3192 showing to the user. In the event of an error, the mid-end's
3193 internal state will be left exactly as it was before the call.
3195 If the function succeeds, it is likely that the game parameters will
3196 have been changed and it is certain that a new game will be
3197 requested. The front end should therefore call
3198 \cw{midend_new_game()}, and probably also re-think the window size
3199 using \cw{midend_size()} and eventually case a refresh using
3200 \cw{midend_redraw()}.
3202 \H{midend-get-game-id} \cw{midend_get_game_id()}
3204 \c char *midend_get_game_id(midend *me)
3206 Returns a descriptive game ID (i.e. one in the form
3207 \cq{params:description}) describing the game currently active in the
3208 mid-end. The returned string is dynamically allocated.
3210 \H{midend-get-random-seed} \cw{midend_get_random_seed()}
3212 \c char *midend_get_random_seed(midend *me)
3214 Returns a random game ID (i.e. one in the form \cq{params#seedstring})
3215 describing the game currently active in the mid-end, if there is one.
3216 If the game was created by entering a description, no random seed will
3217 currently exist and this function will return \cw{NULL}.
3219 The returned string, if it is non-\cw{NULL}, is dynamically allocated.
3221 \H{midend-can-format-as-text-now} \cw{midend_can_format_as_text_now()}
3223 \c int midend_can_format_as_text_now(midend *me);
3225 Returns \cw{TRUE} if the game code is capable of formatting puzzles
3226 of the currently selected game type as ASCII.
3228 If this returns \cw{FALSE}, then \cw{midend_text_format()}
3229 (\k{midend-text-format}) will return \cw{NULL}.
3231 \H{midend-text-format} \cw{midend_text_format()}
3233 \c char *midend_text_format(midend *me);
3235 Formats the current game's current state as ASCII text suitable for
3236 copying to the clipboard. The returned string is dynamically
3239 If the game's \c{can_format_as_text_ever} flag is \cw{FALSE}, or if
3240 its \cw{can_format_as_text_now()} function returns \cw{FALSE}, then
3241 this function will return \cw{NULL}.
3243 If the returned string contains multiple lines (which is likely), it
3244 will use the normal C line ending convention (\cw{\\n} only). On
3245 platforms which use a different line ending convention for data in
3246 the clipboard, it is the front end's responsibility to perform the
3249 \H{midend-solve} \cw{midend_solve()}
3251 \c const char *midend_solve(midend *me);
3253 Requests the mid-end to perform a Solve operation.
3255 On success, \cw{NULL} is returned. On failure, an error message (not
3256 dynamically allocated) is returned, suitable for showing to the
3259 The front end can expect its drawing API and/or
3260 \cw{activate_timer()} to be called from within a call to this
3261 function. Some back ends require that \cw{midend_size()}
3262 (\k{midend-size}) is called before \cw{midend_solve()}.
3264 \H{midend-status} \cw{midend_status()}
3266 \c int midend_status(midend *me);
3268 This function returns +1 if the midend is currently displaying a game
3269 in a solved state, -1 if the game is in a permanently lost state, or 0
3270 otherwise. This function just calls the back end's \cw{status()}
3271 function. Front ends may wish to use this as a cue to proactively
3272 offer the option of starting a new game.
3274 (See \k{backend-status} for more detail about the back end's
3275 \cw{status()} function and discussion of what should count as which
3278 \H{midend-can-undo} \cw{midend_can_undo()}
3280 \c int midend_can_undo(midend *me);
3282 Returns \cw{TRUE} if the midend is currently in a state where the undo
3283 operation is meaningful (i.e. at least one position exists on the undo
3284 chain before the present one). Front ends may wish to use this to
3285 visually activate and deactivate an undo button.
3287 \H{midend-can-redo} \cw{midend_can_redo()}
3289 \c int midend_can_redo(midend *me);
3291 Returns \cw{TRUE} if the midend is currently in a state where the redo
3292 operation is meaningful (i.e. at least one position exists on the redo
3293 chain after the present one). Front ends may wish to use this to
3294 visually activate and deactivate a redo button.
3296 \H{midend-serialise} \cw{midend_serialise()}
3298 \c void midend_serialise(midend *me,
3299 \c void (*write)(void *ctx, const void *buf, int len), void *wctx);
3301 Calling this function causes the mid-end to convert its entire
3302 internal state into a long ASCII text string, and to pass that
3303 string (piece by piece) to the supplied \c{write} function.
3305 Desktop implementations can use this function to save a game in any
3306 state (including half-finished) to a disk file, by supplying a
3307 \c{write} function which is a wrapper on \cw{fwrite()} (or local
3308 equivalent). Other implementations may find other uses for it, such
3309 as compressing the large and sprawling mid-end state into a
3310 manageable amount of memory when a palmtop application is suspended
3311 so that another one can run; in this case \cw{write} might want to
3312 write to a memory buffer rather than a file. There may be other uses
3315 This function will call back to the supplied \c{write} function a
3316 number of times, with the first parameter (\c{ctx}) equal to
3317 \c{wctx}, and the other two parameters pointing at a piece of the
3320 \H{midend-deserialise} \cw{midend_deserialise()}
3322 \c const char *midend_deserialise(midend *me,
3323 \c int (*read)(void *ctx, void *buf, int len), void *rctx);
3325 This function is the counterpart to \cw{midend_serialise()}. It
3326 calls the supplied \cw{read} function repeatedly to read a quantity
3327 of data, and attempts to interpret that data as a serialised mid-end
3328 as output by \cw{midend_serialise()}.
3330 The \cw{read} function is called with the first parameter (\c{ctx})
3331 equal to \c{rctx}, and should attempt to read \c{len} bytes of data
3332 into the buffer pointed to by \c{buf}. It should return \cw{FALSE}
3333 on failure or \cw{TRUE} on success. It should not report success
3334 unless it has filled the entire buffer; on platforms which might be
3335 reading from a pipe or other blocking data source, \c{read} is
3336 responsible for looping until the whole buffer has been filled.
3338 If the de-serialisation operation is successful, the mid-end's
3339 internal data structures will be replaced by the results of the
3340 load, and \cw{NULL} will be returned. Otherwise, the mid-end's state
3341 will be completely unchanged and an error message (typically some
3342 variation on \q{save file is corrupt}) will be returned. As usual,
3343 the error message string is not dynamically allocated.
3345 If this function succeeds, it is likely that the game parameters
3346 will have been changed. The front end should therefore probably
3347 re-think the window size using \cw{midend_size()}, and probably
3348 cause a refresh using \cw{midend_redraw()}.
3350 Because each mid-end is tied to a specific game back end, this
3351 function will fail if you attempt to read in a save file generated by
3352 a different game from the one configured in this mid-end, even if your
3353 application is a monolithic one containing all the puzzles. See
3354 \k{identify-game} for a helper function which will allow you to
3355 identify a save file before you instantiate your mid-end in the first
3358 \H{identify-game} \cw{identify_game()}
3360 \c const char *identify_game(char **name,
3361 \c int (*read)(void *ctx, void *buf, int len), void *rctx);
3363 This function examines a serialised midend stream, of the same kind
3364 used by \cw{midend_serialise()} and \cw{midend_deserialise()}, and
3365 returns the \cw{name} field of the game back end from which it was
3368 You might want this if your front end was a monolithic one containing
3369 all the puzzles, and you wanted to be able to load an arbitrary save
3370 file and automatically switch to the right game. Probably your next
3371 step would be to iterate through \cw{gamelist} (\k{frontend-backend})
3372 looking for a game structure whose \cw{name} field matched the
3373 returned string, and give an error if you didn't find one.
3375 On success, the return value of this function is \cw{NULL}, and the
3376 game name string is written into \cw{*name}. The caller should free
3377 that string after using it.
3379 On failure, \cw{*name} is \cw{NULL}, and the return value is an error
3380 message (which does not need freeing at all).
3382 (This isn't strictly speaking a midend function, since it doesn't
3383 accept or return a pointer to a midend. You'd probably call it just
3384 \e{before} deciding what kind of midend you wanted to instantiate.)
3386 \H{midend-request-id-changes} \cw{midend_request_id_changes()}
3388 \c void midend_request_id_changes(midend *me,
3389 \c void (*notify)(void *), void *ctx);
3391 This function is called by the front end to request notification by
3392 the mid-end when the current game IDs (either descriptive or
3393 random-seed) change. This can occur as a result of keypresses ('n' for
3394 New Game, for example) or when a puzzle supersedes its game
3395 description (see \k{backend-supersede}). After this function is
3396 called, any change of the game ids will cause the mid-end to call
3397 \cw{notify(ctx)} after the change.
3399 This is for use by puzzles which want to present the game description
3400 to the user constantly (e.g. as an HTML hyperlink) instead of only
3401 showing it when the user explicitly requests it.
3403 This is a function I anticipate few front ends needing to implement,
3404 so I make it a callback rather than a static function in order to
3405 relieve most front ends of the need to provide an empty
3408 \H{frontend-backend} Direct reference to the back end structure by
3411 Although \e{most} things the front end needs done should be done by
3412 calling the mid-end, there are a few situations in which the front
3413 end needs to refer directly to the game back end structure.
3415 The most obvious of these is
3417 \b passing the game back end as a parameter to \cw{midend_new()}.
3419 There are a few other back end features which are not wrapped by the
3420 mid-end because there didn't seem much point in doing so:
3422 \b fetching the \c{name} field to use in window titles and similar
3424 \b reading the \c{can_configure}, \c{can_solve} and
3425 \c{can_format_as_text_ever} fields to decide whether to add those
3426 items to the menu bar or equivalent
3428 \b reading the \c{winhelp_topic} field (Windows only)
3430 \b the GTK front end provides a \cq{--generate} command-line option
3431 which directly calls the back end to do most of its work. This is
3432 not really part of the main front end code, though, and I'm not sure
3435 In order to find the game back end structure, the front end does one
3438 \b If the particular front end is compiling a separate binary per
3439 game, then the back end structure is a global variable with the
3440 standard name \cq{thegame}:
3444 \c extern const game thegame;
3448 \b If the front end is compiled as a monolithic application
3449 containing all the puzzles together (in which case the preprocessor
3450 symbol \cw{COMBINED} must be defined when compiling most of the code
3451 base), then there will be two global variables defined:
3455 \c extern const game *gamelist[];
3456 \c extern const int gamecount;
3458 \c{gamelist} will be an array of \c{gamecount} game structures,
3459 declared in the automatically constructed source module \c{list.c}.
3460 The application should search that array for the game it wants,
3461 probably by reaching into each game structure and looking at its
3466 \H{frontend-api} Mid-end to front-end calls
3468 This section describes the small number of functions which a front
3469 end must provide to be called by the mid-end or other standard
3472 \H{frontend-get-random-seed} \cw{get_random_seed()}
3474 \c void get_random_seed(void **randseed, int *randseedsize);
3476 This function is called by a new mid-end, and also occasionally by
3477 game back ends. Its job is to return a piece of data suitable for
3478 using as a seed for initialisation of a new \c{random_state}.
3480 On exit, \c{*randseed} should be set to point at a newly allocated
3481 piece of memory containing some seed data, and \c{*randseedsize}
3482 should be set to the length of that data.
3484 A simple and entirely adequate implementation is to return a piece
3485 of data containing the current system time at the highest
3486 conveniently available resolution.
3488 \H{frontend-activate-timer} \cw{activate_timer()}
3490 \c void activate_timer(frontend *fe);
3492 This is called by the mid-end to request that the front end begin
3493 calling it back at regular intervals.
3495 The timeout interval is left up to the front end; the finer it is,
3496 the smoother move animations will be, but the more CPU time will be
3497 used. Current front ends use values around 20ms (i.e. 50Hz).
3499 After this function is called, the mid-end will expect to receive
3500 calls to \cw{midend_timer()} on a regular basis.
3502 \H{frontend-deactivate-timer} \cw{deactivate_timer()}
3504 \c void deactivate_timer(frontend *fe);
3506 This is called by the mid-end to request that the front end stop
3507 calling \cw{midend_timer()}.
3509 \H{frontend-fatal} \cw{fatal()}
3511 \c void fatal(const char *fmt, ...);
3513 This is called by some utility functions if they encounter a
3514 genuinely fatal error such as running out of memory. It is a
3515 variadic function in the style of \cw{printf()}, and is expected to
3516 show the formatted error message to the user any way it can and then
3517 terminate the application. It must not return.
3519 \H{frontend-default-colour} \cw{frontend_default_colour()}
3521 \c void frontend_default_colour(frontend *fe, float *output);
3523 This function expects to be passed a pointer to an array of three
3524 \cw{float}s. It returns the platform's local preferred background
3525 colour in those three floats, as red, green and blue values (in that
3526 order) ranging from \cw{0.0} to \cw{1.0}.
3528 This function should only ever be called by the back end function
3529 \cw{colours()} (\k{backend-colours}). (Thus, it isn't a
3530 \e{midend}-to-frontend function as such, but there didn't seem to be
3531 anywhere else particularly good to put it. Sorry.)
3533 \C{utils} Utility APIs
3535 This chapter documents a variety of utility APIs provided for the
3536 general use of the rest of the Puzzles code.
3538 \H{utils-random} Random number generation
3540 Platforms' local random number generators vary widely in quality and
3541 seed size. Puzzles therefore supplies its own high-quality random
3542 number generator, with the additional advantage of giving the same
3543 results if fed the same seed data on different platforms. This
3544 allows game random seeds to be exchanged between different ports of
3545 Puzzles and still generate the same games.
3547 Unlike the ANSI C \cw{rand()} function, the Puzzles random number
3548 generator has an \e{explicit} state object called a
3549 \c{random_state}. One of these is managed by each mid-end, for
3550 example, and passed to the back end to generate a game with.
3552 \S{utils-random-init} \cw{random_new()}
3554 \c random_state *random_new(char *seed, int len);
3556 Allocates, initialises and returns a new \c{random_state}. The input
3557 data is used as the seed for the random number stream (i.e. using
3558 the same seed at a later time will generate the same stream).
3560 The seed data can be any data at all; there is no requirement to use
3561 printable ASCII, or NUL-terminated strings, or anything like that.
3563 \S{utils-random-copy} \cw{random_copy()}
3565 \c random_state *random_copy(random_state *tocopy);
3567 Allocates a new \c{random_state}, copies the contents of another
3568 \c{random_state} into it, and returns the new state. If exactly the
3569 same sequence of functions is subseqently called on both the copy and
3570 the original, the results will be identical. This may be useful for
3571 speculatively performing some operation using a given random state,
3572 and later replaying that operation precisely.
3574 \S{utils-random-free} \cw{random_free()}
3576 \c void random_free(random_state *state);
3578 Frees a \c{random_state}.
3580 \S{utils-random-bits} \cw{random_bits()}
3582 \c unsigned long random_bits(random_state *state, int bits);
3584 Returns a random number from 0 to \cw{2^bits-1} inclusive. \c{bits}
3585 should be between 1 and 32 inclusive.
3587 \S{utils-random-upto} \cw{random_upto()}
3589 \c unsigned long random_upto(random_state *state, unsigned long limit);
3591 Returns a random number from 0 to \cw{limit-1} inclusive.
3593 \S{utils-random-state-encode} \cw{random_state_encode()}
3595 \c char *random_state_encode(random_state *state);
3597 Encodes the entire contents of a \c{random_state} in printable
3598 ASCII. Returns a dynamically allocated string containing that
3599 encoding. This can subsequently be passed to
3600 \cw{random_state_decode()} to reconstruct the same \c{random_state}.
3602 \S{utils-random-state-decode} \cw{random_state_decode()}
3604 \c random_state *random_state_decode(char *input);
3606 Decodes a string generated by \cw{random_state_encode()} and
3607 reconstructs an equivalent \c{random_state} to the one encoded, i.e.
3608 it should produce the same stream of random numbers.
3610 This function has no error reporting; if you pass it an invalid
3611 string it will simply generate an arbitrary random state, which may
3612 turn out to be noticeably non-random.
3614 \S{utils-shuffle} \cw{shuffle()}
3616 \c void shuffle(void *array, int nelts, int eltsize, random_state *rs);
3618 Shuffles an array into a random order. The interface is much like
3619 ANSI C \cw{qsort()}, except that there's no need for a compare
3622 \c{array} is a pointer to the first element of the array. \c{nelts}
3623 is the number of elements in the array; \c{eltsize} is the size of a
3624 single element (typically measured using \c{sizeof}). \c{rs} is a
3625 \c{random_state} used to generate all the random numbers for the
3628 \H{utils-presets} Presets menu management
3630 The function \c{midend_get_presets()} (\k{midend-get-presets}) returns
3631 a data structure describing a menu hierarchy. Back ends can also
3632 choose to provide such a structure to the mid-end, if they want to
3633 group their presets hierarchically. To make this easy, there are a few
3634 utility functions to construct preset menu structures, and also one
3635 intended for front-end use.
3637 \S{utils-preset-menu-new} \cw{preset_menu_new()}
3639 \c struct preset_menu *preset_menu_new(void);
3641 Allocates a new \c{struct preset_menu}, and initialises it to hold no
3644 \S{utils-preset-menu-add_submenu} \cw{preset_menu_add_submenu()}
3646 \c struct preset_menu *preset_menu_add_submenu
3647 \c (struct preset_menu *parent, char *title);
3649 Adds a new submenu to the end of an existing preset menu, and returns
3650 a pointer to a newly allocated \c{struct preset_menu} describing the
3653 The string parameter \cq{title} must be dynamically allocated by the
3654 caller. The preset-menu structure will take ownership of it, so the
3655 caller must not free it.
3657 \S{utils-preset-menu-add-preset} \cw{preset_menu_add_preset()}
3659 \c void preset_menu_add_preset
3660 \c (struct preset_menu *menu, char *title, game_params *params);
3662 Adds a preset game configuration to the end of a preset menu.
3664 Both the string parameter \cq{title} and the game parameter structure
3665 \cq{params} itself must be dynamically allocated by the caller. The
3666 preset-menu structure will take ownership of it, so the caller must
3669 \S{utils-preset-menu-lookup-by-id} \cw{preset_menu_lookup_by_id()}
3671 \c game_params *preset_menu_lookup_by_id
3672 \c (struct preset_menu *menu, int id);
3674 Given a numeric index, searches recursively through a preset menu
3675 hierarchy to find the corresponding menu entry, and returns a pointer
3676 to its existing \c{game_params} structure.
3678 This function is intended for front end use (but front ends need not
3679 use it if they prefer to do things another way). If a front end finds
3680 it inconvenient to store anything more than a numeric index alongside
3681 each menu item, then this function provides an easy way for the front
3682 end to get back the actual game parameters corresponding to a menu
3683 item that the user has selected.
3685 \H{utils-alloc} Memory allocation
3687 Puzzles has some central wrappers on the standard memory allocation
3688 functions, which provide compile-time type checking, and run-time
3689 error checking by means of quitting the application if it runs out
3690 of memory. This doesn't provide the best possible recovery from
3691 memory shortage, but on the other hand it greatly simplifies the
3692 rest of the code, because nothing else anywhere needs to worry about
3693 \cw{NULL} returns from allocation.
3695 \S{utils-snew} \cw{snew()}
3697 \c var = snew(type);
3700 This macro takes a single argument which is a \e{type name}. It
3701 allocates space for one object of that type. If allocation fails it
3702 will call \cw{fatal()} and not return; so if it does return, you can
3703 be confident that its return value is non-\cw{NULL}.
3705 The return value is cast to the specified type, so that the compiler
3706 will type-check it against the variable you assign it into. Thus,
3707 this ensures you don't accidentally allocate memory the size of the
3708 wrong type and assign it into a variable of the right one (or vice
3711 \S{utils-snewn} \cw{snewn()}
3713 \c var = snewn(n, type);
3716 This macro is the array form of \cw{snew()}. It takes two arguments;
3717 the first is a number, and the second is a type name. It allocates
3718 space for that many objects of that type, and returns a type-checked
3719 non-\cw{NULL} pointer just as \cw{snew()} does.
3721 \S{utils-sresize} \cw{sresize()}
3723 \c var = sresize(var, n, type);
3726 This macro is a type-checked form of \cw{realloc()}. It takes three
3727 arguments: an input memory block, a new size in elements, and a
3728 type. It re-sizes the input memory block to a size sufficient to
3729 contain that many elements of that type. It returns a type-checked
3730 non-\cw{NULL} pointer, like \cw{snew()} and \cw{snewn()}.
3732 The input memory block can be \cw{NULL}, in which case this function
3733 will behave exactly like \cw{snewn()}. (In principle any
3734 ANSI-compliant \cw{realloc()} implementation ought to cope with
3735 this, but I've never quite trusted it to work everywhere.)
3737 \S{utils-sfree} \cw{sfree()}
3739 \c void sfree(void *p);
3741 This function is pretty much equivalent to \cw{free()}. It is
3742 provided with a dynamically allocated block, and frees it.
3744 The input memory block can be \cw{NULL}, in which case this function
3745 will do nothing. (In principle any ANSI-compliant \cw{free()}
3746 implementation ought to cope with this, but I've never quite trusted
3747 it to work everywhere.)
3749 \S{utils-dupstr} \cw{dupstr()}
3751 \c char *dupstr(const char *s);
3753 This function dynamically allocates a duplicate of a C string. Like
3754 the \cw{snew()} functions, it guarantees to return non-\cw{NULL} or
3757 (Many platforms provide the function \cw{strdup()}. As well as
3758 guaranteeing never to return \cw{NULL}, my version has the advantage
3759 of being defined \e{everywhere}, rather than inconveniently not
3762 \S{utils-free-cfg} \cw{free_cfg()}
3764 \c void free_cfg(config_item *cfg);
3766 This function correctly frees an array of \c{config_item}s, including
3767 walking the array until it gets to the end and freeing any subsidiary
3768 data items in each \c{u} sub-union which are expected to be
3769 dynamically allocated.
3771 (See \k{backend-configure} for details of the \c{config_item}
3774 \H{utils-tree234} Sorted and counted tree functions
3776 Many games require complex algorithms for generating random puzzles,
3777 and some require moderately complex algorithms even during play. A
3778 common requirement during these algorithms is for a means of
3779 maintaining sorted or unsorted lists of items, such that items can
3780 be removed and added conveniently.
3782 For general use, Puzzles provides the following set of functions
3783 which maintain 2-3-4 trees in memory. (A 2-3-4 tree is a balanced
3784 tree structure, with the property that all lookups, insertions,
3785 deletions, splits and joins can be done in \cw{O(log N)} time.)
3787 All these functions expect you to be storing a tree of \c{void *}
3788 pointers. You can put anything you like in those pointers.
3790 By the use of per-node element counts, these tree structures have
3791 the slightly unusual ability to look elements up by their numeric
3792 index within the list represented by the tree. This means that they
3793 can be used to store an unsorted list (in which case, every time you
3794 insert a new element, you must explicitly specify the position where
3795 you wish to insert it). They can also do numeric lookups in a sorted
3796 tree, which might be useful for (for example) tracking the median of
3797 a changing data set.
3799 As well as storing sorted lists, these functions can be used for
3800 storing \q{maps} (associative arrays), by defining each element of a
3801 tree to be a (key, value) pair.
3803 \S{utils-newtree234} \cw{newtree234()}
3805 \c tree234 *newtree234(cmpfn234 cmp);
3807 Creates a new empty tree, and returns a pointer to it.
3809 The parameter \c{cmp} determines the sorting criterion on the tree.
3812 \c typedef int (*cmpfn234)(void *, void *);
3814 If you want a sorted tree, you should provide a function matching
3815 this prototype, which returns like \cw{strcmp()} does (negative if
3816 the first argument is smaller than the second, positive if it is
3817 bigger, zero if they compare equal). In this case, the function
3818 \cw{addpos234()} will not be usable on your tree (because all
3819 insertions must respect the sorting order).
3821 If you want an unsorted tree, pass \cw{NULL}. In this case you will
3822 not be able to use either \cw{add234()} or \cw{del234()}, or any
3823 other function such as \cw{find234()} which depends on a sorting
3824 order. Your tree will become something more like an array, except
3825 that it will efficiently support insertion and deletion as well as
3826 lookups by numeric index.
3828 \S{utils-freetree234} \cw{freetree234()}
3830 \c void freetree234(tree234 *t);
3832 Frees a tree. This function will not free the \e{elements} of the
3833 tree (because they might not be dynamically allocated, or you might
3834 be storing the same set of elements in more than one tree); it will
3835 just free the tree structure itself. If you want to free all the
3836 elements of a tree, you should empty it before passing it to
3837 \cw{freetree234()}, by means of code along the lines of
3839 \c while ((element = delpos234(tree, 0)) != NULL)
3840 \c sfree(element); /* or some more complicated free function */
3841 \e iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
3843 \S{utils-add234} \cw{add234()}
3845 \c void *add234(tree234 *t, void *e);
3847 Inserts a new element \c{e} into the tree \c{t}. This function
3848 expects the tree to be sorted; the new element is inserted according
3851 If an element comparing equal to \c{e} is already in the tree, then
3852 the insertion will fail, and the return value will be the existing
3853 element. Otherwise, the insertion succeeds, and \c{e} is returned.
3855 \S{utils-addpos234} \cw{addpos234()}
3857 \c void *addpos234(tree234 *t, void *e, int index);
3859 Inserts a new element into an unsorted tree. Since there is no
3860 sorting order to dictate where the new element goes, you must
3861 specify where you want it to go. Setting \c{index} to zero puts the
3862 new element right at the start of the list; setting \c{index} to the
3863 current number of elements in the tree puts the new element at the
3866 Return value is \c{e}, in line with \cw{add234()} (although this
3867 function cannot fail except by running out of memory, in which case
3868 it will bomb out and die rather than returning an error indication).
3870 \S{utils-index234} \cw{index234()}
3872 \c void *index234(tree234 *t, int index);
3874 Returns a pointer to the \c{index}th element of the tree, or
3875 \cw{NULL} if \c{index} is out of range. Elements of the tree are
3878 \S{utils-find234} \cw{find234()}
3880 \c void *find234(tree234 *t, void *e, cmpfn234 cmp);
3882 Searches for an element comparing equal to \c{e} in a sorted tree.
3884 If \c{cmp} is \cw{NULL}, the tree's ordinary comparison function
3885 will be used to perform the search. However, sometimes you don't
3886 want that; suppose, for example, each of your elements is a big
3887 structure containing a \c{char *} name field, and you want to find
3888 the element with a given name. You \e{could} achieve this by
3889 constructing a fake element structure, setting its name field
3890 appropriately, and passing it to \cw{find234()}, but you might find
3891 it more convenient to pass \e{just} a name string to \cw{find234()},
3892 supplying an alternative comparison function which expects one of
3893 its arguments to be a bare name and the other to be a large
3894 structure containing a name field.
3896 Therefore, if \c{cmp} is not \cw{NULL}, then it will be used to
3897 compare \c{e} to elements of the tree. The first argument passed to
3898 \c{cmp} will always be \c{e}; the second will be an element of the
3901 (See \k{utils-newtree234} for the definition of the \c{cmpfn234}
3902 function pointer type.)
3904 The returned value is the element found, or \cw{NULL} if the search
3907 \S{utils-findrel234} \cw{findrel234()}
3909 \c void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);
3911 This function is like \cw{find234()}, but has the additional ability
3912 to do a \e{relative} search. The additional parameter \c{relation}
3913 can be one of the following values:
3917 \dd Find only an element that compares equal to \c{e}. This is
3918 exactly the behaviour of \cw{find234()}.
3922 \dd Find the greatest element that compares strictly less than
3923 \c{e}. \c{e} may be \cw{NULL}, in which case it finds the greatest
3924 element in the whole tree (which could also be done by
3925 \cw{index234(t, count234(t)-1)}).
3929 \dd Find the greatest element that compares less than or equal to
3930 \c{e}. (That is, find an element that compares equal to \c{e} if
3931 possible, but failing that settle for something just less than it.)
3935 \dd Find the smallest element that compares strictly greater than
3936 \c{e}. \c{e} may be \cw{NULL}, in which case it finds the smallest
3937 element in the whole tree (which could also be done by
3938 \cw{index234(t, 0)}).
3942 \dd Find the smallest element that compares greater than or equal to
3943 \c{e}. (That is, find an element that compares equal to \c{e} if
3944 possible, but failing that settle for something just bigger than
3947 Return value, as before, is the element found or \cw{NULL} if no
3948 element satisfied the search criterion.
3950 \S{utils-findpos234} \cw{findpos234()}
3952 \c void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);
3954 This function is like \cw{find234()}, but has the additional feature
3955 of returning the index of the element found in the tree; that index
3956 is written to \c{*index} in the event of a successful search (a
3957 non-\cw{NULL} return value).
3959 \c{index} may be \cw{NULL}, in which case this function behaves
3960 exactly like \cw{find234()}.
3962 \S{utils-findrelpos234} \cw{findrelpos234()}
3964 \c void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
3967 This function combines all the features of \cw{findrel234()} and
3970 \S{utils-del234} \cw{del234()}
3972 \c void *del234(tree234 *t, void *e);
3974 Finds an element comparing equal to \c{e} in the tree, deletes it,
3977 The input tree must be sorted.
3979 The element found might be \c{e} itself, or might merely compare
3982 Return value is \cw{NULL} if no such element is found.
3984 \S{utils-delpos234} \cw{delpos234()}
3986 \c void *delpos234(tree234 *t, int index);
3988 Deletes the element at position \c{index} in the tree, and returns
3991 Return value is \cw{NULL} if the index is out of range.
3993 \S{utils-count234} \cw{count234()}
3995 \c int count234(tree234 *t);
3997 Returns the number of elements currently in the tree.
3999 \S{utils-splitpos234} \cw{splitpos234()}
4001 \c tree234 *splitpos234(tree234 *t, int index, int before);
4003 Splits the input tree into two pieces at a given position, and
4004 creates a new tree containing all the elements on one side of that
4007 If \c{before} is \cw{TRUE}, then all the items at or after position
4008 \c{index} are left in the input tree, and the items before that
4009 point are returned in the new tree. Otherwise, the reverse happens:
4010 all the items at or after \c{index} are moved into the new tree, and
4011 those before that point are left in the old one.
4013 If \c{index} is equal to 0 or to the number of elements in the input
4014 tree, then one of the two trees will end up empty (and this is not
4015 an error condition). If \c{index} is further out of range in either
4016 direction, the operation will fail completely and return \cw{NULL}.
4018 This operation completes in \cw{O(log N)} time, no matter how large
4019 the tree or how balanced or unbalanced the split.
4021 \S{utils-split234} \cw{split234()}
4023 \c tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);
4025 Splits a sorted tree according to its sort order.
4027 \c{rel} can be any of the relation constants described in
4028 \k{utils-findrel234}, \e{except} for \cw{REL234_EQ}. All the
4029 elements having that relation to \c{e} will be transferred into the
4030 new tree; the rest will be left in the old one.
4032 The parameter \c{cmp} has the same semantics as it does in
4033 \cw{find234()}: if it is not \cw{NULL}, it will be used in place of
4034 the tree's own comparison function when comparing elements to \c{e},
4035 in such a way that \c{e} itself is always the first of its two
4038 Again, this operation completes in \cw{O(log N)} time, no matter how
4039 large the tree or how balanced or unbalanced the split.
4041 \S{utils-join234} \cw{join234()}
4043 \c tree234 *join234(tree234 *t1, tree234 *t2);
4045 Joins two trees together by concatenating the lists they represent.
4046 All the elements of \c{t2} are moved into \c{t1}, in such a way that
4047 they appear \e{after} the elements of \c{t1}. The tree \c{t2} is
4048 freed; the return value is \c{t1}.
4050 If you apply this function to a sorted tree and it violates the sort
4051 order (i.e. the smallest element in \c{t2} is smaller than or equal
4052 to the largest element in \c{t1}), the operation will fail and
4055 This operation completes in \cw{O(log N)} time, no matter how large
4056 the trees being joined together.
4058 \S{utils-join234r} \cw{join234r()}
4060 \c tree234 *join234r(tree234 *t1, tree234 *t2);
4062 Joins two trees together in exactly the same way as \cw{join234()},
4063 but this time the combined tree is returned in \c{t2}, and \c{t1} is
4064 destroyed. The elements in \c{t1} still appear before those in
4067 Again, this operation completes in \cw{O(log N)} time, no matter how
4068 large the trees being joined together.
4070 \S{utils-copytree234} \cw{copytree234()}
4072 \c tree234 *copytree234(tree234 *t, copyfn234 copyfn,
4073 \c void *copyfnstate);
4075 Makes a copy of an entire tree.
4077 If \c{copyfn} is \cw{NULL}, the tree will be copied but the elements
4078 will not be; i.e. the new tree will contain pointers to exactly the
4079 same physical elements as the old one.
4081 If you want to copy each actual element during the operation, you
4082 can instead pass a function in \c{copyfn} which makes a copy of each
4083 element. That function has the prototype
4085 \c typedef void *(*copyfn234)(void *state, void *element);
4087 and every time it is called, the \c{state} parameter will be set to
4088 the value you passed in as \c{copyfnstate}.
4090 \H{utils-misc} Miscellaneous utility functions and macros
4092 This section contains all the utility functions which didn't
4093 sensibly fit anywhere else.
4095 \S{utils-truefalse} \cw{TRUE} and \cw{FALSE}
4097 The main Puzzles header file defines the macros \cw{TRUE} and
4098 \cw{FALSE}, which are used throughout the code in place of 1 and 0
4099 (respectively) to indicate that the values are in a boolean context.
4100 For code base consistency, I'd prefer it if submissions of new code
4101 followed this convention as well.
4103 \S{utils-maxmin} \cw{max()} and \cw{min()}
4105 The main Puzzles header file defines the pretty standard macros
4106 \cw{max()} and \cw{min()}, each of which is given two arguments and
4107 returns the one which compares greater or less respectively.
4109 These macros may evaluate their arguments multiple times. Avoid side
4112 \S{utils-pi} \cw{PI}
4114 The main Puzzles header file defines a macro \cw{PI} which expands
4115 to a floating-point constant representing pi.
4117 (I've never understood why ANSI's \cw{<math.h>} doesn't define this.
4120 \S{utils-obfuscate-bitmap} \cw{obfuscate_bitmap()}
4122 \c void obfuscate_bitmap(unsigned char *bmp, int bits, int decode);
4124 This function obscures the contents of a piece of data, by
4125 cryptographic methods. It is useful for games of hidden information
4126 (such as Mines, Guess or Black Box), in which the game ID
4127 theoretically reveals all the information the player is supposed to
4128 be trying to guess. So in order that players should be able to send
4129 game IDs to one another without accidentally spoiling the resulting
4130 game by looking at them, these games obfuscate their game IDs using
4133 Although the obfuscation function is cryptographic, it cannot
4134 properly be called encryption because it has no key. Therefore,
4135 anybody motivated enough can re-implement it, or hack it out of the
4136 Puzzles source, and strip the obfuscation off one of these game IDs
4137 to see what lies beneath. (Indeed, they could usually do it much
4138 more easily than that, by entering the game ID into their own copy
4139 of the puzzle and hitting Solve.) The aim is not to protect against
4140 a determined attacker; the aim is simply to protect people who
4141 wanted to play the game honestly from \e{accidentally} spoiling
4144 The input argument \c{bmp} points at a piece of memory to be
4145 obfuscated. \c{bits} gives the length of the data. Note that that
4146 length is in \e{bits} rather than bytes: if you ask for obfuscation
4147 of a partial number of bytes, then you will get it. Bytes are
4148 considered to be used from the top down: thus, for example, setting
4149 \c{bits} to 10 will cover the whole of \cw{bmp[0]} and the \e{top
4150 two} bits of \cw{bmp[1]}. The remainder of a partially used byte is
4151 undefined (i.e. it may be corrupted by the function).
4153 The parameter \c{decode} is \cw{FALSE} for an encoding operation,
4154 and \cw{TRUE} for a decoding operation. Each is the inverse of the
4155 other. (There's no particular reason you shouldn't obfuscate by
4156 decoding and restore cleartext by encoding, if you really wanted to;
4157 it should still work.)
4159 The input bitmap is processed in place.
4161 \S{utils-bin2hex} \cw{bin2hex()}
4163 \c char *bin2hex(const unsigned char *in, int inlen);
4165 This function takes an input byte array and converts it into an
4166 ASCII string encoding those bytes in (lower-case) hex. It returns a
4167 dynamically allocated string containing that encoding.
4169 This function is useful for encoding the result of
4170 \cw{obfuscate_bitmap()} in printable ASCII for use in game IDs.
4172 \S{utils-hex2bin} \cw{hex2bin()}
4174 \c unsigned char *hex2bin(const char *in, int outlen);
4176 This function takes an ASCII string containing hex digits, and
4177 converts it back into a byte array of length \c{outlen}. If there
4178 aren't enough hex digits in the string, the contents of the
4179 resulting array will be undefined.
4181 This function is the inverse of \cw{bin2hex()}.
4183 \S{utils-game-mkhighlight} \cw{game_mkhighlight()}
4185 \c void game_mkhighlight(frontend *fe, float *ret,
4186 \c int background, int highlight, int lowlight);
4188 It's reasonably common for a puzzle game's graphics to use
4189 highlights and lowlights to indicate \q{raised} or \q{lowered}
4190 sections. Fifteen, Sixteen and Twiddle are good examples of this.
4192 Puzzles using this graphical style are running a risk if they just
4193 use whatever background colour is supplied to them by the front end,
4194 because that background colour might be too light to see any
4195 highlights on at all. (In particular, it's not unheard of for the
4196 front end to specify a default background colour of white.)
4198 Therefore, such puzzles can call this utility function from their
4199 \cw{colours()} routine (\k{backend-colours}). You pass it your front
4200 end handle, a pointer to the start of your return array, and three
4201 colour indices. It will:
4203 \b call \cw{frontend_default_colour()} (\k{frontend-default-colour})
4204 to fetch the front end's default background colour
4206 \b alter the brightness of that colour if it's unsuitable
4208 \b define brighter and darker variants of the colour to be used as
4209 highlights and lowlights
4211 \b write those results into the relevant positions in the \c{ret}
4214 Thus, \cw{ret[background*3]} to \cw{ret[background*3+2]} will be set
4215 to RGB values defining a sensible background colour, and similary
4216 \c{highlight} and \c{lowlight} will be set to sensible colours.
4218 \C{writing} How to write a new puzzle
4220 This chapter gives a guide to how to actually write a new puzzle:
4221 where to start, what to do first, how to solve common problems.
4223 The previous chapters have been largely composed of facts. This one
4226 \H{writing-editorial} Choosing a puzzle
4228 Before you start writing a puzzle, you have to choose one. Your
4229 taste in puzzle games is up to you, of course; and, in fact, you're
4230 probably reading this guide because you've \e{already} thought of a
4231 game you want to write. But if you want to get it accepted into the
4232 official Puzzles distribution, then there's a criterion it has to
4235 The current Puzzles editorial policy is that all games should be
4236 \e{fair}. A fair game is one which a player can only fail to
4237 complete through demonstrable lack of skill \dash that is, such that
4238 a better player in the same situation would have \e{known} to do
4239 something different.
4241 For a start, that means every game presented to the user must have
4242 \e{at least one solution}. Giving the unsuspecting user a puzzle
4243 which is actually impossible is not acceptable. (There is an
4244 exception: if the user has selected some non-default option which is
4245 clearly labelled as potentially unfair, \e{then} you're allowed to
4246 generate possibly insoluble puzzles, because the user isn't
4247 unsuspecting any more. Same Game and Mines both have options of this
4250 Also, this actually \e{rules out} games such as Klondike, or the
4251 normal form of Mahjong Solitaire. Those games have the property that
4252 even if there is a solution (i.e. some sequence of moves which will
4253 get from the start state to the solved state), the player doesn't
4254 necessarily have enough information to \e{find} that solution. In
4255 both games, it is possible to reach a dead end because you had an
4256 arbitrary choice to make and made it the wrong way. This violates
4257 the fairness criterion, because a better player couldn't have known
4258 they needed to make the other choice.
4260 (GNOME has a variant on Mahjong Solitaire which makes it fair: there
4261 is a Shuffle operation which randomly permutes all the remaining
4262 tiles without changing their positions, which allows you to get out
4263 of a sticky situation. Using this operation adds a 60-second penalty
4264 to your solution time, so it's to the player's advantage to try to
4265 minimise the chance of having to use it. It's still possible to
4266 render the game uncompletable if you end up with only two tiles
4267 vertically stacked, but that's easy to foresee and avoid using a
4268 shuffle operation. This form of the game \e{is} fair. Implementing
4269 it in Puzzles would require an infrastructure change so that the
4270 back end could communicate time penalties to the mid-end, but that
4271 would be easy enough.)
4273 Providing a \e{unique} solution is a little more negotiable; it
4274 depends on the puzzle. Solo would have been of unacceptably low
4275 quality if it didn't always have a unique solution, whereas Twiddle
4276 inherently has multiple solutions by its very nature and it would
4277 have been meaningless to even \e{suggest} making it uniquely
4278 soluble. Somewhere in between, Flip could reasonably be made to have
4279 unique solutions (by enforcing a zero-dimension kernel in every
4280 generated matrix) but it doesn't seem like a serious quality problem
4283 Of course, you don't \e{have} to care about all this. There's
4284 nothing stopping you implementing any puzzle you want to if you're
4285 happy to maintain your puzzle yourself, distribute it from your own
4286 web site, fork the Puzzles code completely, or anything like that.
4287 It's free software; you can do what you like with it. But any game
4288 that you want to be accepted into \e{my} Puzzles code base has to
4289 satisfy the fairness criterion, which means all randomly generated
4290 puzzles must have a solution (unless the user has deliberately
4291 chosen otherwise) and it must be possible \e{in theory} to find that
4292 solution without having to guess.
4294 \H{writing-gs} Getting started
4296 The simplest way to start writing a new puzzle is to copy
4297 \c{nullgame.c}. This is a template puzzle source file which does
4298 almost nothing, but which contains all the back end function
4299 prototypes and declares the back end data structure correctly. It is
4300 built every time the rest of Puzzles is built, to ensure that it
4301 doesn't get out of sync with the code and remains buildable.
4303 So start by copying \c{nullgame.c} into your new source file. Then
4304 you'll gradually add functionality until the very boring Null Game
4305 turns into your real game.
4307 Next you'll need to add your puzzle to the Makefiles, in order to
4308 compile it conveniently. \e{Do not edit the Makefiles}: they are
4309 created automatically by the script \c{mkfiles.pl}, from the file
4310 called \c{Recipe}. Edit \c{Recipe}, and then re-run \c{mkfiles.pl}.
4312 Also, don't forget to add your puzzle to \c{list.c}: if you don't,
4313 then it will still run fine on platforms which build each puzzle
4314 separately, but Mac OS X and other monolithic platforms will not
4315 include your new puzzle in their single binary.
4317 Once your source file is building, you can move on to the fun bit.
4319 \S{writing-generation} Puzzle generation
4321 Randomly generating instances of your puzzle is almost certain to be
4322 the most difficult part of the code, and also the task with the
4323 highest chance of turning out to be completely infeasible. Therefore
4324 I strongly recommend doing it \e{first}, so that if it all goes
4325 horribly wrong you haven't wasted any more time than you absolutely
4326 had to. What I usually do is to take an unmodified \c{nullgame.c},
4327 and start adding code to \cw{new_game_desc()} which tries to
4328 generate a puzzle instance and print it out using \cw{printf()}.
4329 Once that's working, \e{then} I start connecting it up to the return
4330 value of \cw{new_game_desc()}, populating other structures like
4331 \c{game_params}, and generally writing the rest of the source file.
4333 There are many ways to generate a puzzle which is known to be
4334 soluble. In this section I list all the methods I currently know of,
4335 in case any of them can be applied to your puzzle. (Not all of these
4336 methods will work, or in some cases even make sense, for all
4339 Some puzzles are mathematically tractable, meaning you can work out
4340 in advance which instances are soluble. Sixteen, for example, has a
4341 parity constraint in some settings which renders exactly half the
4342 game space unreachable, but it can be mathematically proved that any
4343 position not in that half \e{is} reachable. Therefore, Sixteen's
4344 grid generation simply consists of selecting at random from a well
4345 defined subset of the game space. Cube in its default state is even
4346 easier: \e{every} possible arrangement of the blue squares and the
4347 cube's starting position is soluble!
4349 Another option is to redefine what you mean by \q{soluble}. Black
4350 Box takes this approach. There are layouts of balls in the box which
4351 are completely indistinguishable from one another no matter how many
4352 beams you fire into the box from which angles, which would normally
4353 be grounds for declaring those layouts unfair; but fortunately,
4354 detecting that indistinguishability is computationally easy. So
4355 Black Box doesn't demand that your ball placements match its own; it
4356 merely demands that your ball placements be \e{indistinguishable}
4357 from the ones it was thinking of. If you have an ambiguous puzzle,
4358 then any of the possible answers is considered to be a solution.
4359 Having redefined the rules in that way, any puzzle is soluble again.
4361 Those are the simple techniques. If they don't work, you have to get
4364 One way to generate a soluble puzzle is to start from the solved
4365 state and make inverse moves until you reach a starting state. Then
4366 you know there's a solution, because you can just list the inverse
4367 moves you made and make them in the opposite order to return to the
4370 This method can be simple and effective for puzzles where you get to
4371 decide what's a starting state and what's not. In Pegs, for example,
4372 the generator begins with one peg in the centre of the board and
4373 makes inverse moves until it gets bored; in this puzzle, valid
4374 inverse moves are easy to detect, and \e{any} state that's reachable
4375 from the solved state by inverse moves is a reasonable starting
4376 position. So Pegs just continues making inverse moves until the
4377 board satisfies some criteria about extent and density, and then
4378 stops and declares itself done.
4380 For other puzzles, it can be a lot more difficult. Same Game uses
4381 this strategy too, and it's lucky to get away with it at all: valid
4382 inverse moves aren't easy to find (because although it's easy to
4383 insert additional squares in a Same Game position, it's difficult to
4384 arrange that \e{after} the insertion they aren't adjacent to any
4385 other squares of the same colour), so you're constantly at risk of
4386 running out of options and having to backtrack or start again. Also,
4387 Same Game grids never start off half-empty, which means you can't
4388 just stop when you run out of moves \dash you have to find a way to
4389 fill the grid up \e{completely}.
4391 The other way to generate a puzzle that's soluble is to start from
4392 the other end, and actually write a \e{solver}. This tends to ensure
4393 that a puzzle has a \e{unique} solution over and above having a
4394 solution at all, so it's a good technique to apply to puzzles for
4395 which that's important.
4397 One theoretical drawback of generating soluble puzzles by using a
4398 solver is that your puzzles are restricted in difficulty to those
4399 which the solver can handle. (Most solvers are not fully general:
4400 many sets of puzzle rules are NP-complete or otherwise nasty, so
4401 most solvers can only handle a subset of the theoretically soluble
4402 puzzles.) It's been my experience in practice, however, that this
4403 usually isn't a problem; computers are good at very different things
4404 from humans, and what the computer thinks is nice and easy might
4405 still be pleasantly challenging for a human. For example, when
4406 solving Dominosa puzzles I frequently find myself using a variety of
4407 reasoning techniques that my solver doesn't know about; in
4408 principle, therefore, I should be able to solve the puzzle using
4409 only those techniques it \e{does} know about, but this would involve
4410 repeatedly searching the entire grid for the one simple deduction I
4411 can make. Computers are good at this sort of exhaustive search, but
4412 it's been my experience that human solvers prefer to do more complex
4413 deductions than to spend ages searching for simple ones. So in many
4414 cases I don't find my own playing experience to be limited by the
4415 restrictions on the solver.
4417 (This isn't \e{always} the case. Solo is a counter-example;
4418 generating Solo puzzles using a simple solver does lead to
4419 qualitatively easier puzzles. Therefore I had to make the Solo
4420 solver rather more advanced than most of them.)
4422 There are several different ways to apply a solver to the problem of
4423 generating a soluble puzzle. I list a few of them below.
4425 The simplest approach is brute force: randomly generate a puzzle,
4426 use the solver to see if it's soluble, and if not, throw it away and
4427 try again until you get lucky. This is often a viable technique if
4428 all else fails, but it tends not to scale well: for many puzzle
4429 types, the probability of finding a uniquely soluble instance
4430 decreases sharply as puzzle size goes up, so this technique might
4431 work reasonably fast for small puzzles but take (almost) forever at
4432 larger sizes. Still, if there's no other alternative it can be
4433 usable: Pattern and Dominosa both use this technique. (However,
4434 Dominosa has a means of tweaking the randomly generated grids to
4435 increase the \e{probability} of them being soluble, by ruling out
4436 one of the most common ambiguous cases. This improved generation
4437 speed by over a factor of 10 on the highest preset!)
4439 An approach which can be more scalable involves generating a grid
4440 and then tweaking it to make it soluble. This is the technique used
4441 by Mines and also by Net: first a random puzzle is generated, and
4442 then the solver is run to see how far it gets. Sometimes the solver
4443 will get stuck; when that happens, examine the area it's having
4444 trouble with, and make a small random change in that area to allow
4445 it to make more progress. Continue solving (possibly even without
4446 restarting the solver), tweaking as necessary, until the solver
4447 finishes. Then restart the solver from the beginning to ensure that
4448 the tweaks haven't caused new problems in the process of solving old
4449 ones (which can sometimes happen).
4451 This strategy works well in situations where the usual solver
4452 failure mode is to get stuck in an easily localised spot. Thus it
4453 works well for Net and Mines, whose most common failure mode tends
4454 to be that most of the grid is fine but there are a few widely
4455 separated ambiguous sections; but it would work less well for
4456 Dominosa, in which the way you get stuck is to have scoured the
4457 whole grid and not found anything you can deduce \e{anywhere}. Also,
4458 it relies on there being a low probability that tweaking the grid
4459 introduces a new problem at the same time as solving the old one;
4460 Mines and Net also have the property that most of their deductions
4461 are local, so that it's very unlikely for a tweak to affect
4462 something half way across the grid from the location where it was
4463 applied. In Dominosa, by contrast, a lot of deductions use
4464 information about half the grid (\q{out of all the sixes, only one
4465 is next to a three}, which can depend on the values of up to 32 of
4466 the 56 squares in the default setting!), so this tweaking strategy
4467 would be rather less likely to work well.
4469 A more specialised strategy is that used in Solo and Slant. These
4470 puzzles have the property that they derive their difficulty from not
4471 presenting all the available clues. (In Solo's case, if all the
4472 possible clues were provided then the puzzle would already be
4473 solved; in Slant it would still require user action to fill in the
4474 lines, but it would present no challenge at all). Therefore, a
4475 simple generation technique is to leave the decision of which clues
4476 to provide until the last minute. In other words, first generate a
4477 random \e{filled} grid with all possible clues present, and then
4478 gradually remove clues for as long as the solver reports that it's
4479 still soluble. Unlike the methods described above, this technique
4480 \e{cannot} fail \dash once you've got a filled grid, nothing can
4481 stop you from being able to convert it into a viable puzzle.
4482 However, it wouldn't even be meaningful to apply this technique to
4483 (say) Pattern, in which clues can never be left out, so the only way
4484 to affect the set of clues is by altering the solution.
4486 (Unfortunately, Solo is complicated by the need to provide puzzles
4487 at varying difficulty levels. It's easy enough to generate a puzzle
4488 of \e{at most} a given level of difficulty; you just have a solver
4489 with configurable intelligence, and you set it to a given level and
4490 apply the above technique, thus guaranteeing that the resulting grid
4491 is solvable by someone with at most that much intelligence. However,
4492 generating a puzzle of \e{at least} a given level of difficulty is
4493 rather harder; if you go for \e{at most} Intermediate level, you're
4494 likely to find that you've accidentally generated a Trivial grid a
4495 lot of the time, because removing just one number is sufficient to
4496 take the puzzle from Trivial straight to Ambiguous. In that
4497 situation Solo has no remaining options but to throw the puzzle away
4500 A final strategy is to use the solver \e{during} puzzle
4501 construction: lay out a bit of the grid, run the solver to see what
4502 it allows you to deduce, and then lay out a bit more to allow the
4503 solver to make more progress. There are articles on the web that
4504 recommend constructing Sudoku puzzles by this method (which is
4505 completely the opposite way round to how Solo does it); for Sudoku
4506 it has the advantage that you get to specify your clue squares in
4507 advance (so you can have them make pretty patterns).
4509 Rectangles uses a strategy along these lines. First it generates a
4510 grid by placing the actual rectangles; then it has to decide where
4511 in each rectangle to place a number. It uses a solver to help it
4512 place the numbers in such a way as to ensure a unique solution. It
4513 does this by means of running a test solver, but it runs the solver
4514 \e{before} it's placed any of the numbers \dash which means the
4515 solver must be capable of coping with uncertainty about exactly
4516 where the numbers are! It runs the solver as far as it can until it
4517 gets stuck; then it narrows down the possible positions of a number
4518 in order to allow the solver to make more progress, and so on. Most
4519 of the time this process terminates with the grid fully solved, at
4520 which point any remaining number-placement decisions can be made at
4521 random from the options not so far ruled out. Note that unlike the
4522 Net/Mines tweaking strategy described above, this algorithm does not
4523 require a checking run after it completes: if it finishes
4524 successfully at all, then it has definitely produced a uniquely
4527 Most of the strategies described above are not 100% reliable. Each
4528 one has a failure rate: every so often it has to throw out the whole
4529 grid and generate a fresh one from scratch. (Solo's strategy would
4530 be the exception, if it weren't for the need to provide configurable
4531 difficulty levels.) Occasional failures are not a fundamental
4532 problem in this sort of work, however: it's just a question of
4533 dividing the grid generation time by the success rate (if it takes
4534 10ms to generate a candidate grid and 1/5 of them work, then it will
4535 take 50ms on average to generate a viable one), and seeing whether
4536 the expected time taken to \e{successfully} generate a puzzle is
4537 unacceptably slow. Dominosa's generator has a very low success rate
4538 (about 1 out of 20 candidate grids turn out to be usable, and if you
4539 think \e{that's} bad then go and look at the source code and find
4540 the comment showing what the figures were before the generation-time
4541 tweaks!), but the generator itself is very fast so this doesn't
4542 matter. Rectangles has a slower generator, but fails well under 50%
4545 So don't be discouraged if you have an algorithm that doesn't always
4546 work: if it \e{nearly} always works, that's probably good enough.
4547 The one place where reliability is important is that your algorithm
4548 must never produce false positives: it must not claim a puzzle is
4549 soluble when it isn't. It can produce false negatives (failing to
4550 notice that a puzzle is soluble), and it can fail to generate a
4551 puzzle at all, provided it doesn't do either so often as to become
4554 One last piece of advice: for grid-based puzzles, when writing and
4555 testing your generation algorithm, it's almost always a good idea
4556 \e{not} to test it initially on a grid that's square (i.e.
4557 \cw{w==h}), because if the grid is square then you won't notice if
4558 you mistakenly write \c{h} instead of \c{w} (or vice versa)
4559 somewhere in the code. Use a rectangular grid for testing, and any
4560 size of grid will be likely to work after that.
4562 \S{writing-textformats} Designing textual description formats
4564 Another aspect of writing a puzzle which is worth putting some
4565 thought into is the design of the various text description formats:
4566 the format of the game parameter encoding, the game description
4567 encoding, and the move encoding.
4569 The first two of these should be reasonably intuitive for a user to
4570 type in; so provide some flexibility where possible. Suppose, for
4571 example, your parameter format consists of two numbers separated by
4572 an \c{x} to specify the grid dimensions (\c{10x10} or \c{20x15}),
4573 and then has some suffixes to specify other aspects of the game
4574 type. It's almost always a good idea in this situation to arrange
4575 that \cw{decode_params()} can handle the suffixes appearing in any
4576 order, even if \cw{encode_params()} only ever generates them in one
4579 These formats will also be expected to be reasonably stable: users
4580 will expect to be able to exchange game IDs with other users who
4581 aren't running exactly the same version of your game. So make them
4582 robust and stable: don't build too many assumptions into the game ID
4583 format which will have to be changed every time something subtle
4584 changes in the puzzle code.
4586 \H{writing-howto} Common how-to questions
4588 This section lists some common things people want to do when writing
4589 a puzzle, and describes how to achieve them within the Puzzles
4592 \S{writing-howto-cursor} Drawing objects at only one position
4594 A common phenomenon is to have an object described in the
4595 \c{game_state} or the \c{game_ui} which can only be at one position.
4596 A cursor \dash probably specified in the \c{game_ui} \dash is a good
4599 In the \c{game_ui}, it would \e{obviously} be silly to have an array
4600 covering the whole game grid with a boolean flag stating whether the
4601 cursor was at each position. Doing that would waste space, would
4602 make it difficult to find the cursor in order to do anything with
4603 it, and would introduce the potential for synchronisation bugs in
4604 which you ended up with two cursors or none. The obviously sensible
4605 way to store a cursor in the \c{game_ui} is to have fields directly
4606 encoding the cursor's coordinates.
4608 However, it is a mistake to assume that the same logic applies to
4609 the \c{game_drawstate}. If you replicate the cursor position fields
4610 in the draw state, the redraw code will get very complicated. In the
4611 draw state, in fact, it \e{is} probably the right thing to have a
4612 cursor flag for every position in the grid. You probably have an
4613 array for the whole grid in the drawstate already (stating what is
4614 currently displayed in the window at each position); the sensible
4615 approach is to add a \q{cursor} flag to each element of that array.
4616 Then the main redraw loop will look something like this
4619 \c for (y = 0; y < h; y++) {
4620 \c for (x = 0; x < w; x++) {
4621 \c int value = state->symbol_at_position[y][x];
4622 \c if (x == ui->cursor_x && y == ui->cursor_y)
4624 \c if (ds->symbol_at_position[y][x] != value) {
4625 \c symbol_drawing_subroutine(dr, ds, x, y, value);
4626 \c ds->symbol_at_position[y][x] = value;
4631 This loop is very simple, pretty hard to get wrong, and
4632 \e{automatically} deals both with erasing the previous cursor and
4633 drawing the new one, with no special case code required.
4635 This type of loop is generally a sensible way to write a redraw
4636 function, in fact. The best thing is to ensure that the information
4637 stored in the draw state for each position tells you \e{everything}
4638 about what was drawn there. A good way to ensure that is to pass
4639 precisely the same information, and \e{only} that information, to a
4640 subroutine that does the actual drawing; then you know there's no
4641 additional information which affects the drawing but which you don't
4644 \S{writing-keyboard-cursor} Implementing a keyboard-controlled cursor
4646 It is often useful to provide a keyboard control method in a
4647 basically mouse-controlled game. A keyboard-controlled cursor is
4648 best implemented by storing its location in the \c{game_ui} (since
4649 if it were in the \c{game_state} then the user would have to
4650 separately undo every cursor move operation). So the procedure would
4653 \b Put cursor position fields in the \c{game_ui}.
4655 \b \cw{interpret_move()} responds to arrow keys by modifying the
4656 cursor position fields and returning \cw{""}.
4658 \b \cw{interpret_move()} responds to some sort of fire button by
4659 actually performing a move based on the current cursor location.
4661 \b You might want an additional \c{game_ui} field stating whether
4662 the cursor is currently visible, and having it disappear when a
4663 mouse action occurs (so that it doesn't clutter the display when not
4666 \b You might also want to automatically hide the cursor in
4667 \cw{changed_state()} when the current game state changes to one in
4668 which there is no move to make (which is the case in some types of
4671 \b \cw{redraw()} draws the cursor using the technique described in
4672 \k{writing-howto-cursor}.
4674 \S{writing-howto-dragging} Implementing draggable sprites
4676 Some games have a user interface which involves dragging some sort
4677 of game element around using the mouse. If you need to show a
4678 graphic moving smoothly over the top of other graphics, use a
4679 blitter (see \k{drawing-blitter} for the blitter API) to save the
4680 background underneath it. The typical scenario goes:
4682 \b Have a blitter field in the \c{game_drawstate}.
4684 \b Set the blitter field to \cw{NULL} in the game's
4685 \cw{new_drawstate()} function, since you don't yet know how big the
4686 piece of saved background needs to be.
4688 \b In the game's \cw{set_size()} function, once you know the size of
4689 the object you'll be dragging around the display and hence the
4690 required size of the blitter, actually allocate the blitter.
4692 \b In \cw{free_drawstate()}, free the blitter if it's not \cw{NULL}.
4694 \b In \cw{interpret_move()}, respond to mouse-down and mouse-drag
4695 events by updating some fields in the \cw{game_ui} which indicate
4696 that a drag is in progress.
4698 \b At the \e{very end} of \cw{redraw()}, after all other drawing has
4699 been done, draw the moving object if there is one. First save the
4700 background under the object in the blitter; then set a clip
4701 rectangle covering precisely the area you just saved (just in case
4702 anti-aliasing or some other error causes your drawing to go beyond
4703 the area you saved). Then draw the object, and call \cw{unclip()}.
4704 Finally, set a flag in the \cw{game_drawstate} that indicates that
4705 the blitter needs restoring.
4707 \b At the very start of \cw{redraw()}, before doing anything else at
4708 all, check the flag in the \cw{game_drawstate}, and if it says the
4709 blitter needs restoring then restore it. (Then clear the flag, so
4710 that this won't happen again in the next redraw if no moving object
4711 is drawn this time.)
4713 This way, you will be able to write the rest of the redraw function
4714 completely ignoring the dragged object, as if it were floating above
4715 your bitmap and being completely separate.
4717 \S{writing-ref-counting} Sharing large invariant data between all
4720 In some puzzles, there is a large amount of data which never changes
4721 between game states. The array of numbers in Dominosa is a good
4724 You \e{could} dynamically allocate a copy of that array in every
4725 \c{game_state}, and have \cw{dup_game()} make a fresh copy of it for
4726 every new \c{game_state}; but it would waste memory and time. A
4727 more efficient way is to use a reference-counted structure.
4729 \b Define a structure type containing the data in question, and also
4730 containing an integer reference count.
4732 \b Have a field in \c{game_state} which is a pointer to this
4735 \b In \cw{new_game()}, when creating a fresh game state at the start
4736 of a new game, create an instance of this structure, initialise it
4737 with the invariant data, and set its reference count to 1.
4739 \b In \cw{dup_game()}, rather than making a copy of the structure
4740 for the new game state, simply set the new game state to point at
4741 the same copy of the structure, and increment its reference count.
4743 \b In \cw{free_game()}, decrement the reference count in the
4744 structure pointed to by the game state; if the count reaches zero,
4747 This way, the invariant data will persist for only as long as it's
4748 genuinely needed; \e{as soon} as the last game state for a
4749 particular puzzle instance is freed, the invariant data for that
4750 puzzle will vanish as well. Reference counting is a very efficient
4751 form of garbage collection, when it works at all. (Which it does in
4752 this instance, of course, because there's no possibility of circular
4755 \S{writing-flash-types} Implementing multiple types of flash
4757 In some games you need to flash in more than one different way.
4758 Mines, for example, flashes white when you win, and flashes red when
4759 you tread on a mine and die.
4761 The simple way to do this is:
4763 \b Have a field in the \c{game_ui} which describes the type of flash.
4765 \b In \cw{flash_length()}, examine the old and new game states to
4766 decide whether a flash is required and what type. Write the type of
4767 flash to the \c{game_ui} field whenever you return non-zero.
4769 \b In \cw{redraw()}, when you detect that \c{flash_time} is
4770 non-zero, examine the field in \c{game_ui} to decide which type of
4773 \cw{redraw()} will never be called with \c{flash_time} non-zero
4774 unless \cw{flash_length()} was first called to tell the mid-end that
4775 a flash was required; so whenever \cw{redraw()} notices that
4776 \c{flash_time} is non-zero, you can be sure that the field in
4777 \c{game_ui} is correctly set.
4779 \S{writing-move-anim} Animating game moves
4781 A number of puzzle types benefit from a quick animation of each move
4784 For some games, such as Fifteen, this is particularly easy. Whenever
4785 \cw{redraw()} is called with \c{oldstate} non-\cw{NULL}, Fifteen
4786 simply compares the position of each tile in the two game states,
4787 and if the tile is not in the same place then it draws it some
4788 fraction of the way from its old position to its new position. This
4789 method copes automatically with undo.
4791 Other games are less obvious. In Sixteen, for example, you can't
4792 just draw each tile a fraction of the way from its old to its new
4793 position: if you did that, the end tile would zip very rapidly past
4794 all the others to get to the other end and that would look silly.
4795 (Worse, it would look inconsistent if the end tile was drawn on top
4796 going one way and on the bottom going the other way.)
4798 A useful trick here is to define a field or two in the game state
4799 that indicates what the last move was.
4801 \b Add a \q{last move} field to the \c{game_state} (or two or more
4802 fields if the move is complex enough to need them).
4804 \b \cw{new_game()} initialises this field to a null value for a new
4807 \b \cw{execute_move()} sets up the field to reflect the move it just
4810 \b \cw{redraw()} now needs to examine its \c{dir} parameter. If
4811 \c{dir} is positive, it determines the move being animated by
4812 looking at the last-move field in \c{newstate}; but if \c{dir} is
4813 negative, it has to look at the last-move field in \c{oldstate}, and
4814 invert whatever move it finds there.
4816 Note also that Sixteen needs to store the \e{direction} of the move,
4817 because you can't quite determine it by examining the row or column
4818 in question. You can in almost all cases, but when the row is
4819 precisely two squares long it doesn't work since a move in either
4820 direction looks the same. (You could argue that since moving a
4821 2-element row left and right has the same effect, it doesn't matter
4822 which one you animate; but in fact it's very disorienting to click
4823 the arrow left and find the row moving right, and almost as bad to
4824 undo a move to the right and find the game animating \e{another}
4827 \S{writing-conditional-anim} Animating drag operations
4829 In Untangle, moves are made by dragging a node from an old position
4830 to a new position. Therefore, at the time when the move is initially
4831 made, it should not be animated, because the node has already been
4832 dragged to the right place and doesn't need moving there. However,
4833 it's nice to animate the same move if it's later undone or redone.
4834 This requires a bit of fiddling.
4836 The obvious approach is to have a flag in the \c{game_ui} which
4837 inhibits move animation, and to set that flag in
4838 \cw{interpret_move()}. The question is, when would the flag be reset
4839 again? The obvious place to do so is \cw{changed_state()}, which
4840 will be called once per move. But it will be called \e{before}
4841 \cw{anim_length()}, so if it resets the flag then \cw{anim_length()}
4842 will never see the flag set at all.
4844 The solution is to have \e{two} flags in a queue.
4846 \b Define two flags in \c{game_ui}; let's call them \q{current} and
4849 \b Set both to \cw{FALSE} in \c{new_ui()}.
4851 \b When a drag operation completes in \cw{interpret_move()}, set the
4852 \q{next} flag to \cw{TRUE}.
4854 \b Every time \cw{changed_state()} is called, set the value of
4855 \q{current} to the value in \q{next}, and then set the value of
4856 \q{next} to \cw{FALSE}.
4858 \b That way, \q{current} will be \cw{TRUE} \e{after} a call to
4859 \cw{changed_state()} if and only if that call to
4860 \cw{changed_state()} was the result of a drag operation processed by
4861 \cw{interpret_move()}. Any other call to \cw{changed_state()}, due
4862 to an Undo or a Redo or a Restart or a Solve, will leave \q{current}
4865 \b So now \cw{anim_length()} can request a move animation if and
4866 only if the \q{current} flag is \e{not} set.
4868 \S{writing-cheating} Inhibiting the victory flash when Solve is used
4870 Many games flash when you complete them, as a visual congratulation
4871 for having got to the end of the puzzle. It often seems like a good
4872 idea to disable that flash when the puzzle is brought to a solved
4873 state by means of the Solve operation.
4875 This is easily done:
4877 \b Add a \q{cheated} flag to the \c{game_state}.
4879 \b Set this flag to \cw{FALSE} in \cw{new_game()}.
4881 \b Have \cw{solve()} return a move description string which clearly
4882 identifies the move as a solve operation.
4884 \b Have \cw{execute_move()} respond to that clear identification by
4885 setting the \q{cheated} flag in the returned \c{game_state}. The
4886 flag will then be propagated to all subsequent game states, even if
4887 the user continues fiddling with the game after it is solved.
4889 \b \cw{flash_length()} now returns non-zero if \c{oldstate} is not
4890 completed and \c{newstate} is, \e{and} neither state has the
4891 \q{cheated} flag set.
4893 \H{writing-testing} Things to test once your puzzle is written
4895 Puzzle implementations written in this framework are self-testing as
4896 far as I could make them.
4898 Textual game and move descriptions, for example, are generated and
4899 parsed as part of the normal process of play. Therefore, if you can
4900 make moves in the game \e{at all} you can be reasonably confident
4901 that the mid-end serialisation interface will function correctly and
4902 you will be able to save your game. (By contrast, if I'd stuck with
4903 a single \cw{make_move()} function performing the jobs of both
4904 \cw{interpret_move()} and \cw{execute_move()}, and had separate
4905 functions to encode and decode a game state in string form, then
4906 those functions would not be used during normal play; so they could
4907 have been completely broken, and you'd never know it until you tried
4908 to save the game \dash which would have meant you'd have to test
4909 game saving \e{extensively} and make sure to test every possible
4910 type of game state. As an added bonus, doing it the way I did leads
4911 to smaller save files.)
4913 There is one exception to this, which is the string encoding of the
4914 \c{game_ui}. Most games do not store anything permanent in the
4915 \c{game_ui}, and hence do not need to put anything in its encode and
4916 decode functions; but if there is anything in there, you do need to
4917 test game loading and saving to ensure those functions work
4920 It's also worth testing undo and redo of all operations, to ensure
4921 that the redraw and the animations (if any) work properly. Failing
4922 to animate undo properly seems to be a common error.
4924 Other than that, just use your common sense.
4926 \versionid Simon Tatham's Portable Puzzle Collection, version 20161228.7cae89f