--- deliantra/server/random_maps/layout.C 2010/07/03 02:19:10 1.14 +++ deliantra/server/random_maps/layout.C 2010/07/04 01:01:42 1.21 @@ -79,7 +79,8 @@ void layout::fill (char fill) { - memset (data [0], fill, w * h); + //memset (data [0], fill, w * h); // only when contiguous :/ + fill_rect (0, 0, w, h, fill); } void @@ -222,22 +223,24 @@ } static inline void -make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d) +make_tunnel (layout &dist, pointlist &seeds, int x, int y, U8 d, int perturb) { for (;;) { point neigh[4]; int ncnt = 0; - if (x > 0 && U8 (dist [x - 1][y]) <= d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y); - if (x < dist.w - 1 && U8 (dist [x + 1][y]) <= d && dist [x + 1][y] > 1) neigh [ncnt++] = point (x + 1, y); - if (y > 0 && U8 (dist [x][y - 1]) <= d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1); - if (y < dist.h - 1 && U8 (dist [x][y + 1]) <= d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1); + d += perturb > 1; + + if (x > 0 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) neigh [ncnt++] = point (x - 1, y); + if (x < dist.w - 1 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) neigh [ncnt++] = point (x + 1, y); + if (y > 0 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) neigh [ncnt++] = point (x, y - 1); + if (y < dist.h - 1 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) neigh [ncnt++] = point (x, y + 1); if (!ncnt) return; - point &p = neigh [rmg_rndm (ncnt)]; + point p = neigh [perturb ? rmg_rndm (ncnt) : 0]; seeds.push (p); @@ -265,13 +268,15 @@ // isolation remover, works on a "distance" map // the map must be initialised with 0 == rooms, 255 = walls static void noinline -isolation_remover (layout &dist) +isolation_remover (layout &dist, unsigned int perturb = 2) { // dist contains // 0 == invisited rooms // 1 == visited rooms // 2+ shortest distance to random near room + clamp_it (perturb, 0, 2); + // phase 1, find seed int cnt = 0; int x, y; @@ -312,7 +317,7 @@ { // found new isolated area, make tunnel push_flood_fill (dist, seeds, x, y); - make_tunnel (dist, seeds, x, y, 255); + make_tunnel (dist, seeds, x, y, 254, perturb); } else { @@ -328,7 +333,7 @@ } void -layout::isolation_remover () +layout::isolation_remover (int perturb) { layout dist (w - 2, h - 2); // map without border @@ -336,7 +341,7 @@ for (int y = 1; y < h - 1; ++y) dist [x - 1][y - 1] = data [x][y] == '#' ? U8 (255) : 0; - ::isolation_remover (dist); + ::isolation_remover (dist, perturb); // now copy the tunnels over for (int x = 1; x < w - 1; ++x) @@ -347,46 +352,6 @@ ///////////////////////////////////////////////////////////////////////////// -// inspired mostly by http://www.jimrandomh.org/misc/caves.txt -void -layout::gen_cave (int subtype) -{ - switch (subtype) - { - // a rough cave - case 0: - fill_rand (rmg_rndm (85, 97)); - break; - - // corridors - case 1: - fill_rand (rmg_rndm (5, 40)); - erode_1_2 (5, 2, 10); - erode_1_2 (5, -1, 10); - erode_1_2 (5, 2, 1); - break; - - // somewhat open, roundish - case 2: - fill_rand (45); - erode_1_2 (5, 0, 5); - erode_1_2 (5, 1, 1); - break; - - // wide open, some room-like structures - case 3: - fill_rand (45); - erode_1_2 (5, 2, 4); - erode_1_2 (5, -1, 3); - break; - } - - border (); - isolation_remover (); -} - -///////////////////////////////////////////////////////////////////////////// - //+GPL /* puts doors at appropriate locations in a maze. */ @@ -394,10 +359,8 @@ layout::doorify () { int ndoors = w * h / 60; /* reasonable number of doors. */ - int doorlocs = 0; /* # of available doorlocations */ - uint16 *doorlist_x = salloc (w * h); - uint16 *doorlist_y = salloc (w * h); + fixed_stack doorloc (w * h); /* make a list of possible door locations */ for (int i = 1; i < w - 1; i++) @@ -406,34 +369,21 @@ int sindex = surround_flag (*this, i, j); if (sindex == 3 || sindex == 12) /* these are possible door sindex */ - { - doorlist_x [doorlocs] = i; - doorlist_y [doorlocs] = j; - doorlocs++; - } + doorloc.push (point (i, j)); } - while (ndoors > 0 && doorlocs > 0) + while (ndoors && doorloc.size) { - int di = rmg_rndm (doorlocs); - int i = doorlist_x [di]; - int j = doorlist_y [di]; - int sindex = surround_flag (*this, i, j); + point p = doorloc.remove (rmg_rndm (doorloc.size)); + + int sindex = surround_flag (*this, p.x, p.y); if (sindex == 3 || sindex == 12) /* these are possible door sindex */ { - data [i][j] = 'D'; - ndoors--; + data [p.x][p.y] = 'D'; + --ndoors; } - - /* reduce the size of the list */ - doorlocs--; - doorlist_x[di] = doorlist_x [doorlocs]; - doorlist_y[di] = doorlist_y [doorlocs]; } - - sfree (doorlist_x, w * h); - sfree (doorlist_y, w * h); } /* takes a map and makes it symmetric: adjusts Xsize and @@ -812,8 +762,121 @@ } } +//-GPL + ///////////////////////////////////////////////////////////////////////////// +// inspired mostly by http://www.jimrandomh.org/misc/caves.txt +void +layout::gen_cave (int subtype) +{ + switch (subtype) + { + // a rough cave + case 0: + fill_rand (rmg_rndm (85, 97)); + break; + + // corridors + case 1: + fill_rand (rmg_rndm (5, 40)); + erode_1_2 (5, 2, 10); + erode_1_2 (5, -1, 10); + erode_1_2 (5, 2, 1); + break; + + // somewhat open, some room-like structures + case 2: + fill_rand (45); + erode_1_2 (5, 2, 4); + erode_1_2 (5, -1, 3); + break; + + // wide open, roundish + case 3: + fill_rand (45); + erode_1_2 (5, 0, 5); + erode_1_2 (5, 1, 1); + break; + } + + border (); + isolation_remover (1); +} + +void +layout::gen_castle () +{ + fill ('#'); + + for (int n = w * h / 30 + 1; n--; ) + { + int rw = rmg_rndm (6, 10); + int rh = rmg_rndm (6, 10); + + if (rw > w || rh > h) + continue; + + int rx = rmg_rndm (0, w - rw); + int ry = rmg_rndm (0, h - rh); + + rect (rx, ry, rx + rw, ry + rh, '#'); + fill_rect (rx + 1, ry + 1, rx + rw - 1, ry + rh - 1, 0); + } + + border (); + isolation_remover (0); +} + +static void +gen_mixed_ (layout &maze, random_map_params *RP) +{ + int dir; + + if (maze.w < 20 && maze.h < 20 && !rmg_rndm (3)) + dir = 2; // stop recursion randomly + else + dir = maze.w > maze.h; + + if (dir == 0 && maze.w > 16) + { + int m = rmg_rndm (8, maze.w - 8); + + layout m1 (maze, 0, 0, m , maze.h); gen_mixed_ (m1, RP); + layout m2 (maze, m, 0, maze.w, maze.h); gen_mixed_ (m2, RP); + } + else if (dir == 1 && maze.h > 16) + { + int m = rmg_rndm (8, maze.h - 8); + + layout m1 (maze, 0, 0, maze.w, m ); gen_mixed_ (m1, RP); + layout m2 (maze, 0, m, maze.w, maze.h); gen_mixed_ (m2, RP); + } + else + { + RP->map_layout_style = rmg_rndm (NROFLAYOUTS - 2) + 1; + + if (RP->map_layout_style == LAYOUT_MULTIPLE) + ++RP->map_layout_style; + + maze.generate (RP); + } +} + +// recursive subdivision with random sublayouts +static void +gen_mixed (layout &maze, random_map_params *RP) +{ + random_map_params &rp = *new random_map_params (RP); + gen_mixed_ (maze, &rp); + delete &rp; + + maze.border (); + maze.isolation_remover (0); +} + +//+GPL + /* function selects the maze function and gives it whatever arguments it needs. */ void @@ -882,26 +945,47 @@ break; - default: - abort (); - } + case LAYOUT_CASTLE: + gen_castle (); - /* rotate the maze randomly */ - rotate (rmg_rndm (4)); + if (rmg_rndm (2)) + doorify (); - symmetrize (RP->symmetry_used); + break; -#if 0 - print ();//D -#endif + case LAYOUT_MULTIPLE: + gen_mixed (*this, RP); + break; - if (RP->expand2x) - expand2x (); + default: + abort (); + } } //-GPL #if 0 +static void +gen_village (layout &maze) +{ + maze.clear (); + maze.border (); + + for (int n = maze.w * maze.h / 200 + 1; n--; ) + { + int rw = rmg_rndm (6, 10); + int rh = rmg_rndm (6, 10); + + int rx = rmg_rndm (2, maze.w - rw - 2); + int ry = rmg_rndm (2, maze.h - rh - 2); + + maze.rect (rx, ry, rx + rw, ry + rh, '#'); + } + + maze.border (); + maze.isolation_remover (2); +} + static struct demo { demo () @@ -910,11 +994,11 @@ for(int i=1;i<100;i++) { - layout maze (40, 25); - maze.fill_rand (85); - maze.border (); - maze.isolation_remover (); + layout maze (40, 30); + gen_village (maze); + maze.doorify (); maze.print (); + exit(0); } exit (1);