chiark / gitweb /
Introduce, and implement as usefully as I can in all front ends, a
[sgt-puzzles.git] / devel.but
1 \cfg{text-indent}{0}
2 \cfg{text-width}{72}
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}
17
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}
25
26 \define{dash} \u2013{-}
27
28 \title Developer documentation for Simon Tatham's puzzle collection
29
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
33 new platform.
34
35 This guide is believed correct as of r6190. Hopefully it will be
36 updated along with the code in future, but if not, I've at least
37 left this version number in here so you can figure out what's
38 changed by tracking commit comments from there onwards.
39
40 \C{intro} Introduction
41
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.
47
48 \H{intro-frontend} Front end
49
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.
54
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.
57
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).
62
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
73 those guidelines.
74
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}.
81
82 \H{intro-backend} Back end
83
84 A \q{back end}, in this collection, is synonymous with a \q{puzzle}.
85 Each back end implements a different game.
86
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.
92
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
99 work.
100
101 The functions and variables provided in the back end data structure
102 are documented in \k{backend}.
103
104 \H{intro-midend} Middle end
105
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.
109
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.
120
121 Functionality provided by the mid-end includes:
122
123 \b Maintaining a list of game state structures and moving back and
124 forth along that list to provide Undo and Redo.
125
126 \b Handling timers (for move animations, flashes on completion, and
127 in some cases actually timing the game).
128
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.
134
135 \b Handling standard keystrokes and menu commands, such as \q{New
136 Game}, \q{Restart Game} and \q{Quit}.
137
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,
141 etc).
142
143 \b Handling the dialog boxes which ask the user for a game ID.
144
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).
149
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
153 properly.
154
155 The API of functions provided by the mid-end to be called by the
156 front end is documented in \k{midend}.
157
158 \H{intro-utils} Miscellaneous utilities
159
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
167 \k{utils}.
168
169 \H{intro-structure} Structure of this guide
170
171 There are a number of function call interfaces within Puzzles, and
172 this guide will discuss each one in a chapter of its own. After
173 that, \k{writing} discusses how to design new games, with some
174 general design thoughts and tips.
175
176 \C{backend} Interface to the back end
177
178 This chapter gives a detailed discussion of the interface that each
179 back end must implement.
180
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:
186
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.
192
193 \b On platforms such as MacOS X and PalmOS, which build all the
194 puzzles into a single monolithic binary, the game structure in each
195 back end must have a different name, and there's a helper module
196 \c{list.c} (constructed automatically by the same Perl script that
197 builds the \cw{Makefile}s) which contains a complete list of those
198 game structures.
199
200 On the latter type of platform, source files may assume that the
201 preprocessor symbol \c{COMBINED} has been defined. Thus, the usual
202 code to declare the game structure looks something like this:
203
204 \c #ifdef COMBINED
205 \c #define thegame net    /* or whatever this game is called */
206 \e                 iii    iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
207 \c #endif
208 \c 
209 \c const struct game thegame = {
210 \c     /* lots of structure initialisation in here */
211 \e     iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
212 \c };
213
214 Game back ends must also internally define a number of data
215 structures, for storing their various persistent state. This chapter
216 will first discuss the nature and use of those structures, and then
217 go on to give details of every element of the game structure.
218
219 \H{backend-structs} Data structures
220
221 Each game is required to define four separate data structures. This
222 section discusses each one and suggests what sorts of things need to
223 be put in it.
224
225 \S{backend-game-params} \c{game_params}
226
227 The \c{game_params} structure contains anything which affects the
228 automatic generation of new puzzles. So if puzzle generation is
229 parametrised in any way, those parameters need to be stored in
230 \c{game_params}.
231
232 Most puzzles currently in this collection are played on a grid of
233 squares, meaning that the most obvious parameter is the grid size.
234 Many puzzles have additional parameters; for example, Mines allows
235 you to control the number of mines in the grid independently of its
236 size, Net can be wrapping or non-wrapping, Solo has difficulty
237 levels and symmetry settings, and so on.
238
239 A simple rule for deciding whether a data item needs to go in
240 \c{game_params} is: would the user expect to be able to control this
241 data item from either the preset-game-types menu or the \q{Custom}
242 game type configuration? If so, it's part of \c{game_params}.
243
244 \c{game_params} structures are permitted to contain pointers to
245 subsidiary data if they need to. The back end is required to provide
246 functions to create and destroy \c{game_params}, and those functions
247 can allocate and free additional memory if necessary. (It has not
248 yet been necessary to do this in any puzzle so far, but the
249 capability is there just in case.)
250
251 \c{game_params} is also the only structure which the game's
252 \cw{compute_size()} function may refer to; this means that any
253 aspect of the game which affects the size of the window it needs to
254 be drawn in must be stored in \c{game_params}. In particular, this
255 imposes the fundamental limitation that random game generation may
256 not have a random effect on the window size: game generation
257 algorithms are constrained to work by starting from the grid size
258 rather than generating it as an emergent phenomenon. (Although this
259 is a restriction in theory, it has not yet seemed to be a problem.)
260
261 \S{backend-game-state} \c{game_state}
262
263 While the user is actually playing a puzzle, the \c{game_state}
264 structure stores all the data corresponding to the current state of
265 play.
266
267 The mid-end keeps \c{game_state}s in a list, and adds to the list
268 every time the player makes a move; the Undo and Redo functions step
269 back and forth through that list.
270
271 Therefore, a good means of deciding whether a data item needs to go
272 in \c{game_state} is: would a player expect that data item to be
273 restored on undo? If so, put it in \c{game_state}, and this will
274 automatically happen without you having to lift a finger. If not
275 \dash for example, the deaths counter in Mines is precisely
276 something that does \e{not} want to be reset to its previous state
277 on an undo \dash then you might have found a data item that needs to
278 go in \c{game_ui} instead.
279
280 During play, \c{game_state}s are often passed around without an
281 accompanying \c{game_params} structure. Therefore, any information
282 in \c{game_params} which is important during play (such as the grid
283 size) must be duplicated within the \c{game_state}. One simple
284 method of doing this is to have the \c{game_state} structure
285 \e{contain} a \c{game_params} structure as one of its members,
286 although this isn't obligatory if you prefer to do it another way.
287
288 \S{backend-game-drawstate} \c{game_drawstate}
289
290 \c{game_drawstate} carries persistent state relating to the current
291 graphical contents of the puzzle window. The same \c{game_drawstate}
292 is passed to every call to the game redraw function, so that it can
293 remember what it has already drawn and what needs redrawing.
294
295 A typical use for a \c{game_drawstate} is to have an array mirroring
296 the array of grid squares in the \c{game_state}; then every time the
297 redraw function was passed a \c{game_state}, it would loop over all
298 the squares, and physically redraw any whose description in the
299 \c{game_state} (i.e. what the square needs to look like when the
300 redraw is completed) did not match its description in the
301 \c{game_drawstate} (i.e. what the square currently looks like).
302
303 \c{game_drawstate} is occasionally completely torn down and
304 reconstructed by the mid-end, if the user somehow forces a full
305 redraw. Therefore, no data should be stored in \c{game_drawstate}
306 which is \e{not} related to the state of the puzzle window, because
307 it might be unexpectedly destroyed.
308
309 The back end provides functions to create and destroy
310 \c{game_drawstate}, which means it can contain pointers to
311 subsidiary allocated data if it needs to. A common thing to want to
312 allocate in a \c{game_drawstate} is a \c{blitter}; see
313 \k{drawing-blitter} for more on this subject.
314
315 \S{backend-game-ui} \c{game_ui}
316
317 \c{game_ui} contains whatever doesn't fit into the above three
318 structures!
319
320 A new \c{game_ui} is created when the user begins playing a new
321 instance of a puzzle (i.e. during \q{New Game} or after entering a
322 game ID etc). It persists until the user finishes playing that game
323 and begins another one (or closes the window); in particular,
324 \q{Restart Game} does \e{not} destroy the \c{game_ui}.
325
326 \c{game_ui} is useful for implementing user-interface state which is
327 not part of \c{game_state}. Common examples are keyboard control
328 (you wouldn't want to have to separately Undo through every cursor
329 motion) and mouse dragging. See \k{writing-keyboard-cursor} and
330 \k{writing-howto-dragging}, respectively, for more details.
331
332 Another use for \c{game_ui} is to store highly persistent data such
333 as the Mines death counter. This is conceptually rather different:
334 where the Net cursor position was \e{not important enough} to
335 preserve for the player to restore by Undo, the Mines death counter
336 is \e{too important} to permit the player to revert by Undo!
337
338 A final use for \c{game_ui} is to pass information to the redraw
339 function about recent changes to the game state. This is used in
340 Mines, for example, to indicate whether a requested \q{flash} should
341 be a white flash for victory or a red flash for defeat; see
342 \k{writing-flash-types}.
343
344 \H{backend-simple} Simple data in the back end
345
346 In this section I begin to discuss each individual element in the
347 back end structure. To begin with, here are some simple
348 self-contained data elements.
349
350 \S{backend-name} \c{name}
351
352 \c const char *name;
353
354 This is a simple ASCII string giving the name of the puzzle. This
355 name will be used in window titles, in game selection menus on
356 monolithic platforms, and anywhere else that the front end needs to
357 know the name of a game.
358
359 \S{backend-winhelp} \c{winhelp_topic}
360
361 \c const char *winhelp_topic;
362
363 This member is used on Windows only, to provide online help.
364 Although the Windows front end provides a separate binary for each
365 puzzle, it has a single monolithic help file; so when a user selects
366 \q{Help} from the menu, the program needs to open the help file and
367 jump to the chapter describing that particular puzzle.
368
369 Therefore, each chapter in \c{puzzles.but} is labelled with a
370 \e{help topic} name, similar to this:
371
372 \c \cfg{winhelp-topic}{games.net}
373
374 And then the corresponding game back end encodes the topic string
375 (here \cq{games.net}) in the \c{winhelp_topic} element of the game
376 structure.
377
378 \H{backend-params} Handling game parameter sets
379
380 In this section I present the various functions which handle the
381 \c{game_params} structure.
382
383 \S{backend-default-params} \cw{default_params()}
384
385 \c game_params *(*default_params)(void);
386
387 This function allocates a new \c{game_params} structure, fills it
388 with the default values, and returns a pointer to it.
389
390 \S{backend-fetch-preset} \cw{fetch_preset()}
391
392 \c int (*fetch_preset)(int i, char **name, game_params **params);
393
394 This function is used to populate the \q{Type} menu, which provides
395 a list of conveniently accessible preset parameters for most games.
396
397 The function is called with \c{i} equal to the index of the preset
398 required (numbering from zero). It returns \cw{FALSE} if that preset
399 does not exist (if \c{i} is less than zero or greater than the
400 largest preset index). Otherwise, it sets \c{*params} to point at a
401 newly allocated \c{game_params} structure containing the preset
402 information, sets \c{*name} to point at a newly allocated C string
403 containing the preset title (to go on the \q{Type} menu), and
404 returns \cw{TRUE}.
405
406 If the game does not wish to support any presets at all, this
407 function is permitted to return \cw{FALSE} always.
408
409 \S{backend-encode-params} \cw{encode_params()}
410
411 \c char *(*encode_params)(game_params *params, int full);
412
413 The job of this function is to take a \c{game_params}, and encode it
414 in a string form for use in game IDs. The return value must be a
415 newly allocated C string, and \e{must} not contain a colon or a hash
416 (since those characters are used to mark the end of the parameter
417 section in a game ID).
418
419 Ideally, it should also not contain any other potentially
420 controversial punctuation; bear in mind when designing a string
421 parameter format that it will probably be used on both Windows and
422 Unix command lines under a variety of exciting shell quoting and
423 metacharacter rules. Sticking entirely to alphanumerics is the
424 safest thing; if you really need punctuation, you can probably get
425 away with commas, periods or underscores without causing anybody any
426 major inconvenience. If you venture far beyond that, you're likely
427 to irritate \e{somebody}.
428
429 (At the time of writing this, all existing games have purely
430 alphanumeric string parameter formats. Usually these involve a
431 letter denoting a parameter, followed optionally by a number giving
432 the value of that parameter, with a few mandatory parts at the
433 beginning such as numeric width and height separated by \cq{x}.)
434
435 If the \c{full} parameter is \cw{TRUE}, this function should encode
436 absolutely everything in the \c{game_params}, such that a subsequent
437 call to \cw{decode_params()} (\k{backend-decode-params}) will yield
438 an identical structure. If \c{full} is \cw{FALSE}, however, you
439 should leave out anything which is not necessary to describe a
440 \e{specific puzzle instance}, i.e. anything which only takes effect
441 when a new puzzle is \e{generated}. For example, the Solo
442 \c{game_params} includes a difficulty rating used when constructing
443 new puzzles; but a Solo game ID need not explicitly include the
444 difficulty, since to describe a puzzle once generated it's
445 sufficient to give the grid dimensions and the location and contents
446 of the clue squares. (Indeed, one might very easily type in a puzzle
447 out of a newspaper without \e{knowing} what its difficulty level is
448 in Solo's terminology.) Therefore, Solo's \cw{encode_params()} only
449 encodes the difficulty level if \c{full} is set.
450
451 \S{backend-decode-params} \cw{decode_params()}
452
453 \c void (*decode_params)(game_params *params, char const *string);
454
455 This function is the inverse of \cw{encode_params()}
456 (\k{backend-encode-params}). It parses the supplied string and fills
457 in the supplied \c{game_params} structure. Note that the structure
458 will \e{already} have been allocated: this function is not expected
459 to create a \e{new} \c{game_params}, but to modify an existing one.
460
461 This function can receive a string which only encodes a subset of
462 the parameters. The most obvious way in which this can happen is if
463 the string was constructed by \cw{encode_params()} with its \c{full}
464 parameter set to \cw{FALSE}; however, it could also happen if the
465 user typed in a parameter set manually and missed something out. Be
466 prepared to deal with a wide range of possibilities.
467
468 When dealing with a parameter which is not specified in the input
469 string, what to do requires a judgment call on the part of the
470 programmer. Sometimes it makes sense to adjust other parameters to
471 bring them into line with the new ones. In Mines, for example, you
472 would probably not want to keep the same mine count if the user
473 dropped the grid size and didn't specify one, since you might easily
474 end up with more mines than would actually fit in the grid! On the
475 other hand, sometimes it makes sense to leave the parameter alone: a
476 Solo player might reasonably expect to be able to configure size and
477 difficulty independently of one another.
478
479 This function currently has no direct means of returning an error if
480 the string cannot be parsed at all. However, the returned
481 \c{game_params} is almost always subsequently passed to
482 \cw{validate_params()} (\k{backend-validate-params}), so if you
483 really want to signal parse errors, you could always have a \c{char
484 *} in your parameters structure which stored an error message, and
485 have \cw{validate_params()} return it if it is non-\cw{NULL}.
486
487 \S{backend-free-params} \cw{free_params()}
488
489 \c void (*free_params)(game_params *params);
490
491 This function frees a \c{game_params} structure, and any subsidiary
492 allocations contained within it.
493
494 \S{backend-dup-params} \cw{dup_params()}
495
496 \c game_params *(*dup_params)(game_params *params);
497
498 This function allocates a new \c{game_params} structure and
499 initialises it with an exact copy of the information in the one
500 provided as input. It returns a pointer to the new duplicate.
501
502 \S{backend-can-configure} \c{can_configure}
503
504 \c int can_configure;
505
506 This boolean data element is set to \cw{TRUE} if the back end
507 supports custom parameter configuration via a dialog box. If it is
508 \cw{TRUE}, then the functions \cw{configure()} and
509 \cw{custom_params()} are expected to work. See \k{backend-configure}
510 and \k{backend-custom-params} for more details.
511
512 \S{backend-configure} \cw{configure()}
513
514 \c config_item *(*configure)(game_params *params);
515
516 This function is called when the user requests a dialog box for
517 custom parameter configuration. It returns a newly allocated array
518 of \cw{config_item} structures, describing the GUI elements required
519 in the dialog box. The array should have one more element than the
520 number of controls, since it is terminated with a \cw{C_END} marker
521 (see below). Each array element describes the control together with
522 its initial value; the front end will modify the value fields and
523 return the updated array to \cw{custom_params()} (see
524 \k{backend-custom-params}).
525
526 The \cw{config_item} structure contains the following elements:
527
528 \c char *name;
529 \c int type;
530 \c char *sval;
531 \c int ival;
532
533 \c{name} is an ASCII string giving the textual label for a GUI
534 control. It is \e{not} expected to be dynamically allocated.
535
536 \c{type} contains one of a small number of \c{enum} values defining
537 what type of control is being described. The meaning of the \c{sval}
538 and \c{ival} fields depends on the value in \c{type}. The valid
539 values are:
540
541 \dt \c{C_STRING}
542
543 \dd Describes a text input box. (This is also used for numeric
544 input. The back end does not bother informing the front end that the
545 box is numeric rather than textual; some front ends do have the
546 capacity to take this into account, but I decided it wasn't worth
547 the extra complexity in the interface.) For this type, \c{ival} is
548 unused, and \c{sval} contains a dynamically allocated string
549 representing the contents of the input box.
550
551 \dt \c{C_BOOLEAN}
552
553 \dd Describes a simple checkbox. For this type, \c{sval} is unused,
554 and \c{ival} is \cw{TRUE} or \cw{FALSE}.
555
556 \dt \c{C_CHOICES}
557
558 \dd Describes a drop-down list presenting one of a small number of
559 fixed choices. For this type, \c{sval} contains a list of strings
560 describing the choices; the very first character of \c{sval} is used
561 as a delimiter when processing the rest (so that the strings
562 \cq{:zero:one:two}, \cq{!zero!one!two} and \cq{xzeroxonextwo} all
563 define a three-element list containing \cq{zero}, \cq{one} and
564 \cq{two}). \c{ival} contains the index of the currently selected
565 element, numbering from zero (so that in the above example, 0 would
566 mean \cq{zero} and 2 would mean \cq{two}).
567
568 \lcont{
569
570 Note that for this control type, \c{sval} is \e{not} dynamically
571 allocated, whereas it was for \c{C_STRING}.
572
573 }
574
575 \dt \c{C_END}
576
577 \dd Marks the end of the array of \c{config_item}s. All other fields
578 are unused.
579
580 The array returned from this function is expected to have filled in
581 the initial values of all the controls according to the input
582 \c{game_params} structure.
583
584 If the game's \c{can_configure} flag is set to \cw{FALSE}, this
585 function is never called and need not do anything at all.
586
587 \S{backend-custom-params} \cw{custom_params()}
588
589 \c game_params *(*custom_params)(config_item *cfg);
590
591 This function is the counterpart to \cw{configure()}
592 (\k{backend-configure}). It receives as input an array of
593 \c{config_item}s which was originally created by \cw{configure()},
594 but in which the control values have since been changed in
595 accordance with user input. Its function is to read the new values
596 out of the controls and return a newly allocated \c{game_params}
597 structure representing the user's chosen parameter set.
598
599 (The front end will have modified the controls' \e{values}, but
600 there will still always be the same set of controls, in the same
601 order, as provided by \cw{configure()}. It is not necessary to check
602 the \c{name} and \c{type} fields, although you could use
603 \cw{assert()} if you were feeling energetic.)
604
605 This function is not expected to (and indeed \e{must not}) free the
606 input \c{config_item} array. (If the parameters fail to validate,
607 the dialog box will stay open.)
608
609 If the game's \c{can_configure} flag is set to \cw{FALSE}, this
610 function is never called and need not do anything at all.
611
612 \S{backend-validate-params} \cw{validate_params()}
613
614 \c char *(*validate_params)(game_params *params, int full);
615
616 This function takes a \c{game_params} structure as input, and checks
617 that the parameters described in it fall within sensible limits. (At
618 the very least, grid dimensions should almost certainly be strictly
619 positive, for example.)
620
621 Return value is \cw{NULL} if no problems were found, or
622 alternatively a (non-dynamically-allocated) ASCII string describing
623 the error in human-readable form.
624
625 If the \c{full} parameter is set, full validation should be
626 performed: any set of parameters which would not permit generation
627 of a sensible puzzle should be faulted. If \c{full} is \e{not} set,
628 the implication is that these parameters are not going to be used
629 for \e{generating} a puzzle; so parameters which can't even sensibly
630 \e{describe} a valid puzzle should still be faulted, but parameters
631 which only affect puzzle generation should not be.
632
633 (The \c{full} option makes a difference when parameter combinations
634 are non-orthogonal. For example, Net has a boolean option
635 controlling whether it enforces a unique solution; it turns out that
636 it's impossible to generate a uniquely soluble puzzle with wrapping
637 walls and width 2, so \cw{validate_params()} will complain if you
638 ask for one. However, if the user had just been playing a unique
639 wrapping puzzle of a more sensible width, and then pastes in a game
640 ID acquired from somebody else which happens to describe a
641 \e{non}-unique wrapping width-2 puzzle, then \cw{validate_params()}
642 will be passed a \c{game_params} containing the width and wrapping
643 settings from the new game ID and the uniqueness setting from the
644 old one. This would be faulted, if it weren't for the fact that
645 \c{full} is not set during this call, so Net ignores the
646 inconsistency. The resulting \c{game_params} is never subsequently
647 used to generate a puzzle; this is a promise made by the mid-end
648 when it asks for a non-full validation.)
649
650 \H{backend-descs} Handling game descriptions
651
652 In this section I present the functions that deal with a textual
653 description of a puzzle, i.e. the part that comes after the colon in
654 a descriptive-format game ID.
655
656 \S{backend-new-desc} \cw{new_desc()}
657
658 \c char *(*new_desc)(game_params *params, random_state *rs,
659 \c                   char **aux, int interactive);
660
661 This function is where all the really hard work gets done. This is
662 the function whose job is to randomly generate a new puzzle,
663 ensuring solubility and uniqueness as appropriate.
664
665 As input it is given a \c{game_params} structure and a random state
666 (see \k{utils-random} for the random number API). It must invent a
667 puzzle instance, encode it in string form, and return a dynamically
668 allocated C string containing that encoding.
669
670 Additionally, it may return a second dynamically allocated string in
671 \c{*aux}. (If it doesn't want to, then it can leave that parameter
672 completely alone; it isn't required to set it to \cw{NULL}, although
673 doing so is harmless.) That string, if present, will be passed to
674 \cw{solve()} (\k{backend-solve}) later on; so if the puzzle is
675 generated in such a way that a solution is known, then information
676 about that solution can be saved in \c{*aux} for \cw{solve()} to
677 use.
678
679 The \c{interactive} parameter should be ignored by almost all
680 puzzles. Its purpose is to distinguish between generating a puzzle
681 within a GUI context for immediate play, and generating a puzzle in
682 a command-line context for saving to be played later. The only
683 puzzle that currently uses this distinction (and, I fervently hope,
684 the only one which will \e{ever} need to use it) is Mines, which
685 chooses a random first-click location when generating puzzles
686 non-interactively, but which waits for the user to place the first
687 click when interactive. If you think you have come up with another
688 puzzle which needs to make use of this parameter, please think for
689 at least ten minutes about whether there is \e{any} alternative!
690
691 Note that game description strings are not required to contain an
692 encoding of parameters such as grid size; a game description is
693 never separated from the \c{game_params} it was generated with, so
694 any information contained in that structure need not be encoded
695 again in the game description.
696
697 \S{backend-validate-desc} \cw{validate_desc()}
698
699 \c char *(*validate_desc)(game_params *params, char *desc);
700
701 This function is given a game description, and its job is to
702 validate that it describes a puzzle which makes sense.
703
704 To some extent it's up to the user exactly how far they take the
705 phrase \q{makes sense}; there are no particularly strict rules about
706 how hard the user is permitted to shoot themself in the foot when
707 typing in a bogus game description by hand. (For example, Rectangles
708 will not verify that the sum of all the numbers in the grid equals
709 the grid's area. So a user could enter a puzzle which was provably
710 not soluble, and the program wouldn't complain; there just wouldn't
711 happen to be any sequence of moves which solved it.)
712
713 The one non-negotiable criterion is that any game description which
714 makes it through \cw{validate_desc()} \e{must not} subsequently
715 cause a crash or an assertion failure when fed to \cw{new_game()}
716 and thence to the rest of the back end.
717
718 The return value is \cw{NULL} on success, or a
719 non-dynamically-allocated C string containing an error message.
720
721 \S{backend-new-game} \cw{new_game()}
722
723 \c game_state *(*new_game)(midend *me, game_params *params,
724 \c                         char *desc);
725
726 This function takes a game description as input, together with its
727 accompanying \c{game_params}, and constructs a \c{game_state}
728 describing the initial state of the puzzle. It returns a newly
729 allocated \c{game_state} structure.
730
731 Almost all puzzles should ignore the \c{me} parameter. It is
732 required by Mines, which needs it for later passing to
733 \cw{midend_supersede_game_desc()} (see \k{backend-supersede}) once
734 the user has placed the first click. I fervently hope that no other
735 puzzle will be awkward enough to require it, so everybody else
736 should ignore it. As with the \c{interactive} parameter in
737 \cw{new_desc()} (\k{backend-new-desc}), if you think you have a
738 reason to need this parameter, please try very hard to think of an
739 alternative approach!
740
741 \H{backend-states} Handling game states
742
743 This section describes the functions which create and destroy
744 \c{game_state} structures.
745
746 (Well, except \cw{new_game()}, which is in \k{backend-new-game}
747 instead of under here; but it deals with game descriptions \e{and}
748 game states and it had to go in one section or the other.)
749
750 \S{backend-dup-game} \cw{dup_game()}
751
752 \c game_state *(*dup_game)(game_state *state);
753
754 This function allocates a new \c{game_state} structure and
755 initialises it with an exact copy of the information in the one
756 provided as input. It returns a pointer to the new duplicate.
757
758 \S{backend-free-game} \cw{free_game()}
759
760 \c void (*free_game)(game_state *state);
761
762 This function frees a \c{game_state} structure, and any subsidiary
763 allocations contained within it.
764
765 \H{backend-ui} Handling \c{game_ui}
766
767 \S{backend-new-ui} \cw{new_ui()}
768
769 \c game_ui *(*new_ui)(game_state *state);
770
771 This function allocates and returns a new \c{game_ui} structure for
772 playing a particular puzzle. It is passed a pointer to the initial
773 \c{game_state}, in case it needs to refer to that when setting up
774 the initial values for the new game.
775
776 \S{backend-free-ui} \cw{free_ui()}
777
778 \c void (*free_ui)(game_ui *ui);
779
780 This function frees a \c{game_ui} structure, and any subsidiary
781 allocations contained within it.
782
783 \S{backend-encode-ui} \cw{encode_ui()}
784
785 \c char *(*encode_ui)(game_ui *ui);
786
787 This function encodes any \e{important} data in a \c{game_ui}
788 structure in string form. It is only called when saving a
789 half-finished game to a file.
790
791 It should be used sparingly. Almost all data in a \c{game_ui} is not
792 important enough to save. The location of the keyboard-controlled
793 cursor, for example, can be reset to a default position on reloading
794 the game without impacting the user experience. If the user should
795 somehow manage to save a game while a mouse drag was in progress,
796 then discarding that mouse drag would be an outright \e{feature}.
797
798 A typical thing that \e{would} be worth encoding in this function is
799 the Mines death counter: it's in the \c{game_ui} rather than the
800 \c{game_state} because it's too important to allow the user to
801 revert it by using Undo, and therefore it's also too important to
802 allow the user to revert it by saving and reloading. (Of course, the
803 user could edit the save file by hand... But if the user is \e{that}
804 determined to cheat, they could just as easily modify the game's
805 source.)
806
807 \S{backend-decode-ui} \cw{decode_ui()}
808
809 \c void (*decode_ui)(game_ui *ui, char *encoding);
810
811 This function parses a string previously output by \cw{encode_ui()},
812 and writes the decoded data back into the provided \c{game_ui}
813 structure.
814
815 \S{backend-changed-state} \cw{changed_state()}
816
817 \c void (*changed_state)(game_ui *ui, game_state *oldstate,
818 \c                       game_state *newstate);
819
820 This function is called by the mid-end whenever the current game
821 state changes, for any reason. Those reasons include:
822
823 \b a fresh move being made by \cw{interpret_move()} and
824 \cw{execute_move()}
825
826 \b a solve operation being performed by \cw{solve()} and
827 \cw{execute_move()}
828
829 \b the user moving back and forth along the undo list by means of
830 the Undo and Redo operations
831
832 \b the user selecting Restart to go back to the initial game state.
833
834 The job of \cw{changed_state()} is to update the \c{game_ui} for
835 consistency with the new game state, if any update is necessary. For
836 example, Same Game stores data about the currently selected tile
837 group in its \c{game_ui}, and this data is intrinsically related to
838 the game state it was derived from. So it's very likely to become
839 invalid when the game state changes; thus, Same Game's
840 \cw{changed_state()} function clears the current selection whenever
841 it is called.
842
843 When \cw{anim_length()} or \cw{flash_length()} are called, you can
844 be sure that there has been a previous call to \cw{changed_state()}.
845 So \cw{changed_state()} can set up data in the \c{game_ui} which will
846 be read by \cw{anim_length()} and \cw{flash_length()}, and those
847 functions will not have to worry about being called without the data
848 having been initialised.
849
850 \H{backend-moves} Making moves
851
852 This section describes the functions which actually make moves in
853 the game: that is, the functions which process user input and end up
854 producing new \c{game_state}s.
855
856 \S{backend-interpret-move} \cw{interpret_move()}
857
858 \c char *(*interpret_move)(game_state *state, game_ui *ui,
859 \c                         game_drawstate *ds,
860 \c                         int x, int y, int button);
861
862 This function receives user input and processes it. Its input
863 parameters are the current \c{game_state}, the current \c{game_ui}
864 and the current \c{game_drawstate}, plus details of the input event.
865 \c{button} is either an ASCII value or a special code (listed below)
866 indicating an arrow or function key or a mouse event; when
867 \c{button} is a mouse event, \c{x} and \c{y} contain the pixel
868 coordinates of the mouse pointer relative to the top left of the
869 puzzle's drawing area.
870
871 \cw{interpret_move()} may return in three different ways:
872
873 \b Returning \cw{NULL} indicates that no action whatsoever occurred
874 in response to the input event; the puzzle was not interested in it
875 at all.
876
877 \b Returning the empty string (\cw{""}) indicates that the input
878 event has resulted in a change being made to the \c{game_ui} which
879 will require a redraw of the game window, but that no actual
880 \e{move} was made (i.e. no new \c{game_state} needs to be created).
881
882 \b Returning anything else indicates that a move was made and that a
883 new \c{game_state} must be created. However, instead of actually
884 constructing a new \c{game_state} itself, this function is required
885 to return a string description of the details of the move. This
886 string will be passed to \cw{execute_move()}
887 (\k{backend-execute-move}) to actually create the new
888 \c{game_state}. (Encoding moves as strings in this way means that
889 the mid-end can keep the strings as well as the game states, and the
890 strings can be written to disk when saving the game and fed to
891 \cw{execute_move()} again on reloading.)
892
893 The return value from \cw{interpret_move()} is expected to be
894 dynamically allocated if and only if it is not either \cw{NULL}
895 \e{or} the empty string.
896
897 After this function is called, the back end is permitted to rely on
898 some subsequent operations happening in sequence:
899
900 \b \cw{execute_move()} will be called to convert this move
901 description into a new \c{game_state}
902
903 \b \cw{changed_state()} will be called with the new \c{game_state}.
904
905 This means that if \cw{interpret_move()} needs to do updates to the
906 \c{game_ui} which are easier to perform by referring to the new
907 \c{game_state}, it can safely leave them to be done in
908 \cw{changed_state()} and not worry about them failing to happen.
909
910 (Note, however, that \cw{execute_move()} may \e{also} be called in
911 other circumstances. It is only \cw{interpret_move()} which can rely
912 on a subsequent call to \cw{changed_state()}.)
913
914 The special key codes supported by this function are:
915
916 \dt \cw{LEFT_BUTTON}, \cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}
917
918 \dd Indicate that one of the mouse buttons was pressed down.
919
920 \dt \cw{LEFT_DRAG}, \cw{MIDDLE_DRAG}, \cw{RIGHT_DRAG}
921
922 \dd Indicate that the mouse was moved while one of the mouse buttons
923 was still down. The mid-end guarantees that when one of these events
924 is received, it will always have been preceded by a button-down
925 event (and possibly other drag events) for the same mouse button,
926 and no event involving another mouse button will have appeared in
927 between.
928
929 \dt \cw{LEFT_RELEASE}, \cw{MIDDLE_RELEASE}, \cw{RIGHT_RELEASE}
930
931 \dd Indicate that a mouse button was released.  The mid-end
932 guarantees that when one of these events is received, it will always
933 have been preceded by a button-down event (and possibly some drag
934 events) for the same mouse button, and no event involving another
935 mouse button will have appeared in between.
936
937 \dt \cw{CURSOR_UP}, \cw{CURSOR_DOWN}, \cw{CURSOR_LEFT},
938 \cw{CURSOR_RIGHT}
939
940 \dd Indicate that an arrow key was pressed.
941
942 \dt \cw{CURSOR_SELECT}
943
944 \dd On platforms which have a prominent \q{select} button alongside
945 their cursor keys, indicates that that button was pressed.
946
947 In addition, there are some modifiers which can be bitwise-ORed into
948 the \c{button} parameter:
949
950 \dt \cw{MOD_CTRL}, \cw{MOD_SHFT}
951
952 \dd These indicate that the Control or Shift key was pressed
953 alongside the key. They only apply to the cursor keys, not to mouse
954 buttons or anything else.
955
956 \dt \cw{MOD_NUM_KEYPAD}
957
958 \dd This applies to some ASCII values, and indicates that the key
959 code was input via the numeric keypad rather than the main keyboard.
960 Some puzzles may wish to treat this differently (for example, a
961 puzzle might want to use the numeric keypad as an eight-way
962 directional pad), whereas others might not (a game involving numeric
963 input probably just wants to treat the numeric keypad as numbers).
964
965 \dt \cw{MOD_MASK}
966
967 \dd This mask is the bitwise OR of all the available modifiers; you
968 can bitwise-AND with \cw{~MOD_MASK} to strip all the modifiers off
969 any input value.
970
971 \S{backend-execute-move} \cw{execute_move()}
972
973 \c game_state *(*execute_move)(game_state *state, char *move);
974
975 This function takes an input \c{game_state} and a move string as
976 output from \cw{interpret_move()}. It returns a newly allocated
977 \c{game_state} which contains the result of applying the specified
978 move to the input game state.
979
980 This function may return \cw{NULL} if it cannot parse the move
981 string (and this is definitely preferable to crashing or failing an
982 assertion, since one way this can happen is if loading a corrupt
983 save file). However, it must not return \cw{NULL} for any move
984 string that really was output from \cw{interpret_move()}: this is
985 punishable by assertion failure in the mid-end.
986
987 \S{backend-can-solve} \c{can_solve}
988
989 \c int can_solve;
990
991 This boolean field is set to \cw{TRUE} if the game's \cw{solve()}
992 function does something. If it's set to \cw{FALSE}, the game will
993 not even offer the \q{Solve} menu option.
994
995 \S{backend-solve} \cw{solve()}
996
997 \c char *(*solve)(game_state *orig, game_state *curr,
998 \c                char *aux, char **error);
999
1000 This function is called when the user selects the \q{Solve} option
1001 from the menu.
1002
1003 It is passed two input game states: \c{orig} is the game state from
1004 the very start of the puzzle, and \c{curr} is the current one.
1005 (Different games find one or other or both of these convenient.) It
1006 is also passed the \c{aux} string saved by \cw{new_desc()}
1007 (\k{backend-new-desc}), in case that encodes important information
1008 needed to provide the solution.
1009
1010 If this function is unable to produce a solution (perhaps, for
1011 example, the game has no in-built solver so it can only solve
1012 puzzles it invented internally and has an \c{aux} string for) then
1013 it may return \cw{NULL}. If it does this, it must also set
1014 \c{*error} to an error message to be presented to the user (such as
1015 \q{Solution not known for this puzzle}); that error message is not
1016 expected to be dynamically allocated.
1017
1018 If this function \e{does} produce a solution, it returns a move
1019 string suitable for feeding to \cw{execute_move()}
1020 (\k{backend-execute-move}).
1021
1022 \H{backend-drawing} Drawing the game graphics
1023
1024 This section discusses the back end functions that deal with
1025 drawing.
1026
1027 \S{backend-new-drawstate} \cw{new_drawstate()}
1028
1029 \c game_drawstate *(*new_drawstate)(drawing *dr, game_state *state);
1030
1031 This function allocates and returns a new \c{game_drawstate}
1032 structure for drawing a particular puzzle. It is passed a pointer to
1033 a \c{game_state}, in case it needs to refer to that when setting up
1034 any initial data.
1035
1036 This function may not rely on the puzzle having been newly started;
1037 a new draw state can be constructed at any time if the front end
1038 requests a forced redraw. For games like Pattern, in which initial
1039 game states are much simpler than general ones, this might be
1040 important to keep in mind.
1041
1042 The parameter \c{dr} is a drawing object (see \k{drawing}) which the
1043 function might need to use to allocate blitters. (However, this
1044 isn't recommended; it's usually more sensible to wait to allocate a
1045 blitter until \cw{set_size()} is called, because that way you can
1046 tailor it to the scale at which the puzzle is being drawn.)
1047
1048 \S{backend-free-drawstate} \cw{free_drawstate()}
1049
1050 \c void (*free_drawstate)(drawing *dr, game_drawstate *ds);
1051
1052 This function frees a \c{game_drawstate} structure, and any
1053 subsidiary allocations contained within it.
1054
1055 The parameter \c{dr} is a drawing object (see \k{drawing}), which
1056 might be required if you are freeing a blitter.
1057
1058 \S{backend-preferred-tilesize} \c{preferred_tilesize}
1059
1060 \c int preferred_tilesize;
1061
1062 Each game is required to define a single integer parameter which
1063 expresses, in some sense, the scale at which it is drawn. This is
1064 described in the APIs as \cq{tilesize}, since most puzzles are on a
1065 square (or possibly triangular or hexagonal) grid and hence a
1066 sensible interpretation of this parameter is to define it as the
1067 size of one grid tile in pixels; however, there's no actual
1068 requirement that the \q{tile size} be proportional to the game
1069 window size. Window size is required to increase monotonically with
1070 \q{tile size}, however.
1071
1072 The data element \c{preferred_tilesize} indicates the tile size
1073 which should be used in the absence of a good reason to do otherwise
1074 (such as the screen being too small, or the user explicitly
1075 requesting a resize if that ever gets implemented).
1076
1077 \S{backend-compute-size} \cw{compute_size()}
1078
1079 \c void (*compute_size)(game_params *params, int tilesize,
1080 \c                      int *x, int *y);
1081
1082 This function is passed a \c{game_params} structure and a tile size.
1083 It returns, in \c{*x} and \c{*y}, the size in pixels of the drawing
1084 area that would be required to render a puzzle with those parameters
1085 at that tile size.
1086
1087 \S{backend-set-size} \cw{set_size()}
1088
1089 \c void (*set_size)(drawing *dr, game_drawstate *ds,
1090 \c                  game_params *params, int tilesize);
1091
1092 This function is responsible for setting up a \c{game_drawstate} to
1093 draw at a given tile size. Typically this will simply involve
1094 copying the supplied \c{tilesize} parameter into a \c{tilesize}
1095 field inside the draw state; for some more complex games it might
1096 also involve setting up other dimension fields, or possibly
1097 allocating a blitter (see \k{drawing-blitter}).
1098
1099 The parameter \c{dr} is a drawing object (see \k{drawing}), which is
1100 required if a blitter needs to be allocated.
1101
1102 Back ends may assume (and may enforce by assertion) that this
1103 function will be called at most once for any \c{game_drawstate}. If
1104 a puzzle needs to be redrawn at a different size, the mid-end will
1105 create a fresh drawstate.
1106
1107 \S{backend-colours} \cw{colours()}
1108
1109 \c float *(*colours)(frontend *fe, int *ncolours);
1110
1111 This function is responsible for telling the front end what colours
1112 the puzzle will need to draw itself.
1113
1114 It returns the number of colours required in \c{*ncolours}, and the
1115 return value from the function itself is a dynamically allocated
1116 array of three times that many \c{float}s, containing the red, green
1117 and blue components of each colour respectively as numbers in the
1118 range [0,1].
1119
1120 The second parameter passed to this function is a front end handle.
1121 The only things it is permitted to do with this handle are to call
1122 the front-end function called \cw{frontend_default_colour()} (see
1123 \k{frontend-default-colour}) or the utility function called
1124 \cw{game_mkhighlight()} (see \k{utils-game-mkhighlight}). (The
1125 latter is a wrapper on the former, so front end implementors only
1126 need to provide \cw{frontend_default_colour()}.) This allows
1127 \cw{colours()} to take local configuration into account when
1128 deciding on its own colour allocations. Most games use the front
1129 end's default colour as their background, apart from a few which
1130 depend on drawing relief highlights so they adjust the background
1131 colour if it's too light for highlights to show up against it.
1132
1133 Note that the colours returned from this function are for
1134 \e{drawing}, not for printing. Printing has an entirely different
1135 colour allocation policy.
1136
1137 \S{backend-anim-length} \cw{anim_length()}
1138
1139 \c float (*anim_length)(game_state *oldstate, game_state *newstate,
1140 \c                      int dir, game_ui *ui);
1141
1142 This function is called when a move is made, undone or redone. It is
1143 given the old and the new \c{game_state}, and its job is to decide
1144 whether the transition between the two needs to be animated or can
1145 be instant.
1146
1147 \c{oldstate} is the state that was current until this call;
1148 \c{newstate} is the state that will be current after it. \c{dir}
1149 specifies the chronological order of those states: if it is
1150 positive, then the transition is the result of a move or a redo (and
1151 so \c{newstate} is the later of the two moves), whereas if it is
1152 negative then the transition is the result of an undo (so that
1153 \c{newstate} is the \e{earlier} move).
1154
1155 If this function decides the transition should be animated, it
1156 returns the desired length of the animation in seconds. If not, it
1157 returns zero.
1158
1159 State changes as a result of a Restart operation are never animated;
1160 the mid-end will handle them internally and never consult this
1161 function at all. State changes as a result of Solve operations are
1162 also not animated by default, although you can change this for a
1163 particular game by setting a flag in \c{flags} (\k{backend-flags}).
1164
1165 The function is also passed a pointer to the local \c{game_ui}. It
1166 may refer to information in here to help with its decision (see
1167 \k{writing-conditional-anim} for an example of this), and/or it may
1168 \e{write} information about the nature of the animation which will
1169 be read later by \cw{redraw()}.
1170
1171 When this function is called, it may rely on \cw{changed_state()}
1172 having been called previously, so if \cw{anim_length()} needs to
1173 refer to information in the \c{game_ui}, then \cw{changed_state()}
1174 is a reliable place to have set that information up.
1175
1176 Move animations do not inhibit further input events. If the user
1177 continues playing before a move animation is complete, the animation
1178 will be abandoned and the display will jump straight to the final
1179 state.
1180
1181 \S{backend-flash-length} \cw{flash_length()}
1182
1183 \c float (*flash_length)(game_state *oldstate, game_state *newstate,
1184 \c                       int dir, game_ui *ui);
1185
1186 This function is called when a move is completed. (\q{Completed}
1187 means that not only has the move been made, but any animation which
1188 accompanied it has finished.) It decides whether the transition from
1189 \c{oldstate} to \c{newstate} merits a \q{flash}.
1190
1191 A flash is much like a move animation, but it is \e{not} interrupted
1192 by further user interface activity; it runs to completion in
1193 parallel with whatever else might be going on on the display. The
1194 only thing which will rush a flash to completion is another flash.
1195
1196 The purpose of flashes is to indicate that the game has been
1197 completed. They were introduced as a separate concept from move
1198 animations because of Net: the habit of most Net players (and
1199 certainly me) is to rotate a tile into place and immediately lock
1200 it, then move on to another tile. When you make your last move, at
1201 the instant the final tile is rotated into place the screen starts
1202 to flash to indicate victory \dash but if you then press the lock
1203 button out of habit, then the move animation is cancelled, and the
1204 victory flash does not complete. (And if you \e{don't} press the
1205 lock button, the completed grid will look untidy because there will
1206 be one unlocked square.) Therefore, I introduced a specific concept
1207 of a \q{flash} which is separate from a move animation and can
1208 proceed in parallel with move animations and any other display
1209 activity, so that the victory flash in Net is not cancelled by that
1210 final locking move.
1211
1212 The input parameters to \cw{flash_length()} are exactly the same as
1213 the ones to \cw{anim_length()}.
1214
1215 Just like \cw{anim_length()}, when this function is called, it may
1216 rely on \cw{changed_state()} having been called previously, so if it
1217 needs to refer to information in the \c{game_ui} then
1218 \cw{changed_state()} is a reliable place to have set that
1219 information up.
1220
1221 (Some games use flashes to indicate defeat as well as victory;
1222 Mines, for example, flashes in a different colour when you tread on
1223 a mine from the colour it uses when you complete the game. In order
1224 to achieve this, its \cw{flash_length()} function has to store a
1225 flag in the \c{game_ui} to indicate which flash type is required.)
1226
1227 \S{backend-redraw} \cw{redraw()}
1228
1229 \c void (*redraw)(drawing *dr, game_drawstate *ds,
1230 \c                game_state *oldstate, game_state *newstate, int dir,
1231 \c                game_ui *ui, float anim_time, float flash_time);
1232
1233 This function is responsible for actually drawing the contents of
1234 the game window, and for redrawing every time the game state or the
1235 \c{game_ui} changes.
1236
1237 The parameter \c{dr} is a drawing object which may be passed to the
1238 drawing API functions (see \k{drawing} for documentation of the
1239 drawing API). This function may not save \c{dr} and use it
1240 elsewhere; it must only use it for calling back to the drawing API
1241 functions within its own lifetime.
1242
1243 \c{ds} is the local \c{game_drawstate}, of course, and \c{ui} is the
1244 local \c{game_ui}.
1245
1246 \c{newstate} is the semantically-current game state, and is always
1247 non-\cw{NULL}. If \c{oldstate} is also non-\cw{NULL}, it means that
1248 a move has recently been made and the game is still in the process
1249 of displaying an animation linking the old and new states; in this
1250 situation, \c{anim_time} will give the length of time (in seconds)
1251 that the animation has already been running. If \c{oldstate} is
1252 \cw{NULL}, then \c{anim_time} is unused (and will hopefully be set
1253 to zero to avoid confusion).
1254
1255 \c{flash_time}, if it is is non-zero, denotes that the game is in
1256 the middle of a flash, and gives the time since the start of the
1257 flash. See \k{backend-flash-length} for general discussion of
1258 flashes.
1259
1260 The very first time this function is called for a new
1261 \c{game_drawstate}, it is expected to redraw the \e{entire} drawing
1262 area. Since this often involves drawing visual furniture which is
1263 never subsequently altered, it is often simplest to arrange this by
1264 having a special \q{first time} flag in the draw state, and
1265 resetting it after the first redraw.
1266
1267 When this function (or any subfunction) calls the drawing API, it is
1268 expected to pass colour indices which were previously defined by the
1269 \cw{colours()} function.
1270
1271 \H{backend-printing} Printing functions
1272
1273 This section discusses the back end functions that deal with
1274 printing puzzles out on paper.
1275
1276 \S{backend-can-print} \c{can_print}
1277
1278 \c int can_print;
1279
1280 This flag is set to \cw{TRUE} if the puzzle is capable of printing
1281 itself on paper. (This makes sense for some puzzles, such as Solo,
1282 which can be filled in with a pencil. Other puzzles, such as
1283 Twiddle, inherently involve moving things around and so would not
1284 make sense to print.)
1285
1286 If this flag is \cw{FALSE}, then the functions \cw{print_size()}
1287 and \cw{print()} will never be called.
1288
1289 \S{backend-can-print-in-colour} \c{can_print_in_colour}
1290
1291 \c int can_print_in_colour;
1292
1293 This flag is set to \cw{TRUE} if the puzzle is capable of printing
1294 itself differently when colour is available. For example, Map can
1295 actually print coloured regions in different \e{colours} rather than
1296 resorting to cross-hatching.
1297
1298 If the \c{can_print} flag is \cw{FALSE}, then this flag will be
1299 ignored.
1300
1301 \S{backend-print-size} \cw{print_size()}
1302
1303 \c void (*print_size)(game_params *params, float *x, float *y);
1304
1305 This function is passed a \c{game_params} structure and a tile size.
1306 It returns, in \c{*x} and \c{*y}, the preferred size in
1307 \e{millimetres} of that puzzle if it were to be printed out on paper.
1308
1309 If the \c{can_print} flag is \cw{FALSE}, this function will never be
1310 called.
1311
1312 \S{backend-print} \cw{print()}
1313
1314 \c void (*print)(drawing *dr, game_state *state, int tilesize);
1315
1316 This function is called when a puzzle is to be printed out on paper.
1317 It should use the drawing API functions (see \k{drawing}) to print
1318 itself.
1319
1320 This function is separate from \cw{redraw()} because it is often
1321 very different:
1322
1323 \b The printing function may not depend on pixel accuracy, since
1324 printer resolution is variable. Draw as if your canvas had infinite
1325 resolution.
1326
1327 \b The printing function sometimes needs to display things in a
1328 completely different style. Net, for example, is very different as
1329 an on-screen puzzle and as a printed one.
1330
1331 \b The printing function is often much simpler since it has no need
1332 to deal with repeated partial redraws.
1333
1334 However, there's no reason the printing and redraw functions can't
1335 share some code if they want to.
1336
1337 When this function (or any subfunction) calls the drawing API, the
1338 colour indices it passes should be colours which have been allocated
1339 by the \cw{print_*_colour()} functions within this execution of
1340 \cw{print()}. This is very different from the fixed small number of
1341 colours used in \cw{redraw()}, because printers do not have a
1342 limitation on the total number of colours that may be used. Some
1343 puzzles' printing functions might wish to allocate only one \q{ink}
1344 colour and use it for all drawing; others might wish to allocate
1345 \e{more} colours than are used on screen.
1346
1347 One possible colour policy worth mentioning specifically is that a
1348 puzzle's printing function might want to allocate the \e{same}
1349 colour indices as are used by the redraw function, so that code
1350 shared between drawing and printing does not have to keep switching
1351 its colour indices. In order to do this, the simplest thing is to
1352 make use of the fact that colour indices returned from
1353 \cw{print_*_colour()} are guaranteed to be in increasing order from
1354 zero. So if you have declared an \c{enum} defining three colours
1355 \cw{COL_BACKGROUND}, \cw{COL_THIS} and \cw{COL_THAT}, you might then
1356 write
1357
1358 \c int c;
1359 \c c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1360 \c c = print_mono_colour(dr, 0); assert(c == COL_THIS);
1361 \c c = print_mono_colour(dr, 0); assert(c == COL_THAT);
1362
1363 If the \c{can_print} flag is \cw{FALSE}, this function will never be
1364 called.
1365
1366 \H{backend-misc} Miscellaneous
1367
1368 \S{backend-can-format-as-text-ever} \c{can_format_as_text_ever}
1369
1370 \c int can_format_as_text_ever;
1371
1372 This boolean field is \cw{TRUE} if the game supports formatting a
1373 game state as ASCII text (typically ASCII art) for copying to the
1374 clipboard and pasting into other applications. If it is \cw{FALSE},
1375 front ends will not offer the \q{Copy} command at all.
1376
1377 If this field is \cw{TRUE}, the game does not necessarily have to
1378 support text formatting for \e{all} games: e.g. a game which can be
1379 played on a square grid or a triangular one might only support copy
1380 and paste for the former, because triangular grids in ASCII art are
1381 just too difficult.
1382
1383 If this field is \cw{FALSE}, the functions
1384 \cw{can_format_as_text_now()} (\k{backend-can-format-as-text-now})
1385 and \cw{text_format()} (\k{backend-text-format}) are never called.
1386
1387 \S{backend-can-format-as-text-now} \c{can_format_as_text_now()}
1388
1389 \c int (*can_format_as_text_now)(game_params *params);
1390
1391 This function is passed a \c{game_params} and returns a boolean,
1392 which is \cw{TRUE} if the game can support ASCII text output for
1393 this particular game type. If it returns \cw{FALSE}, front ends will
1394 grey out or otherwise disable the \q{Copy} command.
1395
1396 Games may enable and disable the copy-and-paste function for
1397 different game \e{parameters}, but are currently constrained to
1398 return the same answer from this function for all game \e{states}
1399 sharing the same parameters. In other words, the \q{Copy} function
1400 may enable or disable itself when the player changes game preset,
1401 but will never change during play of a single game or when another
1402 game of exactly the same type is generated.
1403
1404 This function should not take into account aspects of the game
1405 parameters which are not encoded by \cw{encode_params()}
1406 (\k{backend-encode-params}) when the \c{full} parameter is set to
1407 \cw{FALSE}. Such parameters will not necessarily match up between a
1408 call to this function and a subsequent call to \cw{text_format()}
1409 itself. (For instance, game \e{difficulty} should not affect whether
1410 the game can be copied to the clipboard. Only the actual visible
1411 \e{shape} of the game can affect that.)
1412
1413 \S{backend-text-format} \cw{text_format()}
1414
1415 \c char *(*text_format)(game_state *state);
1416
1417 This function is passed a \c{game_state}, and returns a newly
1418 allocated C string containing an ASCII representation of that game
1419 state. It is used to implement the \q{Copy} operation in many front
1420 ends.
1421
1422 This function will only ever be called if the back end field
1423 \c{can_format_as_text_ever} (\k{backend-can-format-as-text-ever}) is
1424 \cw{TRUE} \e{and} the function \cw{can_format_as_text_now()}
1425 (\k{backend-can-format-as-text-now}) has returned \cw{TRUE} for the
1426 currently selected game parameters.
1427
1428 The returned string may contain line endings (and will probably want
1429 to), using the normal C internal \cq{\\n} convention. For
1430 consistency between puzzles, all multi-line textual puzzle
1431 representations should \e{end} with a newline as well as containing
1432 them internally. (There are currently no puzzles which have a
1433 one-line ASCII representation, so there's no precedent yet for
1434 whether that should come with a newline or not.)
1435
1436 \S{backend-wants-statusbar} \cw{wants_statusbar()}
1437
1438 \c int wants_statusbar;
1439
1440 This boolean field is set to \cw{TRUE} if the puzzle has a use for a
1441 textual status line (to display score, completion status, currently
1442 active tiles, etc).
1443
1444 \S{backend-is-timed} \c{is_timed}
1445
1446 \c int is_timed;
1447
1448 This boolean field is \cw{TRUE} if the puzzle is time-critical. If
1449 so, the mid-end will maintain a game timer while the user plays.
1450
1451 If this field is \cw{FALSE}, then \cw{timing_state()} will never be
1452 called and need not do anything.
1453
1454 \S{backend-timing-state} \cw{timing_state()}
1455
1456 \c int (*timing_state)(game_state *state, game_ui *ui);
1457
1458 This function is passed the current \c{game_state} and the local
1459 \c{game_ui}; it returns \cw{TRUE} if the game timer should currently
1460 be running.
1461
1462 A typical use for the \c{game_ui} in this function is to note when
1463 the game was first completed (by setting a flag in
1464 \cw{changed_state()} \dash see \k{backend-changed-state}), and
1465 freeze the timer thereafter so that the user can undo back through
1466 their solution process without altering their time.
1467
1468 \S{backend-flags} \c{flags}
1469
1470 \c int flags;
1471
1472 This field contains miscellaneous per-backend flags. It consists of
1473 the bitwise OR of some combination of the following:
1474
1475 \dt \cw{BUTTON_BEATS(x,y)}
1476
1477 \dd Given any \cw{x} and \cw{y} from the set \{\cw{LEFT_BUTTON},
1478 \cw{MIDDLE_BUTTON}, \cw{RIGHT_BUTTON}\}, this macro evaluates to a
1479 bit flag which indicates that when buttons \cw{x} and \cw{y} are
1480 both pressed simultaneously, the mid-end should consider \cw{x} to
1481 have priority. (In the absence of any such flags, the mid-end will
1482 always consider the most recently pressed button to have priority.)
1483
1484 \dt \cw{SOLVE_ANIMATES}
1485
1486 \dd This flag indicates that moves generated by \cw{solve()}
1487 (\k{backend-solve}) are candidates for animation just like any other
1488 move. For most games, solve moves should not be animated, so the
1489 mid-end doesn't even bother calling \cw{anim_length()}
1490 (\k{backend-anim-length}), thus saving some special-case code in
1491 each game. On the rare occasion that animated solve moves are
1492 actually required, you can set this flag.
1493
1494 \dt \cw{REQUIRE_RBUTTON}
1495
1496 \dd This flag indicates that the puzzle cannot be usefully played
1497 without the use of mouse buttons other than the left one. On some
1498 PDA platforms, this flag is used by the front end to enable
1499 right-button emulation through an appropriate gesture. Note that a
1500 puzzle is not required to set this just because it \e{uses} the
1501 right button, but only if its use of the right button is critical to
1502 playing the game. (Slant, for example, uses the right button to
1503 cycle through the three square states in the opposite order from the
1504 left button, and hence can manage fine without it.)
1505
1506 \dt \cw{REQUIRE_NUMPAD}
1507
1508 \dd This flag indicates that the puzzle cannot be usefully played
1509 without the use of number-key input. On some PDA platforms it causes
1510 an emulated number pad to appear on the screen. Similarly to
1511 \cw{REQUIRE_RBUTTON}, a puzzle need not specify this simply if its
1512 use of the number keys is not critical.
1513
1514 \H{backend-initiative} Things a back end may do on its own initiative
1515
1516 This section describes a couple of things that a back end may choose
1517 to do by calling functions elsewhere in the program, which would not
1518 otherwise be obvious.
1519
1520 \S{backend-newrs} Create a random state
1521
1522 If a back end needs random numbers at some point during normal play,
1523 it can create a fresh \c{random_state} by first calling
1524 \c{get_random_seed} (\k{frontend-get-random-seed}) and then passing
1525 the returned seed data to \cw{random_new()}.
1526
1527 This is likely not to be what you want. If a puzzle needs randomness
1528 in the middle of play, it's likely to be more sensible to store some
1529 sort of random state within the \c{game_state}, so that the random
1530 numbers are tied to the particular game state and hence the player
1531 can't simply keep undoing their move until they get numbers they
1532 like better.
1533
1534 This facility is currently used only in Net, to implement the
1535 \q{jumble} command, which sets every unlocked tile to a new random
1536 orientation. This randomness \e{is} a reasonable use of the feature,
1537 because it's non-adversarial \dash there's no advantage to the user
1538 in getting different random numbers.
1539
1540 \S{backend-supersede} Supersede its own game description
1541
1542 In response to a move, a back end is (reluctantly) permitted to call
1543 \cw{midend_supersede_game_desc()}:
1544
1545 \c void midend_supersede_game_desc(midend *me,
1546 \c                                 char *desc, char *privdesc);
1547
1548 When the user selects \q{New Game}, the mid-end calls
1549 \cw{new_desc()} (\k{backend-new-desc}) to get a new game
1550 description, and (as well as using that to generate an initial game
1551 state) stores it for the save file and for telling to the user. The
1552 function above overwrites that game description, and also splits it
1553 in two. \c{desc} becomes the new game description which is provided
1554 to the user on request, and is also the one used to construct a new
1555 initial game state if the user selects \q{Restart}. \c{privdesc} is
1556 a \q{private} game description, used to reconstruct the game's
1557 initial state when reloading.
1558
1559 The distinction between the two, as well as the need for this
1560 function at all, comes from Mines. Mines begins with a blank grid
1561 and no idea of where the mines actually are; \cw{new_desc()} does
1562 almost no work in interactive mode, and simply returns a string
1563 encoding the \c{random_state}. When the user first clicks to open a
1564 tile, \e{then} Mines generates the mine positions, in such a way
1565 that the game is soluble from that starting point. Then it uses this
1566 function to supersede the random-state game description with a
1567 proper one. But it needs two: one containing the initial click
1568 location (because that's what you want to happen if you restart the
1569 game, and also what you want to send to a friend so that they play
1570 \e{the same game} as you), and one without the initial click
1571 location (because when you save and reload the game, you expect to
1572 see the same blank initial state as you had before saving).
1573
1574 I should stress again that this function is a horrid hack. Nobody
1575 should use it if they're not Mines; if you think you need to use it,
1576 think again repeatedly in the hope of finding a better way to do
1577 whatever it was you needed to do.
1578
1579 \C{drawing} The drawing API
1580
1581 The back end function \cw{redraw()} (\k{backend-redraw}) is required
1582 to draw the puzzle's graphics on the window's drawing area, or on
1583 paper if the puzzle is printable. To do this portably, it is
1584 provided with a drawing API allowing it to talk directly to the
1585 front end. In this chapter I document that API, both for the benefit
1586 of back end authors trying to use it and for front end authors
1587 trying to implement it.
1588
1589 The drawing API as seen by the back end is a collection of global
1590 functions, each of which takes a pointer to a \c{drawing} structure
1591 (a \q{drawing object}). These objects are supplied as parameters to
1592 the back end's \cw{redraw()} and \cw{print()} functions.
1593
1594 In fact these global functions are not implemented directly by the
1595 front end; instead, they are implemented centrally in \c{drawing.c}
1596 and form a small piece of middleware. The drawing API as supplied by
1597 the front end is a structure containing a set of function pointers,
1598 plus a \cq{void *} handle which is passed to each of those
1599 functions. This enables a single front end to switch between
1600 multiple implementations of the drawing API if necessary. For
1601 example, the Windows API supplies a printing mechanism integrated
1602 into the same GDI which deals with drawing in windows, and therefore
1603 the same API implementation can handle both drawing and printing;
1604 but on Unix, the most common way for applications to print is by
1605 producing PostScript output directly, and although it would be
1606 \e{possible} to write a single (say) \cw{draw_rect()} function which
1607 checked a global flag to decide whether to do GTK drawing operations
1608 or output PostScript to a file, it's much nicer to have two separate
1609 functions and switch between them as appropriate.
1610
1611 When drawing, the puzzle window is indexed by pixel coordinates,
1612 with the top left pixel defined as \cw{(0,0)} and the bottom right
1613 pixel \cw{(w-1,h-1)}, where \c{w} and \c{h} are the width and height
1614 values returned by the back end function \cw{compute_size()}
1615 (\k{backend-compute-size}).
1616
1617 When printing, the puzzle's print area is indexed in exactly the
1618 same way (with an arbitrary tile size provided by the printing
1619 module \c{printing.c}), to facilitate sharing of code between the
1620 drawing and printing routines. However, when printing, puzzles may
1621 no longer assume that the coordinate unit has any relationship to a
1622 pixel; the printer's actual resolution might very well not even be
1623 known at print time, so the coordinate unit might be smaller or
1624 larger than a pixel. Puzzles' print functions should restrict
1625 themselves to drawing geometric shapes rather than fiddly pixel
1626 manipulation.
1627
1628 \e{Puzzles' redraw functions may assume that the surface they draw
1629 on is persistent}. It is the responsibility of every front end to
1630 preserve the puzzle's window contents in the face of GUI window
1631 expose issues and similar. It is not permissible to request that the
1632 back end redraw any part of a window that it has already drawn,
1633 unless something has actually changed as a result of making moves in
1634 the puzzle.
1635
1636 Most front ends accomplish this by having the drawing routines draw
1637 on a stored bitmap rather than directly on the window, and copying
1638 the bitmap to the window every time a part of the window needs to be
1639 redrawn. Therefore, it is vitally important that whenever the back
1640 end does any drawing it informs the front end of which parts of the
1641 window it has accessed, and hence which parts need repainting. This
1642 is done by calling \cw{draw_update()} (\k{drawing-draw-update}).
1643
1644 In the following sections I first discuss the drawing API as seen by
1645 the back end, and then the \e{almost} identical function-pointer
1646 form seen by the front end.
1647
1648 \H{drawing-backend} Drawing API as seen by the back end
1649
1650 This section documents the back-end drawing API, in the form of
1651 functions which take a \c{drawing} object as an argument.
1652
1653 \S{drawing-draw-rect} \cw{draw_rect()}
1654
1655 \c void draw_rect(drawing *dr, int x, int y, int w, int h,
1656 \c                int colour);
1657
1658 Draws a filled rectangle in the puzzle window.
1659
1660 \c{x} and \c{y} give the coordinates of the top left pixel of the
1661 rectangle. \c{w} and \c{h} give its width and height. Thus, the
1662 horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1663 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1664 inclusive.
1665
1666 \c{colour} is an integer index into the colours array returned by
1667 the back end function \cw{colours()} (\k{backend-colours}).
1668
1669 There is no separate pixel-plotting function. If you want to plot a
1670 single pixel, the approved method is to use \cw{draw_rect()} with
1671 width and height set to 1.
1672
1673 Unlike many of the other drawing functions, this function is
1674 guaranteed to be pixel-perfect: the rectangle will be sharply
1675 defined and not anti-aliased or anything like that.
1676
1677 This function may be used for both drawing and printing.
1678
1679 \S{drawing-draw-rect-outline} \cw{draw_rect_outline()}
1680
1681 \c void draw_rect_outline(drawing *dr, int x, int y, int w, int h,
1682 \c                        int colour);
1683
1684 Draws an outline rectangle in the puzzle window.
1685
1686 \c{x} and \c{y} give the coordinates of the top left pixel of the
1687 rectangle. \c{w} and \c{h} give its width and height. Thus, the
1688 horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1689 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1690 inclusive.
1691
1692 \c{colour} is an integer index into the colours array returned by
1693 the back end function \cw{colours()} (\k{backend-colours}).
1694
1695 From a back end perspective, this function may be considered to be
1696 part of the drawing API. However, front ends are not required to
1697 implement it, since it is actually implemented centrally (in
1698 \cw{misc.c}) as a wrapper on \cw{draw_polygon()}.
1699
1700 This function may be used for both drawing and printing.
1701
1702 \S{drawing-draw-line} \cw{draw_line()}
1703
1704 \c void draw_line(drawing *dr, int x1, int y1, int x2, int y2,
1705 \c                int colour);
1706
1707 Draws a straight line in the puzzle window.
1708
1709 \c{x1} and \c{y1} give the coordinates of one end of the line.
1710 \c{x2} and \c{y2} give the coordinates of the other end. The line
1711 drawn includes both those points.
1712
1713 \c{colour} is an integer index into the colours array returned by
1714 the back end function \cw{colours()} (\k{backend-colours}).
1715
1716 Some platforms may perform anti-aliasing on this function.
1717 Therefore, do not assume that you can erase a line by drawing the
1718 same line over it in the background colour; anti-aliasing might
1719 lead to perceptible ghost artefacts around the vanished line.
1720
1721 This function may be used for both drawing and printing.
1722
1723 \S{drawing-draw-polygon} \cw{draw_polygon()}
1724
1725 \c void draw_polygon(drawing *dr, int *coords, int npoints,
1726 \c                   int fillcolour, int outlinecolour);
1727
1728 Draws an outlined or filled polygon in the puzzle window.
1729
1730 \c{coords} is an array of \cw{(2*npoints)} integers, containing the
1731 \c{x} and \c{y} coordinates of \c{npoints} vertices.
1732
1733 \c{fillcolour} and \c{outlinecolour} are integer indices into the
1734 colours array returned by the back end function \cw{colours()}
1735 (\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
1736 indicate that the polygon should be outlined only.
1737
1738 The polygon defined by the specified list of vertices is first
1739 filled in \c{fillcolour}, if specified, and then outlined in
1740 \c{outlinecolour}.
1741
1742 \c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
1743 (and front ends are permitted to enforce this by assertion). This is
1744 because different platforms disagree on whether a filled polygon
1745 should include its boundary line or not, so drawing \e{only} a
1746 filled polygon would have non-portable effects. If you want your
1747 filled polygon not to have a visible outline, you must set
1748 \c{outlinecolour} to the same as \c{fillcolour}.
1749
1750 Some platforms may perform anti-aliasing on this function.
1751 Therefore, do not assume that you can erase a polygon by drawing the
1752 same polygon over it in the background colour. Also, be prepared for
1753 the polygon to extend a pixel beyond its obvious bounding box as a
1754 result of this; if you really need it not to do this to avoid
1755 interfering with other delicate graphics, you should probably use
1756 \cw{clip()} (\k{drawing-clip}).
1757
1758 This function may be used for both drawing and printing.
1759
1760 \S{drawing-draw-circle} \cw{draw_circle()}
1761
1762 \c void draw_circle(drawing *dr, int cx, int cy, int radius,
1763 \c                  int fillcolour, int outlinecolour);
1764
1765 Draws an outlined or filled circle in the puzzle window.
1766
1767 \c{cx} and \c{cy} give the coordinates of the centre of the circle.
1768 \c{radius} gives its radius. The total horizontal pixel extent of
1769 the circle is from \c{cx-radius+1} to \c{cx+radius-1} inclusive, and
1770 the vertical extent similarly around \c{cy}.
1771
1772 \c{fillcolour} and \c{outlinecolour} are integer indices into the
1773 colours array returned by the back end function \cw{colours()}
1774 (\k{backend-colours}). \c{fillcolour} may also be \cw{-1} to
1775 indicate that the circle should be outlined only.
1776
1777 The circle is first filled in \c{fillcolour}, if specified, and then
1778 outlined in \c{outlinecolour}.
1779
1780 \c{outlinecolour} may \e{not} be \cw{-1}; it must be a valid colour
1781 (and front ends are permitted to enforce this by assertion). This is
1782 because different platforms disagree on whether a filled circle
1783 should include its boundary line or not, so drawing \e{only} a
1784 filled circle would have non-portable effects. If you want your
1785 filled circle not to have a visible outline, you must set
1786 \c{outlinecolour} to the same as \c{fillcolour}.
1787
1788 Some platforms may perform anti-aliasing on this function.
1789 Therefore, do not assume that you can erase a circle by drawing the
1790 same circle over it in the background colour. Also, be prepared for
1791 the circle to extend a pixel beyond its obvious bounding box as a
1792 result of this; if you really need it not to do this to avoid
1793 interfering with other delicate graphics, you should probably use
1794 \cw{clip()} (\k{drawing-clip}).
1795
1796 This function may be used for both drawing and printing.
1797
1798 \S{drawing-draw-text} \cw{draw_text()}
1799
1800 \c void draw_text(drawing *dr, int x, int y, int fonttype,
1801 \c                int fontsize, int align, int colour, char *text);
1802
1803 Draws text in the puzzle window.
1804
1805 \c{x} and \c{y} give the coordinates of a point. The relation of
1806 this point to the location of the text is specified by \c{align},
1807 which is a bitwise OR of horizontal and vertical alignment flags:
1808
1809 \dt \cw{ALIGN_VNORMAL}
1810
1811 \dd Indicates that \c{y} is aligned with the baseline of the text.
1812
1813 \dt \cw{ALIGN_VCENTRE}
1814
1815 \dd Indicates that \c{y} is aligned with the vertical centre of the
1816 text. (In fact, it's aligned with the vertical centre of normal
1817 \e{capitalised} text: displaying two pieces of text with
1818 \cw{ALIGN_VCENTRE} at the same \cw{y}-coordinate will cause their
1819 baselines to be aligned with one another, even if one is an ascender
1820 and the other a descender.)
1821
1822 \dt \cw{ALIGN_HLEFT}
1823
1824 \dd Indicates that \c{x} is aligned with the left-hand end of the
1825 text.
1826
1827 \dt \cw{ALIGN_HCENTRE}
1828
1829 \dd Indicates that \c{x} is aligned with the horizontal centre of
1830 the text.
1831
1832 \dt \cw{ALIGN_HRIGHT}
1833
1834 \dd Indicates that \c{x} is aligned with the right-hand end of the
1835 text.
1836
1837 \c{fonttype} is either \cw{FONT_FIXED} or \cw{FONT_VARIABLE}, for a
1838 monospaced or proportional font respectively. (No more detail than
1839 that may be specified; it would only lead to portability issues
1840 between different platforms.)
1841
1842 \c{fontsize} is the desired size, in pixels, of the text. This size
1843 corresponds to the overall point size of the text, not to any
1844 internal dimension such as the cap-height.
1845
1846 \c{colour} is an integer index into the colours array returned by
1847 the back end function \cw{colours()} (\k{backend-colours}).
1848
1849 This function may be used for both drawing and printing.
1850
1851 The character set used to encode the text passed to this function is
1852 specified \e{by the drawing object}, although it must be a superset
1853 of ASCII. If a puzzle wants to display text that is not contained in
1854 ASCII, it should use the \cw{text_fallback()} function
1855 (\k{drawing-text-fallback}) to query the drawing object for an
1856 appropriate representation of the characters it wants.
1857
1858 \S{drawing-text-fallback} \cw{text_fallback()}
1859
1860 \c char *text_fallback(drawing *dr, const char *const *strings,
1861 \c                     int nstrings);
1862
1863 This function is used to request a translation of UTF-8 text into
1864 whatever character encoding is expected by the drawing object's
1865 implementation of \cw{draw_text()}.
1866
1867 The input is a list of strings encoded in UTF-8: \cw{nstrings} gives
1868 the number of strings in the list, and \cw{strings[0]},
1869 \cw{strings[1]}, ..., \cw{strings[nstrings-1]} are the strings
1870 themselves.
1871
1872 The returned string (which is dynamically allocated and must be
1873 freed when finished with) is derived from the first string in the
1874 list that the drawing object expects to be able to display reliably;
1875 it will consist of that string translated into the character set
1876 expected by \cw{draw_text()}.
1877
1878 Drawing implementations are not required to handle anything outside
1879 ASCII, but are permitted to assume that \e{some} string will be
1880 successfully translated. So every call to this function must include
1881 a string somewhere in the list (presumably the last element) which
1882 consists of nothing but ASCII, to be used by any front end which
1883 cannot handle anything else.
1884
1885 For example, if a puzzle wished to display a string including a
1886 multiplication sign (U+00D7 in Unicode, represented by the bytes C3
1887 97 in UTF-8), it might do something like this:
1888
1889 \c static const char *const times_signs[] = { "\xC3\x97", "x" };
1890 \c char *times_sign = text_fallback(dr, times_signs, 2);
1891 \c sprintf(buffer, "%d%s%d", width, times_sign, height);
1892 \c draw_text(dr, x, y, font, size, align, colour, buffer);
1893 \c sfree(buffer);
1894
1895 which would draw a string with a times sign in the middle on
1896 platforms that support it, and fall back to a simple ASCII \cq{x}
1897 where there was no alternative.
1898
1899 \S{drawing-clip} \cw{clip()}
1900
1901 \c void clip(drawing *dr, int x, int y, int w, int h);
1902
1903 Establishes a clipping rectangle in the puzzle window.
1904
1905 \c{x} and \c{y} give the coordinates of the top left pixel of the
1906 clipping rectangle. \c{w} and \c{h} give its width and height. Thus,
1907 the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1908 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1909 inclusive. (These are exactly the same semantics as
1910 \cw{draw_rect()}.)
1911
1912 After this call, no drawing operation will affect anything outside
1913 the specified rectangle. The effect can be reversed by calling
1914 \cw{unclip()} (\k{drawing-unclip}).
1915
1916 Back ends should not assume that a clipping rectangle will be
1917 automatically cleared up by the front end if it's left lying around;
1918 that might work on current front ends, but shouldn't be relied upon.
1919 Always explicitly call \cw{unclip()}.
1920
1921 This function may be used for both drawing and printing.
1922
1923 \S{drawing-unclip} \cw{unclip()}
1924
1925 \c void unclip(drawing *dr);
1926
1927 Reverts the effect of a previous call to \cw{clip()}. After this
1928 call, all drawing operations will be able to affect the entire
1929 puzzle window again.
1930
1931 This function may be used for both drawing and printing.
1932
1933 \S{drawing-draw-update} \cw{draw_update()}
1934
1935 \c void draw_update(drawing *dr, int x, int y, int w, int h);
1936
1937 Informs the front end that a rectangular portion of the puzzle
1938 window has been drawn on and needs to be updated.
1939
1940 \c{x} and \c{y} give the coordinates of the top left pixel of the
1941 update rectangle. \c{w} and \c{h} give its width and height. Thus,
1942 the horizontal extent of the rectangle runs from \c{x} to \c{x+w-1}
1943 inclusive, and the vertical extent from \c{y} to \c{y+h-1}
1944 inclusive. (These are exactly the same semantics as
1945 \cw{draw_rect()}.)
1946
1947 The back end redraw function \e{must} call this function to report
1948 any changes it has made to the window. Otherwise, those changes may
1949 not become immediately visible, and may then appear at an
1950 unpredictable subsequent time such as the next time the window is
1951 covered and re-exposed.
1952
1953 This function is only important when drawing. It may be called when
1954 printing as well, but doing so is not compulsory, and has no effect.
1955 (So if you have a shared piece of code between the drawing and
1956 printing routines, that code may safely call \cw{draw_update()}.)
1957
1958 \S{drawing-status-bar} \cw{status_bar()}
1959
1960 \c void status_bar(drawing *dr, char *text);
1961
1962 Sets the text in the game's status bar to \c{text}. The text is copied
1963 from the supplied buffer, so the caller is free to deallocate or
1964 modify the buffer after use.
1965
1966 (This function is not exactly a \e{drawing} function, but it shares
1967 with the drawing API the property that it may only be called from
1968 within the back end redraw function, so this is as good a place as
1969 any to document it.)
1970
1971 The supplied text is filtered through the mid-end for optional
1972 rewriting before being passed on to the front end; the mid-end will
1973 prepend the current game time if the game is timed (and may in
1974 future perform other rewriting if it seems like a good idea).
1975
1976 This function is for drawing only; it must never be called during
1977 printing.
1978
1979 \S{drawing-blitter} Blitter functions
1980
1981 This section describes a group of related functions which save and
1982 restore a section of the puzzle window. This is most commonly used
1983 to implement user interfaces involving dragging a puzzle element
1984 around the window: at the end of each call to \cw{redraw()}, if an
1985 object is currently being dragged, the back end saves the window
1986 contents under that location and then draws the dragged object, and
1987 at the start of the next \cw{redraw()} the first thing it does is to
1988 restore the background.
1989
1990 The front end defines an opaque type called a \c{blitter}, which is
1991 capable of storing a rectangular area of a specified size.
1992
1993 Blitter functions are for drawing only; they must never be called
1994 during printing.
1995
1996 \S2{drawing-blitter-new} \cw{blitter_new()}
1997
1998 \c blitter *blitter_new(drawing *dr, int w, int h);
1999
2000 Creates a new blitter object which stores a rectangle of size \c{w}
2001 by \c{h} pixels. Returns a pointer to the blitter object.
2002
2003 Blitter objects are best stored in the \c{game_drawstate}. A good
2004 time to create them is in the \cw{set_size()} function
2005 (\k{backend-set-size}), since it is at this point that you first
2006 know how big a rectangle they will need to save.
2007
2008 \S2{drawing-blitter-free} \cw{blitter_free()}
2009
2010 \c void blitter_free(drawing *dr, blitter *bl);
2011
2012 Disposes of a blitter object. Best called in \cw{free_drawstate()}.
2013 (However, check that the blitter object is not \cw{NULL} before
2014 attempting to free it; it is possible that a draw state might be
2015 created and freed without ever having \cw{set_size()} called on it
2016 in between.)
2017
2018 \S2{drawing-blitter-save} \cw{blitter_save()}
2019
2020 \c void blitter_save(drawing *dr, blitter *bl, int x, int y);
2021
2022 This is a true drawing API function, in that it may only be called
2023 from within the game redraw routine. It saves a rectangular portion
2024 of the puzzle window into the specified blitter object.
2025
2026 \c{x} and \c{y} give the coordinates of the top left corner of the
2027 saved rectangle. The rectangle's width and height are the ones
2028 specified when the blitter object was created.
2029
2030 This function is required to cope and do the right thing if \c{x}
2031 and \c{y} are out of range. (The right thing probably means saving
2032 whatever part of the blitter rectangle overlaps with the visible
2033 area of the puzzle window.)
2034
2035 \S2{drawing-blitter-load} \cw{blitter_load()}
2036
2037 \c void blitter_load(drawing *dr, blitter *bl, int x, int y);
2038
2039 This is a true drawing API function, in that it may only be called
2040 from within the game redraw routine. It restores a rectangular
2041 portion of the puzzle window from the specified blitter object.
2042
2043 \c{x} and \c{y} give the coordinates of the top left corner of the
2044 rectangle to be restored. The rectangle's width and height are the
2045 ones specified when the blitter object was created.
2046
2047 Alternatively, you can specify both \c{x} and \c{y} as the special
2048 value \cw{BLITTER_FROMSAVED}, in which case the rectangle will be
2049 restored to exactly where it was saved from. (This is probably what
2050 you want to do almost all the time, if you're using blitters to
2051 implement draggable puzzle elements.)
2052
2053 This function is required to cope and do the right thing if \c{x}
2054 and \c{y} (or the equivalent ones saved in the blitter) are out of
2055 range. (The right thing probably means restoring whatever part of
2056 the blitter rectangle overlaps with the visible area of the puzzle
2057 window.)
2058
2059 If this function is called on a blitter which had previously been
2060 saved from a partially out-of-range rectangle, then the parts of the
2061 saved bitmap which were not visible at save time are undefined. If
2062 the blitter is restored to a different position so as to make those
2063 parts visible, the effect on the drawing area is undefined.
2064
2065 \S{print-mono-colour} \cw{print_mono_colour()}
2066
2067 \c int print_mono_colour(drawing *dr, int grey);
2068
2069 This function allocates a colour index for a simple monochrome
2070 colour during printing.
2071
2072 \c{grey} must be 0 or 1. If \c{grey} is 0, the colour returned is
2073 black; if \c{grey} is 1, the colour is white.
2074
2075 \S{print-grey-colour} \cw{print_grey_colour()}
2076
2077 \c int print_grey_colour(drawing *dr, float grey);
2078
2079 This function allocates a colour index for a grey-scale colour
2080 during printing.
2081
2082 \c{grey} may be any number between 0 (black) and 1 (white); for
2083 example, 0.5 indicates a medium grey.
2084
2085 The chosen colour will be rendered to the limits of the printer's
2086 halftoning capability.
2087
2088 \S{print-hatched-colour} \cw{print_hatched_colour()}
2089
2090 \c int print_hatched_colour(drawing *dr, int hatch);
2091
2092 This function allocates a colour index which does not represent a
2093 literal \e{colour}. Instead, regions shaded in this colour will be
2094 hatched with parallel lines. The \c{hatch} parameter defines what
2095 type of hatching should be used in place of this colour:
2096
2097 \dt \cw{HATCH_SLASH}
2098
2099 \dd This colour will be hatched by lines slanting to the right at 45
2100 degrees. 
2101
2102 \dt \cw{HATCH_BACKSLASH}
2103
2104 \dd This colour will be hatched by lines slanting to the left at 45
2105 degrees.
2106
2107 \dt \cw{HATCH_HORIZ}
2108
2109 \dd This colour will be hatched by horizontal lines.
2110
2111 \dt \cw{HATCH_VERT}
2112
2113 \dd This colour will be hatched by vertical lines.
2114
2115 \dt \cw{HATCH_PLUS}
2116
2117 \dd This colour will be hatched by criss-crossing horizontal and
2118 vertical lines.
2119
2120 \dt \cw{HATCH_X}
2121
2122 \dd This colour will be hatched by criss-crossing diagonal lines.
2123
2124 Colours defined to use hatching may not be used for drawing lines or
2125 text; they may only be used for filling areas. That is, they may be
2126 used as the \c{fillcolour} parameter to \cw{draw_circle()} and
2127 \cw{draw_polygon()}, and as the colour parameter to
2128 \cw{draw_rect()}, but may not be used as the \c{outlinecolour}
2129 parameter to \cw{draw_circle()} or \cw{draw_polygon()}, or with
2130 \cw{draw_line()} or \cw{draw_text()}.
2131
2132 \S{print-rgb-mono-colour} \cw{print_rgb_mono_colour()}
2133
2134 \c int print_rgb_mono_colour(drawing *dr, float r, float g,
2135 \c                           float b, float grey);
2136
2137 This function allocates a colour index for a fully specified RGB
2138 colour during printing.
2139
2140 \c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.
2141
2142 If printing in black and white only, these values will be ignored,
2143 and either pure black or pure white will be used instead, according
2144 to the \q{grey} parameter. (The fallback colour is the same as the
2145 one which would be allocated by \cw{print_mono_colour(grey)}.)
2146
2147 \S{print-rgb-grey-colour} \cw{print_rgb_grey_colour()}
2148
2149 \c int print_rgb_grey_colour(drawing *dr, float r, float g,
2150 \c                           float b, float grey);
2151
2152 This function allocates a colour index for a fully specified RGB
2153 colour during printing.
2154
2155 \c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.
2156
2157 If printing in black and white only, these values will be ignored,
2158 and a shade of grey given by the \c{grey} parameter will be used
2159 instead. (The fallback colour is the same as the one which would be
2160 allocated by \cw{print_grey_colour(grey)}.)
2161
2162 \S{print-rgb-hatched-colour} \cw{print_rgb_hatched_colour()}
2163
2164 \c int print_rgb_hatched_colour(drawing *dr, float r, float g,
2165 \c                              float b, float hatched);
2166
2167 This function allocates a colour index for a fully specified RGB
2168 colour during printing.
2169
2170 \c{r}, \c{g} and \c{b} may each be anywhere in the range from 0 to 1.
2171
2172 If printing in black and white only, these values will be ignored,
2173 and a form of cross-hatching given by the \c{hatch} parameter will
2174 be used instead; see \k{print-hatched-colour} for the possible
2175 values of this parameter. (The fallback colour is the same as the
2176 one which would be allocated by \cw{print_hatched_colour(hatch)}.)
2177
2178 \S{print-line-width} \cw{print_line_width()}
2179
2180 \c void print_line_width(drawing *dr, int width);
2181
2182 This function is called to set the thickness of lines drawn during
2183 printing. It is meaningless in drawing: all lines drawn by
2184 \cw{draw_line()}, \cw{draw_circle} and \cw{draw_polygon()} are one
2185 pixel in thickness. However, in printing there is no clear
2186 definition of a pixel and so line widths must be explicitly
2187 specified.
2188
2189 The line width is specified in the usual coordinate system. Note,
2190 however, that it is a hint only: the central printing system may
2191 choose to vary line thicknesses at user request or due to printer
2192 capabilities.
2193
2194 \S{print-line-dotted} \cw{print_line_dotted()}
2195
2196 \c void print_line_dotted(drawing *dr, int dotted);
2197
2198 This function is called to toggle the drawing of dotted lines during
2199 printing. It is not supported during drawing.
2200
2201 The parameter \cq{dotted} is a boolean; \cw{TRUE} means that future
2202 lines drawn by \cw{draw_line()}, \cw{draw_circle} and
2203 \cw{draw_polygon()} will be dotted, and \cw{FALSE} means that they
2204 will be solid.
2205
2206 Some front ends may impose restrictions on the width of dotted
2207 lines. Asking for a dotted line via this front end will override any
2208 line width request if the front end requires it.
2209
2210 \H{drawing-frontend} The drawing API as implemented by the front end
2211
2212 This section describes the drawing API in the function-pointer form
2213 in which it is implemented by a front end.
2214
2215 (It isn't only platform-specific front ends which implement this
2216 API; the platform-independent module \c{ps.c} also provides an
2217 implementation of it which outputs PostScript. Thus, any platform
2218 which wants to do PS printing can do so with minimum fuss.)
2219
2220 The following entries all describe function pointer fields in a
2221 structure called \c{drawing_api}. Each of the functions takes a
2222 \cq{void *} context pointer, which it should internally cast back to
2223 a more useful type. Thus, a drawing \e{object} (\c{drawing *)}
2224 suitable for passing to the back end redraw or printing functions
2225 is constructed by passing a \c{drawing_api} and a \cq{void *} to the
2226 function \cw{drawing_new()} (see \k{drawing-new}).
2227
2228 \S{drawingapi-draw-text} \cw{draw_text()}
2229
2230 \c void (*draw_text)(void *handle, int x, int y, int fonttype,
2231 \c                   int fontsize, int align, int colour, char *text);
2232
2233 This function behaves exactly like the back end \cw{draw_text()}
2234 function; see \k{drawing-draw-text}.
2235
2236 \S{drawingapi-draw-rect} \cw{draw_rect()}
2237
2238 \c void (*draw_rect)(void *handle, int x, int y, int w, int h,
2239 \c                   int colour);
2240
2241 This function behaves exactly like the back end \cw{draw_rect()}
2242 function; see \k{drawing-draw-rect}.
2243
2244 \S{drawingapi-draw-line} \cw{draw_line()}
2245
2246 \c void (*draw_line)(void *handle, int x1, int y1, int x2, int y2,
2247 \c                   int colour);
2248
2249 This function behaves exactly like the back end \cw{draw_line()}
2250 function; see \k{drawing-draw-line}.
2251
2252 \S{drawingapi-draw-polygon} \cw{draw_polygon()}
2253
2254 \c void (*draw_polygon)(void *handle, int *coords, int npoints,
2255 \c                      int fillcolour, int outlinecolour);
2256
2257 This function behaves exactly like the back end \cw{draw_polygon()}
2258 function; see \k{drawing-draw-polygon}.
2259
2260 \S{drawingapi-draw-circle} \cw{draw_circle()}
2261
2262 \c void (*draw_circle)(void *handle, int cx, int cy, int radius,
2263 \c                     int fillcolour, int outlinecolour);
2264
2265 This function behaves exactly like the back end \cw{draw_circle()}
2266 function; see \k{drawing-draw-circle}.
2267
2268 \S{drawingapi-draw-update} \cw{draw_update()}
2269
2270 \c void (*draw_update)(void *handle, int x, int y, int w, int h);
2271
2272 This function behaves exactly like the back end \cw{draw_update()}
2273 function; see \k{drawing-draw-update}.
2274
2275 An implementation of this API which only supports printing is
2276 permitted to define this function pointer to be \cw{NULL} rather
2277 than bothering to define an empty function. The middleware in
2278 \cw{drawing.c} will notice and avoid calling it.
2279
2280 \S{drawingapi-clip} \cw{clip()}
2281
2282 \c void (*clip)(void *handle, int x, int y, int w, int h);
2283
2284 This function behaves exactly like the back end \cw{clip()}
2285 function; see \k{drawing-clip}.
2286
2287 \S{drawingapi-unclip} \cw{unclip()}
2288
2289 \c void (*unclip)(void *handle);
2290
2291 This function behaves exactly like the back end \cw{unclip()}
2292 function; see \k{drawing-unclip}.
2293
2294 \S{drawingapi-start-draw} \cw{start_draw()}
2295
2296 \c void (*start_draw)(void *handle);
2297
2298 This function is called at the start of drawing. It allows the front
2299 end to initialise any temporary data required to draw with, such as
2300 device contexts.
2301
2302 Implementations of this API which do not provide drawing services
2303 may define this function pointer to be \cw{NULL}; it will never be
2304 called unless drawing is attempted.
2305
2306 \S{drawingapi-end-draw} \cw{end_draw()}
2307
2308 \c void (*end_draw)(void *handle);
2309
2310 This function is called at the end of drawing. It allows the front
2311 end to do cleanup tasks such as deallocating device contexts and
2312 scheduling appropriate GUI redraw events.
2313
2314 Implementations of this API which do not provide drawing services
2315 may define this function pointer to be \cw{NULL}; it will never be
2316 called unless drawing is attempted.
2317
2318 \S{drawingapi-status-bar} \cw{status_bar()}
2319
2320 \c void (*status_bar)(void *handle, char *text);
2321
2322 This function behaves exactly like the back end \cw{status_bar()}
2323 function; see \k{drawing-status-bar}.
2324
2325 Front ends implementing this function need not worry about it being
2326 called repeatedly with the same text; the middleware code in
2327 \cw{status_bar()} will take care of this.
2328
2329 Implementations of this API which do not provide drawing services
2330 may define this function pointer to be \cw{NULL}; it will never be
2331 called unless drawing is attempted.
2332
2333 \S{drawingapi-blitter-new} \cw{blitter_new()}
2334
2335 \c blitter *(*blitter_new)(void *handle, int w, int h);
2336
2337 This function behaves exactly like the back end \cw{blitter_new()}
2338 function; see \k{drawing-blitter-new}.
2339
2340 Implementations of this API which do not provide drawing services
2341 may define this function pointer to be \cw{NULL}; it will never be
2342 called unless drawing is attempted.
2343
2344 \S{drawingapi-blitter-free} \cw{blitter_free()}
2345
2346 \c void (*blitter_free)(void *handle, blitter *bl);
2347
2348 This function behaves exactly like the back end \cw{blitter_free()}
2349 function; see \k{drawing-blitter-free}.
2350
2351 Implementations of this API which do not provide drawing services
2352 may define this function pointer to be \cw{NULL}; it will never be
2353 called unless drawing is attempted.
2354
2355 \S{drawingapi-blitter-save} \cw{blitter_save()}
2356
2357 \c void (*blitter_save)(void *handle, blitter *bl, int x, int y);
2358
2359 This function behaves exactly like the back end \cw{blitter_save()}
2360 function; see \k{drawing-blitter-save}.
2361
2362 Implementations of this API which do not provide drawing services
2363 may define this function pointer to be \cw{NULL}; it will never be
2364 called unless drawing is attempted.
2365
2366 \S{drawingapi-blitter-load} \cw{blitter_load()}
2367
2368 \c void (*blitter_load)(void *handle, blitter *bl, int x, int y);
2369
2370 This function behaves exactly like the back end \cw{blitter_load()}
2371 function; see \k{drawing-blitter-load}.
2372
2373 Implementations of this API which do not provide drawing services
2374 may define this function pointer to be \cw{NULL}; it will never be
2375 called unless drawing is attempted.
2376
2377 \S{drawingapi-begin-doc} \cw{begin_doc()}
2378
2379 \c void (*begin_doc)(void *handle, int pages);
2380
2381 This function is called at the beginning of a printing run. It gives
2382 the front end an opportunity to initialise any required printing
2383 subsystem. It also provides the number of pages in advance.
2384
2385 Implementations of this API which do not provide printing services
2386 may define this function pointer to be \cw{NULL}; it will never be
2387 called unless printing is attempted.
2388
2389 \S{drawingapi-begin-page} \cw{begin_page()}
2390
2391 \c void (*begin_page)(void *handle, int number);
2392
2393 This function is called during printing, at the beginning of each
2394 page. It gives the page number (numbered from 1 rather than 0, so
2395 suitable for use in user-visible contexts).
2396
2397 Implementations of this API which do not provide printing services
2398 may define this function pointer to be \cw{NULL}; it will never be
2399 called unless printing is attempted.
2400
2401 \S{drawingapi-begin-puzzle} \cw{begin_puzzle()}
2402
2403 \c void (*begin_puzzle)(void *handle, float xm, float xc,
2404 \c                      float ym, float yc, int pw, int ph, float wmm);
2405
2406 This function is called during printing, just before printing a
2407 single puzzle on a page. It specifies the size and location of the
2408 puzzle on the page.
2409
2410 \c{xm} and \c{xc} specify the horizontal position of the puzzle on
2411 the page, as a linear function of the page width. The front end is
2412 expected to multiply the page width by \c{xm}, add \c{xc} (measured
2413 in millimetres), and use the resulting x-coordinate as the left edge
2414 of the puzzle.
2415
2416 Similarly, \c{ym} and \c{yc} specify the vertical position of the
2417 puzzle as a function of the page height: the page height times
2418 \c{ym}, plus \c{yc} millimetres, equals the desired distance from
2419 the top of the page to the top of the puzzle.
2420
2421 (This unwieldy mechanism is required because not all printing
2422 systems can communicate the page size back to the software. The
2423 PostScript back end, for example, writes out PS which determines the
2424 page size at print time by means of calling \cq{clippath}, and
2425 centres the puzzles within that. Thus, exactly the same PS file
2426 works on A4 or on US Letter paper without needing local
2427 configuration, which simplifies matters.)
2428
2429 \cw{pw} and \cw{ph} give the size of the puzzle in drawing API
2430 coordinates. The printing system will subsequently call the puzzle's
2431 own print function, which will in turn call drawing API functions in
2432 the expectation that an area \cw{pw} by \cw{ph} units is available
2433 to draw the puzzle on.
2434
2435 Finally, \cw{wmm} gives the desired width of the puzzle in
2436 millimetres. (The aspect ratio is expected to be preserved, so if
2437 the desired puzzle height is also needed then it can be computed as
2438 \cw{wmm*ph/pw}.)
2439
2440 Implementations of this API which do not provide printing services
2441 may define this function pointer to be \cw{NULL}; it will never be
2442 called unless printing is attempted.
2443
2444 \S{drawingapi-end-puzzle} \cw{end_puzzle()}
2445
2446 \c void (*end_puzzle)(void *handle);
2447
2448 This function is called after the printing of a specific puzzle is
2449 complete.
2450
2451 Implementations of this API which do not provide printing services
2452 may define this function pointer to be \cw{NULL}; it will never be
2453 called unless printing is attempted.
2454
2455 \S{drawingapi-end-page} \cw{end_page()}
2456
2457 \c void (*end_page)(void *handle, int number);
2458
2459 This function is called after the printing of a page is finished.
2460
2461 Implementations of this API which do not provide printing services
2462 may define this function pointer to be \cw{NULL}; it will never be
2463 called unless printing is attempted.
2464
2465 \S{drawingapi-end-doc} \cw{end_doc()}
2466
2467 \c void (*end_doc)(void *handle);
2468
2469 This function is called after the printing of the entire document is
2470 finished. This is the moment to close files, send things to the
2471 print spooler, or whatever the local convention is.
2472
2473 Implementations of this API which do not provide printing services
2474 may define this function pointer to be \cw{NULL}; it will never be
2475 called unless printing is attempted.
2476
2477 \S{drawingapi-line-width} \cw{line_width()}
2478
2479 \c void (*line_width)(void *handle, float width);
2480
2481 This function is called to set the line thickness, during printing
2482 only. Note that the width is a \cw{float} here, where it was an
2483 \cw{int} as seen by the back end. This is because \cw{drawing.c} may
2484 have scaled it on the way past.
2485
2486 However, the width is still specified in the same coordinate system
2487 as the rest of the drawing.
2488
2489 Implementations of this API which do not provide printing services
2490 may define this function pointer to be \cw{NULL}; it will never be
2491 called unless printing is attempted.
2492
2493 \S{drawingapi-text-fallback} \cw{text_fallback()}
2494
2495 \c char *(*text_fallback)(void *handle, const char *const *strings,
2496 \c                        int nstrings);
2497
2498 This function behaves exactly like the back end \cw{text_fallback()}
2499 function; see \k{drawing-text-fallback}.
2500
2501 Implementations of this API which do not support any characters
2502 outside ASCII may define this function pointer to be \cw{NULL}, in
2503 which case the central code in \cw{drawing.c} will provide a default
2504 implementation.
2505
2506 \H{drawingapi-frontend} The drawing API as called by the front end
2507
2508 There are a small number of functions provided in \cw{drawing.c}
2509 which the front end needs to \e{call}, rather than helping to
2510 implement. They are described in this section.
2511
2512 \S{drawing-new} \cw{drawing_new()}
2513
2514 \c drawing *drawing_new(const drawing_api *api, midend *me,
2515 \c                      void *handle);
2516
2517 This function creates a drawing object. It is passed a
2518 \c{drawing_api}, which is a structure containing nothing but
2519 function pointers; and also a \cq{void *} handle. The handle is
2520 passed back to each function pointer when it is called.
2521
2522 The \c{midend} parameter is used for rewriting the status bar
2523 contents: \cw{status_bar()} (see \k{drawing-status-bar}) has to call
2524 a function in the mid-end which might rewrite the status bar text.
2525 If the drawing object is to be used only for printing, or if the
2526 game is known not to call \cw{status_bar()}, this parameter may be
2527 \cw{NULL}.
2528
2529 \S{drawing-free} \cw{drawing_free()}
2530
2531 \c void drawing_free(drawing *dr);
2532
2533 This function frees a drawing object. Note that the \cq{void *}
2534 handle is not freed; if that needs cleaning up it must be done by
2535 the front end.
2536
2537 \S{drawing-print-get-colour} \cw{print_get_colour()}
2538
2539 \c void print_get_colour(drawing *dr, int colour, int printincolour,
2540 \c                       int *hatch, float *r, float *g, float *b)
2541
2542 This function is called by the implementations of the drawing API
2543 functions when they are called in a printing context. It takes a
2544 colour index as input, and returns the description of the colour as
2545 requested by the back end.
2546
2547 \c{printincolour} is \cw{TRUE} iff the implementation is printing in
2548 colour. This will alter the results returned if the colour in
2549 question was specified with a black-and-white fallback value.
2550
2551 If the colour should be rendered by hatching, \c{*hatch} is filled
2552 with the type of hatching desired. See \k{print-grey-colour} for
2553 details of the values this integer can take.
2554
2555 If the colour should be rendered as solid colour, \c{*hatch} is
2556 given a negative value, and \c{*r}, \c{*g} and \c{*b} are filled
2557 with the RGB values of the desired colour (if printing in colour),
2558 or all filled with the grey-scale value (if printing in black and
2559 white).
2560
2561 \C{midend} The API provided by the mid-end
2562
2563 This chapter documents the API provided by the mid-end to be called
2564 by the front end. You probably only need to read this if you are a
2565 front end implementor, i.e. you are porting Puzzles to a new
2566 platform. If you're only interested in writing new puzzles, you can
2567 safely skip this chapter.
2568
2569 All the persistent state in the mid-end is encapsulated within a
2570 \c{midend} structure, to facilitate having multiple mid-ends in any
2571 port which supports multiple puzzle windows open simultaneously.
2572 Each \c{midend} is intended to handle the contents of a single
2573 puzzle window.
2574
2575 \H{midend-new} \cw{midend_new()}
2576
2577 \c midend *midend_new(frontend *fe, const game *ourgame,
2578 \c                    const drawing_api *drapi, void *drhandle)
2579
2580 Allocates and returns a new mid-end structure.
2581
2582 The \c{fe} argument is stored in the mid-end. It will be used when
2583 calling back to functions such as \cw{activate_timer()}
2584 (\k{frontend-activate-timer}), and will be passed on to the back end
2585 function \cw{colours()} (\k{backend-colours}).
2586
2587 The parameters \c{drapi} and \c{drhandle} are passed to
2588 \cw{drawing_new()} (\k{drawing-new}) to construct a drawing object
2589 which will be passed to the back end function \cw{redraw()}
2590 (\k{backend-redraw}). Hence, all drawing-related function pointers
2591 defined in \c{drapi} can expect to be called with \c{drhandle} as
2592 their first argument.
2593
2594 The \c{ourgame} argument points to a container structure describing
2595 a game back end. The mid-end thus created will only be capable of
2596 handling that one game. (So even in a monolithic front end
2597 containing all the games, this imposes the constraint that any
2598 individual puzzle window is tied to a single game. Unless, of
2599 course, you feel brave enough to change the mid-end for the window
2600 without closing the window...)
2601
2602 \H{midend-free} \cw{midend_free()}
2603
2604 \c void midend_free(midend *me);
2605
2606 Frees a mid-end structure and all its associated data.
2607
2608 \H{midend-tilesize} 
2609
2610 \c int midend_tilesize(midend *me);
2611
2612 Returns the \cq{tilesize} parameter being used to display the
2613 current puzzle.
2614
2615 \k{backend-preferred-tilesize}
2616
2617 \H{midend-set-params} \cw{midend_set_params()}
2618
2619 \c void midend_set_params(midend *me, game_params *params);
2620
2621 Sets the current game parameters for a mid-end. Subsequent games
2622 generated by \cw{midend_new_game()} (\k{midend-new-game}) will use
2623 these parameters until further notice.
2624
2625 The usual way in which the front end will have an actual
2626 \c{game_params} structure to pass to this function is if it had
2627 previously got it from \cw{midend_fetch_preset()}
2628 (\k{midend-fetch-preset}). Thus, this function is usually called in
2629 response to the user making a selection from the presets menu.
2630
2631 \H{midend-get-params} \cw{midend_get_params()}
2632
2633 \c game_params *midend_get_params(midend *me);
2634
2635 Returns the current game parameters stored in this mid-end.
2636
2637 The returned value is dynamically allocated, and should be freed
2638 when finished with by passing it to the game's own
2639 \cw{free_params()} function (see \k{backend-free-params}).
2640
2641 \H{midend-size} \cw{midend_size()}
2642
2643 \c void midend_size(midend *me, int *x, int *y, int user_size);
2644
2645 Tells the mid-end to figure out its window size.
2646
2647 On input, \c{*x} and \c{*y} should contain the maximum or requested
2648 size for the window. (Typically this will be the size of the screen
2649 that the window has to fit on, or similar.) The mid-end will
2650 repeatedly call the back end function \cw{compute_size()}
2651 (\k{backend-compute-size}), searching for a tile size that best
2652 satisfies the requirements. On exit, \c{*x} and \c{*y} will contain
2653 the size needed for the puzzle window's drawing area. (It is of
2654 course up to the front end to adjust this for any additional window
2655 furniture such as menu bars and window borders, if necessary. The
2656 status bar is also not included in this size.)
2657
2658 Use \c{user_size} to indicate whether \c{*x} and \c{*y} are a
2659 requested size, or just a maximum size.
2660
2661 If \c{user_size} is set to \cw{TRUE}, the mid-end will treat the
2662 input size as a request, and will pick a tile size which
2663 approximates it \e{as closely as possible}, going over the game's
2664 preferred tile size if necessary to achieve this. The mid-end will
2665 also use the resulting tile size as its preferred one until further
2666 notice, on the assumption that this size was explicitly requested
2667 by the user. Use this option if you want your front end to support
2668 dynamic resizing of the puzzle window with automatic scaling of the
2669 puzzle to fit.
2670
2671 If \c{user_size} is set to \cw{FALSE}, then the game's tile size
2672 will never go over its preferred one, although it may go under in
2673 order to fit within the maximum bounds specified by \c{*x} and
2674 \c{*y}. This is the recommended approach when opening a new window
2675 at default size: the game will use its preferred size unless it has
2676 to use a smaller one to fit on the screen. If the tile size is
2677 shrunk for this reason, the change will not persist; if a smaller
2678 grid is subsequently chosen, the tile size will recover.
2679
2680 The mid-end will try as hard as it can to return a size which is
2681 less than or equal to the input size, in both dimensions. In extreme
2682 circumstances it may fail (if even the lowest possible tile size
2683 gives window dimensions greater than the input), in which case it
2684 will return a size greater than the input size. Front ends should be
2685 prepared for this to happen (i.e. don't crash or fail an assertion),
2686 but may handle it in any way they see fit: by rejecting the game
2687 parameters which caused the problem, by opening a window larger than
2688 the screen regardless of inconvenience, by introducing scroll bars
2689 on the window, by drawing on a large bitmap and scaling it into a
2690 smaller window, or by any other means you can think of. It is likely
2691 that when the tile size is that small the game will be unplayable
2692 anyway, so don't put \e{too} much effort into handling it
2693 creatively.
2694
2695 If your platform has no limit on window size (or if you're planning
2696 to use scroll bars for large puzzles), you can pass dimensions of
2697 \cw{INT_MAX} as input to this function. You should probably not do
2698 that \e{and} set the \c{user_size} flag, though!
2699
2700 \H{midend-new-game} \cw{midend_new_game()}
2701
2702 \c void midend_new_game(midend *me);
2703
2704 Causes the mid-end to begin a new game. Normally the game will be a
2705 new randomly generated puzzle. However, if you have previously
2706 called \cw{midend_game_id()} or \cw{midend_set_config()}, the game
2707 generated might be dictated by the results of those functions. (In
2708 particular, you \e{must} call \cw{midend_new_game()} after calling
2709 either of those functions, or else no immediate effect will be
2710 visible.)
2711
2712 You will probably need to call \cw{midend_size()} after calling this
2713 function, because if the game parameters have been changed since the
2714 last new game then the window size might need to change. (If you
2715 know the parameters \e{haven't} changed, you don't need to do this.)
2716
2717 This function will create a new \c{game_drawstate}, but does not
2718 actually perform a redraw (since you often need to call
2719 \cw{midend_size()} before the redraw can be done). So after calling
2720 this function and after calling \cw{midend_size()}, you should then
2721 call \cw{midend_redraw()}. (It is not necessary to call
2722 \cw{midend_force_redraw()}; that will discard the draw state and
2723 create a fresh one, which is unnecessary in this case since there's
2724 a fresh one already. It would work, but it's usually excessive.)
2725
2726 \H{midend-restart-game} \cw{midend_restart_game()}
2727
2728 \c void midend_restart_game(midend *me);
2729
2730 This function causes the current game to be restarted. This is done
2731 by placing a new copy of the original game state on the end of the
2732 undo list (so that an accidental restart can be undone).
2733
2734 This function automatically causes a redraw, i.e. the front end can
2735 expect its drawing API to be called from \e{within} a call to this
2736 function.
2737
2738 \H{midend-force-redraw} \cw{midend_force_redraw()}
2739
2740 \c void midend_force_redraw(midend *me);
2741
2742 Forces a complete redraw of the puzzle window, by means of
2743 discarding the current \c{game_drawstate} and creating a new one
2744 from scratch before calling the game's \cw{redraw()} function.
2745
2746 The front end can expect its drawing API to be called from within a
2747 call to this function.
2748
2749 \H{midend-redraw} \cw{midend_redraw()}
2750
2751 \c void midend_redraw(midend *me);
2752
2753 Causes a partial redraw of the puzzle window, by means of simply
2754 calling the game's \cw{redraw()} function. (That is, the only things
2755 redrawn will be things that have changed since the last redraw.)
2756
2757 The front end can expect its drawing API to be called from within a
2758 call to this function.
2759
2760 \H{midend-process-key} \cw{midend_process_key()}
2761
2762 \c int midend_process_key(midend *me, int x, int y, int button);
2763
2764 The front end calls this function to report a mouse or keyboard
2765 event. The parameters \c{x}, \c{y} and \c{button} are almost
2766 identical to the ones passed to the back end function
2767 \cw{interpret_move()} (\k{backend-interpret-move}), except that the
2768 front end is \e{not} required to provide the guarantees about mouse
2769 event ordering. The mid-end will sort out multiple simultaneous
2770 button presses and changes of button; the front end's responsibility
2771 is simply to pass on the mouse events it receives as accurately as
2772 possible.
2773
2774 (Some platforms may need to emulate absent mouse buttons by means of
2775 using a modifier key such as Shift with another mouse button. This
2776 tends to mean that if Shift is pressed or released in the middle of
2777 a mouse drag, the mid-end will suddenly stop receiving, say,
2778 \cw{LEFT_DRAG} events and start receiving \cw{RIGHT_DRAG}s, with no
2779 intervening button release or press events. This too is something
2780 which the mid-end will sort out for you; the front end has no
2781 obligation to maintain sanity in this area.)
2782
2783 The front end \e{should}, however, always eventually send some kind
2784 of button release. On some platforms this requires special effort:
2785 Windows, for example, requires a call to the system API function
2786 \cw{SetCapture()} in order to ensure that your window receives a
2787 mouse-up event even if the pointer has left the window by the time
2788 the mouse button is released. On any platform that requires this
2789 sort of thing, the front end \e{is} responsible for doing it.
2790
2791 Calling this function is very likely to result in calls back to the
2792 front end's drawing API and/or \cw{activate_timer()}
2793 (\k{frontend-activate-timer}).
2794
2795 The return value from \cw{midend_process_key()} is non-zero, unless
2796 the effect of the keypress was to request termination of the
2797 program. A front end should shut down the puzzle in response to a
2798 zero return.
2799
2800 \H{midend-colours} \cw{midend_colours()}
2801
2802 \c float *midend_colours(midend *me, int *ncolours);
2803
2804 Returns an array of the colours required by the game, in exactly the
2805 same format as that returned by the back end function \cw{colours()}
2806 (\k{backend-colours}). Front ends should call this function rather
2807 than calling the back end's version directly, since the mid-end adds
2808 standard customisation facilities. (At the time of writing, those
2809 customisation facilities are implemented hackily by means of
2810 environment variables, but it's not impossible that they may become
2811 more full and formal in future.)
2812
2813 \H{midend-timer} \cw{midend_timer()}
2814
2815 \c void midend_timer(midend *me, float tplus);
2816
2817 If the mid-end has called \cw{activate_timer()}
2818 (\k{frontend-activate-timer}) to request regular callbacks for
2819 purposes of animation or timing, this is the function the front end
2820 should call on a regular basis. The argument \c{tplus} gives the
2821 time, in seconds, since the last time either this function was
2822 called or \cw{activate_timer()} was invoked.
2823
2824 One of the major purposes of timing in the mid-end is to perform
2825 move animation. Therefore, calling this function is very likely to
2826 result in calls back to the front end's drawing API.
2827
2828 \H{midend-num-presets} \cw{midend_num_presets()}
2829
2830 \c int midend_num_presets(midend *me);
2831
2832 Returns the number of game parameter presets supplied by this game.
2833 Front ends should use this function and \cw{midend_fetch_preset()}
2834 to configure their presets menu rather than calling the back end
2835 directly, since the mid-end adds standard customisation facilities.
2836 (At the time of writing, those customisation facilities are
2837 implemented hackily by means of environment variables, but it's not
2838 impossible that they may become more full and formal in future.)
2839
2840 \H{midend-fetch-preset} \cw{midend_fetch_preset()}
2841
2842 \c void midend_fetch_preset(midend *me, int n,
2843 \c                          char **name, game_params **params);
2844
2845 Returns one of the preset game parameter structures for the game. On
2846 input \c{n} must be a non-negative integer and less than the value
2847 returned from \cw{midend_num_presets()}. On output, \c{*name} is set
2848 to an ASCII string suitable for entering in the game's presets menu,
2849 and \c{*params} is set to the corresponding \c{game_params}
2850 structure.
2851
2852 Both of the two output values are dynamically allocated, but they
2853 are owned by the mid-end structure: the front end should not ever
2854 free them directly, because they will be freed automatically during
2855 \cw{midend_free()}.
2856
2857 \H{midend-which-preset} \cw{midend_which_preset()}
2858
2859 \c int midend_which_preset(midend *me);
2860
2861 Returns the numeric index of the preset game parameter structure
2862 which matches the current game parameters, or a negative number if
2863 no preset matches. Front ends could use this to maintain a tick
2864 beside one of the items in the menu (or tick the \q{Custom} option
2865 if the return value is less than zero).
2866
2867 \H{midend-wants-statusbar} \cw{midend_wants_statusbar()}
2868
2869 \c int midend_wants_statusbar(midend *me);
2870
2871 This function returns \cw{TRUE} if the puzzle has a use for a
2872 textual status line (to display score, completion status, currently
2873 active tiles, time, or anything else).
2874
2875 Front ends should call this function rather than talking directly to
2876 the back end.
2877
2878 \H{midend-get-config} \cw{midend_get_config()}
2879
2880 \c config_item *midend_get_config(midend *me, int which,
2881 \c                                char **wintitle);
2882
2883 Returns a dialog box description for user configuration.
2884
2885 On input, \cw{which} should be set to one of three values, which
2886 select which of the various dialog box descriptions is returned:
2887
2888 \dt \cw{CFG_SETTINGS}
2889
2890 \dd Requests the GUI parameter configuration box generated by the
2891 puzzle itself. This should be used when the user selects \q{Custom}
2892 from the game types menu (or equivalent). The mid-end passes this
2893 request on to the back end function \cw{configure()}
2894 (\k{backend-configure}).
2895
2896 \dt \cw{CFG_DESC}
2897
2898 \dd Requests a box suitable for entering a descriptive game ID (and
2899 viewing the existing one). The mid-end generates this dialog box
2900 description itself. This should be used when the user selects
2901 \q{Specific} from the game menu (or equivalent).
2902
2903 \dt \cw{CFG_SEED}
2904
2905 \dd Requests a box suitable for entering a random-seed game ID (and
2906 viewing the existing one). The mid-end generates this dialog box
2907 description itself. This should be used when the user selects
2908 \q{Random Seed} from the game menu (or equivalent).
2909
2910 The returned value is an array of \cw{config_item}s, exactly as
2911 described in \k{backend-configure}. Another returned value is an
2912 ASCII string giving a suitable title for the configuration window,
2913 in \c{*wintitle}.
2914
2915 Both returned values are dynamically allocated and will need to be
2916 freed. The window title can be freed in the obvious way; the
2917 \cw{config_item} array is a slightly complex structure, so a utility
2918 function \cw{free_cfg()} is provided to free it for you. See
2919 \k{utils-free-cfg}.
2920
2921 (Of course, you will probably not want to free the \cw{config_item}
2922 array until the dialog box is dismissed, because before then you
2923 will probably need to pass it to \cw{midend_set_config}.)
2924
2925 \H{midend-set-config} \cw{midend_set_config()}
2926
2927 \c char *midend_set_config(midend *me, int which,
2928 \c                         config_item *cfg);
2929
2930 Passes the mid-end the results of a configuration dialog box.
2931 \c{which} should have the same value which it had when
2932 \cw{midend_get_config()} was called; \c{cfg} should be the array of
2933 \c{config_item}s returned from \cw{midend_get_config()}, modified to
2934 contain the results of the user's editing operations.
2935
2936 This function returns \cw{NULL} on success, or otherwise (if the
2937 configuration data was in some way invalid) an ASCII string
2938 containing an error message suitable for showing to the user.
2939
2940 If the function succeeds, it is likely that the game parameters will
2941 have been changed and it is certain that a new game will be
2942 requested. The front end should therefore call
2943 \cw{midend_new_game()}, and probably also re-think the window size
2944 using \cw{midend_size()} and eventually perform a refresh using
2945 \cw{midend_redraw()}.
2946
2947 \H{midend-game-id} \cw{midend_game_id()}
2948
2949 \c char *midend_game_id(midend *me, char *id);
2950
2951 Passes the mid-end a string game ID (of any of the valid forms
2952 \cq{params}, \cq{params:description} or \cq{params#seed}) which the
2953 mid-end will process and use for the next generated game.
2954
2955 This function returns \cw{NULL} on success, or otherwise (if the
2956 configuration data was in some way invalid) an ASCII string
2957 containing an error message (not dynamically allocated) suitable for
2958 showing to the user. In the event of an error, the mid-end's
2959 internal state will be left exactly as it was before the call.
2960
2961 If the function succeeds, it is likely that the game parameters will
2962 have been changed and it is certain that a new game will be
2963 requested. The front end should therefore call
2964 \cw{midend_new_game()}, and probably also re-think the window size
2965 using \cw{midend_size()} and eventually case a refresh using
2966 \cw{midend_redraw()}.
2967
2968 \H{midend-get-game-id} \cw{midend_get_game_id()}
2969
2970 \c char *midend_get_game_id(midend *me)
2971
2972 Returns a descriptive game ID (i.e. one in the form
2973 \cq{params:description}) describing the game currently active in the
2974 mid-end. The returned string is dynamically allocated.
2975
2976 \H{midend-can-format-as-text-now} \cw{midend_can_format_as_text_now()}
2977
2978 \c int midend_can_format_as_text_now(midend *me);
2979
2980 Returns \cw{TRUE} if the game code is capable of formatting puzzles
2981 of the currently selected game type as ASCII.
2982
2983 If this returns \cw{FALSE}, then \cw{midend_text_format()}
2984 (\k{midend-text-format}) will return \cw{NULL}.
2985
2986 \H{midend-text-format} \cw{midend_text_format()}
2987
2988 \c char *midend_text_format(midend *me);
2989
2990 Formats the current game's current state as ASCII text suitable for
2991 copying to the clipboard. The returned string is dynamically
2992 allocated.
2993
2994 If the game's \c{can_format_as_text_ever} flag is \cw{FALSE}, or if
2995 its \cw{can_format_as_text_now()} function returns \cw{FALSE}, then
2996 this function will return \cw{NULL}.
2997
2998 If the returned string contains multiple lines (which is likely), it
2999 will use the normal C line ending convention (\cw{\\n} only). On
3000 platforms which use a different line ending convention for data in
3001 the clipboard, it is the front end's responsibility to perform the
3002 conversion.
3003
3004 \H{midend-solve} \cw{midend_solve()}
3005
3006 \c char *midend_solve(midend *me);
3007
3008 Requests the mid-end to perform a Solve operation.
3009
3010 On success, \cw{NULL} is returned. On failure, an error message (not
3011 dynamically allocated) is returned, suitable for showing to the
3012 user.
3013
3014 The front end can expect its drawing API and/or
3015 \cw{activate_timer()} to be called from within a call to this
3016 function.
3017
3018 \H{midend-serialise} \cw{midend_serialise()}
3019
3020 \c void midend_serialise(midend *me,
3021 \c                       void (*write)(void *ctx, void *buf, int len),
3022 \c                       void *wctx);
3023
3024 Calling this function causes the mid-end to convert its entire
3025 internal state into a long ASCII text string, and to pass that
3026 string (piece by piece) to the supplied \c{write} function.
3027
3028 Desktop implementations can use this function to save a game in any
3029 state (including half-finished) to a disk file, by supplying a
3030 \c{write} function which is a wrapper on \cw{fwrite()} (or local
3031 equivalent). Other implementations may find other uses for it, such
3032 as compressing the large and sprawling mid-end state into a
3033 manageable amount of memory when a palmtop application is suspended
3034 so that another one can run; in this case \cw{write} might want to
3035 write to a memory buffer rather than a file. There may be other uses
3036 for it as well.
3037
3038 This function will call back to the supplied \c{write} function a
3039 number of times, with the first parameter (\c{ctx}) equal to
3040 \c{wctx}, and the other two parameters pointing at a piece of the
3041 output string.
3042
3043 \H{midend-deserialise} \cw{midend_deserialise()}
3044
3045 \c char *midend_deserialise(midend *me,
3046 \c                          int (*read)(void *ctx, void *buf, int len),
3047 \c                          void *rctx);
3048
3049 This function is the counterpart to \cw{midend_serialise()}. It
3050 calls the supplied \cw{read} function repeatedly to read a quantity
3051 of data, and attempts to interpret that data as a serialised mid-end
3052 as output by \cw{midend_serialise()}.
3053
3054 The \cw{read} function is called with the first parameter (\c{ctx})
3055 equal to \c{rctx}, and should attempt to read \c{len} bytes of data
3056 into the buffer pointed to by \c{buf}. It should return \cw{FALSE}
3057 on failure or \cw{TRUE} on success. It should not report success
3058 unless it has filled the entire buffer; on platforms which might be
3059 reading from a pipe or other blocking data source, \c{read} is
3060 responsible for looping until the whole buffer has been filled.
3061
3062 If the de-serialisation operation is successful, the mid-end's
3063 internal data structures will be replaced by the results of the
3064 load, and \cw{NULL} will be returned. Otherwise, the mid-end's state
3065 will be completely unchanged and an error message (typically some
3066 variation on \q{save file is corrupt}) will be returned. As usual,
3067 the error message string is not dynamically allocated.
3068
3069 If this function succeeds, it is likely that the game parameters
3070 will have been changed. The front end should therefore probably
3071 re-think the window size using \cw{midend_size()}, and probably
3072 cause a refresh using \cw{midend_redraw()}.
3073
3074 Because each mid-end is tied to a specific game back end, this
3075 function will fail if you attempt to read in a save file generated
3076 by a different game from the one configured in this mid-end, even if
3077 your application is a monolithic one containing all the puzzles. (It
3078 would be pretty easy to write a function which would look at a save
3079 file and determine which game it was for; any front end implementor
3080 who needs such a function can probably be accommodated.)
3081
3082 \H{frontend-backend} Direct reference to the back end structure by
3083 the front end
3084
3085 Although \e{most} things the front end needs done should be done by
3086 calling the mid-end, there are a few situations in which the front
3087 end needs to refer directly to the game back end structure.
3088
3089 The most obvious of these is
3090
3091 \b passing the game back end as a parameter to \cw{midend_new()}.
3092
3093 There are a few other back end features which are not wrapped by the
3094 mid-end because there didn't seem much point in doing so:
3095
3096 \b fetching the \c{name} field to use in window titles and similar
3097
3098 \b reading the \c{can_configure}, \c{can_solve} and
3099 \c{can_format_as_text_ever} fields to decide whether to add those
3100 items to the menu bar or equivalent
3101
3102 \b reading the \c{winhelp_topic} field (Windows only)
3103
3104 \b the GTK front end provides a \cq{--generate} command-line option
3105 which directly calls the back end to do most of its work. This is
3106 not really part of the main front end code, though, and I'm not sure
3107 it counts.
3108
3109 In order to find the game back end structure, the front end does one
3110 of two things:
3111
3112 \b If the particular front end is compiling a separate binary per
3113 game, then the back end structure is a global variable with the
3114 standard name \cq{thegame}:
3115
3116 \lcont{
3117
3118 \c extern const game thegame;
3119
3120 }
3121
3122 \b If the front end is compiled as a monolithic application
3123 containing all the puzzles together (in which case the preprocessor
3124 symbol \cw{COMBINED} must be defined when compiling most of the code
3125 base), then there will be two global variables defined:
3126
3127 \lcont{
3128
3129 \c extern const game *gamelist[];
3130 \c extern const int gamecount;
3131
3132 \c{gamelist} will be an array of \c{gamecount} game structures,
3133 declared in the automatically constructed source module \c{list.c}.
3134 The application should search that array for the game it wants,
3135 probably by reaching into each game structure and looking at its
3136 \c{name} field.
3137
3138 }
3139
3140 \H{frontend-api} Mid-end to front-end calls
3141
3142 This section describes the small number of functions which a front
3143 end must provide to be called by the mid-end or other standard
3144 utility modules.
3145
3146 \H{frontend-get-random-seed} \cw{get_random_seed()}
3147
3148 \c void get_random_seed(void **randseed, int *randseedsize);
3149
3150 This function is called by a new mid-end, and also occasionally by
3151 game back ends. Its job is to return a piece of data suitable for
3152 using as a seed for initialisation of a new \c{random_state}.
3153
3154 On exit, \c{*randseed} should be set to point at a newly allocated
3155 piece of memory containing some seed data, and \c{*randseedsize}
3156 should be set to the length of that data.
3157
3158 A simple and entirely adequate implementation is to return a piece
3159 of data containing the current system time at the highest
3160 conveniently available resolution.
3161
3162 \H{frontend-activate-timer} \cw{activate_timer()}
3163
3164 \c void activate_timer(frontend *fe);
3165
3166 This is called by the mid-end to request that the front end begin
3167 calling it back at regular intervals.
3168
3169 The timeout interval is left up to the front end; the finer it is,
3170 the smoother move animations will be, but the more CPU time will be
3171 used. Current front ends use values around 20ms (i.e. 50Hz).
3172
3173 After this function is called, the mid-end will expect to receive
3174 calls to \cw{midend_timer()} on a regular basis.
3175
3176 \H{frontend-deactivate-timer} \cw{deactivate_timer()}
3177
3178 \c void deactivate_timer(frontend *fe);
3179
3180 This is called by the mid-end to request that the front end stop
3181 calling \cw{midend_timer()}.
3182
3183 \H{frontend-fatal} \cw{fatal()}
3184
3185 \c void fatal(char *fmt, ...);
3186
3187 This is called by some utility functions if they encounter a
3188 genuinely fatal error such as running out of memory. It is a
3189 variadic function in the style of \cw{printf()}, and is expected to
3190 show the formatted error message to the user any way it can and then
3191 terminate the application. It must not return.
3192
3193 \H{frontend-default-colour} \cw{frontend_default_colour()}
3194
3195 \c void frontend_default_colour(frontend *fe, float *output);
3196
3197 This function expects to be passed a pointer to an array of three
3198 \cw{float}s. It returns the platform's local preferred background
3199 colour in those three floats, as red, green and blue values (in that
3200 order) ranging from \cw{0.0} to \cw{1.0}.
3201
3202 This function should only ever be called by the back end function
3203 \cw{colours()} (\k{backend-colours}). (Thus, it isn't a
3204 \e{midend}-to-frontend function as such, but there didn't seem to be
3205 anywhere else particularly good to put it. Sorry.)
3206
3207 \C{utils} Utility APIs
3208
3209 This chapter documents a variety of utility APIs provided for the
3210 general use of the rest of the Puzzles code.
3211
3212 \H{utils-random} Random number generation
3213
3214 Platforms' local random number generators vary widely in quality and
3215 seed size. Puzzles therefore supplies its own high-quality random
3216 number generator, with the additional advantage of giving the same
3217 results if fed the same seed data on different platforms. This
3218 allows game random seeds to be exchanged between different ports of
3219 Puzzles and still generate the same games.
3220
3221 Unlike the ANSI C \cw{rand()} function, the Puzzles random number
3222 generator has an \e{explicit} state object called a
3223 \c{random_state}. One of these is managed by each mid-end, for
3224 example, and passed to the back end to generate a game with.
3225
3226 \S{utils-random-init} \cw{random_new()}
3227
3228 \c random_state *random_new(char *seed, int len);
3229
3230 Allocates, initialises and returns a new \c{random_state}. The input
3231 data is used as the seed for the random number stream (i.e. using
3232 the same seed at a later time will generate the same stream).
3233
3234 The seed data can be any data at all; there is no requirement to use
3235 printable ASCII, or NUL-terminated strings, or anything like that.
3236
3237 \S{utils-random-copy} \cw{random_copy()}
3238
3239 \c random_state *random_copy(random_state *tocopy);
3240
3241 Allocates a new \c{random_state}, copies the contents of another
3242 \c{random_state} into it, and returns the new state.  If exactly the
3243 same sequence of functions is subseqently called on both the copy and
3244 the original, the results will be identical.  This may be useful for
3245 speculatively performing some operation using a given random state,
3246 and later replaying that operation precisely.
3247
3248 \S{utils-random-free} \cw{random_free()}
3249
3250 \c void random_free(random_state *state);
3251
3252 Frees a \c{random_state}.
3253
3254 \S{utils-random-bits} \cw{random_bits()}
3255
3256 \c unsigned long random_bits(random_state *state, int bits);
3257
3258 Returns a random number from 0 to \cw{2^bits-1} inclusive. \c{bits}
3259 should be between 1 and 32 inclusive.
3260
3261 \S{utils-random-upto} \cw{random_upto()}
3262
3263 \c unsigned long random_upto(random_state *state, unsigned long limit);
3264
3265 Returns a random number from 0 to \cw{limit-1} inclusive.
3266
3267 \S{utils-random-state-encode} \cw{random_state_encode()}
3268
3269 \c char *random_state_encode(random_state *state);
3270
3271 Encodes the entire contents of a \c{random_state} in printable
3272 ASCII. Returns a dynamically allocated string containing that
3273 encoding. This can subsequently be passed to
3274 \cw{random_state_decode()} to reconstruct the same \c{random_state}.
3275
3276 \S{utils-random-state-decode} \cw{random_state_decode()}
3277
3278 \c random_state *random_state_decode(char *input);
3279
3280 Decodes a string generated by \cw{random_state_encode()} and
3281 reconstructs an equivalent \c{random_state} to the one encoded, i.e.
3282 it should produce the same stream of random numbers.
3283
3284 This function has no error reporting; if you pass it an invalid
3285 string it will simply generate an arbitrary random state, which may
3286 turn out to be noticeably non-random.
3287
3288 \S{utils-shuffle} \cw{shuffle()}
3289
3290 \c void shuffle(void *array, int nelts, int eltsize, random_state *rs);
3291
3292 Shuffles an array into a random order. The interface is much like
3293 ANSI C \cw{qsort()}, except that there's no need for a compare
3294 function.
3295
3296 \c{array} is a pointer to the first element of the array. \c{nelts}
3297 is the number of elements in the array; \c{eltsize} is the size of a
3298 single element (typically measured using \c{sizeof}). \c{rs} is a
3299 \c{random_state} used to generate all the random numbers for the
3300 shuffling process.
3301
3302 \H{utils-alloc} Memory allocation
3303
3304 Puzzles has some central wrappers on the standard memory allocation
3305 functions, which provide compile-time type checking, and run-time
3306 error checking by means of quitting the application if it runs out
3307 of memory. This doesn't provide the best possible recovery from
3308 memory shortage, but on the other hand it greatly simplifies the
3309 rest of the code, because nothing else anywhere needs to worry about
3310 \cw{NULL} returns from allocation.
3311
3312 \S{utils-snew} \cw{snew()}
3313
3314 \c var = snew(type);
3315 \e iii        iiii
3316
3317 This macro takes a single argument which is a \e{type name}. It
3318 allocates space for one object of that type. If allocation fails it
3319 will call \cw{fatal()} and not return; so if it does return, you can
3320 be confident that its return value is non-\cw{NULL}.
3321
3322 The return value is cast to the specified type, so that the compiler
3323 will type-check it against the variable you assign it into. Thus,
3324 this ensures you don't accidentally allocate memory the size of the
3325 wrong type and assign it into a variable of the right one (or vice
3326 versa!).
3327
3328 \S{utils-snewn} \cw{snewn()}
3329
3330 \c var = snewn(n, type);
3331 \e iii         i  iiii
3332
3333 This macro is the array form of \cw{snew()}. It takes two arguments;
3334 the first is a number, and the second is a type name. It allocates
3335 space for that many objects of that type, and returns a type-checked
3336 non-\cw{NULL} pointer just as \cw{snew()} does.
3337
3338 \S{utils-sresize} \cw{sresize()}
3339
3340 \c var = sresize(var, n, type);
3341 \e iii           iii  i  iiii
3342
3343 This macro is a type-checked form of \cw{realloc()}. It takes three
3344 arguments: an input memory block, a new size in elements, and a
3345 type. It re-sizes the input memory block to a size sufficient to
3346 contain that many elements of that type. It returns a type-checked
3347 non-\cw{NULL} pointer, like \cw{snew()} and \cw{snewn()}.
3348
3349 The input memory block can be \cw{NULL}, in which case this function
3350 will behave exactly like \cw{snewn()}. (In principle any
3351 ANSI-compliant \cw{realloc()} implementation ought to cope with
3352 this, but I've never quite trusted it to work everywhere.)
3353
3354 \S{utils-sfree} \cw{sfree()}
3355
3356 \c void sfree(void *p);
3357
3358 This function is pretty much equivalent to \cw{free()}. It is
3359 provided with a dynamically allocated block, and frees it.
3360
3361 The input memory block can be \cw{NULL}, in which case this function
3362 will do nothing. (In principle any ANSI-compliant \cw{free()}
3363 implementation ought to cope with this, but I've never quite trusted
3364 it to work everywhere.)
3365
3366 \S{utils-dupstr} \cw{dupstr()}
3367
3368 \c char *dupstr(const char *s);
3369
3370 This function dynamically allocates a duplicate of a C string. Like
3371 the \cw{snew()} functions, it guarantees to return non-\cw{NULL} or
3372 not return at all.
3373
3374 (Many platforms provide the function \cw{strdup()}. As well as
3375 guaranteeing never to return \cw{NULL}, my version has the advantage
3376 of being defined \e{everywhere}, rather than inconveniently not
3377 quite everywhere.)
3378
3379 \S{utils-free-cfg} \cw{free_cfg()}
3380
3381 \c void free_cfg(config_item *cfg);
3382
3383 This function correctly frees an array of \c{config_item}s,
3384 including walking the array until it gets to the end and freeing
3385 precisely those \c{sval} fields which are expected to be dynamically
3386 allocated.
3387
3388 (See \k{backend-configure} for details of the \c{config_item}
3389 structure.)
3390
3391 \H{utils-tree234} Sorted and counted tree functions
3392
3393 Many games require complex algorithms for generating random puzzles,
3394 and some require moderately complex algorithms even during play. A
3395 common requirement during these algorithms is for a means of
3396 maintaining sorted or unsorted lists of items, such that items can
3397 be removed and added conveniently.
3398
3399 For general use, Puzzles provides the following set of functions
3400 which maintain 2-3-4 trees in memory. (A 2-3-4 tree is a balanced
3401 tree structure, with the property that all lookups, insertions,
3402 deletions, splits and joins can be done in \cw{O(log N)} time.)
3403
3404 All these functions expect you to be storing a tree of \c{void *}
3405 pointers. You can put anything you like in those pointers.
3406
3407 By the use of per-node element counts, these tree structures have
3408 the slightly unusual ability to look elements up by their numeric
3409 index within the list represented by the tree. This means that they
3410 can be used to store an unsorted list (in which case, every time you
3411 insert a new element, you must explicitly specify the position where
3412 you wish to insert it). They can also do numeric lookups in a sorted
3413 tree, which might be useful for (for example) tracking the median of
3414 a changing data set.
3415
3416 As well as storing sorted lists, these functions can be used for
3417 storing \q{maps} (associative arrays), by defining each element of a
3418 tree to be a (key, value) pair.
3419
3420 \S{utils-newtree234} \cw{newtree234()}
3421
3422 \c tree234 *newtree234(cmpfn234 cmp);
3423
3424 Creates a new empty tree, and returns a pointer to it.
3425
3426 The parameter \c{cmp} determines the sorting criterion on the tree.
3427 Its prototype is
3428
3429 \c typedef int (*cmpfn234)(void *, void *);
3430
3431 If you want a sorted tree, you should provide a function matching
3432 this prototype, which returns like \cw{strcmp()} does (negative if
3433 the first argument is smaller than the second, positive if it is
3434 bigger, zero if they compare equal). In this case, the function
3435 \cw{addpos234()} will not be usable on your tree (because all
3436 insertions must respect the sorting order).
3437
3438 If you want an unsorted tree, pass \cw{NULL}. In this case you will
3439 not be able to use either \cw{add234()} or \cw{del234()}, or any
3440 other function such as \cw{find234()} which depends on a sorting
3441 order. Your tree will become something more like an array, except
3442 that it will efficiently support insertion and deletion as well as
3443 lookups by numeric index.
3444
3445 \S{utils-freetree234} \cw{freetree234()}
3446
3447 \c void freetree234(tree234 *t);
3448
3449 Frees a tree. This function will not free the \e{elements} of the
3450 tree (because they might not be dynamically allocated, or you might
3451 be storing the same set of elements in more than one tree); it will
3452 just free the tree structure itself. If you want to free all the
3453 elements of a tree, you should empty it before passing it to
3454 \cw{freetree234()}, by means of code along the lines of
3455
3456 \c while ((element = delpos234(tree, 0)) != NULL)
3457 \c     sfree(element); /* or some more complicated free function */
3458 \e                     iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
3459
3460 \S{utils-add234} \cw{add234()}
3461
3462 \c void *add234(tree234 *t, void *e);
3463
3464 Inserts a new element \c{e} into the tree \c{t}. This function
3465 expects the tree to be sorted; the new element is inserted according
3466 to the sort order.
3467
3468 If an element comparing equal to \c{e} is already in the tree, then
3469 the insertion will fail, and the return value will be the existing
3470 element. Otherwise, the insertion succeeds, and \c{e} is returned.
3471
3472 \S{utils-addpos234} \cw{addpos234()}
3473
3474 \c void *addpos234(tree234 *t, void *e, int index);
3475
3476 Inserts a new element into an unsorted tree. Since there is no
3477 sorting order to dictate where the new element goes, you must
3478 specify where you want it to go. Setting \c{index} to zero puts the
3479 new element right at the start of the list; setting \c{index} to the
3480 current number of elements in the tree puts the new element at the
3481 end.
3482
3483 Return value is \c{e}, in line with \cw{add234()} (although this
3484 function cannot fail except by running out of memory, in which case
3485 it will bomb out and die rather than returning an error indication).
3486
3487 \S{utils-index234} \cw{index234()}
3488
3489 \c void *index234(tree234 *t, int index);
3490
3491 Returns a pointer to the \c{index}th element of the tree, or
3492 \cw{NULL} if \c{index} is out of range. Elements of the tree are
3493 numbered from zero.
3494
3495 \S{utils-find234} \cw{find234()}
3496
3497 \c void *find234(tree234 *t, void *e, cmpfn234 cmp);
3498
3499 Searches for an element comparing equal to \c{e} in a sorted tree.
3500
3501 If \c{cmp} is \cw{NULL}, the tree's ordinary comparison function
3502 will be used to perform the search. However, sometimes you don't
3503 want that; suppose, for example, each of your elements is a big
3504 structure containing a \c{char *} name field, and you want to find
3505 the element with a given name. You \e{could} achieve this by
3506 constructing a fake element structure, setting its name field
3507 appropriately, and passing it to \cw{find234()}, but you might find
3508 it more convenient to pass \e{just} a name string to \cw{find234()},
3509 supplying an alternative comparison function which expects one of
3510 its arguments to be a bare name and the other to be a large
3511 structure containing a name field.
3512
3513 Therefore, if \c{cmp} is not \cw{NULL}, then it will be used to
3514 compare \c{e} to elements of the tree. The first argument passed to
3515 \c{cmp} will always be \c{e}; the second will be an element of the
3516 tree.
3517
3518 (See \k{utils-newtree234} for the definition of the \c{cmpfn234}
3519 function pointer type.)
3520
3521 The returned value is the element found, or \cw{NULL} if the search
3522 is unsuccessful.
3523
3524 \S{utils-findrel234} \cw{findrel234()}
3525
3526 \c void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);
3527
3528 This function is like \cw{find234()}, but has the additional ability
3529 to do a \e{relative} search. The additional parameter \c{relation}
3530 can be one of the following values:
3531
3532 \dt \cw{REL234_EQ}
3533
3534 \dd Find only an element that compares equal to \c{e}. This is
3535 exactly the behaviour of \cw{find234()}.
3536
3537 \dt \cw{REL234_LT}
3538
3539 \dd Find the greatest element that compares strictly less than
3540 \c{e}. \c{e} may be \cw{NULL}, in which case it finds the greatest
3541 element in the whole tree (which could also be done by
3542 \cw{index234(t, count234(t)-1)}).
3543
3544 \dt \cw{REL234_LE}
3545
3546 \dd Find the greatest element that compares less than or equal to
3547 \c{e}. (That is, find an element that compares equal to \c{e} if
3548 possible, but failing that settle for something just less than it.)
3549
3550 \dt \cw{REL234_GT}
3551
3552 \dd Find the smallest element that compares strictly greater than
3553 \c{e}. \c{e} may be \cw{NULL}, in which case it finds the smallest
3554 element in the whole tree (which could also be done by
3555 \cw{index234(t, 0)}).
3556
3557 \dt \cw{REL234_GE}
3558
3559 \dd Find the smallest element that compares greater than or equal to
3560 \c{e}. (That is, find an element that compares equal to \c{e} if
3561 possible, but failing that settle for something just bigger than
3562 it.)
3563
3564 Return value, as before, is the element found or \cw{NULL} if no
3565 element satisfied the search criterion.
3566
3567 \S{utils-findpos234} \cw{findpos234()}
3568
3569 \c void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);
3570
3571 This function is like \cw{find234()}, but has the additional feature
3572 of returning the index of the element found in the tree; that index
3573 is written to \c{*index} in the event of a successful search (a
3574 non-\cw{NULL} return value).
3575
3576 \c{index} may be \cw{NULL}, in which case this function behaves
3577 exactly like \cw{find234()}.
3578
3579 \S{utils-findrelpos234} \cw{findrelpos234()}
3580
3581 \c void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
3582 \c                     int *index);
3583
3584 This function combines all the features of \cw{findrel234()} and
3585 \cw{findpos234()}.
3586
3587 \S{utils-del234} \cw{del234()}
3588
3589 \c void *del234(tree234 *t, void *e);
3590
3591 Finds an element comparing equal to \c{e} in the tree, deletes it,
3592 and returns it.
3593
3594 The input tree must be sorted.
3595
3596 The element found might be \c{e} itself, or might merely compare
3597 equal to it.
3598
3599 Return value is \cw{NULL} if no such element is found.
3600
3601 \S{utils-delpos234} \cw{delpos234()}
3602
3603 \c void *delpos234(tree234 *t, int index);
3604
3605 Deletes the element at position \c{index} in the tree, and returns
3606 it.
3607
3608 Return value is \cw{NULL} if the index is out of range.
3609
3610 \S{utils-count234} \cw{count234()}
3611
3612 \c int count234(tree234 *t);
3613
3614 Returns the number of elements currently in the tree.
3615
3616 \S{utils-splitpos234} \cw{splitpos234()}
3617
3618 \c tree234 *splitpos234(tree234 *t, int index, int before);
3619
3620 Splits the input tree into two pieces at a given position, and
3621 creates a new tree containing all the elements on one side of that
3622 position.
3623
3624 If \c{before} is \cw{TRUE}, then all the items at or after position
3625 \c{index} are left in the input tree, and the items before that
3626 point are returned in the new tree. Otherwise, the reverse happens:
3627 all the items at or after \c{index} are moved into the new tree, and
3628 those before that point are left in the old one.
3629
3630 If \c{index} is equal to 0 or to the number of elements in the input
3631 tree, then one of the two trees will end up empty (and this is not
3632 an error condition). If \c{index} is further out of range in either
3633 direction, the operation will fail completely and return \cw{NULL}.
3634
3635 This operation completes in \cw{O(log N)} time, no matter how large
3636 the tree or how balanced or unbalanced the split.
3637
3638 \S{utils-split234} \cw{split234()}
3639
3640 \c tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);
3641
3642 Splits a sorted tree according to its sort order.
3643
3644 \c{rel} can be any of the relation constants described in
3645 \k{utils-findrel234}, \e{except} for \cw{REL234_EQ}. All the
3646 elements having that relation to \c{e} will be transferred into the
3647 new tree; the rest will be left in the old one.
3648
3649 The parameter \c{cmp} has the same semantics as it does in
3650 \cw{find234()}: if it is not \cw{NULL}, it will be used in place of
3651 the tree's own comparison function when comparing elements to \c{e},
3652 in such a way that \c{e} itself is always the first of its two
3653 operands.
3654
3655 Again, this operation completes in \cw{O(log N)} time, no matter how
3656 large the tree or how balanced or unbalanced the split.
3657
3658 \S{utils-join234} \cw{join234()}
3659
3660 \c tree234 *join234(tree234 *t1, tree234 *t2);
3661
3662 Joins two trees together by concatenating the lists they represent.
3663 All the elements of \c{t2} are moved into \c{t1}, in such a way that
3664 they appear \e{after} the elements of \c{t1}. The tree \c{t2} is
3665 freed; the return value is \c{t1}.
3666
3667 If you apply this function to a sorted tree and it violates the sort
3668 order (i.e. the smallest element in \c{t2} is smaller than or equal
3669 to the largest element in \c{t1}), the operation will fail and
3670 return \cw{NULL}.
3671
3672 This operation completes in \cw{O(log N)} time, no matter how large
3673 the trees being joined together.
3674
3675 \S{utils-join234r} \cw{join234r()}
3676
3677 \c tree234 *join234r(tree234 *t1, tree234 *t2);
3678
3679 Joins two trees together in exactly the same way as \cw{join234()},
3680 but this time the combined tree is returned in \c{t2}, and \c{t1} is
3681 destroyed. The elements in \c{t1} still appear before those in
3682 \c{t2}.
3683
3684 Again, this operation completes in \cw{O(log N)} time, no matter how
3685 large the trees being joined together.
3686
3687 \S{utils-copytree234} \cw{copytree234()}
3688
3689 \c tree234 *copytree234(tree234 *t, copyfn234 copyfn,
3690 \c                      void *copyfnstate);
3691
3692 Makes a copy of an entire tree.
3693
3694 If \c{copyfn} is \cw{NULL}, the tree will be copied but the elements
3695 will not be; i.e. the new tree will contain pointers to exactly the
3696 same physical elements as the old one.
3697
3698 If you want to copy each actual element during the operation, you
3699 can instead pass a function in \c{copyfn} which makes a copy of each
3700 element. That function has the prototype
3701
3702 \c typedef void *(*copyfn234)(void *state, void *element);
3703
3704 and every time it is called, the \c{state} parameter will be set to
3705 the value you passed in as \c{copyfnstate}.
3706
3707 \H{utils-misc} Miscellaneous utility functions and macros
3708
3709 This section contains all the utility functions which didn't
3710 sensibly fit anywhere else.
3711
3712 \S{utils-truefalse} \cw{TRUE} and \cw{FALSE}
3713
3714 The main Puzzles header file defines the macros \cw{TRUE} and
3715 \cw{FALSE}, which are used throughout the code in place of 1 and 0
3716 (respectively) to indicate that the values are in a boolean context.
3717 For code base consistency, I'd prefer it if submissions of new code
3718 followed this convention as well.
3719
3720 \S{utils-maxmin} \cw{max()} and \cw{min()}
3721
3722 The main Puzzles header file defines the pretty standard macros
3723 \cw{max()} and \cw{min()}, each of which is given two arguments and
3724 returns the one which compares greater or less respectively.
3725
3726 These macros may evaluate their arguments multiple times. Avoid side
3727 effects.
3728
3729 \S{utils-pi} \cw{PI}
3730
3731 The main Puzzles header file defines a macro \cw{PI} which expands
3732 to a floating-point constant representing pi.
3733
3734 (I've never understood why ANSI's \cw{<math.h>} doesn't define this.
3735 It'd be so useful!)
3736
3737 \S{utils-obfuscate-bitmap} \cw{obfuscate_bitmap()}
3738
3739 \c void obfuscate_bitmap(unsigned char *bmp, int bits, int decode);
3740
3741 This function obscures the contents of a piece of data, by
3742 cryptographic methods. It is useful for games of hidden information
3743 (such as Mines, Guess or Black Box), in which the game ID
3744 theoretically reveals all the information the player is supposed to
3745 be trying to guess. So in order that players should be able to send
3746 game IDs to one another without accidentally spoiling the resulting
3747 game by looking at them, these games obfuscate their game IDs using
3748 this function.
3749
3750 Although the obfuscation function is cryptographic, it cannot
3751 properly be called encryption because it has no key. Therefore,
3752 anybody motivated enough can re-implement it, or hack it out of the
3753 Puzzles source, and strip the obfuscation off one of these game IDs
3754 to see what lies beneath. (Indeed, they could usually do it much
3755 more easily than that, by entering the game ID into their own copy
3756 of the puzzle and hitting Solve.) The aim is not to protect against
3757 a determined attacker; the aim is simply to protect people who
3758 wanted to play the game honestly from \e{accidentally} spoiling
3759 their own fun.
3760
3761 The input argument \c{bmp} points at a piece of memory to be
3762 obfuscated. \c{bits} gives the length of the data. Note that that
3763 length is in \e{bits} rather than bytes: if you ask for obfuscation
3764 of a partial number of bytes, then you will get it. Bytes are
3765 considered to be used from the top down: thus, for example, setting
3766 \c{bits} to 10 will cover the whole of \cw{bmp[0]} and the \e{top
3767 two} bits of \cw{bmp[1]}. The remainder of a partially used byte is
3768 undefined (i.e. it may be corrupted by the function).
3769
3770 The parameter \c{decode} is \cw{FALSE} for an encoding operation,
3771 and \cw{TRUE} for a decoding operation. Each is the inverse of the
3772 other. (There's no particular reason you shouldn't obfuscate by
3773 decoding and restore cleartext by encoding, if you really wanted to;
3774 it should still work.)
3775
3776 The input bitmap is processed in place.
3777
3778 \S{utils-bin2hex} \cw{bin2hex()}
3779
3780 \c char *bin2hex(const unsigned char *in, int inlen);
3781
3782 This function takes an input byte array and converts it into an
3783 ASCII string encoding those bytes in (lower-case) hex. It returns a
3784 dynamically allocated string containing that encoding.
3785
3786 This function is useful for encoding the result of
3787 \cw{obfuscate_bitmap()} in printable ASCII for use in game IDs.
3788
3789 \S{utils-hex2bin} \cw{hex2bin()}
3790
3791 \c unsigned char *hex2bin(const char *in, int outlen);
3792
3793 This function takes an ASCII string containing hex digits, and
3794 converts it back into a byte array of length \c{outlen}. If there
3795 aren't enough hex digits in the string, the contents of the
3796 resulting array will be undefined.
3797
3798 This function is the inverse of \cw{bin2hex()}.
3799
3800 \S{utils-game-mkhighlight} \cw{game_mkhighlight()}
3801
3802 \c void game_mkhighlight(frontend *fe, float *ret,
3803 \c                       int background, int highlight, int lowlight);
3804
3805 It's reasonably common for a puzzle game's graphics to use
3806 highlights and lowlights to indicate \q{raised} or \q{lowered}
3807 sections. Fifteen, Sixteen and Twiddle are good examples of this.
3808
3809 Puzzles using this graphical style are running a risk if they just
3810 use whatever background colour is supplied to them by the front end,
3811 because that background colour might be too light to see any
3812 highlights on at all. (In particular, it's not unheard of for the
3813 front end to specify a default background colour of white.)
3814
3815 Therefore, such puzzles can call this utility function from their
3816 \cw{colours()} routine (\k{backend-colours}). You pass it your front
3817 end handle, a pointer to the start of your return array, and three
3818 colour indices. It will:
3819
3820 \b call \cw{frontend_default_colour()} (\k{frontend-default-colour})
3821 to fetch the front end's default background colour
3822
3823 \b alter the brightness of that colour if it's unsuitable
3824
3825 \b define brighter and darker variants of the colour to be used as
3826 highlights and lowlights
3827
3828 \b write those results into the relevant positions in the \c{ret}
3829 array.
3830
3831 Thus, \cw{ret[background*3]} to \cw{ret[background*3+2]} will be set
3832 to RGB values defining a sensible background colour, and similary
3833 \c{highlight} and \c{lowlight} will be set to sensible colours.
3834
3835 \C{writing} How to write a new puzzle
3836
3837 This chapter gives a guide to how to actually write a new puzzle:
3838 where to start, what to do first, how to solve common problems.
3839
3840 The previous chapters have been largely composed of facts. This one
3841 is mostly advice.
3842
3843 \H{writing-editorial} Choosing a puzzle
3844
3845 Before you start writing a puzzle, you have to choose one. Your
3846 taste in puzzle games is up to you, of course; and, in fact, you're
3847 probably reading this guide because you've \e{already} thought of a
3848 game you want to write. But if you want to get it accepted into the
3849 official Puzzles distribution, then there's a criterion it has to
3850 meet.
3851
3852 The current Puzzles editorial policy is that all games should be
3853 \e{fair}. A fair game is one which a player can only fail to
3854 complete through demonstrable lack of skill \dash that is, such that
3855 a better player in the same situation would have \e{known} to do
3856 something different.
3857
3858 For a start, that means every game presented to the user must have
3859 \e{at least one solution}. Giving the unsuspecting user a puzzle
3860 which is actually impossible is not acceptable. (There is an
3861 exception: if the user has selected some non-default option which is
3862 clearly labelled as potentially unfair, \e{then} you're allowed to
3863 generate possibly insoluble puzzles, because the user isn't
3864 unsuspecting any more. Same Game and Mines both have options of this
3865 type.)
3866
3867 Also, this actually \e{rules out} games such as Klondike, or the
3868 normal form of Mahjong Solitaire. Those games have the property that
3869 even if there is a solution (i.e. some sequence of moves which will
3870 get from the start state to the solved state), the player doesn't
3871 necessarily have enough information to \e{find} that solution. In
3872 both games, it is possible to reach a dead end because you had an
3873 arbitrary choice to make and made it the wrong way. This violates
3874 the fairness criterion, because a better player couldn't have known
3875 they needed to make the other choice.
3876
3877 (GNOME has a variant on Mahjong Solitaire which makes it fair: there
3878 is a Shuffle operation which randomly permutes all the remaining
3879 tiles without changing their positions, which allows you to get out
3880 of a sticky situation. Using this operation adds a 60-second penalty
3881 to your solution time, so it's to the player's advantage to try to
3882 minimise the chance of having to use it. It's still possible to
3883 render the game uncompletable if you end up with only two tiles
3884 vertically stacked, but that's easy to foresee and avoid using a
3885 shuffle operation. This form of the game \e{is} fair. Implementing
3886 it in Puzzles would require an infrastructure change so that the
3887 back end could communicate time penalties to the mid-end, but that
3888 would be easy enough.)
3889
3890 Providing a \e{unique} solution is a little more negotiable; it
3891 depends on the puzzle. Solo would have been of unacceptably low
3892 quality if it didn't always have a unique solution, whereas Twiddle
3893 inherently has multiple solutions by its very nature and it would
3894 have been meaningless to even \e{suggest} making it uniquely
3895 soluble. Somewhere in between, Flip could reasonably be made to have
3896 unique solutions (by enforcing a zero-dimension kernel in every
3897 generated matrix) but it doesn't seem like a serious quality problem
3898 that it doesn't.
3899
3900 Of course, you don't \e{have} to care about all this. There's
3901 nothing stopping you implementing any puzzle you want to if you're
3902 happy to maintain your puzzle yourself, distribute it from your own
3903 web site, fork the Puzzles code completely, or anything like that.
3904 It's free software; you can do what you like with it. But any game
3905 that you want to be accepted into \e{my} Puzzles code base has to
3906 satisfy the fairness criterion, which means all randomly generated
3907 puzzles must have a solution (unless the user has deliberately
3908 chosen otherwise) and it must be possible \e{in theory} to find that
3909 solution without having to guess.
3910
3911 \H{writing-gs} Getting started
3912
3913 The simplest way to start writing a new puzzle is to copy
3914 \c{nullgame.c}. This is a template puzzle source file which does
3915 almost nothing, but which contains all the back end function
3916 prototypes and declares the back end data structure correctly. It is
3917 built every time the rest of Puzzles is built, to ensure that it
3918 doesn't get out of sync with the code and remains buildable.
3919
3920 So start by copying \c{nullgame.c} into your new source file. Then
3921 you'll gradually add functionality until the very boring Null Game
3922 turns into your real game.
3923
3924 Next you'll need to add your puzzle to the Makefiles, in order to
3925 compile it conveniently. \e{Do not edit the Makefiles}: they are
3926 created automatically by the script \c{mkfiles.pl}, from the file
3927 called \c{Recipe}. Edit \c{Recipe}, and then re-run \c{mkfiles.pl}.
3928
3929 Also, don't forget to add your puzzle to \c{list.c}: if you don't,
3930 then it will still run fine on platforms which build each puzzle
3931 separately, but Mac OS X and other monolithic platforms will not
3932 include your new puzzle in their single binary.
3933
3934 Once your source file is building, you can move on to the fun bit.
3935
3936 \S{writing-generation} Puzzle generation
3937
3938 Randomly generating instances of your puzzle is almost certain to be
3939 the most difficult part of the code, and also the task with the
3940 highest chance of turning out to be completely infeasible. Therefore
3941 I strongly recommend doing it \e{first}, so that if it all goes
3942 horribly wrong you haven't wasted any more time than you absolutely
3943 had to. What I usually do is to take an unmodified \c{nullgame.c},
3944 and start adding code to \cw{new_game_desc()} which tries to
3945 generate a puzzle instance and print it out using \cw{printf()}.
3946 Once that's working, \e{then} I start connecting it up to the return
3947 value of \cw{new_game_desc()}, populating other structures like
3948 \c{game_params}, and generally writing the rest of the source file.
3949
3950 There are many ways to generate a puzzle which is known to be
3951 soluble. In this section I list all the methods I currently know of,
3952 in case any of them can be applied to your puzzle. (Not all of these
3953 methods will work, or in some cases even make sense, for all
3954 puzzles.)
3955
3956 Some puzzles are mathematically tractable, meaning you can work out
3957 in advance which instances are soluble. Sixteen, for example, has a
3958 parity constraint in some settings which renders exactly half the
3959 game space unreachable, but it can be mathematically proved that any
3960 position not in that half \e{is} reachable. Therefore, Sixteen's
3961 grid generation simply consists of selecting at random from a well
3962 defined subset of the game space. Cube in its default state is even
3963 easier: \e{every} possible arrangement of the blue squares and the
3964 cube's starting position is soluble!
3965
3966 Another option is to redefine what you mean by \q{soluble}. Black
3967 Box takes this approach. There are layouts of balls in the box which
3968 are completely indistinguishable from one another no matter how many
3969 beams you fire into the box from which angles, which would normally
3970 be grounds for declaring those layouts unfair; but fortunately,
3971 detecting that indistinguishability is computationally easy. So
3972 Black Box doesn't demand that your ball placements match its own; it
3973 merely demands that your ball placements be \e{indistinguishable}
3974 from the ones it was thinking of. If you have an ambiguous puzzle,
3975 then any of the possible answers is considered to be a solution.
3976 Having redefined the rules in that way, any puzzle is soluble again.
3977
3978 Those are the simple techniques. If they don't work, you have to get
3979 cleverer.
3980
3981 One way to generate a soluble puzzle is to start from the solved
3982 state and make inverse moves until you reach a starting state. Then
3983 you know there's a solution, because you can just list the inverse
3984 moves you made and make them in the opposite order to return to the
3985 solved state.
3986
3987 This method can be simple and effective for puzzles where you get to
3988 decide what's a starting state and what's not. In Pegs, for example,
3989 the generator begins with one peg in the centre of the board and
3990 makes inverse moves until it gets bored; in this puzzle, valid
3991 inverse moves are easy to detect, and \e{any} state that's reachable
3992 from the solved state by inverse moves is a reasonable starting
3993 position. So Pegs just continues making inverse moves until the
3994 board satisfies some criteria about extent and density, and then
3995 stops and declares itself done.
3996
3997 For other puzzles, it can be a lot more difficult. Same Game uses
3998 this strategy too, and it's lucky to get away with it at all: valid
3999 inverse moves aren't easy to find (because although it's easy to
4000 insert additional squares in a Same Game position, it's difficult to
4001 arrange that \e{after} the insertion they aren't adjacent to any
4002 other squares of the same colour), so you're constantly at risk of
4003 running out of options and having to backtrack or start again. Also,
4004 Same Game grids never start off half-empty, which means you can't
4005 just stop when you run out of moves \dash you have to find a way to
4006 fill the grid up \e{completely}.
4007
4008 The other way to generate a puzzle that's soluble is to start from
4009 the other end, and actually write a \e{solver}. This tends to ensure
4010 that a puzzle has a \e{unique} solution over and above having a
4011 solution at all, so it's a good technique to apply to puzzles for
4012 which that's important.
4013
4014 One theoretical drawback of generating soluble puzzles by using a
4015 solver is that your puzzles are restricted in difficulty to those
4016 which the solver can handle. (Most solvers are not fully general:
4017 many sets of puzzle rules are NP-complete or otherwise nasty, so
4018 most solvers can only handle a subset of the theoretically soluble
4019 puzzles.) It's been my experience in practice, however, that this
4020 usually isn't a problem; computers are good at very different things
4021 from humans, and what the computer thinks is nice and easy might
4022 still be pleasantly challenging for a human. For example, when
4023 solving Dominosa puzzles I frequently find myself using a variety of
4024 reasoning techniques that my solver doesn't know about; in
4025 principle, therefore, I should be able to solve the puzzle using
4026 only those techniques it \e{does} know about, but this would involve
4027 repeatedly searching the entire grid for the one simple deduction I
4028 can make. Computers are good at this sort of exhaustive search, but
4029 it's been my experience that human solvers prefer to do more complex
4030 deductions than to spend ages searching for simple ones. So in many
4031 cases I don't find my own playing experience to be limited by the
4032 restrictions on the solver.
4033
4034 (This isn't \e{always} the case. Solo is a counter-example;
4035 generating Solo puzzles using a simple solver does lead to
4036 qualitatively easier puzzles. Therefore I had to make the Solo
4037 solver rather more advanced than most of them.)
4038
4039 There are several different ways to apply a solver to the problem of
4040 generating a soluble puzzle. I list a few of them below.
4041
4042 The simplest approach is brute force: randomly generate a puzzle,
4043 use the solver to see if it's soluble, and if not, throw it away and
4044 try again until you get lucky. This is often a viable technique if
4045 all else fails, but it tends not to scale well: for many puzzle
4046 types, the probability of finding a uniquely soluble instance
4047 decreases sharply as puzzle size goes up, so this technique might
4048 work reasonably fast for small puzzles but take (almost) forever at
4049 larger sizes. Still, if there's no other alternative it can be
4050 usable: Pattern and Dominosa both use this technique. (However,
4051 Dominosa has a means of tweaking the randomly generated grids to
4052 increase the \e{probability} of them being soluble, by ruling out
4053 one of the most common ambiguous cases. This improved generation
4054 speed by over a factor of 10 on the highest preset!)
4055
4056 An approach which can be more scalable involves generating a grid
4057 and then tweaking it to make it soluble. This is the technique used
4058 by Mines and also by Net: first a random puzzle is generated, and
4059 then the solver is run to see how far it gets. Sometimes the solver
4060 will get stuck; when that happens, examine the area it's having
4061 trouble with, and make a small random change in that area to allow
4062 it to make more progress. Continue solving (possibly even without
4063 restarting the solver), tweaking as necessary, until the solver
4064 finishes. Then restart the solver from the beginning to ensure that
4065 the tweaks haven't caused new problems in the process of solving old
4066 ones (which can sometimes happen).
4067
4068 This strategy works well in situations where the usual solver
4069 failure mode is to get stuck in an easily localised spot. Thus it
4070 works well for Net and Mines, whose most common failure mode tends
4071 to be that most of the grid is fine but there are a few widely
4072 separated ambiguous sections; but it would work less well for
4073 Dominosa, in which the way you get stuck is to have scoured the
4074 whole grid and not found anything you can deduce \e{anywhere}. Also,
4075 it relies on there being a low probability that tweaking the grid
4076 introduces a new problem at the same time as solving the old one;
4077 Mines and Net also have the property that most of their deductions
4078 are local, so that it's very unlikely for a tweak to affect
4079 something half way across the grid from the location where it was
4080 applied. In Dominosa, by contrast, a lot of deductions use
4081 information about half the grid (\q{out of all the sixes, only one
4082 is next to a three}, which can depend on the values of up to 32 of
4083 the 56 squares in the default setting!), so this tweaking strategy
4084 would be rather less likely to work well.
4085
4086 A more specialised strategy is that used in Solo and Slant. These
4087 puzzles have the property that they derive their difficulty from not
4088 presenting all the available clues. (In Solo's case, if all the
4089 possible clues were provided then the puzzle would already be
4090 solved; in Slant it would still require user action to fill in the
4091 lines, but it would present no challenge at all). Therefore, a
4092 simple generation technique is to leave the decision of which clues
4093 to provide until the last minute. In other words, first generate a
4094 random \e{filled} grid with all possible clues present, and then
4095 gradually remove clues for as long as the solver reports that it's
4096 still soluble. Unlike the methods described above, this technique
4097 \e{cannot} fail \dash once you've got a filled grid, nothing can
4098 stop you from being able to convert it into a viable puzzle.
4099 However, it wouldn't even be meaningful to apply this technique to
4100 (say) Pattern, in which clues can never be left out, so the only way
4101 to affect the set of clues is by altering the solution.
4102
4103 (Unfortunately, Solo is complicated by the need to provide puzzles
4104 at varying difficulty levels. It's easy enough to generate a puzzle
4105 of \e{at most} a given level of difficulty; you just have a solver
4106 with configurable intelligence, and you set it to a given level and
4107 apply the above technique, thus guaranteeing that the resulting grid
4108 is solvable by someone with at most that much intelligence. However,
4109 generating a puzzle of \e{at least} a given level of difficulty is
4110 rather harder; if you go for \e{at most} Intermediate level, you're
4111 likely to find that you've accidentally generated a Trivial grid a
4112 lot of the time, because removing just one number is sufficient to
4113 take the puzzle from Trivial straight to Ambiguous. In that
4114 situation Solo has no remaining options but to throw the puzzle away
4115 and start again.)
4116
4117 A final strategy is to use the solver \e{during} puzzle
4118 construction: lay out a bit of the grid, run the solver to see what
4119 it allows you to deduce, and then lay out a bit more to allow the
4120 solver to make more progress. There are articles on the web that
4121 recommend constructing Sudoku puzzles by this method (which is
4122 completely the opposite way round to how Solo does it); for Sudoku
4123 it has the advantage that you get to specify your clue squares in
4124 advance (so you can have them make pretty patterns).
4125
4126 Rectangles uses a strategy along these lines. First it generates a
4127 grid by placing the actual rectangles; then it has to decide where
4128 in each rectangle to place a number. It uses a solver to help it
4129 place the numbers in such a way as to ensure a unique solution. It
4130 does this by means of running a test solver, but it runs the solver
4131 \e{before} it's placed any of the numbers \dash which means the
4132 solver must be capable of coping with uncertainty about exactly
4133 where the numbers are! It runs the solver as far as it can until it
4134 gets stuck; then it narrows down the possible positions of a number
4135 in order to allow the solver to make more progress, and so on. Most
4136 of the time this process terminates with the grid fully solved, at
4137 which point any remaining number-placement decisions can be made at
4138 random from the options not so far ruled out. Note that unlike the
4139 Net/Mines tweaking strategy described above, this algorithm does not
4140 require a checking run after it completes: if it finishes
4141 successfully at all, then it has definitely produced a uniquely
4142 soluble puzzle.
4143
4144 Most of the strategies described above are not 100% reliable. Each
4145 one has a failure rate: every so often it has to throw out the whole
4146 grid and generate a fresh one from scratch. (Solo's strategy would
4147 be the exception, if it weren't for the need to provide configurable
4148 difficulty levels.) Occasional failures are not a fundamental
4149 problem in this sort of work, however: it's just a question of
4150 dividing the grid generation time by the success rate (if it takes
4151 10ms to generate a candidate grid and 1/5 of them work, then it will
4152 take 50ms on average to generate a viable one), and seeing whether
4153 the expected time taken to \e{successfully} generate a puzzle is
4154 unacceptably slow. Dominosa's generator has a very low success rate
4155 (about 1 out of 20 candidate grids turn out to be usable, and if you
4156 think \e{that's} bad then go and look at the source code and find
4157 the comment showing what the figures were before the generation-time
4158 tweaks!), but the generator itself is very fast so this doesn't
4159 matter. Rectangles has a slower generator, but fails well under 50%
4160 of the time.
4161
4162 So don't be discouraged if you have an algorithm that doesn't always
4163 work: if it \e{nearly} always works, that's probably good enough.
4164 The one place where reliability is important is that your algorithm
4165 must never produce false positives: it must not claim a puzzle is
4166 soluble when it isn't. It can produce false negatives (failing to
4167 notice that a puzzle is soluble), and it can fail to generate a
4168 puzzle at all, provided it doesn't do either so often as to become
4169 slow.
4170
4171 One last piece of advice: for grid-based puzzles, when writing and
4172 testing your generation algorithm, it's almost always a good idea
4173 \e{not} to test it initially on a grid that's square (i.e.
4174 \cw{w==h}), because if the grid is square then you won't notice if
4175 you mistakenly write \c{h} instead of \c{w} (or vice versa)
4176 somewhere in the code. Use a rectangular grid for testing, and any
4177 size of grid will be likely to work after that.
4178
4179 \S{writing-textformats} Designing textual description formats
4180
4181 Another aspect of writing a puzzle which is worth putting some
4182 thought into is the design of the various text description formats:
4183 the format of the game parameter encoding, the game description
4184 encoding, and the move encoding.
4185
4186 The first two of these should be reasonably intuitive for a user to
4187 type in; so provide some flexibility where possible. Suppose, for
4188 example, your parameter format consists of two numbers separated by
4189 an \c{x} to specify the grid dimensions (\c{10x10} or \c{20x15}),
4190 and then has some suffixes to specify other aspects of the game
4191 type. It's almost always a good idea in this situation to arrange
4192 that \cw{decode_params()} can handle the suffixes appearing in any
4193 order, even if \cw{encode_params()} only ever generates them in one
4194 order.
4195
4196 These formats will also be expected to be reasonably stable: users
4197 will expect to be able to exchange game IDs with other users who
4198 aren't running exactly the same version of your game. So make them
4199 robust and stable: don't build too many assumptions into the game ID
4200 format which will have to be changed every time something subtle
4201 changes in the puzzle code.
4202
4203 \H{writing-howto} Common how-to questions
4204
4205 This section lists some common things people want to do when writing
4206 a puzzle, and describes how to achieve them within the Puzzles
4207 framework.
4208
4209 \S{writing-howto-cursor} Drawing objects at only one position
4210
4211 A common phenomenon is to have an object described in the
4212 \c{game_state} or the \c{game_ui} which can only be at one position.
4213 A cursor \dash probably specified in the \c{game_ui} \dash is a good
4214 example.
4215
4216 In the \c{game_ui}, it would \e{obviously} be silly to have an array
4217 covering the whole game grid with a boolean flag stating whether the
4218 cursor was at each position. Doing that would waste space, would
4219 make it difficult to find the cursor in order to do anything with
4220 it, and would introduce the potential for synchronisation bugs in
4221 which you ended up with two cursors or none. The obviously sensible
4222 way to store a cursor in the \c{game_ui} is to have fields directly
4223 encoding the cursor's coordinates.
4224
4225 However, it is a mistake to assume that the same logic applies to
4226 the \c{game_drawstate}. If you replicate the cursor position fields
4227 in the draw state, the redraw code will get very complicated. In the
4228 draw state, in fact, it \e{is} probably the right thing to have a
4229 cursor flag for every position in the grid. You probably have an
4230 array for the whole grid in the drawstate already (stating what is
4231 currently displayed in the window at each position); the sensible
4232 approach is to add a \q{cursor} flag to each element of that array.
4233 Then the main redraw loop will look something like this
4234 (pseudo-code):
4235
4236 \c for (y = 0; y < h; y++) {
4237 \c     for (x = 0; x < w; x++) {
4238 \c         int value = state->symbol_at_position[y][x];
4239 \c         if (x == ui->cursor_x && y == ui->cursor_y)
4240 \c             value |= CURSOR;
4241 \c         if (ds->symbol_at_position[y][x] != value) {
4242 \c             symbol_drawing_subroutine(dr, ds, x, y, value);
4243 \c             ds->symbol_at_position[y][x] = value;
4244 \c         }
4245 \c     }
4246 \c }
4247
4248 This loop is very simple, pretty hard to get wrong, and
4249 \e{automatically} deals both with erasing the previous cursor and
4250 drawing the new one, with no special case code required.
4251
4252 This type of loop is generally a sensible way to write a redraw
4253 function, in fact. The best thing is to ensure that the information
4254 stored in the draw state for each position tells you \e{everything}
4255 about what was drawn there. A good way to ensure that is to pass
4256 precisely the same information, and \e{only} that information, to a
4257 subroutine that does the actual drawing; then you know there's no
4258 additional information which affects the drawing but which you don't
4259 notice changes in.
4260
4261 \S{writing-keyboard-cursor} Implementing a keyboard-controlled cursor
4262
4263 It is often useful to provide a keyboard control method in a
4264 basically mouse-controlled game. A keyboard-controlled cursor is
4265 best implemented by storing its location in the \c{game_ui} (since
4266 if it were in the \c{game_state} then the user would have to
4267 separately undo every cursor move operation). So the procedure would
4268 be:
4269
4270 \b Put cursor position fields in the \c{game_ui}.
4271
4272 \b \cw{interpret_move()} responds to arrow keys by modifying the
4273 cursor position fields and returning \cw{""}.
4274
4275 \b \cw{interpret_move()} responds to some sort of fire button by
4276 actually performing a move based on the current cursor location.
4277
4278 \b You might want an additional \c{game_ui} field stating whether
4279 the cursor is currently visible, and having it disappear when a
4280 mouse action occurs (so that it doesn't clutter the display when not
4281 actually in use).
4282
4283 \b You might also want to automatically hide the cursor in
4284 \cw{changed_state()} when the current game state changes to one in
4285 which there is no move to make (which is the case in some types of
4286 completed game).
4287
4288 \b \cw{redraw()} draws the cursor using the technique described in
4289 \k{writing-howto-cursor}.
4290
4291 \S{writing-howto-dragging} Implementing draggable sprites
4292
4293 Some games have a user interface which involves dragging some sort
4294 of game element around using the mouse. If you need to show a
4295 graphic moving smoothly over the top of other graphics, use a
4296 blitter (see \k{drawing-blitter} for the blitter API) to save the
4297 background underneath it. The typical scenario goes:
4298
4299 \b Have a blitter field in the \c{game_drawstate}.
4300
4301 \b Set the blitter field to \cw{NULL} in the game's
4302 \cw{new_drawstate()} function, since you don't yet know how big the
4303 piece of saved background needs to be.
4304
4305 \b In the game's \cw{set_size()} function, once you know the size of
4306 the object you'll be dragging around the display and hence the
4307 required size of the blitter, actually allocate the blitter.
4308
4309 \b In \cw{free_drawstate()}, free the blitter if it's not \cw{NULL}.
4310
4311 \b In \cw{interpret_move()}, respond to mouse-down and mouse-drag
4312 events by updating some fields in the \cw{game_ui} which indicate
4313 that a drag is in progress.
4314
4315 \b At the \e{very end} of \cw{redraw()}, after all other drawing has
4316 been done, draw the moving object if there is one. First save the
4317 background under the object in the blitter; then set a clip
4318 rectangle covering precisely the area you just saved (just in case
4319 anti-aliasing or some other error causes your drawing to go beyond
4320 the area you saved). Then draw the object, and call \cw{unclip()}.
4321 Finally, set a flag in the \cw{game_drawstate} that indicates that
4322 the blitter needs restoring.
4323
4324 \b At the very start of \cw{redraw()}, before doing anything else at
4325 all, check the flag in the \cw{game_drawstate}, and if it says the
4326 blitter needs restoring then restore it. (Then clear the flag, so
4327 that this won't happen again in the next redraw if no moving object
4328 is drawn this time.)
4329
4330 This way, you will be able to write the rest of the redraw function
4331 completely ignoring the dragged object, as if it were floating above
4332 your bitmap and being completely separate.
4333
4334 \S{writing-ref-counting} Sharing large invariant data between all
4335 game states
4336
4337 In some puzzles, there is a large amount of data which never changes
4338 between game states. The array of numbers in Dominosa is a good
4339 example.
4340
4341 You \e{could} dynamically allocate a copy of that array in every
4342 \c{game_state}, and have \cw{dup_game()} make a fresh copy of it for
4343 every new \c{game_state}; but it would waste memory and time. A
4344 more efficient way is to use a reference-counted structure.
4345
4346 \b Define a structure type containing the data in question, and also
4347 containing an integer reference count.
4348
4349 \b Have a field in \c{game_state} which is a pointer to this
4350 structure.
4351
4352 \b In \cw{new_game()}, when creating a fresh game state at the start
4353 of a new game, create an instance of this structure, initialise it
4354 with the invariant data, and set its reference count to 1.
4355
4356 \b In \cw{dup_game()}, rather than making a copy of the structure
4357 for the new game state, simply set the new game state to point at
4358 the same copy of the structure, and increment its reference count.
4359
4360 \b In \cw{free_game()}, decrement the reference count in the
4361 structure pointed to by the game state; if the count reaches zero,
4362 free the structure.
4363
4364 This way, the invariant data will persist for only as long as it's
4365 genuinely needed; \e{as soon} as the last game state for a
4366 particular puzzle instance is freed, the invariant data for that
4367 puzzle will vanish as well. Reference counting is a very efficient
4368 form of garbage collection, when it works at all. (Which it does in
4369 this instance, of course, because there's no possibility of circular
4370 references.)
4371
4372 \S{writing-flash-types} Implementing multiple types of flash
4373
4374 In some games you need to flash in more than one different way.
4375 Mines, for example, flashes white when you win, and flashes red when
4376 you tread on a mine and die.
4377
4378 The simple way to do this is:
4379
4380 \b Have a field in the \c{game_ui} which describes the type of flash.
4381
4382 \b In \cw{flash_length()}, examine the old and new game states to
4383 decide whether a flash is required and what type. Write the type of
4384 flash to the \c{game_ui} field whenever you return non-zero.
4385
4386 \b In \cw{redraw()}, when you detect that \c{flash_time} is
4387 non-zero, examine the field in \c{game_ui} to decide which type of
4388 flash to draw.
4389
4390 \cw{redraw()} will never be called with \c{flash_time} non-zero
4391 unless \cw{flash_length()} was first called to tell the mid-end that
4392 a flash was required; so whenever \cw{redraw()} notices that
4393 \c{flash_time} is non-zero, you can be sure that the field in
4394 \c{game_ui} is correctly set.
4395
4396 \S{writing-move-anim} Animating game moves
4397
4398 A number of puzzle types benefit from a quick animation of each move
4399 you make.
4400
4401 For some games, such as Fifteen, this is particularly easy. Whenever
4402 \cw{redraw()} is called with \c{oldstate} non-\cw{NULL}, Fifteen
4403 simply compares the position of each tile in the two game states,
4404 and if the tile is not in the same place then it draws it some
4405 fraction of the way from its old position to its new position. This
4406 method copes automatically with undo.
4407
4408 Other games are less obvious. In Sixteen, for example, you can't
4409 just draw each tile a fraction of the way from its old to its new
4410 position: if you did that, the end tile would zip very rapidly past
4411 all the others to get to the other end and that would look silly.
4412 (Worse, it would look inconsistent if the end tile was drawn on top
4413 going one way and on the bottom going the other way.)
4414
4415 A useful trick here is to define a field or two in the game state
4416 that indicates what the last move was.
4417
4418 \b Add a \q{last move} field to the \c{game_state} (or two or more
4419 fields if the move is complex enough to need them).
4420
4421 \b \cw{new_game()} initialises this field to a null value for a new
4422 game state.
4423
4424 \b \cw{execute_move()} sets up the field to reflect the move it just
4425 performed.
4426
4427 \b \cw{redraw()} now needs to examine its \c{dir} parameter. If
4428 \c{dir} is positive, it determines the move being animated by
4429 looking at the last-move field in \c{newstate}; but if \c{dir} is
4430 negative, it has to look at the last-move field in \c{oldstate}, and
4431 invert whatever move it finds there.
4432
4433 Note also that Sixteen needs to store the \e{direction} of the move,
4434 because you can't quite determine it by examining the row or column
4435 in question. You can in almost all cases, but when the row is
4436 precisely two squares long it doesn't work since a move in either
4437 direction looks the same. (You could argue that since moving a
4438 2-element row left and right has the same effect, it doesn't matter
4439 which one you animate; but in fact it's very disorienting to click
4440 the arrow left and find the row moving right, and almost as bad to
4441 undo a move to the right and find the game animating \e{another}
4442 move to the right.)
4443
4444 \S{writing-conditional-anim} Animating drag operations
4445
4446 In Untangle, moves are made by dragging a node from an old position
4447 to a new position. Therefore, at the time when the move is initially
4448 made, it should not be animated, because the node has already been
4449 dragged to the right place and doesn't need moving there. However,
4450 it's nice to animate the same move if it's later undone or redone.
4451 This requires a bit of fiddling.
4452
4453 The obvious approach is to have a flag in the \c{game_ui} which
4454 inhibits move animation, and to set that flag in
4455 \cw{interpret_move()}. The question is, when would the flag be reset
4456 again? The obvious place to do so is \cw{changed_state()}, which
4457 will be called once per move. But it will be called \e{before}
4458 \cw{anim_length()}, so if it resets the flag then \cw{anim_length()}
4459 will never see the flag set at all.
4460
4461 The solution is to have \e{two} flags in a queue.
4462
4463 \b Define two flags in \c{game_ui}; let's call them \q{current} and
4464 \q{next}.
4465
4466 \b Set both to \cw{FALSE} in \c{new_ui()}.
4467
4468 \b When a drag operation completes in \cw{interpret_move()}, set the
4469 \q{next} flag to \cw{TRUE}.
4470
4471 \b Every time \cw{changed_state()} is called, set the value of
4472 \q{current} to the value in \q{next}, and then set the value of
4473 \q{next} to \cw{FALSE}.
4474
4475 \b That way, \q{current} will be \cw{TRUE} \e{after} a call to
4476 \cw{changed_state()} if and only if that call to
4477 \cw{changed_state()} was the result of a drag operation processed by
4478 \cw{interpret_move()}. Any other call to \cw{changed_state()}, due
4479 to an Undo or a Redo or a Restart or a Solve, will leave \q{current}
4480 \cw{FALSE}.
4481
4482 \b So now \cw{anim_length()} can request a move animation if and
4483 only if the \q{current} flag is \e{not} set.
4484
4485 \S{writing-cheating} Inhibiting the victory flash when Solve is used
4486
4487 Many games flash when you complete them, as a visual congratulation
4488 for having got to the end of the puzzle. It often seems like a good
4489 idea to disable that flash when the puzzle is brought to a solved
4490 state by means of the Solve operation.
4491
4492 This is easily done:
4493
4494 \b Add a \q{cheated} flag to the \c{game_state}.
4495
4496 \b Set this flag to \cw{FALSE} in \cw{new_game()}.
4497
4498 \b Have \cw{solve()} return a move description string which clearly
4499 identifies the move as a solve operation.
4500
4501 \b Have \cw{execute_move()} respond to that clear identification by
4502 setting the \q{cheated} flag in the returned \c{game_state}. The
4503 flag will then be propagated to all subsequent game states, even if
4504 the user continues fiddling with the game after it is solved.
4505
4506 \b \cw{flash_length()} now returns non-zero if \c{oldstate} is not
4507 completed and \c{newstate} is, \e{and} neither state has the
4508 \q{cheated} flag set.
4509
4510 \H{writing-testing} Things to test once your puzzle is written
4511
4512 Puzzle implementations written in this framework are self-testing as
4513 far as I could make them.
4514
4515 Textual game and move descriptions, for example, are generated and
4516 parsed as part of the normal process of play. Therefore, if you can
4517 make moves in the game \e{at all} you can be reasonably confident
4518 that the mid-end serialisation interface will function correctly and
4519 you will be able to save your game. (By contrast, if I'd stuck with
4520 a single \cw{make_move()} function performing the jobs of both
4521 \cw{interpret_move()} and \cw{execute_move()}, and had separate
4522 functions to encode and decode a game state in string form, then
4523 those functions would not be used during normal play; so they could
4524 have been completely broken, and you'd never know it until you tried
4525 to save the game \dash which would have meant you'd have to test
4526 game saving \e{extensively} and make sure to test every possible
4527 type of game state. As an added bonus, doing it the way I did leads
4528 to smaller save files.)
4529
4530 There is one exception to this, which is the string encoding of the
4531 \c{game_ui}. Most games do not store anything permanent in the
4532 \c{game_ui}, and hence do not need to put anything in its encode and
4533 decode functions; but if there is anything in there, you do need to
4534 test game loading and saving to ensure those functions work
4535 properly.
4536
4537 It's also worth testing undo and redo of all operations, to ensure
4538 that the redraw and the animations (if any) work properly. Failing
4539 to animate undo properly seems to be a common error.
4540
4541 Other than that, just use your common sense.