--- deliantra/server/random_maps/layout.C 2010/06/30 20:51:02 1.1 +++ deliantra/server/random_maps/layout.C 2010/06/30 23:03:40 1.2 @@ -62,16 +62,93 @@ for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill; } +void +LayoutData::fill_rand (int percent) +{ + percent = lerp (percent, 0, 100, 0, 256); + + for (int x = w - 1; --x > 0; ) + for (int y = h - 1; --y > 0; ) + col [x][y] = rmg_rndm (256) > percent ? 0 : '#'; +} + +///////////////////////////////////////////////////////////////////////////// + +// erode by cellular automata +void +LayoutData::erode_1_2 (int c1, int c2, int repeat) +{ + LayoutData neu (w, h); + + while (repeat--) + { + for (int x = 0; x < w; ++x) + { + coroapi::cede_to_tick (); + + for (int y = 0; y < h; ++y) + { + int n1 = 0, n2 = 0; + + // a 5x5 area, dx, dy, distance (1 == <= 1, 0 <= 2) + static I8 dds[][3] = { + { -2, -1, 0 }, + { -2, 0, 0 }, + { -2, 1, 0 }, + + { -1, -2, 0 }, + { -1, -1, 1 }, + { -1, 0, 1 }, + { -1, 1, 1 }, + { -1, 2, 0 }, + + { 0, -2, 0 }, + { 0, -1, 1 }, + { 0, 0, 1 }, + { 0, 1, 1 }, + { 0, 2, 0 }, + + { 1, -2, 0 }, + { 1, -1, 1 }, + { 1, 0, 1 }, + { 1, 1, 1 }, + { 1, 2, 0 }, + + { 2, -1, 0 }, + { 2, 0, 0 }, + { 2, 1, 0 }, + }; + + for (int i = array_length (dds); i--; ) + { + int nx = x + dds [i][0]; + int ny = y + dds [i][1]; + + if (!IN_RANGE_EXC (nx, 0, w) || !IN_RANGE_EXC (ny, 0, h) || !col [nx][ny]) + { + n1 += dds [i][2]; + n2++; + } + } + + neu [x][y] = n1 >= c1 || n2 <= c2 ? '#' : 0; + } + } + + swap (neu); + } +} + ///////////////////////////////////////////////////////////////////////////// void -Layout::print () +LayoutData::print () { - for (int y = 0; y < ptr->h; y++) + for (int y = 0; y < h; y++) { - for (int x = 0; x < ptr->w; x++) + for (int x = 0; x < w; x++) { - U8 c = (U8)ptr->col[x][y]; + U8 c = (U8)col [x][y]; if (!c) c = ' '; @@ -94,14 +171,8 @@ typedef fixed_stack pointlist; -static void -room (Layout &layout, int xc, int yc) -{ - layout->rect (xc - 2, yc - 2, xc + 3, yc + 3, 0); -} - static noinline void -push_flood_fill (Layout maze, Layout dist, pointlist &seeds, int x, int y) +push_flood_fill (LayoutData &maze, LayoutData &dist, pointlist &seeds, int x, int y) { if (maze [x][y]) return; @@ -111,7 +182,7 @@ int y0 = y; - while (y < maze->h && !maze [x][y]) + while (y < maze.h && !maze [x][y]) { seeds.push (point (x, y)); @@ -122,13 +193,13 @@ while (--y >= y0) { - if (x > 0) push_flood_fill (maze, dist, seeds, x - 1, y); - if (x < maze->w - 1) push_flood_fill (maze, dist, seeds, x + 1, y); + if (x > 0) push_flood_fill (maze, dist, seeds, x - 1, y); + if (x < maze.w - 1) push_flood_fill (maze, dist, seeds, x + 1, y); } } static inline void -make_tunnel (Layout maze, Layout dist, pointlist &seeds, int x, int y, U8 d) +make_tunnel (LayoutData &maze, LayoutData &dist, pointlist &seeds, int x, int y, U8 d) { for (;;) { @@ -137,13 +208,13 @@ maze [x][y] = 1; dist [x][y] = 1; - if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) + if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) --x; - else if (x < maze->w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) + else if (x < maze.w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) ++x; - else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) + else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) --y; - else if (y < maze->h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) + else if (y < maze.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) ++y; else break; @@ -153,19 +224,22 @@ } static void -isolation_remover (Layout maze, bool dirty) +isolation_remover (LayoutData &maze, bool dirty) { - Layout dist (maze->w, maze->h); + LayoutData dist (maze.w, maze.h); - dist->fill (255); + dist.fill (255); - fixed_stack seeds (maze->w * maze->h * 4); + fixed_stack seeds (maze.w * maze.h * 4); // phase 1, find seed - for (int x = 1; x < maze->w; ++x) - for (int y = 1; y < maze->h; ++y) + for (int x = 1; x < maze.w; ++x) + for (int y = 1; y < maze.h; ++y) if (!maze [x][y]) { + // found first free space - picking the first one gives + // us a slight bias for tunnels, but usually you won't + // notice that in-game seeds.push (point (x, y)); // phase 2, while we have seeds, if @@ -173,6 +247,8 @@ while (seeds.size) { + coroapi::cede_to_tick (); + point p = seeds.remove (rmg_rndm (seeds.size)); x = p.x; @@ -193,25 +269,25 @@ { U8 d = U8 (dist [x][y]) + 1; - if (x < maze->w - 1 && U8 (dist [x + 1][y]) > d) + if (x < maze.w - 1 && U8 (dist [x + 1][y]) > d) { dist [x + 1][y] = d; seeds.push (point (x + 1, y)); } - if (x > 0 && U8 (dist [x - 1][y]) > d) + if (x > 0 && U8 (dist [x - 1][y]) > d) { dist [x - 1][y] = d; seeds.push (point (x - 1, y)); } - if (y < maze->h - 1 && U8 (dist [x][y + 1]) > d) + if (y < maze.h - 1 && U8 (dist [x][y + 1]) > d) { dist [x][y + 1] = d; seeds.push (point (x, y + 1)); } - if (y > 0 && U8 (dist [x][y - 1]) > d) + if (y > 0 && U8 (dist [x][y - 1]) > d) { dist [x][y - 1] = d; seeds.push (point (x, y - 1)); @@ -223,11 +299,10 @@ } success: - dist.free (); // we mark free but visited floors as 1, undo this here - for (int x = 0; x < maze->w; ++x) - for (int y = 0; y < maze->h; ++y) + for (int x = 0; x < maze.w; ++x) + for (int y = 0; y < maze.h; ++y) if (maze [x][y] == 1) maze [x][y] = 0; } @@ -235,9 +310,47 @@ void LayoutData::isolation_remover (bool dirty) { - Layout maze; - maze.ptr = this; - ::isolation_remover (maze, dirty); + ::isolation_remover (*this, dirty); +} + +///////////////////////////////////////////////////////////////////////////// + +// inspired mostly by http://www.jimrandomh.org/misc/caves.txt +void +LayoutData::gen_cave (int subtype) +{ + switch (subtype) + { + // a rough cave + case 0: + fill_rand (rmg_rndm (80, 95)); + 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 (); } #if 0 @@ -248,31 +361,12 @@ Layout maze (40, 25); rmg_rndm.seed (time (0)); - for (int p = 80; p < 100; p += 1) { - maze->fill ('#'); - -#if 1 - for (int x = 1; x < maze->w - 1; ++x) - for (int y = 1; y < maze->h - 1; ++y) - maze [x][y] = rmg_rndm(100) < p ? '#' : 0; -#else - room (maze, 5, 5); - room (maze, 30,20); - room (maze, 10,20); - room (maze, 20,10); -#endif - - isolation_remover (maze, 1); - maze.print (); - } - -#if 0 for(int i=1;i<10;i) { - maze_gen (maze, 1); - maze.print (); + maze->gen_cave (3); + maze->print (); } -#endif + exit (1); } } demo;