Add a maze solving demo

3 files changed, 344 insertions, 1 deletions

diff --git a/.gitignore b/.gitignore
index 4801e15..832f713 100644
--- a/.gitignore
+++ b/.gitignore
@@ -4,6 +4,7 @@ fish-demo
 flowers-demo
 gears-demo
 gradient-demo
+maze-demo
 poppler-demo
 pythagoras-demo
 sierpinski-demo
diff --git a/Makefile b/Makefile
index fc7cd29..bf0f434 100644
--- a/Makefile
+++ b/Makefile
@@ -38,7 +38,7 @@ else
 DEFINES+=-DHAVE_COGL=0
 endif
 
-all: spinner-demo spiral-demo slideshow-demo tiger-demo fish-demo flowers-demo gears-demo gradient-demo chart-demo waterfall-demo dragon-demo pythagoras-demo wave-demo sierpinski-demo
+all: spinner-demo spiral-demo slideshow-demo tiger-demo fish-demo flowers-demo gears-demo gradient-demo chart-demo waterfall-demo dragon-demo pythagoras-demo wave-demo sierpinski-demo maze-demo
 
 ifeq ($(shell pkg-config --exists poppler-glib && echo 1), 1)
 all: poppler-demo
@@ -80,6 +80,8 @@ wave-demo: wave-demo.c $(SOURCES) demo.h Makefile
 	$(CC) $(DEFINES) $(CFLAGS) -o $@ wave-demo.c $(SOURCES) $(LIBS)
 sierpinski-demo: sierpinski-demo.c $(SOURCES) demo.h Makefile
 	$(CC) $(DEFINES) $(CFLAGS) -o $@ sierpinski-demo.c $(SOURCES) $(LIBS)
+maze-demo: maze-demo.c $(SOURCES) demo.h Makefile
+	$(CC) $(DEFINES) $(CFLAGS) -o $@ maze-demo.c $(SOURCES) $(LIBS)
 clean:
 	rm -f *-demo
 
diff --git a/maze-demo.c b/maze-demo.c
new file mode 100644
index 0000000..276c01c
--- /dev/null
+++ b/maze-demo.c
@@ -0,0 +1,340 @@
+#include "demo.h"
+#include <stdlib.h>
+#include <string.h>
+#include <sys/time.h>
+#include <math.h>
+
+enum { N = 1, S = 2, W = 4, E = 8, V = 16, D = 32};
+
+static int w = 40;
+static int h = 20;
+static int avail;
+static uint8_t **cell;
+
+#define each(i, x, y) for (i = x; i <= y; i++)
+inline static int max(int a, int b) { return a >= b ? a : b; }
+inline static int min(int a, int b) { return b >= a ? a : b; }
+
+static int irand(int n)
+{
+	int r, rmax = n * (RAND_MAX / n);
+	while ((r = rand()) >= rmax);
+	return r / (RAND_MAX/n);
+}
+
+static void show(cairo_t *cr, int width, int height)
+{
+	int i, j;
+	int dx, dy, step;
+
+	dx = width/(w+2);
+	dy = height/(h+2);
+	step = min(dx, dy);
+	step = max(step, 4);
+
+	cairo_set_operator(cr, CAIRO_OPERATOR_CLEAR);
+	cairo_paint(cr);
+	cairo_set_operator(cr, CAIRO_OPERATOR_OVER);
+
+	cairo_translate(cr, (width-step*w)/2, (height-step*h)/2);
+	cairo_scale(cr, step, step);
+
+	cairo_set_source_rgb(cr, 0.2, 0.2, 0.7);
+	cairo_arc(cr, .5, .5, 1/3., 0, 2*M_PI);
+	cairo_fill(cr);
+	cairo_arc(cr, (w-.5), (h-.5), 1/3., 0, 2*M_PI);
+	cairo_fill(cr);
+
+	each(i, 0, 2 * h) {
+		each(j, 0, 2 * w) {
+			uint8_t c = cell[i][j];
+			if (c > V)
+				continue;
+
+			if ((c & (N | S)) == (N | S)) {
+				cairo_move_to(cr, j/2, i/2);
+				cairo_line_to(cr, j/2, i/2+1);
+			}
+			if ((c & (W | E)) == (W | E)) {
+				cairo_move_to(cr, j/2, i/2);
+				cairo_line_to(cr, j/2+1, i/2);
+			}
+		}
+	}
+
+	cairo_set_source_rgb(cr, 1, 1, 1);
+	cairo_save(cr); {
+		cairo_identity_matrix(cr);
+		cairo_set_line_width(cr, 2);
+		cairo_set_antialias(cr, CAIRO_ANTIALIAS_NONE);
+		cairo_stroke(cr);
+	} cairo_restore (cr);
+
+	each(i, 0, 2 * h) {
+		each(j, 0, 2 * w) {
+			uint8_t c = cell[i][j];
+			if (c & V) {
+				cairo_arc(cr, j/2+.5, i/2+.5, 1/5., 0, 2*M_PI);
+				cairo_set_source_rgb(cr, 0.70, 0.75, 0.75);
+				cairo_fill(cr);
+			}
+			if (c & D) {
+				cairo_arc(cr, j/2+.5, i/2+.5, 1/4., 0, 2*M_PI);
+				cairo_set_source_rgb(cr, 0.5, 0.0, 0.0);
+				cairo_fill(cr);
+			}
+		}
+	}
+
+	each(i, 0, 2 * h) {
+		each(j, 0, 2 * w) {
+			uint8_t c = cell[i][j];
+			if ((c & V) == 0)
+				continue;
+			if (c & N) {
+				cairo_move_to(cr, j/2+.5, i/2);
+				cairo_line_to(cr, j/2+.5, i/2+.5);
+			}
+			if (c & S) {
+				cairo_move_to(cr, j/2+.5, i/2+.5);
+				cairo_line_to(cr, j/2+.5, i/2+1);
+			}
+			if (c & W) {
+				cairo_move_to(cr, j/2, i/2+.5);
+				cairo_line_to(cr, j/2+.5, i/2+.5);
+			}
+			if (c & E) {
+				cairo_move_to(cr, j/2+.5, i/2+.5);
+				cairo_line_to(cr, j/2+1, i/2+.5);
+			}
+		}
+	}
+
+	cairo_set_source_rgb(cr, 0.2, 0.7, 0.2);
+	cairo_save(cr); {
+		cairo_identity_matrix(cr);
+		cairo_set_line_width(cr, 1);
+		cairo_set_antialias(cr, CAIRO_ANTIALIAS_NONE);
+		cairo_stroke(cr);
+	} cairo_restore (cr);
+
+	cairo_identity_matrix(cr);
+}
+
+static int dirs[4][2] = {{-2, 0}, {0, 2}, {2, 0}, {0, -2}};
+static void walk(int x, int y)
+{
+	int i, t, x1, y1, d[4] = { 0, 1, 2, 3 };
+
+	cell[y][x] |= V;
+	avail--;
+
+	for (x1 = 3; x1; x1--)
+		if (x1 != (y1 = irand(x1 + 1)))
+			i = d[x1], d[x1] = d[y1], d[y1] = i;
+
+	for (i = 0; avail && i < 4; i++) {
+		x1 = x + dirs[ d[i] ][0], y1 = y + dirs[ d[i] ][1];
+
+		if (cell[y1][x1] & V)
+		       	continue;
+
+		/* break walls */
+		if (x1 == x) {
+			t = (y + y1) / 2;
+			cell[t][x+1] &= ~W;
+		       	cell[t][x] &= ~(E|W);
+		       	cell[t][x-1] &= ~E;
+		} else if (y1 == y) {
+			t = (x + x1)/2;
+			cell[y-1][t] &= ~S;
+		       	cell[y][t] &= ~(N|S);
+		       	cell[y+1][t] &= ~N;
+		}
+		walk(x1, y1);
+	}
+}
+
+static int solve(int x, int y, int tox, int toy, int *depth)
+{
+	int i;
+
+	cell[y][x] |= V;
+	if (x == tox && y == toy)
+	       	return 1;
+
+	if (--*depth == 0)
+		return -1;
+
+	each(i, 0, 3) {
+		int x1 = x + dirs[i][0];
+	       	int y1 = y + dirs[i][1];
+		int ret;
+
+		if (cell[y1][x1] & V)
+		       	continue;
+
+		if (i & 1) {
+			int t = (y + y1)/2;
+			if (cell[t][x] & ~D)
+				continue;
+
+			ret = solve(x1, y1, tox, toy, depth);
+			if (ret == 0)
+				continue;
+
+			cell[t-1][x] |= S;
+			cell[t+1][x] |= N;
+		} else {
+			int t = (x + x1)/2;
+			if (cell[y][t] & ~D)
+			       	continue;
+
+			ret = solve(x1, y1, tox, toy, depth);
+			if (ret == 0)
+				continue;
+
+			cell[y][t-1] |= E;
+			cell[y][t+1] |= W;
+		}
+
+		return ret;
+	}
+
+	if (--*depth == 0)
+		return -1;
+
+	cell[y][x] = D;
+	return 0;
+}
+
+static void maze_create(void)
+{
+	int i, h2 = 2 * h + 2, w2 = 2 * w + 2;
+	uint8_t **p;
+
+	p = calloc(sizeof(uint8_t*) * (h2 + 2) + w2 * h2 + 1, 1);
+
+	p[1] = (uint8_t*)(p + h2 + 2) + 1;
+	each(i, 2, h2) p[i] = p[i-1] + w2;
+	p[0] = p[h2];
+	cell = &p[1];
+}
+
+static void maze_reset(void)
+{
+	int i, j;
+	int h2 = 2 * h + 2, w2 = 2 * w + 2;
+
+	each(i, 0, 2*h) each(j, 0, 2*w) cell[i][j] = 0;
+
+	each(i, -1, 2 * h + 1) cell[i][-1] = cell[i][w2 - 1] = V;
+	each(j, 0, 2 * w) cell[-1][j] = cell[h2 - 1][j] = V;
+	each(i, 0, h) each(j, 0, 2 * w) cell[2*i][j] |= E|W;
+	each(i, 0, 2 * h) each(j, 0, w) cell[i][2*j] |= N|S;
+	each(j, 0, 2 * w) cell[0][j] &= ~N, cell[2*h][j] &= ~S;
+	each(i, 0, 2 * h) cell[i][0] &= ~W, cell[i][2*w] &= ~E;
+
+	avail = w * h;
+	walk(irand(2) * 2 + 1, irand(h) * 2 + 1);
+}
+
+static int done;
+static void signal_handler(int sig)
+{
+	done = sig;
+}
+
+int main (int argc, char **argv)
+{
+	struct device *device = device_open(argc, argv);
+	struct timeval start, last_tty, last_fps, now, complete;
+	int iterations = 1;
+
+	double delta;
+	int frame = 0;
+	int show_fps = 1;
+	int benchmark;
+	const char *version = device_show_version(argc, argv);
+	//enum clip clip = device_get_clip(argc, argv);
+
+	int n;
+
+	benchmark = device_get_benchmark(argc, argv);
+	if (benchmark == 0)
+		benchmark = 20;
+	if (benchmark > 0)
+		show_fps = 0;
+
+	signal(SIGHUP, signal_handler);
+
+	for (n = 1; n < argc; n++) {
+		if (strcmp (argv[n], "--hide-fps") == 0)
+			show_fps = 0;
+	}
+
+	maze_create();
+	maze_reset();
+	complete.tv_sec = 0;
+
+	gettimeofday(&start, 0); now = last_tty = last_fps = start;
+	do {
+		struct framebuffer *fb = device->get_framebuffer (device);
+		cairo_t *cr = cairo_create(fb->surface);
+		int i, j, ret;
+
+		each(i, 0, 2 * h) each(j, 0, 2 * w)
+			if (cell[i][j] & (V|D)) cell[i][j] = 0;
+		i = iterations++;
+		ret = solve(1, 1, 2 * w - 1, 2 * h - 1, &i);
+		show(cr, device->width, device->height);
+
+		gettimeofday(&now, NULL);
+		if (show_fps && last_fps.tv_sec) {
+			fps_draw(cr, device->name, version, &last_fps, &now);
+		}
+		last_fps = now;
+
+		cairo_destroy(cr);
+
+		fb->show (fb);
+		fb->destroy (fb);
+
+		frame++;
+		if (benchmark > 0) {
+			delta = now.tv_sec - start.tv_sec;
+			delta += (now.tv_usec - start.tv_usec)*1e-6;
+			if (delta > benchmark) {
+				printf("maze: %.2f fps\n", frame / delta);
+				break;
+			}
+		}
+
+		if (ret > 0) {
+			if (complete.tv_sec == 0)
+				complete = now;
+			delta = now.tv_sec - complete.tv_sec;
+			delta += (now.tv_usec - complete.tv_usec)*1e-6;
+			if (delta > 1.5) {
+				maze_reset();
+				iterations = 1;
+				complete.tv_sec = 0;
+			}
+		}
+	} while (!done);
+
+	if (benchmark < 0) {
+		struct framebuffer *fb = device->get_framebuffer (device);
+		cairo_t *cr = cairo_create(fb->surface);
+
+		show(cr, device->width, device->height);
+		cairo_destroy(cr);
+
+		fps_finish(fb, device->name, version);
+		fb->show (fb);
+		fb->destroy (fb);
+		pause();
+	}
+
+	return 0;
+}