* AtoBaroundObstacle[LongDescr][MPEG] Bitpict figures out how to draw automatically the shortest possible line (city-block metric) from object A to object B while avoiding the "Obstacle."
* BoundingBox.reversed[LongDescr] [MPEG] Rules take arbitrary shapes and fill them out to their bounding box. The letters of THE END were so modified, and the sequence shown backwards to go from the boxes to the lettering.
* CntxtFreeStrngGrmr [LongDescr] [MPEG] Context Free String Grammar rewrite system, implemented in BITPICTS. The tricky part is getting the locally oriented bitpict system to globally move everything to the right of the insertion point.
* TheEnd.Components[LongDescr]
[MPEG]
Elegant
and complete three rule algorithm for reducing connected components to
dots, handling loops, blobs, and efficient tip-nibbling
* BallsAndRamps [LongDescr] [MPEG] Two simple bitpict rules allow "balls" to flow down out of a hopper and pile up below.
* NewtonApple [LongDescr] [MPEG] An "apple" falls from a tree and goes "THUNK!" when it hits young Isaac Newton on the head.
* DiffusionLtdAggrgtn [LongDescr] [MPEG] Points appear and randomly wander until hitting something, whereupon they stick forming an intricate accumulation.
* TheEnd.Bernoulli [LongDescr]
[MPEG]
Pixels
of the characters of the words "THE END" fall and bounce through a triangular
pattern of "pins" to generate a binomial distribution.
* FindLongestStick [LongDescr] [MPEG] Finds the longest of a set of sticks, using Martin Gardner's physical computation algorithm.
* GearsAndRods.color [LongDescr] [MPEG] Bitpict rules can solve the problem of determining which way the final gear will turn when the first rod is pushed.
* MazeWalker [LongDescr] [MPEG] Two-rule system implements the "keep your lefthand on the wall" strategy for solving a simply-connected maze.
* RomanAddition [LongDescr]
[MPEG]
Correctly
adds up several lines of Roman Numerals.
GraphicalPaint.House[LongDescr] [MPEG] Rules move a paint brush icon over to a can of paint, where it picks up paint, and then proceeds to paint some houses.
* PacMan [LongDescr] [MPEG] Rules play a simple version of the old video game PacMan.
* MacFileToTrash [LongDescr]
[MPEG]
Rules
simulate the Macintosh interaction of selecting a file and dragging to
the trash.
* TheEnd.Paint [LongDescr]
[MPEG]
Paint
brush comes by and paints the interior of a "THE END" sign.
* FlyingCrosses [LongDescr] [MPEG] Crosses fly acoss the screen and bounce off of obstacles.
* FlyingBarsYikes [LongDescr]
[MPEG]
A
1x2 bar flies around ricocheting off dots and wreaking havoc when it hits
the walls.
* AtoBaroundObstacle [ShortDescr] [MPEG]
This example shows both high level and component low level algorithms. At the high level it shows an example of what might be called "Field Based Graphics" where a field defined over the whole 2D surface shapes the ways lines are drawn. In this case BITPICT figures out how to draw automatically the shortest possible line (city-block metric) from object A to object B while avoiding the "Obstacle." This is accomplished in stages. First a set of rules grows a buffer zone, one pixel layer at a time, around the obstacle. Second, another set of rules grows a distance field around the target object, B. The iso-distance contours of the field are layed out one pixel layer at a time. A down-hill "walker" will travel down this field later. Note that the contours need only be rendered mod 3, i.e., by a repeating sequence of three colored layers. If only two layers were used, the contour lines would be well defined, but the walker, siting on a countour would have know way of knowing which of its two neighboring contours was up-hill vs. down-hill. With three colors cycling in fixed sequence, it is always possible to tell which way is down hill. (Three and only three are needed). Once the mod3 field is finished, another set of rules implements the walker who begins at source A and travels locally downhill across the field lines, leaving a brighter chalk line behind. After the shortest path is done, all the infrastructure colored bits can be removed (not shown in the MPEG), leaving just the shortest path curve around the obstacle.
The shortest path part of this example is quite general and can be used to find the shortest paths from an arbitrary number of sources to their respective closest sink (or sinks) around arbitrary obstacles.
* BoundingBox.reversed[ShortDescr] [MPEG]
This mpeg is a trick used as a closing segment of a presentation. It is a backwards replay of a basic bounding box algorithm. In forward order it would show a set of rules that can take arbitrary shapes and fill them out to their bounding box. The letters of THE END were so modified, and the sequence shown backwards to go from the boxes to the lettering.
* CntxtFreeStrngGrmr [ShortDescr] [MPEG]
This example also shows both high level and component low level algorithms. At the high level it is an implementation of a Context Free String Grammar rewrite system, implemented in BITPICTS. There are bitpict rules related to the string grammar rewrites. These are done by the six rules on the left which rewrite a single character to be the leftmost of the two replacing characters. The rightmost character is written in a special brownish color *below* the line of the string. The tricky part is getting bitpict to insert this second character into the line above it -- something which requires the locally oriented bitpict system to globally move everything to the right of the insertion point over to make room. This is accomplished by the three rules in the middle column and a forth at the top of the next column. The rule at the bottom of the second column from the right then moves the brown pixels (below the line) up to their rightful position above the line. The remaining rules just clean up various color changes that were keeping track of state along the way.
* TheEnd.Components [ShortDescr] [MPEG]
This example is a more elegant and thorough algorithm for reducing connected
components to dots than that used in the Count Components example. That
example could not handle loops or blobs, and required three rules to do
the nibbling. This system uses masked bitpicts and takes care of all these
problems in total of three rules. One high priority rule (left) nibbles
away at blobs. The second, lower priority rule, then nibbles away at tips.
Using a cross-shaped mask it covers all the cases in the first phase of
the Count Components example. The third, lowest priority rule is used to
break loops, firing exactly once for each loop, after each of which times
the second rule takes over again for a while, until only dots are left.
* BallsAndRamps [ShortDescr] [MPEG]
Two simple bitpict rules allow "balls" to flow down out of a hopper and pile up below. The first says a ball with nothing below it falls. The second says a ball touching a ramp slides down and to the side. Together they can simulate fairly complex behavior of balls with hoppers and baffles. Interestingly, it captures well qualitative behavior like the wider the opening of the hopper, the faster it empties out, etc.
* NewtonApple [ShortDescr] [MPEG]
In this example, a critical "apple" is not well attached to the tree and falls hitting young Isaac Newton on the head with a "THUNK!" The first rule simply says an "apple" unsupported from above or below, falls one pixel. A second rule says that an apple falling onto a horizontal surface goes "THUNK!" Thus the consequences of the initial picture can be "deduced" without recourse to any sentential representations.
* DiffusionLtdAggrgtn [ShortDescr] [MPEG]
This is a simulation of Diffusion Limited Aggregation (DLA). Points are randomly generated one at a time in the middle of a large square. Each then does a random walk (brownian motion) until it hits something, whereupon it sticks. An intricate pattern of accumulation results.
* TheEnd.Bernoulli [ShortDescr] [MPEG]
In this example the pixels of the characters of the words "THE END"
fall one at a time and bounce through a triangular pattern of "pins", resulting
in generating a binomial distribution of points below. Low priority rules
drop the pixels one at a time. Falling pixels hitting a pin move randomly
either right or left and fall further, generating the distribution.
This example (one of my favorites) solves the problem of counting the number of disconnected components in the mass of bifurcating spaghetti in the field window. It begins by simplifying the problem with three rules that nibble back at the tips of the spaghetti. One nibbles straight tips, another nibble L-corners, the third nibbles T junctions. In algebraic simplification problems (3x+7y=2x-5), we use carefully crafted rewrite rules that preserve a critical algebraic invariant -- equality. In this topological problem the rules have been carefully crafted preserve a critical topological invariant -- namely connectedness. That is none of these three rules creates or destroys an existing component. At any given moment there is a one-to-one correspondence between the original bifurcating spaghetti and the components left in the picture. The rules *do* shrink the components at each step, eventually each to a single dot. At that point there is a 1-to-1 correspondence between the initial spaghetti and these dots. There now remains the simpler problem of counting these dots. The next set of rules includes one, the "falling snow" rule, which drops each dot down until it reaches the bottom of the picture. Another drifts a dot on the bottom line to the right one space -- but only if there are two blank spaces available. This ensures that the dots to not merge into one another. The result of this stage is all the dots, one for each of the original components, neatly arranged in the lower right of the picture. New rules then convert each dot into a vertical bar, then five vertical bars in to a "V", two Vs into and X, etc to form a Roman Numeral count of the original components. Rules along the way in this phase move Roman Numerals to the left as needed, and reorder the symbols canonically. Note that this implements Old (?) Roman Numerals, where 4 = IIII (not IV). Simple rules could added to accomodate 4=IV, etc.
* FindLongestStick [ShortDescr] [MPEG]
In this example, BITPICT rules solves the problem of finding the longest of a set of sticks, using the physical computation algorithm described years ago by Martin Gardner. First, rules take a stick pixel unsupported at the bottom of a stick and drops it down. Then high priority rules drop all the other pixels of that stick as well (maintaining the integrity of the stick.) Then another stick's bottom is dropped, etc. until all sticks have fallen to the ground (with the longest stick protruding highest.) Then a horizontal bar is dropped down until it first contacts a stick, whereup the bar turns red, stops falling, points to and then highlights the appropriate measure mark on the ruler.
* GearsAndRods.color [ShortDescr] [MPEG]
In this example a set of "gears" and rods are interconnected. A set of bitpict rules can solve the problem of determining which way the final gear will turn when the first rod is pushed. One rule takes a little arrow character (chevron, really) and moves it forward leaving a chalkline behind. Another rule takes the arrow around a bend. This will have the chevron move all the way around a gear or along a rod. Another rule copies the chevron (preserving motion sense) across adjacencies, e.g., from one gear to the next, or to/from rods. The initial sense of motion is propagated all through the set of linkages, and finally cleaned up by some last rules into clean arrows on each component. The arrow direction on the final gear gives the answer.
* GearsAndRods.BW [NO-ShortDescr] [MPEG]
Older black and white version of the previous example. A little less easy for the human eye (and they bitpict engine!) to parse.
* MazeWalker [ShortDescr] [MPEG]
This very simple two-rule system implements the "keep your lefthand on the wall" strategy for solving a simply-connected maze. The field window contains: a maze with walls 2pixels wide and corridors 5 pixels wide, a single isolated bit one pixel away from the maze wall at the entrance representing the maze walker, and a target "nugget" attached to the wall in the upper left of the maze. The first rule, matching in any orientation, tells the maze-walker, if there are two empty spaces in front of it, to take one step forward, leaving a "chalkline" behind it. This ensures that it always leaves one empty buffering space ahead of it after it moves. It turns out that this rule automatically takes the walker around inside corners (exercise left to the reader). A second rule is needed to handle going around outside corners. These rules apply repeatedly until the walker hits the nugget (when no rules apply and the system halts).
* RomanAddition [ShortDescr] [MPEG]
This example, related to the last part of the CountComponents example,
takes a set of Roman Numerals and adds them up. It does so by collecting
all the terms into the lower right, sorting them, and simplifying. (Again
using Old Roman Numerals.)
* GraphicalPaint.House[ShortDescr] [MPEG]
In this example, simple bitpict rules move a paint brush icon around, over to a can of paint, where it picks up paint, and then proceeds to paint some houses. There are rules to move an empty brush to the right, then to dip an empty brush into a paint can. A simple paint diffusion rule fills the brush. Other rules take a full brush out of the can and move it to the houses. Over the unpainted houses, the brush touches down and the paint diffusion rule fills in the house. The brush then raises and moves on.
* PacMan [ShortDescr] [MPEG]
A few bitpict rules play a simple version of the old video game PacMan. Rules move the pacman ahead as he opens and closes his mouth. Other rules have him turn at obstacles and gobble the power pills.
* MacFileToTrash [ShortDescr] [MPEG]
Simple rules simulate a small piece of Macintosh interface interaction.
First a rule converts a file icon to its inverse-video "selected" state.
Other rules move any selected icon to the right and down around obstacles
until the trash is reached, whereupon another rule puts the file in the
trash and fattens the can.
This is a "quiz" for the viewer: What will these five rules do?
Answer: They animate a little man building an endless stairway for
himself, taking boards from the source cabinet.
* StairBuilderColor [ShortDescr] [MPEG]
A little man builds an endless stairway for himself, taking boards from the source cabinet (color version).
* TheEnd.Paint [ShortDescr] [MPEG]
Paint brush comes by and paints the interior of a "THE END" sign. The algorithm essentially identical to that of the paint program above, but it uses color instead of checkerboard paint.
* WalkingMan [NO-ShortDescr] [MPEG]
Funny cartoon man walks across the screen. (Done by student Pablo Perez).
First incarnation of logic circuits that compute right from the diagram pixels. Bitpatterns looking like Os and 1s move along the wires. When they come to a gate, the picture of the gate changes if necessary to make its outputs consistent with its inputs. The circuit in the field diagram is just an arbitrary set of gates.
* Logic2.fat.thin.T-FlipFlop[NO-ShortDescr] [MPEG]
Second incarnation of logic circuits that compute right from the diagram pixels. Wires get fat to represent high state (1) and thin to represent low (0). These width changes propagate along the wires and when they come to a gate, the picture of the gate changes if necessary to make its outputs consistent with its inputs. Here the circuit in the diagram is a T-flipflop, with a pulsing loop to drive it from state to state.
* Logic2.fat.thin.XOR [NO-ShortDescr] [MPEG]
Second incarnation of logic circuits that compute right from the diagram pixels. Wires get fat to represent high state (1) and thin to represent low (0). These width changes propagate along the wires and when they come to a gate, the picture of the gate changes if necessary to make its outputs consistent with its inputs. Here the circuit in the diagram is a simple X-OR.
* Logic3.color.XORcycle[ShortDescr] [MPEG]
Third incarnation of logic circuits that compute right from the diagram
pixels, using color. Here wires get yellow to represent high state (1)
and gray to represent low (0). These color changes propagate along the
wires and when they come to a gate, the picture of the gate changes if
necessary to make its outputs consistent with its inputs. Digital readouts
convert wire states to bit values. Here the circuit in the diagram is a
simple X-OR, together with a pair of loops that drive it through a full
truth table.
A simple one-bitpict rule system creates two sorts of fractal growth (Serpinsky Gasket and a space-filling rectangular "snowflake") depending on the conflict resolution scheme.
* FlyingCrosses [ShortDescr] [MPEG]
Simple rule system has crosses fly acoss the screen and bounce off of obstacles. Good to illustrate basic bitpict operation.
* FlyingBarsYikes [ShortDescr] [MPEG]
A simple rule slides a 1x2 bar of pixels along its length. Placed in a field of dots, collisions cause an ambiguous local configuration and random tie breaking make it to change course. The bar dances around until it hits the window frame when all heck breaks loose.
* TicTacToe [ShortDescr] [MPEG]
This example shows rules to play tic-tac-toe. This system uses "mask" bitpicts, i.e., bitpicts that are not required to be rectangular -- implemented by having a mask that tells which pixels really matter to the match and which do not (the latter are greyed out). There are rules to place Xs and Os in empty spots, and to highlight wins. (Many cases are taken care of by symmetry.) Note that this implements legal play of tic-tac-toe, but only minimally strategic play. (It is smart enough to make three in a row when it gets the chance, but not smart enough to block- easy to fix if desired.) An interesting algorithmic detail here is the way turn-taking is implemented -- as each player places a mark, it changes the color of the board to signal the other player that it is her turn.