X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~jacobn/git?p=bedbugs.git;a=blobdiff_plain;f=src%2Fbedbugs.c;h=f703ad673011086f42bb472c28dc8815e3202728;hp=ef9fd3cec796f58a0132e2a5a9e1d0517e1f2ebf;hb=9ca5a58108ea873729fb129d50654356785fae3f;hpb=f0cabf59def2699e8d877b944dc1e3c06cb63af0 diff --git a/src/bedbugs.c b/src/bedbugs.c index ef9fd3c..f703ad6 100644 --- a/src/bedbugs.c +++ b/src/bedbugs.c @@ -1,6 +1,55 @@ /* - * Relevant bits of original copyright notice from - * http://bjh21.me.uk/bedstead/ bedstead.c #137: + * Output bits of a rule file for Golly for a Conway-like cellular + * automaton displayed with smoothing reminiscent of the Mullard + * SAA5050 Teletext character generation (aka BBC "MODE 7"). + * + * The resulting automaton flips the world between two states: + * one where everything is one of two states, and one where an + * expanded set of 32 states is used (16 'off', 16 'on') according + * to what diagonals are required for the smoothing. Each of the + * expanded states has an associated icon. + * + * In the first step we go from two states to 32 implementing the + * smoothing algorithm as a transition function on a 3x3 neighbourhood. + * In the second step we go from 32 back to 2 with a Conway-derived + * transition function, again on a 3x3 neighbourhood (this step is not + * in this source file). + * (FIXME: this would be more slick, although probably even less + * efficient, implemented in one go with a 5x5 neighbourhood, which + * Golly does support.) + * + * The smoothing algorithm and graphics are derived from 'Bedstead' by + * Ben Harris: http://bjh21.me.uk/bedstead/ + * The idea of applying this smoothing to Conway's Life can be blamed + * on Simon Tatham. + */ + +/* + * This file is part of Bedbugs. + * Copyright (C) 2014 Jacob Nevins. + * Portions copyright (C) 2009 Ben Harris (see below). + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Website: http://www.chiark.greenend.org.uk/ucgi/~jacobn/git/bedbugs-git/ + * + * + * This source file, bedbugs.c, is based on + * http://bjh21.me.uk/bedstead/ bedstead.c bzr r137 + * from which the following bits of the copyright notice and documentation + * remain relevant: * * [...] the file is covered by the following: * @@ -27,8 +76,8 @@ * SOFTWARE. */ /* - * This is a program to construct an outline font from a bitmap. It's - * based on the character-rounding algorithm of the Mullard SAA5050 + * This [was once] a program to construct an outline font from a bitmap. + * It's based on the character-rounding algorithm of the Mullard SAA5050 * series of Teletext character generators, and thus works best on * character shapes in the same style of those of the SAA5050. This * file includes all of the glyphs from the SAA5050, SAA5051, SAA5052, @@ -73,18 +122,6 @@ * # # . . . . / # / . . . / # / . . . * # # . . . . # / . . . . # / . . . . * - * That is the interesting part of the program, and is in the dochar() - * function. Most of the rest is just dull geometry to join all the - * bits together into a sensible outline. Much of the code is wildly - * inefficient -- O(n^2) algorithms aren't much of a problem when you - * have at most a few thousand points to deal with. - * - * A rather nice feature of the outlines produced by this program is - * that when rasterised at precisely 10 or 20 pixels high, they - * produce the input and output respectively of the character-rounding - * process. While there are obious additional smoothings that could - * be applied, doing so would probably lose this nice property. - * * [...] */ @@ -154,7 +191,8 @@ triangles(bool *r, int size, int startpos, int bl, int br, int tr, int tl) static void whitepixel(bool *r, int size, int bl, int br, int tr, int tl) { - /* wrt blackpixel(): -1 for adjacency, -1 for gridlines */ + /* wrt blackpixel(): -1 for adjacency, -1 for gridlines + * (which Golly has no apparent way to suppress :/ ) */ const int startpos = size-size/4-2; triangles(r, size, startpos, bl, br, tr, tl); } @@ -172,6 +210,16 @@ blackpixel(bool *r, int size, int bl, int br, int tr, int tl) int main(int argc, char *argv[]) { + + /* FIXME: output a complete rule file rather than a heap of + * fragments requiring manual assembly */ + + /* Bedbugs step 1: output smoothing rules as a Golly rule + * table mapping from (0,1) to an expanded set of states that + * we can hang icons from. (The smoothing algorithm requires + * a 3x3 neighbourhood, which is fortuitous.) */ + + /* Index into small bitmap */ #define GETPIX(x,y) (!!(iter & 1u<<((y)*3+(x)))) #define L GETPIX(x-1, y) #define R GETPIX(x+1, y) @@ -182,9 +230,12 @@ int main(int argc, char *argv[]) #define DL GETPIX(x-1, y+1) #define DR GETPIX(x+1, y+1) + /* Iterate over all neighbourhoods (9 cells) */ int iter; for (iter = 0; iter < 1u<<9; iter++) { int state, x = 1, y = 1; + /* The core of the Bedstead smoothing algorithm + * from Ben Harris. */ if (GETPIX(x, y)) { bool tl, tr, bl, br; @@ -200,6 +251,7 @@ int main(int argc, char *argv[]) if (R || UR || U) tr = true; if (L || DL || D) bl = true; if (R || DR || D) br = true; + /* On states are 18..33 */ state = 2 + 16 + (bl | br<<1 | tr<<2 | tl<<3); } else { bool tl, tr, bl, br; @@ -211,11 +263,23 @@ int main(int argc, char *argv[]) if (R && U && !UR) tr = true; if (L && D && !DL) bl = true; if (R && D && !DR) br = true; + /* Off states are 2..17 */ state = 2 + (bl | br<<1 | tr<<2 | tl<<3); } + /* Output rule in Golly rule format + * (FIXME completely unoptimised) */ printf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n", GETPIX(x,y),U,UR,R,DR,D,DL,L,UL,state); } + + /* Bedbugs step 2: icons. In each size supported by Golly, + * draw one icon per state, in the XPM format Golly wants. + * This does not actually depend on step 1 at all. + * (FIXME: but it could. Some of the states we generate icons + * and rules for are not actually reachable. We could spot + * unused states above and avoid generating icons or rules for + * them.) + * (FIXME: we could also output pre-Golly-2.5 format icons) */ { const int sizes[] = {7, 15, 31}; int size_index; @@ -230,14 +294,16 @@ int main(int argc, char *argv[]) for (state = 1; state < 34; state++) { bool *r = blank(size); if (state == 0) { - ; /* nothing */ + ; /* Conway 'off': nothing */ } else if (state == 1) { - /* everything */ + /* Conway 'on': everything */ memset(r, 1, size*size*sizeof(*r)); } else if (state < 16+2) { + /* Bedstead 'off' */ int bits = ~(state-2); whitepixel(r, size, bits&1, bits&2, bits&4, bits&8); } else { + /* Bedstead 'on' */ int bits = state-16-2; blackpixel(r, size, bits&1, bits&2, bits&4, bits&8); }