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 * # # . . . . # / . . . . # / . . . .
136 return calloc(size*size, sizeof(bool));
139 static void output(bool *r, int size) {
141 for (y=0; y<size; y++) {
143 for (x=0; x<size; x++) {
144 putchar(r[x+y*size] ? 'A' : '.');
152 triangle(bool *r, int size, int startpos, bool top, bool left)
155 for (y = 0; y < startpos; y++) {
156 for (x = 0; x < startpos-y; x++) {
175 triangles(bool *r, int size, int startpos, int bl, int br, int tr, int tl)
178 triangle(r, size, startpos, false, true);
181 triangle(r, size, startpos, false, false);
184 triangle(r, size, startpos, true, false);
187 triangle(r, size, startpos, true, true);
192 whitepixel(bool *r, int size, int bl, int br, int tr, int tl)
194 /* wrt blackpixel(): -1 for adjacency, -1 for gridlines
195 * (which Golly has no apparent way to suppress :/ ) */
196 const int startpos = size-size/4-2;
197 triangles(r, size, startpos, bl, br, tr, tl);
201 blackpixel(bool *r, int size, int bl, int br, int tr, int tl)
203 const int startpos = size/4;
205 triangles(r, size, startpos, bl, br, tr, tl);
206 for (i=0; i<size*size; i++) {
211 int main(int argc, char *argv[])
214 /* FIXME: output a complete rule file rather than a heap of
215 * fragments requiring manual assembly */
217 /* Bedbugs step 1: output smoothing rules as a Golly rule
218 * table mapping from (0,1) to an expanded set of states that
219 * we can hang icons from. (The smoothing algorithm requires
220 * a 3x3 neighbourhood, which is fortuitous.) */
222 /* Index into small bitmap */
223 #define GETPIX(x,y) (!!(iter & 1u<<((y)*3+(x))))
224 #define L GETPIX(x-1, y)
225 #define R GETPIX(x+1, y)
226 #define U GETPIX(x, y-1)
227 #define D GETPIX(x, y+1)
228 #define UL GETPIX(x-1, y-1)
229 #define UR GETPIX(x+1, y-1)
230 #define DL GETPIX(x-1, y+1)
231 #define DR GETPIX(x+1, y+1)
233 /* Iterate over all neighbourhoods (9 cells) */
235 for (iter = 0; iter < 1u<<9; iter++) {
236 int state, x = 1, y = 1;
237 /* The core of the Bedstead smoothing algorithm
238 * from Ben Harris. */
242 /* Assume filled in */
243 tl = tr = bl = br = true;
244 /* Check for diagonals */
245 if ((UL && !U && !L) || (DR && !D && !R))
247 if ((UR && !U && !R) || (DL && !D && !L))
250 if (L || UL || U) tl = true;
251 if (R || UR || U) tr = true;
252 if (L || DL || D) bl = true;
253 if (R || DR || D) br = true;
254 /* On states are 18..33 */
255 state = 2 + 16 + (bl | br<<1 | tr<<2 | tl<<3);
260 tl = tr = bl = br = false;
261 /* white pixel -- just diagonals */
262 if (L && U && !UL) tl = true;
263 if (R && U && !UR) tr = true;
264 if (L && D && !DL) bl = true;
265 if (R && D && !DR) br = true;
266 /* Off states are 2..17 */
267 state = 2 + (bl | br<<1 | tr<<2 | tl<<3);
269 /* Output rule in Golly rule format
270 * (FIXME completely unoptimised) */
271 printf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n",
272 GETPIX(x,y),U,UR,R,DR,D,DL,L,UL,state);
275 /* Bedbugs step 2: icons. In each size supported by Golly,
276 * draw one icon per state, in the XPM format Golly wants.
277 * This does not actually depend on step 1 at all.
278 * (FIXME: but it could. Some of the states we generate icons
279 * and rules for are not actually reachable. We could spot
280 * unused states above and avoid generating icons or rules for
282 * (FIXME: we could also output pre-Golly-2.5 format icons) */
284 const int sizes[] = {7, 15, 31};
287 size_index < sizeof(sizes)/sizeof(sizes[0]);
289 int size = sizes[size_index], state;
290 printf("XPM\n/* width height num_colors chars_per_pixel */\n");
291 printf("\"%d %d 2 1\"\n", size, size*33);
292 printf("/* colors */\n\". c #000000\"\n\"A c #FFFFFF\"\n");
293 /* icons never used for state 0 */
294 for (state = 1; state < 34; state++) {
295 bool *r = blank(size);
297 ; /* Conway 'off': nothing */
298 } else if (state == 1) {
299 /* Conway 'on': everything */
300 memset(r, 1, size*size*sizeof(*r));
301 } else if (state < 16+2) {
303 int bits = ~(state-2);
304 whitepixel(r, size, bits&1, bits&2, bits&4, bits&8);
307 int bits = state-16-2;
308 blackpixel(r, size, bits&1, bits&2, bits&4, bits&8);
310 printf("/* icon for state %d */\n", state);