--- deliantra/server/random_maps/layout.C 2010/06/30 23:03:40 1.2 +++ deliantra/server/random_maps/layout.C 2010/07/01 01:22:44 1.3 @@ -23,7 +23,7 @@ #include #include -LayoutData::LayoutData (int w, int h) +Layout::Layout (int w, int h) : w(w), h(h) { int size = (sizeof (char *) + sizeof (char) * h) * w; @@ -36,7 +36,7 @@ col [x] = data + x * h; } -LayoutData::~LayoutData () +Layout::~Layout () { int size = (sizeof (char *) + sizeof (char) * h) * w; @@ -44,26 +44,26 @@ } void -LayoutData::fill (char fill) +Layout::fill (char fill) { memset (col [0], fill, w * h); } void -LayoutData::rect (int x1, int y1, int x2, int y2, char fill) +Layout::rect (int x1, int y1, int x2, int y2, char fill) { for (; x1 < x2; ++x1) memset (col [x1] + y1, fill, y2 - y1); } -void LayoutData::border (char fill) +void Layout::border (char fill) { for (int i = 0; i < w; i++) col [i][0] = col [i][h - 1] = fill; for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill; } void -LayoutData::fill_rand (int percent) +Layout::fill_rand (int percent) { percent = lerp (percent, 0, 100, 0, 256); @@ -76,9 +76,9 @@ // erode by cellular automata void -LayoutData::erode_1_2 (int c1, int c2, int repeat) +Layout::erode_1_2 (int c1, int c2, int repeat) { - LayoutData neu (w, h); + Layout neu (w, h); while (repeat--) { @@ -142,7 +142,7 @@ ///////////////////////////////////////////////////////////////////////////// void -LayoutData::print () +Layout::print () { for (int y = 0; y < h; y++) { @@ -172,143 +172,147 @@ typedef fixed_stack pointlist; static noinline void -push_flood_fill (LayoutData &maze, LayoutData &dist, pointlist &seeds, int x, int y) +push_flood_fill (Layout &dist, pointlist &seeds, int x, int y) { - if (maze [x][y]) + if (dist [x][y]) return; - while (y > 0 && !maze [x][y - 1]) + while (y > 0 && !dist [x][y - 1]) --y; int y0 = y; - while (y < maze.h && !maze [x][y]) + while (y < dist.h && !dist [x][y]) { seeds.push (point (x, y)); - maze [x][y] = 1; dist [x][y] = 1; ++y; } 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 (dist, seeds, x - 1, y); + if (x < dist.w - 1) push_flood_fill (dist, seeds, x + 1, y); } } static inline void -make_tunnel (LayoutData &maze, LayoutData &dist, pointlist &seeds, int x, int y, U8 d) +make_tunnel (Layout &dist, pointlist &seeds, int x, int y, U8 d) { for (;;) { - seeds.push (point (x, y)); - - maze [x][y] = 1; - dist [x][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 < dist.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) --y; - else if (y < maze.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) + else if (y < dist.h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) ++y; else break; d = dist [x][y]; + dist [x][y] = 1; + seeds.push (point (x, y)); } } -static void -isolation_remover (LayoutData &maze, bool dirty) +static void inline +maybe_push (Layout &dist, pointlist &seeds, int x, int y, U8 d) { - LayoutData dist (maze.w, maze.h); + char &D = dist [x][y]; - dist.fill (255); + if (U8 (D) > d) // if wall and higher distance, lower distance + D = d; + else if (D) // otherwise, if it's no room, this space is uninteresting + return; - fixed_stack seeds (maze.w * maze.h * 4); + seeds.push (point (x, y)); +} - // phase 1, find seed - 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)); +static void +isolation_remover (Layout &maze, bool dirty) +{ + Layout dist (maze.w, maze.h); - // phase 2, while we have seeds, if - // seed is empty, floodfill, else grow + // dist contains + // 0 == invisited rooms + // 1 == visited rooms + // 2+ shortest distance to random near room - while (seeds.size) - { - coroapi::cede_to_tick (); + // phase 1, initialise dist array, find seed + int cnt = 0; + int x, y; - point p = seeds.remove (rmg_rndm (seeds.size)); + for (int i = 0; i < maze.w; ++i) + for (int j = 0; j < maze.h; ++j) + { + if (maze [i][j] == '#') + dist [i][j] = U8 (255); + else + { + dist [i][j] = 0; + if (!rmg_rndm (++cnt)) + x = i, y = j; + } + } - x = p.x; - y = p.y; + if (!cnt) + return; - if (!maze [x][y]) - { - // found new isolated area, make tunnel? - if (!dirty) - push_flood_fill (maze, dist, seeds, x, y); + fixed_stack seeds (maze.w * maze.h * 5); - make_tunnel (maze, dist, seeds, x, y, 255); + // 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)); - if (dirty) - push_flood_fill (maze, dist, seeds, x, y); - } - else - { - U8 d = U8 (dist [x][y]) + 1; + // phase 2, while we have seeds, if + // seed is empty, floodfill, else grow - if (x < maze.w - 1 && U8 (dist [x + 1][y]) > d) - { - dist [x + 1][y] = d; - seeds.push (point (x + 1, y)); - } + while (seeds.size) + { + coroapi::cede_to_tick (); - if (x > 0 && U8 (dist [x - 1][y]) > d) - { - dist [x - 1][y] = d; - seeds.push (point (x - 1, y)); - } + point p = seeds.remove (rmg_rndm (seeds.size)); - if (y < maze.h - 1 && U8 (dist [x][y + 1]) > d) - { - dist [x][y + 1] = d; - seeds.push (point (x, y + 1)); - } + x = p.x; + y = p.y; - if (y > 0 && U8 (dist [x][y - 1]) > d) - { - dist [x][y - 1] = d; - seeds.push (point (x, y - 1)); - } - } - } + if (!dist [x][y]) + { + // found new isolated area, make tunnel + if (!dirty) + push_flood_fill (dist, seeds, x, y); + + make_tunnel (dist, seeds, x, y, 255); - goto success; + if (dirty) + push_flood_fill (dist, seeds, x, y); } + else + { + // nothing here, continue to expand + U8 d = U8 (dist [x][y]) + 1; -success: + if (x < dist.w - 1) maybe_push (dist, seeds, x + 1, y, d); + if (x > 0) maybe_push (dist, seeds, x - 1, y, d); + if (y < dist.h - 1) maybe_push (dist, seeds, x, y + 1, d); + if (y > 0) maybe_push (dist, seeds, x, y - 1, d); + } + } - // we mark free but visited floors as 1, undo this here + // now copy the tunnels over for (int x = 0; x < maze.w; ++x) for (int y = 0; y < maze.h; ++y) - if (maze [x][y] == 1) + if (maze [x][y] == '#' && dist [x][y] == 1) maze [x][y] = 0; } void -LayoutData::isolation_remover (bool dirty) +Layout::isolation_remover (bool dirty) { ::isolation_remover (*this, dirty); } @@ -317,7 +321,7 @@ // inspired mostly by http://www.jimrandomh.org/misc/caves.txt void -LayoutData::gen_cave (int subtype) +Layout::gen_cave (int subtype) { switch (subtype) { @@ -363,8 +367,10 @@ for(int i=1;i<10;i) { - maze->gen_cave (3); - maze->print (); + maze.fill_rand (97); + maze.border (); + maze.isolation_remover (); + maze.print (); } exit (1);