wjc@eddie.MIT.EDU (Bill Chiarchiaro) (06/03/87)
I hope this question doesn't seem too archeological... I am trying to find the algorithm for the Munching Squares graphics hack. This was, I believe, originally done on a PDP-1 at MIT in the early 60's, and has been used as a graphics demo on some more recent hardware (MicroAngelo graphics board, Lisp Machines, etc.). I remember that the algorithm consisted of some clever XOR'ing of a seed value with the contents of your graphics memory, but I can't recall any more than that. Any help would be appreciated. Thanks, Bill wjc@eddie.mit.edu
jimc@iscuva.UUCP (06/04/87)
In article <6004@eddie.MIT.EDU> wjc@eddie.MIT.EDU (Bill Chiarchiaro) writes: > >I am trying to find the algorithm for the Munching Squares >graphics hack. This was, I believe, originally done on a PDP-1 >at MIT in the early 60's, and has been used as a graphics demo >on some more recent hardware (MicroAngelo graphics board, >Lisp Machines, etc.). Anyone who knows please post this! I have access to a MicroAngelo, and I've been fascinated by the program, but I don't relish the thought of going in with a disassembler to find out what it is. I'm interested in porting this to one of our new machines. +----------------+ ! II CCCCCC ! Jim Cathey ! II SSSSCC ! ISC Systems Corp. ! II CC ! Spokane, WA ! IISSSS CC ! UUCP: ihnp4!tektronix!reed!iscuva!jimc ! II CCCCCC ! (509)927-5757 +----------------+ "With excitement like this, who is needing enemas?"
wjc@mit-eddie.UUCP (06/04/87)
I received two replies to my question, and also looked at the code for the munching squares demo on Symbolics Lisp machines. The algorithm is as follows: Assume a square bitmap with the number of pixels along a side equal to a power of 2, say 2^N. Get an N-bit number from the user, this is the SEED. Clear an N-bit accumulator, ACC. Now loop on the following statements: Set ACC = ACC + SEED (don't worry about overflow, just let it wrap around) Move the lower N bits of ACC into an N-bit variable X. Move (the upper N bits of ACC) xor X into an N-bit varible Y. Invert the state of the pixel at (X, Y). That's the whole thing. You can let it run forever, however all states will have been seen after 2^(2N+1) iterations. Good seed values are: 1, 2, 401, 10421, 11111, 100001, and 100020. These are in octal. Have fun. Bill
wjc@mit-eddie.UUCP (06/05/87)
In my description of the Munching Squares algorithm, I said that SEED and ACC are N bits long. They should each be 2N bits long. To clear things up: If you have a bitmap that is 256 pixels by 256 pixels, then SEED and ACC should each be 16 bits long. X and Y should each be 8 bits long. Sorry for the confusion. Bill
garrity@garrity.applicon.UUCP (06/08/87)
If you use SunView, the following implementation of munching squares makes a pretty good replacement for the default lockscreen. If you are sick of that life game, simply compile this program into a file called munch, and then type "lockscreen munch" instead of lockscreen. #include <stdio.h> #include <pixrect/pixrect_hs.h> #include <signal.h> #define SIZE 1280 int alarm_handler(); int restart; main(argc, argv) int argc; char *argv[]; { int seed, acc, fd, x, y; struct pixrect *pr; signal(SIGALRM, alarm_handler); alarm(30); while (1) { if (argc > 1) sscanf(argv[1], "%ld", &seed); else { srandom(time(0)); seed = random(); } acc = seed; pr = pr_open("/dev/fb"); pr_rop(pr, 0, 0, SIZE, SIZE, PIX_SET, 0, 0, 0); restart = 0; while (!restart) { x = acc & 255; y = (acc >> 8) & 255; pr_rop(pr, x * 5, y * 5, 5, 5, PIX_SRC ^ PIX_DST | PIX_COLOR(1), 0, 0, 0); acc += seed; } } } int alarm_handler(sig, code) int sig, code; { restart = 1; alarm(30); } -- Mike Garrity -- -- Asking is just polite demanding. -- Max Headroom -- -- snail: Applicon, a division of Schlumberger Systems, Inc. -- 829 Middlesex Tpk. -- P.O. box 7004 -- Billerica MA, 01821 -- -- uucp: {allegra|decvax|mit-eddie|utzoo}!linus!raybed2!applicon!garrity -- {amd|bbncca|cbosgd|wjh12|ihnp4|yale}!ima!applicon!h iK&$KR
richard@gryphon.CTS.COM (Richard Sexton) (06/09/87)
In article <536@iscuva.ISCS.COM>, jimc@iscuva.ISCS.COM (Jim Cathey) writes: > In article <6004@eddie.MIT.EDU> wjc@eddie.MIT.EDU (Bill Chiarchiaro) writes: > > > >I am trying to find the algorithm for the Munching Squares > >graphics hack. This was, I believe, originally done on a PDP-1 > >at MIT in the early 60's, and has been used as a graphics demo > >on some more recent hardware (MicroAngelo graphics board, > >Lisp Machines, etc.). > > Anyone who knows please post this! I have access to a MicroAngelo, and I've > been fascinated by the program, but I don't relish the thought of going in > with a disassembler to find out what it is. I'm interested in porting this > to one of our new machines. > > +----------------+ > ! II CCCCCC ! Jim Cathey > ! II SSSSCC ! ISC Systems Corp. > ! II CC ! Spokane, WA > ! IISSSS CC ! UUCP: ihnp4!tektronix!reed!iscuva!jimc > ! II CCCCCC ! (509)927-5757 > +----------------+ > "With excitement like this, who is needing enemas?" ok at SIGGRAPH '74 BITMAP GRAPHICS course notes. This *may* be what you want. ^^ Look, a baby line eater, a half word eater. Isn't it cute ? -- Richard Sexton INTERNET: richard@gryphon.CTS.COM UUCP: {akgua, hplabs!hp-sdd, sdcsvax, ihnp4, nosc}!crash!gryphon!richard