Instantly share code, notes, and snippets.

Embed
What would you like to do?
Another method for generating “all RGB” images
// gcc -g -Wall --std=c99 wilson.c -lpng -o wilson && ./wilson
/* Generate a random spanning tree of the RGB cube, and a random
spanning tree of the pixel grid, using Wilson's algorithm, then
do a simultaneous breadth-first search of these trees to obtain
a bijection between the RGB cube and the pixel grid.
Inspired by allrgb.com.
-- Robin Houston, 2014-03
*/
#include <bitstring.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <png.h>
#define N_BITS 24
#define N (1 << N_BITS)
#define _t3(i, j, k) ( ((i & 0xFF) << 16) | ((j & 0xFF) << 8) | (k & 0xFF) )
#define _x3(n) ((n >> 16) & 0xFF)
#define _y3(n) ((n >> 8) & 0xFF)
#define _z3(n) (n & 0xFF)
#define _t2(i, j) ( ((i & 0xFFF) << 12) | (j & 0xFFF) )
#define _x2(n) ((n >> 12) & 0xFFF)
#define _y2(n) (n & 0xFFF)
typedef struct {
int adjacent[N][7]; // length-prefixed
int queue_start;
int queue_end;
int queue[N];
} maze;
bool has_next(maze *m) {
return m->queue_end > m->queue_start;
}
int next(maze *m) {
int r = m->queue[m->queue_start++];
int *adjacent_to_r = m->adjacent[r];
for (int i=0; i < adjacent_to_r[0]; i++) {
m->queue[m->queue_end++] = adjacent_to_r[i + 1];
}
return r;
}
int random_3d_neighbour(int cell) {
int neighbours[6];
int num_neighbours = 0;
int x = _x3(cell),
y = _y3(cell),
z = _z3(cell);
if (x > 0) neighbours[num_neighbours++] = _t3(x-1, y, z);
if (x < 0xFF) neighbours[num_neighbours++] = _t3(x+1, y, z);
if (y > 0) neighbours[num_neighbours++] = _t3(x, y-1, z);
if (y < 0xFF) neighbours[num_neighbours++] = _t3(x, y+1, z);
if (z > 0) neighbours[num_neighbours++] = _t3(x, y, z-1);
if (z < 0xFF) neighbours[num_neighbours++] = _t3(x, y, z+1);
while (1) {
int r = rand() & 0x7;
if (r < num_neighbours) return neighbours[r];
}
}
int random_2d_neighbour(int cell) {
int neighbours[4];
int num_neighbours = 0;
int x = _x2(cell),
y = _y2(cell);
if (x > 0) neighbours[num_neighbours++] = _t2(x-1, y);
if (x < 0xFFF) neighbours[num_neighbours++] = _t2(x+1, y);
if (y > 0) neighbours[num_neighbours++] = _t2(x, y-1);
if (y < 0xFFF) neighbours[num_neighbours++] = _t2(x, y+1);
while (1) {
int r = rand() & 0x7;
if (r < num_neighbours) return neighbours[r];
}
}
maze *generate_maze(int start_cell, int random_neighbour(int)) {
maze *m = calloc(sizeof(maze), 1);
m->queue_start = 0;
m->queue_end = 1;
m->queue[0] = start_cell;
int *pointers = calloc(sizeof(int), N);
bitstr_t *seen = bit_alloc(N);
bit_nclear(seen, 0, N-1);
bit_set(seen, start_cell);
int n = 1;
int s = 0;
int percent_done = -1;
int *path = malloc(sizeof(int) * N);
int path_len = 0;
while (n < N) {
int percent_now_done = n * 100 / N;
if (percent_now_done > percent_done) {
printf("%d%% complete\n", percent_now_done);
percent_done = percent_now_done;
}
path_len = 1;
path[0] = s++;
while (!bit_test(seen, path[path_len - 1])) {
pointers[path[path_len - 1]] = -path_len;
int next_cell = random_neighbour(path[path_len - 1]);
if (pointers[next_cell] < 0) {
int truncation = -pointers[next_cell];
for (int i=truncation; i < path_len; i++) {
pointers[path[i]] = 0;
}
path_len = truncation;
}
else {
path[path_len++] = next_cell;
}
}
// Incorporate path
for (int i=0; i < path_len - 1; i++) {
pointers[path[i]] = path[i+1];
bit_set(seen, path[i]);
n++;
}
}
printf("100%% complete\n");
for (int i=0; i<N; i++) {
int j = pointers[i];
if (i != start_cell) {
int *adjacent_to_j = m->adjacent[j];
adjacent_to_j[++adjacent_to_j[0]] = i;
}
}
free(path);
free(pointers);
free(seen);
return m;
}
void write_png(char *filename, int *img)
{
FILE *fp = fopen(filename, "wb");
png_structp png_ptr = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);
png_infop info_ptr = png_create_info_struct(png_ptr);
png_init_io(png_ptr, fp);
png_set_IHDR(png_ptr, info_ptr, 4096, 4096,
8, PNG_COLOR_TYPE_RGB, PNG_INTERLACE_NONE,
PNG_COMPRESSION_TYPE_BASE, PNG_FILTER_TYPE_BASE);
png_write_info(png_ptr, info_ptr);
png_bytep row = malloc(3 * 4096 * sizeof(png_byte));
for (int y=0; y < 4096; y++) {
for (int x=0; x < 4096; x++) {
int color = img[_t2(x, y)];
row[x*3] = (color >> 16) & 0xFF;
row[x*3 + 1] = (color >> 8) & 0xFF;
row[x*3 + 2] = color & 0xFF;
}
png_write_row(png_ptr, row);
}
fclose(fp);
png_free_data(png_ptr, info_ptr, PNG_FREE_ALL, -1);
png_destroy_write_struct(&png_ptr, (png_infopp)NULL);
free(row);
}
int main(int argc, char **argv)
{
sranddev();
maze *m3 = generate_maze(_t3(127, 127, 127), random_3d_neighbour);
maze *m2 = generate_maze(_t2(2047, 2047), random_2d_neighbour);
int *img = calloc(sizeof(int), N);
int n = 0;
int percent_done = -1;
while (has_next(m2)) {
img[next(m2)] = next(m3);
int percent_now_done = ++n * 100 / N;
if (percent_now_done > percent_done) {
printf("Image generation %d%% done\n", percent_now_done);
percent_done = percent_now_done;
}
}
write_png("wilson.png", img);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment