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&$KRrichard@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