/* (c) 2021 Aaron Taylor <ataylor at subgeniuskitty dot com> */
/* See LICENSE.txt file for copyright and license details. */
/* TODO: Write description explaining that this simulates all 1D NN CAs, and explain briefly what all those terms imply. */
/* TODO: Explain things like the topology of the space. */
/* TODO: Explain how the numbering for a CA expands to the actual rules. */
/* TODO: Briefly explain the four different classes of behavior and their implications. */
/* TODO: Include a link to Wikipedia. */
/* TODO: I suppose a lot of this stuff goes in the README instead. */
/* TODO: Explain the data structures in detail. */
/* TODO: Explain all the options, like the various starting conditions. */
/* TODO: Explain all the dependencies like libXpm. */
/* TODO: Add a #define for the hack version. */
/* TODO: Check manpage for all functions I use and ensure my includes are correct. I don't want to depend on picking up includes via screenhack.h. */
/* TODO: Verify everything in this file is C89. Get rid of things like '//' comments, pack all my declarations upfront, no stdint, etc. */
#include <X11/Intrinsic.h>
* We do a few manual manipulations of X resources in this hack, like picking
* random colors. In order to ensure our manual manipulations always use the
* same X resource specification as Xscreensaver, we pass HACKNAME to
* Xscreensaver via the XSCREENSAVER_MODULE() line at the bottom of this file,
* and then always use HACKNAME or MAKE_STRING(HACKNAME) as the base of the
* resource specification when making manual manipulations.
#define HACKNAME WolframAutomata
#define MAKE_STRING_X(s) #s
#define MAKE_STRING(s) MAKE_STRING_X(s)
// directory to output XBM files of each run (and call an external command to convert to PNGs?)
// (could use libXpm to save an XPM and then convert to PNG with ImageMagick) (this is a single function call to go from pixmap -> file)
// (since it depends on an external library, make this whole feature optional at build-time?)
// number of generations to simulate
// delay time (speed of simulation)
// foreground and background color
// -random-colors (highest precedence)
// -foreground "COLORNAME"
// -background "COLORNAME"
// (default is black and white)
// (mention sample color combinations in manpage, and link to: https://en.wikipedia.org/wiki/X11_color_names)
// (note to the user that most color names they can naturally think of (e.g. red, purple, gray, pink, etc) are valid X11 color names for these CLI options.)
// display info overlay with CA number and start conditions?
// which ruleset number to use? Or random? Or random from small set of hand-selected interesting examples?
// In order of precedence:
// -rule-random (select a random rule on each run)
// -rule N (always simulate Rule N on each run)
// (if neither of the above two are specified, then a random CURATED rule is selected on each run)
// which starting population to use, random or one bit? (for random: allow specifying a density)
// In order of precedence:
// -population-random DENSITY
// (the two options above only apply to the simulation under the -rule-random or -rule N options. in curated mode, starting population is defined in the curation array)
// TODO: In the future, add the option for user to pass list of cell IDs to turn ON.
// size of pixel square (e.g. 1x1, 2x2, 3x3, etc)
/* -------------------------------------------------------------------------- */
/* -------------------------------------------------------------------------- */
/* Various X resources */
// TODO: Explain that this holds the whole evolution of the CA and the actual displayed visualization is simply a snapshot into this pixmap.
Pixmap evolution_history
;
// TODO: Explain all of these.
int xlim
, ylim
, ypos
; // explain roughly how and where we use these. Note: I'm not thrilled xlim/ylim since they are actually the width of the display, not the limit of the index (off by one). Change those names.
Bool
* current_generation
;
uint8_t rule_number
; // Note: This is not a CLI option. You're thinking of rule_requested.
uint8_t rule_requested
; // Note: Repurposing Rule 0 as a null value.
/* Misc Commandline Options */
int pixel_size
; /* Size of CA cell in pixels (e.g. pixel_size=3 means 3x3 pixels per cell). */
int delay_microsec
; /* Requested delay to screenhack framework before next call to WolframAutomata_draw(). */
int num_generations
; /* Number of generations of the CA to simulate before restarting. */
/* Expository Variables - Not strictly necessary, but makes some code easier to read. */
enum seed_population seed
;
static const struct curated_ruleset curated_ruleset_list
[] = {
static const struct color_pair color_list
[] = {
{"white", "darkmagenta"},
{"darkslategray", "darkslategray1"},
{"lightsteelblue", "darkslategray"},
{"royalblue4", "royalblue"},
{"antiquewhite2", "antiquewhite4"},
{"darkolivegreen1", "darkolivegreen"},
{"darkseagreen1", "darkseagreen4"},
{"lightblue", "darkgreen"},
{"khaki", "darkolivegreen"},
{"lightslategray", "darkslategray"},
{"tomato", "darkslategray"},
/* -------------------------------------------------------------------------- */
/* -------------------------------------------------------------------------- */
// TODO: decorations? inline?
generate_random_seed(struct state
* state
)
for (i
= 0; i
< state
->number_of_cells
; i
++) {
state
->current_generation
[i
] = ((random() % 100) < state
->population_density
) ? True
: False
;
// TODO: function decorations?
// TODO: Explain why this santizes the index for accessing current_generation (i.e. it creates a circular topology).
sindex(struct state
* state
, int index
)
index
+= state
->number_of_cells
;
while (index
>= state
->number_of_cells
) {
index
-= state
->number_of_cells
;
// TODO: function decorations?
// TODO: At least give a one-sentence explanation of the algorithm since this function is the core of the simulation.
calculate_cell(struct state
* state
, int cell_id
)
uint8_t cell_pattern
= 0;
for (i
= -1; i
< 2; i
++) {
cell_pattern
= cell_pattern
<< 1;
if (state
->current_generation
[sindex(state
, cell_id
+i
)] == True
) {
if ((state
->rule_number
>> cell_pattern
) & 1) {
// TODO: function decorations?
render_current_generation(struct state
* state
)
for (xpos
= 0; xpos
< state
->number_of_cells
; xpos
++) {
if (state
->current_generation
[xpos
] == True
) {
XFillRectangle(state
->dpy
, state
->evolution_history
, state
->gc
, xpos
*state
->pixel_size
, state
->ypos
, state
->pixel_size
, state
->pixel_size
);
XSetForeground(state
->dpy
, state
->gc
, state
->bg
);
XFillRectangle(state
->dpy
, state
->evolution_history
, state
->gc
, xpos
*state
->pixel_size
, state
->ypos
, state
->pixel_size
, state
->pixel_size
);
XSetForeground(state
->dpy
, state
->gc
, state
->fg
);
/* -------------------------------------------------------------------------- */
/* Screenhack API Functions */
/* -------------------------------------------------------------------------- */
WolframAutomata_init(Display
* dpy
, Window win
)
struct state
* state
= calloc(1, sizeof(*state
));
fprintf(stderr
, "ERROR: Failed to calloc() for state struct in WolframAutomata_init().\n");
const struct curated_ruleset
* curated_ruleset
= NULL
;
XGetWindowAttributes(state
->dpy
, state
->win
, &xgwa
);
state
->xlim
= xgwa
.width
;
state
->ylim
= xgwa
.height
;
state
->ypos
= 0; // TODO: Explain why.
if (get_boolean_resource(state
->dpy
, "random-colors", "Boolean")) {
XrmDatabase db
= XtDatabase(state
->dpy
);
size_t rand_i
= random() % sizeof(color_list
)/sizeof(color_list
[0]);
XrmPutStringResource(&db
, MAKE_STRING(HACKNAME
) ".background", color_list
[rand_i
].bg
);
XrmPutStringResource(&db
, MAKE_STRING(HACKNAME
) ".foreground", color_list
[rand_i
].fg
);
state
->fg
= gcv
.foreground
= get_pixel_resource(state
->dpy
, xgwa
.colormap
, "foreground", "Foreground");
state
->bg
= gcv
.background
= get_pixel_resource(state
->dpy
, xgwa
.colormap
, "background", "Background");
state
->gc
= XCreateGC(state
->dpy
, state
->win
, GCForeground
, &gcv
);
/* Set the size of each simulated cell as NxN pixels for pixel_size=N. */
if (get_boolean_resource(state
->dpy
, "random-pixel-size", "Boolean")) {
/* Although we are choosing the pixel size 'randomly', a truly random */
/* selection would bias toward large numbers since there are more of */
/* them. To avoid this, we select a random number for a bit shift, */
/* resulting in a pixel size of 1, 2, 4, 8, 16 or 32, equally likely. */
state
->pixel_size
= 1 << (random() % 6);
state
->pixel_size
= get_integer_resource(state
->dpy
, "pixel-size", "Integer");
if (state
->pixel_size
< 1) state
->pixel_size
= 1;
if (state
->pixel_size
> state
->xlim
) state
->pixel_size
= state
->xlim
;
state
->number_of_cells
= state
->xlim
/ state
->pixel_size
;
// TODO: Do we want to enforce that number_of_cells > 0?
/* Set the delay (in microseconds) between simulation of each generation */
/* of the simulation, also known as the delay between calls to */
/* WolframAutomata_draw(), which simulates one generation per call. */
if (get_boolean_resource(state
->dpy
, "random-delay", "Boolean")) {
/* When randomly setting the delay, the problem is to avoid being too */
/* fast or too slow, as well as ensuring slower speeds are chosen */
/* with the same likelihood as faster speeds, as perceived by a */
/* human. By empirical observation, we note that for 1x1 up to 4x4 */
/* pixel cell sizes, values for state->delay_microsec between */
/* 2048 (2^11) and 16556 (2^14) produce pleasant scroll rates. To */
/* maintain this appearance, we bitshift state->pixel_size down until */
/* it is a maximum of 4x4 pixels in size, record how many bitshifts */
/* took place, and then shift our valid window for */
/* state->delay_microsec up by an equal number of bitshifts. For */
/* example, if state->pixel_size=9, then it takes one right shift to */
/* reach state->pixel_size=4. Thus, the valid window for */
/* state->delay_microsec becomes 4096 (2^12) up to 32768 (2^15). */
size_t pixel_shift_range
= 1;
size_t pixel_size_temp
= state
->pixel_size
;
while (pixel_size_temp
> 4) {
/* In the below line, '3' represents the total range, namely '14-11' */
/* from '2^14' and '2^11' as the endpoints. Similarly, the '11' in */
/* the below line represents the starting point of this range, from */
/* the exponent in '2^11'. */
state
->delay_microsec
= 1 << ((random() % 3) + 11 + pixel_shift_range
);
state
->delay_microsec
= get_integer_resource(state
->dpy
, "delay-usec", "Integer");
if (state
->delay_microsec
< 0) state
->delay_microsec
= 0;
/* Set the number of generations to simulate before wiping the simulation */
/* and re-running with new settings. */
if (get_boolean_resource(state
->dpy
, "random-num-generations", "Boolean")) {
/* By empirical observation, keep the product */
/* state->num_generations * state->pixel_size */
/* below 10,000 to avoid BadAlloc errors from the X server due to */
/* requesting an enormous pixmap. This value works on both a 12 core */
/* Xeon with 108 GiB of RAM and a Sun Ultra 2 with 2 GiB of RAM. */
state
->num_generations
= random() % (10000 / state
->pixel_size
);
/* Ensure selected value is large enough to at least fill the screen. */
/* Cast to avoid overflow. */
if ((long)state
->num_generations
* (long)state
->pixel_size
< state
->ylim
) {
state
->num_generations
= (state
->ylim
/ state
->pixel_size
) + 1;
state
->num_generations
= get_integer_resource(state
->dpy
, "num-generations", "Integer");
/* The minimum number of generations is 2 since we must allocate enough */
/* space to hold the seed generation and at least one pass through */
/* WolframAutomata_draw(), which is where we check whether or not we've */
/* reached the end of the pixmap. */
if (state
->num_generations
< 0) state
->num_generations
= 2;
/* The maximum number of generations is pixel_size dependent. This is a */
/* soft limit and may be increased if you have plenty of RAM (and a */
/* cooperative X server). The value 10,000 was determined empirically. */
if ((long)state
->num_generations
* (long)state
->pixel_size
> 10000) {
state
->num_generations
= 10000 / state
->pixel_size
;
/* Time to figure out which rule to use for this simulation. */
/* We ignore any weirdness resulting from the following cast since every */
/* bit pattern is also a valid rule; if the user provides weird input, */
/* then we'll return weird (but well-defined!) output. */
state
->rule_requested
= (uint8_t) get_integer_resource(state
->dpy
, "rule-requested", "Integer");
state
->rule_random
= get_boolean_resource(state
->dpy
, "rule-random", "Boolean");
/* Through the following set of branches, we enforce CLI flag precedence. */
if (state
->rule_random
) {
/* If this flag is set, the user wants truly random rules rather than */
/* random rules from a curated list. */
state
->rule_number
= (uint8_t) random();
} else if (state
->rule_requested
!= 0) {
/* Rule 0 is terribly uninteresting, so we are reusing it as a 'null' */
/* value and hoping nobody notices. Finding a non-zero value means */
/* the user requested a specific rule. Use it. */
state
->rule_number
= state
->rule_requested
;
/* No command-line options were specified, so select rules randomly */
/* from a curated list. */
size_t number_of_array_elements
= sizeof(curated_ruleset_list
)/sizeof(curated_ruleset_list
[0]);
curated_ruleset
= &curated_ruleset_list
[random() % number_of_array_elements
];
state
->rule_number
= curated_ruleset
->rule
;
/* Time to construct the seed generation for this simulation. */
state
->population_single
= get_boolean_resource(state
->dpy
, "population-single", "Boolean");
state
->population_density
= get_integer_resource(state
->dpy
, "population-density", "Integer");
if (state
->population_density
< 0 || state
->population_density
> 100) state
->population_density
= 50;
state
->current_generation
= calloc(1, sizeof(*state
->current_generation
)*state
->number_of_cells
);
if (!state
->current_generation
) {
fprintf(stderr
, "ERROR: Failed to calloc() for cell generation in WolframAutomata_init().\n");
/* If we're using a curated ruleset, ignore any CLI flags related to */
/* setting the seed generation, instead drawing that information from */
/* the curated ruleset. */
switch (curated_ruleset
->seed
) {
case random_cell
: generate_random_seed(state
); break;
case middle_cell
: state
->current_generation
[state
->number_of_cells
/2] = True
; break;
case edge_cell
: state
->current_generation
[0] = True
; break;
/* If we're not using a curated ruleset, process any relevant flags */
/* from the user, falling back to a random seed generation if nothing */
if (state
->population_single
) {
state
->current_generation
[0] = True
;
generate_random_seed(state
);
// TODO: These should be command-line options, but I need to learn how the get_integer_resource() and similar functions work first.
state
->display_info
= True
;
state
->evolution_history
= XCreatePixmap(state
->dpy
, state
->win
, state
->xlim
, state
->num_generations
*state
->pixel_size
, xgwa
.depth
);
// Pixmap contents are undefined after creation. Explicitly set a black
// background by drawing a black rectangle over the entire pixmap.
XAllocNamedColor(state
->dpy
, DefaultColormapOfScreen(DefaultScreenOfDisplay(state
->dpy
)), "black", &blacks
, &blackx
);
XSetForeground(state
->dpy
, state
->gc
, blacks
.pixel
);
XFillRectangle(state
->dpy
, state
->evolution_history
, state
->gc
, 0, 0, state
->xlim
, state
->num_generations
*state
->pixel_size
);
XSetForeground(state
->dpy
, state
->gc
, state
->fg
);
render_current_generation(state
);
state
->ypos
+= state
->pixel_size
;
WolframAutomata_draw(Display
* dpy
, Window win
, void * closure
)
// TODO: Mark these basic sections of the function
// calculate (and store) new generation
// draw new generation as line of pixels on pixmap
// calculate current 'viewport' into pixmap
// check for termination condition
struct state
* state
= closure
;
Bool new_generation
[state
->xlim
];
for (xpos
= 0; xpos
< state
->number_of_cells
; xpos
++) {
new_generation
[xpos
] = calculate_cell(state
, xpos
);
for (xpos
= 0; xpos
< state
->number_of_cells
; xpos
++) {
state
->current_generation
[xpos
] = new_generation
[xpos
];
render_current_generation(state
);
// Was this the final generation of this particular simulation? If so, give
// the user a moment to bask in the glory of our output and then start a
if (state
->ypos
/state
->pixel_size
< state
->num_generations
-1) {
state
->ypos
+= state
->pixel_size
;
// TODO: Wait for a second or two, clear the screen and do a new iteration with suitably changed settings.
// Note: Since we can't actually loop or sleep here, we need to add a flag to the state struct to indicate that we're in an 'admiration timewindow' (and indicate when it should end)
printf("infinite hamster wheel\n");
// Calculate the vertical offset of the current 'window' into the history
// of the CA. After the CA's evolution extends past what we can display, have
// the window track the current generation and most recent history.
if (state
->ypos
< state
->ylim
) {
window_y_offset
= state
->ypos
- (state
->ylim
- 1);
// Render everything to the display.
XCopyArea(state
->dpy
, state
->evolution_history
, state
->win
, state
->gc
, 0, window_y_offset
, state
->xlim
, state
->ylim
, 0, 0);
// TODO: Print info on screen if display_info is true. Will need fonts/etc. Do I want to create a separate pixmap for this during the init() function and then just copy the pixmap each time we draw the screen in draw()?
return state
->delay_microsec
;
static const char * WolframAutomata_defaults
[] = {
// TODO: Difference between dot and asterisk? Presumably the asterisk matches all resouces of attribute "pixelsize"? Apply answer to all new options.
"*num-generations: 5000",
"*population-density: 50",
"*population-single: False",
"*random-pixel-size: False",
"*random-num-generations: False",
static XrmOptionDescRec WolframAutomata_options
[] = {
{ "-background", ".background", XrmoptionSepArg
, 0},
{ "-foreground", ".foreground", XrmoptionSepArg
, 0},
{ "-random-colors", ".random-colors", XrmoptionNoArg
, "True"},
{ "-delay-usec", ".delay-usec", XrmoptionSepArg
, 0 },
{ "-pixel-size", ".pixel-size", XrmoptionSepArg
, 0 },
{ "-num-generations", ".num-generations", XrmoptionSepArg
, 0 },
{ "-rule", ".rule-requested", XrmoptionSepArg
, 0 },
{ "-rule-random", ".rule-random", XrmoptionNoArg
, "True" },
{ "-population-density", ".population-density", XrmoptionSepArg
, 0 },
{ "-population-single", ".population-single", XrmoptionNoArg
, "True" },
{ "-random-delay", ".random-delay", XrmoptionNoArg
, "True" },
{ "-random-pixel-size", ".random-pixel-size", XrmoptionNoArg
, "True" },
{ "-random-num-generations", ".random-num-generations", XrmoptionNoArg
, "True" },
WolframAutomata_event(Display
* dpy
, Window win
, void * closure
, XEvent
* event
)
WolframAutomata_free(Display
* dpy
, Window win
, void * closure
)
struct state
* state
= closure
;
XFreeGC(state
->dpy
, state
->gc
);
XFreePixmap(state
->dpy
, state
->evolution_history
);
free(state
->current_generation
);
WolframAutomata_reshape(Display
* dpy
, Window win
, void * closure
, unsigned int w
, unsigned int h
)
WolframAutomata_free(dpy
, win
, closure
);
closure
= WolframAutomata_init(dpy
, win
);
XSCREENSAVER_MODULE ("1D Nearest-Neighbor Cellular Automata", HACKNAME
)