| 1 |
/* |
| 2 |
* This file is part of Deliantra, the Roguelike Realtime MMORPG. |
| 3 |
* |
| 4 |
* Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team |
| 5 |
* |
| 6 |
* Deliantra is free software: you can redistribute it and/or modify it under |
| 7 |
* the terms of the Affero GNU General Public License as published by the |
| 8 |
* Free Software Foundation, either version 3 of the License, or (at your |
| 9 |
* option) any later version. |
| 10 |
* |
| 11 |
* This program is distributed in the hope that it will be useful, |
| 12 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 13 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 14 |
* GNU General Public License for more details. |
| 15 |
* |
| 16 |
* You should have received a copy of the Affero GNU General Public License |
| 17 |
* and the GNU General Public License along with this program. If not, see |
| 18 |
* <http://www.gnu.org/licenses/>. |
| 19 |
* |
| 20 |
* The authors can be reached via e-mail to <support@deliantra.net> |
| 21 |
*/ |
| 22 |
|
| 23 |
#include <global.h> |
| 24 |
#include <random_map.h> |
| 25 |
|
| 26 |
LayoutData::LayoutData (int w, int h) |
| 27 |
: w(w), h(h) |
| 28 |
{ |
| 29 |
int size = (sizeof (char *) + sizeof (char) * h) * w; |
| 30 |
|
| 31 |
col = (char **)salloc<char> (size); |
| 32 |
|
| 33 |
char *data = (char *)(col + w); |
| 34 |
|
| 35 |
for (int x = w; x--; ) |
| 36 |
col [x] = data + x * h; |
| 37 |
} |
| 38 |
|
| 39 |
LayoutData::~LayoutData () |
| 40 |
{ |
| 41 |
int size = (sizeof (char *) + sizeof (char) * h) * w; |
| 42 |
|
| 43 |
sfree ((char *)col, size); |
| 44 |
} |
| 45 |
|
| 46 |
void |
| 47 |
LayoutData::fill (char fill) |
| 48 |
{ |
| 49 |
memset (col [0], fill, w * h); |
| 50 |
} |
| 51 |
|
| 52 |
void |
| 53 |
LayoutData::rect (int x1, int y1, int x2, int y2, char fill) |
| 54 |
{ |
| 55 |
for (; x1 < x2; ++x1) |
| 56 |
memset (col [x1] + y1, fill, y2 - y1); |
| 57 |
} |
| 58 |
|
| 59 |
void LayoutData::border (char fill) |
| 60 |
{ |
| 61 |
for (int i = 0; i < w; i++) col [i][0] = col [i][h - 1] = fill; |
| 62 |
for (int j = 0; j < h; j++) col [0][j] = col [w - 1][j] = fill; |
| 63 |
} |
| 64 |
|
| 65 |
///////////////////////////////////////////////////////////////////////////// |
| 66 |
|
| 67 |
void |
| 68 |
Layout::print () |
| 69 |
{ |
| 70 |
for (int y = 0; y < ptr->h; y++) |
| 71 |
{ |
| 72 |
for (int x = 0; x < ptr->w; x++) |
| 73 |
{ |
| 74 |
U8 c = (U8)ptr->col[x][y]; |
| 75 |
|
| 76 |
if (!c) |
| 77 |
c = ' '; |
| 78 |
else if (c < 10) |
| 79 |
c += '0'; |
| 80 |
else if (c < 32) |
| 81 |
c += 'a' - 10; |
| 82 |
|
| 83 |
putc ((char)c, stdout); |
| 84 |
} |
| 85 |
|
| 86 |
putc ('\n', stdout); |
| 87 |
} |
| 88 |
|
| 89 |
putc ('\n', stdout); |
| 90 |
} |
| 91 |
|
| 92 |
///////////////////////////////////////////////////////////////////////////// |
| 93 |
// isolation remover - ensures single connected area |
| 94 |
|
| 95 |
typedef fixed_stack<point> pointlist; |
| 96 |
|
| 97 |
static void |
| 98 |
room (Layout &layout, int xc, int yc) |
| 99 |
{ |
| 100 |
layout->rect (xc - 2, yc - 2, xc + 3, yc + 3, 0); |
| 101 |
} |
| 102 |
|
| 103 |
static noinline void |
| 104 |
push_flood_fill (Layout maze, Layout dist, pointlist &seeds, int x, int y) |
| 105 |
{ |
| 106 |
if (maze [x][y]) |
| 107 |
return; |
| 108 |
|
| 109 |
while (y > 0 && !maze [x][y - 1]) |
| 110 |
--y; |
| 111 |
|
| 112 |
int y0 = y; |
| 113 |
|
| 114 |
while (y < maze->h && !maze [x][y]) |
| 115 |
{ |
| 116 |
seeds.push (point (x, y)); |
| 117 |
|
| 118 |
maze [x][y] = 1; |
| 119 |
dist [x][y] = 1; |
| 120 |
++y; |
| 121 |
} |
| 122 |
|
| 123 |
while (--y >= y0) |
| 124 |
{ |
| 125 |
if (x > 0) push_flood_fill (maze, dist, seeds, x - 1, y); |
| 126 |
if (x < maze->w - 1) push_flood_fill (maze, dist, seeds, x + 1, y); |
| 127 |
} |
| 128 |
} |
| 129 |
|
| 130 |
static inline void |
| 131 |
make_tunnel (Layout maze, Layout dist, pointlist &seeds, int x, int y, U8 d) |
| 132 |
{ |
| 133 |
for (;;) |
| 134 |
{ |
| 135 |
seeds.push (point (x, y)); |
| 136 |
|
| 137 |
maze [x][y] = 1; |
| 138 |
dist [x][y] = 1; |
| 139 |
|
| 140 |
if (x > 1 && U8 (dist [x - 1][y]) < d && dist [x - 1][y] > 1) |
| 141 |
--x; |
| 142 |
else if (x < maze->w - 2 && U8 (dist [x + 1][y]) < d && dist [x + 1][y] > 1) |
| 143 |
++x; |
| 144 |
else if (y > 1 && U8 (dist [x][y - 1]) < d && dist [x][y - 1] > 1) |
| 145 |
--y; |
| 146 |
else if (y < maze->h - 2 && U8 (dist [x][y + 1]) < d && dist [x][y + 1] > 1) |
| 147 |
++y; |
| 148 |
else |
| 149 |
break; |
| 150 |
|
| 151 |
d = dist [x][y]; |
| 152 |
} |
| 153 |
} |
| 154 |
|
| 155 |
static void |
| 156 |
isolation_remover (Layout maze, bool dirty) |
| 157 |
{ |
| 158 |
Layout dist (maze->w, maze->h); |
| 159 |
|
| 160 |
dist->fill (255); |
| 161 |
|
| 162 |
fixed_stack<point> seeds (maze->w * maze->h * 4); |
| 163 |
|
| 164 |
// phase 1, find seed |
| 165 |
for (int x = 1; x < maze->w; ++x) |
| 166 |
for (int y = 1; y < maze->h; ++y) |
| 167 |
if (!maze [x][y]) |
| 168 |
{ |
| 169 |
seeds.push (point (x, y)); |
| 170 |
|
| 171 |
// phase 2, while we have seeds, if |
| 172 |
// seed is empty, floodfill, else grow |
| 173 |
|
| 174 |
while (seeds.size) |
| 175 |
{ |
| 176 |
point p = seeds.remove (rmg_rndm (seeds.size)); |
| 177 |
|
| 178 |
x = p.x; |
| 179 |
y = p.y; |
| 180 |
|
| 181 |
if (!maze [x][y]) |
| 182 |
{ |
| 183 |
// found new isolated area, make tunnel? |
| 184 |
if (!dirty) |
| 185 |
push_flood_fill (maze, dist, seeds, x, y); |
| 186 |
|
| 187 |
make_tunnel (maze, dist, seeds, x, y, 255); |
| 188 |
|
| 189 |
if (dirty) |
| 190 |
push_flood_fill (maze, dist, seeds, x, y); |
| 191 |
} |
| 192 |
else |
| 193 |
{ |
| 194 |
U8 d = U8 (dist [x][y]) + 1; |
| 195 |
|
| 196 |
if (x < maze->w - 1 && U8 (dist [x + 1][y]) > d) |
| 197 |
{ |
| 198 |
dist [x + 1][y] = d; |
| 199 |
seeds.push (point (x + 1, y)); |
| 200 |
} |
| 201 |
|
| 202 |
if (x > 0 && U8 (dist [x - 1][y]) > d) |
| 203 |
{ |
| 204 |
dist [x - 1][y] = d; |
| 205 |
seeds.push (point (x - 1, y)); |
| 206 |
} |
| 207 |
|
| 208 |
if (y < maze->h - 1 && U8 (dist [x][y + 1]) > d) |
| 209 |
{ |
| 210 |
dist [x][y + 1] = d; |
| 211 |
seeds.push (point (x, y + 1)); |
| 212 |
} |
| 213 |
|
| 214 |
if (y > 0 && U8 (dist [x][y - 1]) > d) |
| 215 |
{ |
| 216 |
dist [x][y - 1] = d; |
| 217 |
seeds.push (point (x, y - 1)); |
| 218 |
} |
| 219 |
} |
| 220 |
} |
| 221 |
|
| 222 |
goto success; |
| 223 |
} |
| 224 |
|
| 225 |
success: |
| 226 |
dist.free (); |
| 227 |
|
| 228 |
// we mark free but visited floors as 1, undo this here |
| 229 |
for (int x = 0; x < maze->w; ++x) |
| 230 |
for (int y = 0; y < maze->h; ++y) |
| 231 |
if (maze [x][y] == 1) |
| 232 |
maze [x][y] = 0; |
| 233 |
} |
| 234 |
|
| 235 |
void |
| 236 |
LayoutData::isolation_remover (bool dirty) |
| 237 |
{ |
| 238 |
Layout maze; |
| 239 |
maze.ptr = this; |
| 240 |
::isolation_remover (maze, dirty); |
| 241 |
} |
| 242 |
|
| 243 |
#if 0 |
| 244 |
static struct demo |
| 245 |
{ |
| 246 |
demo () |
| 247 |
{ |
| 248 |
Layout maze (40, 25); |
| 249 |
rmg_rndm.seed (time (0)); |
| 250 |
|
| 251 |
for (int p = 80; p < 100; p += 1) { |
| 252 |
maze->fill ('#'); |
| 253 |
|
| 254 |
#if 1 |
| 255 |
for (int x = 1; x < maze->w - 1; ++x) |
| 256 |
for (int y = 1; y < maze->h - 1; ++y) |
| 257 |
maze [x][y] = rmg_rndm(100) < p ? '#' : 0; |
| 258 |
#else |
| 259 |
room (maze, 5, 5); |
| 260 |
room (maze, 30,20); |
| 261 |
room (maze, 10,20); |
| 262 |
room (maze, 20,10); |
| 263 |
#endif |
| 264 |
|
| 265 |
isolation_remover (maze, 1); |
| 266 |
maze.print (); |
| 267 |
} |
| 268 |
|
| 269 |
#if 0 |
| 270 |
for(int i=1;i<10;i) |
| 271 |
{ |
| 272 |
maze_gen (maze, 1); |
| 273 |
maze.print (); |
| 274 |
} |
| 275 |
#endif |
| 276 |
exit (1); |
| 277 |
} |
| 278 |
} demo; |
| 279 |
#endif |
