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 r6140. 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, there will be a section about how to design new games, with
174 some 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} which contains a complete list of those game structures.
198 On the latter type of platform, source files may assume that the
199 preprocessor symbol \c{COMBINED} has been defined. Thus, the usual
200 code to declare the game structure looks something like this:
203 \c #define thegame net /* or whatever this game is called */
204 \e iii iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
207 \c const struct game thegame = {
208 \c /* lots of structure initialisation in here */
209 \e iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
212 Game back ends must also internally define a number of data
213 structures, for storing their various persistent state. This chapter
214 will first discuss the nature and use of those structures, and then
215 go on to give details of every element of the game structure.
217 \H{backend-structs} Data structures
219 Each game is required to define four separate data structures. This
220 section discusses each one and suggests what sorts of things need to
223 \S{backend-game-params} \c{game_params}
225 The \c{game_params} structure contains anything which affects the
226 automatic generation of new puzzles. So if puzzle generation is
227 parametrised in any way, those parameters need to be stored in
230 Most puzzles currently in this collection are played on a grid of
231 squares, meaning that the most obvious parameter is the grid size.
232 Many puzzles have additional parameters; for example, Mines allows
233 you to control the number of mines in the grid independently of its
234 size, Net can be wrapping or non-wrapping, Solo has difficulty
235 levels and symmetry settings, and so on.
237 A simple rule for deciding whether a data item needs to go in
238 \c{game_params} is: would the user expect to be able to control this
239 data item from either the preset-game-types menu or the \q{Custom}
240 game type configuration? If so, it's part of \c{game_params}.
242 \c{game_params} structures are permitted to contain pointers to
243 subsidiary data if they need to. The back end is required to provide
244 functions to create and destroy \c{game_params}, and those functions
245 can allocate and free additional memory if necessary. (It has not
246 yet been necessary to do this in any puzzle so far, but the
247 capability is there just in case.)
249 \c{game_params} is also the only structure which the game's
250 \cw{compute_size()} function may refer to; this means that any
251 aspect of the game which affects the size of the window it needs to
252 be drawn in must be stored in \c{game_params}. In particular, this
253 imposes the fundamental limitation that random game generation may
254 not have a random effect on the window size: game generation
255 algorithms are constrained to work by starting from the grid size
256 rather than generating it as an emergent phenomenon. (Although this
257 is a restriction in theory, it has not yet seemed to be a problem.)
259 \S{backend-game-state} \c{game_state}
261 While the user is actually playing a puzzle, the \c{game_state}
262 structure stores all the data corresponding to the current state of
265 The mid-end keeps \c{game_state}s in a list, and adds to the list
266 every time the player makes a move; the Undo and Redo functions step
267 back and forth through that list.
269 Therefore, a good means of deciding whether a data item needs to go
270 in \c{game_state} is: would a player expect that data item to be
271 restored on undo? If so, put it in \c{game_state}, and this will
272 automatically happen without you having to lift a finger. If not
273 \dash for example, the deaths counter in Mines is precisely
274 something that does \e{not} want to be reset to its previous state
275 on an undo \dash then you might have found a data item that needs to
276 go in \c{game_ui} instead.
278 During play, \c{game_state}s are often passed around without an
279 accompanying \c{game_params} structure. Therefore, any information
280 in \c{game_params} which is important during play (such as the grid
281 size) must be duplicated within the \c{game_state}. One simple
282 method of doing this is to have the \c{game_state} structure
283 \e{contain} a \c{game_params} structure as one of its members,
284 although this isn't obligatory if you prefer to do it another way.
286 \S{backend-game-drawstate} \c{game_drawstate}
288 \c{game_drawstate} carries persistent state relating to the current
289 graphical contents of the puzzle window. The same \c{game_drawstate}
290 is passed to every call to the game redraw function, so that it can
291 remember what it has already drawn and what needs redrawing.
293 A typical use for a \c{game_drawstate} is to have an array mirroring
294 the array of grid squares in the \c{game_state}; then every time the
295 redraw function was passed a \c{game_state}, it would loop over all
296 the squares, and physically redraw any whose description in the
297 \c{game_state} (i.e. what the square needs to look like when the
298 redraw is completed) did not match its description in the
299 \c{game_drawstate} (i.e. what the square currently looks like).
301 \c{game_drawstate} is occasionally completely torn down and
302 reconstructed by the mid-end, if the user somehow forces a full
303 redraw. Therefore, no data should be stored in \c{game_drawstate}
304 which is \e{not} related to the state of the puzzle window, because
305 it might be unexpectedly destroyed.
307 The back end provides functions to create and destroy
308 \c{game_drawstate}, which means it can contain pointers to
309 subsidiary allocated data if it needs to. A common thing to want to
310 allocate in a \c{game_drawstate} is a \c{blitter}; see
311 \k{drawing-blitter} for more on this subject.
313 \S{backend-game-ui} \c{game_ui}
315 \c{game_ui} contains whatever doesn't fit into the above three
318 A new \c{game_ui} is created when the user begins playing a new
319 instance of a puzzle (i.e. during \q{New Game} or after entering a
320 game ID etc). It persists until the user finishes playing that game
321 and begins another one (or closes the window); in particular,
322 \q{Restart Game} does \e{not} destroy the \c{game_ui}.
324 \c{game_ui} is useful for implementing user-interface state which is
325 not part of \c{game_state}. Common examples are keyboard control
326 (you wouldn't want to have to separately Undo through every cursor
327 motion) and mouse dragging. See \k{writing-keyboard-cursor} and
328 \k{writing-howto-dragging}, respectively, for more details.
330 Another use for \c{game_ui} is to store highly persistent data such
331 as the Mines death counter. This is conceptually rather different:
332 where the Net cursor position was \e{not important enough} to
333 preserve for the player to restore by Undo, the Mines death counter
334 is \e{too important} to permit the player to revert by Undo!
336 A final use for \c{game_ui} is to pass information to the redraw
337 function about recent changes to the game state. This is used in
338 Mines, for example, to indicate whether a requested \q{flash} should
339 be a white flash for victory or a red flash for defeat; see
340 \k{writing-flash-types}.
342 \H{backend-simple} Simple data in the back end
344 In this section I begin to discuss each individual element in the
345 back end structure. To begin with, here are some simple
346 self-contained data elements.
348 \S{backend-name} \c{name}
352 This is a simple ASCII string giving the name of the puzzle. This
353 name will be used in window titles, in game selection menus on
354 monolithic platforms, and anywhere else that the front end needs to
355 know the name of a game.
357 \S{backend-winhelp} \c{winhelp_topic}
359 \c const char *winhelp_topic;
361 This member is used on Windows only, to provide online help.
362 Although the Windows front end provides a separate binary for each
363 puzzle, it has a single monolithic help file; so when a user selects
364 \q{Help} from the menu, the program needs to open the help file and
365 jump to the chapter describing that particular puzzle.
367 Therefore, each chapter in \c{puzzles.but} is labelled with a
368 \e{help topic} name, similar to this:
370 \c \cfg{winhelp-topic}{games.net}
372 And then the corresponding game back end encodes the topic string
373 (here \cq{games.net}) in the \c{winhelp_topic} element of the game
376 \H{backend-params} Handling game parameter sets
378 In this section I present the various functions which handle the
379 \c{game_params} structure.
381 \S{backend-default-params} \cw{default_params()}
383 \c game_params *(*default_params)(void);
385 This function allocates a new \c{game_params} structure, fills it
386 with the default values, and returns a pointer to it.
388 \S{backend-fetch-preset} \cw{fetch_preset()}
390 \c int (*fetch_preset)(int i, char **name, game_params **params);
392 This function is used to populate the \q{Type} menu, which provides
393 a list of conveniently accessible preset parameters for most games.
395 The function is called with \c{i} equal to the index of the preset
396 required (numbering from zero). It returns \cw{FALSE} if that preset
397 does not exist (if \c{i} is less than zero or greater than the
398 largest preset index). Otherwise, it sets \c{*params} to point at a
399 newly allocated \c{game_params} structure containing the preset
400 information, sets \c{*name} to point at a newly allocated C string
401 containing the preset title (to go on the \q{Type} menu), and
404 If the game does not wish to support any presets at all, this
405 function is permitted to return \cw{FALSE} always.
407 \S{backend-encode-params} \cw{encode_params()}
409 \c char *(*encode_params)(game_params *params, int full);
411 The job of this function is to take a \c{game_params}, and encode it
412 in a string form for use in game IDs. The return value must be a
413 newly allocated C string, and \e{must} not contain a colon or a hash
414 (since those characters are used to mark the end of the parameter
415 section in a game ID).
417 Ideally, it should also not contain any other potentially
418 controversial punctuation; bear in mind when designing a string
419 parameter format that it will probably be used on both Windows and
420 Unix command lines under a variety of exciting shell quoting and
421 metacharacter rules. Sticking entirely to alphanumerics is the
422 safest thing; if you really need punctuation, you can probably get
423 away with commas, periods or underscores without causing anybody any
424 major inconvenience. If you venture far beyond that, you're likely
425 to irritate \e{somebody}.
427 (At the time of writing this, all existing games have purely
428 alphanumeric string parameter formats. Usually these involve a
429 letter denoting a parameter, followed optionally by a number giving
430 the value of that parameter, with a few mandatory parts at the
431 beginning such as numeric width and height separated by \cq{x}.)
433 If the \c{full} parameter is \cw{TRUE}, this function should encode
434 absolutely everything in the \c{game_params}, such that a subsequent
435 call to \cw{decode_params()} (\k{backend-decode-params}) will yield
436 an identical structure. If \c{full} is \cw{FALSE}, however, you
437 should leave out anything which is not necessary to describe a
438 \e{specific puzzle instance}, i.e. anything which only takes effect
439 when a new puzzle is \e{generated}. For example, the Solo
440 \c{game_params} includes a difficulty rating used when constructing
441 new puzzles; but a Solo game ID need not explicitly include the
442 difficulty, since to describe a puzzle once generated it's
443 sufficient to give the grid dimensions and the location and contents
444 of the clue squares. (Indeed, one might very easily type in a puzzle
445 out of a newspaper without \e{knowing} what its difficulty level is
446 in Solo's terminology.) Therefore. Solo's \cw{encode_params()} only
447 encodes the difficulty level if \c{full} is set.
449 \S{backend-decode-params} \cw{decode_params()}
451 \c void (*decode_params)(game_params *params, char const *string);
453 This function is the inverse of \cw{encode_params()}
454 (\k{backend-encode-params}). It parses the supplied string and fills
455 in the supplied \c{game_params} structure. Note that the structure
456 will \e{already} have been allocated: this function is not expected
457 to create a \e{new} \c{game_params}, but to modify an existing one.
459 This function can receive a string which only encodes a subset of
460 the parameters. The most obvious way in which this can happen is if
461 the string was constructed by \cw{encode_params()} with its \c{full}
462 parameter set to \cw{FALSE}; however, it could also happen if the
463 user typed in a parameter set manually and missed something out. Be
464 prepared to deal with a wide range of possibilities.
466 When dealing with a parameter which is not specified in the input
467 string, what to do requires a judgment call on the part of the
468 programmer. Sometimes it makes sense to adjust other parameters to
469 bring them into line with the new ones. In Mines, for example, you
470 would probably not want to keep the same mine count if the user
471 dropped the grid size and didn't specify one, since you might easily
472 end up with more mines than would actually fit in the grid! On the
473 other hand, sometimes it makes sense to leave the parameter alone: a
474 Solo player might reasonably expect to be able to configure size and
475 difficulty independently of one another.
477 This function currently has no direct means of returning an error if
478 the string cannot be parsed at all. However, the returned
479 \c{game_params} is almost always subsequently passed to
480 \cw{validate_params()} (\k{backend-validate-params}), so if you
481 really want to signal parse errors, you could always have a \c{char
482 *} in your parameters structure which stored an error message, and
483 have \cw{validate_params()} return it if it is non-\cw{NULL}.
485 \S{backend-free-params} \cw{free_params()}
487 \c void (*free_params)(game_params *params);
489 This function frees a \c{game_params} structure, and any subsidiary
490 allocations contained within it.
492 \S{backend-dup-params} \cw{dup_params()}
494 \c game_params *(*dup_params)(game_params *params);
496 This function allocates a new \c{game_params} structure and
497 initialises it with an exact copy of the information in the one
498 provided as input. It returns a pointer to the new duplicate.
500 \S{backend-can-configure} \c{can_configure}
502 \c int can_configure;
504 This boolean data element is set to \cw{TRUE} if the back end
505 supports custom parameter configuration via a dialog box. If it is
506 \cw{TRUE}, then the functions \cw{configure()} and
507 \cw{custom_params()} are expected to work. See \k{backend-configure}
508 and \k{backend-custom-params} for more details.
510 \S{backend-configure} \cw{configure()}
512 \c config_item *(*configure)(game_params *params);
514 This function is called when the user requests a dialog box for
515 custom parameter configuration. It returns a newly allocated array
516 of \cw{config_item} structures, describing the GUI elements required
517 in the dialog box. The
519 The \cw{config_item} structure contains the following elements:
526 \c{name} is an ASCII string giving the textual label for a GUI
527 control. It is \e{not} expected to be dynamically allocated.
529 \c{type} contains one of a small number of \c{enum} values defining
530 what type of control is being described. The meaning of the \c{sval}
531 and \c{ival} fields depends on the value in \c{type}. The valid
536 \dd Describes a text input box. (This is also used for numeric
537 input. The back end does not bother informing the front end that the
538 box is numeric rather than textual; some front ends do have the
539 capacity to take this into account, but I decided it wasn't worth
540 the extra complexity in the interface.) For this type, \c{ival} is
541 unused, and \c{sval} contains a dynamically allocated string
542 representing the contents of the input box.
546 \dd Describes a simple checkbox. For this type, \c{sval} is unused,
547 and \c{ival} is \cw{TRUE} or \cw{FALSE}.
551 \dd Describes a drop-down list presenting one of a small number of
552 fixed choices. For this type, \c{sval} contains a list of strings
553 describing the choices; the very first character of \c{sval} is used
554 as a delimiter when processing the rest (so that the strings
555 \cq{:zero:one:two}, \cq{!zero!one!two} and \cq{xzeroxonextwo} all
556 define a three-element list containing \cq{zero}, \cq{one} and
557 \cq{two}). \c{ival} contains the index of the currently selected
558 element, numbering from zero (so that in the above example, 0 would
559 mean \cq{zero} and 2 would mean \cq{two}).
563 Note that for this control type, \c{sval} is \e{not} dynamically
564 allocated, whereas it was for \c{C_STRING}.
570 \dd Marks the end of the array of \c{config_item}s. All other fields
573 The array returned from this function is expected to have filled in
574 the initial values of all the controls according to the input
575 \c{game_params} structure.
577 If the game's \c{can_configure} flag is set to \cw{FALSE}, this
578 function is never called and need not do anything at all.
580 \S{backend-custom-params} \cw{custom_params()}
582 \c game_params *(*custom_params)(config_item *cfg);
584 This function is the counterpart to \cw{configure()}
585 (\k{backend-configure}). It receives as input an array of
586 \c{config_item}s which was originally created by \cw{configure()},
587 but in which the control values have since been changed in
588 accordance with user input. Its function is to read the new values
589 out of the controls and return a newly allocated \c{game_params}
590 structure representing the user's chosen parameter set.
592 (The front end will have modified the controls' \e{values}, but
593 there will still always be the same set of controls, in the same
594 order, as provided by \cw{configure()}. It is not necessary to check
595 the \c{name} and \c{type} fields, although you could use
596 \cw{assert()} if you were feeling energetic.)
598 This function is not expected to (and indeed \e{must not}) free the
599 input \c{config_item} array. (If the parameters fail to validate,
600 the dialog box will stay open.)
602 If the game's \c{can_configure} flag is set to \cw{FALSE}, this
603 function is never called and need not do anything at all.
605 \S{backend-validate-params} \cw{validate_params()}
607 \c char *(*validate_params)(game_params *params, int full);
609 This function takes a \c{game_params} structure as input, and checks
610 that the parameters described in it fall within sensible limits. (At
611 the very least, grid dimensions should almost certainly be strictly
612 positive, for example.)
614 Return value is \cw{NULL} if no problems were found, or
615 alternatively a (non-dynamically-allocated) ASCII string describing
616 the error in human-readable form.
618 If the \c{full} parameter is set, full validation should be
619 performed: any set of parameters which would not permit generation
620 of a sensible puzzle should be faulted. If \c{full} is \e{not} set,
621 the implication is that these parameters are not going to be used
622 for \e{generating} a puzzle; so parameters which can't even sensibly
623 \e{describe} a valid puzzle should still be faulted, but parameters
624 which only affect puzzle generation should not be.
626 (The \c{full} option makes a difference when parameter combinations
627 are non-orthogonal. For example, Net has a boolean option
628 controlling whether it enforces a unique solution; it turns out that
629 it's impossible to generate a uniquely soluble puzzle with wrapping
630 walls and width 2, so \cw{validate_params()} will complain if you
631 ask for one. However, if the user had just been playing a unique
632 wrapping puzzle of a more sensible width, and then pastes in a game
633 ID acquired from somebody else which happens to describe a
634 \e{non}-unique wrapping width-2 puzzle, then \cw{validate_params()}
635 will be passed a \c{game_params} containing the width and wrapping
636 settings from the new game ID and the uniqueness setting from the
637 old one. This would be faulted, if it weren't for the fact that
638 \c{full} is not set during this call, so Net ignores the
639 inconsistency. The resulting \c{game_params} is never subsequently
640 used to generate a puzzle; this is a promise made by the mid-end
641 when it asks for a non-full validation.)
643 \H{backend-descs} Handling game descriptions
645 In this section I present the functions that deal with a textual
646 description of a puzzle, i.e. the part that comes after the colon in
647 a descriptive-format game ID.
649 \S{backend-new-desc} \cw{new_desc()}
651 \c char *(*new_desc)(game_params *params, random_state *rs,
652 \c char **aux, int interactive);
654 This function is where all the really hard work gets done. This is
655 the function whose job is to randomly generate a new puzzle,
656 ensuring solubility and uniqueness as appropriate.
658 As input it is given a \c{game_params} structure and a random state
659 (see \k{utils-random} for the random number API). It must invent a
660 puzzle instance, encode it in string form, and return a dynamically
661 allocated C string containing that encoding.
663 Additionally, it may return a second dynamically allocated string in
664 \c{*aux}. (If it doesn't want to, then it can leave that parameter
665 completely alone; it isn't required to set it to \cw{NULL}, although
666 doing so is harmless.) That string, if present, will be passed to
667 \cw{solve()} (\k{backend-solve}) later on; so if the puzzle is
668 generated in such a way that a solution is known, then information
669 about that solution can be saved in \c{*aux} for \cw{solve()} to
672 The \c{interactive} parameter should be ignored by almost all
673 puzzles. Its purpose is to distinguish between generating a puzzle
674 within a GUI context for immediate play, and generating a puzzle in
675 a command-line context for saving to be played later. The only
676 puzzle that currently uses this distinction (and, I fervently hope,
677 the only one which will \e{ever} need to use it) is Mines, which
678 chooses a random first-click location when generating puzzles
679 non-interactively, but which waits for the user to place the first
680 click when interactive. If you think you have come up with another
681 puzzle which needs to make use of this parameter, please think for
682 at least ten minutes about whether there is \e{any} alternative!
684 Note that game description strings are not required to contain an
685 encoding of parameters such as grid size; a game description is
686 never separated from the \c{game_params} it was generated with, so
687 any information contained in that structure need not be encoded
688 again in the game description.
690 \S{backend-validate-desc} \cw{validate_desc()}
692 \c char *(*validate_desc)(game_params *params, char *desc);
694 This function is given a game description, and its job is to
695 validate that it describes a puzzle which makes sense.
697 To some extent it's up to the user exactly how far they take the
698 phrase \q{makes sense}; there are no particularly strict rules about
699 how hard the user is permitted to shoot themself in the foot when
700 typing in a bogus game description by hand. (For example, Rectangles
701 will not verify that the sum of all the numbers in the grid equals
702 the grid's area. So a user could enter a puzzle which was provably
703 not soluble, and the program wouldn't complain; there just wouldn't
704 happen to be any sequence of moves which solved it.)
706 The one non-negotiable criterion is that any game description which
707 makes it through \cw{validate_desc()} \e{must not} subsequently
708 cause a crash or an assertion failure when fed to \cw{new_game()}
709 and thence to the rest of the back end.
711 The return value is \cw{NULL} on success, or a
712 non-dynamically-allocated C string containing an error message.
714 \S{backend-new-game} \cw{new_game()}
716 \c game_state *(*new_game)(midend_data *me, game_params *params,
719 This function takes a game description as input, together with its
720 accompanying \c{game_params}, and constructs a \c{game_state}
721 describing the initial state of the puzzle. It returns a newly
722 allocated \c{game_state} structure.
724 Almost all puzzles should ignore the \c{me} parameter. It is
725 required by Mines, which needs it for later passing to
726 \cw{midend_supersede_game_desc()} (see \k{backend-supersede}) once
727 the user has placed the first click. I fervently hope that no other
728 puzzle will be awkward enough to require it, so everybody else
729 should ignore it. As with the \c{interactive} parameter in
730 \cw{new_desc()} (\k{backend-new-desc}), if you think you have a
731 reason to need this parameter, please try very hard to think of an
732 alternative approach!
734 \H{backend-states} Handling game states
736 This section describes the functions which create and destroy
737 \c{game_state} structures.
739 (Well, except \cw{new_game()}, which is in \k{backend-new-game}
740 instead of under here; but it deals with game descriptions \e{and}
741 game states and it had to go in one section or the other.)
743 \S{backend-dup-game} \cw{dup_game()}
745 \c game_state *(*dup_game)(game_state *state);
747 This function allocates a new \c{game_state} structure and
748 initialises it with an exact copy of the information in the one
749 provided as input. It returns a pointer to the new duplicate.
751 \S{backend-free-game} \cw{free_game()}
753 \c void (*free_game)(game_state *state);
755 This function frees a \c{game_state} structure, and any subsidiary
756 allocations contained within it.
758 \H{backend-ui} Handling \c{game_ui}
760 \S{backend-new-ui} \cw{new_ui()}
762 \c game_ui *(*new_ui)(game_state *state);
764 This function allocates and returns a new \c{game_ui} structure for
765 playing a particular puzzle. It is passed a pointer to the initial
766 \c{game_state}, in case it needs to refer to that when setting up
767 the initial values for the new game.
769 \S{backend-free-ui} \cw{free_ui()}
771 \c void (*free_ui)(game_ui *ui);
773 This function frees a \c{game_ui} structure, and any subsidiary
774 allocations contained within it.
776 \S{backend-encode-ui} \cw{encode_ui()}
778 \c char *(*encode_ui)(game_ui *ui);
780 This function encodes any \e{important} data in a \c{game_ui}
781 structure in string form. It is only called when saving a
782 half-finished game to a file.
784 It should be used sparingly. Almost all data in a \c{game_ui} is not
785 important enough to save. The location of the keyboard-controlled
786 cursor, for example, can be reset to a default position on reloading
787 the game without impacting the user experience. If the user should
788 somehow manage to save a game while a mouse drag was in progress,
789 then discarding that mouse drag would be an outright \e{feature},
791 A typical thing that \e{would} be worth encoding in this function is
792 the Mines death counter: it's in the \c{game_ui} rather than the
793 \c{game_state} because it's too important to allow the user to
794 revert it by using Undo, and therefore it's also too important to
795 allow the user to revert it by saving and reloading. (Of course, the
796 user could edit the save file by hand... But if the user is \e{that}
797 determined to cheat, they could just as easily modify the game's
800 \S{backend-decode-ui} \cw{decode_ui()}
802 \c void (*decode_ui)(game_ui *ui, char *encoding);
804 This function parses a string previously output by \cw{encode_ui()},
805 and writes the decoded data back into the provided \c{game_ui}
808 \S{backend-changed-state} \cw{changed_state()}
810 \c void (*changed_state)(game_ui *ui, game_state *oldstate,
811 \c game_state *newstate);
813 This function is called by the mid-end whenever the current game
814 state changes, for any reason. Those reasons include:
816 \b a fresh move being made by \cw{interpret_move()} and
819 \b a solve operation being performed by \cw{solve()} and
822 \b the user moving back and forth along the undo list by means of
823 the Undo and Redo operations
825 \b the user selecting Restart to go back to the initial game state.
827 The job of \cw{changed_state()} is to update the \c{game_ui} for
828 consistency with the new game state, if any update is necessary. For
829 example, Same Game stores data about the currently selected tile
830 group in its \c{game_ui}, and this data is intrinsically related to
831 the game state it was derived from. So it's very likely to become
832 invalid when the game state changes; thus, Same Game's
833 \cw{changed_state()} function clears the current selection whenever
836 Any call to \cw{changed_state()} can be sure that there will be a
837 subsequent call to \cw{anim_length()} and \cw{flash_length()}. So
838 \cw{changed_state()} can set up data in the \c{game_ui} which will
839 be read by \cw{anim_length()} and \cw{flash_length()}, and not have
840 to worry about those functions being called without the data having
843 \H{backend-moves} Making moves
845 This section describes the functions which actually make moves in
846 the game: that is, the functions which process user input and end up
847 producing new \c{game_state}s.
849 \S{backend-interpret-move} \cw{interpret_move()}
851 \c char *(*interpret_move)(game_state *state, game_ui *ui,
852 \c game_drawstate *ds,
853 \c int x, int y, int button);
855 This function receives user input and processes it. Its input
856 parameters are the current \c{game_state}, the current \c{game_ui}
857 and the current \c{game_drawstate}, plus details of the input event.
858 \c{button} is either an ASCII value or a special code (listed below)
859 indicating an arrow or function key or a mouse event; when
860 \c{button} is a mouse event, \c{x} and \c{y} contain the pixel
861 coordinates of the mouse pointer relative to the top left of the
862 puzzle's drawing area.
864 \cw{interpret_move()} may return in three different ways:
866 \b Returning \cw{NULL} indicates that no action whatsoever occurred
867 in response to the input event; the puzzle was not interested in it
870 \b Returning the empty string (\cw{""}) indicates that the input
871 event has resulted in a change being made to the \c{game_ui} which
872 will require a redraw of the game window, but that no actual
873 \e{move} was made (i.e. no new \c{game_state} needs to be created).
875 \b Returning anything else indicates that a move was made and that a
876 new \c{game_state} must be created. However, instead of actually
877 constructing a new \c{game_state} itself, this function is required
878 to return a string description of the details of the move. This
879 string will be passed to \cw{execute_move()}
880 (\k{backend-execute-move}) to actually create the new
881 \c{game_state}. (Encoding moves as strings in this way means that
882 the mid-end can keep the strings as well as the game states, and the
883 strings can be written to disk when saving the game and fed to
884 \cw{execute_move()} again on reloading.)
886 The return value from \cw{interpret_move()} is expected to be
887 dynamically allocated if and only if it is not either \cw{NULL}
888 \e{or} the empty string.
890 After this function is called, the back end is permitted to rely on
891 some subsequent operations happening in sequence:
893 \b \cw{execute_move()} will be called to convert this move
894 description into a new \c{game_state}
896 \b \cw{changed_state()} will be called with the new \c{game_state}.
898 This means that if \cw{interpret_move()} needs to do updates to the
899 \c{game_ui} which are easier to perform by referring to the new
900 \c{game_state}, it can safely leave them to be done in
901 \cw{changed_state()} and not worry about them failing to happen.
903 (Note, however, that \cw{execute_move()} may \e{also} be called in
904 other circumstances. It is only \cw{interpret_move()} which can rely
905 on a subsequent call to \cw{changed_state()}.)
907 The special key codes supported by this function are:
909 \dt \cw{LEFT_BUTTON}, \cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}
911 \dd Indicate that one of the mouse buttons was pressed down.
913 \dt \cw{LEFT_DRAG}, \cw{MIDDLE_DRAG}, \cw{RIGHT_DRAG}
915 \dd Indicate that the mouse was moved while one of the mouse buttons
916 was still down. The mid-end guarantees that when one of these events
917 is received, it will always have been preceded by a button-down
918 event (and possibly other drag events) for the same mouse button,
919 and no event involving another mouse button will have appeared in
922 \dt \cw{LEFT_RELEASE}, \cw{MIDDLE_RELEASE}, \cw{RIGHT_RELEASE}
924 \dd Indicate that a mouse button was released. The mid-end
925 guarantees that when one of these events is received, it will always
926 have been preceded by a button-down event (and possibly some drag
927 events) for the same mouse button, and no event involving another
928 mouse button will have appeared in between.
930 \dt \cw{CURSOR_UP}, \cw{CURSOR_DOWN}, \cw{CURSOR_LEFT},
933 \dd Indicate that an arrow key was pressed.
935 \dt \cw{CURSOR_SELECT}
937 \dd On platforms which have a prominent \q{select} button alongside
938 their cursor keys, indicates that that button was pressed.
940 In addition, there are some modifiers which can be bitwise-ORed into
941 the \c{button} parameter:
943 \dt \cw{MOD_CTRL}, \cw{MOD_SHFT}
945 \dd These indicate that the Control or Shift key was pressed
946 alongside the key. They only apply to the cursor keys, not to mouse
947 buttons or anything else.
949 \dt \cw{MOD_NUM_KEYPAD}
951 \dd This applies to some ASCII values, and indicates that the key
952 code was input via the numeric keypad rather than the main keyboard.
953 Some puzzles may wish to treat this differently (for example, a
954 puzzle might want to use the numeric keypad as an eight-way
955 directional pad), whereas others might not (a game involving numeric
956 input probably just wants to treat the numeric keypad as numbers).
960 \dd This mask is the bitwise OR of all the available modifiers; you
961 can bitwise-AND with \cw{~MOD_MASK} to strip all the modifiers off
964 \S{backend-execute-move} \cw{execute_move()}
966 \c game_state *(*execute_move)(game_state *state, char *move);
968 This function takes an input \c{game_state} and a move string as
969 output from \cw{interpret_move()}. It returns a newly allocated
970 \c{game_state} which contains the result of applying the specified
971 move to the input game state.
973 This function may return \cw{NULL} if it cannot parse the move
974 string (and this is definitely preferable to crashing or failing an
975 assertion, since one way this can happen is if loading a corrupt
976 save file). However, it must not return \cw{NULL} for any move
977 string that really was output from \cw{interpret_move()}: this is
978 punishable by assertion failure in the mid-end.
980 \S{backend-can-solve} \c{can_solve}
984 This boolean field is set to \cw{TRUE} if the game's \cw{solve()}
985 function does something. If it's set to \cw{FALSE}, the game will
986 not even offer the \q{Solve} menu option.
988 \S{backend-solve} \cw{solve()}
990 \c char *(*solve)(game_state *orig, game_state *curr,
991 \c char *aux, char **error);
993 This function is called when the user selects the \q{Solve} option
996 It is passed two input game states: \c{orig} is the game state from
997 the very start of the puzzle, and \c{curr} is the current one.
998 (Different games find one or other or both of these convenient.) It
999 is also passed the \c{aux} string saved by \cw{new_desc()}
1000 (\k{backend-new-desc}), in case that encodes important information
1001 needed to provide the solution.
1003 If this function is unable to produce a solution (perhaps, for
1004 example, the game has no in-built solver so it can only solve
1005 puzzles it invented internally and has an \c{aux} string for) then
1006 it may return \cw{NULL}. If it does this, it must also set
1007 \c{*error} to an error message to be presented to the user (such as
1008 \q{Solution not known for this puzzle}); that error message is not
1009 expected to be dynamically allocated.
1011 If this function \e{does} produce a solution, it returns a move
1012 string suitable for feeding to \cw{execute_move()}
1013 (\k{backend-execute-move}).
1015 \H{backend-drawing} Drawing the game graphics
1017 This section discusses the back end functions that deal with
1020 \S{backend-new-drawstate} \cw{new_drawstate()}
1022 \c game_drawstate *(*new_drawstate)(game_state *state);
1024 This function allocates and returns a new \c{game_drawstate}
1025 structure for drawing a particular puzzle. It is passed a pointer to
1026 a \c{game_state}, in case it needs to refer to that when setting up
1029 This function may not rely on the puzzle having been newly started;
1030 a new draw state can be constructed at any time if the front end
1031 requests a forced redraw. For games like Pattern, in which initial
1032 game states are much simpler than general ones, this might be
1033 important to keep in mind.
1035 \S{backend-free-drawstate} \cw{free_drawstate()}
1037 \c void (*free_drawstate)(game_drawstate *ds);
1039 This function frees a \c{game_drawstate} structure, and any
1040 subsidiary allocations contained within it.
1042 \S{backend-preferred-tilesize} \c{preferred_tilesize}
1044 \c int preferred_tilesize;
1046 Each game is required to define a single integer parameter which
1047 expresses, in some sense, the scale at which it is drawn. This is
1048 described in the APIs as \cq{tilesize}, since most puzzles are on a
1049 square (or possibly triangular or hexagonal) grid and hence a
1050 sensible interpretation of this parameter is to define it as the
1051 size of one grid tile in pixels; however, there's no actual
1052 requirement that the \q{tile size} be proportional to the game
1053 window size. Window size is required to increase monotonically with
1054 \q{tile size}, however.
1056 The data element \c{preferred_tilesize} indicates the tile size
1057 which should be used in the absence of a good reason to do otherwise
1058 (such as the screen being too small, or the user explicitly
1059 requesting a resize if that ever gets implemented).
1061 \S{backend-compute-size} \cw{compute_size()}
1063 \c void (*compute_size)(game_params *params, int tilesize,
1066 This function is passed a \c{game_params} structure and a tile size.
1067 It returns, in \c{*x} and \c{*y}, the size in pixels of the drawing
1068 area that would be required to render a puzzle with those parameters
1071 \S{backend-set-size} \cw{set_size()}
1073 \c void (*set_size)(game_drawstate *ds, game_params *params,
1076 This function is responsible for setting up a \c{game_drawstate} to
1077 draw at a given tile size. Typically this will simply involve
1078 copying the supplied \c{tilesize} parameter into a \c{tilesize}
1079 field inside the draw state; for some more complex games it might
1080 also involve setting up other dimension fields, or possibly
1081 allocating a blitter (see \k{drawing-blitter}).
1083 \S{backend-colours} \cw{colours()}
1085 \c float *(*colours)(frontend *fe, game_state *state, int *ncolours);
1087 This function is responsible for telling the front end what colours
1088 the puzzle will need to draw itself.
1090 It returns the number of colours required in \c{*ncolours}, and the
1091 return value from the function itself is a dynamically allocated
1092 array of three times that many \c{float}s, containing the red, green
1093 and blue components of each colour respectively as numbers in the
1096 It is passed a sample \c{game_state} in case it needs one, although
1097 currently no puzzle does need this. (In fact, colours are not
1098 reallocated when the game parameters change or a new game is
1099 started, so you can't reliably use this \c{game_state} to allocate a
1100 different number of colours depending on the game. It is probably
1101 actually a mistake to rely on this parameter at all. I ought to
1102 either remove it or fix it; probably the former.)
1104 The final parameter passed to this function is a front end handle.
1105 The only thing it is permitted to do with this handle is to call the
1106 front-end function called \cw{frontend_default_colour()} (see
1107 \k{frontend-default-colour}). This allows \cw{colours()} to take
1108 local configuration into account when deciding on its own colour
1109 allocations. Most games use the front end's default colour as their
1110 background, apart from a few which depend on drawing relief
1111 highlights so they adjust the background colour if it's too light
1112 for highlights to show up against it.
1114 \S{backend-anim-length} \cw{anim_length()}
1116 \c float (*anim_length)(game_state *oldstate, game_state *newstate,
1117 \c int dir, game_ui *ui);
1119 This function is called when a move is made, undone or redone. It is
1120 given the old and the new \c{game_state}, and its job is to decide
1121 whether the transition between the two needs to be animated or can
1124 \c{oldstate} is the state that was current until this call;
1125 \c{newstate} is the state that will be current after it. \c{dir}
1126 specifies the chronological order of those states: if it is
1127 positive, then the transition is the result of a move or a redo (and
1128 so \c{newstate} is the later of the two moves), whereas if it is
1129 negative then the transition is the result of an undo (so that
1130 \c{newstate} is the \e{earlier} move).
1132 If this function decides the transition should be animated, it
1133 returns the desired length of the animation in seconds. If not, it
1136 State changes as a result of a Restart operation are never animated;
1137 the mid-end will handle them internally and never consult this
1138 function at all. State changes as a result of Solve operations are
1139 also not animated by default, although you can change this for a
1140 particular game by setting a flag in \c{mouse_priorities}
1141 (\k{backend-mouse-priorities}).
1143 The function is also passed a pointer to the local \c{game_ui}. It
1144 may refer to information in here to help with its decision (see
1145 \k{writing-conditional-anim} for an example of this), and/or it may
1146 \e{write} information about the nature of the animation which will
1147 be read later by \cw{redraw()}.
1149 When this function is called, it may rely on \cw{changed_state()}
1150 having been called previously, so if \cw{anim_length()} needs to
1151 refer to information in the \c{game_ui}, then \cw{changed_state()}
1152 is a reliable place to have set that information up.
1154 Move animations do not inhibit further input events. If the user
1155 continues playing before a move animation is complete, the animation
1156 will be abandoned and the display will jump straight to the final
1159 \S{backend-flash-length} \cw{flash_length()}
1161 \c float (*flash_length)(game_state *oldstate, game_state *newstate,
1162 \c int dir, game_ui *ui);
1164 This function is called when a move is completed. (\q{Completed}
1165 means that not only has the move been made, but any animation which
1166 accompanied it has finished.) It decides whether the transition from
1167 \c{oldstate} to \c{newstate} merits a \q{flash}.
1169 A flash is much like a move animation, but it is \e{not} interrupted
1170 by further user interface activity; it runs to completion in
1171 parallel with whatever else might be going on on the display. The
1172 only thing which will rush a flash to completion is another flash.
1174 The purpose of flashes is to indicate that the game has been
1175 completed. They were introduced as a separate concept from move
1176 animations because of Net: the habit of most Net players (and
1177 certainly me) is to rotate a tile into place and immediately lock
1178 it, then move on to another tile. When you make your last move, at
1179 the instant the final tile is rotated into place the screen starts
1180 to flash to indicate victory \dash but if you then press the lock
1181 button out of habit, then the move animation is cancelled, and the
1182 victory flash does not complete. (And if you \e{don't} press the
1183 lock button, the completed grid will look untidy because there will
1184 be one unlocked square.) Therefore, I introduced a specific concept
1185 of a \q{flash} which is separate from a move animation and can
1186 proceed in parallel with move animations and any other display
1187 activity, so that the victory flash in Net is not cancelled by that
1190 The input parameters to \cw{flash_length()} are exactly the same as
1191 the ones to \cw{anim_length()}.
1193 Just like \cw{anim_length()}, when this function is called, it may
1194 rely on \cw{changed_state()} having been called previously, so if it
1195 needs to refer to information in the \c{game_ui} then
1196 \cw{changed_state()} is a reliable place to have set that
1199 (Some games use flashes to indicate defeat as well as victory;
1200 Mines, for example, flashes in a different colour when you tread on
1201 a mine from the colour it uses when you complete the game. In order
1202 to achieve this, its \cw{flash_length()} function has to store a
1203 flag in the \c{game_ui} to indicate which flash type is required.)
1205 \S{backend-redraw} \cw{redraw()}
1207 \c void (*redraw)(frontend *fe, game_drawstate *ds,
1208 \c game_state *oldstate, game_state *newstate, int dir,
1209 \c game_ui *ui, float anim_time, float flash_time);
1211 This function is responsible for actually drawing the contents of
1212 the game window, and for redrawing every time the game state or the
1213 \c{game_ui} changes.
1215 The parameter \c{fe} is a front end handle which may be passed to
1216 the drawing API functions (see \k{drawing} for documentation of the
1217 drawing API). This function may not save \c{fe} and use it
1218 elsewhere; it must only use it for calling back to the drawing API
1219 functions within its own lifetime.
1221 \c{ds} is the local \c{game_drawstate}, of course, and \c{ui} is the
1224 \c{newstate} is the semantically-current game state, and is always
1225 non-\cw{NULL}. If \c{oldstate} is also non-\cw{NULL}, it means that
1226 a move has recently been made and the game is still in the process
1227 of displaying an animation linking the old and new states; in this
1228 situation, \c{anim_time} will give the length of time (in seconds)
1229 that the animation has already been running. If \c{oldstate} is
1230 \cw{NULL}, then \c{anim_time} is unused (and will hopefully be set
1231 to zero to avoid confusion).
1233 \c{flash_time}, if it is is non-zero, denotes that the game is in
1234 the middle of a flash, and gives the time since the start of the
1235 flash. See \k{backend-flash-length} for general discussion of
1238 The very first time this function is called for a new
1239 \c{game_drawstate}, it is expected to redraw the \e{entire} drawing
1240 area. Since this often involves drawing visual furniture which is
1241 never subsequently altered, it is often simplest to arrange this by
1242 having a special \q{first time} flag in the draw state, and
1243 resetting it after the first redraw.
1245 \H{backend-misc} Miscellaneous
1247 \S{backend-can-format-as-text} \c{can_format_as_text}
1249 \c int can_format_as_text;
1251 This boolean field is \cw{TRUE} if the game supports formatting a
1252 game state as ASCII text (typically ASCII art) for copying to the
1253 clipboard and pasting into other applications. If it is \cw{FALSE},
1254 front ends will not offer the \q{Copy} command at all.
1256 If this field is \cw{FALSE}, the function \cw{text_format()}
1257 (\k{backend-text-format}) is not expected to do anything at all.
1259 \S{backend-text-format} \cw{text_format()}
1261 \c char *(*text_format)(game_state *state);
1263 This function is passed a \c{game_state}, and returns a newly
1264 allocated C string containing an ASCII representation of that game
1265 state. It is used to implement the \q{Copy} operation in many front
1268 This function should only be called if the back end field
1269 \c{can_format_as_text} (\k{backend-can-format-as-text}) is
1272 The returned string may contain line endings (and will probably want
1273 to), using the normal C internal \cq{\\n} convention. For
1274 consistency between puzzles, all multi-line textual puzzle
1275 representations should \e{end} with a newline as well as containing
1276 them internally. (There are currently no puzzles which have a
1277 one-line ASCII representation, so there's no precedent yet for
1278 whether that should come with a newline or not.)
1280 \S{backend-wants-statusbar} \cw{wants_statusbar()}
1282 \c int (*wants_statusbar)(void);
1284 This function returns \cw{TRUE} if the puzzle has a use for a
1285 textual status line (to display score, completion status, currently
1288 (This should probably be a static boolean field rather than a
1289 function. I don't remember why I did it this way. I probably ought
1292 \S{backend-is-timed} \c{is_timed}
1296 This boolean field is \cw{TRUE} if the puzzle is time-critical. If
1297 so, the mid-end will maintain a game timer while the user plays.
1299 If this field is \cw{FALSE}, then \cw{timing_state()} will never be
1300 called and need not do anything.
1302 \S{backend-timing-state} \cw{timing_state()}
1304 \c int (*timing_state)(game_state *state, game_ui *ui);
1306 This function is passed the current \c{game_state} and the local
1307 \c{game_ui}; it returns \cw{TRUE} if the game timer should currently
1310 A typical use for the \c{game_ui} in this function is to note when
1311 the game was first completed (by setting a flag in
1312 \cw{changed_state()} \dash see \k{backend-changed-state}), and
1313 freeze the timer thereafter so that the user can undo back through
1314 their solution process without altering their time.
1316 \S{backend-mouse-priorities} \c{mouse_priorities}
1318 \c int mouse_priorities;
1320 This field is badly named. It is in fact a generic flags word. It
1321 consists of the bitwise OR of the following flags:
1323 \dt \cw{BUTTON_BEATS(x,y)}
1325 \dd Given any \cw{x} and \cw{y} from the set (\cw{LEFT_BUTTON},
1326 \cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}), this macro evaluates to a
1327 bit flag which indicates that when buttons \cw{x} and \cw{y} are
1328 both pressed simultaneously, the mid-end should consider \cw{x} to
1329 have priority. (In the absence of any such flags, the mid-end will
1330 always consider the most recently pressed button to have priority.)
1332 \dt \cw{SOLVE_ANIMATES}
1334 \dd This flag indicates that moves generated by \cw{solve()}
1335 (\k{backend-solve}) are candidates for animation just like any other
1336 move. For most games, solve moves should not be animated, so the
1337 mid-end doesn't even bother calling \cw{anim_length()}
1338 (\k{backend-anim-length}), thus saving some special-case code in
1339 each game. On the rare occasion that animated solve moves are
1340 actually required, you can set this flag.
1342 \H{backend-initiative} Things a back end may do on its own initiative
1344 This section describes a couple of things that a back end may choose
1345 to do by calling functions elsewhere in the program, which would not
1346 otherwise be obvious.
1348 \S{backend-newrs} Create a random state
1350 If a back end needs random numbers at some point during normal play,
1351 it can create a fresh \c{random_state} by first calling
1352 \c{get_random_seed} (\k{frontend-get-random-seed}) and then passing
1353 the returned seed data to \cw{random_init()}.
1355 This is likely not to be what you want. If a puzzle needs randomness
1356 in the middle of play, it's likely to be more sensible to store some
1357 sort of random state within the \e{game_state}, so that the random
1358 numbers are tied to the particular game state and hence the player
1359 can't simply keep undoing their move until they get numbers they
1362 This facility is currently used only in Net, to implement the
1363 \q{jumble} command, which sets every unlocked tile to a new random
1364 orientation. This randomness \e{is} a reasonable use of the feature,
1365 because it's non-adversarial \dash there's no advantage to the user
1366 in getting different random numbers.
1368 \S{backend-supersede} Supersede its own game description
1370 In response to a move, a back end is (reluctantly) permitted to call
1371 \cw{midend_supersede_game_desc()}:
1373 \c void midend_supersede_game_desc(midend_data *me,
1374 \c char *desc, char *privdesc);
1376 When the user selects \q{New Game}, the mid-end calls
1377 \cw{new_desc()} (\k{backend-new-desc}) to get a new game
1378 description, and (as well as using that to generate an initial game
1379 state) stores it for the save file and for telling to the user. The
1380 function above overwrites that game description, and also splits it
1381 in two. \c{desc} becomes the new game description which is provided
1382 to the user on request, and is also the one used to construct a new
1383 initial game state if the user selects \q{Restart}. \c{privdesc} is
1384 a \q{private} game description, used to reconstruct the game's
1385 initial state when reloading.
1387 The distinction between the two, as well as the need for this
1388 function at all, comes from Mines. Mines begins with a blank grid
1389 and no idea of where the mines actually are; \cw{new_desc()} does
1390 almost no work in interactive mode, and simply returns a string
1391 encoding the \c{random_state}. When the user first clicks to open a
1392 tile, \e{then} Mines generates the mine positions, in such a way
1393 that the game is soluble from that starting point. Then it uses this
1394 function to supersede the random-state game description with a
1395 proper one. But it needs two: one containing the initial click
1396 location (because that's what you want to happen if you restart the
1397 game, and also what you want to send to a friend so that they play
1398 \e{the same game} as you), and one without the initial click
1399 location (because when you save and reload the game, you expect to
1400 see the same blank initial state as you had before saving).
1402 I should stress again that this function is a horrid hack. Nobody
1403 should use it if they're not Mines; if you think you need to use it,
1404 think again repeatedly in the hope of finding a better way to do
1405 whatever it was you needed to do.
1407 \C{drawing} The drawing API: front-end functions called from the
1410 The back end function \cw{redraw()} (\k{backend-redraw}) is required
1411 to draw the puzzle's graphics on the window's drawing area. To do
1412 this portably, it is provided with a drawing API allowing it to talk
1413 directly to the front end. In this chapter I document that API, both
1414 for the benefit of back end authors trying to use it and for front
1415 end authors trying to implement it.
1417 All of the drawing functions take a pointer to a \c{frontend}
1418 structure, which is passed in to \cw{redraw()}.
1420 The puzzle window is indexed by pixel coordinates, with the top left
1421 pixel defined as \cw{(0,0)} and the bottom right pixel
1422 \cw{(w-1,h-1)}, where \c{w} and \c{h} are the width and height
1423 values returned by the back end function \cw{compute_size()}
1424 (\k{backend-compute-size}).
1426 \e{Puzzles may assume that the surface they draw on is persistent}.
1427 It is the responsibility of every front end to preserve the puzzle's
1428 window contents in the face of GUI window expose issues and similar.
1429 It is not permissible to request the back end redraw any part of a
1430 window that it has already drawn, unless something has actually
1431 changed as a result of making moves in the puzzle.
1433 Most front ends accomplish this by having the drawing routines draw
1434 on a stored bitmap rather than directly on the window, and copying
1435 the bitmap to the window every time a part of the window needs to be
1436 redrawn. Therefore, it is vitally important that whenever the back
1437 end does any drawing it informs the front end of which parts of the
1438 window it has accessed, and hence which parts need repainting. This
1439 is done by calling \cw{draw_update()} (\k{drawing-draw-update}).
1441 \H{drawing-draw-rect} \cw{draw_rect()}
1443 \c void draw_rect(frontend *fe, int x, int y, int w, int h,
1446 Draws a filled rectangle in the puzzle window.
1448 \c{x} and \c{y} give the coordinates of the top left pixel of the
1449 rectangle. \c{w} and \c{h} give its width and height. Thus, the
1450 horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1451 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1454 \c{colour} is an integer index into the colours array returned by
1455 the back end function \cw{colours()} (\k{backend-colours}).
1457 There is no separate pixel-plotting function. If you want to plot a
1458 single pixel, the approved method is to use \cw{draw_rect()} with
1459 width and height set to 1.
1461 Unlike many of the other drawing functions, this function is
1462 guaranteed to be pixel-perfect: the rectangle will be sharply
1463 defined and not anti-aliased or anything like that.
1465 \H{drawing-draw-rect-outline} \cw{draw_rect_outline()}
1467 \c void draw_rect_outline(frontend *fe, int x, int y, int w, int h,
1470 Draws an outline rectangle in the puzzle window.
1472 \c{x} and \c{y} give the coordinates of the top left pixel of the
1473 rectangle. \c{w} and \c{h} give its width and height. Thus, the
1474 horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1475 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1478 \c{colour} is an integer index into the colours array returned by
1479 the back end function \cw{colours()} (\k{backend-colours}).
1481 From a back end perspective, this function may be considered to be
1482 part of the drawing API. However, front ends are not required to
1483 implement it, since it is actually implemented centrally (in
1484 \cw{misc.c}) as a wrapper on four calls to \cw{draw_line()}.
1486 \H{drawing-draw-line} \cw{draw_line()}
1488 \c void draw_line(frontend *fe, int x1, int y1, int x2, int y2,
1491 Draws a straight line in the puzzle window.
1493 \c{x1} and \c{y1} give the coordinates of one end of the line.
1494 \c{x2} and \c{y2} give the coordinates of the other end. The line
1495 drawn includes both those points.
1497 \c{colour} is an integer index into the colours array returned by
1498 the back end function \cw{colours()} (\k{backend-colours}).
1500 Some platforms may perform anti-aliasing on this function.
1501 Therefore, do not assume that you can erase a line by drawing the
1502 same line over it in the background colour; anti-aliasing might
1503 lead to perceptible ghost artefacts around the vanished line.
1505 \H{drawing-draw-polygon} \cw{draw_polygon()}
1507 \c void draw_polygon(frontend *fe, int *coords, int npoints,
1508 \c int fillcolour, int outlinecolour);
1510 Draws an outlined or filled polygon in the puzzle window.
1512 \c{coords} is an array of \cw{(2*npoints)} integers, containing the
1513 \c{x} and \c{y} coordinates of \c{npoints} vertices.
1515 \c{fillcolour} and \c{outlinecolour} are integer indices into the
1516 colours array returned by the back end function \cw{colours()}
1517 (\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
1518 indicate that the polygon should be outlined only.
1520 The polygon defined by the specified list of vertices is first
1521 filled in \c{fillcolour}, if specified, and then outlined in
1524 \c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
1525 (and front ends are permitted to enforce this by assertion). This is
1526 because different platforms disagree on whether a filled polygon
1527 should include its boundary line or not, so drawing \e{only} a
1528 filled polygon would have non-portable effects. If you want your
1529 filled polygon not to have a visible outline, you must set
1530 \c{outlinecolour} to the same as \c{fillcolour}.
1532 Some platforms may perform anti-aliasing on this function.
1533 Therefore, do not assume that you can erase a polygon by drawing the
1534 same polygon over it in the background colour. Also, be prepared for
1535 the polygon to extend a pixel beyond its obvious bounding box as a
1536 result of this; if you really need it not to do this to avoid
1537 interfering with other delicate graphics, you should probably use
1538 \cw{clip()} (\k{drawing-clip}).
1540 \H{drawing-draw-circle} \cw{draw_circle()}
1542 \c void draw_circle(frontend *fe, int cx, int cy, int radius,
1543 \c int fillcolour, int outlinecolour);
1545 Draws an outlined or filled circle in the puzzle window.
1547 \c{cx} and \c{cy} give the coordinates of the centre of the circle.
1548 \c{radius} gives its radius. The total horizontal pixel extent of
1549 the circle is from \c{cx-radius+1} to \c{cx+radius-1} inclusive, and
1550 the vertical extent similarly around \c{cy}.
1552 \c{fillcolour} and \c{outlinecolour} are integer indices into the
1553 colours array returned by the back end function \cw{colours()}
1554 (\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
1555 indicate that the circle should be outlined only.
1557 The circle is first filled in \c{fillcolour}, if specified, and then
1558 outlined in \c{outlinecolour}.
1560 \c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
1561 (and front ends are permitted to enforce this by assertion). This is
1562 because different platforms disagree on whether a filled circle
1563 should include its boundary line or not, so drawing \e{only} a
1564 filled circle would have non-portable effects. If you want your
1565 filled circle not to have a visible outline, you must set
1566 \c{outlinecolour} to the same as \c{fillcolour}.
1568 Some platforms may perform anti-aliasing on this function.
1569 Therefore, do not assume that you can erase a circle by drawing the
1570 same circle over it in the background colour. Also, be prepared for
1571 the circle to extend a pixel beyond its obvious bounding box as a
1572 result of this; if you really need it not to do this to avoid
1573 interfering with other delicate graphics, you should probably use
1574 \cw{clip()} (\k{drawing-clip}).
1576 \H{drawing-draw-text} \cw{draw_text()}
1578 \c void draw_text(frontend *fe, int x, int y, int fonttype,
1579 \c int fontsize, int align, int colour, char *text);
1581 Draws text in the puzzle window.
1583 \c{x} and \c{y} give the coordinates of a point. The relation of
1584 this point to the location of the text is specified by \c{align},
1585 which is a bitwise OR of horizontal and vertical alignment flags:
1587 \dt \cw{ALIGN_VNORMAL}
1589 \dd Indicates that \c{y} is aligned with the baseline of the text.
1591 \dt \cw{ALIGN_VCENTRE}
1593 \dd Indicates that \c{y} is aligned with the vertical centre of the
1594 text. (In fact, it's aligned with the vertical centre of normal
1595 \e{capitalised} text: displaying two pieces of text with
1596 \cw{ALIGN_VCENTRE} at the same \cw{y}-coordinate will cause their
1597 baselines to be aligned with one another, even if one is an ascender
1598 and the other a descender.)
1600 \dt \cw{ALIGN_HLEFT}
1602 \dd Indicates that \c{x} is aligned with the left-hand end of the
1605 \dt \cw{ALIGN_HCENTRE}
1607 \dd Indicates that \c{x} is aligned with the horizontal centre of
1610 \dt \cw{ALIGN_HRIGHT}
1612 \dd Indicates that \c{x} is aligned with the right-hand end of the
1615 \c{fonttype} is either \cw{FONT_FIXED} or \cw{FONT_VARIABLE}, for a
1616 monospaced or proportional font respectively. (No more detail than
1617 that may be specified; it would only lead to portability issues
1618 between different platforms.)
1620 \c{fontsize} is the desired size, in pixels, of the text. This size
1621 corresponds to the overall point size of the text, not to any
1622 internal dimension such as the cap-height.
1624 \c{colour} is an integer index into the colours array returned by
1625 the back end function \cw{colours()} (\k{backend-colours}).
1627 \H{drawing-clip} \cw{clip()}
1629 \c void clip(frontend *fe, int x, int y, int w, int h);
1631 Establishes a clipping rectangle in the puzzle window.
1633 \c{x} and \c{y} give the coordinates of the top left pixel of the
1634 clipping rectangle. \c{w} and \c{h} give its width and height. Thus,
1635 the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1636 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1637 inclusive. (These are exactly the same semantics as
1640 After this call, no drawing operation will affect anything outside
1641 the specified rectangle. The effect can be reversed by calling
1642 \cw{unclip()} (\k{drawing-unclip}).
1644 Back ends should not assume that a clipping rectangle will be
1645 automatically cleared up by the front end if it's left lying around;
1646 that might work on current front ends, but shouldn't be relied upon.
1647 Always explicitly call \cw{unclip()}.
1649 \H{drawing-unclip} \cw{unclip()}
1651 \c void unclip(frontend *fe);
1653 Reverts the effect of a previous call to \cw{clip()}. After this
1654 call, all drawing operations will be able to affect the entire
1655 puzzle window again.
1657 \H{drawing-draw-update} \cw{draw_update()}
1659 \c void draw_update(frontend *fe, int x, int y, int w, int h);
1661 Informs the front end that a rectangular portion of the puzzle
1662 window has been drawn on and needs to be updated.
1664 \c{x} and \c{y} give the coordinates of the top left pixel of the
1665 update rectangle. \c{w} and \c{h} give its width and height. Thus,
1666 the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1667 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1668 inclusive. (These are exactly the same semantics as
1671 The back end redraw function \e{must} call this function to report
1672 any changes it has made to the window. Otherwise, those changes may
1673 not become immediately visible, and may then appear at an
1674 unpredictable subsequent time such as the next time the window is
1675 covered and re-exposed.
1677 \H{drawing-status-bar} \cw{status_bar()}
1679 \c void status_bar(frontend *fe, char *text);
1681 Sets the text in the game's status bar to \c{text}.
1683 (This function is not exactly a \e{drawing} function, but it shares
1684 with the drawing API the property that it may only be called from
1685 within the back end redraw function, so this is as good a place as
1686 any to document it.)
1688 Front ends implementing this function should not use the provided
1689 text directly; they should call \cw{midend_rewrite_statusbar()}
1690 (\k{midend-rewrite-statusbar}) to process it first.
1692 In a game which has a timer, this function is likely to be called
1693 every time the timer goes off, i.e. many times a second. It is
1694 therefore likely to be common that this function is called with
1695 precisely the same text as the last time it was called. Front ends
1696 may well wish to detect this common case and avoid bothering to do
1697 anything. If they do, however, they \e{must} perform this check on
1698 the value \e{returned} from \cw{midend_rewrite_statusbar()}, rather
1699 than the value passed in to it (because the mid-end will frequently
1700 update the status-bar timer without the back end's intervention).
1702 \H{drawing-blitter} Blitter functions
1704 This section describes a group of related function which save and
1705 restore a section of the puzzle window. This is most commonly used
1706 to implement user interfaces involving dragging a puzzle element
1707 around the window: at the end of each call to \cw{redraw()}, if an
1708 object is currently being dragged, the back end saves the window
1709 contents under that location and then draws the dragged object, and
1710 at the start of the next \cw{redraw()} the first thing it does is to
1711 restore the background.
1713 The front end defines an opaque type called a \c{blitter}, which is
1714 capable of storing a rectangular area of a specified size.
1716 \S{drawing-blitter-new} \cw{blitter_new()}
1718 \c blitter *blitter_new(int w, int h);
1720 Creates a new blitter object which stores a rectangle of size \c{w}
1721 by \c{h} pixels. Returns a pointer to the blitter object.
1723 Blitter objects are best stored in the \c{game_drawstate}. A good
1724 time to create them is in the \cw{set_size()} function
1725 (\k{backend-set-size}), since it is at this point that you first
1726 know how big a rectangle they will need to save.
1728 \S{drawing-blitter-free} \cw{blitter_free()}
1730 \c void blitter_free(blitter *bl);
1732 Disposes of a blitter object. Best called in \cw{free_drawstate()}.
1733 (However, check that the blitter object is not \cw{NULL} before
1734 attempting to free it; it is possible that a draw state might be
1735 created and freed without ever having \cw{set_size()} called on it
1738 \S{drawing-blitter-save} \cw{blitter_save()}
1740 \c void blitter_save(frontend *fe, blitter *bl, int x, int y);
1742 This is a true drawing API function, in that it may only be called
1743 from within the game redraw routine. It saves a rectangular portion
1744 of the puzzle window into the specified blitter object.
1746 \c{x} and \c{y} give the coordinates of the top left corner of the
1747 saved rectangle. The rectangle's width and height are the ones
1748 specified when the blitter object was created.
1750 This function is required to cope and do the right thing if \c{x}
1751 and \c{y} are out of range. (The right thing probably means saving
1752 whatever part of the blitter rectangle overlaps with the visible
1753 area of the puzzle window.)
1755 \S{drawing-blitter-load} \cw{blitter_load()}
1757 \c void blitter_load(frontend *fe, blitter *bl, int x, int y);
1759 This is a true drawing API function, in that it may only be called
1760 from within the game redraw routine. It restores a rectangular
1761 portion of the puzzle window from the specified blitter object.
1763 \c{x} and \c{y} give the coordinates of the top left corner of the
1764 rectangle to be restored. The rectangle's width and height are the
1765 ones specified when the blitter object was created.
1767 Alternatively, you can specify both \c{x} and \c{y} as the special
1768 value \cw{BLITTER_FROMSAVED}, in which case the rectangle will be
1769 restored to exactly where it was saved from. (This is probably what
1770 you want to do almost all the time, if you're using blitters to
1771 implement draggable puzzle elements.)
1773 This function is required to cope and do the right thing if \c{x}
1774 and \c{y} (or the equivalent ones saved in the blitter) are out of
1775 range. (The right thing probably means restoring whatever part of
1776 the blitter rectangle overlaps with the visible area of the puzzle
1779 If this function is called on a blitter which had previously been
1780 saved from a partially out-of-range rectangle, then the parts of the
1781 saved bitmap which were not visible at save time are undefined. If
1782 the blitter is restored to a different position so as to make those
1783 parts visible, the effect on the drawing area is undefined.
1785 \H{drawing-midend} Additional functions only called by the mid-end
1787 The two functions documented in this section are part of the drawing
1788 API as seen by a front end, but are not needed by the back end. The
1789 mid-end calls these functions before and after calling the back end
1792 \S{drawing-start-draw} \cw{start_draw()}
1794 \c void start_draw(frontend *fe);
1796 This function is called before any drawing takes place. It allows
1797 the front end to initialise any temporary data required to draw
1798 with, such as device contexts.
1800 \S{drawing-end-draw} \cw{end_draw()}
1802 \c void end_draw(frontend *fe);
1804 This function is called at the end of drawing. It allows the front
1805 end to do cleanup tasks such as deallocating device contexts and
1806 scheduling appropriate GUI redraw events.
1808 \H{frontend-default-colour} \cw{frontend_default_colour()}
1810 \c void frontend_default_colour(frontend *fe, float *output);
1812 This function expects to be passed a pointer to an array of three
1813 \cw{float}s. It returns the platform's local preferred background
1814 colour in those three floats, as red, green and blue values (in that
1815 order) ranging from \cw{0.0} to \cw{1.0}.
1817 This function should only ever be called by the back end function
1818 \cw{colours()} (\k{backend-colours}). (Thus, it isn't a drawing API
1819 function as such, but it's a front end function of interest to
1820 puzzle implementors so it's probably best in this section.)
1822 \C{midend} The API provided by the mid-end
1824 This chapter documents the API provided by the mid-end to be called
1825 by the front end. You probably only need to read this if you are a
1826 front end implementor, i.e. you are porting Puzzles to a new
1827 platform. If you're only interested in writing new puzzles, you can
1828 safely skip this chapter.
1830 All the persistent state in the mid-end is encapsulated within a
1831 \c{midend_data} structure, to facilitate having multiple mid-ends in
1832 any port which supports multiple puzzle windows open simultaneously.
1833 Each \c{midend_data} is intended to handle the contents of a single
1836 \H{midend-new} \cw{midend_new()}
1838 \c midend_data *midend_new(frontend *fe, const game *ourgame);
1840 Allocates and returns a new mid-end structure.
1842 The \c{fe} argument is stored in the mid-end. It will be used when
1843 calling back to functions such as \cw{activate_timer()}
1844 (\k{frontend-activate-timer}), and will be passed on to back end
1845 functions such as \cw{colours()} (\k{backend-colours}) and
1846 \cw{redraw()} (\k{backend-redraw}). The latter, of course, means
1847 that the front end can expect to receive this pointer in calls to
1848 the entire drawing API (\k{drawing}).
1850 The \c{ourgame} argument points to a container structure describing
1851 a game back end. The mid-end thus created will only be capable of
1852 handling that one game. (So even in a monolithic front end
1853 containing all the games, this imposes the constraint that any
1854 individual puzzle window is tied to a single game. Unless, of
1855 course, you feel brave enough to change the mid-end for the window
1856 without closing the window...)
1858 \H{midend-free} \cw{midend_free()}
1860 \c void midend_free(midend_data *me);
1862 Frees a mid-end structure and all its associated data.
1864 \H{midend-set-params} \cw{midend_set_params()}
1866 \c void midend_set_params(midend_data *me, game_params *params);
1868 Sets the current game parameters for a mid-end. Subsequent games
1869 generated by \cw{midend_new_game()} (\k{midend-new-game}) will use
1870 these parameters until further notice.
1872 The usual way in which the front end will have an actual
1873 \c{game_params} structure to pass to this function is if it had
1874 previously got it from \cw{midend_fetch_preset()}
1875 (\k{midend-fetch-preset}). Thus, this function is usually called in
1876 response to the user making a selection from the presets menu.
1878 \H{midend-size} \cw{midend_size()}
1880 \c void midend_size(midend_data *me, int *x, int *y, int expand);
1882 Tells the mid-end to figure out its window size.
1884 On input, \c{*x} and \c{*y} should contain the maximum or requested
1885 size for the window. (Typically this will be the size of the screen
1886 that the window has to fit on, or similar.) The mid-end will
1887 repeatedly call the back end function \cw{compute_size()}
1888 (\k{backend-compute-size}), searching for a tile size that best
1889 satisfies the requirements. On exit, \c{*x} and \c{*y} will contain
1890 the size needed for the puzzle window's drawing area. (It is of
1891 course up to the front end to adjust this for any additional window
1892 furniture such as menu bars and window borders, if necessary. The
1893 status bar is also not included in this size.)
1895 If \c{expand} is set to \cw{FALSE}, then the game's tile size will
1896 never go over its preferred one. This is the recommended approach
1897 when opening a new window at default size: the game will use its
1898 preferred size unless it has to use a smaller one to fit on the
1901 If \c{expand} is set to \cw{TRUE}, the mid-end will pick a tile size
1902 which approximates the input size \e{as closely as possible}, and
1903 will go over the game's preferred tile size if necessary to achieve
1904 this. Use this option if you want your front end to support dynamic
1905 resizing of the puzzle window with automatic scaling of the puzzle
1908 The mid-end will try as hard as it can to return a size which is
1909 less than or equal to the input size, in both dimensions. In extreme
1910 circumstances it may fail (if even the lowest possible tile size
1911 gives window dimensions greater than the input), in which case it
1912 will return a size greater than the input size. Front ends should be
1913 prepared for this to happen (i.e. don't crash or fail an assertion),
1914 but may handle it in any way they see fit: by rejecting the game
1915 parameters which caused the problem, by opening a window larger than
1916 the screen regardless of inconvenience, by introducing scroll bars
1917 on the window, by drawing on a large bitmap and scaling it into a
1918 smaller window, or by any other means you can think of. It is likely
1919 that when the tile size is that small the game will be unplayable
1920 anyway, so don't put \e{too} much effort into handling it
1923 If your platform has no limit on window size (or if you're planning
1924 to use scroll bars for large puzzles), you can pass dimensions of
1925 \cw{INT_MAX} as input to this function. You should probably not do
1926 that \e{and} set the \c{expand} flag, though!
1928 \H{midend-new-game} \cw{midend_new_game()}
1930 \c void midend_new_game(midend_data *me);
1932 Causes the mid-end to begin a new game. Normally the game will be a
1933 new randomly generated puzzle. However, if you have previously
1934 called \cw{midend_game_id()} or \cw{midend_set_config()}, the game
1935 generated might be dictated by the results of those functions. (In
1936 particular, you \e{must} call \cw{midend_new_game()} after calling
1937 either of those functions, or else no immediate effect will be
1940 You will probably need to call \cw{midend_size()} after calling this
1941 function, because if the game parameters have been changed since the
1942 last new game then the window size might need to change. (If you
1943 know the parameters \e{haven't} changed, you don't need to do this.)
1945 This function will create a new \c{game_drawstate}, but does not
1946 actually perform a redraw (since you often need to call
1947 \cw{midend_size()} before the redraw can be done). So after calling
1948 this function and after calling \cw{midend_size()}, you should then
1949 call \cw{midend_redraw()}. (It is not necessary to call
1950 \cw{midend_force_redraw()}; that will discard the draw state and
1951 create a fresh one, which is unnecessary in this case since there's
1952 a fresh one already. It would work, but it's usually excessive.)
1954 \H{midend-restart-game} \cw{midend_restart_game()}
1956 \c void midend_restart_game(midend_data *me);
1958 This function causes the current game to be restarted. This is done
1959 by placing a new copy of the original game state on the end of the
1960 undo list (so that an accidental restart can be undone).
1962 This function automatically causes a redraw, i.e. the front end can
1963 expect its drawing API to be called from \e{within} a call to this
1966 \H{midend-force-redraw} \cw{midend_force_redraw()}
1968 \c void midend_force_redraw(midend_data *me);
1970 Forces a complete redraw of the puzzle window, by means of
1971 discarding the current \c{game_drawstate} and creating a new one
1972 from scratch before calling the game's \cw{redraw()} function.
1974 The front end can expect its drawing API to be called from within a
1975 call to this function.
1977 \H{midend-redraw} \cw{midend_redraw()}
1979 \c void midend_redraw(midend_data *me);
1981 Causes a partial redraw of the puzzle window, by means of simply
1982 calling the game's \cw{redraw()} function. (That is, the only things
1983 redrawn will be things that have changed since the last redraw.)
1985 The front end can expect its drawing API to be called from within a
1986 call to this function.
1988 \H{midend-process-key} \cw{midend_process_key()}
1990 \c int midend_process_key(midend_data *me, int x, int y, int button);
1992 The front end calls this function to report a mouse or keyboard
1993 event. The parameters \c{x}, \c{y} and \c{button} are almost
1994 identical to the ones passed to the back end function
1995 \cw{interpret_move()} (\k{backend-interpret-move}), except that the
1996 front end is \e{not} required to provide the guarantees about mouse
1997 event ordering. The mid-end will sort out multiple simultaneous
1998 button presses and changes of button; the front end's responsibility
1999 is simply to pass on the mouse events it receives as accurately as
2002 (Some platforms may need to emulate absent mouse buttons by means of
2003 using a modifier key such as Shift with another mouse button. This
2004 tends to mean that if Shift is pressed or released in the middle of
2005 a mouse drag, the mid-end will suddenly stop receiving, say,
2006 \cw{LEFT_DRAG} events and start receiving \cw{RIGHT_DRAG}s, with no
2007 intervening button release or press events. This too is something
2008 which the mid-end will sort out for you; the front end has no
2009 obligation to maintain sanity in this area.)
2011 The front end \e{should}, however, always eventually send some kind
2012 of button release. On some platforms this requires special effort:
2013 Windows, for example, requires a call to the system API function
2014 \cw{SetCapture()} in order to ensure that your window receives a
2015 mouse-up event even if the pointer has left the window by the time
2016 the mouse button is released. On any platform that requires this
2017 sort of thing, the front end \e{is} responsible for doing it.
2019 Calling this function is very likely to result in calls back to the
2020 front end's drawing API and/or \cw{activate_timer()}
2021 (\k{frontend-activate-timer}).
2023 \H{midend-colours} \cw{midend_colours()}
2025 \c float *midend_colours(midend_data *me, int *ncolours);
2027 Returns an array of the colours required by the game, in exactly the
2028 same format as that returned by the back end function \cw{colours()}
2029 (\k{backend-colours}). Front ends should call this function rather
2030 than calling the back end's version directly, since the mid-end adds
2031 standard customisation facilities. (At the time of writing, those
2032 customisation facilities are implemented hackily by means of
2033 environment variables, but it's not impossible that they may become
2034 more full and formal in future.)
2036 \H{midend-timer} \cw{midend_timer()}
2038 \c void midend_timer(midend_data *me, float tplus);
2040 If the mid-end has called \cw{activate_timer()}
2041 (\k{frontend-activate-timer}) to request regular callbacks for
2042 purposes of animation or timing, this is the function the front end
2043 should call on a regular basis. The argument \c{tplus} gives the
2044 time, in seconds, since the last time either this function was
2045 called or \cw{activate_timer()} was invoked.
2047 One of the major purposes of timing in the mid-end is to perform
2048 move animation. Therefore, calling this function is very likely to
2049 result in calls back to the front end's drawing API.
2051 \H{midend-num-presets} \cw{midend_num_presets()}
2053 \c int midend_num_presets(midend_data *me);
2055 Returns the number of game parameter presets supplied by this game.
2056 Front ends should use this function and \cw{midend_fetch_preset()}
2057 to configure their presets menu rather than calling the back end
2058 directly, since the mid-end adds standard customisation facilities.
2059 (At the time of writing, those customisation facilities are
2060 implemented hackily by means of environment variables, but it's not
2061 impossible that they may become more full and formal in future.)
2063 \H{midend-fetch-preset} \cw{midend_fetch_preset()}
2065 \c void midend_fetch_preset(midend_data *me, int n,
2066 \c char **name, game_params **params);
2068 Returns one of the preset game parameter structures for the game. On
2069 input \c{n} must be a non-negative integer and less than the value
2070 returned from \cw{midend_num_presets()}. On output, \c{*name} is set
2071 to an ASCII string suitable for entering in the game's presets menu,
2072 and \c{*params} is set to the corresponding \c{game_params}
2075 Both of the two output values are dynamically allocated, but they
2076 are owned by the mid-end structure: the front end should not ever
2077 free them directly, because they will be freed automatically during
2080 \H{midend-wants-statusbar} \cw{midend_wants_statusbar()}
2082 \c int midend_wants_statusbar(midend_data *me);
2084 This function returns \cw{TRUE} if the puzzle has a use for a
2085 textual status line (to display score, completion status, currently
2086 active tiles, time, or anything else).
2088 Front ends should call this function rather than talking directly to
2091 \H{midend-get-config} \cw{midend_get_config()}
2093 \c config_item *midend_get_config(midend_data *me, int which,
2094 \c char **wintitle);
2096 Returns a dialog box description for user configuration.
2098 On input, \cw{which} should be set to one of three values, which
2099 select which of the various dialog box descriptions is returned:
2101 \dt \cw{CFG_SETTINGS}
2103 \dd Requests the GUI parameter configuration box generated by the
2104 puzzle itself. This should be used when the user selects \q{Custom}
2105 from the game types menu (or equivalent). The mid-end passes this
2106 request on to the back end function \cw{configure()}
2107 (\k{backend-configure}).
2111 \dd Requests a box suitable for entering a descriptive game ID (and
2112 viewing the existing one). The mid-end generates this dialog box
2113 description itself. This should be used when the user selects
2114 \q{Specific} from the game menu (or equivalent).
2118 \dd Requests a box suitable for entering a random-seed game ID (and
2119 viewing the existing one). The mid-end generates this dialog box
2120 description itself. This should be used when the user selects
2121 \q{Random Seed} from the game menu (or equivalent).
2123 The returned value is an array of \cw{config_item}s, exactly as
2124 described in \k{backend-configure}. Another returned value is an
2125 ASCII string giving a suitable title for the configuration window,
2128 Both returned values are dynamically allocated and will need to be
2129 freed. The window title can be freed in the obvious way; the
2130 \cw{config_item} array is a slightly complex structure, so a utility
2131 function \cw{free_cfg()} is provided to free it for you. See
2134 (Of course, you will probably not want to free the \cw{config_item}
2135 array until the dialog box is dismissed, because before then you
2136 will probably need to pass it to \cw{midend_set_config}.)
2138 \H{midend-set-config} \cw{midend_set_config()}
2140 \c char *midend_set_config(midend_data *me, int which,
2141 \c config_item *cfg);
2143 Passes the mid-end the results of a configuration dialog box.
2144 \c{which} should have the same value which it had when
2145 \cw{midend_get_config()} was called; \c{cfg} should be the array of
2146 \c{config_item}s returned from \cw{midend_get_config()}, modified to
2147 contain the results of the user's editing operations.
2149 This function returns \cw{NULL} on success, or otherwise (if the
2150 configuration data was in some way invalid) an ASCII string
2151 containing an error message suitable for showing to the user.
2153 If the function succeeds, it is likely that the game parameters will
2154 have been changed and it is certain that a new game will be
2155 requested. The front end should therefore call
2156 \cw{midend_new_game()}, and probably also re-think the window size
2157 using \cw{midend_size()} and eventually perform a refresh using
2158 \cw{midend_redraw()}.
2160 \H{midend-game-id} \cw{midend_game_id()}
2162 \c char *midend_game_id(midend_data *me, char *id);
2164 Passes the mid-end a string game ID (of any of the valid forms
2165 \cq{params}, \cq{params:description} or \cq{params#seed}) which the
2166 mid-end will process and use for the next generated game.
2168 This function returns \cw{NULL} on success, or otherwise (if the
2169 configuration data was in some way invalid) an ASCII string
2170 containing an error message (not dynamically allocated) suitable for
2171 showing to the user. In the event of an error, the mid-end's
2172 internal state will be left exactly as it was before the call.
2174 If the function succeeds, it is likely that the game parameters will
2175 have been changed and it is certain that a new game will be
2176 requested. The front end should therefore call
2177 \cw{midend_new_game()}, and probably also re-think the window size
2178 using \cw{midend_size()} and eventually case a refresh using
2179 \cw{midend_redraw()}.
2181 \H{midend-text-format} \cw{midend_text_format()}
2183 \c char *midend_text_format(midend_data *me);
2185 Formats the current game's current state as ASCII text suitable for
2186 copying to the clipboard. The returned string is dynamically
2189 You should not call this function if the game's
2190 \c{can_format_as_text} flag is \cw{FALSE}.
2192 If the returned string contains multiple lines (which is likely), it
2193 will use the normal C line ending convention (\cw{\\n} only). On
2194 platforms which use a different line ending convention for data in
2195 the clipboard, it is the front end's responsibility to perform the
2198 \H{midend-solve} \cw{midend_solve()}
2200 \c char *midend_solve(midend_data *me);
2202 Requests the mid-end to perform a Solve operation.
2204 On success, \cw{NULL} is returned. On failure, an error message (not
2205 dynamically allocated) is returned, suitable for showing to the
2208 The front end can expect its drawing API and/or
2209 \cw{activate_timer()} to be called from within a call to this
2212 \H{midend-rewrite-statusbar} \cw{midend_rewrite_statusbar()}
2214 \c char *midend_rewrite_statusbar(midend_data *me, char *text);
2216 The front end should call this function from within
2217 \cw{status_bar()} (\k{drawing-status-bar}). It should be passed the
2218 string that was passed by the back end to \cw{status_bar()}; it will
2219 return a dynamically allocated string adjusted by the mid-end.
2220 (Specifically, adjusted to include the timer if the game is a timed
2221 one.) The returned value should be placed in the actual status bar
2222 in place of the input value.
2224 (This is a nasty piece of architecture; I apologise for it. It would
2225 seem a lot more pleasant to have the back end pass its status bar
2226 text to the mid-end, which in turn would rewrite it and pass it on
2227 to the front end, so that each front end needed to do nothing
2228 strange. The main reason why I haven't done this is because it means
2229 the back end redraw function would need to be passed a mid-end
2230 pointer \e{as well} as a front end pointer, which seemed like an
2231 excessive proliferation of opaque handles. The only way to avoid
2232 that proliferation would be to have all the drawing API functions
2233 also gatewayed through the mid-end, and that seemed like an
2234 excessive proliferation of wrapper functions. The current setup
2235 isn't nice, but it has minimal impact and I'm unconvinced that any
2236 of the other options are an improvement.)
2238 \H{midend-serialise} \cw{midend_serialise()}
2240 \c void midend_serialise(midend_data *me,
2241 \c void (*write)(void *ctx, void *buf, int len),
2244 Calling this function causes the mid-end to convert its entire
2245 internal state into a long ASCII text string, and to pass that
2246 string (piece by piece) to the supplied \c{write} function.
2248 Desktop implementations can use this function to save a game in any
2249 state (including half-finished) to a disk file, by supplying a
2250 \c{write} function which is a wrapper on \cw{fwrite()} (or local
2251 equivalent). Other implementations may find other uses for it, such
2252 as compressing the large and sprawling mid-end state into a
2253 manageable amount of memory when a palmtop application is suspended
2254 so that another one can run; in this case \cw{write} might want to
2255 write to a memory buffer rather than a file. There may be other uses
2258 This function will call back to the supplied \c{write} function a
2259 number of times, with the first parameter (\c{ctx}) equal to
2260 \c{wctx}, and the other two parameters pointing at a piece of the
2263 \H{midend-deserialise} \cw{midend_deserialise()}
2265 \c char *midend_deserialise(midend_data *me,
2266 \c int (*read)(void *ctx, void *buf, int len),
2269 This function is the counterpart to \cw{midend_serialise()}. It
2270 calls the supplied \cw{read} function repeatedly to read a quantity
2271 of data, and attempts to interpret that data as a serialised mid-end
2272 as output by \cw{midend_serialise()}.
2274 The \cw{read} function is called with the first parameter (\c{ctx})
2275 equal to \c{rctx}, and should attempt to read \c{len} bytes of data
2276 into the buffer pointed to by \c{buf}. It should return \cw{FALSE}
2277 on failure or \cw{TRUE} on success. It should not report success
2278 unless it has filled the entire buffer; on platforms which might be
2279 reading from a pipe or other blocking data source, \c{read} is
2280 responsible for looping until the whole buffer has been filled.
2282 If the de-serialisation operation is successful, the mid-end's
2283 internal data structures will be replaced by the results of the
2284 load, and \cw{NULL} will be returned. Otherwise, the mid-end's state
2285 will be completely unchanged and an error message (typically some
2286 variation on \q{save file is corrupt}) will be returned. As usual,
2287 the error message string is not dynamically allocated.
2289 If this function succeeds, it is likely that the game parameters
2290 will have been changed. The front end should therefore probably
2291 re-think the window size using \cw{midend_size()}, and probably
2292 cause a refresh using \cw{midend_redraw()}.
2294 Because each mid-end is tied to a specific game back end, this
2295 function will fail if you attempt to read in a save file generated
2296 by a different game from the one configured in this mid-end, even if
2297 your application is a monolithic one containing all the puzzles. (It
2298 would be pretty easy to write a function which would look at a save
2299 file and determine which game it was for; any front end implementor
2300 who needs such a function can probably be accommodated.)
2302 \H{frontend-backend} Direct reference to the back end structure by
2305 Although \e{most} things the front end needs done should be done by
2306 calling the mid-end, there are a few situations in which the front
2307 end needs to refer directly to the game back end structure.
2309 The most obvious of these is
2311 \b passing the game back end as a parameter to \cw{midend_new()}.
2313 There are a few other back end features which are not wrapped by the
2314 mid-end because there didn't seem much point in doing so:
2316 \b fetching the \c{name} field to use in window titles and similar
2318 \b reading the \c{can_configure}, \c{can_solve} and
2319 \c{can_format_as_text} fields to decide whether to add those items
2320 to the menu bar or equivalent
2322 \b reading the \c{winhelp_topic} field (Windows only)
2324 \b the GTK front end provides a \cq{--generate} command-line option
2325 which directly calls the back end to do most of its work. This is
2326 not really part of the main front end code, though, and I'm not sure
2329 In order to find the game back end structure, the front end does one
2332 \b If the particular front end is compiling a separate binary per
2333 game, then the back end structure is a global variable with the
2334 standard name \cq{thegame}:
2338 \c extern const game thegame;
2342 \b If the front end is compiled as a monolithic application
2343 containing all the puzzles together (in which case the preprocessor
2344 symbol \cw{COMBINED} must be defined when compiling most of the code
2345 base), then there will be two global variables defined:
2349 \c extern const game *gamelist[];
2350 \c extern const int gamecount;
2352 \c{gamelist} will be an array of \c{gamecount} game structures,
2353 declared in the source module \c{list.c}. The application should
2354 search that array for the game it wants, probably by reaching into
2355 each game structure and looking at its \c{name} field.
2359 \H{frontend-api} Mid-end to front-end calls
2361 This section describes the small number of functions which a front
2362 end must provide to be called by the mid-end or other standard
2365 \H{frontend-get-random-seed} \cw{get_random_seed()}
2367 \c void get_random_seed(void **randseed, int *randseedsize);
2369 This function is called by a new mid-end, and also occasionally by
2370 game back ends. Its job is to return a piece of data suitable for
2371 using as a seed for initialisation of a new \c{random_state}.
2373 On exit, \c{*randseed} should be set to point at a newly allocated
2374 piece of memory containing some seed data, and \c{*randseedsize}
2375 should be set to the length of that data.
2377 A simple and entirely adequate implementation is to return a piece
2378 of data containing the current system time at the highest
2379 conveniently available resolution.
2381 \H{frontend-activate-timer} \cw{activate_timer()}
2383 \c void activate_timer(frontend *fe);
2385 This is called by the mid-end to request that the front end begin
2386 calling it back at regular intervals.
2388 The timeout interval is left up to the front end; the finer it is,
2389 the smoother move animations will be, but the more CPU time will be
2390 used. Current front ends use values around 20ms (i.e. 50Hz).
2392 After this function is called, the mid-end will expect to receive
2393 calls to \cw{midend_timer()} on a regular basis.
2395 \H{frontend-deactivate-timer} \cw{deactivate_timer()}
2397 \c void deactivate_timer(frontend *fe);
2399 This is called by the mid-end to request that the front end stop
2400 calling \cw{midend_timer()}.
2402 \H{frontend-fatal} \cw{fatal()}
2404 \c void fatal(char *fmt, ...);
2406 This is called by some utility functions if they encounter a
2407 genuinely fatal error such as running out of memory. It is a
2408 variadic function in the style of \cw{printf()}, and is expected to
2409 show the formatted error message to the user any way it can and then
2410 terminate the application. It must not return.
2412 \C{utils} Utility APIs
2414 This chapter documents a variety of utility APIs provided for the
2415 general use of the rest of the Puzzles code.
2417 \H{utils-random} Random number generation
2419 Platforms' local random number generators vary widely in quality and
2420 seed size. Puzzles therefore supplies its own high-quality random
2421 number generator, with the additional advantage of giving the same
2422 results if fed the same seed data on different platforms. This
2423 allows game random seeds to be exchanged between different ports of
2424 Puzzles and still generate the same games.
2426 Unlike the ANSI C \cw{rand()} function, the Puzzles random number
2427 generator has an \e{explicit} state object called a
2428 \c{random_state}. One of these is managed by each mid-end, for
2429 example, and passed to the back end to generate a game with.
2431 \S{utils-random-init} \cw{random_init()}
2433 \c random_state *random_init(char *seed, int len);
2435 Allocates, initialises and returns a new \c{random_state}. The input
2436 data is used as the seed for the random number stream (i.e. using
2437 the same seed at a later time will generate the same stream).
2439 The seed data can be any data at all; there is no requirement to use
2440 printable ASCII, or NUL-terminated strings, or anything like that.
2442 \S{utils-random-free} \cw{random_free()}
2444 \c void random_free(random_state *state);
2446 Frees a \c{random_state}.
2448 \S{utils-random-bits} \cw{random_bits()}
2450 \c unsigned long random_bits(random_state *state, int bits);
2452 Returns a random number from 0 to \cw{2^bits-1} inclusive. \c{bits}
2453 should be between 1 and 32 inclusive.
2455 \S{utils-random-upto} \cw{random_upto()}
2457 \c unsigned long random_upto(random_state *state, unsigned long limit);
2459 Returns a random number from 0 to \cw{limit-1} inclusive.
2461 \S{utils-random-state-encode} \cw{random_state_encode()}
2463 \c char *random_state_encode(random_state *state);
2465 Encodes the entire contents of a \c{random_state} in printable
2466 ASCII. Returns a dynamically allocated string containing that
2467 encoding. This can subsequently be passed to
2468 \cw{random_state_decode()} to reconstruct the same \c{random_state}.
2470 \S{utils-random-state-decode} \cw{random_state_decode()}
2472 \c random_state *random_state_decode(char *input);
2474 Decodes a string generated by \cw{random_state_encode()} and
2475 reconstructs an equivalent \c{random_state} to the one encoded, i.e.
2476 it should produce the same stream of random numbers.
2478 This function has no error reporting; if you pass it an invalid
2479 string it will simply generate an arbitrary random state, which may
2480 turn out to be noticeably non-random.
2482 \S{utils-shuffle} \cw{shuffle()}
2484 \c void shuffle(void *array, int nelts, int eltsize, random_state *rs);
2486 Shuffles an array into a random order. The interface is much like
2487 ANSI C \cw{qsort()}, except that there's no need for a compare
2490 \c{array} is a pointer to the first element of the array. \c{nelts}
2491 is the number of elements in the array; \c{eltsize} is the size of a
2492 single element (typically measured using \c{sizeof}). \c{rs} is a
2493 \c{random_state} used to generate all the random numbers for the
2496 \H{utils-alloc} Memory allocation
2498 Puzzles has some central wrappers on the standard memory allocation
2499 functions, which provide compile-time type checking, and run-time
2500 error checking by means of quitting the application if it runs out
2501 of memory. This doesn't provide the best possible recovery from
2502 memory shortage, but on the other hand it greatly simplifies the
2503 rest of the code, because nothing else anywhere needs to worry about
2504 \cw{NULL} returns from allocation.
2506 \S{utils-snew} \cw{snew()}
2508 \c var = snew(type);
2511 This macro takes a single argument which is a \e{type name}. It
2512 allocates space for one object of that type. If allocation fails it
2513 will call \cw{fatal()} and not return; so if it does return, you can
2514 be confident that its return value is non-\cw{NULL}.
2516 The return value is cast to the specified type, so that the compiler
2517 will type-check it against the variable you assign it into. Thus,
2518 this ensures you don't accidentally allocate memory the size of the
2519 wrong type and assign it into a variable of the right one (or vice
2522 \S{utils-snewn} \cw{snewn()}
2524 \c var = snewn(n, type);
2527 This macro is the array form of \cw{snew()}. It takes two arguments;
2528 the first is a number, and the second is a type name. It allocates
2529 space for that many objects of that type, and returns a type-checked
2530 non-\cw{NULL} pointer just as \cw{snew()} does.
2532 \S{utils-sresize} \cw{sresize()}
2534 \c var = sresize(var, n, type);
2537 This macro is a type-checked form of \cw{realloc()}. It takes three
2538 arguments: an input memory block, a new size in elements, and a
2539 type. It re-sizes the input memory block to a size sufficient to
2540 contain that many elements of that type. It returns a type-checked
2541 non-\cw{NULL} pointer, like \cw{snew()} and \cw{snewn()}.
2543 The input memory block can be \cw{NULL}, in which case this function
2544 will behave exactly like \cw{snewn()}. (In principle any
2545 ANSI-compliant \cw{realloc()} implementation ought to cope with
2546 this, but I've never quite trusted it to work everywhere.)
2548 \S{utils-sfree} \cw{sfree()}
2550 \c void sfree(void *p);
2552 This function is pretty much equivalent to \cw{free()}. It is
2553 provided with a dynamically allocated block, and frees it.
2555 The input memory block can be \cw{NULL}, in which case this function
2556 will do nothing. (In principle any ANSI-compliant \cw{free()}
2557 implementation ought to cope with this, but I've never quite trusted
2558 it to work everywhere.)
2560 \S{utils-dupstr} \cw{dupstr()}
2562 \c char *dupstr(const char *s);
2564 This function dynamically allocates a duplicate of a C string. Like
2565 the \cw{snew()} functions, it guarantees to return non-\cw{NULL} or
2568 (Many platforms provide the function \cw{strdup()}. As well as
2569 guaranteeing never to return \cw{NULL}, my version has the advantage
2570 of being defined \e{everywhere}, rather than inconveniently not
2573 \S{utils-free-cfg} \cw{free_cfg()}
2575 \c void free_cfg(config_item *cfg);
2577 This function correctly frees an array of \c{config_item}s,
2578 including walking the array until it gets to the end and freeing
2579 precisely those \c{sval} fields which are expected to be dynamically
2582 (See \k{backend-configure} for details of the \c{config_item}
2585 \H{utils-tree234} Sorted and counted tree functions
2587 Many games require complex algorithms for generating random puzzles,
2588 and some require moderately complex algorithms even during play. A
2589 common requirement during these algorithms is for a means of
2590 maintaining sorted or unsorted lists of items, such that items can
2591 be removed and added conveniently.
2593 For general use, Puzzles provides the following set of functions
2594 which maintain 2-3-4 trees in memory. (A 2-3-4 tree is a balanced
2595 tree structure, with the property that all lookups, insertions,
2596 deletions, splits and joins can be done in \cw{O(log N)} time.)
2598 All these functions expect you to be storing a tree of \c{void *}
2599 pointers. You can put anything you like in those pointers.
2601 By the use of per-node element counts, these tree structures have
2602 the slightly unusual ability to look elements up by their numeric
2603 index within the list represented by the tree. This means that they
2604 can be used to store an unsorted list (in which case, every time you
2605 insert a new element, you must explicitly specify the position where
2606 you wish to insert it). They can also do numeric lookups in a sorted
2607 tree, which might be useful for (for example) tracking the median of
2608 a changing data set.
2610 As well as storing sorted lists, these functions can be used for
2611 storing \q{maps} (associative arrays), by defining each element of a
2612 tree to be a (key, value) pair.
2614 \S{utils-newtree234} \cw{newtree234()}
2616 \c tree234 *newtree234(cmpfn234 cmp);
2618 Creates a new empty tree, and returns a pointer to it.
2620 The parameter \c{cmp} determines the sorting criterion on the tree.
2623 \c typedef int (*cmpfn234)(void *, void *);
2625 If you want a sorted tree, you should provide a function matching
2626 this prototype, which returns like \cw{strcmp()} does (negative if
2627 the first argument is smaller than the second, positive if it is
2628 bigger, zero if they compare equal). In this case, the function
2629 \cw{addpos234()} will not be usable on your tree (because all
2630 insertions must respect the sorting order).
2632 If you want an unsorted tree, pass \cw{NULL}. In this case you will
2633 not be able to use either \cw{add234()} or \cw{del234()}, or any
2634 other function such as \cw{find234()} which depends on a sorting
2635 order. Your tree will become something more like an array, except
2636 that it will efficiently support insertion and deletion as well as
2637 lookups by numeric index.
2639 \S{utils-freetree234} \cw{freetree234()}
2641 \c void freetree234(tree234 *t);
2643 Frees a tree. This function will not free the \e{elements} of the
2644 tree (because they might not be dynamically allocated, or you might
2645 be storing the same set of elements in more than one tree); it will
2646 just free the tree structure itself. If you want to free all the
2647 elements of a tree, you should empty it before passing it to
2648 \cw{freetree234()}, by means of code along the lines of
2650 \c while ((element = delpos234(tree, 0)) != NULL)
2651 \c sfree(element); /* or some more complicated free function */
2652 \e iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
2654 \S{utils-add234} \cw{add234()}
2656 \c void *add234(tree234 *t, void *e);
2658 Inserts a new element \c{e} into the tree \c{t}. This function
2659 expects the tree to be sorted; the new element is inserted according
2662 If an element comparing equal to \c{e} is already in the tree, then
2663 the insertion will fail, and the return value will be the existing
2664 element. Otherwise, the insertion succeeds, and \c{e} is returned.
2666 \S{utils-addpos234} \cw{addpos234()}
2668 \c void *addpos234(tree234 *t, void *e, int index);
2670 Inserts a new element into an unsorted tree. Since there is no
2671 sorting order to dictate where the new element goes, you must
2672 specify where you want it to go. Setting \c{index} to zero puts the
2673 new element right at the start of the list; setting \c{index} to the
2674 current number of elements in the tree puts the new element at the
2677 Return value is \c{e}, in line with \cw{add234()} (although this
2678 function cannot fail except by running out of memory, in which case
2679 it will bomb out and die rather than returning an error indication).
2681 \S{utils-index234} \cw{index234()}
2683 \c void *index234(tree234 *t, int index);
2685 Returns a pointer to the \c{index}th element of the tree, or
2686 \cw{NULL} if \c{index} is out of range. Elements of the tree are
2689 \S{utils-find234} \cw{find234()}
2691 \c void *find234(tree234 *t, void *e, cmpfn234 cmp);
2693 Searches for an element comparing equal to \c{e} in a sorted tree.
2695 If \c{cmp} is \cw{NULL}, the tree's ordinary comparison function
2696 will be used to perform the search. However, sometimes you don't
2697 want that; suppose, for example, each of your elements is a big
2698 structure containing a \c{char *} name field, and you want to find
2699 the element with a given name. You \e{could} achieve this by
2700 constructing a fake element structure, setting its name field
2701 appropriately, and passing it to \cw{find234()}, but you might find
2702 it more convenient to pass \e{just} a name string to \cw{find234()},
2703 supplying an alternative comparison function which expects one of
2704 its arguments to be a bare name and the other to be a large
2705 structure containing a name field.
2707 Therefore, if \c{cmp} is not \cw{NULL}, then it will be used to
2708 compare \c{e} to elements of the tree. The first argument passed to
2709 \c{cmp} will always be \c{e}; the second will be an element of the
2712 (See \k{utils-newtree234} for the definition of the \c{cmpfn234}
2713 function pointer type.)
2715 The returned value is the element found, or \cw{NULL} if the search
2718 \S{utils-findrel234} \cw{findrel234()}
2720 \c void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);
2722 This function is like \cw{find234()}, but has the additional ability
2723 to do a \e{relative} search. The additional parameter \c{relation}
2724 can be one of the following values:
2728 \dd Find only an element that compares equal to \c{e}. This is
2729 exactly the behaviour of \cw{find234()}.
2733 \dd Find the greatest element that compares strictly less than
2734 \c{e}. \c{e} may be \cw{NULL}, in which case it finds the greatest
2735 element in the whole tree (which could also be done by
2736 \cw{index234(t, count234(t)-1)}).
2740 \dd Find the greatest element that compares less than or equal to
2741 \c{e}. (That is, find an element that compares equal to \c{e} if
2742 possible, but failing that settle for something just less than it.)
2746 \dd Find the smallest element that compares strictly greater than
2747 \c{e}. \c{e} may be \cw{NULL}, in which case it finds the smallest
2748 element in the whole tree (which could also be done by
2749 \cw{index234(t, 0)}).
2753 \dd Find the smallest element that compares greater than or equal to
2754 \c{e}. (That is, find an element that compares equal to \c{e} if
2755 possible, but failing that settle for something just bigger than
2758 Return value, as before, is the element found or \cw{NULL} if no
2759 element satisfied the search criterion.
2761 \S{utils-findpos234} \cw{findpos234()}
2763 \c void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);
2765 This function is like \cw{find234()}, but has the additional feature
2766 of returning the index of the element found in the tree; that index
2767 is written to \c{*index} in the event of a successful search (a
2768 non-\cw{NULL} return value).
2770 \c{index} may be \cw{NULL}, in which case this function behaves
2771 exactly like \cw{find234()}.
2773 \S{utils-findrelpos234} \cw{findrelpos234()}
2775 \c void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
2778 This function combines all the features of \cw{findrel234()} and
2781 \S{utils-del234} \cw{del234()}
2783 \c void *del234(tree234 *t, void *e);
2785 Finds an element comparing equal to \c{e} in the tree, deletes it,
2788 The input tree must be sorted.
2790 The element found might be \c{e} itself, or might merely compare
2793 Return value is \cw{NULL} if no such element is found.
2795 \S{utils-delpos234} \cw{delpos234()}
2797 \c void *delpos234(tree234 *t, int index);
2799 Deletes the element at position \c{index} in the tree, and returns
2802 Return value is \cw{NULL} if the index is out of range.
2804 \S{utils-count234} \cw{count234()}
2806 \c int count234(tree234 *t);
2808 Returns the number of elements currently in the tree.
2810 \S{utils-splitpos234} \cw{splitpos234()}
2812 \c tree234 *splitpos234(tree234 *t, int index, int before);
2814 Splits the input tree into two pieces at a given position, and
2815 creates a new tree containing all the elements on one side of that
2818 If \c{before} is \cw{TRUE}, then all the items at or after position
2819 \c{index} are left in the input tree, and the items before that
2820 point are returned in the new tree. Otherwise, the reverse happens:
2821 all the items at or after \c{index} are moved into the new tree, and
2822 those before that point are left in the old one.
2824 If \c{index} is equal to 0 or to the number of elements in the input
2825 tree, then one of the two trees will end up empty (and this is not
2826 an error condition). If \c{index} is further out of range in either
2827 direction, the operation will fail completely and return \cw{NULL}.
2829 This operation completes in \cw{O(log N)} time, no matter how large
2830 the tree or how balanced or unbalanced the split.
2832 \S{utils-split234} \cw{split234()}
2834 \c tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);
2836 Splits a sorted tree according to its sort order.
2838 \c{rel} can be any of the relation constants described in
2839 \k{utils-findrel234}, \e{except} for \cw{REL234_EQ}. All the
2840 elements having that relation to \c{e} will be transferred into the
2841 new tree; the rest will be left in the old one.
2843 The parameter \c{cmp} has the same semantics as it does in
2844 \cw{find234()}: if it is not \cw{NULL}, it will be used in place of
2845 the tree's own comparison function when comparing elements to \c{e},
2846 in such a way that \c{e} itself is always the first of its two
2849 Again, this operation completes in \cw{O(log N)} time, no matter how
2850 large the tree or how balanced or unbalanced the split.
2852 \S{utils-join234} \cw{join234()}
2854 \c tree234 *join234(tree234 *t1, tree234 *t2);
2856 Joins two trees together by concatenating the lists they represent.
2857 All the elements of \c{t2} are moved into \c{t1}, in such a way that
2858 they appear \e{after} the elements of \c{t1}. The tree \c{t2} is
2859 freed; the return value is \c{t1}.
2861 If you apply this function to a sorted tree and it violates the sort
2862 order (i.e. the smallest element in \c{t2} is smaller than or equal
2863 to the largest element in \c{t1}), the operation will fail and
2866 This operation completes in \cw{O(log N)} time, no matter how large
2867 the trees being joined together.
2869 \S{utils-join234r} \cw{join234r()}
2871 \c tree234 *join234r(tree234 *t1, tree234 *t2);
2873 Joins two trees together in exactly the same way as \cw{join234()},
2874 but this time the combined tree is returned in \c{t2}, and \c{t1} is
2875 destroyed. The elements in \c{t1} still appear before those in
2878 Again, this operation completes in \cw{O(log N)} time, no matter how
2879 large the trees being joined together.
2881 \S{utils-copytree234} \cw{copytree234()}
2883 \c tree234 *copytree234(tree234 *t, copyfn234 copyfn,
2884 \c void *copyfnstate);
2886 Makes a copy of an entire tree.
2888 If \c{copyfn} is \cw{NULL}, the tree will be copied but the elements
2889 will not be; i.e. the new tree will contain pointers to exactly the
2890 same physical elements as the old one.
2892 If you want to copy each actual element during the operation, you
2893 can instead pass a function in \c{copyfn} which makes a copy of each
2894 element. That function has the prototype
2896 \c typedef void *(*copyfn234)(void *state, void *element);
2898 and every time it is called, the \c{state} parameter will be set to
2899 the value you passed in as \c{copyfnstate}.
2901 \H{utils-misc} Miscellaneous utility functions and macros
2903 This section contains all the utility functions which didn't
2904 sensibly fit anywhere else.
2906 \S{utils-truefalse} \cw{TRUE} and \cw{FALSE}
2908 The main Puzzles header file defines the macros \cw{TRUE} and
2909 \cw{FALSE}, which are used throughout the code in place of 0 and 1
2910 to indicate that the values are in a boolean context. For code base
2911 consistency, I'd prefer it if submissions of new code followed this
2914 \S{utils-maxmin} \cw{max()} and \cw{min()}
2916 The main Puzzles header file defines the pretty standard macros
2917 \cw{max()} and \cw{min()}, each of which is given two arguments and
2918 returns the one which compares greater or less respectively.
2920 These macros may evaluate their arguments multiple times. Avoid side
2923 \S{utils-pi} \cw{PI}
2925 The main Puzzles header file defines a macro \cw{PI} which expands
2926 to a floating-point constant representing pi.
2928 (I've never understood why ANSI's \cw{<math.h>} doesn't define this.
2931 \S{utils-obfuscate-bitmap} \cw{obfuscate_bitmap()}
2933 \c void obfuscate_bitmap(unsigned char *bmp, int bits, int decode);
2935 This function obscures the contents of a piece of data, by
2936 cryptographic methods. It is useful for games of hidden information
2937 (such as Mines, Guess or Black Box), in which the game ID
2938 theoretically reveals all the information the player is supposed to
2939 be trying to guess. So in order that players should be able to send
2940 game IDs to one another without accidentally spoiling the resulting
2941 game by looking at them, these games obfuscate their game IDs using
2944 Although the obfuscation function is cryptographic, it cannot
2945 properly be called encryption because it has no key. Therefore,
2946 anybody motivated enough can re-implement it, or hack it out of the
2947 Puzzles source, and strip the obfuscation off one of these game IDs
2948 to see what lies beneath. (Indeed, they could usually do it much
2949 more easily than that, by entering the game ID into their own copy
2950 of the puzzle and hitting Solve.) The aim is not to protect against
2951 a determined attacker; the aim is simply to protect people who
2952 wanted to play the game honestly from \e{accidentally} spoiling
2955 The input argument \c{bmp} points at a piece of memory to be
2956 obfuscated. \c{bits} gives the length of the data. Note that that
2957 length is in \e{bits} rather than bytes: if you ask for obfuscation
2958 of a partial number of bytes, then you will get it. Bytes are
2959 considered to be used from the top down: thus, for example, setting
2960 \c{bits} to 10 will cover the whole of \cw{bmp[0]} and the \e{top
2961 two} bits of \cw{bmp[1]}. The remainder of a partially used byte is
2962 undefined (i.e. it may be corrupted by the function).
2964 The parameter \c{decode} is \cw{FALSE} for an encoding operation,
2965 and \cw{TRUE} for a decoding operation. Each is the inverse of the
2966 other. (There's no particular reason you shouldn't obfuscate by
2967 decoding and restore cleartext by encoding, if you really wanted to;
2968 it should still work.)
2970 The input bitmap is processed in place.
2972 \S{utils-bin2hex} \cw{bin2hex()}
2974 \c char *bin2hex(const unsigned char *in, int inlen);
2976 This function takes an input byte array and converts it into an
2977 ASCII string encoding those bytes in (lower-case) hex. It returns a
2978 dynamically allocated string containing that encoding.
2980 This function is useful for encoding the result of
2981 \cw{obfuscate_bitmap()} in printable ASCII for use in game IDs.
2983 \S{utils-hex2bin} \cw{hex2bin()}
2985 \c unsigned char *hex2bin(const char *in, int outlen);
2987 This function takes an ASCII string containing hex digits, and
2988 converts it back into a byte array of length \c{outlen}. If there
2989 aren't enough hex digits in the string, the contents of the
2990 resulting array will be undefined.
2992 This function is the inverse of \cw{bin2hex()}.
2994 \S{utils-game-mkhighlight} \cw{game_mkhighlight()}
2996 \c void game_mkhighlight(frontend *fe, float *ret,
2997 \c int background, int highlight, int lowlight);
2999 It's reasonably common for a puzzle game's graphics to use
3000 highlights and lowlights to indicate \q{raised} or \q{lowered}
3001 sections. Fifteen, Sixteen and Twiddle are good examples of this.
3003 Puzzles using this graphical style are running a risk if they just
3004 use whatever background colour is supplied to them by the front end,
3005 because that background colour might be too light to see any
3006 highlights on at all. (In particular, it's not unheard of for the
3007 front end to specify a default background colour of white.)
3009 Therefore, such puzzles can call this utility function from their
3010 \cw{colours()} routine (\k{backend-colours}). You pass it your front
3011 end handle, a pointer to the start of your return array, and three
3012 colour indices. It will:
3014 \b call \cw{frontend_default_colour()} (\k{frontend-default-colour})
3015 to fetch the front end's default background colour
3017 \b alter the brightness of that colour if it's unsuitable
3019 \b define brighter and darker variants of the colour to be used as
3020 highlights and lowlights
3022 \b write those results into the relevant positions in the \c{ret}
3025 Thus, \cw{ret[background*3]} to \cw{ret[background*3+2]} will be set
3026 to RGB values defining a sensible background colour, and similary
3027 \c{highlight} and \c{lowlight} will be set to sensible colours.
3029 \C{writing} How to write a new puzzle
3031 This chapter gives a guide to how to actually write a new puzzle:
3032 where to start, what to do first, how to solve common problems.
3034 The previous chapters have been largely composed of facts. This one
3037 \H{writing-editorial} Choosing a puzzle
3039 Before you start writing a puzzle, you have to choose one. Your
3040 taste in puzzle games is up to you, of course; and, in fact, you're
3041 probably reading this guide because you've \e{already} thought of a
3042 game you want to write. But if you want to get it accepted into the
3043 official Puzzles distribution, then there's a criterion it has to
3046 The current Puzzles editorial policy is that all games should be
3047 \e{fair}. A fair game is one which a player can only fail to
3048 complete through demonstrable lack of skill \dash that is, such that
3049 a better player in the same situation would have \e{known} to do
3050 something different.
3052 For a start, that means every game presented to the user must have
3053 \e{at least one solution}. Giving the unsuspecting user a puzzle
3054 which is actually impossible is not acceptable. (There is an
3055 exception: if the user has selected some non-default option which is
3056 clearly labelled as potentially unfair, \e{then} you're allowed to
3057 generate possibly insoluble puzzles, because the user isn't
3058 unsuspecting any more. Same Game and Mines both have options of this
3061 Also, this actually \e{rules out} games such as Klondike, or the
3062 normal form of Mahjong Solitaire. Those games have the property that
3063 even if there is a solution (i.e. some sequence of moves which will
3064 get from the start state to the solved state), the player doesn't
3065 necessarily have enough information to \e{find} that solution. In
3066 both games, it is possible to reach a dead end because you had an
3067 arbitrary choice to make and made it the wrong way. This violates
3068 the fairness criterion, because a better player couldn't have known
3069 they needed to make the other choice.
3071 (GNOME has a variant on Mahjong Solitaire which makes it fair: there
3072 is a Shuffle operation which randomly permutes all the remaining
3073 tiles without changing their positions, which allows you to get out
3074 of a sticky situation. Using this operation adds a 60-second penalty
3075 to your solution time, so it's to the player's advantage to try to
3076 minimise the chance of having to use it. It's still possible to
3077 render the game uncompletable if you end up with only two tiles
3078 vertically stacked, but that's easy to foresee and avoid using a
3079 shuffle operation. This form of the game \e{is} fair. Implementing
3080 it in Puzzles would require an infrastructure change so that the
3081 back end could communicate time penalties to the mid-end, but that
3082 would be easy enough.)
3084 Providing a \e{unique} solution is a little more negotiable; it
3085 depends on the puzzle. Solo would have been of unacceptably low
3086 quality if it didn't always have a unique solution, whereas Twiddle
3087 inherently has multiple solutions by its very nature and it would
3088 have been meaningless to even \e{suggest} making it uniquely
3089 soluble. Somewhere in between, Flip could reasonably be made to have
3090 unique solutions (by enforcing a zero-dimension kernel in every
3091 generated matrix) but it doesn't seem like a serious quality problem
3094 Of course, you don't \e{have} to care about all this. There's
3095 nothing stopping you implementing any puzzle you want to if you're
3096 happy to maintain your puzzle yourself, distribute it from your own
3097 web site, fork the Puzzles code completely, or anything like that.
3098 It's free software; you can do what you like with it. But any game
3099 that you want to be accepted into \e{my} Puzzles code base has to
3100 satisfy the fairness criterion, which means all randomly generated
3101 puzzles must have a solution (unless the user has deliberately
3102 chosen otherwise) and it must be possible \e{in theory} to find that
3103 solution without having to guess.
3105 \H{writing-gs} Getting started
3107 The simplest way to start writing a new puzzle is to copy
3108 \c{nullgame.c}. This is a template puzzle source file which does
3109 almost nothing, but which contains all the back end function
3110 prototypes and declares the back end data structure correctly. It is
3111 built every time the rest of Puzzles is built, to ensure that it
3112 doesn't get out of sync with the code and remains buildable.
3114 So start by copying \c{nullgame.c} into your new source file. Then
3115 you'll gradually add functionality until the very boring Null Game
3116 turns into your real game.
3118 Next you'll need to add your puzzle to the Makefiles, in order to
3119 compile it conveniently. \e{Do not edit the Makefiles}: they are
3120 created automatically by the script \c{mkfiles.pl}, from the file
3121 called \c{Recipe}. Edit \c{Recipe}, and then re-run \c{mkfiles.pl}.
3123 Once your source file is building, you can move on to the fun bit.
3125 \S{writing-generation} Puzzle generation
3127 Randomly generating instances of your puzzle is almost certain to be
3128 the most difficult part of the code, and also the task with the
3129 highest chance of turning out to be completely infeasible. Therefore
3130 I strongly recommend doing it \e{first}, so that if it all goes
3131 horribly wrong you haven't wasted any more time than you absolutely
3132 had to. What I usually do is to take an unmodified \c{nullgame.c},
3133 and start adding code to \cw{new_game_desc()} which tries to
3134 generate a puzzle instance and print it out using \cw{printf()}.
3135 Once that's working, \e{then} I start connecting it up to the return
3136 value of \cw{new_game_desc()}, populating other structures like
3137 \c{game_params}, and generally writing the rest of the source file.
3139 There are many ways to generate a puzzle which is known to be
3140 soluble. In this section I list all the methods I currently know of,
3141 in case any of them can be applied to your puzzle. (Not all of these
3142 methods will work, or in some cases even make sense, for all
3145 Some puzzles are mathematically tractable, meaning you can work out
3146 in advance which instances are soluble. Sixteen, for example, has a
3147 parity constraint in some settings which renders exactly half the
3148 game space unreachable, but it can be mathematically proved that any
3149 position not in that half \e{is} reachable. Therefore, Sixteen's
3150 grid generation simply consists of selecting at random from a well
3151 defined subset of the game space. Cube in its default state is even
3152 easier: \e{every} possible arrangement of the blue squares and the
3153 cube's starting position is soluble!
3155 Another option is to redefine what you mean by \q{soluble}. Black
3156 Box takes this approach. There are layouts of balls in the box which
3157 are completely indistinguishable from one another no matter how many
3158 beams you fire into the box from which angles, which would normally
3159 be grounds for declaring those layouts unfair; but fortunately,
3160 detecting that indistinguishability is computationally easy. So
3161 Black Box doesn't demand that your ball placements match its own; it
3162 merely demands that your ball placements be \e{indistinguishable}
3163 from the ones it was thinking of. If you have an ambiguous puzzle,
3164 then any of the possible answers is considered to be a solution.
3165 Having redefined the rules in that way, any puzzle is soluble again.
3167 Those are the simple techniques. If they don't work, you have to get
3170 One way to generate a soluble puzzle is to start from the solved
3171 state and make inverse moves until you reach a starting state. Then
3172 you know there's a solution, because you can just list the inverse
3173 moves you made and make them in the opposite order to return to the
3176 This method can be simple and effective for puzzles where you get to
3177 decide what's a starting state and what's not. In Pegs, for example,
3178 the generator begins with one peg in the centre of the board and
3179 makes inverse moves until it gets bored; in this puzzle, valid
3180 inverse moves are easy to detect, and \e{any} state that's reachable
3181 from the solved state by inverse moves is a reasonable starting
3182 position. So Pegs just continues making inverse moves until the
3183 board satisfies some criteria about extent and density, and then
3184 stops and declares itself done.
3186 For other puzzles, it can be a lot more difficult. Same Game uses
3187 this strategy too, and it's lucky to get away with it at all: valid
3188 inverse moves aren't easy to find (because although it's easy to
3189 insert additional squares in a Same Game position, it's difficult to
3190 arrange that \e{after} the insertion they aren't adjacent to any
3191 other squares of the same colour), so you're constantly at risk of
3192 running out of options and having to backtrack or start again. Also,
3193 Same Game grids never start off half-empty, which means you can't
3194 just stop when you run out of moves \dash you have to find a way to
3195 fill the grid up \e{completely}.
3197 The other way to generate a puzzle that's soluble is to start from
3198 the other end, and actually write a \e{solver}. This tends to ensure
3199 that a puzzle has a \e{unique} solution over and above having a
3200 solution at all, so it's a good technique to apply to puzzles for
3201 which that's important.
3203 One theoretical drawback of generating soluble puzzles by using a
3204 solver is that your puzzles are restricted in difficulty to those
3205 which the solver can handle. (Most solvers are not fully general:
3206 many sets of puzzle rules are NP-complete or otherwise nasty, so
3207 most solvers can only handle a subset of the theoretically soluble
3208 puzzles.) It's been my experience in practice, however, that this
3209 usually isn't a problem; computers are good at very different things
3210 from humans, and what the computer thinks is nice and easy might
3211 still be pleasantly challenging for a human. For example, when
3212 solving Dominosa puzzles I frequently find myself using a variety of
3213 reasoning techniques that my solver doesn't know about; in
3214 principle, therefore, I should be able to solve the puzzle using
3215 only those techniques it \e{does} know about, but this would involve
3216 repeatedly searching the entire grid for the one simple deduction I
3217 can make. Computers are good at this sort of exhaustive search, but
3218 it's been my experience that human solvers prefer to do more complex
3219 deductions than to spend ages searching for simple ones. So in many
3220 cases I don't find my own playing experience to be limited by the
3221 restrictions on the solver.
3223 (This isn't \e{always} the case. Solo is a counter-example;
3224 generating Solo puzzles using a simple solver does lead to
3225 qualitatively easier puzzles. Therefore I had to make the Solo
3226 solver rather more advanced than most of them.)
3228 There are several different ways to apply a solver to the problem of
3229 generating a soluble puzzle. I list a few of them below.
3231 The simplest approach is brute force: randomly generate a puzzle,
3232 use the solver to see if it's soluble, and if not, throw it away and
3233 try again until you get lucky. This is often a viable technique if
3234 all else fails, but it tends not to scale well: for many puzzle
3235 types, the probability of finding a uniquely soluble instance
3236 decreases sharply as puzzle size goes up, so this technique might
3237 work reasonably fast for small puzzles but take (almost) forever at
3238 larger sizes. Still, if there's no other alternative it can be
3239 usable: Pattern and Dominosa both use this technique. (However,
3240 Dominosa has a means of tweaking the randomly generated grids to
3241 increase the \e{probability} of them being soluble, by ruling out
3242 one of the most common ambiguous cases. This improved generation
3243 speed by over a factor of 10 on the highest preset!)
3245 An approach which can be more scalable involves generating a grid
3246 and then tweaking it to make it soluble. This is the technique used
3247 by Mines and also by Net: first a random puzzle is generated, and
3248 then the solver is run to see how far it gets. Sometimes the solver
3249 will get stuck; when that happens, examine the area it's having
3250 trouble with, and make a small random change in that area to allow
3251 it to make more progress. Continue solving (possibly even without
3252 restarting the solver), tweaking as necessary, until the solver
3253 finishes. Then restart the solver from the beginning to ensure that
3254 the tweaks haven't caused new problems in the process of solving old
3255 ones (which can sometimes happen).
3257 This strategy works well in situations where the usual solver
3258 failure mode is to get stuck in an easily localised spot. Thus it
3259 works well for Net and Mines, whose most common failure mode tends
3260 to be that most of the grid is fine but there are a few widely
3261 separated ambiguous sections; but it would work less well for
3262 Dominosa, in which the way you get stuck is to have scoured the
3263 whole grid and not found anything you can deduce \e{anywhere}. Also,
3264 it relies on there being a low probability that tweaking the grid
3265 introduces a new problem at the same time as solving the old one;
3266 Mines and Net also have the property that most of their deductions
3267 are local, so that it's very unlikely for a tweak to affect
3268 something half way across the grid from the location where it was
3269 applied. In Dominosa, by contrast, a lot of deductions use
3270 information about half the grid (\q{out of all the sixes, only one
3271 is next to a three}, which can depend on the values of up to 32 of
3272 the 56 squares in the default setting!), so this tweaking strategy
3273 would be rather less likely to work well.
3275 A more specialised strategy is that used in Solo. Solo has the
3276 unusual property that the clues (information provided at the
3277 beginning of the puzzle) and the solution (information the user is
3278 required to fill in) are inherently interchangeable; therefore a
3279 simple generation technique is to leave the decision of which
3280 numbers are clues until the last minute. Solo works by first
3281 generating a random \e{filled} grid, and then gradually removing
3282 numbers for as long as the solver reports that it's still soluble.
3283 Unlike the methods described above, this technique \e{cannot} fail
3284 \dash once you've got a filled grid, nothing can stop you from being
3285 able to convert it into a viable puzzle. However, it wouldn't even
3286 be meaningful to apply this technique to (say) Pattern, in which the
3287 clues and the solution occupy completely different spaces.
3289 (Unfortunately, Solo is complicated by the need to provide puzzles
3290 at varying difficulty levels. It's easy enough to generate a puzzle
3291 of \e{at most} a given level of difficulty; you just have a solver
3292 with configurable intelligence, and you set it to a given level and
3293 apply the above technique, thus guaranteeing that the resulting grid
3294 is solvable by someone with at most that much intelligence. However,
3295 generating a puzzle of \e{at least} a given level of difficulty is
3296 rather harder; if you go for \e{at most} Intermediate level, you're
3297 likely to find that you've accidentally generated a Trivial grid a
3298 lot of the time, because removing just one number is sufficient to
3299 take the puzzle from Trivial straight to Ambiguous. In that
3300 situation Solo has no remaining options but to throw the puzzle away
3303 A final strategy is to use the solver \e{during} puzzle
3304 construction: lay out a bit of the grid, run the solver to see what
3305 it allows you to deduce, and then lay out a bit more to allow the
3306 solver to make more progress. There are articles on the web that
3307 recommend constructing Sudoku puzzles by this method (which is
3308 completely the opposite way round to how Solo does it); for Sudoku
3309 it has the advantage that you get to specify your clue squares in
3310 advance (so you can have them make pretty patterns).
3312 Rectangles uses a strategy along these lines. First it generates a
3313 grid by placing the actual rectangles; then it has to decide where
3314 in each rectangle to place a number. It uses a solver to help it
3315 place the numbers in such a way as to ensure a unique solution. It
3316 does this by means of running a test solver, but it runs the solver
3317 \e{before} it's placed any of the numbers \dash which means the
3318 solver must be capable of coping with uncertainty about exactly
3319 where the numbers are! It runs the solver as far as it can until it
3320 gets stuck; then it narrows down the possible positions of a number
3321 in order to allow the solver to make more progress, and so on. Most
3322 of the time this process terminates with the grid fully solved, at
3323 which point any remaining number-placement decisions can be made at
3324 random from the options not so far ruled out. Note that unlike the
3325 Net/Mines tweaking strategy described above, this algorithm does not
3326 require a checking run after it completes: if it finishes
3327 successfully at all, then it has definitely produced a uniquely
3330 Most of the strategies described above are not 100% reliable. Each
3331 one has a failure rate: every so often it has to throw out the whole
3332 grid and generate a fresh one from scratch. (Solo's strategy would
3333 be the exception, if it weren't for the need to provide configurable
3334 difficulty levels.) Occasional failures are not a fundamental
3335 problem in this sort of work, however: it's just a question of
3336 dividing the grid generation time by the success rate (if it takes
3337 10ms to generate a candidate grid and 1/5 of them work, then it will
3338 take 50ms on average to generate a viable one), and seeing whether
3339 the expected time taken to \e{successfully} generate a puzzle is
3340 unacceptably slow. Dominosa's generator has a very low success rate
3341 (about 1 out of 20 candidate grids turn out to be usable, and if you
3342 think \e{that's} bad then go and look at the source code and find
3343 the comment showing what the figures were before the generation-time
3344 tweaks!), but the generator itself is very fast so this doesn't
3345 matter. Rectangles has a slower generator, but fails well under 50%
3348 So don't be discouraged if you have an algorithm that doesn't always
3349 work: if it \e{nearly} always works, that's probably good enough.
3350 The one place where reliability is important is that your algorithm
3351 must never produce false positives: it must not claim a puzzle is
3352 soluble when it isn't. It can produce false negatives (failing to
3353 notice that a puzzle is soluble), and it can fail to generate a
3354 puzzle at all, provided it doesn't do either so often as to become
3357 One last piece of advice: for grid-based puzzles when writing and
3358 testing your generation algorithm, it's almost always a good idea
3359 \e{not} to test it initially on a grid that's square (i.e.
3360 \cw{w==h}), because that way you won't notice if you mistakenly
3361 write \c{w} instead of \c{h} or vice versa somewhere in the code.
3362 Use a rectangular grid for testing, and any size of grid will be
3363 likely to work after that.
3365 \S{writing-textformats} Designing textual description formats
3367 Another aspect of writing a puzzle which is worth putting some
3368 thought into is the design of the various text description formats:
3369 the format of the game parameter encoding, the game description
3370 encoding, and the move encoding.
3372 The first two of these should be reasonably intuitive for a user to
3373 type in; so provide some flexibility where possible. Suppose, for
3374 example, your parameter format consists of two numbers separated by
3375 an \c{x} to specify the grid dimensions (\c{10x10} or \c{20x15}),
3376 and then has some suffixes to specify other aspects of the game
3377 type. It's almost always a good idea in this situation to arrange
3378 that \cw{decode_params()} can handle the suffixes appearing in any
3379 order, even if \cw{encode_params()} only ever generates them in one
3382 These formats will also be expected to be reasonably stable: users
3383 will expect to be able to exchange game IDs with other users who
3384 aren't running exactly the same version of your game. So make them
3385 robust and stable: don't build too many assumptions into the game ID
3386 format which will have to be changed every time something subtle
3387 changes in the puzzle code.
3389 \H{writing-howto} Common how-to questions
3391 This section lists some common things people want to do when writing
3392 a puzzle, and describes how to achieve them within the Puzzles
3395 \S{writing-howto-cursor} Drawing objects at only one position
3397 A common phenomenon is to have an object described in the
3398 \c{game_state} or the \c{game_ui} which can only be at one position.
3399 A cursor \dash probably specified in the \c{game_ui} \dash is a good
3402 In the \c{game_ui}, it would \e{obviously} be silly to have an array
3403 covering the whole game grid with a boolean flag stating whether the
3404 cursor was at each position. Doing that would waste space, would
3405 make it difficult to find the cursor in order to do anything with
3406 it, and would introduce the potential for synchronisation bugs in
3407 which you ended up with two cursors or none. The obviously sensible
3408 way to store a cursor in the \c{game_ui} is to have fields directly
3409 encodings the cursor's coordinates.
3411 However, it is a mistake to assume that the same logic applies to
3412 the \c{game_drawstate}. If you replicate the cursor position fields
3413 in the draw state, the redraw code will get very complicated. In the
3414 draw state, in fact, it \e{is} probably the right thing to have a
3415 cursor flag for every position in the grid. You probably have an
3416 array for the whole grid in the drawstate already (stating what is
3417 currently displayed in the window at each position); the sensible
3418 approach is to add a \q{cursor} flag to each element of that array.
3419 Then the main redraw loop will look something like this
3422 \c for (y = 0; y < h; y++) {
3423 \c for (x = 0; x < w; x++) {
3424 \c int value = state->symbol_at_position[y][x];
3425 \c if (x == ui->cursor_x && y == ui->cursor_y)
3427 \c if (ds->symbol_at_position[y][x] != value) {
3428 \c symbol_drawing_subroutine(fe, ds, x, y, value);
3429 \c ds->symbol_at_position[y][x] = value;
3434 This loop is very simple, pretty hard to get wrong, and
3435 \e{automatically} deals both with erasing the previous cursor and
3436 drawing the new one, with no special case code required.
3438 This type of loop is generally a sensible way to write a redraw
3439 function, in fact. The best thing is to ensure that the information
3440 stored in the draw state for each position tells you \e{everything}
3441 about what was drawn there. A good way to ensure that is to pass
3442 precisely the same information, and \e{only} that information, to a
3443 subroutine that does the actual drawing; then you know there's no
3444 additional information which affects the drawing but which you don't
3447 \S{writing-keyboard-cursor} Implementing a keyboard-controlled cursor
3449 It is often useful to provide a keyboard control method in a
3450 basically mouse-controlled game. A keyboard-controlled cursor is
3451 best implemented by storing its location in the \c{game_ui} (since
3452 if it were in the \c{game_state} then the user would have to
3453 separately undo every cursor move operation). So the procedure would
3456 \b Put cursor position fields in the \c{game_ui}.
3458 \b \cw{interpret_move()} responds to arrow keys by modifying the
3459 cursor position fields and returning \cw{""}.
3461 \b \cw{interpret_move()} responds to some sort of fire button by
3462 actually performing a move based on the current cursor location.
3464 \b You might want an additional \c{game_ui} field stating whether
3465 the cursor is currently visible, and having it disappear when a
3466 mouse action occurs (so that it doesn't clutter the display when not
3469 \b You might also want to automatically hide the cursor in
3470 \cw{changed_state()} when the current game state changes to one in
3471 which there is no move to make (which is the case in some types of
3474 \b \cw{redraw()} draws the cursor using the technique described in
3475 \k{writing-howto-cursor}.
3477 \S{writing-howto-dragging} Implementing draggable sprites
3479 Some games have a user interface which involves dragging some sort
3480 of game element around using the mouse. If you need to show a
3481 graphic moving smoothly over the top of other graphics, use a
3482 blitter (see \k{drawing-blitter} for the blitter API) to save the
3483 background underneath it. The typical scenario goes:
3485 \b Have a blitter field in the \c{game_drawstate}.
3487 \b Set the blitter field to \cw{NULL} in the game's
3488 \cw{new_drawstate()} function, since you don't yet know how big the
3489 piece of saved background needs to be.
3491 \b In the game's \cw{set_size()} function, once you know the size of
3492 the object you'll be dragging around the display and hence the
3493 required size of the blitter, actually allocate the blitter (making
3494 sure to free a previous one if present \dash it's possible that
3495 \cw{set_size()} might be called twice on the same draw state).
3497 \b In \cw{free_drawstate()}, free the blitter if it's not \cw{NULL}.
3499 \b In \cw{interpret_move()}, respond to mouse-down and mouse-drag
3500 events by updating some fields in the \cw{game_ui} which indicate
3501 that a drag is in progress.
3503 \b At the \e{very end} of \cw{redraw()}, after all other drawing has
3504 been done, draw the moving object if there is one. First save the
3505 background under the object in the blitter; then set a clip
3506 rectangle covering precisely the area you just saved (just in case
3507 anti-aliasing or some other error causes your drawing to go beyond
3508 the area you saved). Then draw the object, and call \cw{unclip()}.
3509 Finally, set a flag in the \cw{game_drawstate} that indicates that
3510 the blitter needs restoring.
3512 \b At the very start of \cw{redraw()}, before doing anything else at
3513 all, check the flag in the \cw{game_drawstate}, and if it says the
3514 blitter needs restoring then restore it. (Then clear the flag, so
3515 that this won't happen again in the next redraw if no moving object
3516 is drawn this time.)
3518 This way, you will be able to write the rest of the redraw function
3519 completely ignoring the dragged object, as if it were floating above
3520 your bitmap and being completely separate.
3522 \S{writing-ref-counting} Sharing large invariant data between all
3525 In some puzzles, there is a large amount of data which never changes
3526 between game states. The array of numbers in Dominosa is a good
3529 You \e{could} dynamically allocate a copy of that array in every
3530 \c{game_state}, and have \cw{dup_game()} make a fresh copy of it for
3531 every new \c{game_state}; but it would waste memory and time. A
3532 more efficient way is to use a reference-counted structure.
3534 \b Define a structure type containing the data in question, and also
3535 containing an integer reference count.
3537 \b Have a field in \c{game_state} which is a pointer to this
3540 \b In \cw{new_game()}, when creating a fresh game state at the start
3541 of a new game, create an instance of this structure, initialise it
3542 with the invariant data, and set its reference count to 1.
3544 \b In \cw{dup_game()}, rather than making a copy of the structure
3545 for the new game state, simply set the new game state to point at
3546 the same copy of the structure, and increment its reference count.
3548 \b In \cw{free_game()}, decrement the reference count in the
3549 structure pointed to by the game state; if the count reaches zero,
3552 This way, the invariant data will persist for only as long as it's
3553 genuinely needed; \e{as soon} as the last game state for a
3554 particular puzzle instance is freed, the invariant data for that
3555 puzzle will vanish as well. Reference counting is a very efficient
3556 form of garbage collection, when it works at all. (Which it does in
3557 this instance, of course, because there's no possibility of circular
3560 \S{writing-flash-types} Implementing multiple types of flash
3562 In some games you need to flash in more than one different way.
3563 Mines, for example, flashes white when you win, and flashes red when
3564 you tread on a mine and die.
3566 The simple way to do this is:
3568 \b Have a field in the \c{game_ui} which describes the type of flash.
3570 \b In \cw{flash_length()}, examine the old and new game states to
3571 decide whether a flash is required and what type. Write the type of
3572 flash to the \c{game_ui} field whenever you return non-zero.
3574 \b In \cw{redraw()}, when you detect that \c{flash_time} is
3575 non-zero, examine the field in \c{game_ui} to decide which type of
3578 \cw{redraw()} will never be called with \c{flash_time} non-zero
3579 unless \cw{flash_length()} was first called to tell the mid-end that
3580 a flash was required; so whenever \cw{redraw()} notices that
3581 \c{flash_time} is non-zero, you can be sure that the field in
3582 \c{game_ui} is correctly set.
3584 \S{writing-move-anim} Animating game moves
3586 A number of puzzle types benefit from a quick animation of each move
3589 For some games, such as Fifteen, this is particularly easy. Whenever
3590 \cw{redraw()} is called with \c{oldstate} non-\cw{NULL}, Fifteen
3591 simply compares the position of each tile in the two game states,
3592 and if the tile is not in the same place then it draws it some
3593 fraction of the way from its old position to its new position. This
3594 method copes automatically with undo.
3596 Other games are less obvious. In Sixteen, for example, you can't
3597 just draw each tile a fraction of the way from its old to its new
3598 position: if you did that, the end tile would zip very rapidly past
3599 all the others to get to the other end and that would look silly.
3600 (Worse, it would look inconsistent if the end tile was drawn on top
3601 going one way and on the bottom going the other way.)
3603 A useful trick here is to define a field or two in the game state
3604 that indicates what the last move was.
3606 \b Add a \q{last move} field to the \c{game_state} (or two or more
3607 fields if the move is complex enough to need them).
3609 \b \cw{new_game()} initialises this field to a null value for a new
3612 \b \cw{execute_move()} sets up the field to reflect the move it just
3615 \b \cw{redraw()} now needs to examine its \c{dir} parameter. If
3616 \c{dir} is positive, it determines the move being animated by
3617 looking at the last-move field in \c{newstate}; but if \c{dir} is
3618 negative, it has to look at the last-move field in \c{oldstate}, and
3619 invert whatever move it finds there.
3621 Note also that Sixteen needs to store the \e{direction} of the move,
3622 because you can't quite determine it by examining the row or column
3623 in question. You can in almost all cases, but when the row is
3624 precisely two squares long it doesn't work since a move in either
3625 direction looks the same. (You could argue that since moving a
3626 2-element row left and right has the same effect, it doesn't matter
3627 which one you animate; but in fact it's very disorienting to click
3628 the arrow left and find the row moving right, and almost as bad to
3629 undo a move to the right and find the game animating \e{another}
3632 \S{writing-conditional-anim} Animating drag operations
3634 In Untangle, moves are made by dragging a node from an old position
3635 to a new position. Therefore, at the time when the move is initially
3636 made, it should not be animated, because the node has already been
3637 dragged to the right place and doesn't need moving there. However,
3638 it's nice to animate the same move if it's later undone or redone.
3639 This requires a bit of fiddling.
3641 The obvious approach is to have a flag in the \c{game_ui} which
3642 inhibits move animation, and to set that flag in
3643 \cw{interpret_move()}. The question is, when would the flag be reset
3644 again? The obvious place to do so is \cw{changed_state()}, which
3645 will be called once per move. But it will be called \e{before}
3646 \cw{anim_length()}, so if it resets the flag then \cw{anim_length()}
3647 will never see the flag set at all.
3649 The solution is to have \e{two} flags in a queue.
3651 \b Define two flags in \c{game_ui}; let's call them \q{current} and
3654 \b Set both to \cw{FALSE} in \c{new_ui()}.
3656 \b When a drag operation completes in \cw{interpret_move()}, set the
3657 \q{next} flag to \cw{TRUE}.
3659 \b Every time \cw{changed_state()} is called, set the value of
3660 \q{current} to the value in \q{next}, and then set the value of
3661 \q{next} to \cw{FALSE}.
3663 \b That way, \q{current} will be \cw{TRUE} \e{after} a call to
3664 \cw{changed_state()} if and only if that call to
3665 \cw{changed_state()} was the result of a drag operation processed by
3666 \cw{interpret_move()}. Any other call to \cw{changed_state()}, due
3667 to an Undo or a Redo or a Restart or a Solve, will leave \q{current}
3670 \b So now \cw{anim_length()} can request a move animation if and
3671 only if the \q{current} flag is \e{not} set.
3673 \S{writing-cheating} Inhibiting the victory flash when Solve is used
3675 Many games flash when you complete them, as a visual congratulation
3676 for having got to the end of the puzzle. It often seems like a good
3677 idea to disable that flash when the puzzle is brought to a solved
3678 state by means of the Solve operation.
3680 This is easily done:
3682 \b Add a \q{cheated} flag to the \c{game_state}.
3684 \b Set this flag to \cw{FALSE} in \cw{new_game()}.
3686 \b Have \cw{solve()} return a move description string which clearly
3687 identifies the move as a solve operation.
3689 \b Have \cw{execute_move()} respond to that clear identification by
3690 setting the \q{cheated} flag in the returned \c{game_state}. The
3691 flag will then be propagated to all subsequent game states, even if
3692 the user continues fiddling with the game after it is solved.
3694 \b \cw{flash_length()} now returns non-zero if \c{oldstate} is not
3695 completed and \c{newstate} is, \e{and} neither state has the
3696 \q{cheated} flag set.
3698 \H{writing-testing} Things to test once your puzzle is written
3700 Puzzle implementations written in this framework are self-testing as
3701 far as I could make them.
3703 Textual game and move descriptions, for example, are generated and
3704 parsed as part of the normal process of play. Therefore, if you can
3705 make moves in the game \e{at all} you can be reasonably confident
3706 that the mid-end serialisation interface will function correctly and
3707 you will be able to save your game. (By contrast, if I'd stuck with
3708 a single \cw{make_move()} function performing the jobs of both
3709 \cw{interpret_move()} and \cw{execute_move()}, and had separate
3710 functions to encode and decode a game state in string form, then
3711 those functions would not be used during normal play; so they could
3712 have been completely broken, and you'd never know it until you tried
3713 to save the game \dash which would have meant you'd have to test
3714 game saving \e{extensively} and make sure to test every possible
3715 type of game state. As an added bonus, doing it the way I did leads
3716 to smaller save files.)
3718 There is one exception to this, which is the string encoding of the
3719 \c{game_ui}. Most games do not store anything permanent in the
3720 \c{game_ui}, and hence do not need to put anything in its encode and
3721 decode functions; but if there is anything in there, you do need to
3722 test game loading and saving to ensure those functions work
3725 It's also worth testing undo and redo of all operations, to ensure
3726 that the redraw and the animations (if any) work properly. Failing
3727 to animate undo properly seems to be a common error.
3729 Other than that, just use your common sense.