1
/* $Id: algorithms.c,v 1.12 2004/02/01 13:22:08 mitch Exp $
2
* Contains routines for generating mazes, somewhat intertwined with
3
* Gimp plug-in-maze specific stuff.
5
* Kevin Turner <acapnotic@users.sourceforge.net>
6
* http://gimp-plug-ins.sourceforge.net/maze/
9
/* mazegen code from rec.games.programmer's maze-faq:
10
* * maz.c - generate a maze
12
* * algorithm posted to rec.games.programmer by jallen@ic.sunysb.edu
13
* * program cleaned and reorganized by mzraly@ldbvax.dnet.lotus.com
15
* * don't make people pay for this, or I'll jump up and down and
16
* * yell and scream and embarass you in front of your friends...
19
/* I've put a HTMLized version of the FAQ up at
20
* http://www.poboxes.com/kevint/gimp/maze-faq/maze-faq.html
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.
46
#include "libgimp/gimp.h"
47
#include "libgimp/gimpui.h"
48
#include "libgimp/stdplugins-intl.h"
50
extern MazeValues mvals;
53
void mazegen(gint pos,
58
void mazegen_tileable(gint pos,
67
void prim_tileable(gchar *maz,
71
#define ABSMOD(A,B) ( ((A) < 0) ? (((B) + (A)) % (B)) : ((A) % (B)) )
73
/* Since we are using a 1D array on 2D space, we need to do our own
74
calculations. (Ok, so there are ways of doing dynamically allocated
75
2D arrays, but we started this way, so let's stick with it. */
77
/* The difference between CELL_* and WALL_* is that cell moves two spaces,
78
while wall moves one. */
80
/* Macros assume that x and y will be defined where they are used. */
81
/* A return of -1 means "no such place, don't go there". */
82
#define CELL_UP(POS) ((POS) < (x*2) ? -1 : (POS) - x - x)
83
#define CELL_DOWN(POS) ((POS) >= x*(y-2) ? -1 : (POS) + x + x)
84
#define CELL_LEFT(POS) (((POS) % x) <= 1 ? -1 : (POS) - 2)
85
#define CELL_RIGHT(POS) (((POS) % x) >= (x - 2) ? -1 : (POS) + 2)
87
/* With walls, we don't need to check for boundaries, since we are
88
assured that there *is* a valid cell on the other side of the
90
#define WALL_UP(POS) ((POS) - x)
91
#define WALL_DOWN(POS) ((POS) + x)
92
#define WALL_LEFT(POS) ((POS) - 1)
93
#define WALL_RIGHT(POS) ((POS) + 1)
95
/***** For tileable mazes *****/
97
#define CELL_UP_TILEABLE(POS) ((POS) < (x*2) ? x*(y-2)+(POS) : (POS) - x - x)
98
#define CELL_DOWN_TILEABLE(POS) ((POS) >= x*(y-2) ? (POS) - x*(y-2) : (POS) + x + x)
99
#define CELL_LEFT_TILEABLE(POS) (((POS) % x) <= 1 ? (POS) + x - 2 : (POS) - 2)
100
#define CELL_RIGHT_TILEABLE(POS) (((POS) % x) >= (x - 2) ? (POS) + 2 - x : (POS) + 2)
101
/* Up and left need checks, but down and right should never have to
102
wrap on an even sized maze. */
103
#define WALL_UP_TILEABLE(POS) ((POS) < x ? x*(y-1)+(POS) : (POS) - x)
104
#define WALL_DOWN_TILEABLE(POS) ((POS) + x)
105
#define WALL_LEFT_TILEABLE(POS) (((POS) % x) == 0 ? (POS) + x - 1 : (POS) - 1)
106
#define WALL_RIGHT_TILEABLE(POS) ((POS) + 1)
108
/* Down and right with checks.
109
#define WALL_DOWN_TILEABLE(POS) ((POS) >= x*(y-1) ? (POS) - x * (y-1) : (POS) + x)
110
#define WALL_RIGHT_TILEABLE(POS) (((POS) % x) == (x - 1) ? (POS) + 1 - x : (POS) + 1)
113
/* The Incredible Recursive Maze Generation Routine */
114
/* Ripped from rec.programmers.games maze-faq */
115
/* Modified and commented by me, Kevin Turner. */
117
mazegen(gint pos, gchar *maz, gint x, gint y, gint rnd)
122
/* Punch a hole here... */
125
/* If there is a wall two rows above us, bit 1 is 1. */
126
while((d= (pos <= (x * 2) ? 0 : (maz[pos - x - x ] ? 0 : 1))
127
/* If there is a wall two rows below us, bit 2 is 1. */
128
| (pos >= x * (y - 2) ? 0 : (maz[pos + x + x] ? 0 : 2))
129
/* If there is a wall two columns to the right, bit 3 is 1. */
130
| (pos % x == x - 2 ? 0 : (maz[pos + 2] ? 0 : 4))
131
/* If there is a wall two colums to the left, bit 4 is 1. */
132
| ((pos % x == 1 ) ? 0 : (maz[pos-2] ? 0 : 8)))) {
134
/* Note if all bits are 0, d is false, we don't do this
135
while loop, we don't call ourselves again, so this branch
138
/* I see what this loop does (more or less), but I don't know
139
_why_ it does it this way... I also haven't figured out exactly
140
which values of multiple will work and which won't. */
142
rnd = (rnd * mvals.multiple + mvals.offset);
144
if (++c > 100) { /* Break and try to salvage something */
145
i=99; /* if it looks like we're going to be */
146
break; /* here forever... */
148
} while ( !(d & ( 1 << i) ) );
149
/* ...While there's *not* a wall in direction i. */
150
/* (stop looping when there is) */
152
switch (i) { /* This is simple enough. */
153
case 0: /* Go in the direction we just figured . . . */
166
return; /* Hey neat, broken mazes! */
167
break; /* (Umm... Wow... Yeah, neat.) */
169
g_warning("maze: mazegen: Going in unknown direction.\n"
170
"i: %d, d: %d, seed: %d, mw: %d, mh: %d, mult: %d, offset: %d\n",
171
i, d,mvals.seed, x, y, mvals.multiple, mvals.offset);
175
/* And punch a hole there. */
178
/* Now, start again just past where we punched the hole... */
179
mazegen(pos + 2 * j, maz, x, y, rnd);
181
} /* End while(d=...) Loop */
183
/* This routine is quite quick, even for rather large mazes.
184
For that reason, it doesn't need a progress bar. */
188
/* Tileable mazes are my creation, based on the routine above. */
190
mazegen_tileable(gint pos, gchar *maz, gint x, gint y, gint rnd)
195
/* Punch a hole here... */
198
/* If there is a wall two rows above us, bit 1 is 1. */
199
while((d= (maz[CELL_UP_TILEABLE(pos)] ? 0 : 1)
200
/* If there is a wall two rows below us, bit 2 is 1. */
201
| (maz[CELL_DOWN_TILEABLE(pos)] ? 0 : 2)
202
/* If there is a wall two columns to the right, bit 3 is 1. */
203
| (maz[CELL_RIGHT_TILEABLE(pos)] ? 0 : 4)
204
/* If there is a wall two colums to the left, bit 4 is 1. */
205
| (maz[CELL_LEFT_TILEABLE(pos)] ? 0 : 8))) {
207
/* Note if all bits are 0, d is false, we don't do this
208
while loop, we don't call ourselves again, so this branch
211
/* I see what this loop does (more or less), but I don't know
212
_why_ it does it this way... I also haven't figured out exactly
213
which values of multiple will work and which won't. */
215
rnd = (rnd * mvals.multiple + mvals.offset);
217
if (++c > 100) { /* Break and try to salvage something */
218
i=99; /* if it looks like we're going to be */
219
break; /* here forever... */
221
} while ( !(d & ( 1 << i) ) );
222
/* ...While there's *not* a wall in direction i. */
223
/* (stop looping when there is) */
225
switch (i) { /* This is simple enough. */
226
case 0: /* Go in the direction we just figured . . . */
227
maz[WALL_UP_TILEABLE(pos)]=IN;
228
npos = CELL_UP_TILEABLE(pos);
231
maz[WALL_DOWN_TILEABLE(pos)]=IN;
232
npos = CELL_DOWN_TILEABLE(pos);
235
maz[WALL_RIGHT_TILEABLE(pos)]=IN;
236
npos = CELL_RIGHT_TILEABLE(pos);
239
maz[WALL_LEFT_TILEABLE(pos)]=IN;
240
npos = CELL_LEFT_TILEABLE(pos);
243
return; /* Hey neat, broken mazes! */
244
break; /* (Umm... Wow... Yeah, neat.) */
246
g_warning("maze: mazegen_tileable: Going in unknown direction.\n"
247
"i: %d, d: %d, seed: %d, mw: %d, mh: %d, mult: %d, offset: %d\n",
248
i, d,mvals.seed, x, y, mvals.multiple, mvals.offset);
252
/* Now, start again just past where we punched the hole... */
253
mazegen_tileable(npos, maz, x, y, rnd);
255
} /* End while(d=...) Loop */
262
print_glist(gpointer data, gpointer user_data)
264
g_print("%d ",(guint)data);
268
/* This function (as well as prim_tileable) make use of the somewhat
269
unclean practice of storing ints as pointers. I've been informed
270
that this may cause problems with 64-bit stuff. However, hopefully
271
it will be okay, since the only values stored are positive. If it
272
does break, let me know, and I'll go cry in a corner for a while
273
before I get up the strength to re-code it. */
275
prim(gint pos, gchar *maz, guint x, guint y)
277
GSList *front_cells=NULL;
279
gint up, down, left, right; /* Not unsigned, because macros return -1. */
280
guint progress=0, max_progress;
283
gint rnd = mvals.seed;
285
g_rand_set_seed (gr, rnd);
287
gimp_progress_init (_("Constructing maze using Prim's Algorithm..."));
289
/* OUT is zero, so we should be already initalized. */
293
/* Starting position has already been determined by the calling function. */
297
/* For now, repeating everything four times seems manageable. But when
298
Gimp is extended to drawings in n-dimensional space instead of 2D,
299
this will require a bit of a re-write. */
304
right=CELL_RIGHT(pos);
308
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(up));
312
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(down));
316
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(left));
320
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(right));
323
/* While frontier is not empty do the following... */
324
while(g_slist_length(front_cells) > 0) {
326
/* Remove one cell at random from frontier and place it in IN. */
327
current = g_rand_int_range (gr, 0, g_slist_length(front_cells));
328
pos = GPOINTER_TO_INT(g_slist_nth(front_cells,current)->data);
330
front_cells=g_slist_remove(front_cells,GINT_TO_POINTER(pos));
333
/* If the cell has any neighbors in OUT, remove them from
334
OUT and place them in FRONTIER. */
339
right=CELL_RIGHT(pos);
346
front_cells=g_slist_prepend(front_cells,
347
GINT_TO_POINTER(up));
360
front_cells=g_slist_prepend(front_cells,
361
GINT_TO_POINTER(down));
374
front_cells=g_slist_prepend(front_cells,
375
GINT_TO_POINTER(left));
385
switch (maz[right]) {
388
front_cells=g_slist_prepend(front_cells,
389
GINT_TO_POINTER(right));
399
/* The cell is guaranteed to have at least one neighbor in
400
IN (otherwise it would not have been in FRONTIER); pick
401
one such neighbor at random and connect it to the new
402
cell (ie knock out a wall). */
405
g_warning("maze: prim: Lack of neighbors.\n"
406
"seed: %d, mw: %d, mh: %d, mult: %d, offset: %d\n",
407
mvals.seed, x, y, mvals.multiple, mvals.offset);
413
rnd = (rnd * mvals.multiple + mvals.offset);
415
if (++c > 100) { /* Break and try to salvage something */
416
i=99; /* if it looks like we're going to be */
417
break; /* here forever... */
419
} while ( !(d & ( 1 << i) ) );
423
maz[WALL_UP(pos)]=IN;
426
maz[WALL_DOWN(pos)]=IN;
429
maz[WALL_LEFT(pos)]=IN;
432
maz[WALL_RIGHT(pos)]=IN;
437
g_warning("maze: prim: Going in unknown direction.\n"
438
"i: %d, d: %d, seed: %d, mw: %d, mh: %d, mult: %d, offset: %d\n",
439
i, d, mvals.seed, x, y, mvals.multiple, mvals.offset);
442
if (progress++ % PRIMS_PROGRESS_UPDATE)
443
gimp_progress_update ((double) progress / (double) max_progress);
445
} /* while front_cells */
447
g_slist_free(front_cells);
451
prim_tileable(gchar *maz, guint x, guint y)
453
GSList *front_cells=NULL;
455
guint up, down, left, right;
456
guint progress=0, max_progress;
459
gint rnd = mvals.seed;
461
g_rand_set_seed (gr, rnd);
463
gimp_progress_init (_("Constructing tileable maze using Prim's Algorithm..."));
465
/* OUT is zero, so we should be already initalized. */
469
/* Pick someplace to start. */
471
pos = x * 2 * g_rand_int_range (gr, 0, y/2) + 2 * g_rand_int_range(gr, 0, x/2);
476
up=CELL_UP_TILEABLE(pos);
477
down=CELL_DOWN_TILEABLE(pos);
478
left=CELL_LEFT_TILEABLE(pos);
479
right=CELL_RIGHT_TILEABLE(pos);
481
maz[up]=maz[down]=maz[left]=maz[right]=FRONTIER;
483
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(up));
484
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(down));
485
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(left));
486
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(right));
488
/* While frontier is not empty do the following... */
489
while(g_slist_length(front_cells) > 0) {
491
/* Remove one cell at random from frontier and place it in IN. */
492
current = g_rand_int_range (gr, 0, g_slist_length(front_cells));
493
pos = GPOINTER_TO_UINT(g_slist_nth(front_cells,current)->data);
495
front_cells=g_slist_remove(front_cells,GUINT_TO_POINTER(pos));
498
/* If the cell has any neighbors in OUT, remove them from
499
OUT and place them in FRONTIER. */
501
up=CELL_UP_TILEABLE(pos);
502
down=CELL_DOWN_TILEABLE(pos);
503
left=CELL_LEFT_TILEABLE(pos);
504
right=CELL_RIGHT_TILEABLE(pos);
510
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(up));
521
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(down));
532
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(left));
540
switch (maz[right]) {
543
front_cells=g_slist_append(front_cells,GINT_TO_POINTER(right));
552
/* The cell is guaranteed to have at least one neighbor in
553
IN (otherwise it would not have been in FRONTIER); pick
554
one such neighbor at random and connect it to the new
555
cell (ie knock out a wall). */
558
g_warning("maze: prim's tileable: Lack of neighbors.\n"
559
"seed: %d, mw: %d, mh: %d, mult: %d, offset: %d\n",
560
mvals.seed, x, y, mvals.multiple, mvals.offset);
566
rnd = (rnd * mvals.multiple + mvals.offset);
568
if (++c > 100) { /* Break and try to salvage something */
569
i=99; /* if it looks like we're going to be */
570
break; /* here forever... */
572
} while ( !(d & ( 1 << i) ) );
576
maz[WALL_UP_TILEABLE(pos)]=IN;
579
maz[WALL_DOWN_TILEABLE(pos)]=IN;
582
maz[WALL_LEFT_TILEABLE(pos)]=IN;
585
maz[WALL_RIGHT_TILEABLE(pos)]=IN;
590
g_warning("maze: prim's tileable: Going in unknown direction.\n"
591
"i: %d, d: %d, seed: %d, mw: %d, mh: %d, mult: %d, offset: %d\n",
592
i, d, mvals.seed, x, y, mvals.multiple, mvals.offset);
595
if (progress++ % PRIMS_PROGRESS_UPDATE)
596
gimp_progress_update ((double) progress / (double) max_progress);
598
} /* while front_cells */
600
g_slist_free(front_cells);
added
removed
plug-ins/maze/algorithms.c
