1 Developer documentation for Simon Tatham's puzzle collection
2 ============================================================
4 This is a guide to the internal structure of Simon Tatham's Portable
5 Puzzle Collection (henceforth referred to simply as `Puzzles'), for
6 use by anyone attempting to implement a new puzzle or port to a new
9 This guide is believed correct as of r6190. Hopefully it will be updated
10 along with the code in future, but if not, I've at least left this
11 version number in here so you can figure out what's changed by tracking
12 commit comments from there onwards.
17 The Puzzles code base is divided into four parts: a set of
18 interchangeable front ends, a set of interchangeable back ends, a
19 universal `middle end' which acts as a buffer between the two, and a
20 bunch of miscellaneous utility functions. In the following sections I
21 give some general discussion of each of these parts.
26 The front end is the non-portable part of the code: it's the bit that
27 you replace completely when you port to a different platform. So it's
28 responsible for all system calls, all GUI interaction, and anything else
31 The current front ends in the main code base are for Windows, GTK and
32 MacOS X; I also know of a third-party front end for PalmOS.
34 The front end contains main() or the local platform's equivalent. Top-
35 level control over the application's execution flow belongs to the front
36 end (it isn't, for example, a set of functions called by a universal
37 main() somewhere else).
39 The front end has complete freedom to design the GUI for any given
40 port of Puzzles. There is no centralised mechanism for maintaining the
41 menu layout, for example. This has a cost in consistency (when I _do_
42 want the same menu layout on more than one platform, I have to edit
43 two pieces of code in parallel every time I make a change), but the
44 advantage is that local GUI conventions can be conformed to and local
45 constraints adapted to. For example, MacOS X has strict human interface
46 guidelines which specify a different menu layout from the one I've used
47 on Windows and GTK; there's nothing stopping the OS X front end from
48 providing a menu layout consistent with those guidelines.
50 Although the front end is mostly caller rather than the callee in its
51 interactions with other parts of the code, it is required to implement
52 a small API for other modules to call, mostly of drawing functions for
53 games to use when drawing their graphics. The drawing API is documented
54 in chapter 3; the other miscellaneous front end API functions are
55 documented in section 4.35.
60 A `back end', in this collection, is synonymous with a `puzzle'. Each
61 back end implements a different game.
63 At the top level, a back end is simply a data structure, containing a
64 few constants (flag words, preferred pixel size) and a large number of
65 function pointers. Back ends are almost invariably callee rather than
66 caller, which means there's a limitation on what a back end can do on
69 The persistent state in a back end is divided into a number of data
70 structures, which are used for different purposes and therefore likely
71 to be switched around, changed without notice, and otherwise updated by
72 the rest of the code. It is important when designing a back end to put
73 the right pieces of data into the right structures, or standard midend-
74 provided features (such as Undo) may fail to work.
76 The functions and variables provided in the back end data structure are
77 documented in chapter 2.
82 Puzzles has a single and universal `middle end'. This code is common to
83 all platforms and all games; it sits in between the front end and the
84 back end and provides standard functionality everywhere.
86 People adding new back ends or new front ends should generally not need
87 to edit the middle end. On rare occasions there might be a change that
88 can be made to the middle end to permit a new game to do something not
89 currently anticipated by the middle end's present design; however, this
90 is terribly easy to get wrong and should probably not be undertaken
91 without consulting the primary maintainer (me). Patch submissions
92 containing unannounced mid-end changes will be treated on their merits
93 like any other patch; this is just a friendly warning that mid-end
94 changes will need quite a lot of merits to make them acceptable.
96 Functionality provided by the mid-end includes:
98 - Maintaining a list of game state structures and moving back and
99 forth along that list to provide Undo and Redo.
101 - Handling timers (for move animations, flashes on completion, and in
102 some cases actually timing the game).
104 - Handling the container format of game IDs: receiving them, picking
105 them apart into parameters, description and/or random seed, and
106 so on. The game back end need only handle the individual parts
107 of a game ID (encoded parameters and encoded game description);
108 everything else is handled centrally by the mid-end.
110 - Handling standard keystrokes and menu commands, such as `New Game',
111 `Restart Game' and `Quit'.
113 - Pre-processing mouse events so that the game back ends can rely on
114 them arriving in a sensible order (no missing button-release events,
115 no sudden changes of which button is currently pressed, etc).
117 - Handling the dialog boxes which ask the user for a game ID.
119 - Handling serialisation of entire games (for loading and saving a
120 half-finished game to a disk file, or for handling application
121 shutdown and restart on platforms such as PalmOS where state is
122 expected to be saved).
124 Thus, there's a lot of work done once by the mid-end so that individual
125 back ends don't have to worry about it. All the back end has to do is
126 cooperate in ensuring the mid-end can do its work properly.
128 The API of functions provided by the mid-end to be called by the front
129 end is documented in chapter 4.
131 1.4. Miscellaneous utilities
132 ----------------------------
134 In addition to these three major structural components, the Puzzles code
135 also contains a variety of utility modules usable by all of the above
136 components. There is a set of functions to provide platform-independent
137 random number generation; functions to make memory allocation easier;
138 functions which implement a balanced tree structure to be used as
139 necessary in complex algorithms; and a few other miscellaneous
140 functions. All of these are documented in chapter 5.
142 1.5. Structure of this guide
143 ----------------------------
145 There are a number of function call interfaces within Puzzles, and this
146 guide will discuss each one in a chapter of its own. After that, chapter
147 6 discusses how to design new games, with some general design thoughts
150 2. Interface to the back end
151 ----------------------------
153 This chapter gives a detailed discussion of the interface that each back
156 At the top level, each back end source file exports a single global
157 symbol, which is a `const struct game' containing a large number of
158 function pointers and a small amount of constant data. This structure is
159 called by different names depending on what kind of platform the puzzle
160 set is being compiled on:
162 - On platforms such as Windows and GTK, which build a separate binary
163 for each puzzle, the game structure in every back end has the same
164 name, `thegame'; the front end refers directly to this name, so that
165 compiling the same front end module against a different back end
166 module builds a different puzzle.
168 - On platforms such as MacOS X and PalmOS, which build all the puzzles
169 into a single monolithic binary, the game structure in each back end
170 must have a different name, and there's a helper module `list.c'
171 (constructed automatically by the same Perl script that builds the
172 Makefiles) which contains a complete list of those game structures.
174 On the latter type of platform, source files may assume that the
175 preprocessor symbol `COMBINED' has been defined. Thus, the usual code to
176 declare the game structure looks something like this:
179 #define thegame net /* or whatever this game is called */
182 const struct game thegame = {
183 /* lots of structure initialisation in here */
186 Game back ends must also internally define a number of data structures,
187 for storing their various persistent state. This chapter will first
188 discuss the nature and use of those structures, and then go on to give
189 details of every element of the game structure.
194 Each game is required to define four separate data structures. This
195 section discusses each one and suggests what sorts of things need to be
201 The `game_params' structure contains anything which affects the
202 automatic generation of new puzzles. So if puzzle generation is
203 parametrised in any way, those parameters need to be stored in
206 Most puzzles currently in this collection are played on a grid of
207 squares, meaning that the most obvious parameter is the grid size. Many
208 puzzles have additional parameters; for example, Mines allows you to
209 control the number of mines in the grid independently of its size, Net
210 can be wrapping or non-wrapping, Solo has difficulty levels and symmetry
213 A simple rule for deciding whether a data item needs to go in
214 `game_params' is: would the user expect to be able to control this data
215 item from either the preset-game-types menu or the `Custom' game type
216 configuration? If so, it's part of `game_params'.
218 `game_params' structures are permitted to contain pointers to subsidiary
219 data if they need to. The back end is required to provide functions to
220 create and destroy `game_params', and those functions can allocate and
221 free additional memory if necessary. (It has not yet been necessary to
222 do this in any puzzle so far, but the capability is there just in case.)
224 `game_params' is also the only structure which the game's compute_size()
225 function may refer to; this means that any aspect of the game which
226 affects the size of the window it needs to be drawn in must be stored in
227 `game_params'. In particular, this imposes the fundamental limitation
228 that random game generation may not have a random effect on the window
229 size: game generation algorithms are constrained to work by starting
230 from the grid size rather than generating it as an emergent phenomenon.
231 (Although this is a restriction in theory, it has not yet seemed to be a
237 While the user is actually playing a puzzle, the `game_state' structure
238 stores all the data corresponding to the current state of play.
240 The mid-end keeps `game_state's in a list, and adds to the list every
241 time the player makes a move; the Undo and Redo functions step back and
242 forth through that list.
244 Therefore, a good means of deciding whether a data item needs to go in
245 `game_state' is: would a player expect that data item to be restored on
246 undo? If so, put it in `game_state', and this will automatically happen
247 without you having to lift a finger. If not - for example, the deaths
248 counter in Mines is precisely something that does _not_ want to be reset
249 to its previous state on an undo - then you might have found a data item
250 that needs to go in `game_ui' instead.
252 During play, `game_state's are often passed around without an
253 accompanying `game_params' structure. Therefore, any information in
254 `game_params' which is important during play (such as the grid size)
255 must be duplicated within the `game_state'. One simple method of doing
256 this is to have the `game_state' structure _contain_ a `game_params'
257 structure as one of its members, although this isn't obligatory if you
258 prefer to do it another way.
260 2.1.3. `game_drawstate'
261 -----------------------
263 `game_drawstate' carries persistent state relating to the current
264 graphical contents of the puzzle window. The same `game_drawstate'
265 is passed to every call to the game redraw function, so that it can
266 remember what it has already drawn and what needs redrawing.
268 A typical use for a `game_drawstate' is to have an array mirroring the
269 array of grid squares in the `game_state'; then every time the redraw
270 function was passed a `game_state', it would loop over all the squares,
271 and physically redraw any whose description in the `game_state' (i.e.
272 what the square needs to look like when the redraw is completed) did
273 not match its description in the `game_drawstate' (i.e. what the square
274 currently looks like).
276 `game_drawstate' is occasionally completely torn down and reconstructed
277 by the mid-end, if the user somehow forces a full redraw. Therefore, no
278 data should be stored in `game_drawstate' which is _not_ related to the
279 state of the puzzle window, because it might be unexpectedly destroyed.
281 The back end provides functions to create and destroy `game_drawstate',
282 which means it can contain pointers to subsidiary allocated data if it
283 needs to. A common thing to want to allocate in a `game_drawstate' is a
284 `blitter'; see section 3.1.13 for more on this subject.
289 `game_ui' contains whatever doesn't fit into the above three structures!
291 A new `game_ui' is created when the user begins playing a new instance
292 of a puzzle (i.e. during `New Game' or after entering a game ID etc). It
293 persists until the user finishes playing that game and begins another
294 one (or closes the window); in particular, `Restart Game' does _not_
295 destroy the `game_ui'.
297 `game_ui' is useful for implementing user-interface state which is not
298 part of `game_state'. Common examples are keyboard control (you wouldn't
299 want to have to separately Undo through every cursor motion) and mouse
300 dragging. See section 6.3.2 and section 6.3.3, respectively, for more
303 Another use for `game_ui' is to store highly persistent data such as
304 the Mines death counter. This is conceptually rather different: where
305 the Net cursor position was _not important enough_ to preserve for the
306 player to restore by Undo, the Mines death counter is _too important_ to
307 permit the player to revert by Undo!
309 A final use for `game_ui' is to pass information to the redraw function
310 about recent changes to the game state. This is used in Mines, for
311 example, to indicate whether a requested `flash' should be a white flash
312 for victory or a red flash for defeat; see section 6.3.5.
314 2.2. Simple data in the back end
315 --------------------------------
317 In this section I begin to discuss each individual element in the back
318 end structure. To begin with, here are some simple self-contained data
326 This is a simple ASCII string giving the name of the puzzle. This name
327 will be used in window titles, in game selection menus on monolithic
328 platforms, and anywhere else that the front end needs to know the name
331 2.2.2. `winhelp_topic'
332 ----------------------
334 const char *winhelp_topic;
336 This member is used on Windows only, to provide online help. Although
337 the Windows front end provides a separate binary for each puzzle, it has
338 a single monolithic help file; so when a user selects `Help' from the
339 menu, the program needs to open the help file and jump to the chapter
340 describing that particular puzzle.
342 Therefore, each chapter in `puzzles.but' is labelled with a _help topic_
343 name, similar to this:
345 \cfg{winhelp-topic}{games.net}
347 And then the corresponding game back end encodes the topic string (here
348 `games.net') in the `winhelp_topic' element of the game structure.
350 2.3. Handling game parameter sets
351 ---------------------------------
353 In this section I present the various functions which handle the
354 `game_params' structure.
356 2.3.1. default_params()
357 -----------------------
359 game_params *(*default_params)(void);
361 This function allocates a new `game_params' structure, fills it with the
362 default values, and returns a pointer to it.
364 2.3.2. fetch_preset()
365 ---------------------
367 int (*fetch_preset)(int i, char **name, game_params **params);
369 This function is used to populate the `Type' menu, which provides a list
370 of conveniently accessible preset parameters for most games.
372 The function is called with `i' equal to the index of the preset
373 required (numbering from zero). It returns FALSE if that preset does
374 not exist (if `i' is less than zero or greater than the largest preset
375 index). Otherwise, it sets `*params' to point at a newly allocated
376 `game_params' structure containing the preset information, sets `*name'
377 to point at a newly allocated C string containing the preset title (to
378 go on the `Type' menu), and returns TRUE.
380 If the game does not wish to support any presets at all, this function
381 is permitted to return FALSE always.
383 2.3.3. encode_params()
384 ----------------------
386 char *(*encode_params)(const game_params *params, int full);
388 The job of this function is to take a `game_params', and encode it in
389 a string form for use in game IDs. The return value must be a newly
390 allocated C string, and _must_ not contain a colon or a hash (since
391 those characters are used to mark the end of the parameter section in a
394 Ideally, it should also not contain any other potentially controversial
395 punctuation; bear in mind when designing a string parameter format
396 that it will probably be used on both Windows and Unix command lines
397 under a variety of exciting shell quoting and metacharacter rules.
398 Sticking entirely to alphanumerics is the safest thing; if you really
399 need punctuation, you can probably get away with commas, periods or
400 underscores without causing anybody any major inconvenience. If you
401 venture far beyond that, you're likely to irritate _somebody_.
403 (At the time of writing this, all existing games have purely
404 alphanumeric string parameter formats. Usually these involve a letter
405 denoting a parameter, followed optionally by a number giving the value
406 of that parameter, with a few mandatory parts at the beginning such as
407 numeric width and height separated by `x'.)
409 If the `full' parameter is TRUE, this function should encode absolutely
410 everything in the `game_params', such that a subsequent call to
411 decode_params() (section 2.3.4) will yield an identical structure.
412 If `full' is FALSE, however, you should leave out anything which
413 is not necessary to describe a _specific puzzle instance_, i.e.
414 anything which only takes effect when a new puzzle is _generated_.
415 For example, the Solo `game_params' includes a difficulty rating used
416 when constructing new puzzles; but a Solo game ID need not explicitly
417 include the difficulty, since to describe a puzzle once generated it's
418 sufficient to give the grid dimensions and the location and contents
419 of the clue squares. (Indeed, one might very easily type in a puzzle
420 out of a newspaper without _knowing_ what its difficulty level is in
421 Solo's terminology.) Therefore, Solo's encode_params() only encodes the
422 difficulty level if `full' is set.
424 2.3.4. decode_params()
425 ----------------------
427 void (*decode_params)(game_params *params, char const *string);
429 This function is the inverse of encode_params() (section 2.3.3). It
430 parses the supplied string and fills in the supplied `game_params'
431 structure. Note that the structure will _already_ have been allocated:
432 this function is not expected to create a _new_ `game_params', but to
433 modify an existing one.
435 This function can receive a string which only encodes a subset of the
436 parameters. The most obvious way in which this can happen is if the
437 string was constructed by encode_params() with its `full' parameter set
438 to FALSE; however, it could also happen if the user typed in a parameter
439 set manually and missed something out. Be prepared to deal with a wide
440 range of possibilities.
442 When dealing with a parameter which is not specified in the input
443 string, what to do requires a judgment call on the part of the
444 programmer. Sometimes it makes sense to adjust other parameters to bring
445 them into line with the new ones. In Mines, for example, you would
446 probably not want to keep the same mine count if the user dropped the
447 grid size and didn't specify one, since you might easily end up with
448 more mines than would actually fit in the grid! On the other hand,
449 sometimes it makes sense to leave the parameter alone: a Solo player
450 might reasonably expect to be able to configure size and difficulty
451 independently of one another.
453 This function currently has no direct means of returning an error if the
454 string cannot be parsed at all. However, the returned `game_params' is
455 almost always subsequently passed to validate_params() (section 2.3.10),
456 so if you really want to signal parse errors, you could always have a
457 `char *' in your parameters structure which stored an error message, and
458 have validate_params() return it if it is non-NULL.
463 void (*free_params)(game_params *params);
465 This function frees a `game_params' structure, and any subsidiary
466 allocations contained within it.
471 game_params *(*dup_params)(const game_params *params);
473 This function allocates a new `game_params' structure and initialises it
474 with an exact copy of the information in the one provided as input. It
475 returns a pointer to the new duplicate.
477 2.3.7. `can_configure'
478 ----------------------
482 This boolean data element is set to TRUE if the back end supports
483 custom parameter configuration via a dialog box. If it is TRUE, then
484 the functions configure() and custom_params() are expected to work. See
485 section 2.3.8 and section 2.3.9 for more details.
490 config_item *(*configure)(const game_params *params);
492 This function is called when the user requests a dialog box for
493 custom parameter configuration. It returns a newly allocated array of
494 config_item structures, describing the GUI elements required in the
495 dialog box. The array should have one more element than the number of
496 controls, since it is terminated with a C_END marker (see below). Each
497 array element describes the control together with its initial value; the
498 front end will modify the value fields and return the updated array to
499 custom_params() (see section 2.3.9).
501 The config_item structure contains the following elements:
508 `name' is an ASCII string giving the textual label for a GUI control. It
509 is _not_ expected to be dynamically allocated.
511 `type' contains one of a small number of `enum' values defining what
512 type of control is being described. The meaning of the `sval' and `ival'
513 fields depends on the value in `type'. The valid values are:
517 Describes a text input box. (This is also used for numeric input.
518 The back end does not bother informing the front end that the box is
519 numeric rather than textual; some front ends do have the capacity
520 to take this into account, but I decided it wasn't worth the extra
521 complexity in the interface.) For this type, `ival' is unused, and
522 `sval' contains a dynamically allocated string representing the
523 contents of the input box.
527 Describes a simple checkbox. For this type, `sval' is unused, and
528 `ival' is TRUE or FALSE.
532 Describes a drop-down list presenting one of a small number of
533 fixed choices. For this type, `sval' contains a list of strings
534 describing the choices; the very first character of `sval' is
535 used as a delimiter when processing the rest (so that the strings
536 `:zero:one:two', `!zero!one!two' and `xzeroxonextwo' all define
537 a three-element list containing `zero', `one' and `two'). `ival'
538 contains the index of the currently selected element, numbering from
539 zero (so that in the above example, 0 would mean `zero' and 2 would
542 Note that for this control type, `sval' is _not_ dynamically
543 allocated, whereas it was for `C_STRING'.
547 Marks the end of the array of `config_item's. All other fields are
550 The array returned from this function is expected to have filled in the
551 initial values of all the controls according to the input `game_params'
554 If the game's `can_configure' flag is set to FALSE, this function is
555 never called and need not do anything at all.
557 2.3.9. custom_params()
558 ----------------------
560 game_params *(*custom_params)(const config_item *cfg);
562 This function is the counterpart to configure() (section 2.3.8). It
563 receives as input an array of `config_item's which was originally
564 created by configure(), but in which the control values have since been
565 changed in accordance with user input. Its function is to read the new
566 values out of the controls and return a newly allocated `game_params'
567 structure representing the user's chosen parameter set.
569 (The front end will have modified the controls' _values_, but there will
570 still always be the same set of controls, in the same order, as provided
571 by configure(). It is not necessary to check the `name' and `type'
572 fields, although you could use assert() if you were feeling energetic.)
574 This function is not expected to (and indeed _must not_) free the input
575 `config_item' array. (If the parameters fail to validate, the dialog box
578 If the game's `can_configure' flag is set to FALSE, this function is
579 never called and need not do anything at all.
581 2.3.10. validate_params()
582 -------------------------
584 char *(*validate_params)(const game_params *params, int full);
586 This function takes a `game_params' structure as input, and checks that
587 the parameters described in it fall within sensible limits. (At the very
588 least, grid dimensions should almost certainly be strictly positive, for
591 Return value is NULL if no problems were found, or alternatively a (non-
592 dynamically-allocated) ASCII string describing the error in human-
595 If the `full' parameter is set, full validation should be performed: any
596 set of parameters which would not permit generation of a sensible puzzle
597 should be faulted. If `full' is _not_ set, the implication is that
598 these parameters are not going to be used for _generating_ a puzzle; so
599 parameters which can't even sensibly _describe_ a valid puzzle should
600 still be faulted, but parameters which only affect puzzle generation
603 (The `full' option makes a difference when parameter combinations are
604 non-orthogonal. For example, Net has a boolean option controlling
605 whether it enforces a unique solution; it turns out that it's impossible
606 to generate a uniquely soluble puzzle with wrapping walls and width
607 2, so validate_params() will complain if you ask for one. However,
608 if the user had just been playing a unique wrapping puzzle of a more
609 sensible width, and then pastes in a game ID acquired from somebody else
610 which happens to describe a _non_-unique wrapping width-2 puzzle, then
611 validate_params() will be passed a `game_params' containing the width
612 and wrapping settings from the new game ID and the uniqueness setting
613 from the old one. This would be faulted, if it weren't for the fact that
614 `full' is not set during this call, so Net ignores the inconsistency.
615 The resulting `game_params' is never subsequently used to generate a
616 puzzle; this is a promise made by the mid-end when it asks for a non-
619 2.4. Handling game descriptions
620 -------------------------------
622 In this section I present the functions that deal with a textual
623 description of a puzzle, i.e. the part that comes after the colon in a
624 descriptive-format game ID.
629 char *(*new_desc)(const game_params *params, random_state *rs,
630 char **aux, int interactive);
632 This function is where all the really hard work gets done. This is
633 the function whose job is to randomly generate a new puzzle, ensuring
634 solubility and uniqueness as appropriate.
636 As input it is given a `game_params' structure and a random state
637 (see section 5.1 for the random number API). It must invent a puzzle
638 instance, encode it in string form, and return a dynamically allocated C
639 string containing that encoding.
641 Additionally, it may return a second dynamically allocated string
642 in `*aux'. (If it doesn't want to, then it can leave that parameter
643 completely alone; it isn't required to set it to NULL, although doing
644 so is harmless.) That string, if present, will be passed to solve()
645 (section 2.7.4) later on; so if the puzzle is generated in such a way
646 that a solution is known, then information about that solution can be
647 saved in `*aux' for solve() to use.
649 The `interactive' parameter should be ignored by almost all puzzles.
650 Its purpose is to distinguish between generating a puzzle within a GUI
651 context for immediate play, and generating a puzzle in a command-line
652 context for saving to be played later. The only puzzle that currently
653 uses this distinction (and, I fervently hope, the only one which will
654 _ever_ need to use it) is Mines, which chooses a random first-click
655 location when generating puzzles non-interactively, but which waits
656 for the user to place the first click when interactive. If you think
657 you have come up with another puzzle which needs to make use of this
658 parameter, please think for at least ten minutes about whether there is
661 Note that game description strings are not required to contain an
662 encoding of parameters such as grid size; a game description is
663 never separated from the `game_params' it was generated with, so any
664 information contained in that structure need not be encoded again in the
667 2.4.2. validate_desc()
668 ----------------------
670 char *(*validate_desc)(const game_params *params, const char *desc);
672 This function is given a game description, and its job is to validate
673 that it describes a puzzle which makes sense.
675 To some extent it's up to the user exactly how far they take the phrase
676 `makes sense'; there are no particularly strict rules about how hard the
677 user is permitted to shoot themself in the foot when typing in a bogus
678 game description by hand. (For example, Rectangles will not verify that
679 the sum of all the numbers in the grid equals the grid's area. So a user
680 could enter a puzzle which was provably not soluble, and the program
681 wouldn't complain; there just wouldn't happen to be any sequence of
682 moves which solved it.)
684 The one non-negotiable criterion is that any game description which
685 makes it through validate_desc() _must not_ subsequently cause a crash
686 or an assertion failure when fed to new_game() and thence to the rest of
689 The return value is NULL on success, or a non-dynamically-allocated C
690 string containing an error message.
695 game_state *(*new_game)(midend *me, const game_params *params,
698 This function takes a game description as input, together with its
699 accompanying `game_params', and constructs a `game_state' describing the
700 initial state of the puzzle. It returns a newly allocated `game_state'
703 Almost all puzzles should ignore the `me' parameter. It is required by
704 Mines, which needs it for later passing to midend_supersede_game_desc()
705 (see section 2.11.2) once the user has placed the first click. I
706 fervently hope that no other puzzle will be awkward enough to require
707 it, so everybody else should ignore it. As with the `interactive'
708 parameter in new_desc() (section 2.4.1), if you think you have a reason
709 to need this parameter, please try very hard to think of an alternative
712 2.5. Handling game states
713 -------------------------
715 This section describes the functions which create and destroy
716 `game_state' structures.
718 (Well, except new_game(), which is in section 2.4.3 instead of under
719 here; but it deals with game descriptions _and_ game states and it had
720 to go in one section or the other.)
725 game_state *(*dup_game)(const game_state *state);
727 This function allocates a new `game_state' structure and initialises it
728 with an exact copy of the information in the one provided as input. It
729 returns a pointer to the new duplicate.
734 void (*free_game)(game_state *state);
736 This function frees a `game_state' structure, and any subsidiary
737 allocations contained within it.
739 2.6. Handling `game_ui'
740 -----------------------
745 game_ui *(*new_ui)(const game_state *state);
747 This function allocates and returns a new `game_ui' structure for
748 playing a particular puzzle. It is passed a pointer to the initial
749 `game_state', in case it needs to refer to that when setting up the
750 initial values for the new game.
755 void (*free_ui)(game_ui *ui);
757 This function frees a `game_ui' structure, and any subsidiary
758 allocations contained within it.
763 char *(*encode_ui)(const game_ui *ui);
765 This function encodes any _important_ data in a `game_ui' structure in
766 string form. It is only called when saving a half-finished game to a
769 It should be used sparingly. Almost all data in a `game_ui' is not
770 important enough to save. The location of the keyboard-controlled
771 cursor, for example, can be reset to a default position on reloading
772 the game without impacting the user experience. If the user should
773 somehow manage to save a game while a mouse drag was in progress, then
774 discarding that mouse drag would be an outright _feature_.
776 A typical thing that _would_ be worth encoding in this function is the
777 Mines death counter: it's in the `game_ui' rather than the `game_state'
778 because it's too important to allow the user to revert it by using Undo,
779 and therefore it's also too important to allow the user to revert it by
780 saving and reloading. (Of course, the user could edit the save file by
781 hand... But if the user is _that_ determined to cheat, they could just
782 as easily modify the game's source.)
787 void (*decode_ui)(game_ui *ui, const char *encoding);
789 This function parses a string previously output by encode_ui(), and
790 writes the decoded data back into the provided `game_ui' structure.
792 2.6.5. changed_state()
793 ----------------------
795 void (*changed_state)(game_ui *ui, const game_state *oldstate,
796 const game_state *newstate);
798 This function is called by the mid-end whenever the current game state
799 changes, for any reason. Those reasons include:
801 - a fresh move being made by interpret_move() and execute_move()
803 - a solve operation being performed by solve() and execute_move()
805 - the user moving back and forth along the undo list by means of the
806 Undo and Redo operations
808 - the user selecting Restart to go back to the initial game state.
810 The job of changed_state() is to update the `game_ui' for consistency
811 with the new game state, if any update is necessary. For example,
812 Same Game stores data about the currently selected tile group in its
813 `game_ui', and this data is intrinsically related to the game state it
814 was derived from. So it's very likely to become invalid when the game
815 state changes; thus, Same Game's changed_state() function clears the
816 current selection whenever it is called.
818 When anim_length() or flash_length() are called, you can be sure that
819 there has been a previous call to changed_state(). So changed_state()
820 can set up data in the `game_ui' which will be read by anim_length() and
821 flash_length(), and those functions will not have to worry about being
822 called without the data having been initialised.
827 This section describes the functions which actually make moves in
828 the game: that is, the functions which process user input and end up
829 producing new `game_state's.
831 2.7.1. interpret_move()
832 -----------------------
834 char *(*interpret_move)(const game_state *state, game_ui *ui,
835 const game_drawstate *ds,
836 int x, int y, int button);
838 This function receives user input and processes it. Its input parameters
839 are the current `game_state', the current `game_ui' and the current
840 `game_drawstate', plus details of the input event. `button' is either
841 an ASCII value or a special code (listed below) indicating an arrow or
842 function key or a mouse event; when `button' is a mouse event, `x' and
843 `y' contain the pixel coordinates of the mouse pointer relative to the
844 top left of the puzzle's drawing area.
846 (The pointer to the `game_drawstate' is marked `const', because
847 `interpret_move' should not write to it. The normal use of that pointer
848 will be to read the game's tile size parameter in order to divide mouse
851 interpret_move() may return in three different ways:
853 - Returning NULL indicates that no action whatsoever occurred in
854 response to the input event; the puzzle was not interested in it at
857 - Returning the empty string ("") indicates that the input event has
858 resulted in a change being made to the `game_ui' which will require
859 a redraw of the game window, but that no actual _move_ was made
860 (i.e. no new `game_state' needs to be created).
862 - Returning anything else indicates that a move was made and that
863 a new `game_state' must be created. However, instead of actually
864 constructing a new `game_state' itself, this function is required to
865 return a string description of the details of the move. This string
866 will be passed to execute_move() (section 2.7.2) to actually create
867 the new `game_state'. (Encoding moves as strings in this way means
868 that the mid-end can keep the strings as well as the game states,
869 and the strings can be written to disk when saving the game and fed
870 to execute_move() again on reloading.)
872 The return value from interpret_move() is expected to be dynamically
873 allocated if and only if it is not either NULL _or_ the empty string.
875 After this function is called, the back end is permitted to rely on some
876 subsequent operations happening in sequence:
878 - execute_move() will be called to convert this move description into
881 - changed_state() will be called with the new `game_state'.
883 This means that if interpret_move() needs to do updates to the `game_ui'
884 which are easier to perform by referring to the new `game_state', it can
885 safely leave them to be done in changed_state() and not worry about them
888 (Note, however, that execute_move() may _also_ be called in other
889 circumstances. It is only interpret_move() which can rely on a
890 subsequent call to changed_state().)
892 The special key codes supported by this function are:
894 LEFT_BUTTON, MIDDLE_BUTTON, RIGHT_BUTTON
896 Indicate that one of the mouse buttons was pressed down.
898 LEFT_DRAG, MIDDLE_DRAG, RIGHT_DRAG
900 Indicate that the mouse was moved while one of the mouse buttons was
901 still down. The mid-end guarantees that when one of these events is
902 received, it will always have been preceded by a button-down event
903 (and possibly other drag events) for the same mouse button, and no
904 event involving another mouse button will have appeared in between.
906 LEFT_RELEASE, MIDDLE_RELEASE, RIGHT_RELEASE
908 Indicate that a mouse button was released. The mid-end guarantees
909 that when one of these events is received, it will always have been
910 preceded by a button-down event (and possibly some drag events) for
911 the same mouse button, and no event involving another mouse button
912 will have appeared in between.
914 CURSOR_UP, CURSOR_DOWN, CURSOR_LEFT, CURSOR_RIGHT
916 Indicate that an arrow key was pressed.
920 On platforms which have a prominent `select' button alongside their
921 cursor keys, indicates that that button was pressed.
923 In addition, there are some modifiers which can be bitwise-ORed into the
928 These indicate that the Control or Shift key was pressed alongside
929 the key. They only apply to the cursor keys, not to mouse buttons or
934 This applies to some ASCII values, and indicates that the key code
935 was input via the numeric keypad rather than the main keyboard. Some
936 puzzles may wish to treat this differently (for example, a puzzle
937 might want to use the numeric keypad as an eight-way directional
938 pad), whereas others might not (a game involving numeric input
939 probably just wants to treat the numeric keypad as numbers).
943 This mask is the bitwise OR of all the available modifiers; you can
944 bitwise-AND with ~MOD_MASK to strip all the modifiers off any input
947 2.7.2. execute_move()
948 ---------------------
950 game_state *(*execute_move)(const game_state *state, char *move);
952 This function takes an input `game_state' and a move string as output
953 from interpret_move(). It returns a newly allocated `game_state' which
954 contains the result of applying the specified move to the input game
957 This function may return NULL if it cannot parse the move string (and
958 this is definitely preferable to crashing or failing an assertion, since
959 one way this can happen is if loading a corrupt save file). However, it
960 must not return NULL for any move string that really was output from
961 interpret_move(): this is punishable by assertion failure in the mid-
969 This boolean field is set to TRUE if the game's solve() function does
970 something. If it's set to FALSE, the game will not even offer the
976 char *(*solve)(const game_state *orig, const game_state *curr,
977 const char *aux, char **error);
979 This function is called when the user selects the `Solve' option from
982 It is passed two input game states: `orig' is the game state from the
983 very start of the puzzle, and `curr' is the current one. (Different
984 games find one or other or both of these convenient.) It is also passed
985 the `aux' string saved by new_desc() (section 2.4.1), in case that
986 encodes important information needed to provide the solution.
988 If this function is unable to produce a solution (perhaps, for example,
989 the game has no in-built solver so it can only solve puzzles it invented
990 internally and has an `aux' string for) then it may return NULL. If it
991 does this, it must also set `*error' to an error message to be presented
992 to the user (such as `Solution not known for this puzzle'); that error
993 message is not expected to be dynamically allocated.
995 If this function _does_ produce a solution, it returns a move string
996 suitable for feeding to execute_move() (section 2.7.2). Like a (non-
997 empty) string returned from interpret_move(), the returned string should
998 be dynamically allocated.
1000 2.8. Drawing the game graphics
1001 ------------------------------
1003 This section discusses the back end functions that deal with drawing.
1005 2.8.1. new_drawstate()
1006 ----------------------
1008 game_drawstate *(*new_drawstate)(drawing *dr,
1009 const game_state *state);
1011 This function allocates and returns a new `game_drawstate' structure for
1012 drawing a particular puzzle. It is passed a pointer to a `game_state',
1013 in case it needs to refer to that when setting up any initial data.
1015 This function may not rely on the puzzle having been newly started; a
1016 new draw state can be constructed at any time if the front end requests
1017 a forced redraw. For games like Pattern, in which initial game states
1018 are much simpler than general ones, this might be important to keep in
1021 The parameter `dr' is a drawing object (see chapter 3) which the
1022 function might need to use to allocate blitters. (However, this isn't
1023 recommended; it's usually more sensible to wait to allocate a blitter
1024 until set_size() is called, because that way you can tailor it to the
1025 scale at which the puzzle is being drawn.)
1027 2.8.2. free_drawstate()
1028 -----------------------
1030 void (*free_drawstate)(drawing *dr, game_drawstate *ds);
1032 This function frees a `game_drawstate' structure, and any subsidiary
1033 allocations contained within it.
1035 The parameter `dr' is a drawing object (see chapter 3), which might be
1036 required if you are freeing a blitter.
1038 2.8.3. `preferred_tilesize'
1039 ---------------------------
1041 int preferred_tilesize;
1043 Each game is required to define a single integer parameter which
1044 expresses, in some sense, the scale at which it is drawn. This is
1045 described in the APIs as `tilesize', since most puzzles are on a
1046 square (or possibly triangular or hexagonal) grid and hence a sensible
1047 interpretation of this parameter is to define it as the size of one grid
1048 tile in pixels; however, there's no actual requirement that the `tile
1049 size' be proportional to the game window size. Window size is required
1050 to increase monotonically with `tile size', however.
1052 The data element `preferred_tilesize' indicates the tile size which
1053 should be used in the absence of a good reason to do otherwise (such as
1054 the screen being too small, or the user explicitly requesting a resize
1055 if that ever gets implemented).
1057 2.8.4. compute_size()
1058 ---------------------
1060 void (*compute_size)(const game_params *params, int tilesize,
1063 This function is passed a `game_params' structure and a tile size. It
1064 returns, in `*x' and `*y', the size in pixels of the drawing area that
1065 would be required to render a puzzle with those parameters at that tile
1071 void (*set_size)(drawing *dr, game_drawstate *ds,
1072 const game_params *params, int tilesize);
1074 This function is responsible for setting up a `game_drawstate' to draw
1075 at a given tile size. Typically this will simply involve copying the
1076 supplied `tilesize' parameter into a `tilesize' field inside the draw
1077 state; for some more complex games it might also involve setting up
1078 other dimension fields, or possibly allocating a blitter (see section
1081 The parameter `dr' is a drawing object (see chapter 3), which is
1082 required if a blitter needs to be allocated.
1084 Back ends may assume (and may enforce by assertion) that this function
1085 will be called at most once for any `game_drawstate'. If a puzzle needs
1086 to be redrawn at a different size, the mid-end will create a fresh
1092 float *(*colours)(frontend *fe, int *ncolours);
1094 This function is responsible for telling the front end what colours the
1095 puzzle will need to draw itself.
1097 It returns the number of colours required in `*ncolours', and the return
1098 value from the function itself is a dynamically allocated array of three
1099 times that many `float's, containing the red, green and blue components
1100 of each colour respectively as numbers in the range [0,1].
1102 The second parameter passed to this function is a front end handle.
1103 The only things it is permitted to do with this handle are to call the
1104 front-end function called frontend_default_colour() (see section 4.40)
1105 or the utility function called game_mkhighlight() (see section 5.4.7).
1106 (The latter is a wrapper on the former, so front end implementors only
1107 need to provide frontend_default_colour().) This allows colours() to
1108 take local configuration into account when deciding on its own colour
1109 allocations. Most games use the front end's default colour as their
1110 background, apart from a few which depend on drawing relief highlights
1111 so they adjust the background colour if it's too light for highlights to
1114 Note that the colours returned from this function are for _drawing_,
1115 not for printing. Printing has an entirely different colour allocation
1118 2.8.7. anim_length()
1119 --------------------
1121 float (*anim_length)(const game_state *oldstate,
1122 const game_state *newstate,
1123 int dir, game_ui *ui);
1125 This function is called when a move is made, undone or redone. It is
1126 given the old and the new `game_state', and its job is to decide whether
1127 the transition between the two needs to be animated or can be instant.
1129 `oldstate' is the state that was current until this call; `newstate'
1130 is the state that will be current after it. `dir' specifies the
1131 chronological order of those states: if it is positive, then the
1132 transition is the result of a move or a redo (and so `newstate' is the
1133 later of the two moves), whereas if it is negative then the transition
1134 is the result of an undo (so that `newstate' is the _earlier_ move).
1136 If this function decides the transition should be animated, it returns
1137 the desired length of the animation in seconds. If not, it returns zero.
1139 State changes as a result of a Restart operation are never animated; the
1140 mid-end will handle them internally and never consult this function at
1141 all. State changes as a result of Solve operations are also not animated
1142 by default, although you can change this for a particular game by
1143 setting a flag in `flags' (section 2.10.7).
1145 The function is also passed a pointer to the local `game_ui'. It may
1146 refer to information in here to help with its decision (see section
1147 6.3.7 for an example of this), and/or it may _write_ information about
1148 the nature of the animation which will be read later by redraw().
1150 When this function is called, it may rely on changed_state() having been
1151 called previously, so if anim_length() needs to refer to information in
1152 the `game_ui', then changed_state() is a reliable place to have set that
1155 Move animations do not inhibit further input events. If the user
1156 continues playing before a move animation is complete, the animation
1157 will be abandoned and the display will jump straight to the final state.
1159 2.8.8. flash_length()
1160 ---------------------
1162 float (*flash_length)(const game_state *oldstate,
1163 const game_state *newstate,
1164 int dir, game_ui *ui);
1166 This function is called when a move is completed. (`Completed'
1167 means that not only has the move been made, but any animation which
1168 accompanied it has finished.) It decides whether the transition from
1169 `oldstate' to `newstate' merits a `flash'.
1171 A flash is much like a move animation, but it is _not_ interrupted by
1172 further user interface activity; it runs to completion in parallel with
1173 whatever else might be going on on the display. The only thing which
1174 will rush a flash to completion is another flash.
1176 The purpose of flashes is to indicate that the game has been completed.
1177 They were introduced as a separate concept from move animations because
1178 of Net: the habit of most Net players (and certainly me) is to rotate a
1179 tile into place and immediately lock it, then move on to another tile.
1180 When you make your last move, at the instant the final tile is rotated
1181 into place the screen starts to flash to indicate victory - but if you
1182 then press the lock button out of habit, then the move animation is
1183 cancelled, and the victory flash does not complete. (And if you _don't_
1184 press the lock button, the completed grid will look untidy because there
1185 will be one unlocked square.) Therefore, I introduced a specific concept
1186 of a `flash' which is separate from a move animation and can proceed in
1187 parallel with move animations and any other display activity, so that
1188 the victory flash in Net is not cancelled by that final locking move.
1190 The input parameters to flash_length() are exactly the same as the ones
1193 Just like anim_length(), when this function is called, it may rely on
1194 changed_state() having been called previously, so if it needs to refer
1195 to information in the `game_ui' then changed_state() is a reliable place
1196 to have set that information up.
1198 (Some games use flashes to indicate defeat as well as victory; Mines,
1199 for example, flashes in a different colour when you tread on a mine from
1200 the colour it uses when you complete the game. In order to achieve this,
1201 its flash_length() function has to store a flag in the `game_ui' to
1202 indicate which flash type is required.)
1207 int (*status)(const game_state *state);
1209 This function returns a status value indicating whether the current game
1210 is still in play, or has been won, or has been conclusively lost. The
1211 mid-end uses this to implement midend_status() (section 4.27).
1213 The return value should be +1 if the game has been successfully solved.
1214 If the game has been lost in a situation where further play is unlikely,
1215 the return value should be -1. If neither is true (so play is still
1216 ongoing), return zero.
1218 Front ends may wish to use a non-zero status as a cue to proactively
1219 offer the option of starting a new game. Therefore, back ends should
1220 not return -1 if the game has been _technically_ lost but undoing and
1221 continuing is still a realistic possibility.
1223 (For instance, games with hidden information such as Guess or Mines
1224 might well return a non-zero status whenever they reveal the solution,
1225 whether or not the player guessed it correctly, on the grounds that a
1226 player would be unlikely to hide the solution and continue playing after
1227 the answer was spoiled. On the other hand, games where you can merely
1228 get into a dead end such as Same Game or Inertia might choose to return
1229 0 in that situation, on the grounds that the player would quite likely
1230 press Undo and carry on playing.)
1235 void (*redraw)(drawing *dr, game_drawstate *ds,
1236 const game_state *oldstate,
1237 const game_state *newstate,
1238 int dir, const game_ui *ui,
1239 float anim_time, float flash_time);
1241 This function is responsible for actually drawing the contents of
1242 the game window, and for redrawing every time the game state or the
1245 The parameter `dr' is a drawing object which may be passed to the
1246 drawing API functions (see chapter 3 for documentation of the drawing
1247 API). This function may not save `dr' and use it elsewhere; it must only
1248 use it for calling back to the drawing API functions within its own
1251 `ds' is the local `game_drawstate', of course, and `ui' is the local
1254 `newstate' is the semantically-current game state, and is always non-
1255 NULL. If `oldstate' is also non-NULL, it means that a move has recently
1256 been made and the game is still in the process of displaying an
1257 animation linking the old and new states; in this situation, `anim_time'
1258 will give the length of time (in seconds) that the animation has already
1259 been running. If `oldstate' is NULL, then `anim_time' is unused (and
1260 will hopefully be set to zero to avoid confusion).
1262 `flash_time', if it is is non-zero, denotes that the game is in the
1263 middle of a flash, and gives the time since the start of the flash. See
1264 section 2.8.8 for general discussion of flashes.
1266 The very first time this function is called for a new `game_drawstate',
1267 it is expected to redraw the _entire_ drawing area. Since this often
1268 involves drawing visual furniture which is never subsequently altered,
1269 it is often simplest to arrange this by having a special `first time'
1270 flag in the draw state, and resetting it after the first redraw.
1272 When this function (or any subfunction) calls the drawing API, it is
1273 expected to pass colour indices which were previously defined by the
1276 2.9. Printing functions
1277 -----------------------
1279 This section discusses the back end functions that deal with printing
1280 puzzles out on paper.
1287 This flag is set to TRUE if the puzzle is capable of printing itself
1288 on paper. (This makes sense for some puzzles, such as Solo, which can
1289 be filled in with a pencil. Other puzzles, such as Twiddle, inherently
1290 involve moving things around and so would not make sense to print.)
1292 If this flag is FALSE, then the functions print_size() and print() will
1295 2.9.2. `can_print_in_colour'
1296 ----------------------------
1298 int can_print_in_colour;
1300 This flag is set to TRUE if the puzzle is capable of printing itself
1301 differently when colour is available. For example, Map can actually
1302 print coloured regions in different _colours_ rather than resorting to
1305 If the `can_print' flag is FALSE, then this flag will be ignored.
1310 void (*print_size)(const game_params *params, float *x, float *y);
1312 This function is passed a `game_params' structure and a tile size. It
1313 returns, in `*x' and `*y', the preferred size in _millimetres_ of that
1314 puzzle if it were to be printed out on paper.
1316 If the `can_print' flag is FALSE, this function will never be called.
1321 void (*print)(drawing *dr, const game_state *state, int tilesize);
1323 This function is called when a puzzle is to be printed out on paper. It
1324 should use the drawing API functions (see chapter 3) to print itself.
1326 This function is separate from redraw() because it is often very
1329 - The printing function may not depend on pixel accuracy, since
1330 printer resolution is variable. Draw as if your canvas had infinite
1333 - The printing function sometimes needs to display things in a
1334 completely different style. Net, for example, is very different as
1335 an on-screen puzzle and as a printed one.
1337 - The printing function is often much simpler since it has no need to
1338 deal with repeated partial redraws.
1340 However, there's no reason the printing and redraw functions can't share
1341 some code if they want to.
1343 When this function (or any subfunction) calls the drawing API, the
1344 colour indices it passes should be colours which have been allocated by
1345 the print_*_colour() functions within this execution of print(). This is
1346 very different from the fixed small number of colours used in redraw(),
1347 because printers do not have a limitation on the total number of colours
1348 that may be used. Some puzzles' printing functions might wish to
1349 allocate only one `ink' colour and use it for all drawing; others might
1350 wish to allocate _more_ colours than are used on screen.
1352 One possible colour policy worth mentioning specifically is that a
1353 puzzle's printing function might want to allocate the _same_ colour
1354 indices as are used by the redraw function, so that code shared between
1355 drawing and printing does not have to keep switching its colour indices.
1356 In order to do this, the simplest thing is to make use of the fact that
1357 colour indices returned from print_*_colour() are guaranteed to be in
1358 increasing order from zero. So if you have declared an `enum' defining
1359 three colours COL_BACKGROUND, COL_THIS and COL_THAT, you might then
1363 c = print_mono_colour(dr, 1); assert(c == COL_BACKGROUND);
1364 c = print_mono_colour(dr, 0); assert(c == COL_THIS);
1365 c = print_mono_colour(dr, 0); assert(c == COL_THAT);
1367 If the `can_print' flag is FALSE, this function will never be called.
1372 2.10.1. `can_format_as_text_ever'
1373 ---------------------------------
1375 int can_format_as_text_ever;
1377 This boolean field is TRUE if the game supports formatting a game state
1378 as ASCII text (typically ASCII art) for copying to the clipboard and
1379 pasting into other applications. If it is FALSE, front ends will not
1380 offer the `Copy' command at all.
1382 If this field is TRUE, the game does not necessarily have to support
1383 text formatting for _all_ games: e.g. a game which can be played on
1384 a square grid or a triangular one might only support copy and paste
1385 for the former, because triangular grids in ASCII art are just too
1388 If this field is FALSE, the functions can_format_as_text_now() (section
1389 2.10.2) and text_format() (section 2.10.3) are never called.
1391 2.10.2. `can_format_as_text_now()'
1392 ----------------------------------
1394 int (*can_format_as_text_now)(const game_params *params);
1396 This function is passed a `game_params' and returns a boolean, which is
1397 TRUE if the game can support ASCII text output for this particular game
1398 type. If it returns FALSE, front ends will grey out or otherwise disable
1401 Games may enable and disable the copy-and-paste function for different
1402 game _parameters_, but are currently constrained to return the same
1403 answer from this function for all game _states_ sharing the same
1404 parameters. In other words, the `Copy' function may enable or disable
1405 itself when the player changes game preset, but will never change during
1406 play of a single game or when another game of exactly the same type is
1409 This function should not take into account aspects of the game
1410 parameters which are not encoded by encode_params() (section 2.3.3)
1411 when the `full' parameter is set to FALSE. Such parameters will not
1412 necessarily match up between a call to this function and a subsequent
1413 call to text_format() itself. (For instance, game _difficulty_ should
1414 not affect whether the game can be copied to the clipboard. Only the
1415 actual visible _shape_ of the game can affect that.)
1417 2.10.3. text_format()
1418 ---------------------
1420 char *(*text_format)(const game_state *state);
1422 This function is passed a `game_state', and returns a newly allocated C
1423 string containing an ASCII representation of that game state. It is used
1424 to implement the `Copy' operation in many front ends.
1426 This function will only ever be called if the back end field
1427 `can_format_as_text_ever' (section 2.10.1) is TRUE _and_ the function
1428 can_format_as_text_now() (section 2.10.2) has returned TRUE for the
1429 currently selected game parameters.
1431 The returned string may contain line endings (and will probably want
1432 to), using the normal C internal `\n' convention. For consistency
1433 between puzzles, all multi-line textual puzzle representations should
1434 _end_ with a newline as well as containing them internally. (There are
1435 currently no puzzles which have a one-line ASCII representation, so
1436 there's no precedent yet for whether that should come with a newline or
1439 2.10.4. wants_statusbar
1440 -----------------------
1442 int wants_statusbar;
1444 This boolean field is set to TRUE if the puzzle has a use for a textual
1445 status line (to display score, completion status, currently active
1453 This boolean field is TRUE if the puzzle is time-critical. If so, the
1454 mid-end will maintain a game timer while the user plays.
1456 If this field is FALSE, then timing_state() will never be called and
1457 need not do anything.
1459 2.10.6. timing_state()
1460 ----------------------
1462 int (*timing_state)(const game_state *state, game_ui *ui);
1464 This function is passed the current `game_state' and the local
1465 `game_ui'; it returns TRUE if the game timer should currently be
1468 A typical use for the `game_ui' in this function is to note when the
1469 game was first completed (by setting a flag in changed_state() - see
1470 section 2.6.5), and freeze the timer thereafter so that the user can
1471 undo back through their solution process without altering their time.
1478 This field contains miscellaneous per-backend flags. It consists of the
1479 bitwise OR of some combination of the following:
1483 Given any x and y from the set {LEFT_BUTTON, MIDDLE_BUTTON,
1484 RIGHT_BUTTON}, this macro evaluates to a bit flag which indicates
1485 that when buttons x and y are both pressed simultaneously, the mid-
1486 end should consider x to have priority. (In the absence of any such
1487 flags, the mid-end will always consider the most recently pressed
1488 button to have priority.)
1492 This flag indicates that moves generated by solve() (section 2.7.4)
1493 are candidates for animation just like any other move. For most
1494 games, solve moves should not be animated, so the mid-end doesn't
1495 even bother calling anim_length() (section 2.8.7), thus saving some
1496 special-case code in each game. On the rare occasion that animated
1497 solve moves are actually required, you can set this flag.
1501 This flag indicates that the puzzle cannot be usefully played
1502 without the use of mouse buttons other than the left one. On some
1503 PDA platforms, this flag is used by the front end to enable right-
1504 button emulation through an appropriate gesture. Note that a puzzle
1505 is not required to set this just because it _uses_ the right button,
1506 but only if its use of the right button is critical to playing the
1507 game. (Slant, for example, uses the right button to cycle through
1508 the three square states in the opposite order from the left button,
1509 and hence can manage fine without it.)
1513 This flag indicates that the puzzle cannot be usefully played
1514 without the use of number-key input. On some PDA platforms it
1515 causes an emulated number pad to appear on the screen. Similarly to
1516 REQUIRE_RBUTTON, a puzzle need not specify this simply if its use of
1517 the number keys is not critical.
1519 2.11. Things a back end may do on its own initiative
1520 ----------------------------------------------------
1522 This section describes a couple of things that a back end may choose
1523 to do by calling functions elsewhere in the program, which would not
1524 otherwise be obvious.
1526 2.11.1. Create a random state
1527 -----------------------------
1529 If a back end needs random numbers at some point during normal play, it
1530 can create a fresh `random_state' by first calling `get_random_seed'
1531 (section 4.36) and then passing the returned seed data to random_new().
1533 This is likely not to be what you want. If a puzzle needs randomness in
1534 the middle of play, it's likely to be more sensible to store some sort
1535 of random state within the `game_state', so that the random numbers are
1536 tied to the particular game state and hence the player can't simply keep
1537 undoing their move until they get numbers they like better.
1539 This facility is currently used only in Net, to implement the `jumble'
1540 command, which sets every unlocked tile to a new random orientation.
1541 This randomness _is_ a reasonable use of the feature, because it's non-
1542 adversarial - there's no advantage to the user in getting different
1545 2.11.2. Supersede its own game description
1546 ------------------------------------------
1548 In response to a move, a back end is (reluctantly) permitted to call
1549 midend_supersede_game_desc():
1551 void midend_supersede_game_desc(midend *me,
1552 char *desc, char *privdesc);
1554 When the user selects `New Game', the mid-end calls new_desc()
1555 (section 2.4.1) to get a new game description, and (as well as using
1556 that to generate an initial game state) stores it for the save file
1557 and for telling to the user. The function above overwrites that
1558 game description, and also splits it in two. `desc' becomes the new
1559 game description which is provided to the user on request, and is
1560 also the one used to construct a new initial game state if the user
1561 selects `Restart'. `privdesc' is a `private' game description, used to
1562 reconstruct the game's initial state when reloading.
1564 The distinction between the two, as well as the need for this function
1565 at all, comes from Mines. Mines begins with a blank grid and no
1566 idea of where the mines actually are; new_desc() does almost no
1567 work in interactive mode, and simply returns a string encoding the
1568 `random_state'. When the user first clicks to open a tile, _then_ Mines
1569 generates the mine positions, in such a way that the game is soluble
1570 from that starting point. Then it uses this function to supersede the
1571 random-state game description with a proper one. But it needs two: one
1572 containing the initial click location (because that's what you want to
1573 happen if you restart the game, and also what you want to send to a
1574 friend so that they play _the same game_ as you), and one without the
1575 initial click location (because when you save and reload the game, you
1576 expect to see the same blank initial state as you had before saving).
1578 I should stress again that this function is a horrid hack. Nobody should
1579 use it if they're not Mines; if you think you need to use it, think
1580 again repeatedly in the hope of finding a better way to do whatever it
1581 was you needed to do.
1586 The back end function redraw() (section 2.8.10) is required to draw
1587 the puzzle's graphics on the window's drawing area, or on paper if the
1588 puzzle is printable. To do this portably, it is provided with a drawing
1589 API allowing it to talk directly to the front end. In this chapter I
1590 document that API, both for the benefit of back end authors trying to
1591 use it and for front end authors trying to implement it.
1593 The drawing API as seen by the back end is a collection of global
1594 functions, each of which takes a pointer to a `drawing' structure (a
1595 `drawing object'). These objects are supplied as parameters to the back
1596 end's redraw() and print() functions.
1598 In fact these global functions are not implemented directly by the front
1599 end; instead, they are implemented centrally in `drawing.c' and form a
1600 small piece of middleware. The drawing API as supplied by the front end
1601 is a structure containing a set of function pointers, plus a `void *'
1602 handle which is passed to each of those functions. This enables a single
1603 front end to switch between multiple implementations of the drawing API
1604 if necessary. For example, the Windows API supplies a printing mechanism
1605 integrated into the same GDI which deals with drawing in windows, and
1606 therefore the same API implementation can handle both drawing and
1607 printing; but on Unix, the most common way for applications to print
1608 is by producing PostScript output directly, and although it would be
1609 _possible_ to write a single (say) draw_rect() function which checked
1610 a global flag to decide whether to do GTK drawing operations or output
1611 PostScript to a file, it's much nicer to have two separate functions and
1612 switch between them as appropriate.
1614 When drawing, the puzzle window is indexed by pixel coordinates, with
1615 the top left pixel defined as (0,0) and the bottom right pixel (w-1,h-
1616 1), where `w' and `h' are the width and height values returned by the
1617 back end function compute_size() (section 2.8.4).
1619 When printing, the puzzle's print area is indexed in exactly the same
1620 way (with an arbitrary tile size provided by the printing module
1621 `printing.c'), to facilitate sharing of code between the drawing and
1622 printing routines. However, when printing, puzzles may no longer assume
1623 that the coordinate unit has any relationship to a pixel; the printer's
1624 actual resolution might very well not even be known at print time, so
1625 the coordinate unit might be smaller or larger than a pixel. Puzzles'
1626 print functions should restrict themselves to drawing geometric shapes
1627 rather than fiddly pixel manipulation.
1629 _Puzzles' redraw functions may assume that the surface they draw on is
1630 persistent_. It is the responsibility of every front end to preserve
1631 the puzzle's window contents in the face of GUI window expose issues
1632 and similar. It is not permissible to request that the back end redraw
1633 any part of a window that it has already drawn, unless something has
1634 actually changed as a result of making moves in the puzzle.
1636 Most front ends accomplish this by having the drawing routines draw on a
1637 stored bitmap rather than directly on the window, and copying the bitmap
1638 to the window every time a part of the window needs to be redrawn.
1639 Therefore, it is vitally important that whenever the back end does any
1640 drawing it informs the front end of which parts of the window it has
1641 accessed, and hence which parts need repainting. This is done by calling
1642 draw_update() (section 3.1.11).
1644 Persistence of old drawing is convenient. However, a puzzle should be
1645 very careful about how it updates its drawing area. The problem is that
1646 some front ends do anti-aliased drawing: rather than simply choosing
1647 between leaving each pixel untouched or painting it a specified colour,
1648 an antialiased drawing function will _blend_ the original and new
1649 colours in pixels at a figure's boundary according to the proportion of
1650 the pixel occupied by the figure (probably modified by some heuristic
1651 fudge factors). All of this produces a smoother appearance for curves
1654 An unfortunate effect of drawing an anti-aliased figure repeatedly
1655 is that the pixels around the figure's boundary come steadily more
1656 saturated with `ink' and the boundary appears to `spread out'. Worse,
1657 redrawing a figure in a different colour won't fully paint over the old
1658 boundary pixels, so the end result is a rather ugly smudge.
1660 A good strategy to avoid unpleasant anti-aliasing artifacts is to
1661 identify a number of rectangular areas which need to be redrawn, clear
1662 them to the background colour, and then redraw their contents from
1663 scratch, being careful all the while not to stray beyond the boundaries
1664 of the original rectangles. The clip() function (section 3.1.9) comes in
1665 very handy here. Games based on a square grid can often do this fairly
1666 easily. Other games may need to be somewhat more careful. For example,
1667 Loopy's redraw function first identifies portions of the display which
1668 need to be updated. Then, if the changes are fairly well localised, it
1669 clears and redraws a rectangle containing each changed area. Otherwise,
1670 it gives up and redraws the entire grid from scratch.
1672 It is possible to avoid clearing to background and redrawing from
1673 scratch if one is very careful about which drawing functions one
1674 uses: if a function is documented as not anti-aliasing under some
1675 circumstances, you can rely on each pixel in a drawing either being left
1676 entirely alone or being set to the requested colour, with no blending
1679 In the following sections I first discuss the drawing API as seen by the
1680 back end, and then the _almost_ identical function-pointer form seen by
1683 3.1. Drawing API as seen by the back end
1684 ----------------------------------------
1686 This section documents the back-end drawing API, in the form of
1687 functions which take a `drawing' object as an argument.
1692 void draw_rect(drawing *dr, int x, int y, int w, int h,
1695 Draws a filled rectangle in the puzzle window.
1697 `x' and `y' give the coordinates of the top left pixel of the rectangle.
1698 `w' and `h' give its width and height. Thus, the horizontal extent of
1699 the rectangle runs from `x' to `x+w-1' inclusive, and the vertical
1700 extent from `y' to `y+h-1' inclusive.
1702 `colour' is an integer index into the colours array returned by the back
1703 end function colours() (section 2.8.6).
1705 There is no separate pixel-plotting function. If you want to plot a
1706 single pixel, the approved method is to use draw_rect() with width and
1709 Unlike many of the other drawing functions, this function is guaranteed
1710 to be pixel-perfect: the rectangle will be sharply defined and not anti-
1711 aliased or anything like that.
1713 This function may be used for both drawing and printing.
1715 3.1.2. draw_rect_outline()
1716 --------------------------
1718 void draw_rect_outline(drawing *dr, int x, int y, int w, int h,
1721 Draws an outline rectangle in the puzzle window.
1723 `x' and `y' give the coordinates of the top left pixel of the rectangle.
1724 `w' and `h' give its width and height. Thus, the horizontal extent of
1725 the rectangle runs from `x' to `x+w-1' inclusive, and the vertical
1726 extent from `y' to `y+h-1' inclusive.
1728 `colour' is an integer index into the colours array returned by the back
1729 end function colours() (section 2.8.6).
1731 From a back end perspective, this function may be considered to be part
1732 of the drawing API. However, front ends are not required to implement
1733 it, since it is actually implemented centrally (in misc.c) as a wrapper
1736 This function may be used for both drawing and printing.
1741 void draw_line(drawing *dr, int x1, int y1, int x2, int y2,
1744 Draws a straight line in the puzzle window.
1746 `x1' and `y1' give the coordinates of one end of the line. `x2' and `y2'
1747 give the coordinates of the other end. The line drawn includes both
1750 `colour' is an integer index into the colours array returned by the back
1751 end function colours() (section 2.8.6).
1753 Some platforms may perform anti-aliasing on this function. Therefore,
1754 do not assume that you can erase a line by drawing the same line over
1755 it in the background colour; anti-aliasing might lead to perceptible
1756 ghost artefacts around the vanished line. Horizontal and vertical lines,
1757 however, are pixel-perfect and not anti-aliased.
1759 This function may be used for both drawing and printing.
1761 3.1.4. draw_polygon()
1762 ---------------------
1764 void draw_polygon(drawing *dr, int *coords, int npoints,
1765 int fillcolour, int outlinecolour);
1767 Draws an outlined or filled polygon in the puzzle window.
1769 `coords' is an array of (2*npoints) integers, containing the `x' and `y'
1770 coordinates of `npoints' vertices.
1772 `fillcolour' and `outlinecolour' are integer indices into the colours
1773 array returned by the back end function colours() (section 2.8.6).
1774 `fillcolour' may also be -1 to indicate that the polygon should be
1777 The polygon defined by the specified list of vertices is first filled in
1778 `fillcolour', if specified, and then outlined in `outlinecolour'.
1780 `outlinecolour' may _not_ be -1; it must be a valid colour (and front
1781 ends are permitted to enforce this by assertion). This is because
1782 different platforms disagree on whether a filled polygon should include
1783 its boundary line or not, so drawing _only_ a filled polygon would
1784 have non-portable effects. If you want your filled polygon not to
1785 have a visible outline, you must set `outlinecolour' to the same as
1788 Some platforms may perform anti-aliasing on this function. Therefore, do
1789 not assume that you can erase a polygon by drawing the same polygon over
1790 it in the background colour. Also, be prepared for the polygon to extend
1791 a pixel beyond its obvious bounding box as a result of this; if you
1792 really need it not to do this to avoid interfering with other delicate
1793 graphics, you should probably use clip() (section 3.1.9). You can rely
1794 on horizontal and vertical lines not being anti-aliased.
1796 This function may be used for both drawing and printing.
1798 3.1.5. draw_circle()
1799 --------------------
1801 void draw_circle(drawing *dr, int cx, int cy, int radius,
1802 int fillcolour, int outlinecolour);
1804 Draws an outlined or filled circle in the puzzle window.
1806 `cx' and `cy' give the coordinates of the centre of the circle. `radius'
1807 gives its radius. The total horizontal pixel extent of the circle is
1808 from `cx-radius+1' to `cx+radius-1' inclusive, and the vertical extent
1809 similarly around `cy'.
1811 `fillcolour' and `outlinecolour' are integer indices into the colours
1812 array returned by the back end function colours() (section 2.8.6).
1813 `fillcolour' may also be -1 to indicate that the circle should be
1816 The circle is first filled in `fillcolour', if specified, and then
1817 outlined in `outlinecolour'.
1819 `outlinecolour' may _not_ be -1; it must be a valid colour (and front
1820 ends are permitted to enforce this by assertion). This is because
1821 different platforms disagree on whether a filled circle should include
1822 its boundary line or not, so drawing _only_ a filled circle would
1823 have non-portable effects. If you want your filled circle not to
1824 have a visible outline, you must set `outlinecolour' to the same as
1827 Some platforms may perform anti-aliasing on this function. Therefore, do
1828 not assume that you can erase a circle by drawing the same circle over
1829 it in the background colour. Also, be prepared for the circle to extend
1830 a pixel beyond its obvious bounding box as a result of this; if you
1831 really need it not to do this to avoid interfering with other delicate
1832 graphics, you should probably use clip() (section 3.1.9).
1834 This function may be used for both drawing and printing.
1836 3.1.6. draw_thick_line()
1837 ------------------------
1839 void draw_thick_line(drawing *dr, float thickness,
1840 float x1, float y1, float x2, float y2,
1843 Draws a line in the puzzle window, giving control over the line's
1846 `x1' and `y1' give the coordinates of one end of the line. `x2' and `y2'
1847 give the coordinates of the other end. `thickness' gives the thickness
1848 of the line, in pixels.
1850 Note that the coordinates and thickness are floating-point: the
1851 continuous coordinate system is in effect here. It's important to be
1852 able to address points with better-than-pixel precision in this case,
1853 because one can't otherwise properly express the endpoints of lines with
1854 both odd and even thicknesses.
1856 Some platforms may perform anti-aliasing on this function. The precise
1857 pixels affected by a thick-line drawing operation may vary between
1858 platforms, and no particular guarantees are provided. Indeed, even
1859 horizontal or vertical lines may be anti-aliased.
1861 This function may be used for both drawing and printing.
1866 void draw_text(drawing *dr, int x, int y, int fonttype,
1867 int fontsize, int align, int colour, char *text);
1869 Draws text in the puzzle window.
1871 `x' and `y' give the coordinates of a point. The relation of this point
1872 to the location of the text is specified by `align', which is a bitwise
1873 OR of horizontal and vertical alignment flags:
1877 Indicates that `y' is aligned with the baseline of the text.
1881 Indicates that `y' is aligned with the vertical centre of the
1882 text. (In fact, it's aligned with the vertical centre of normal
1883 _capitalised_ text: displaying two pieces of text with ALIGN_VCENTRE
1884 at the same y-coordinate will cause their baselines to be aligned
1885 with one another, even if one is an ascender and the other a
1890 Indicates that `x' is aligned with the left-hand end of the text.
1894 Indicates that `x' is aligned with the horizontal centre of the
1899 Indicates that `x' is aligned with the right-hand end of the text.
1901 `fonttype' is either FONT_FIXED or FONT_VARIABLE, for a monospaced
1902 or proportional font respectively. (No more detail than that may be
1903 specified; it would only lead to portability issues between different
1906 `fontsize' is the desired size, in pixels, of the text. This size
1907 corresponds to the overall point size of the text, not to any internal
1908 dimension such as the cap-height.
1910 `colour' is an integer index into the colours array returned by the back
1911 end function colours() (section 2.8.6).
1913 This function may be used for both drawing and printing.
1915 The character set used to encode the text passed to this function is
1916 specified _by the drawing object_, although it must be a superset of
1917 ASCII. If a puzzle wants to display text that is not contained in ASCII,
1918 it should use the text_fallback() function (section 3.1.8) to query the
1919 drawing object for an appropriate representation of the characters it
1922 3.1.8. text_fallback()
1923 ----------------------
1925 char *text_fallback(drawing *dr, const char *const *strings,
1928 This function is used to request a translation of UTF-8 text into
1929 whatever character encoding is expected by the drawing object's
1930 implementation of draw_text().
1932 The input is a list of strings encoded in UTF-8: nstrings gives the
1933 number of strings in the list, and strings[0], strings[1], ...,
1934 strings[nstrings-1] are the strings themselves.
1936 The returned string (which is dynamically allocated and must be freed
1937 when finished with) is derived from the first string in the list that
1938 the drawing object expects to be able to display reliably; it will
1939 consist of that string translated into the character set expected by
1942 Drawing implementations are not required to handle anything outside
1943 ASCII, but are permitted to assume that _some_ string will be
1944 successfully translated. So every call to this function must include
1945 a string somewhere in the list (presumably the last element) which
1946 consists of nothing but ASCII, to be used by any front end which cannot
1947 handle anything else.
1949 For example, if a puzzle wished to display a string including a
1950 multiplication sign (U+00D7 in Unicode, represented by the bytes C3 97
1951 in UTF-8), it might do something like this:
1953 static const char *const times_signs[] = { "\xC3\x97", "x" };
1954 char *times_sign = text_fallback(dr, times_signs, 2);
1955 sprintf(buffer, "%d%s%d", width, times_sign, height);
1956 draw_text(dr, x, y, font, size, align, colour, buffer);
1959 which would draw a string with a times sign in the middle on platforms
1960 that support it, and fall back to a simple ASCII `x' where there was no
1966 void clip(drawing *dr, int x, int y, int w, int h);
1968 Establishes a clipping rectangle in the puzzle window.
1970 `x' and `y' give the coordinates of the top left pixel of the clipping
1971 rectangle. `w' and `h' give its width and height. Thus, the horizontal
1972 extent of the rectangle runs from `x' to `x+w-1' inclusive, and the
1973 vertical extent from `y' to `y+h-1' inclusive. (These are exactly the
1974 same semantics as draw_rect().)
1976 After this call, no drawing operation will affect anything outside the
1977 specified rectangle. The effect can be reversed by calling unclip()
1978 (section 3.1.10). The clipping rectangle is pixel-perfect: pixels within
1979 the rectangle are affected as usual by drawing functions; pixels outside
1980 are completely untouched.
1982 Back ends should not assume that a clipping rectangle will be
1983 automatically cleared up by the front end if it's left lying around;
1984 that might work on current front ends, but shouldn't be relied upon.
1985 Always explicitly call unclip().
1987 This function may be used for both drawing and printing.
1992 void unclip(drawing *dr);
1994 Reverts the effect of a previous call to clip(). After this call, all
1995 drawing operations will be able to affect the entire puzzle window
1998 This function may be used for both drawing and printing.
2000 3.1.11. draw_update()
2001 ---------------------
2003 void draw_update(drawing *dr, int x, int y, int w, int h);
2005 Informs the front end that a rectangular portion of the puzzle window
2006 has been drawn on and needs to be updated.
2008 `x' and `y' give the coordinates of the top left pixel of the update
2009 rectangle. `w' and `h' give its width and height. Thus, the horizontal
2010 extent of the rectangle runs from `x' to `x+w-1' inclusive, and the
2011 vertical extent from `y' to `y+h-1' inclusive. (These are exactly the
2012 same semantics as draw_rect().)
2014 The back end redraw function _must_ call this function to report any
2015 changes it has made to the window. Otherwise, those changes may not
2016 become immediately visible, and may then appear at an unpredictable
2017 subsequent time such as the next time the window is covered and re-
2020 This function is only important when drawing. It may be called when
2021 printing as well, but doing so is not compulsory, and has no effect.
2022 (So if you have a shared piece of code between the drawing and printing
2023 routines, that code may safely call draw_update().)
2025 3.1.12. status_bar()
2026 --------------------
2028 void status_bar(drawing *dr, char *text);
2030 Sets the text in the game's status bar to `text'. The text is copied
2031 from the supplied buffer, so the caller is free to deallocate or modify
2032 the buffer after use.
2034 (This function is not exactly a _drawing_ function, but it shares with
2035 the drawing API the property that it may only be called from within the
2036 back end redraw function, so this is as good a place as any to document
2039 The supplied text is filtered through the mid-end for optional rewriting
2040 before being passed on to the front end; the mid-end will prepend the
2041 current game time if the game is timed (and may in future perform other
2042 rewriting if it seems like a good idea).
2044 This function is for drawing only; it must never be called during
2047 3.1.13. Blitter functions
2048 -------------------------
2050 This section describes a group of related functions which save and
2051 restore a section of the puzzle window. This is most commonly used to
2052 implement user interfaces involving dragging a puzzle element around the
2053 window: at the end of each call to redraw(), if an object is currently
2054 being dragged, the back end saves the window contents under that
2055 location and then draws the dragged object, and at the start of the next
2056 redraw() the first thing it does is to restore the background.
2058 The front end defines an opaque type called a `blitter', which is
2059 capable of storing a rectangular area of a specified size.
2061 Blitter functions are for drawing only; they must never be called during
2064 3.1.13.1. blitter_new()
2065 -----------------------
2067 blitter *blitter_new(drawing *dr, int w, int h);
2069 Creates a new blitter object which stores a rectangle of size `w' by `h'
2070 pixels. Returns a pointer to the blitter object.
2072 Blitter objects are best stored in the `game_drawstate'. A good time to
2073 create them is in the set_size() function (section 2.8.5), since it is
2074 at this point that you first know how big a rectangle they will need to
2077 3.1.13.2. blitter_free()
2078 ------------------------
2080 void blitter_free(drawing *dr, blitter *bl);
2082 Disposes of a blitter object. Best called in free_drawstate(). (However,
2083 check that the blitter object is not NULL before attempting to free it;
2084 it is possible that a draw state might be created and freed without ever
2085 having set_size() called on it in between.)
2087 3.1.13.3. blitter_save()
2088 ------------------------
2090 void blitter_save(drawing *dr, blitter *bl, int x, int y);
2092 This is a true drawing API function, in that it may only be called from
2093 within the game redraw routine. It saves a rectangular portion of the
2094 puzzle window into the specified blitter object.
2096 `x' and `y' give the coordinates of the top left corner of the saved
2097 rectangle. The rectangle's width and height are the ones specified when
2098 the blitter object was created.
2100 This function is required to cope and do the right thing if `x' and `y'
2101 are out of range. (The right thing probably means saving whatever part
2102 of the blitter rectangle overlaps with the visible area of the puzzle
2105 3.1.13.4. blitter_load()
2106 ------------------------
2108 void blitter_load(drawing *dr, blitter *bl, int x, int y);
2110 This is a true drawing API function, in that it may only be called from
2111 within the game redraw routine. It restores a rectangular portion of the
2112 puzzle window from the specified blitter object.
2114 `x' and `y' give the coordinates of the top left corner of the rectangle
2115 to be restored. The rectangle's width and height are the ones specified
2116 when the blitter object was created.
2118 Alternatively, you can specify both `x' and `y' as the special value
2119 BLITTER_FROMSAVED, in which case the rectangle will be restored to
2120 exactly where it was saved from. (This is probably what you want to do
2121 almost all the time, if you're using blitters to implement draggable
2124 This function is required to cope and do the right thing if `x' and
2125 `y' (or the equivalent ones saved in the blitter) are out of range.
2126 (The right thing probably means restoring whatever part of the blitter
2127 rectangle overlaps with the visible area of the puzzle window.)
2129 If this function is called on a blitter which had previously been saved
2130 from a partially out-of-range rectangle, then the parts of the saved
2131 bitmap which were not visible at save time are undefined. If the blitter
2132 is restored to a different position so as to make those parts visible,
2133 the effect on the drawing area is undefined.
2135 3.1.14. print_mono_colour()
2136 ---------------------------
2138 int print_mono_colour(drawing *dr, int grey);
2140 This function allocates a colour index for a simple monochrome colour
2143 `grey' must be 0 or 1. If `grey' is 0, the colour returned is black; if
2144 `grey' is 1, the colour is white.
2146 3.1.15. print_grey_colour()
2147 ---------------------------
2149 int print_grey_colour(drawing *dr, float grey);
2151 This function allocates a colour index for a grey-scale colour during
2154 `grey' may be any number between 0 (black) and 1 (white); for example,
2155 0.5 indicates a medium grey.
2157 The chosen colour will be rendered to the limits of the printer's
2158 halftoning capability.
2160 3.1.16. print_hatched_colour()
2161 ------------------------------
2163 int print_hatched_colour(drawing *dr, int hatch);
2165 This function allocates a colour index which does not represent a
2166 literal _colour_. Instead, regions shaded in this colour will be hatched
2167 with parallel lines. The `hatch' parameter defines what type of hatching
2168 should be used in place of this colour:
2172 This colour will be hatched by lines slanting to the right at 45
2177 This colour will be hatched by lines slanting to the left at 45
2182 This colour will be hatched by horizontal lines.
2186 This colour will be hatched by vertical lines.
2190 This colour will be hatched by criss-crossing horizontal and
2195 This colour will be hatched by criss-crossing diagonal lines.
2197 Colours defined to use hatching may not be used for drawing lines or
2198 text; they may only be used for filling areas. That is, they may be
2199 used as the `fillcolour' parameter to draw_circle() and draw_polygon(),
2200 and as the colour parameter to draw_rect(), but may not be used as the
2201 `outlinecolour' parameter to draw_circle() or draw_polygon(), or with
2202 draw_line() or draw_text().
2204 3.1.17. print_rgb_mono_colour()
2205 -------------------------------
2207 int print_rgb_mono_colour(drawing *dr, float r, float g,
2208 float b, float grey);
2210 This function allocates a colour index for a fully specified RGB colour
2213 `r', `g' and `b' may each be anywhere in the range from 0 to 1.
2215 If printing in black and white only, these values will be ignored, and
2216 either pure black or pure white will be used instead, according to the
2217 `grey' parameter. (The fallback colour is the same as the one which
2218 would be allocated by print_mono_colour(grey).)
2220 3.1.18. print_rgb_grey_colour()
2221 -------------------------------
2223 int print_rgb_grey_colour(drawing *dr, float r, float g,
2224 float b, float grey);
2226 This function allocates a colour index for a fully specified RGB colour
2229 `r', `g' and `b' may each be anywhere in the range from 0 to 1.
2231 If printing in black and white only, these values will be ignored, and
2232 a shade of grey given by the `grey' parameter will be used instead.
2233 (The fallback colour is the same as the one which would be allocated by
2234 print_grey_colour(grey).)
2236 3.1.19. print_rgb_hatched_colour()
2237 ----------------------------------
2239 int print_rgb_hatched_colour(drawing *dr, float r, float g,
2240 float b, float hatched);
2242 This function allocates a colour index for a fully specified RGB colour
2245 `r', `g' and `b' may each be anywhere in the range from 0 to 1.
2247 If printing in black and white only, these values will be ignored, and
2248 a form of cross-hatching given by the `hatch' parameter will be used
2249 instead; see section 3.1.16 for the possible values of this parameter.
2250 (The fallback colour is the same as the one which would be allocated by
2251 print_hatched_colour(hatch).)
2253 3.1.20. print_line_width()
2254 --------------------------
2256 void print_line_width(drawing *dr, int width);
2258 This function is called to set the thickness of lines drawn during
2259 printing. It is meaningless in drawing: all lines drawn by draw_line(),
2260 draw_circle and draw_polygon() are one pixel in thickness. However, in
2261 printing there is no clear definition of a pixel and so line widths must
2262 be explicitly specified.
2264 The line width is specified in the usual coordinate system. Note,
2265 however, that it is a hint only: the central printing system may choose
2266 to vary line thicknesses at user request or due to printer capabilities.
2268 3.1.21. print_line_dotted()
2269 ---------------------------
2271 void print_line_dotted(drawing *dr, int dotted);
2273 This function is called to toggle the drawing of dotted lines during
2274 printing. It is not supported during drawing.
2276 The parameter `dotted' is a boolean; TRUE means that future lines drawn
2277 by draw_line(), draw_circle and draw_polygon() will be dotted, and FALSE
2278 means that they will be solid.
2280 Some front ends may impose restrictions on the width of dotted lines.
2281 Asking for a dotted line via this front end will override any line width
2282 request if the front end requires it.
2284 3.2. The drawing API as implemented by the front end
2285 ----------------------------------------------------
2287 This section describes the drawing API in the function-pointer form in
2288 which it is implemented by a front end.
2290 (It isn't only platform-specific front ends which implement this API;
2291 the platform-independent module `ps.c' also provides an implementation
2292 of it which outputs PostScript. Thus, any platform which wants to do PS
2293 printing can do so with minimum fuss.)
2295 The following entries all describe function pointer fields in a
2296 structure called `drawing_api'. Each of the functions takes a `void *'
2297 context pointer, which it should internally cast back to a more useful
2298 type. Thus, a drawing _object_ (`drawing *)' suitable for passing to
2299 the back end redraw or printing functions is constructed by passing a
2300 `drawing_api' and a `void *' to the function drawing_new() (see section
2306 void (*draw_text)(void *handle, int x, int y, int fonttype,
2307 int fontsize, int align, int colour, char *text);
2309 This function behaves exactly like the back end draw_text() function;
2315 void (*draw_rect)(void *handle, int x, int y, int w, int h,
2318 This function behaves exactly like the back end draw_rect() function;
2324 void (*draw_line)(void *handle, int x1, int y1, int x2, int y2,
2327 This function behaves exactly like the back end draw_line() function;
2330 3.2.4. draw_polygon()
2331 ---------------------
2333 void (*draw_polygon)(void *handle, int *coords, int npoints,
2334 int fillcolour, int outlinecolour);
2336 This function behaves exactly like the back end draw_polygon() function;
2339 3.2.5. draw_circle()
2340 --------------------
2342 void (*draw_circle)(void *handle, int cx, int cy, int radius,
2343 int fillcolour, int outlinecolour);
2345 This function behaves exactly like the back end draw_circle() function;
2348 3.2.6. draw_thick_line()
2349 ------------------------
2351 void draw_thick_line(drawing *dr, float thickness,
2352 float x1, float y1, float x2, float y2,
2355 This function behaves exactly like the back end draw_thick_line()
2356 function; see section 3.1.6.
2358 An implementation of this API which doesn't provide high-quality
2359 rendering of thick lines is permitted to define this function pointer
2360 to be NULL. The middleware in drawing.c will notice and provide a low-
2361 quality alternative using draw_polygon().
2363 3.2.7. draw_update()
2364 --------------------
2366 void (*draw_update)(void *handle, int x, int y, int w, int h);
2368 This function behaves exactly like the back end draw_update() function;
2371 An implementation of this API which only supports printing is permitted
2372 to define this function pointer to be NULL rather than bothering to
2373 define an empty function. The middleware in drawing.c will notice and
2379 void (*clip)(void *handle, int x, int y, int w, int h);
2381 This function behaves exactly like the back end clip() function; see
2387 void (*unclip)(void *handle);
2389 This function behaves exactly like the back end unclip() function; see
2392 3.2.10. start_draw()
2393 --------------------
2395 void (*start_draw)(void *handle);
2397 This function is called at the start of drawing. It allows the front end
2398 to initialise any temporary data required to draw with, such as device
2401 Implementations of this API which do not provide drawing services may
2402 define this function pointer to be NULL; it will never be called unless
2403 drawing is attempted.
2408 void (*end_draw)(void *handle);
2410 This function is called at the end of drawing. It allows the front end
2411 to do cleanup tasks such as deallocating device contexts and scheduling
2412 appropriate GUI redraw events.
2414 Implementations of this API which do not provide drawing services may
2415 define this function pointer to be NULL; it will never be called unless
2416 drawing is attempted.
2418 3.2.12. status_bar()
2419 --------------------
2421 void (*status_bar)(void *handle, char *text);
2423 This function behaves exactly like the back end status_bar() function;
2426 Front ends implementing this function need not worry about it
2427 being called repeatedly with the same text; the middleware code in
2428 status_bar() will take care of this.
2430 Implementations of this API which do not provide drawing services may
2431 define this function pointer to be NULL; it will never be called unless
2432 drawing is attempted.
2434 3.2.13. blitter_new()
2435 ---------------------
2437 blitter *(*blitter_new)(void *handle, int w, int h);
2439 This function behaves exactly like the back end blitter_new() function;
2440 see section 3.1.13.1.
2442 Implementations of this API which do not provide drawing services may
2443 define this function pointer to be NULL; it will never be called unless
2444 drawing is attempted.
2446 3.2.14. blitter_free()
2447 ----------------------
2449 void (*blitter_free)(void *handle, blitter *bl);
2451 This function behaves exactly like the back end blitter_free() function;
2452 see section 3.1.13.2.
2454 Implementations of this API which do not provide drawing services may
2455 define this function pointer to be NULL; it will never be called unless
2456 drawing is attempted.
2458 3.2.15. blitter_save()
2459 ----------------------
2461 void (*blitter_save)(void *handle, blitter *bl, int x, int y);
2463 This function behaves exactly like the back end blitter_save() function;
2464 see section 3.1.13.3.
2466 Implementations of this API which do not provide drawing services may
2467 define this function pointer to be NULL; it will never be called unless
2468 drawing is attempted.
2470 3.2.16. blitter_load()
2471 ----------------------
2473 void (*blitter_load)(void *handle, blitter *bl, int x, int y);
2475 This function behaves exactly like the back end blitter_load() function;
2476 see section 3.1.13.4.
2478 Implementations of this API which do not provide drawing services may
2479 define this function pointer to be NULL; it will never be called unless
2480 drawing is attempted.
2485 void (*begin_doc)(void *handle, int pages);
2487 This function is called at the beginning of a printing run. It gives the
2488 front end an opportunity to initialise any required printing subsystem.
2489 It also provides the number of pages in advance.
2491 Implementations of this API which do not provide printing services may
2492 define this function pointer to be NULL; it will never be called unless
2493 printing is attempted.
2495 3.2.18. begin_page()
2496 --------------------
2498 void (*begin_page)(void *handle, int number);
2500 This function is called during printing, at the beginning of each page.
2501 It gives the page number (numbered from 1 rather than 0, so suitable for
2502 use in user-visible contexts).
2504 Implementations of this API which do not provide printing services may
2505 define this function pointer to be NULL; it will never be called unless
2506 printing is attempted.
2508 3.2.19. begin_puzzle()
2509 ----------------------
2511 void (*begin_puzzle)(void *handle, float xm, float xc,
2512 float ym, float yc, int pw, int ph, float wmm);
2514 This function is called during printing, just before printing a single
2515 puzzle on a page. It specifies the size and location of the puzzle on
2518 `xm' and `xc' specify the horizontal position of the puzzle on the page,
2519 as a linear function of the page width. The front end is expected to
2520 multiply the page width by `xm', add `xc' (measured in millimetres), and
2521 use the resulting x-coordinate as the left edge of the puzzle.
2523 Similarly, `ym' and `yc' specify the vertical position of the puzzle as
2524 a function of the page height: the page height times `ym', plus `yc'
2525 millimetres, equals the desired distance from the top of the page to the
2528 (This unwieldy mechanism is required because not all printing systems
2529 can communicate the page size back to the software. The PostScript back
2530 end, for example, writes out PS which determines the page size at print
2531 time by means of calling `clippath', and centres the puzzles within
2532 that. Thus, exactly the same PS file works on A4 or on US Letter paper
2533 without needing local configuration, which simplifies matters.)
2535 pw and ph give the size of the puzzle in drawing API coordinates. The
2536 printing system will subsequently call the puzzle's own print function,
2537 which will in turn call drawing API functions in the expectation that an
2538 area pw by ph units is available to draw the puzzle on.
2540 Finally, wmm gives the desired width of the puzzle in millimetres. (The
2541 aspect ratio is expected to be preserved, so if the desired puzzle
2542 height is also needed then it can be computed as wmm*ph/pw.)
2544 Implementations of this API which do not provide printing services may
2545 define this function pointer to be NULL; it will never be called unless
2546 printing is attempted.
2548 3.2.20. end_puzzle()
2549 --------------------
2551 void (*end_puzzle)(void *handle);
2553 This function is called after the printing of a specific puzzle is
2556 Implementations of this API which do not provide printing services may
2557 define this function pointer to be NULL; it will never be called unless
2558 printing is attempted.
2563 void (*end_page)(void *handle, int number);
2565 This function is called after the printing of a page is finished.
2567 Implementations of this API which do not provide printing services may
2568 define this function pointer to be NULL; it will never be called unless
2569 printing is attempted.
2574 void (*end_doc)(void *handle);
2576 This function is called after the printing of the entire document is
2577 finished. This is the moment to close files, send things to the print
2578 spooler, or whatever the local convention is.
2580 Implementations of this API which do not provide printing services may
2581 define this function pointer to be NULL; it will never be called unless
2582 printing is attempted.
2584 3.2.23. line_width()
2585 --------------------
2587 void (*line_width)(void *handle, float width);
2589 This function is called to set the line thickness, during printing only.
2590 Note that the width is a float here, where it was an int as seen by the
2591 back end. This is because drawing.c may have scaled it on the way past.
2593 However, the width is still specified in the same coordinate system as
2594 the rest of the drawing.
2596 Implementations of this API which do not provide printing services may
2597 define this function pointer to be NULL; it will never be called unless
2598 printing is attempted.
2600 3.2.24. text_fallback()
2601 -----------------------
2603 char *(*text_fallback)(void *handle, const char *const *strings,
2606 This function behaves exactly like the back end text_fallback()
2607 function; see section 3.1.8.
2609 Implementations of this API which do not support any characters outside
2610 ASCII may define this function pointer to be NULL, in which case the
2611 central code in drawing.c will provide a default implementation.
2613 3.3. The drawing API as called by the front end
2614 -----------------------------------------------
2616 There are a small number of functions provided in drawing.c which the
2617 front end needs to _call_, rather than helping to implement. They are
2618 described in this section.
2620 3.3.1. drawing_new()
2621 --------------------
2623 drawing *drawing_new(const drawing_api *api, midend *me,
2626 This function creates a drawing object. It is passed a `drawing_api',
2627 which is a structure containing nothing but function pointers; and also
2628 a `void *' handle. The handle is passed back to each function pointer
2631 The `midend' parameter is used for rewriting the status bar contents:
2632 status_bar() (see section 3.1.12) has to call a function in the mid-
2633 end which might rewrite the status bar text. If the drawing object
2634 is to be used only for printing, or if the game is known not to call
2635 status_bar(), this parameter may be NULL.
2637 3.3.2. drawing_free()
2638 ---------------------
2640 void drawing_free(drawing *dr);
2642 This function frees a drawing object. Note that the `void *' handle is
2643 not freed; if that needs cleaning up it must be done by the front end.
2645 3.3.3. print_get_colour()
2646 -------------------------
2648 void print_get_colour(drawing *dr, int colour, int printincolour,
2649 int *hatch, float *r, float *g, float *b)
2651 This function is called by the implementations of the drawing API
2652 functions when they are called in a printing context. It takes a colour
2653 index as input, and returns the description of the colour as requested
2656 `printincolour' is TRUE iff the implementation is printing in colour.
2657 This will alter the results returned if the colour in question was
2658 specified with a black-and-white fallback value.
2660 If the colour should be rendered by hatching, `*hatch' is filled with
2661 the type of hatching desired. See section 3.1.15 for details of the
2662 values this integer can take.
2664 If the colour should be rendered as solid colour, `*hatch' is given a
2665 negative value, and `*r', `*g' and `*b' are filled with the RGB values
2666 of the desired colour (if printing in colour), or all filled with the
2667 grey-scale value (if printing in black and white).
2669 4. The API provided by the mid-end
2670 ----------------------------------
2672 This chapter documents the API provided by the mid-end to be called by
2673 the front end. You probably only need to read this if you are a front
2674 end implementor, i.e. you are porting Puzzles to a new platform. If
2675 you're only interested in writing new puzzles, you can safely skip this
2678 All the persistent state in the mid-end is encapsulated within a
2679 `midend' structure, to facilitate having multiple mid-ends in any
2680 port which supports multiple puzzle windows open simultaneously. Each
2681 `midend' is intended to handle the contents of a single puzzle window.
2686 midend *midend_new(frontend *fe, const game *ourgame,
2687 const drawing_api *drapi, void *drhandle)
2689 Allocates and returns a new mid-end structure.
2691 The `fe' argument is stored in the mid-end. It will be used when calling
2692 back to functions such as activate_timer() (section 4.37), and will be
2693 passed on to the back end function colours() (section 2.8.6).
2695 The parameters `drapi' and `drhandle' are passed to drawing_new()
2696 (section 3.3.1) to construct a drawing object which will be passed to
2697 the back end function redraw() (section 2.8.10). Hence, all drawing-
2698 related function pointers defined in `drapi' can expect to be called
2699 with `drhandle' as their first argument.
2701 The `ourgame' argument points to a container structure describing a game
2702 back end. The mid-end thus created will only be capable of handling that
2703 one game. (So even in a monolithic front end containing all the games,
2704 this imposes the constraint that any individual puzzle window is tied to
2705 a single game. Unless, of course, you feel brave enough to change the
2706 mid-end for the window without closing the window...)
2711 void midend_free(midend *me);
2713 Frees a mid-end structure and all its associated data.
2715 4.3. midend_tilesize()
2716 ----------------------
2718 int midend_tilesize(midend *me);
2720 Returns the `tilesize' parameter being used to display the current
2721 puzzle (section 2.8.3).
2723 4.4. midend_set_params()
2724 ------------------------
2726 void midend_set_params(midend *me, game_params *params);
2728 Sets the current game parameters for a mid-end. Subsequent games
2729 generated by midend_new_game() (section 4.8) will use these parameters
2730 until further notice.
2732 The usual way in which the front end will have an actual `game_params'
2733 structure to pass to this function is if it had previously got it from
2734 midend_fetch_preset() (section 4.16). Thus, this function is usually
2735 called in response to the user making a selection from the presets menu.
2737 4.5. midend_get_params()
2738 ------------------------
2740 game_params *midend_get_params(midend *me);
2742 Returns the current game parameters stored in this mid-end.
2744 The returned value is dynamically allocated, and should be freed when
2745 finished with by passing it to the game's own free_params() function
2746 (see section 2.3.5).
2751 void midend_size(midend *me, int *x, int *y, int user_size);
2753 Tells the mid-end to figure out its window size.
2755 On input, `*x' and `*y' should contain the maximum or requested size
2756 for the window. (Typically this will be the size of the screen that the
2757 window has to fit on, or similar.) The mid-end will repeatedly call the
2758 back end function compute_size() (section 2.8.4), searching for a tile
2759 size that best satisfies the requirements. On exit, `*x' and `*y' will
2760 contain the size needed for the puzzle window's drawing area. (It is
2761 of course up to the front end to adjust this for any additional window
2762 furniture such as menu bars and window borders, if necessary. The status
2763 bar is also not included in this size.)
2765 Use `user_size' to indicate whether `*x' and `*y' are a requested size,
2766 or just a maximum size.
2768 If `user_size' is set to TRUE, the mid-end will treat the input size as
2769 a request, and will pick a tile size which approximates it _as closely
2770 as possible_, going over the game's preferred tile size if necessary to
2771 achieve this. The mid-end will also use the resulting tile size as its
2772 preferred one until further notice, on the assumption that this size was
2773 explicitly requested by the user. Use this option if you want your front
2774 end to support dynamic resizing of the puzzle window with automatic
2775 scaling of the puzzle to fit.
2777 If `user_size' is set to FALSE, then the game's tile size will never go
2778 over its preferred one, although it may go under in order to fit within
2779 the maximum bounds specified by `*x' and `*y'. This is the recommended
2780 approach when opening a new window at default size: the game will use
2781 its preferred size unless it has to use a smaller one to fit on the
2782 screen. If the tile size is shrunk for this reason, the change will not
2783 persist; if a smaller grid is subsequently chosen, the tile size will
2786 The mid-end will try as hard as it can to return a size which is
2787 less than or equal to the input size, in both dimensions. In extreme
2788 circumstances it may fail (if even the lowest possible tile size gives
2789 window dimensions greater than the input), in which case it will return
2790 a size greater than the input size. Front ends should be prepared
2791 for this to happen (i.e. don't crash or fail an assertion), but may
2792 handle it in any way they see fit: by rejecting the game parameters
2793 which caused the problem, by opening a window larger than the screen
2794 regardless of inconvenience, by introducing scroll bars on the window,
2795 by drawing on a large bitmap and scaling it into a smaller window, or by
2796 any other means you can think of. It is likely that when the tile size
2797 is that small the game will be unplayable anyway, so don't put _too_
2798 much effort into handling it creatively.
2800 If your platform has no limit on window size (or if you're planning to
2801 use scroll bars for large puzzles), you can pass dimensions of INT_MAX
2802 as input to this function. You should probably not do that _and_ set the
2803 `user_size' flag, though!
2805 The midend relies on the frontend calling midend_new_game() (section
2806 4.8) before calling midend_size().
2808 4.7. midend_reset_tilesize()
2809 ----------------------------
2811 void midend_reset_tilesize(midend *me);
2813 This function resets the midend's preferred tile size to that of the
2816 As discussed in section 4.6, puzzle resizes are typically 'sticky',
2817 in that once the user has dragged the puzzle to a different window
2818 size, the resulting tile size will be remembered and used when the
2819 puzzle configuration changes. If you _don't_ want that, e.g. if you
2820 want to provide a command to explicitly reset the puzzle size back to
2821 its default, then you can call this just before calling midend_size()
2822 (which, in turn, you would probably call with `user_size' set to FALSE).
2824 4.8. midend_new_game()
2825 ----------------------
2827 void midend_new_game(midend *me);
2829 Causes the mid-end to begin a new game. Normally the game will be a
2830 new randomly generated puzzle. However, if you have previously called
2831 midend_game_id() or midend_set_config(), the game generated might be
2832 dictated by the results of those functions. (In particular, you _must_
2833 call midend_new_game() after calling either of those functions, or else
2834 no immediate effect will be visible.)
2836 You will probably need to call midend_size() after calling this
2837 function, because if the game parameters have been changed since the
2838 last new game then the window size might need to change. (If you know
2839 the parameters _haven't_ changed, you don't need to do this.)
2841 This function will create a new `game_drawstate', but does not actually
2842 perform a redraw (since you often need to call midend_size() before
2843 the redraw can be done). So after calling this function and after
2844 calling midend_size(), you should then call midend_redraw(). (It is not
2845 necessary to call midend_force_redraw(); that will discard the draw
2846 state and create a fresh one, which is unnecessary in this case since
2847 there's a fresh one already. It would work, but it's usually excessive.)
2849 4.9. midend_restart_game()
2850 --------------------------
2852 void midend_restart_game(midend *me);
2854 This function causes the current game to be restarted. This is done by
2855 placing a new copy of the original game state on the end of the undo
2856 list (so that an accidental restart can be undone).
2858 This function automatically causes a redraw, i.e. the front end can
2859 expect its drawing API to be called from _within_ a call to this
2860 function. Some back ends require that midend_size() (section 4.6) is
2861 called before midend_restart_game().
2863 4.10. midend_force_redraw()
2864 ---------------------------
2866 void midend_force_redraw(midend *me);
2868 Forces a complete redraw of the puzzle window, by means of discarding
2869 the current `game_drawstate' and creating a new one from scratch before
2870 calling the game's redraw() function.
2872 The front end can expect its drawing API to be called from within a call
2873 to this function. Some back ends require that midend_size() (section
2874 4.6) is called before midend_force_redraw().
2876 4.11. midend_redraw()
2877 ---------------------
2879 void midend_redraw(midend *me);
2881 Causes a partial redraw of the puzzle window, by means of simply calling
2882 the game's redraw() function. (That is, the only things redrawn will be
2883 things that have changed since the last redraw.)
2885 The front end can expect its drawing API to be called from within a call
2886 to this function. Some back ends require that midend_size() (section
2887 4.6) is called before midend_redraw().
2889 4.12. midend_process_key()
2890 --------------------------
2892 int midend_process_key(midend *me, int x, int y, int button);
2894 The front end calls this function to report a mouse or keyboard event.
2895 The parameters `x', `y' and `button' are almost identical to the ones
2896 passed to the back end function interpret_move() (section 2.7.1), except
2897 that the front end is _not_ required to provide the guarantees about
2898 mouse event ordering. The mid-end will sort out multiple simultaneous
2899 button presses and changes of button; the front end's responsibility
2900 is simply to pass on the mouse events it receives as accurately as
2903 (Some platforms may need to emulate absent mouse buttons by means of
2904 using a modifier key such as Shift with another mouse button. This tends
2905 to mean that if Shift is pressed or released in the middle of a mouse
2906 drag, the mid-end will suddenly stop receiving, say, LEFT_DRAG events
2907 and start receiving RIGHT_DRAGs, with no intervening button release or
2908 press events. This too is something which the mid-end will sort out for
2909 you; the front end has no obligation to maintain sanity in this area.)
2911 The front end _should_, however, always eventually send some kind of
2912 button release. On some platforms this requires special effort: Windows,
2913 for example, requires a call to the system API function SetCapture() in
2914 order to ensure that your window receives a mouse-up event even if the
2915 pointer has left the window by the time the mouse button is released.
2916 On any platform that requires this sort of thing, the front end _is_
2917 responsible for doing it.
2919 Calling this function is very likely to result in calls back to the
2920 front end's drawing API and/or activate_timer() (section 4.37).
2922 The return value from midend_process_key() is non-zero, unless the
2923 effect of the keypress was to request termination of the program. A
2924 front end should shut down the puzzle in response to a zero return.
2926 4.13. midend_colours()
2927 ----------------------
2929 float *midend_colours(midend *me, int *ncolours);
2931 Returns an array of the colours required by the game, in exactly
2932 the same format as that returned by the back end function colours()
2933 (section 2.8.6). Front ends should call this function rather than
2934 calling the back end's version directly, since the mid-end adds standard
2935 customisation facilities. (At the time of writing, those customisation
2936 facilities are implemented hackily by means of environment variables,
2937 but it's not impossible that they may become more full and formal in
2940 4.14. midend_timer()
2941 --------------------
2943 void midend_timer(midend *me, float tplus);
2945 If the mid-end has called activate_timer() (section 4.37) to request
2946 regular callbacks for purposes of animation or timing, this is the
2947 function the front end should call on a regular basis. The argument
2948 `tplus' gives the time, in seconds, since the last time either this
2949 function was called or activate_timer() was invoked.
2951 One of the major purposes of timing in the mid-end is to perform move
2952 animation. Therefore, calling this function is very likely to result in
2953 calls back to the front end's drawing API.
2955 4.15. midend_num_presets()
2956 --------------------------
2958 int midend_num_presets(midend *me);
2960 Returns the number of game parameter presets supplied by this game.
2961 Front ends should use this function and midend_fetch_preset() to
2962 configure their presets menu rather than calling the back end directly,
2963 since the mid-end adds standard customisation facilities. (At the time
2964 of writing, those customisation facilities are implemented hackily by
2965 means of environment variables, but it's not impossible that they may
2966 become more full and formal in future.)
2968 4.16. midend_fetch_preset()
2969 ---------------------------
2971 void midend_fetch_preset(midend *me, int n,
2972 char **name, game_params **params);
2974 Returns one of the preset game parameter structures for the game.
2975 On input `n' must be a non-negative integer and less than the value
2976 returned from midend_num_presets(). On output, `*name' is set to an
2977 ASCII string suitable for entering in the game's presets menu, and
2978 `*params' is set to the corresponding `game_params' structure.
2980 Both of the two output values are dynamically allocated, but they are
2981 owned by the mid-end structure: the front end should not ever free them
2982 directly, because they will be freed automatically during midend_free().
2984 4.17. midend_which_preset()
2985 ---------------------------
2987 int midend_which_preset(midend *me);
2989 Returns the numeric index of the preset game parameter structure which
2990 matches the current game parameters, or a negative number if no preset
2991 matches. Front ends could use this to maintain a tick beside one of the
2992 items in the menu (or tick the `Custom' option if the return value is
2995 4.18. midend_wants_statusbar()
2996 ------------------------------
2998 int midend_wants_statusbar(midend *me);
3000 This function returns TRUE if the puzzle has a use for a textual status
3001 line (to display score, completion status, currently active tiles, time,
3004 Front ends should call this function rather than talking directly to the
3007 4.19. midend_get_config()
3008 -------------------------
3010 config_item *midend_get_config(midend *me, int which,
3013 Returns a dialog box description for user configuration.
3015 On input, which should be set to one of three values, which select which
3016 of the various dialog box descriptions is returned:
3020 Requests the GUI parameter configuration box generated by the puzzle
3021 itself. This should be used when the user selects `Custom' from the
3022 game types menu (or equivalent). The mid-end passes this request on
3023 to the back end function configure() (section 2.3.8).
3027 Requests a box suitable for entering a descriptive game ID (and
3028 viewing the existing one). The mid-end generates this dialog box
3029 description itself. This should be used when the user selects
3030 `Specific' from the game menu (or equivalent).
3034 Requests a box suitable for entering a random-seed game ID (and
3035 viewing the existing one). The mid-end generates this dialog box
3036 description itself. This should be used when the user selects
3037 `Random Seed' from the game menu (or equivalent).
3039 The returned value is an array of config_items, exactly as described
3040 in section 2.3.8. Another returned value is an ASCII string giving a
3041 suitable title for the configuration window, in `*wintitle'.
3043 Both returned values are dynamically allocated and will need to be
3044 freed. The window title can be freed in the obvious way; the config_item
3045 array is a slightly complex structure, so a utility function free_cfg()
3046 is provided to free it for you. See section 5.2.6.
3048 (Of course, you will probably not want to free the config_item array
3049 until the dialog box is dismissed, because before then you will probably
3050 need to pass it to midend_set_config.)
3052 4.20. midend_set_config()
3053 -------------------------
3055 char *midend_set_config(midend *me, int which,
3058 Passes the mid-end the results of a configuration dialog box. `which'
3059 should have the same value which it had when midend_get_config() was
3060 called; `cfg' should be the array of `config_item's returned from
3061 midend_get_config(), modified to contain the results of the user's
3064 This function returns NULL on success, or otherwise (if the
3065 configuration data was in some way invalid) an ASCII string containing
3066 an error message suitable for showing to the user.
3068 If the function succeeds, it is likely that the game parameters will
3069 have been changed and it is certain that a new game will be requested.
3070 The front end should therefore call midend_new_game(), and probably also
3071 re-think the window size using midend_size() and eventually perform a
3072 refresh using midend_redraw().
3074 4.21. midend_game_id()
3075 ----------------------
3077 char *midend_game_id(midend *me, char *id);
3079 Passes the mid-end a string game ID (of any of the valid forms `params',
3080 `params:description' or `params#seed') which the mid-end will process
3081 and use for the next generated game.
3083 This function returns NULL on success, or otherwise (if the
3084 configuration data was in some way invalid) an ASCII string containing
3085 an error message (not dynamically allocated) suitable for showing to the
3086 user. In the event of an error, the mid-end's internal state will be
3087 left exactly as it was before the call.
3089 If the function succeeds, it is likely that the game parameters will
3090 have been changed and it is certain that a new game will be requested.
3091 The front end should therefore call midend_new_game(), and probably
3092 also re-think the window size using midend_size() and eventually case a
3093 refresh using midend_redraw().
3095 4.22. midend_get_game_id()
3096 --------------------------
3098 char *midend_get_game_id(midend *me)
3100 Returns a descriptive game ID (i.e. one in the form
3101 `params:description') describing the game currently active in the mid-
3102 end. The returned string is dynamically allocated.
3104 4.23. midend_get_random_seed()
3105 ------------------------------
3107 char *midend_get_random_seed(midend *me)
3109 Returns a random game ID (i.e. one in the form `params#seedstring')
3110 describing the game currently active in the mid-end, if there is one.
3111 If the game was created by entering a description, no random seed will
3112 currently exist and this function will return NULL.
3114 The returned string, if it is non-NULL, is dynamically allocated.
3116 4.24. midend_can_format_as_text_now()
3117 -------------------------------------
3119 int midend_can_format_as_text_now(midend *me);
3121 Returns TRUE if the game code is capable of formatting puzzles of the
3122 currently selected game type as ASCII.
3124 If this returns FALSE, then midend_text_format() (section 4.25) will
3127 4.25. midend_text_format()
3128 --------------------------
3130 char *midend_text_format(midend *me);
3132 Formats the current game's current state as ASCII text suitable for
3133 copying to the clipboard. The returned string is dynamically allocated.
3135 If the game's `can_format_as_text_ever' flag is FALSE, or if its
3136 can_format_as_text_now() function returns FALSE, then this function will
3139 If the returned string contains multiple lines (which is likely), it
3140 will use the normal C line ending convention (\n only). On platforms
3141 which use a different line ending convention for data in the clipboard,
3142 it is the front end's responsibility to perform the conversion.
3144 4.26. midend_solve()
3145 --------------------
3147 char *midend_solve(midend *me);
3149 Requests the mid-end to perform a Solve operation.
3151 On success, NULL is returned. On failure, an error message (not
3152 dynamically allocated) is returned, suitable for showing to the user.
3154 The front end can expect its drawing API and/or activate_timer() to be
3155 called from within a call to this function. Some back ends require that
3156 midend_size() (section 4.6) is called before midend_solve().
3158 4.27. midend_status()
3159 ---------------------
3161 int midend_status(midend *me);
3163 This function returns +1 if the midend is currently displaying a game
3164 in a solved state, -1 if the game is in a permanently lost state, or 0
3165 otherwise. This function just calls the back end's status() function.
3166 Front ends may wish to use this as a cue to proactively offer the option
3167 of starting a new game.
3169 (See section 2.8.9 for more detail about the back end's status()
3170 function and discussion of what should count as which status code.)
3172 4.28. midend_can_undo()
3173 -----------------------
3175 int midend_can_undo(midend *me);
3177 Returns TRUE if the midend is currently in a state where the undo
3178 operation is meaningful (i.e. at least one position exists on the undo
3179 chain before the present one). Front ends may wish to use this to
3180 visually activate and deactivate an undo button.
3182 4.29. midend_can_redo()
3183 -----------------------
3185 int midend_can_redo(midend *me);
3187 Returns TRUE if the midend is currently in a state where the redo
3188 operation is meaningful (i.e. at least one position exists on the
3189 redo chain after the present one). Front ends may wish to use this to
3190 visually activate and deactivate a redo button.
3192 4.30. midend_serialise()
3193 ------------------------
3195 void midend_serialise(midend *me,
3196 void (*write)(void *ctx, void *buf, int len),
3199 Calling this function causes the mid-end to convert its entire internal
3200 state into a long ASCII text string, and to pass that string (piece by
3201 piece) to the supplied `write' function.
3203 Desktop implementations can use this function to save a game in any
3204 state (including half-finished) to a disk file, by supplying a `write'
3205 function which is a wrapper on fwrite() (or local equivalent). Other
3206 implementations may find other uses for it, such as compressing the
3207 large and sprawling mid-end state into a manageable amount of memory
3208 when a palmtop application is suspended so that another one can run; in
3209 this case write might want to write to a memory buffer rather than a
3210 file. There may be other uses for it as well.
3212 This function will call back to the supplied `write' function a number
3213 of times, with the first parameter (`ctx') equal to `wctx', and the
3214 other two parameters pointing at a piece of the output string.
3216 4.31. midend_deserialise()
3217 --------------------------
3219 char *midend_deserialise(midend *me,
3220 int (*read)(void *ctx, void *buf, int len),
3223 This function is the counterpart to midend_serialise(). It calls the
3224 supplied read function repeatedly to read a quantity of data, and
3225 attempts to interpret that data as a serialised mid-end as output by
3228 The read function is called with the first parameter (`ctx') equal
3229 to `rctx', and should attempt to read `len' bytes of data into the
3230 buffer pointed to by `buf'. It should return FALSE on failure or TRUE
3231 on success. It should not report success unless it has filled the
3232 entire buffer; on platforms which might be reading from a pipe or other
3233 blocking data source, `read' is responsible for looping until the whole
3234 buffer has been filled.
3236 If the de-serialisation operation is successful, the mid-end's internal
3237 data structures will be replaced by the results of the load, and NULL
3238 will be returned. Otherwise, the mid-end's state will be completely
3239 unchanged and an error message (typically some variation on `save file
3240 is corrupt') will be returned. As usual, the error message string is not
3241 dynamically allocated.
3243 If this function succeeds, it is likely that the game parameters will
3244 have been changed. The front end should therefore probably re-think the
3245 window size using midend_size(), and probably cause a refresh using
3248 Because each mid-end is tied to a specific game back end, this function
3249 will fail if you attempt to read in a save file generated by a different
3250 game from the one configured in this mid-end, even if your application
3251 is a monolithic one containing all the puzzles. See section 4.32 for a
3252 helper function which will allow you to identify a save file before you
3253 instantiate your mid-end in the first place.
3255 4.32. identify_game()
3256 ---------------------
3258 char *identify_game(char **name,
3259 int (*read)(void *ctx, void *buf, int len),
3262 This function examines a serialised midend stream, of the same kind used
3263 by midend_serialise() and midend_deserialise(), and returns the name
3264 field of the game back end from which it was saved.
3266 You might want this if your front end was a monolithic one containing
3267 all the puzzles, and you wanted to be able to load an arbitrary save
3268 file and automatically switch to the right game. Probably your next step
3269 would be to iterate through gamelist (section 4.34) looking for a game
3270 structure whose name field matched the returned string, and give an
3271 error if you didn't find one.
3273 On success, the return value of this function is NULL, and the game name
3274 string is written into *name. The caller should free that string after
3277 On failure, *name is NULL, and the return value is an error message
3278 (which does not need freeing at all).
3280 (This isn't strictly speaking a midend function, since it doesn't accept
3281 or return a pointer to a midend. You'd probably call it just _before_
3282 deciding what kind of midend you wanted to instantiate.)
3284 4.33. midend_request_id_changes()
3285 ---------------------------------
3287 void midend_request_id_changes(midend *me,
3288 void (*notify)(void *), void *ctx);
3290 This function is called by the front end to request notification by the
3291 mid-end when the current game IDs (either descriptive or random-seed)
3292 change. This can occur as a result of keypresses ('n' for New Game, for
3293 example) or when a puzzle supersedes its game description (see section
3294 2.11.2). After this function is called, any change of the game ids will
3295 cause the mid-end to call notify(ctx) after the change.
3297 This is for use by puzzles which want to present the game description to
3298 the user constantly (e.g. as an HTML hyperlink) instead of only showing
3299 it when the user explicitly requests it.
3301 This is a function I anticipate few front ends needing to implement, so
3302 I make it a callback rather than a static function in order to relieve
3303 most front ends of the need to provide an empty implementation.
3305 4.34. Direct reference to the back end structure by the front end
3306 -----------------------------------------------------------------
3308 Although _most_ things the front end needs done should be done by
3309 calling the mid-end, there are a few situations in which the front end
3310 needs to refer directly to the game back end structure.
3312 The most obvious of these is
3314 - passing the game back end as a parameter to midend_new().
3316 There are a few other back end features which are not wrapped by the
3317 mid-end because there didn't seem much point in doing so:
3319 - fetching the `name' field to use in window titles and similar
3321 - reading the `can_configure', `can_solve' and
3322 `can_format_as_text_ever' fields to decide whether to add those
3323 items to the menu bar or equivalent
3325 - reading the `winhelp_topic' field (Windows only)
3327 - the GTK front end provides a `--generate' command-line option which
3328 directly calls the back end to do most of its work. This is not
3329 really part of the main front end code, though, and I'm not sure it
3332 In order to find the game back end structure, the front end does one of
3335 - If the particular front end is compiling a separate binary per game,
3336 then the back end structure is a global variable with the standard
3339 extern const game thegame;
3341 - If the front end is compiled as a monolithic application containing
3342 all the puzzles together (in which case the preprocessor symbol
3343 COMBINED must be defined when compiling most of the code base), then
3344 there will be two global variables defined:
3346 extern const game *gamelist[];
3347 extern const int gamecount;
3349 `gamelist' will be an array of `gamecount' game structures, declared
3350 in the automatically constructed source module `list.c'. The
3351 application should search that array for the game it wants, probably
3352 by reaching into each game structure and looking at its `name'
3355 4.35. Mid-end to front-end calls
3356 --------------------------------
3358 This section describes the small number of functions which a front end
3359 must provide to be called by the mid-end or other standard utility
3362 4.36. get_random_seed()
3363 -----------------------
3365 void get_random_seed(void **randseed, int *randseedsize);
3367 This function is called by a new mid-end, and also occasionally by game
3368 back ends. Its job is to return a piece of data suitable for using as a
3369 seed for initialisation of a new `random_state'.
3371 On exit, `*randseed' should be set to point at a newly allocated piece
3372 of memory containing some seed data, and `*randseedsize' should be set
3373 to the length of that data.
3375 A simple and entirely adequate implementation is to return a piece of
3376 data containing the current system time at the highest conveniently
3377 available resolution.
3379 4.37. activate_timer()
3380 ----------------------
3382 void activate_timer(frontend *fe);
3384 This is called by the mid-end to request that the front end begin
3385 calling it back at regular intervals.
3387 The timeout interval is left up to the front end; the finer it is, the
3388 smoother move animations will be, but the more CPU time will be used.
3389 Current front ends use values around 20ms (i.e. 50Hz).
3391 After this function is called, the mid-end will expect to receive calls
3392 to midend_timer() on a regular basis.
3394 4.38. deactivate_timer()
3395 ------------------------
3397 void deactivate_timer(frontend *fe);
3399 This is called by the mid-end to request that the front end stop calling
3405 void fatal(char *fmt, ...);
3407 This is called by some utility functions if they encounter a genuinely
3408 fatal error such as running out of memory. It is a variadic function
3409 in the style of printf(), and is expected to show the formatted error
3410 message to the user any way it can and then terminate the application.
3413 4.40. frontend_default_colour()
3414 -------------------------------
3416 void frontend_default_colour(frontend *fe, float *output);
3418 This function expects to be passed a pointer to an array of three
3419 floats. It returns the platform's local preferred background colour
3420 in those three floats, as red, green and blue values (in that order)
3421 ranging from 0.0 to 1.0.
3423 This function should only ever be called by the back end function
3424 colours() (section 2.8.6). (Thus, it isn't a _midend_-to-frontend
3425 function as such, but there didn't seem to be anywhere else particularly
3426 good to put it. Sorry.)
3431 This chapter documents a variety of utility APIs provided for the
3432 general use of the rest of the Puzzles code.
3434 5.1. Random number generation
3435 -----------------------------
3437 Platforms' local random number generators vary widely in quality and
3438 seed size. Puzzles therefore supplies its own high-quality random number
3439 generator, with the additional advantage of giving the same results if
3440 fed the same seed data on different platforms. This allows game random
3441 seeds to be exchanged between different ports of Puzzles and still
3442 generate the same games.
3444 Unlike the ANSI C rand() function, the Puzzles random number generator
3445 has an _explicit_ state object called a `random_state'. One of these
3446 is managed by each mid-end, for example, and passed to the back end to
3447 generate a game with.
3452 random_state *random_new(char *seed, int len);
3454 Allocates, initialises and returns a new `random_state'. The input data
3455 is used as the seed for the random number stream (i.e. using the same
3456 seed at a later time will generate the same stream).
3458 The seed data can be any data at all; there is no requirement to use
3459 printable ASCII, or NUL-terminated strings, or anything like that.
3461 5.1.2. random_copy()
3462 --------------------
3464 random_state *random_copy(random_state *tocopy);
3466 Allocates a new `random_state', copies the contents of another
3467 `random_state' into it, and returns the new state. If exactly the
3468 same sequence of functions is subseqently called on both the copy and
3469 the original, the results will be identical. This may be useful for
3470 speculatively performing some operation using a given random state, and
3471 later replaying that operation precisely.
3473 5.1.3. random_free()
3474 --------------------
3476 void random_free(random_state *state);
3478 Frees a `random_state'.
3480 5.1.4. random_bits()
3481 --------------------
3483 unsigned long random_bits(random_state *state, int bits);
3485 Returns a random number from 0 to 2^bits-1 inclusive. `bits' should be
3486 between 1 and 32 inclusive.
3488 5.1.5. random_upto()
3489 --------------------
3491 unsigned long random_upto(random_state *state, unsigned long limit);
3493 Returns a random number from 0 to limit-1 inclusive.
3495 5.1.6. random_state_encode()
3496 ----------------------------
3498 char *random_state_encode(random_state *state);
3500 Encodes the entire contents of a `random_state' in printable ASCII.
3501 Returns a dynamically allocated string containing that encoding. This
3502 can subsequently be passed to random_state_decode() to reconstruct the
3503 same `random_state'.
3505 5.1.7. random_state_decode()
3506 ----------------------------
3508 random_state *random_state_decode(char *input);
3510 Decodes a string generated by random_state_encode() and reconstructs an
3511 equivalent `random_state' to the one encoded, i.e. it should produce the
3512 same stream of random numbers.
3514 This function has no error reporting; if you pass it an invalid string
3515 it will simply generate an arbitrary random state, which may turn out to
3516 be noticeably non-random.
3521 void shuffle(void *array, int nelts, int eltsize, random_state *rs);
3523 Shuffles an array into a random order. The interface is much like ANSI C
3524 qsort(), except that there's no need for a compare function.
3526 `array' is a pointer to the first element of the array. `nelts' is the
3527 number of elements in the array; `eltsize' is the size of a single
3528 element (typically measured using `sizeof'). `rs' is a `random_state'
3529 used to generate all the random numbers for the shuffling process.
3531 5.2. Memory allocation
3532 ----------------------
3534 Puzzles has some central wrappers on the standard memory allocation
3535 functions, which provide compile-time type checking, and run-time error
3536 checking by means of quitting the application if it runs out of memory.
3537 This doesn't provide the best possible recovery from memory shortage,
3538 but on the other hand it greatly simplifies the rest of the code,
3539 because nothing else anywhere needs to worry about NULL returns from
3547 This macro takes a single argument which is a _type name_. It allocates
3548 space for one object of that type. If allocation fails it will call
3549 fatal() and not return; so if it does return, you can be confident that
3550 its return value is non-NULL.
3552 The return value is cast to the specified type, so that the compiler
3553 will type-check it against the variable you assign it into. Thus, this
3554 ensures you don't accidentally allocate memory the size of the wrong
3555 type and assign it into a variable of the right one (or vice versa!).
3560 var = snewn(n, type);
3562 This macro is the array form of snew(). It takes two arguments; the
3563 first is a number, and the second is a type name. It allocates space
3564 for that many objects of that type, and returns a type-checked non-NULL
3565 pointer just as snew() does.
3570 var = sresize(var, n, type);
3572 This macro is a type-checked form of realloc(). It takes three
3573 arguments: an input memory block, a new size in elements, and a type.
3574 It re-sizes the input memory block to a size sufficient to contain that
3575 many elements of that type. It returns a type-checked non-NULL pointer,
3576 like snew() and snewn().
3578 The input memory block can be NULL, in which case this function will
3579 behave exactly like snewn(). (In principle any ANSI-compliant realloc()
3580 implementation ought to cope with this, but I've never quite trusted it
3581 to work everywhere.)
3586 void sfree(void *p);
3588 This function is pretty much equivalent to free(). It is provided with a
3589 dynamically allocated block, and frees it.
3591 The input memory block can be NULL, in which case this function will do
3592 nothing. (In principle any ANSI-compliant free() implementation ought to
3593 cope with this, but I've never quite trusted it to work everywhere.)
3598 char *dupstr(const char *s);
3600 This function dynamically allocates a duplicate of a C string. Like the
3601 snew() functions, it guarantees to return non-NULL or not return at all.
3603 (Many platforms provide the function strdup(). As well as guaranteeing
3604 never to return NULL, my version has the advantage of being defined
3605 _everywhere_, rather than inconveniently not quite everywhere.)
3610 void free_cfg(config_item *cfg);
3612 This function correctly frees an array of `config_item's, including
3613 walking the array until it gets to the end and freeing precisely those
3614 `sval' fields which are expected to be dynamically allocated.
3616 (See section 2.3.8 for details of the `config_item' structure.)
3618 5.3. Sorted and counted tree functions
3619 --------------------------------------
3621 Many games require complex algorithms for generating random puzzles, and
3622 some require moderately complex algorithms even during play. A common
3623 requirement during these algorithms is for a means of maintaining sorted
3624 or unsorted lists of items, such that items can be removed and added
3627 For general use, Puzzles provides the following set of functions which
3628 maintain 2-3-4 trees in memory. (A 2-3-4 tree is a balanced tree
3629 structure, with the property that all lookups, insertions, deletions,
3630 splits and joins can be done in O(log N) time.)
3632 All these functions expect you to be storing a tree of `void *'
3633 pointers. You can put anything you like in those pointers.
3635 By the use of per-node element counts, these tree structures have the
3636 slightly unusual ability to look elements up by their numeric index
3637 within the list represented by the tree. This means that they can be
3638 used to store an unsorted list (in which case, every time you insert a
3639 new element, you must explicitly specify the position where you wish to
3640 insert it). They can also do numeric lookups in a sorted tree, which
3641 might be useful for (for example) tracking the median of a changing data
3644 As well as storing sorted lists, these functions can be used for storing
3645 `maps' (associative arrays), by defining each element of a tree to be a
3651 tree234 *newtree234(cmpfn234 cmp);
3653 Creates a new empty tree, and returns a pointer to it.
3655 The parameter `cmp' determines the sorting criterion on the tree. Its
3658 typedef int (*cmpfn234)(void *, void *);
3660 If you want a sorted tree, you should provide a function matching this
3661 prototype, which returns like strcmp() does (negative if the first
3662 argument is smaller than the second, positive if it is bigger, zero if
3663 they compare equal). In this case, the function addpos234() will not be
3664 usable on your tree (because all insertions must respect the sorting
3667 If you want an unsorted tree, pass NULL. In this case you will not be
3668 able to use either add234() or del234(), or any other function such
3669 as find234() which depends on a sorting order. Your tree will become
3670 something more like an array, except that it will efficiently support
3671 insertion and deletion as well as lookups by numeric index.
3673 5.3.2. freetree234()
3674 --------------------
3676 void freetree234(tree234 *t);
3678 Frees a tree. This function will not free the _elements_ of the tree
3679 (because they might not be dynamically allocated, or you might be
3680 storing the same set of elements in more than one tree); it will just
3681 free the tree structure itself. If you want to free all the elements of
3682 a tree, you should empty it before passing it to freetree234(), by means
3683 of code along the lines of
3685 while ((element = delpos234(tree, 0)) != NULL)
3686 sfree(element); /* or some more complicated free function */
3691 void *add234(tree234 *t, void *e);
3693 Inserts a new element `e' into the tree `t'. This function expects the
3694 tree to be sorted; the new element is inserted according to the sort
3697 If an element comparing equal to `e' is already in the tree, then the
3698 insertion will fail, and the return value will be the existing element.
3699 Otherwise, the insertion succeeds, and `e' is returned.
3704 void *addpos234(tree234 *t, void *e, int index);
3706 Inserts a new element into an unsorted tree. Since there is no sorting
3707 order to dictate where the new element goes, you must specify where you
3708 want it to go. Setting `index' to zero puts the new element right at the
3709 start of the list; setting `index' to the current number of elements in
3710 the tree puts the new element at the end.
3712 Return value is `e', in line with add234() (although this function
3713 cannot fail except by running out of memory, in which case it will bomb
3714 out and die rather than returning an error indication).
3719 void *index234(tree234 *t, int index);
3721 Returns a pointer to the `index'th element of the tree, or NULL if
3722 `index' is out of range. Elements of the tree are numbered from zero.
3727 void *find234(tree234 *t, void *e, cmpfn234 cmp);
3729 Searches for an element comparing equal to `e' in a sorted tree.
3731 If `cmp' is NULL, the tree's ordinary comparison function will be used
3732 to perform the search. However, sometimes you don't want that; suppose,
3733 for example, each of your elements is a big structure containing a
3734 `char *' name field, and you want to find the element with a given name.
3735 You _could_ achieve this by constructing a fake element structure,
3736 setting its name field appropriately, and passing it to find234(),
3737 but you might find it more convenient to pass _just_ a name string to
3738 find234(), supplying an alternative comparison function which expects
3739 one of its arguments to be a bare name and the other to be a large
3740 structure containing a name field.
3742 Therefore, if `cmp' is not NULL, then it will be used to compare `e' to
3743 elements of the tree. The first argument passed to `cmp' will always be
3744 `e'; the second will be an element of the tree.
3746 (See section 5.3.1 for the definition of the `cmpfn234' function pointer
3749 The returned value is the element found, or NULL if the search is
3755 void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation);
3757 This function is like find234(), but has the additional ability to do a
3758 _relative_ search. The additional parameter `relation' can be one of the
3763 Find only an element that compares equal to `e'. This is exactly the
3764 behaviour of find234().
3768 Find the greatest element that compares strictly less than `e'. `e'
3769 may be NULL, in which case it finds the greatest element in the
3770 whole tree (which could also be done by index234(t, count234(t)-1)).
3774 Find the greatest element that compares less than or equal to `e'.
3775 (That is, find an element that compares equal to `e' if possible,
3776 but failing that settle for something just less than it.)
3780 Find the smallest element that compares strictly greater than `e'.
3781 `e' may be NULL, in which case it finds the smallest element in the
3782 whole tree (which could also be done by index234(t, 0)).
3786 Find the smallest element that compares greater than or equal
3787 to `e'. (That is, find an element that compares equal to `e' if
3788 possible, but failing that settle for something just bigger than
3791 Return value, as before, is the element found or NULL if no element
3792 satisfied the search criterion.
3797 void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index);
3799 This function is like find234(), but has the additional feature of
3800 returning the index of the element found in the tree; that index is
3801 written to `*index' in the event of a successful search (a non-NULL
3804 `index' may be NULL, in which case this function behaves exactly like
3807 5.3.9. findrelpos234()
3808 ----------------------
3810 void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, int relation,
3813 This function combines all the features of findrel234() and
3819 void *del234(tree234 *t, void *e);
3821 Finds an element comparing equal to `e' in the tree, deletes it, and
3824 The input tree must be sorted.
3826 The element found might be `e' itself, or might merely compare equal to
3829 Return value is NULL if no such element is found.
3834 void *delpos234(tree234 *t, int index);
3836 Deletes the element at position `index' in the tree, and returns it.
3838 Return value is NULL if the index is out of range.
3843 int count234(tree234 *t);
3845 Returns the number of elements currently in the tree.
3847 5.3.13. splitpos234()
3848 ---------------------
3850 tree234 *splitpos234(tree234 *t, int index, int before);
3852 Splits the input tree into two pieces at a given position, and creates a
3853 new tree containing all the elements on one side of that position.
3855 If `before' is TRUE, then all the items at or after position `index' are
3856 left in the input tree, and the items before that point are returned in
3857 the new tree. Otherwise, the reverse happens: all the items at or after
3858 `index' are moved into the new tree, and those before that point are
3859 left in the old one.
3861 If `index' is equal to 0 or to the number of elements in the input tree,
3862 then one of the two trees will end up empty (and this is not an error
3863 condition). If `index' is further out of range in either direction, the
3864 operation will fail completely and return NULL.
3866 This operation completes in O(log N) time, no matter how large the tree
3867 or how balanced or unbalanced the split.
3872 tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel);
3874 Splits a sorted tree according to its sort order.
3876 `rel' can be any of the relation constants described in section 5.3.7,
3877 _except_ for REL234_EQ. All the elements having that relation to `e'
3878 will be transferred into the new tree; the rest will be left in the old
3881 The parameter `cmp' has the same semantics as it does in find234(): if
3882 it is not NULL, it will be used in place of the tree's own comparison
3883 function when comparing elements to `e', in such a way that `e' itself
3884 is always the first of its two operands.
3886 Again, this operation completes in O(log N) time, no matter how large
3887 the tree or how balanced or unbalanced the split.
3892 tree234 *join234(tree234 *t1, tree234 *t2);
3894 Joins two trees together by concatenating the lists they represent. All
3895 the elements of `t2' are moved into `t1', in such a way that they appear
3896 _after_ the elements of `t1'. The tree `t2' is freed; the return value
3899 If you apply this function to a sorted tree and it violates the sort
3900 order (i.e. the smallest element in `t2' is smaller than or equal to the
3901 largest element in `t1'), the operation will fail and return NULL.
3903 This operation completes in O(log N) time, no matter how large the trees
3904 being joined together.
3909 tree234 *join234r(tree234 *t1, tree234 *t2);
3911 Joins two trees together in exactly the same way as join234(), but this
3912 time the combined tree is returned in `t2', and `t1' is destroyed. The
3913 elements in `t1' still appear before those in `t2'.
3915 Again, this operation completes in O(log N) time, no matter how large
3916 the trees being joined together.
3918 5.3.17. copytree234()
3919 ---------------------
3921 tree234 *copytree234(tree234 *t, copyfn234 copyfn,
3924 Makes a copy of an entire tree.
3926 If `copyfn' is NULL, the tree will be copied but the elements will not
3927 be; i.e. the new tree will contain pointers to exactly the same physical
3928 elements as the old one.
3930 If you want to copy each actual element during the operation, you can
3931 instead pass a function in `copyfn' which makes a copy of each element.
3932 That function has the prototype
3934 typedef void *(*copyfn234)(void *state, void *element);
3936 and every time it is called, the `state' parameter will be set to the
3937 value you passed in as `copyfnstate'.
3939 5.4. Miscellaneous utility functions and macros
3940 -----------------------------------------------
3942 This section contains all the utility functions which didn't sensibly
3945 5.4.1. TRUE and FALSE
3946 ---------------------
3948 The main Puzzles header file defines the macros TRUE and FALSE, which
3949 are used throughout the code in place of 1 and 0 (respectively) to
3950 indicate that the values are in a boolean context. For code base
3951 consistency, I'd prefer it if submissions of new code followed this
3954 5.4.2. max() and min()
3955 ----------------------
3957 The main Puzzles header file defines the pretty standard macros max()
3958 and min(), each of which is given two arguments and returns the one
3959 which compares greater or less respectively.
3961 These macros may evaluate their arguments multiple times. Avoid side
3967 The main Puzzles header file defines a macro PI which expands to a
3968 floating-point constant representing pi.
3970 (I've never understood why ANSI's <math.h> doesn't define this. It'd be
3973 5.4.4. obfuscate_bitmap()
3974 -------------------------
3976 void obfuscate_bitmap(unsigned char *bmp, int bits, int decode);
3978 This function obscures the contents of a piece of data, by cryptographic
3979 methods. It is useful for games of hidden information (such as Mines,
3980 Guess or Black Box), in which the game ID theoretically reveals all the
3981 information the player is supposed to be trying to guess. So in order
3982 that players should be able to send game IDs to one another without
3983 accidentally spoiling the resulting game by looking at them, these games
3984 obfuscate their game IDs using this function.
3986 Although the obfuscation function is cryptographic, it cannot properly
3987 be called encryption because it has no key. Therefore, anybody motivated
3988 enough can re-implement it, or hack it out of the Puzzles source,
3989 and strip the obfuscation off one of these game IDs to see what lies
3990 beneath. (Indeed, they could usually do it much more easily than that,
3991 by entering the game ID into their own copy of the puzzle and hitting
3992 Solve.) The aim is not to protect against a determined attacker; the aim
3993 is simply to protect people who wanted to play the game honestly from
3994 _accidentally_ spoiling their own fun.
3996 The input argument `bmp' points at a piece of memory to be obfuscated.
3997 `bits' gives the length of the data. Note that that length is in _bits_
3998 rather than bytes: if you ask for obfuscation of a partial number of
3999 bytes, then you will get it. Bytes are considered to be used from the
4000 top down: thus, for example, setting `bits' to 10 will cover the whole
4001 of bmp[0] and the _top two_ bits of bmp[1]. The remainder of a partially
4002 used byte is undefined (i.e. it may be corrupted by the function).
4004 The parameter `decode' is FALSE for an encoding operation, and TRUE
4005 for a decoding operation. Each is the inverse of the other. (There's
4006 no particular reason you shouldn't obfuscate by decoding and restore
4007 cleartext by encoding, if you really wanted to; it should still work.)
4009 The input bitmap is processed in place.
4014 char *bin2hex(const unsigned char *in, int inlen);
4016 This function takes an input byte array and converts it into an
4017 ASCII string encoding those bytes in (lower-case) hex. It returns a
4018 dynamically allocated string containing that encoding.
4020 This function is useful for encoding the result of obfuscate_bitmap() in
4021 printable ASCII for use in game IDs.
4026 unsigned char *hex2bin(const char *in, int outlen);
4028 This function takes an ASCII string containing hex digits, and converts
4029 it back into a byte array of length `outlen'. If there aren't enough
4030 hex digits in the string, the contents of the resulting array will be
4033 This function is the inverse of bin2hex().
4035 5.4.7. game_mkhighlight()
4036 -------------------------
4038 void game_mkhighlight(frontend *fe, float *ret,
4039 int background, int highlight, int lowlight);
4041 It's reasonably common for a puzzle game's graphics to use highlights
4042 and lowlights to indicate `raised' or `lowered' sections. Fifteen,
4043 Sixteen and Twiddle are good examples of this.
4045 Puzzles using this graphical style are running a risk if they just use
4046 whatever background colour is supplied to them by the front end, because
4047 that background colour might be too light to see any highlights on at
4048 all. (In particular, it's not unheard of for the front end to specify a
4049 default background colour of white.)
4051 Therefore, such puzzles can call this utility function from their
4052 colours() routine (section 2.8.6). You pass it your front end handle, a
4053 pointer to the start of your return array, and three colour indices. It
4056 - call frontend_default_colour() (section 4.40) to fetch the front
4057 end's default background colour
4059 - alter the brightness of that colour if it's unsuitable
4061 - define brighter and darker variants of the colour to be used as
4062 highlights and lowlights
4064 - write those results into the relevant positions in the `ret' array.
4066 Thus, ret[background*3] to ret[background*3+2] will be set to RGB values
4067 defining a sensible background colour, and similary `highlight' and
4068 `lowlight' will be set to sensible colours.
4070 6. How to write a new puzzle
4071 ----------------------------
4073 This chapter gives a guide to how to actually write a new puzzle: where
4074 to start, what to do first, how to solve common problems.
4076 The previous chapters have been largely composed of facts. This one is
4079 6.1. Choosing a puzzle
4080 ----------------------
4082 Before you start writing a puzzle, you have to choose one. Your taste
4083 in puzzle games is up to you, of course; and, in fact, you're probably
4084 reading this guide because you've _already_ thought of a game you want
4085 to write. But if you want to get it accepted into the official Puzzles
4086 distribution, then there's a criterion it has to meet.
4088 The current Puzzles editorial policy is that all games should be _fair_.
4089 A fair game is one which a player can only fail to complete through
4090 demonstrable lack of skill - that is, such that a better player in the
4091 same situation would have _known_ to do something different.
4093 For a start, that means every game presented to the user must have _at
4094 least one solution_. Giving the unsuspecting user a puzzle which is
4095 actually impossible is not acceptable. (There is an exception: if the
4096 user has selected some non-default option which is clearly labelled as
4097 potentially unfair, _then_ you're allowed to generate possibly insoluble
4098 puzzles, because the user isn't unsuspecting any more. Same Game and
4099 Mines both have options of this type.)
4101 Also, this actually _rules out_ games such as Klondike, or the normal
4102 form of Mahjong Solitaire. Those games have the property that even if
4103 there is a solution (i.e. some sequence of moves which will get from
4104 the start state to the solved state), the player doesn't necessarily
4105 have enough information to _find_ that solution. In both games, it is
4106 possible to reach a dead end because you had an arbitrary choice to make
4107 and made it the wrong way. This violates the fairness criterion, because
4108 a better player couldn't have known they needed to make the other
4111 (GNOME has a variant on Mahjong Solitaire which makes it fair: there
4112 is a Shuffle operation which randomly permutes all the remaining tiles
4113 without changing their positions, which allows you to get out of a
4114 sticky situation. Using this operation adds a 60-second penalty to your
4115 solution time, so it's to the player's advantage to try to minimise
4116 the chance of having to use it. It's still possible to render the game
4117 uncompletable if you end up with only two tiles vertically stacked,
4118 but that's easy to foresee and avoid using a shuffle operation. This
4119 form of the game _is_ fair. Implementing it in Puzzles would require
4120 an infrastructure change so that the back end could communicate time
4121 penalties to the mid-end, but that would be easy enough.)
4123 Providing a _unique_ solution is a little more negotiable; it depends
4124 on the puzzle. Solo would have been of unacceptably low quality if it
4125 didn't always have a unique solution, whereas Twiddle inherently has
4126 multiple solutions by its very nature and it would have been meaningless
4127 to even _suggest_ making it uniquely soluble. Somewhere in between, Flip
4128 could reasonably be made to have unique solutions (by enforcing a zero-
4129 dimension kernel in every generated matrix) but it doesn't seem like a
4130 serious quality problem that it doesn't.
4132 Of course, you don't _have_ to care about all this. There's nothing
4133 stopping you implementing any puzzle you want to if you're happy to
4134 maintain your puzzle yourself, distribute it from your own web site,
4135 fork the Puzzles code completely, or anything like that. It's free
4136 software; you can do what you like with it. But any game that you want
4137 to be accepted into _my_ Puzzles code base has to satisfy the fairness
4138 criterion, which means all randomly generated puzzles must have a
4139 solution (unless the user has deliberately chosen otherwise) and it must
4140 be possible _in theory_ to find that solution without having to guess.
4142 6.2. Getting started
4143 --------------------
4145 The simplest way to start writing a new puzzle is to copy `nullgame.c'.
4146 This is a template puzzle source file which does almost nothing, but
4147 which contains all the back end function prototypes and declares the
4148 back end data structure correctly. It is built every time the rest of
4149 Puzzles is built, to ensure that it doesn't get out of sync with the
4150 code and remains buildable.
4152 So start by copying `nullgame.c' into your new source file. Then you'll
4153 gradually add functionality until the very boring Null Game turns into
4156 Next you'll need to add your puzzle to the Makefiles, in order to
4157 compile it conveniently. _Do not edit the Makefiles_: they are created
4158 automatically by the script `mkfiles.pl', from the file called `Recipe'.
4159 Edit `Recipe', and then re-run `mkfiles.pl'.
4161 Also, don't forget to add your puzzle to `list.c': if you don't, then it
4162 will still run fine on platforms which build each puzzle separately, but
4163 Mac OS X and other monolithic platforms will not include your new puzzle
4164 in their single binary.
4166 Once your source file is building, you can move on to the fun bit.
4168 6.2.1. Puzzle generation
4169 ------------------------
4171 Randomly generating instances of your puzzle is almost certain to be
4172 the most difficult part of the code, and also the task with the highest
4173 chance of turning out to be completely infeasible. Therefore I strongly
4174 recommend doing it _first_, so that if it all goes horribly wrong you
4175 haven't wasted any more time than you absolutely had to. What I usually
4176 do is to take an unmodified `nullgame.c', and start adding code to
4177 new_game_desc() which tries to generate a puzzle instance and print it
4178 out using printf(). Once that's working, _then_ I start connecting it up
4179 to the return value of new_game_desc(), populating other structures like
4180 `game_params', and generally writing the rest of the source file.
4182 There are many ways to generate a puzzle which is known to be soluble.
4183 In this section I list all the methods I currently know of, in case any
4184 of them can be applied to your puzzle. (Not all of these methods will
4185 work, or in some cases even make sense, for all puzzles.)
4187 Some puzzles are mathematically tractable, meaning you can work out in
4188 advance which instances are soluble. Sixteen, for example, has a parity
4189 constraint in some settings which renders exactly half the game space
4190 unreachable, but it can be mathematically proved that any position
4191 not in that half _is_ reachable. Therefore, Sixteen's grid generation
4192 simply consists of selecting at random from a well defined subset of the
4193 game space. Cube in its default state is even easier: _every_ possible
4194 arrangement of the blue squares and the cube's starting position is
4197 Another option is to redefine what you mean by `soluble'. Black Box
4198 takes this approach. There are layouts of balls in the box which are
4199 completely indistinguishable from one another no matter how many beams
4200 you fire into the box from which angles, which would normally be grounds
4201 for declaring those layouts unfair; but fortunately, detecting that
4202 indistinguishability is computationally easy. So Black Box doesn't
4203 demand that your ball placements match its own; it merely demands
4204 that your ball placements be _indistinguishable_ from the ones it was
4205 thinking of. If you have an ambiguous puzzle, then any of the possible
4206 answers is considered to be a solution. Having redefined the rules in
4207 that way, any puzzle is soluble again.
4209 Those are the simple techniques. If they don't work, you have to get
4212 One way to generate a soluble puzzle is to start from the solved state
4213 and make inverse moves until you reach a starting state. Then you know
4214 there's a solution, because you can just list the inverse moves you made
4215 and make them in the opposite order to return to the solved state.
4217 This method can be simple and effective for puzzles where you get to
4218 decide what's a starting state and what's not. In Pegs, for example,
4219 the generator begins with one peg in the centre of the board and makes
4220 inverse moves until it gets bored; in this puzzle, valid inverse moves
4221 are easy to detect, and _any_ state that's reachable from the solved
4222 state by inverse moves is a reasonable starting position. So Pegs just
4223 continues making inverse moves until the board satisfies some criteria
4224 about extent and density, and then stops and declares itself done.
4226 For other puzzles, it can be a lot more difficult. Same Game uses
4227 this strategy too, and it's lucky to get away with it at all: valid
4228 inverse moves aren't easy to find (because although it's easy to insert
4229 additional squares in a Same Game position, it's difficult to arrange
4230 that _after_ the insertion they aren't adjacent to any other squares of
4231 the same colour), so you're constantly at risk of running out of options
4232 and having to backtrack or start again. Also, Same Game grids never
4233 start off half-empty, which means you can't just stop when you run out
4234 of moves - you have to find a way to fill the grid up _completely_.
4236 The other way to generate a puzzle that's soluble is to start from the
4237 other end, and actually write a _solver_. This tends to ensure that a
4238 puzzle has a _unique_ solution over and above having a solution at all,
4239 so it's a good technique to apply to puzzles for which that's important.
4241 One theoretical drawback of generating soluble puzzles by using a solver
4242 is that your puzzles are restricted in difficulty to those which the
4243 solver can handle. (Most solvers are not fully general: many sets of
4244 puzzle rules are NP-complete or otherwise nasty, so most solvers can
4245 only handle a subset of the theoretically soluble puzzles.) It's been
4246 my experience in practice, however, that this usually isn't a problem;
4247 computers are good at very different things from humans, and what the
4248 computer thinks is nice and easy might still be pleasantly challenging
4249 for a human. For example, when solving Dominosa puzzles I frequently
4250 find myself using a variety of reasoning techniques that my solver
4251 doesn't know about; in principle, therefore, I should be able to solve
4252 the puzzle using only those techniques it _does_ know about, but this
4253 would involve repeatedly searching the entire grid for the one simple
4254 deduction I can make. Computers are good at this sort of exhaustive
4255 search, but it's been my experience that human solvers prefer to do more
4256 complex deductions than to spend ages searching for simple ones. So in
4257 many cases I don't find my own playing experience to be limited by the
4258 restrictions on the solver.
4260 (This isn't _always_ the case. Solo is a counter-example; generating
4261 Solo puzzles using a simple solver does lead to qualitatively easier
4262 puzzles. Therefore I had to make the Solo solver rather more advanced
4265 There are several different ways to apply a solver to the problem of
4266 generating a soluble puzzle. I list a few of them below.
4268 The simplest approach is brute force: randomly generate a puzzle, use
4269 the solver to see if it's soluble, and if not, throw it away and try
4270 again until you get lucky. This is often a viable technique if all
4271 else fails, but it tends not to scale well: for many puzzle types, the
4272 probability of finding a uniquely soluble instance decreases sharply
4273 as puzzle size goes up, so this technique might work reasonably fast
4274 for small puzzles but take (almost) forever at larger sizes. Still, if
4275 there's no other alternative it can be usable: Pattern and Dominosa
4276 both use this technique. (However, Dominosa has a means of tweaking the
4277 randomly generated grids to increase the _probability_ of them being
4278 soluble, by ruling out one of the most common ambiguous cases. This
4279 improved generation speed by over a factor of 10 on the highest preset!)
4281 An approach which can be more scalable involves generating a grid and
4282 then tweaking it to make it soluble. This is the technique used by Mines
4283 and also by Net: first a random puzzle is generated, and then the solver
4284 is run to see how far it gets. Sometimes the solver will get stuck;
4285 when that happens, examine the area it's having trouble with, and make
4286 a small random change in that area to allow it to make more progress.
4287 Continue solving (possibly even without restarting the solver), tweaking
4288 as necessary, until the solver finishes. Then restart the solver from
4289 the beginning to ensure that the tweaks haven't caused new problems in
4290 the process of solving old ones (which can sometimes happen).
4292 This strategy works well in situations where the usual solver failure
4293 mode is to get stuck in an easily localised spot. Thus it works well
4294 for Net and Mines, whose most common failure mode tends to be that most
4295 of the grid is fine but there are a few widely separated ambiguous
4296 sections; but it would work less well for Dominosa, in which the way you
4297 get stuck is to have scoured the whole grid and not found anything you
4298 can deduce _anywhere_. Also, it relies on there being a low probability
4299 that tweaking the grid introduces a new problem at the same time as
4300 solving the old one; Mines and Net also have the property that most of
4301 their deductions are local, so that it's very unlikely for a tweak to
4302 affect something half way across the grid from the location where it was
4303 applied. In Dominosa, by contrast, a lot of deductions use information
4304 about half the grid (`out of all the sixes, only one is next to a
4305 three', which can depend on the values of up to 32 of the 56 squares in
4306 the default setting!), so this tweaking strategy would be rather less
4307 likely to work well.
4309 A more specialised strategy is that used in Solo and Slant. These
4310 puzzles have the property that they derive their difficulty from not
4311 presenting all the available clues. (In Solo's case, if all the possible
4312 clues were provided then the puzzle would already be solved; in Slant
4313 it would still require user action to fill in the lines, but it would
4314 present no challenge at all). Therefore, a simple generation technique
4315 is to leave the decision of which clues to provide until the last
4316 minute. In other words, first generate a random _filled_ grid with all
4317 possible clues present, and then gradually remove clues for as long as
4318 the solver reports that it's still soluble. Unlike the methods described
4319 above, this technique _cannot_ fail - once you've got a filled grid,
4320 nothing can stop you from being able to convert it into a viable puzzle.
4321 However, it wouldn't even be meaningful to apply this technique to (say)
4322 Pattern, in which clues can never be left out, so the only way to affect
4323 the set of clues is by altering the solution.
4325 (Unfortunately, Solo is complicated by the need to provide puzzles at
4326 varying difficulty levels. It's easy enough to generate a puzzle of
4327 _at most_ a given level of difficulty; you just have a solver with
4328 configurable intelligence, and you set it to a given level and apply the
4329 above technique, thus guaranteeing that the resulting grid is solvable
4330 by someone with at most that much intelligence. However, generating a
4331 puzzle of _at least_ a given level of difficulty is rather harder; if
4332 you go for _at most_ Intermediate level, you're likely to find that
4333 you've accidentally generated a Trivial grid a lot of the time, because
4334 removing just one number is sufficient to take the puzzle from Trivial
4335 straight to Ambiguous. In that situation Solo has no remaining options
4336 but to throw the puzzle away and start again.)
4338 A final strategy is to use the solver _during_ puzzle construction:
4339 lay out a bit of the grid, run the solver to see what it allows you to
4340 deduce, and then lay out a bit more to allow the solver to make more
4341 progress. There are articles on the web that recommend constructing
4342 Sudoku puzzles by this method (which is completely the opposite way
4343 round to how Solo does it); for Sudoku it has the advantage that you
4344 get to specify your clue squares in advance (so you can have them make
4347 Rectangles uses a strategy along these lines. First it generates a grid
4348 by placing the actual rectangles; then it has to decide where in each
4349 rectangle to place a number. It uses a solver to help it place the
4350 numbers in such a way as to ensure a unique solution. It does this by
4351 means of running a test solver, but it runs the solver _before_ it's
4352 placed any of the numbers - which means the solver must be capable of
4353 coping with uncertainty about exactly where the numbers are! It runs
4354 the solver as far as it can until it gets stuck; then it narrows down
4355 the possible positions of a number in order to allow the solver to make
4356 more progress, and so on. Most of the time this process terminates with
4357 the grid fully solved, at which point any remaining number-placement
4358 decisions can be made at random from the options not so far ruled out.
4359 Note that unlike the Net/Mines tweaking strategy described above, this
4360 algorithm does not require a checking run after it completes: if it
4361 finishes successfully at all, then it has definitely produced a uniquely
4364 Most of the strategies described above are not 100% reliable. Each
4365 one has a failure rate: every so often it has to throw out the whole
4366 grid and generate a fresh one from scratch. (Solo's strategy would
4367 be the exception, if it weren't for the need to provide configurable
4368 difficulty levels.) Occasional failures are not a fundamental problem in
4369 this sort of work, however: it's just a question of dividing the grid
4370 generation time by the success rate (if it takes 10ms to generate a
4371 candidate grid and 1/5 of them work, then it will take 50ms on average
4372 to generate a viable one), and seeing whether the expected time taken
4373 to _successfully_ generate a puzzle is unacceptably slow. Dominosa's
4374 generator has a very low success rate (about 1 out of 20 candidate grids
4375 turn out to be usable, and if you think _that's_ bad then go and look
4376 at the source code and find the comment showing what the figures were
4377 before the generation-time tweaks!), but the generator itself is very
4378 fast so this doesn't matter. Rectangles has a slower generator, but
4379 fails well under 50% of the time.
4381 So don't be discouraged if you have an algorithm that doesn't always
4382 work: if it _nearly_ always works, that's probably good enough. The one
4383 place where reliability is important is that your algorithm must never
4384 produce false positives: it must not claim a puzzle is soluble when it
4385 isn't. It can produce false negatives (failing to notice that a puzzle
4386 is soluble), and it can fail to generate a puzzle at all, provided it
4387 doesn't do either so often as to become slow.
4389 One last piece of advice: for grid-based puzzles, when writing and
4390 testing your generation algorithm, it's almost always a good idea _not_
4391 to test it initially on a grid that's square (i.e. w==h), because if the
4392 grid is square then you won't notice if you mistakenly write `h' instead
4393 of `w' (or vice versa) somewhere in the code. Use a rectangular grid for
4394 testing, and any size of grid will be likely to work after that.
4396 6.2.2. Designing textual description formats
4397 --------------------------------------------
4399 Another aspect of writing a puzzle which is worth putting some thought
4400 into is the design of the various text description formats: the format
4401 of the game parameter encoding, the game description encoding, and the
4404 The first two of these should be reasonably intuitive for a user to type
4405 in; so provide some flexibility where possible. Suppose, for example,
4406 your parameter format consists of two numbers separated by an `x' to
4407 specify the grid dimensions (`10x10' or `20x15'), and then has some
4408 suffixes to specify other aspects of the game type. It's almost always a
4409 good idea in this situation to arrange that decode_params() can handle
4410 the suffixes appearing in any order, even if encode_params() only ever
4411 generates them in one order.
4413 These formats will also be expected to be reasonably stable: users will
4414 expect to be able to exchange game IDs with other users who aren't
4415 running exactly the same version of your game. So make them robust and
4416 stable: don't build too many assumptions into the game ID format which
4417 will have to be changed every time something subtle changes in the
4420 6.3. Common how-to questions
4421 ----------------------------
4423 This section lists some common things people want to do when writing a
4424 puzzle, and describes how to achieve them within the Puzzles framework.
4426 6.3.1. Drawing objects at only one position
4427 -------------------------------------------
4429 A common phenomenon is to have an object described in the `game_state'
4430 or the `game_ui' which can only be at one position. A cursor - probably
4431 specified in the `game_ui' - is a good example.
4433 In the `game_ui', it would _obviously_ be silly to have an array
4434 covering the whole game grid with a boolean flag stating whether the
4435 cursor was at each position. Doing that would waste space, would make
4436 it difficult to find the cursor in order to do anything with it, and
4437 would introduce the potential for synchronisation bugs in which you
4438 ended up with two cursors or none. The obviously sensible way to store a
4439 cursor in the `game_ui' is to have fields directly encoding the cursor's
4442 However, it is a mistake to assume that the same logic applies to the
4443 `game_drawstate'. If you replicate the cursor position fields in the
4444 draw state, the redraw code will get very complicated. In the draw
4445 state, in fact, it _is_ probably the right thing to have a cursor flag
4446 for every position in the grid. You probably have an array for the whole
4447 grid in the drawstate already (stating what is currently displayed in
4448 the window at each position); the sensible approach is to add a `cursor'
4449 flag to each element of that array. Then the main redraw loop will look
4450 something like this (pseudo-code):
4452 for (y = 0; y < h; y++) {
4453 for (x = 0; x < w; x++) {
4454 int value = state->symbol_at_position[y][x];
4455 if (x == ui->cursor_x && y == ui->cursor_y)
4457 if (ds->symbol_at_position[y][x] != value) {
4458 symbol_drawing_subroutine(dr, ds, x, y, value);
4459 ds->symbol_at_position[y][x] = value;
4464 This loop is very simple, pretty hard to get wrong, and _automatically_
4465 deals both with erasing the previous cursor and drawing the new one,
4466 with no special case code required.
4468 This type of loop is generally a sensible way to write a redraw
4469 function, in fact. The best thing is to ensure that the information
4470 stored in the draw state for each position tells you _everything_ about
4471 what was drawn there. A good way to ensure that is to pass precisely
4472 the same information, and _only_ that information, to a subroutine that
4473 does the actual drawing; then you know there's no additional information
4474 which affects the drawing but which you don't notice changes in.
4476 6.3.2. Implementing a keyboard-controlled cursor
4477 ------------------------------------------------
4479 It is often useful to provide a keyboard control method in a basically
4480 mouse-controlled game. A keyboard-controlled cursor is best implemented
4481 by storing its location in the `game_ui' (since if it were in the
4482 `game_state' then the user would have to separately undo every cursor
4483 move operation). So the procedure would be:
4485 - Put cursor position fields in the `game_ui'.
4487 - interpret_move() responds to arrow keys by modifying the cursor
4488 position fields and returning "".
4490 - interpret_move() responds to some sort of fire button by actually
4491 performing a move based on the current cursor location.
4493 - You might want an additional `game_ui' field stating whether the
4494 cursor is currently visible, and having it disappear when a mouse
4495 action occurs (so that it doesn't clutter the display when not
4498 - You might also want to automatically hide the cursor in
4499 changed_state() when the current game state changes to one in
4500 which there is no move to make (which is the case in some types of
4503 - redraw() draws the cursor using the technique described in section
4506 6.3.3. Implementing draggable sprites
4507 -------------------------------------
4509 Some games have a user interface which involves dragging some sort of
4510 game element around using the mouse. If you need to show a graphic
4511 moving smoothly over the top of other graphics, use a blitter (see
4512 section 3.1.13 for the blitter API) to save the background underneath
4513 it. The typical scenario goes:
4515 - Have a blitter field in the `game_drawstate'.
4517 - Set the blitter field to NULL in the game's new_drawstate()
4518 function, since you don't yet know how big the piece of saved
4519 background needs to be.
4521 - In the game's set_size() function, once you know the size of the
4522 object you'll be dragging around the display and hence the required
4523 size of the blitter, actually allocate the blitter.
4525 - In free_drawstate(), free the blitter if it's not NULL.
4527 - In interpret_move(), respond to mouse-down and mouse-drag events by
4528 updating some fields in the game_ui which indicate that a drag is in
4531 - At the _very end_ of redraw(), after all other drawing has been
4532 done, draw the moving object if there is one. First save the
4533 background under the object in the blitter; then set a clip
4534 rectangle covering precisely the area you just saved (just in case
4535 anti-aliasing or some other error causes your drawing to go beyond
4536 the area you saved). Then draw the object, and call unclip().
4537 Finally, set a flag in the game_drawstate that indicates that the
4538 blitter needs restoring.
4540 - At the very start of redraw(), before doing anything else at all,
4541 check the flag in the game_drawstate, and if it says the blitter
4542 needs restoring then restore it. (Then clear the flag, so that this
4543 won't happen again in the next redraw if no moving object is drawn
4546 This way, you will be able to write the rest of the redraw function
4547 completely ignoring the dragged object, as if it were floating above
4548 your bitmap and being completely separate.
4550 6.3.4. Sharing large invariant data between all game states
4551 -----------------------------------------------------------
4553 In some puzzles, there is a large amount of data which never changes
4554 between game states. The array of numbers in Dominosa is a good example.
4556 You _could_ dynamically allocate a copy of that array in every
4557 `game_state', and have dup_game() make a fresh copy of it for every new
4558 `game_state'; but it would waste memory and time. A more efficient way
4559 is to use a reference-counted structure.
4561 - Define a structure type containing the data in question, and also
4562 containing an integer reference count.
4564 - Have a field in `game_state' which is a pointer to this structure.
4566 - In new_game(), when creating a fresh game state at the start of a
4567 new game, create an instance of this structure, initialise it with
4568 the invariant data, and set its reference count to 1.
4570 - In dup_game(), rather than making a copy of the structure for the
4571 new game state, simply set the new game state to point at the same
4572 copy of the structure, and increment its reference count.
4574 - In free_game(), decrement the reference count in the structure
4575 pointed to by the game state; if the count reaches zero, free the
4578 This way, the invariant data will persist for only as long as it's
4579 genuinely needed; _as soon_ as the last game state for a particular
4580 puzzle instance is freed, the invariant data for that puzzle will
4581 vanish as well. Reference counting is a very efficient form of garbage
4582 collection, when it works at all. (Which it does in this instance, of
4583 course, because there's no possibility of circular references.)
4585 6.3.5. Implementing multiple types of flash
4586 -------------------------------------------
4588 In some games you need to flash in more than one different way. Mines,
4589 for example, flashes white when you win, and flashes red when you tread
4592 The simple way to do this is:
4594 - Have a field in the `game_ui' which describes the type of flash.
4596 - In flash_length(), examine the old and new game states to decide
4597 whether a flash is required and what type. Write the type of flash
4598 to the `game_ui' field whenever you return non-zero.
4600 - In redraw(), when you detect that `flash_time' is non-zero, examine
4601 the field in `game_ui' to decide which type of flash to draw.
4603 redraw() will never be called with `flash_time' non-zero unless
4604 flash_length() was first called to tell the mid-end that a flash was
4605 required; so whenever redraw() notices that `flash_time' is non-zero,
4606 you can be sure that the field in `game_ui' is correctly set.
4608 6.3.6. Animating game moves
4609 ---------------------------
4611 A number of puzzle types benefit from a quick animation of each move you
4614 For some games, such as Fifteen, this is particularly easy. Whenever
4615 redraw() is called with `oldstate' non-NULL, Fifteen simply compares the
4616 position of each tile in the two game states, and if the tile is not in
4617 the same place then it draws it some fraction of the way from its old
4618 position to its new position. This method copes automatically with undo.
4620 Other games are less obvious. In Sixteen, for example, you can't just
4621 draw each tile a fraction of the way from its old to its new position:
4622 if you did that, the end tile would zip very rapidly past all the others
4623 to get to the other end and that would look silly. (Worse, it would look
4624 inconsistent if the end tile was drawn on top going one way and on the
4625 bottom going the other way.)
4627 A useful trick here is to define a field or two in the game state that
4628 indicates what the last move was.
4630 - Add a `last move' field to the `game_state' (or two or more fields
4631 if the move is complex enough to need them).
4633 - new_game() initialises this field to a null value for a new game
4636 - execute_move() sets up the field to reflect the move it just
4639 - redraw() now needs to examine its `dir' parameter. If `dir' is
4640 positive, it determines the move being animated by looking at the
4641 last-move field in `newstate'; but if `dir' is negative, it has to
4642 look at the last-move field in `oldstate', and invert whatever move
4645 Note also that Sixteen needs to store the _direction_ of the move,
4646 because you can't quite determine it by examining the row or column in
4647 question. You can in almost all cases, but when the row is precisely
4648 two squares long it doesn't work since a move in either direction looks
4649 the same. (You could argue that since moving a 2-element row left and
4650 right has the same effect, it doesn't matter which one you animate; but
4651 in fact it's very disorienting to click the arrow left and find the row
4652 moving right, and almost as bad to undo a move to the right and find the
4653 game animating _another_ move to the right.)
4655 6.3.7. Animating drag operations
4656 --------------------------------
4658 In Untangle, moves are made by dragging a node from an old position to a
4659 new position. Therefore, at the time when the move is initially made, it
4660 should not be animated, because the node has already been dragged to the
4661 right place and doesn't need moving there. However, it's nice to animate
4662 the same move if it's later undone or redone. This requires a bit of
4665 The obvious approach is to have a flag in the `game_ui' which inhibits
4666 move animation, and to set that flag in interpret_move(). The question
4667 is, when would the flag be reset again? The obvious place to do so
4668 is changed_state(), which will be called once per move. But it will
4669 be called _before_ anim_length(), so if it resets the flag then
4670 anim_length() will never see the flag set at all.
4672 The solution is to have _two_ flags in a queue.
4674 - Define two flags in `game_ui'; let's call them `current' and `next'.
4676 - Set both to FALSE in `new_ui()'.
4678 - When a drag operation completes in interpret_move(), set the `next'
4681 - Every time changed_state() is called, set the value of `current' to
4682 the value in `next', and then set the value of `next' to FALSE.
4684 - That way, `current' will be TRUE _after_ a call to changed_state()
4685 if and only if that call to changed_state() was the result of a
4686 drag operation processed by interpret_move(). Any other call to
4687 changed_state(), due to an Undo or a Redo or a Restart or a Solve,
4688 will leave `current' FALSE.
4690 - So now anim_length() can request a move animation if and only if the
4691 `current' flag is _not_ set.
4693 6.3.8. Inhibiting the victory flash when Solve is used
4694 ------------------------------------------------------
4696 Many games flash when you complete them, as a visual congratulation for
4697 having got to the end of the puzzle. It often seems like a good idea to
4698 disable that flash when the puzzle is brought to a solved state by means
4699 of the Solve operation.
4701 This is easily done:
4703 - Add a `cheated' flag to the `game_state'.
4705 - Set this flag to FALSE in new_game().
4707 - Have solve() return a move description string which clearly
4708 identifies the move as a solve operation.
4710 - Have execute_move() respond to that clear identification by setting
4711 the `cheated' flag in the returned `game_state'. The flag will
4712 then be propagated to all subsequent game states, even if the user
4713 continues fiddling with the game after it is solved.
4715 - flash_length() now returns non-zero if `oldstate' is not completed
4716 and `newstate' is, _and_ neither state has the `cheated' flag set.
4718 6.4. Things to test once your puzzle is written
4719 -----------------------------------------------
4721 Puzzle implementations written in this framework are self-testing as far
4722 as I could make them.
4724 Textual game and move descriptions, for example, are generated and
4725 parsed as part of the normal process of play. Therefore, if you can make
4726 moves in the game _at all_ you can be reasonably confident that the
4727 mid-end serialisation interface will function correctly and you will
4728 be able to save your game. (By contrast, if I'd stuck with a single
4729 make_move() function performing the jobs of both interpret_move() and
4730 execute_move(), and had separate functions to encode and decode a game
4731 state in string form, then those functions would not be used during
4732 normal play; so they could have been completely broken, and you'd never
4733 know it until you tried to save the game - which would have meant you'd
4734 have to test game saving _extensively_ and make sure to test every
4735 possible type of game state. As an added bonus, doing it the way I did
4736 leads to smaller save files.)
4738 There is one exception to this, which is the string encoding of the
4739 `game_ui'. Most games do not store anything permanent in the `game_ui',
4740 and hence do not need to put anything in its encode and decode
4741 functions; but if there is anything in there, you do need to test game
4742 loading and saving to ensure those functions work properly.
4744 It's also worth testing undo and redo of all operations, to ensure that
4745 the redraw and the animations (if any) work properly. Failing to animate
4746 undo properly seems to be a common error.
4748 Other than that, just use your common sense.