2 * Output bits of a rule file for Golly for a Conway-like cellular
3 * automaton displayed with smoothing reminiscent of the Mullard
4 * SAA5050 Teletext character generation (aka BBC "MODE 7").
6 * The resulting automaton flips the world between two states:
7 * one where everything is one of two states, and one where an
8 * expanded set of 32 states is used (16 'off', 16 'on') according
9 * to what diagonals are required for the smoothing. Each of the
10 * expanded states has an associated icon.
12 * In the first step we go from two states to 32 implementing the
13 * smoothing algorithm as a transition function on a 3x3 neighbourhood.
14 * In the second step we go from 32 back to 2 with a Conway-derived
15 * transition function, again on a 3x3 neighbourhood (this step is not
16 * in this source file).
17 * (FIXME: this would be more slick, although probably even less
18 * efficient, implemented in one go with a 5x5 neighbourhood, which
19 * Golly does support.)
21 * The smoothing algorithm and graphics are derived from 'Bedstead' by
22 * Ben Harris: http://bjh21.me.uk/bedstead/
23 * The idea of applying this smoothing to Conway's Life can be blamed
28 * This file is part of Bedbugs.
29 * Copyright (C) 2014 Jacob Nevins.
30 * Portions copyright (C) 2009 Ben Harris (see below).
32 * This program is free software; you can redistribute it and/or modify
33 * it under the terms of the GNU General Public License as published by
34 * the Free Software Foundation; either version 2 of the License, or
35 * (at your option) any later version.
37 * This program is distributed in the hope that it will be useful,
38 * but WITHOUT ANY WARRANTY; without even the implied warranty of
39 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
40 * GNU General Public License for more details.
42 * You should have received a copy of the GNU General Public License along
43 * with this program; if not, write to the Free Software Foundation, Inc.,
44 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
46 * Website: http://www.chiark.greenend.org.uk/ucgi/~jacobn/git/bedbugs.git/
49 * This source file, bedbugs.c, is based on
50 * http://bjh21.me.uk/bedstead/ bedstead.c bzr r137
51 * from which the following bits of the copyright notice and documentation
54 * [...] the file is covered by the following:
56 * Copyright (c) 2009 Ben Harris.
58 * Permission is hereby granted, free of charge, to any person
59 * obtaining a copy of this software and associated documentation files
60 * (the "Software"), to deal in the Software without restriction,
61 * including without limitation the rights to use, copy, modify, merge,
62 * publish, distribute, sublicense, and/or sell copies of the Software,
63 * and to permit persons to whom the Software is furnished to do so,
64 * subject to the following conditions:
66 * The above copyright notice and this permission notice shall be
67 * included in all copies or substantial portions of the Software.
69 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
70 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
71 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
72 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
73 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
74 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
75 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
79 * This [was once] a program to construct an outline font from a bitmap.
80 * It's based on the character-rounding algorithm of the Mullard SAA5050
81 * series of Teletext character generators, and thus works best on
82 * character shapes in the same style of those of the SAA5050. This
83 * file includes all of the glyphs from the SAA5050, SAA5051, SAA5052,
84 * SAA5053, SAA5054, SAA5055, SAA5056, and SAA5057. The output is a
85 * Spline Font Database file suitable for feeding to Fontforge.
87 * The character-smoothing algorithm of the SAA5050 and friends is
88 * a fairly simple means of expanding a 5x9 pixel character to 10x18
89 * pixels for use on an interlaced display. All it does is to detect
90 * 2x2 clumps of pixels containing a diagonal line and add a couple of
91 * subpixels to it, like this:
93 * . # -> . . # # -> . . # # or # . -> # # . . -> # # . .
94 * # . . . # # . # # # . # # # . . # # # .
95 * # # . . # # # . . . # # . # # #
96 * # # . . # # . . . . # # . . # #
98 * This is applied to every occurrence of these patterns, even when
99 * they overlap, and the result is that thin diagonal lines are
100 * smoothed out while other features mostly remain the same.
102 * One way of extending this towards continuity would be to repeatedly
103 * double the resolution and add more pixels to diagonals each time,
104 * but this ends up with the diagonals being much too heavy. Instead,
105 * in places where the SAA5050 would add pixels, this program adds a
106 * largeish triangle to each unfilled pixel, and removes a small
107 * triangle from each filled one, something like this:
109 * . # -> . . # # -> . . / # or # . -> # # . . -> # \ . .
110 * # . . . # # . / # / . # # # . . \ # \ .
111 * # # . . / # / . . . # # . \ # \
112 * # # . . # / . . . . # # . . \ #
114 * The position of the lines is such that on a long diagonal line, the
115 * amount of filled space is the same as in the rounded bitmap. There
116 * are a few additional complications, in that the trimming of filled
117 * pixels can leave odd gaps where a diagonal stem joins another one,
118 * so the code detects this and doesn't trim in these cases:
120 * . # # -> . . # # # # -> . . / # # # -> . . / # # #
121 * # . . . . # # # # . / # / # # . / # # # #
122 * # # . . . . / # / . . . / # / . . .
123 * # # . . . . # / . . . . # / . . . .
138 return calloc(size*size, sizeof(bool));
141 static void output(bool *r, int size) {
143 for (y=0; y<size; y++) {
145 for (x=0; x<size; x++) {
146 putchar(r[x+y*size] ? 'A' : '.');
154 triangle(bool *r, int size, int startpos, bool top, bool left)
157 for (y = 0; y < startpos; y++) {
158 for (x = 0; x < startpos-y; x++) {
177 triangles(bool *r, int size, int startpos, int bl, int br, int tr, int tl)
180 triangle(r, size, startpos, false, true);
183 triangle(r, size, startpos, false, false);
186 triangle(r, size, startpos, true, false);
189 triangle(r, size, startpos, true, true);
194 whitepixel(bool *r, int size, int bl, int br, int tr, int tl)
196 /* wrt blackpixel(): -1 for adjacency, -1 for gridlines
197 * (which Golly has no apparent way to suppress :/ ) */
198 const int startpos = size-size/4-2;
199 triangles(r, size, startpos, bl, br, tr, tl);
203 blackpixel(bool *r, int size, int bl, int br, int tr, int tl)
205 const int startpos = size/4;
207 triangles(r, size, startpos, bl, br, tr, tl);
208 for (i=0; i<size*size; i++) {
215 /* Output smoothing rules as a Golly rule table mapping from
216 * (0,1) to an expanded set of states that we can hang icons
217 * from. (The smoothing algorithm requires a 3x3 neighbourhood,
218 * which is fortuitous.) */
220 /* Index into small bitmap */
221 #define GETPIX(x,y) (!!(iter & 1u<<((y)*3+(x))))
222 #define L GETPIX(x-1, y)
223 #define R GETPIX(x+1, y)
224 #define U GETPIX(x, y-1)
225 #define D GETPIX(x, y+1)
226 #define UL GETPIX(x-1, y-1)
227 #define UR GETPIX(x+1, y-1)
228 #define DL GETPIX(x-1, y+1)
229 #define DR GETPIX(x+1, y+1)
231 /* Iterate over all neighbourhoods (9 cells) */
233 for (iter = 0; iter < 1u<<9; iter++) {
234 int state, x = 1, y = 1;
235 /* The core of the Bedstead smoothing algorithm
236 * from Ben Harris. */
240 /* Assume filled in */
241 tl = tr = bl = br = true;
242 /* Check for diagonals */
243 if ((UL && !U && !L) || (DR && !D && !R))
245 if ((UR && !U && !R) || (DL && !D && !L))
248 if (L || UL || U) tl = true;
249 if (R || UR || U) tr = true;
250 if (L || DL || D) bl = true;
251 if (R || DR || D) br = true;
252 /* On states are 18..33 */
253 state = 2 + 16 + (bl | br<<1 | tr<<2 | tl<<3);
258 tl = tr = bl = br = false;
259 /* white pixel -- just diagonals */
260 if (L && U && !UL) tl = true;
261 if (R && U && !UR) tr = true;
262 if (L && D && !DL) bl = true;
263 if (R && D && !DR) br = true;
264 /* Off states are 2..17 */
265 state = 2 + (bl | br<<1 | tr<<2 | tl<<3);
268 /* Special case: we don't want to try to
269 * flip all of infinite empty space between
270 * 0 and 2 every step (this has odd effects
275 /* Output rule in Golly rule format
276 * (FIXME completely unoptimised) */
277 printf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n",
278 GETPIX(x,y),U,UR,R,DR,D,DL,L,UL,state);
284 /* Bedbugs icons. In each size supported by Golly,
285 * draw one icon per state, in the XPM format Golly wants.
286 * This does not actually depend on bedstead() at all.
287 * (FIXME: but it could. Some of the states we generate icons
288 * and rules for are not actually reachable. We could spot
289 * unused states above and avoid generating icons or rules for
291 * (FIXME: we could also output pre-Golly-2.5 format icons) */
293 const int sizes[] = {7, 15, 31};
296 size_index < sizeof(sizes)/sizeof(sizes[0]);
298 int size = sizes[size_index], state;
299 printf("XPM\n/* width height num_colors chars_per_pixel */\n");
300 printf("\"%d %d 2 1\"\n", size, size*33);
301 /* We have to have a non-greyscale colour to trigger Golly's
302 * "multi-colour icon" mode, so that we can make some states'
303 * non-icon versions black. And it's not sufficient to
304 * include an unreferenced, colour, so our 'on' state is
306 printf("/* colors */\n\". c #000000\"\n\"A c #FEFEFF\"\n");
307 /* icons never used for state 0 */
308 for (state = 1; state < 34; state++) {
309 bool *r = blank(size);
311 ; /* Conway 'off': nothing */
312 } else if (state == 1) {
313 /* Conway 'on': everything */
314 memset(r, 1, size*size*sizeof(*r));
315 } else if (state < 16+2) {
317 int bits = ~(state-2);
318 whitepixel(r, size, bits&1, bits&2, bits&4, bits&8);
321 int bits = state-16-2;
322 blackpixel(r, size, bits&1, bits&2, bits&4, bits&8);
324 printf("/* icon for state %d */\n", state);
335 for (i=0; i<34; i++) {
345 lvl = (i >= 2+16) ? 255 : 0;
348 printf("%2d %3d %3d %3d\n", i, lvl, lvl, lvl);
352 int main(int argc, char *argv[])
354 while (!feof(stdin)) {
355 char l[100]; /* bleah */
356 if (!fgets(l, sizeof(l), stdin)) {
359 if (strlen(l) == sizeof(l)-1) {
360 fprintf(stderr, "Long input line; possible truncation; I suck\n");
363 if (strlen(l) >= 2 && l[0] == '@' && l[1] == '@') {
364 size_t n = strcspn(l+2, "\n");
365 if (strncmp(l+2, "BEDSTEAD", n) == 0) {
367 } else if (strncmp(l+2, "ICONS", n) == 0) {
369 } else if (strncmp(l+2, "COLORS", n) == 0) {
372 /* Bodily insert named file on stdout. */
375 if (!(f = fopen(l+2, "r"))) {
376 fprintf(stderr, "Couldn't open '%s': %s\n", l+2,
381 char buf[2048]; /* also bleah */
382 size_t n = fread(buf, 1, sizeof(buf), f);
383 fwrite(buf, 1, n, stdout);
384 } while (!feof(f) && !ferror(f));
386 fprintf(stderr, "Error reading '%s': %s\n", l+2,