src/cave/object/caveobjectmaze.cpp

   1 /*
   2  * Copyright (c) 2007-2013, Czirkos Zoltan http://code.google.com/p/gdash/
   3  *
   4  * Permission to use, copy, modify, and distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #include "config.h"
  18
  19 #include "cave/object/caveobjectmaze.hpp"
  20 #include "cave/elementproperties.hpp"
  21
  22 #include <glib/gi18n.h>
  23
  24 #include "fileops/bdcffhelper.hpp"
  25 #include "cave/caverendered.hpp"
  26 #include "misc/printf.hpp"
  27 #include "misc/logger.hpp"
  28 #include "misc/util.hpp"
  29
  30 std::string CaveMaze::get_bdcff() const
  31 {
  32     BdcffFormat f("Maze");
  33
  34     f << p1 << p2 << wall_width << path_width << horiz;
  35     f << seed[0] << seed[1] << seed[2] << seed[3] << seed[4] << wall_element << path_element;
  36     switch (maze_type) {
  37         case Perfect: f << "perfect"; break;
  38         case Unicursal: f << "unicursal"; break;
  39         case Braid: f << "braid"; break;
  40         default:
  41             g_assert_not_reached();
  42     };
  43     return f;
  44 }
  45
  46 CaveMaze* CaveMaze::clone_from_bdcff(const std::string &name, std::istream &is) const
  47 {
  48     Coordinate p1, p2;
  49     int ww, pw, horiz;
  50     int seed[5];
  51     GdElementEnum wall, path;
  52     std::string mazetype;
  53     CaveMaze::MazeType mazet;
  54
  55     if (!(is >> p1 >> p2 >> ww >> pw >> horiz >> seed[0] >> seed[1] >> seed[2] >> seed[3] >> seed[4] >> wall >> path >> mazetype))
  56         return NULL;
  57     if (gd_str_ascii_caseequal(mazetype, "unicursal"))
  58         mazet=CaveMaze::Unicursal;
  59     else if (gd_str_ascii_caseequal(mazetype, "perfect"))
  60         mazet=CaveMaze::Perfect;
  61     else if (gd_str_ascii_caseequal(mazetype, "braid"))
  62         mazet=CaveMaze::Braid;
  63     else {
  64         gd_warning(CPrintf("unknown maze type: %s, defaulting to perfect") % mazetype);
  65         mazet=CaveMaze::Perfect;
  66     }
  67     CaveMaze *m=new CaveMaze(p1, p2, wall, path, mazet);
  68     m->set_horiz(horiz);
  69     m->set_widths(ww, pw);
  70     m->set_seed(seed[0], seed[1], seed[2], seed[3], seed[4]);
  71
  72     return m;
  73 }
  74
  75 /* create a maze in a bool map. */
  76 /* recursive algorithm. */
  77 void CaveMaze::mazegen(CaveMap<bool> &maze, RandomGenerator &rand, int x, int y, int horiz)
  78 {
  79     int dirmask=15;
  80
  81     maze(x,y)=true;
  82     while (dirmask!=0) {
  83         int dir;
  84
  85         dir=rand.rand_int_range(0, 100)<horiz?2:0;      /* horiz or vert */
  86         /* if no horizontal movement possible, choose vertical */
  87         if (dir==2 && (dirmask&12)==0)
  88             dir=0;
  89         else if (dir==0 && (dirmask&3)==0)  /* and vice versa */
  90             dir=2;
  91         dir+=rand.rand_int_range(0, 2);             /* dir */
  92
  93         if (dirmask&(1<<dir)) {
  94             dirmask&=~(1<<dir);
  95
  96             switch(dir) {
  97                 case 0: /* up */
  98                     if (y>=2 && !maze(x, y-2)) {
  99                         maze(x, y-1)=true;
 100                         mazegen(maze, rand, x, y-2, horiz);
 101                     }
 102                     break;
 103                 case 1: /* down */
 104                     if (y<maze.height()-2 && !maze(x, y+2)) {
 105                         maze(x, y+1)=true;
 106                         mazegen(maze, rand, x, y+2, horiz);
 107                     }
 108                     break;
 109                 case 2: /* left */
 110                     if (x>=2 && !maze(x-2, y)) {
 111                         maze(x-1, y)=true;
 112                         mazegen(maze, rand, x-2, y, horiz);
 113                     }
 114                     break;
 115                 case 3: /* right */
 116                     if (x<maze.width()-2 && !maze(x+2, y)) {
 117                         maze(x+1, y)=true;
 118                         mazegen(maze, rand, x+2, y, horiz);
 119                     }
 120                     break;
 121                 default:
 122                     g_assert_not_reached();
 123             }
 124         }
 125     }
 126 }
 127
 128
 129 void
 130 CaveMaze::braidmaze(CaveMap<bool> &maze, RandomGenerator &rand)
 131 {
 132     int w=maze.width();
 133     int h=maze.height();
 134
 135     for (int y=0; y<h; y+=2)
 136         for (int x=0; x<w; x+=2) {
 137             int closed=0, dirs=0;
 138             int closed_dirs[4];
 139
 140             /* if it is the edge of the map, OR no path carved, then we can't go in that direction. */
 141             if (x<1 || !maze(x-1, y)) {
 142                 closed++;   /* closed from this side. */
 143                 if (x>0)
 144                     closed_dirs[dirs++]=MV_LEFT;    /* if not the edge, we might open this wall (carve a path) to remove a dead end */
 145             }
 146             /* other 3 directions similar */
 147             if (y<1 || !maze(x, y-1)) {
 148                 closed++;
 149                 if (y>0)
 150                     closed_dirs[dirs++]=MV_UP;
 151             }
 152             if (x>=w-1 || !maze(x+1, y)) {
 153                 closed++;
 154                 if (x<w-1)
 155                     closed_dirs[dirs++]=MV_RIGHT;
 156             }
 157             if (y>=h-1 || !maze(x, y+1)) {
 158                 closed++;
 159                 if (y<h-1)
 160                     closed_dirs[dirs++]=MV_DOWN;
 161             }
 162
 163             /* if closed from 3 sides, then it is a dead end. also check dirs!=0, that might fail for a 1x1 maze :) */
 164             if (closed==3 && dirs!=0) {
 165                 /* make up a random direction, and open in that direction, so dead end is removed */
 166                 int dir=closed_dirs[rand.rand_int_range(0, dirs)];
 167
 168                 switch(dir) {
 169                     case MV_LEFT: maze(x-1, y)=true; break;
 170                     case MV_UP: maze(x, y-1)=true; break;
 171                     case MV_RIGHT: maze(x+1, y)=true; break;
 172                     case MV_DOWN: maze(x, y+1)=true; break;
 173                 }
 174             }
 175         }
 176 }
 177
 178
 179 void CaveMaze::unicursalmaze(CaveMap<bool> &maze, int &w, int &h)
 180 {
 181     /* convert to unicursal maze */
 182     /* original:
 183         xxx x
 184           x x
 185         xxxxx
 186
 187         unicursal:
 188         xxxxxxx xxx
 189         x     x x x
 190         xxxxx x x x
 191             x x x x
 192         xxxxx xxx x
 193         x         x
 194         xxxxxxxxxxx
 195     */
 196     CaveMap<bool> unicursal(w*2+1, h*2+1, false);
 197
 198     for (int y=0; y<h; y++)
 199         for(int x=0; x<w; x++) {
 200             if (maze(x, y)) {
 201                 unicursal(x*2, y*2)=true;
 202                 unicursal(x*2+2, y*2)=true;
 203                 unicursal(x*2, y*2+2)=true;
 204                 unicursal(x*2+2, y*2+2)=true;
 205
 206                 if (x<1 || !maze(x-1, y)) unicursal(x*2, y*2+1)=true;
 207                 if (y<1 || !maze(x, y-1)) unicursal(x*2+1, y*2)=true;
 208                 if (x>=w-1 || !maze(x+1, y)) unicursal(x*2+2, y*2+1)=true;
 209                 if (y>=h-1 || !maze(x, y+1)) unicursal(x*2+1, y*2+2)=true;
 210             }
 211         }
 212
 213     /* change to new maze - the unicursal maze */
 214     /* copy this, as this will be drawn */
 215     maze=unicursal;
 216     h=h*2-1;
 217     w=w*2-1;
 218 }
 219
 220
 221 CaveMaze::CaveMaze(Coordinate _p1, Coordinate _p2, GdElementEnum _wall, GdElementEnum _path, MazeType _type)
 222 :   CaveRectangular(_type==Perfect?GD_MAZE:(_type==Braid?GD_MAZE_BRAID:GD_MAZE_UNICURSAL), _p1, _p2),
 223     maze_type(_type),
 224     wall_width(1),
 225     path_width(1),
 226     wall_element(_wall),
 227     path_element(_path),
 228     horiz(50)
 229 {
 230     for (int j=0; j<5; j++)
 231         seed[j]=-1;
 232 }
 233
 234 /// Set wall and path width.
 235 void CaveMaze::set_widths(int wall, int path)
 236 {
 237     wall_width=wall;
 238     path_width=path;
 239 }
 240
 241 /// Set seed values.
 242 void CaveMaze::set_seed(int s1, int s2, int s3, int s4, int s5)
 243 {
 244     seed[0]=s1;
 245     seed[1]=s2;
 246     seed[2]=s3;
 247     seed[3]=s4;
 248     seed[4]=s5;
 249 }
 250
 251 /*
 252  * This draws all kinds of mazes.
 253  *
 254  * Steps:
 255  * - draw a normal maze with walls and paths of 1 cell in width.
 256  * - if needed, convert it to braid maze or unicursal maze.
 257  * - resize the maze to the given path and wall width.
 258  */
 259 void CaveMaze::draw(CaveRendered &cave) const
 260 {
 261     /* change coordinates if not in correct order */
 262     int x1=p1.x;
 263     int y1=p1.y;
 264     int x2=p2.x;
 265     int y2=p2.y;
 266     if (y1>y2)
 267         std::swap(y1, y2);
 268     if (x1>x2)
 269         std::swap(x1, x2);
 270     int wall=this->wall_width;
 271     if (wall<1)
 272         wall=1;
 273     int path=this->path_width;
 274     if (path<1)
 275         path=1;
 276
 277     /* calculate the width and height of the maze.
 278         n=number of passages, path=path width, wall=wall width, maze=maze width.
 279        if given the number of passages, the width of the maze is:
 280
 281        n*path+(n-1)*wall=maze
 282        n*path+n*wall-wall=maze
 283        n*(path+wall)=maze+wall
 284        n=(maze+wall)/(path+wall)
 285      */
 286     /* number of passages for each side */
 287     int w=(x2-x1+1+wall)/(path+wall);
 288     int h=(y2-y1+1+wall)/(path+wall);
 289     /* and we calculate the size of the internal map */
 290     if (maze_type==Unicursal) {
 291         /* for unicursal maze, width and height must be mod2=0, and we will convert to paths&walls later */
 292         w=w/2*2;
 293         h=h/2*2;
 294     } else {
 295         /* for normal maze */
 296         w=2*(w-1)+1;
 297         h=2*(h-1)+1;
 298     }
 299
 300     RandomGenerator rand;
 301     if (seed[cave.rendered_on]==-1)
 302         rand.set_seed(cave.random.rand_int());
 303     else
 304         rand.set_seed(seed[cave.rendered_on]);
 305
 306     /* start generation only if map is big enough. otherwise the application would crash, as the editor
 307      * places maze objects during mouse click&drag with no size! */
 308
 309     /* draw maze. */
 310     CaveMap<bool> map(w, h, false);
 311     if (w>=1 && h>=1)
 312         mazegen(map, rand, 0, 0, horiz);
 313     /* if braid maze, turn the above to a braid one. */
 314     if (maze_type==Braid)
 315         braidmaze(map, rand);
 316     /* if unicursal, turn it into an unicursal one. w and h is changed! */
 317     if (w>=1 && h>=1 && maze_type==Unicursal)
 318         unicursalmaze(map, w, h);
 319
 320     /* copy map to cave with correct elements and size */
 321     /* now copy the map into the cave. the copying works like this...
 322        pwpwp
 323        xxxxx p
 324        x x   w
 325        x xxx p
 326        x     w
 327        xxxxx p
 328        columns and rows denoted with "p" are to be drawn with path width, the others with wall width. */
 329     int yk=y1;
 330     for (int y=0; y<h; y++) {
 331         for (int i=0; i<(y%2==0?path:wall); i++) {
 332             int xk=x1;
 333             for (int x=0; x<w; x++)
 334                 for (int j=0; j<(x%2==0?path:wall); j++)
 335                     cave.store_rc(xk++, yk, map(x, y)?path_element:wall_element, this);
 336
 337             /* if width is smaller than requested, fill with wall */
 338             for(int x=xk; x<=x2; x++)
 339                 cave.store_rc(x, yk, wall_element, this);
 340
 341             yk++;
 342         }
 343     }
 344     /* if height is smaller than requested, fill with wall */
 345     for (int y=yk; y<=y2; y++)
 346         for (int x=x1; x<=x2; x++)
 347             cave.store_rc(x, y, wall_element, this);
 348 }
 349
 350 PropertyDescription const CaveMaze::descriptor[] = {
 351     {"", GD_TAB, 0, N_("Maze")},
 352     {"", GD_TYPE_BOOLEAN_LEVELS, 0, N_("Levels"), GetterBase::create_new(&CaveMaze::seen_on), N_("Levels on which this object is visible.")},
 353     {"", GD_TYPE_INT_LEVELS, 0, N_("Seed"), GetterBase::create_new(&CaveMaze::seed), N_("The random seed value for the random number generator. If it is -1, the cave is different every time played. If not, the same pattern is always recreated."), -1, GD_CAVE_SEED_MAX},
 354     {"", GD_TYPE_COORDINATE, 0, N_("Start corner"), GetterBase::create_new(&CaveMaze::p1), N_("Specifies one of the corners of the object."), 0, 127},
 355     {"", GD_TYPE_COORDINATE, 0, N_("End corner"), GetterBase::create_new(&CaveMaze::p2), N_("Specifies one of the corners of the object."), 0, 127},
 356     {"", GD_TYPE_INT, 0, N_("Wall width"), GetterBase::create_new(&CaveMaze::wall_width), NULL, 1, 40},
 357     {"", GD_TYPE_INT, 0, N_("Path width"), GetterBase::create_new(&CaveMaze::path_width), NULL, 1, 40},
 358     {"", GD_TYPE_ELEMENT, 0, N_("Wall element"), GetterBase::create_new(&CaveMaze::wall_element), N_("Walls of the maze are drawn using this element.")},
 359     {"", GD_TYPE_ELEMENT, 0, N_("Path element"), GetterBase::create_new(&CaveMaze::path_element), N_("This element sets the paths in the maze.")},
 360     {"", GD_TYPE_INT, 0, N_("Horizontal %"), GetterBase::create_new(&CaveMaze::horiz), N_("This number controls, how much the algorithm will prefer horizontal routes."), 0, 100},
 361     {NULL},
 362 };
 363
 364 PropertyDescription const* CaveMaze::get_description_array() const
 365 {
 366     return descriptor;
 367 }
 368
 369 std::string CaveMaze::get_description_markup() const
 370 {
 371     return SPrintf(_("Maze from %d,%d to %d,%d, wall <b>%s</b>, path <b>%s</b>"))
 372         % p1.x % p1.y % p2.x % p2.y % gd_element_properties[wall_element].lowercase_name % gd_element_properties[path_element].lowercase_name;
 373 }