1
/* $Id: maze.c,v 1.37 2004/11/18 08:59:56 neo Exp $
2
* This is a plug-in for the GIMP.
5
* Implemented as a GIMP 0.99 Plugin by
6
* Kevin Turner <acapnotic@users.sourceforge.net>
7
* http://gimp-plug-ins.sourceforge.net/maze/
9
* Code generously borrowed from assorted GIMP plugins
10
* and used as a template to get me started on this one. :)
13
* maze_face.c: Rework the divboxes to be more like spinbuttons.
15
* Maybe add an option to kill the outer border.
17
* Fix that stray line down there between maze wall and dead space border...
19
* handy.c: Make get_colors() work with indexed. * HELP! *
24
* This program is free software; you can redistribute it and/or modify
25
* it under the terms of the GNU General Public License as published by
26
* the Free Software Foundation; either version 2 of the License, or
27
* (at your option) any later version.
29
* This program is distributed in the hope that it will be useful,
30
* but WITHOUT ANY WARRANTY; without even the implied warranty of
31
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32
* GNU General Public License for more details.
34
* You should have received a copy of the GNU General Public License
35
* along with this program; if not, write to the Free Software
36
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
45
#include "libgimp/gimp.h"
46
#include "libgimp/gimpui.h"
50
#include "libgimp/stdplugins-intl.h"
53
static void query (void);
54
static void run (const gchar *name,
56
const GimpParam *param,
58
GimpParam **return_vals);
60
static void maze (GimpDrawable *drawable);
62
static void mask_maze (gint32 selection_ID,
74
extern gint maze_dialog (void);
77
extern void mazegen (gint pos,
82
extern void mazegen_tileable (gint pos,
87
extern void prim (guint pos,
91
extern void prim_tileable (guchar *maz,
96
extern void get_colors (GimpDrawable *drawable,
100
extern void drawbox (GimpPixelRgn *dest_rgn,
108
GimpPlugInInfo PLUG_IN_INFO =
110
NULL, /* init_proc */
111
NULL, /* quit_proc */
112
query, /* query_proc */
118
5, /* Passage width */
119
5, /* Passage height */
121
FALSE, /* Tileable? */
122
57, /* multiple * These two had "Experiment with this?" comments */
123
1, /* offset * in the maz.c source, so, lets expiriment. :) */
124
DEPTH_FIRST, /* Algorithm */
125
TRUE, /* random_seed */
139
static GimpParamDef args[] =
141
{ GIMP_PDB_INT32, "run_mode", "Interactive, non-interactive" },
142
{ GIMP_PDB_IMAGE, "image_ID", "(unused)" },
143
{ GIMP_PDB_DRAWABLE, "drawable_ID", "ID of drawable" },
144
/* If we did have parameters, these be them: */
145
{ GIMP_PDB_INT16, "width", "Width of the passages" },
146
{ GIMP_PDB_INT16, "height", "Height of the passages"},
147
{ GIMP_PDB_INT8, "tileable", "Tileable maze?"},
148
{ GIMP_PDB_INT8, "algorithm", "Generation algorithm"
149
"(0=DEPTH FIRST, 1=PRIM'S ALGORITHM)" },
150
{ GIMP_PDB_INT32, "seed", "Random Seed"},
151
{ GIMP_PDB_INT16, "multiple", "Multiple (use 57)" },
152
{ GIMP_PDB_INT16, "offset", "Offset (use 1)" }
155
gimp_install_procedure ("plug_in_maze",
157
"Generates a maze using either the depth-first "
158
"search method or Prim's algorithm. Can make "
159
"tileable mazes too.",
160
"Kevin Turner <kevint@poboxes.com>",
164
"RGB*, GRAY*, INDEXED*",
166
G_N_ELEMENTS (args), 0,
169
gimp_plugin_menu_register ("plug_in_maze",
170
"<Image>/Filters/Render/Pattern");
174
run (const gchar *name,
176
const GimpParam *param,
178
GimpParam **return_vals)
180
static GimpParam values[1];
181
GimpDrawable *drawable;
182
GimpRunMode run_mode;
183
GimpPDBStatusType status = GIMP_PDB_SUCCESS;
187
g_print("maze PID: %d\n",getpid());
189
run_mode = param[0].data.d_int32;
192
*return_vals = values;
198
values[0].type = GIMP_PDB_STATUS;
199
values[0].data.d_status = status;
201
drawable = gimp_drawable_get (param[2].data.d_drawable);
205
case GIMP_RUN_INTERACTIVE:
206
/* Possibly retrieve data */
207
gimp_get_data ("plug_in_maze", &mvals);
209
/* The interface needs to know the dimensions of the image... */
210
gimp_drawable_mask_bounds (drawable->drawable_id, &x1, &y1, &x2, &y2);
214
/* Acquire info with a dialog */
215
if (! maze_dialog ())
217
gimp_drawable_detach (drawable);
222
case GIMP_RUN_NONINTERACTIVE:
224
status = GIMP_PDB_CALLING_ERROR;
226
if (status == GIMP_PDB_SUCCESS)
228
mvals.width = (gint16) param[3].data.d_int16;
229
mvals.height = (gint16) param[4].data.d_int16;
230
mvals.tile = (gint8) param[5].data.d_int8;
231
mvals.algorithm = (gint8) param[6].data.d_int8;
232
mvals.seed = (guint32) param[7].data.d_int32;
233
mvals.multiple = (gint16) param[8].data.d_int16;
234
mvals.offset = (gint16) param[9].data.d_int16;
236
if (mvals.random_seed)
237
mvals.seed = g_random_int ();
241
case GIMP_RUN_WITH_LAST_VALS:
242
/* Possibly retrieve data */
243
gimp_get_data ("plug_in_maze", &mvals);
245
if (mvals.random_seed)
246
mvals.seed = g_random_int ();
253
/* color, gray, or indexed... hmm, miss anything? ;) */
254
if (gimp_drawable_is_rgb (drawable->drawable_id) ||
255
gimp_drawable_is_gray (drawable->drawable_id) ||
256
gimp_drawable_is_indexed (drawable->drawable_id))
260
if (run_mode != GIMP_RUN_NONINTERACTIVE)
261
gimp_displays_flush ();
263
if (run_mode == GIMP_RUN_INTERACTIVE ||
264
(run_mode == GIMP_RUN_WITH_LAST_VALS))
265
gimp_set_data ("plug_in_maze", &mvals, sizeof (MazeValues));
269
status = GIMP_PDB_EXECUTION_ERROR;
272
values[0].data.d_status = status;
275
gimp_drawable_detach (drawable);
280
maze_dump (guchar *maz, gint mw, gint mh)
285
for (yy = 0; yy < mh; yy++)
287
for (xx = 0; xx < mw; xx++)
288
g_print ("%3d ", maz[foo++]);
294
maze_dumpX (guchar *maz, gint mw, gint mh)
299
for (yy = 0; yy < mh; yy++)
301
for (xx = 0; xx < mw; xx++)
302
g_print ("%c", maz[foo++] ? 'X' : '.');
309
maze (GimpDrawable * drawable)
311
GimpPixelRgn dest_rgn;
314
guint progress, max_progress;
315
gint x1, y1, x2, y2, x, y;
317
gint maz_x, maz_xx, maz_row, maz_yy;
320
gboolean active_selection;
325
/* Gets the input area... */
326
active_selection = gimp_drawable_mask_bounds (drawable->drawable_id,
329
/***************** Maze Stuff Happens Here ***************/
331
mw = (x2-x1) / mvals.width;
332
mh = (y2-y1) / mvals.height;
336
mw -= !(mw & 1); /* mazegen doesn't work with even-sized mazes. */
337
mh -= !(mh & 1); /* Note I don't warn the user about this... */
341
/* On the other hand, tileable mazes must be even. */
346
/* It will really suck if your tileable maze ends up with this dead
347
space around it. Oh well, life is hard. */
348
deadx = ((x2-x1) - mw * mvals.width) / 2;
349
deady = ((y2-y1) - mh * mvals.height) / 2;
351
maz = g_new0 (guchar, mw * mh);
354
printf("x: %d\ty: %d\nmw: %d\tmh: %d\ndx: %d\tdy: %d\nwidth:%d\theight: %d\n",
355
(x2 - x1), (y2 - y1), mw, mh, deadx, deady, mvals.width, mvals.height);
359
switch (mvals.algorithm)
362
case PRIMS_ALGORITHM:
365
g_warning ("maze: Invalid algorithm choice %d", mvals.algorithm);
370
switch (mvals.algorithm)
373
mazegen_tileable (0, maz, mw, mh, mvals.seed);
376
case PRIMS_ALGORITHM:
377
prim_tileable (maz, mw, mh);
387
if (active_selection)
389
/* Mask and draw mazes until there's no
391
mask_maze (drawable->drawable_id,
392
maz, mw, mh, x1, x2, y1, y2, deadx, deady);
394
for (maz_yy = mw; maz_yy < (mh * mw); maz_yy += 2 * mw)
396
for (maz_xx = 1; maz_xx < mw; maz_xx += 2)
398
if (maz[maz_yy + maz_xx] == 0)
400
switch (mvals.algorithm)
403
mazegen (maz_yy+maz_xx, maz, mw, mh, mvals.seed);
406
case PRIMS_ALGORITHM:
407
prim (maz_yy+maz_xx, maz, mw, mh);
419
/* No active selection. */
422
switch (mvals.algorithm)
425
mazegen (pos, maz, mw, mh, mvals.seed);
428
case PRIMS_ALGORITHM:
429
prim (pos, maz, mw, mh);
438
/************** Begin Drawing *********************/
440
/* Initialize pixel region (?) */
441
gimp_pixel_rgn_init (&dest_rgn, drawable, x1, y1, (x2 - x1), (y2 - y1),
445
max_progress = (x2 - x1) * (y2 - y1);
447
/* Get the foreground and background colors */
448
get_colors (drawable, fg, bg);
450
gimp_progress_init (_("Drawing Maze..."));
452
for (pr = gimp_pixel_rgns_register (1, &dest_rgn);
454
pr = gimp_pixel_rgns_process (pr))
456
x = dest_rgn.x - x1 - deadx;
457
y = dest_rgn.y - y1 - deady;
459
/* First boxes by edge of tile must be handled specially
460
because they may have started on a previous tile,
461
unbeknownst to us. */
463
dx = mvals.width - (x % mvals.width);
464
dy = mvals.height - (y % mvals.height);
465
maz_x = x/mvals.width;
466
maz_row = mw * (y/mvals.height);
468
/* Draws the upper-left [split] box */
469
drawbox (&dest_rgn, 0, 0, dx, dy,
470
(maz[maz_row + maz_x] == IN) ? fg : bg);
473
/* Draw the top row [split] boxes */
474
for (xx=dx; xx < dest_rgn.w; xx+=mvals.width)
476
drawbox (&dest_rgn, xx, 0, mvals.width, dy,
477
(maz[maz_row + maz_xx++] == IN) ? fg : bg);
480
maz_yy = maz_row + mw;
482
for (yy = dy; yy < dest_rgn.h; yy += mvals.height)
484
drawbox (&dest_rgn, 0, yy, dx, mvals.height,
485
(maz[maz_yy + maz_x] == IN) ? fg : bg);
490
/* Everything else */
491
for (yy = dy; yy < dest_rgn.h; yy += mvals.height)
493
maz_xx = maz_x; maz_row+=mw;
495
for (xx = dx; xx < dest_rgn.w; xx += mvals.width)
497
drawbox (&dest_rgn, xx, yy, mvals.width, mvals.height,
498
(maz[maz_row + maz_xx++] == IN) ? fg : bg);
502
progress += dest_rgn.w * dest_rgn.h;
503
gimp_progress_update ((double) progress / (double) max_progress);
504
/* Indicate progress in drawing. */
507
gimp_drawable_flush (drawable);
508
gimp_drawable_merge_shadow (drawable->drawable_id, TRUE);
509
gimp_drawable_update (drawable->drawable_id, x1, y1, (x2 - x1), (y2 - y1));
514
* Depth first: Nonzero cells will not be connected to or visited.
516
* Cells that are not IN will not be connected to.
517
* Cells that are not OUT will not be converted to FRONTIER.
519
* So we'll put unavailable cells in a non-zero non-in non-out class
523
/* But first... A little discussion about cells. */
525
/* In the eyes of the generation algorithms, the world is made up of
526
* two sorts of things: Cells, and the walls between them. Walls can
527
* be knocked out, and then you have a passage between cells. The
528
* drawing routine has a simpler view of life... Everything is a
529
* pixel. Or a block of pixels. It makes no distinction between
530
* passages, walls, and cells.
532
* We may also make the distinction between two different types of
533
* passages: horizontal and vertical. With that in mind, a
534
* part of the world looks something like this:
536
* @-@-@-@- Where @ is a cell, | is a vertical passage, and - is a
537
* | | | | horizontal passsage.
539
* | | | | Remember, the maze generation routines will not rest
540
* until the maze is full, that is, every cell is connected
541
* to another. Already, we can determine a few things about the final
542
* maze. We know which blocks will be cells, which blocks may become
543
* passages (and we know what sort), and we also notice that there are
544
* some blocks that will never be either cells or passages.
546
* Now, back to our masking routine... To save a little time, lets
547
* just take sample points from the block. We'll sample a point from
548
* the top and the bottom of vertical passages, left/right for
549
* horizontal, and, hmm, left/right/top/bottom for cells. And of
550
* course, we needn't concern ourselves with the others. We could
551
* also sample the midpoint of each...
552
* Then what we'll do is see if the average is higher than some magic
553
* threshold number, and if so, we let maze happen there. Otherwise
557
/* And, uh, that's on the TODO list. Looks like I spent so much time
558
* writing comments I haven't left enough to implement the code. :)
559
* Right now we only sample one point. */
561
mask_maze (gint32 drawable_ID, guchar *maz, guint mw, guint mh,
562
gint x1, gint x2, gint y1, gint y2, gint deadx, gint deady)
565
GimpPixelRgn sel_rgn;
566
gint xx0=0, yy0=0, xoff, yoff;
570
gint cur_row, cur_col;
571
gint x1half, x2half, y1half, y2half;
575
gimp_image_get_selection (gimp_drawable_get_image (drawable_ID))) == -1)
578
gimp_pixel_rgn_init (&sel_rgn, gimp_drawable_get (selection_ID),
579
x1, y1, (x2-x1), (y2-y1),
581
gimp_drawable_offsets (drawable_ID, &xoff, &yoff);
583
/* Special cases: If mw or mh < 3 */
584
/* FIXME (Currently works, but inefficiently.) */
588
linebuf = g_new (guchar, sel_rgn.w * sel_rgn.bpp);
590
xx0 = x1 + deadx + mvals.width + xoff;
591
yy0 = y1 + deady + mvals.height + yoff;
593
x1half = mvals.width / 2;
594
x2half = mvals.width - 1;
596
y1half = mvals.height / 2;
597
y2half = mvals.height - 1;
599
/* Here, yy is with respect to the drawable (or something),
600
whereas xx is with respect to the row buffer. */
604
for (cur_row=1; cur_row < mh; cur_row += 2)
606
gimp_pixel_rgn_get_row (&sel_rgn, linebuf, x1+xoff, yy, (x2 - x1));
608
cur_col = 1; xx = mvals.width;
613
maz[cur_row * mw + cur_col] =
614
(linebuf[xx] + linebuf[xx + x1half] + linebuf[xx+x2half]) / 5;
621
maz[cur_row * mw + cur_col] =
622
(linebuf[xx] + linebuf[xx + x1half] + linebuf[xx+x2half]) / 3;
629
yy += 2 * mvals.height;
631
} /* next cur_row += 2 */
633
/* Done doing horizontal scans, change this from a row buffer to
636
linebuf = g_new (guchar, sel_rgn.h * sel_rgn.bpp);
638
/* Now xx is with respect to the drawable (or whatever),
639
and yy is with respect to the row buffer. */
642
for (cur_col = 1; cur_col < mw; cur_col += 2)
644
gimp_pixel_rgn_get_col (&sel_rgn, linebuf, xx, y1, (y2-y1));
646
cur_row = 1; yy = mvals.height;
651
maz[cur_row * mw + cur_col] +=
652
(linebuf[yy] + linebuf[yy+y2half]) / 5;
659
maz[cur_row * mw + cur_col] =
660
(linebuf[yy] + linebuf[yy + y1half] + linebuf[yy+y2half]) / 3;
666
xx += 2 * mvals.width;
672
/* Do the alpha -> masked conversion. */
674
for (yy = 0; yy < mh; yy++)
676
for (xx = 0; xx < mw; xx++)
678
maz[foo] = ( maz[foo] < MAZE_ALPHA_THRESHOLD ) ? MASKED : OUT;
685
/* The attempt to implement this with tiles: (it wasn't fun) */
690
/* Tiles make my life decidedly difficult here. There are too
691
* many special cases... "What if a tile starts less/more than
692
* halfway through a block? What if we get a narrow edge-tile
693
* that..." etc, etc. I shall investigate other options.
694
* Possibly a row buffer, or can we use something other than this
695
* black-magic gimp_pixel_rgns_register call to get tiles of
696
* different sizes? Now that'd be nice... */
698
for (pr = gimp_pixel_rgns_register (1, &sel_rgn);
700
pr = gimp_pixel_rgns_process (pr))
702
/* This gives us coordinates relative to the starting point
703
* of the maze grid. Negative values happen here if there
705
x = sel_rgn.x - x1 - deadx;
706
y = sel_rgn.y - y1 - deady;
708
/* These coordinates are relative to the current tile. */
709
/* This starts us off at the first block boundary in the
712
/* e.g. with x=16 and width=10.
716
x: 6789!123456789!123456789!12
717
....|.........|.........|..
718
xx: 0123456789!123456789!123456
720
So to start on the boundary, begin at 4.
722
For the case x=0, 10-0=10. So xx0 will always between 1 and width. */
724
xx0 = mvals.width - (x % mvals.width);
725
yy0 = mvals.height - (y % mvals.height);
727
/* Find the corresponding row and column in the maze. */
728
maz_x = (x+xx0)/mvals.width;
729
maz_row = mw * ((y + yy0)/mvals.height);
731
for (yy = yy0 * sel_rgn.rowstride;
732
yy < sel_rgn.h * sel_rgn.rowstride;
733
yy += (mvals.height * sel_rgn.rowstride))
736
for (xx = xx0 * sel_rgn.bpp;
738
xx += mvals.width * sel_rgn.bpp)
740
if (sel_rgn.data[yy+xx] < MAZE_ALPHA_THRESHOLD)
741
maz[maz_row+maz_xx]=MASKED;
748
} /* next pr sel_rgn tile thing */
750
/* maze_dump(maz,mw,mh); */