61 changes between the files.
old versionnew version   ( changed   added   deleted)  
digger2.cppdigger3.cpp

0 //0 //
1 // Digging map generator (second)1 // Digging map generator (third)
2 // By Jim Babcock2 // By Jim Babcock
3 //3 //
4 // This program is part of the article 'Digging Features' and may be4 // This program is part of the article 'Digging Features' and may be
5 // distributed under the same terms as that article.5 // distributed under the same terms as that article.
6 //6 //
7 // www.jimrandomh.org/rldev7 // www.jimrandomh.org/rldev
8 //8 //
9 #include <cstdio>9 #include <cstdio>
10 #include <cstdlib>10 #include <cstdlib>
11 #include <ctime>11 #include <ctime>
12 #include <cassert>12 #include <cassert>
13 #include <vector>13 #include <vector>
14 using namespace std;14 using namespace std;
15  15  
16 //16 //
17 // Some handy things about vectors:17 // Some handy things about vectors:
18 //18 //
19 // point + direction = one step away from (point) in (direction)19 // point + direction = one step away from (point) in (direction)
20 // point + direction*num = (num) steps in (direction) away from (point)20 // point + direction*num = (num) steps in (direction) away from (point)
21 // dir.right() = 90 degrees clockwise from dir21 // dir.right() = 90 degrees clockwise from dir
22 // dir.left() = 90 degrees counter-clockwise from dir22 // dir.left() = 90 degrees counter-clockwise from dir
23 //23 //
24 class Vector24 class Vector
25 {25 {
26 public:26 public:
27     int x, y;27     int x, y;
28     28     
29     inline Vector() { x=y=0; }29     inline Vector() { x=y=0; }
30     inline Vector(int x, int y) { this->x=x; this->y=y; }30     inline Vector(int x, int y) { this->x=x; this->y=y; }
31     31     
32     inline Vector operator+(const Vector &vec) { return Vector(x+vec.x, y+vec.y); }32     inline Vector operator+(const Vector &vec) { return Vector(x+vec.x, y+vec.y); }
33     inline Vector operator-(const Vector &vec) { return Vector(x-vec.x, y-vec.y); }33     inline Vector operator-(const Vector &vec) { return Vector(x-vec.x, y-vec.y); }
34     inline Vector& operator+=(const Vector &vec) { x += vec.x; y += vec.y; return *this; }34     inline Vector& operator+=(const Vector &vec) { x += vec.x; y += vec.y; return *this; }
35     inline Vector& operator-=(const Vector &vec) { x -= vec.x; y -= vec.y; return *this; }35     inline Vector& operator-=(const Vector &vec) { x -= vec.x; y -= vec.y; return *this; }
36     inline Vector operator*(int scalar) { return Vector(x*scalar, y*scalar); }36     inline Vector operator*(int scalar) { return Vector(x*scalar, y*scalar); }
37     37     
38     inline friend Vector operator*(int scalar, Vector vec) { return Vector(vec.x*scalar, vec.y*scalar); }38     inline friend Vector operator*(int scalar, Vector vec) { return Vector(vec.x*scalar, vec.y*scalar); }
39     39     
40     inline bool operator==(const Vector &vec) { return x==vec.x && y==vec.y; }40     inline bool operator==(const Vector &vec) { return x==vec.x && y==vec.y; }
41     inline bool operator!=(const Vector &vec) { return x!=vec.x || y!=vec.y; }41     inline bool operator!=(const Vector &vec) { return x!=vec.x || y!=vec.y; }
42     42     
43     inline Vector left() { return Vector(y, -x); }43     inline Vector left() { return Vector(y, -x); }
44     inline Vector right() { return Vector(-y, x); }44     inline Vector right() { return Vector(-y, x); }
45 };45 };
46 int dig_random(Vector pos, Vector heading);46 int dig_random(Vector pos, Vector heading);
47 int dig_room(Vector entrance, Vector heading);47 int dig_room(Vector entrance, Vector heading);
48 int dig_corridor(Vector entrance, Vector heading);48 int dig_corridor(Vector entrance, Vector heading);
49 int is_in_bounds(Vector v);49 int is_in_bounds(Vector v);
50 int is_in_bounds_or_border(Vector v);50 int is_in_bounds_or_border(Vector v);
51 int is_known(Vector v);51 int is_known(Vector v);
52 int is_floor(Vector v);52 int is_floor(Vector v);
53 int is_wall(Vector v);53 int is_wall(Vector v);
54  54 int is_permawall(Vector v);
55 void dig_tile(Vector v);55 void dig_tile(Vector v);
56 void door_tile(Vector v);56 void door_tile(Vector v);
57 void fill_tile(Vector v);57 void fill_tile(Vector v);
58  58 void permawall_tile(Vector v);
59 int rand_range(int Min, int Max);59 int rand_range(int Min, int Max);
60  60  
61  61  
62 enum { TILE_UNKNOWN, TILE_FLOOR, TILE_WALL, TILE_DOOR };62 enum { TILE_UNKNOWN, TILE_FLOOR, TILE_WALL, TILE_PERMAWALL, TILE_DOOR };
63 int **grid;63 int **grid;
64 int size_x, size_y;64 int size_x, size_y;
65 const int max_tries = 5;65 const int max_tries = 5;
66  66  
67  67  
68 class Doorway68 class Doorway
69 {69 {
70 public:70 public:
71     Doorway(Vector l, Vector h, bool door) { location=l; heading=h; has_door=door; }71     Doorway(Vector l, Vector h, bool door) { location=l; heading=h; has_door=door; }
72     Vector location, heading;72     Vector location, heading;
73     bool has_door;73     bool has_door;
74 };74 };
75 std::vector<Doorway> doorways;75 std::vector<Doorway> doorways;
76  76  
77  77  
78 void dig_loop(void)78 void dig_loop(void)
79 {79 {
80     Vector entrance = Vector(size_x/2, size_y-1);80     Vector entrance = Vector(size_x/2, size_y-1);
81     doorways.push_back(Doorway(entrance, Vector(0, -1), true));81     doorways.push_back(Doorway(entrance, Vector(0, -1), true));
82     82     
83     door_tile(entrance);83     door_tile(entrance);
84     fill_tile(entrance+Vector(1, 0));84     fill_tile(entrance+Vector(1, 0));
85     fill_tile(entrance-Vector(1, 0));85     fill_tile(entrance-Vector(1, 0));
86     86     
87     while(doorways.size() > 0)87     while(doorways.size() > 0)
88     {88     {
89         int which = rand_range(0, doorways.size()-1);89         int which = rand_range(0, doorways.size()-1);
90         Doorway door = doorways[which];90         Doorway door = doorways[which];
91         doorways.erase(doorways.begin()+which);91         doorways.erase(doorways.begin()+which);
92         92         
93         if(dig_random(door.location, door.heading))93         if(dig_random(door.location, door.heading))
94         {94         {
95             if(door.has_door)95             if(door.has_door)
96                 door_tile(door.location);96                 door_tile(door.location);
97             else if(is_wall(door.location))97             else if(is_wall(door.location))
98                 dig_tile(door.location);98                 dig_tile(door.location);
99         }99         }
100     }100     }
101 }101 }
102  102  
103 // Dig either a room or a corridor. Retry until something fits, or max_tries103 // Dig either a room or a corridor. Retry until something fits, or max_tries
104 // times total.104 // times total.
105 int dig_random(Vector pos, Vector heading)105 int dig_random(Vector pos, Vector heading)
106 {106 {
107     int success = 0;107     int success = 0;
108     int tries;108     int tries;
109     109     
110     for(tries=0; tries<max_tries; tries++)110     for(tries=0; tries<max_tries; tries++)
111     {111     {
112         switch( rand_range(0, 1) ) {112         switch( rand_range(0, 1) ) {
113             default:113             default:
114             case 0: success = dig_room (pos, heading); break;114             case 0: success = dig_room (pos, heading); break;
115             case 1: success = dig_corridor (pos, heading); break;115             case 1: success = dig_corridor (pos, heading); break;
116         }116         }
117         if(success)117         if(success)
118             return 1;118             return 1;
119     }119     }
120     return 0;120     return 0;
121 }121 }
122  122  
123 // Dig a randomly sized room with an entrance at #entrance, facing in the123 // Dig a randomly sized room with an entrance at #entrance, facing in the
124 // direction given by #heading. If it doesn't fit, return 0 without changing124 // direction given by #heading. If it doesn't fit, return 0 without changing
125 // anything. If it does fit, try to place more connected to the room as well.125 // anything. If it does fit, try to place more connected to the room as well.
126 int dig_room(Vector entrance, Vector heading)126 int dig_room(Vector entrance, Vector heading)
127 {127 {
128     Vector size;128     Vector size;
129     Vector pos, corner;129     Vector pos, corner;
130     Vector door_pos;130     Vector door_pos;
131     int entrance_offset;131     int entrance_offset;
132     132     
133     // ########133     // ########
134     // #......# ^134     // #......# ^
135     // #......# |size.y135     // #......# |size.y
136     // #......# |136     // #......# |
137     // #......# v137     // #......# v
138     // C####.##138     // C####.##
139     // <---->139     // <---->
140     // size.x140     // size.x
141     // <---->141     // <---->
142     // entrance_offset142     // entrance_offset
143     143     
144     size.x = rand_range(3, 6);144     size.x = rand_range(3, 6);
145     size.y = rand_range(3, 6);145     size.y = rand_range(3, 6);
146     entrance_offset = rand_range(1, size.x);146     entrance_offset = rand_range(1, size.x);
147     147     
148     corner = entrance + (heading.left()*entrance_offset);148     corner = entrance + (heading.left()*entrance_offset);
149     149     
150     // Check the area to see if any of it has already been dug150     // Check the area to see if any of it has already been dug
151     pos=corner;151     pos=corner;
152     for(int yi=0; yi<size.y+2; yi++) {152     for(int yi=0; yi<size.y+2; yi++) {
153         for(int xi=0; xi<size.x+2; xi++) {153         for(int xi=0; xi<size.x+2; xi++) {
154             if(!is_in_bounds_or_border(pos))154             if(!is_in_bounds_or_border(pos))
155                 return 0;155                 return 0;
156             if(!is_wall(pos) && pos!=entrance)156             if(!is_wall(pos) && pos!=entrance)
157                 return 0;157                 return 0;
158             pos += heading.right();158             pos += heading.right();
159         }159         }
160         pos -= heading.right()*(size.x+2);160         pos -= heading.right()*(size.x+2);
161         pos += heading;161         pos += heading;
162     }162     }
163     163     
164     // Fill the whole area with rock164     // Fill the whole area with rock
165     pos=corner;165     pos=corner;
166     for(int yi=0; yi<size.y+2; yi++) {166     for(int yi=0; yi<size.y+2; yi++) {
167         for(int xi=0; xi<size.x+2; xi++) {167         for(int xi=0; xi<size.x+2; xi++) {
168             fill_tile(pos);168             fill_tile(pos);
169             169             
170             pos += heading.right();170             pos += heading.right();
171         }171         }
172         pos -= heading.right()*(size.x+2);172         pos -= heading.right()*(size.x+2);
173         pos += heading;173         pos += heading;
174     }174     }
175     175     
176  176     // Turn the corners into permawall
177  177     permawall_tile(corner);
178  178     permawall_tile(corner + (heading.right()*(size.x+1)));
179  179     permawall_tile(corner + (heading*(size.y+1)));
180  180     permawall_tile(corner + (heading.right()*(size.x+1)) + (heading*(size.y+1)));
181  181     
182     // Dig out the inside182     // Dig out the inside
183     pos=corner+heading+heading.right();183     pos=corner+heading+heading.right();
184     for(int yi=0; yi<size.y; yi++) {184     for(int yi=0; yi<size.y; yi++) {
185         for(int xi=0; xi<size.x; xi++) {185         for(int xi=0; xi<size.x; xi++) {
186             dig_tile(pos);186             dig_tile(pos);
187             pos += heading.right();187             pos += heading.right();
188         }188         }
189         pos -= heading.right()*size.x;189         pos -= heading.right()*size.x;
190         pos += heading;190         pos += heading;
191     }191     }
192     192     
193     // Make the entrance a door193     // Make the entrance a door
194     door_tile(entrance);194     door_tile(entrance);
195     195     
196     // Left wall connection196     // Left wall connection
197     door_pos = corner + heading*rand_range(1, size.y);197     door_pos = corner + heading*rand_range(1, size.y);
198     doorways.push_back(Doorway(door_pos, heading.left(), true));198     doorways.push_back(Doorway(door_pos, heading.left(), true));
199     // Opposite wall connection199     // Opposite wall connection
200     door_pos = corner + heading*(size.y+1) + heading.right()*rand_range(1, size.x);200     door_pos = corner + heading*(size.y+1) + heading.right()*rand_range(1, size.x);
201     doorways.push_back(Doorway(door_pos, heading, true));201     doorways.push_back(Doorway(door_pos, heading, true));
202     // Right wall connection202     // Right wall connection
203     door_pos = corner + heading.right()*(size.x+1) + heading*rand_range(1, size.y);203     door_pos = corner + heading.right()*(size.x+1) + heading*rand_range(1, size.y);
204     doorways.push_back(Doorway(door_pos, heading.right(), true));204     doorways.push_back(Doorway(door_pos, heading.right(), true));
205     205     
206     return 1;206     return 1;
207 }207 }
208  208  
209 int dig_corridor(Vector entrance, Vector heading)209 int dig_corridor(Vector entrance, Vector heading)
210 {210 {
211     int length = rand_range(2, 6);211     int length = rand_range(2, 6);
212     int ii;212     int ii;
213     Vector pos;213     Vector pos;
214     Vector left_pos, right_pos;214     Vector left_pos, right_pos;
215  215     bool found_intersect = false;
216     216     
217     pos = entrance;217     pos = entrance;
218     left_pos = entrance + heading.left();218     left_pos = entrance + heading.left();
219     right_pos = entrance + heading.right();219     right_pos = entrance + heading.right();
220     220     
221     // Check that there's space for the corridor221     // Check that the corridor doesn't intersect something in a bad way
222     for(ii=0; ii<length; ii++)222     for(ii=0; ii<length; ii++)
223     {223     {
224         pos += heading;224         pos += heading;
225         left_pos += heading;225         left_pos += heading;
226         right_pos += heading;226         right_pos += heading;
227         227         
228         if(!is_in_bounds(pos) || !is_wall(pos) || !is_wall(left_pos) || !is_wall(right_pos))228         if(!is_in_bounds(pos))
229             return 0;229             return 0;
230  230         if(!is_wall(pos)) {
231  231             found_intersect = true;
232  232             length = ii;
233  233             break;
234  234         }
235  235         if( !is_wall(left_pos) || !is_wall(right_pos)
236  236          || is_permawall(pos) )
237  237             return 0;
238     }238     }
239     239     
240  240     // Drop corridors that're so short they'd have 2 consecutive doors, like
241  241     // this:
242  242     // ..##..
243  243     // ..++..
244  244     // ..##..
245  245     if(length<=1)
246  246         return 0;
247  247     
248  248     // Prune dead ends
249  249     if(!found_intersect)
250  250         return 0;
251  251     
252     // Dig the corridor252     // Dig the corridor
253     pos = entrance;253     pos = entrance;
254     left_pos = entrance + heading.left();254     left_pos = entrance + heading.left();
255     right_pos = entrance + heading.right();255     right_pos = entrance + heading.right();
256     256     
257     for(ii=0; ii<length; ii++)257     for(ii=0; ii<length; ii++)
258     {258     {
259         pos += heading;259         pos += heading;
260         left_pos += heading;260         left_pos += heading;
261         right_pos += heading;261         right_pos += heading;
262         262         
263         dig_tile(pos);263         dig_tile(pos);
264         fill_tile(left_pos);264         fill_tile(left_pos);
265         fill_tile(right_pos);265         fill_tile(right_pos);
266  266         
267  267         if(!is_in_bounds(pos+heading))
268  268             break;
269  269         if(!is_wall(pos+heading))
270  270             break;
271     }271     }
272     272     
273     fill_tile(pos); // Seal off the end (it'll turn into a door when connected)273     if(!is_in_bounds(pos+heading) || is_wall(pos+heading)) {
274     doorways.push_back(Doorway(pos, heading, false));274         // If not connected to anything
275  275         // Seal off the end (it'll turn into a door when connected)
276  276         fill_tile(pos);
277  277         doorways.push_back(Doorway(pos, heading, false));
278  278     } else {
279  279         // Put a doorway at the end
280  280         door_tile(pos);
281  281     }
282     282     
283  283 // // Put something at the end, or, if that fails, seal off the dead end.
284  284 // if(!dig_random(pos, heading))
285  285 // fill_tile(pos);
286  286     
287     return 1;287     return 1;
288 }288 }
289  289  
290  290  
291 int is_in_bounds(Vector v)291 int is_in_bounds(Vector v)
292 {292 {
293     return v.x>=1 && v.y>=1 && v.x<size_x-1 && v.y<size_y-1;293     return v.x>=1 && v.y>=1 && v.x<size_x-1 && v.y<size_y-1;
294 }294 }
295 int is_in_bounds_or_border(Vector v)295 int is_in_bounds_or_border(Vector v)
296 {296 {
297     return v.x>=0 && v.y>=0 && v.x<size_x && v.y<size_y;297     return v.x>=0 && v.y>=0 && v.x<size_x && v.y<size_y;
298 }298 }
299  299  
300 int is_known(Vector v) {300 int is_known(Vector v) {
301     return grid[v.y][v.x] != TILE_UNKNOWN;301     return grid[v.y][v.x] != TILE_UNKNOWN;
302 }302 }
303 int is_floor(Vector v) {303 int is_floor(Vector v) {
304     return grid[v.y][v.x] == TILE_FLOOR;304     return grid[v.y][v.x] == TILE_FLOOR;
305 }305 }
306 int is_wall(Vector v) {306 int is_wall(Vector v) {
307     return grid[v.y][v.x] == TILE_WALL || grid[v.y][v.x] == TILE_UNKNOWN;307     return grid[v.y][v.x] == TILE_WALL
308  308         || grid[v.y][v.x] == TILE_UNKNOWN
309  309         || grid[v.y][v.x] == TILE_PERMAWALL;
310 }310 }
311  311 int is_permawall(Vector v) {
312  312     return grid[v.y][v.x] == TILE_PERMAWALL;
313  313 }
314 void dig_tile(Vector v) {314 void dig_tile(Vector v) {
315     grid[v.y][v.x] = TILE_FLOOR;315     grid[v.y][v.x] = TILE_FLOOR;
316 }316 }
317 void door_tile(Vector v) {317 void door_tile(Vector v) {
318     grid[v.y][v.x] = TILE_DOOR;318     grid[v.y][v.x] = TILE_DOOR;
319 }319 }
320 void fill_tile(Vector v) {320 void fill_tile(Vector v) {
321     grid[v.y][v.x] = TILE_WALL;321     grid[v.y][v.x] = TILE_WALL;
322 }322 }
323  323 void permawall_tile(Vector v) {
324  324     grid[v.y][v.x] = TILE_PERMAWALL;
325  325 }
326  326  
327  327  
328 // Return a random number between Min and Max.328 // Return a random number between Min and Max.
329 int rand_range(int Min, int Max)329 int rand_range(int Min, int Max)
330 {330 {
331     return rand() % (Max-Min+1) + Min;331     return rand() % (Max-Min+1) + Min;
332 }332 }
333  333  
334  334  
335 void init_map(void)335 void init_map(void)
336 {336 {
337     int xi, yi;337     int xi, yi;
338     338     
339     grid = new int*[size_y];339     grid = new int*[size_y];
340     340     
341     for(yi=0; yi<size_y; yi++)341     for(yi=0; yi<size_y; yi++)
342         grid[yi] = new int[size_x];342         grid[yi] = new int[size_x];
343     343     
344     for(yi=0; yi<size_y; yi++)344     for(yi=0; yi<size_y; yi++)
345     for(xi=0; xi<size_x; xi++)345     for(xi=0; xi<size_x; xi++)
346         grid[yi][xi] = TILE_UNKNOWN;346         grid[yi][xi] = TILE_UNKNOWN;
347 }347 }
348  348  
349  349  
350 void print_map(void)350 void print_map(void)
351 {351 {
352     for(int yi=0; yi<size_y; yi++)352     for(int yi=0; yi<size_y; yi++)
353     {353     {
354         for(int xi=0; xi<size_x; xi++)354         for(int xi=0; xi<size_x; xi++)
355         {355         {
356             switch(grid[yi][xi]) {356             switch(grid[yi][xi]) {
357                 case TILE_UNKNOWN: putchar(' '); break;357                 case TILE_UNKNOWN: putchar(' '); break;
358                 case TILE_FLOOR: putchar('.'); break;358                 case TILE_FLOOR: putchar('.'); break;
359                 case TILE_WALL: putchar('#'); break;359                 case TILE_WALL: putchar('#'); break;
360  360                 case TILE_PERMAWALL: putchar('#'); break;
361                 case TILE_DOOR: putchar('+'); break;361                 case TILE_DOOR: putchar('+'); break;
362             }362             }
363         }363         }
364         putchar('\n');364         putchar('\n');
365     }365     }
366 }366 }
367  367  
368 int main(int argc, char **argv)368 int main(int argc, char **argv)
369 {369 {
370     if(argc < 3) {370     if(argc < 3) {
371         printf("Usage: %s xsize ysize\n", argv[0]);371         printf("Usage: %s xsize ysize\n", argv[0]);
372         return 1;372         return 1;
373     }373     }
374     size_x = atoi(argv[1]);374     size_x = atoi(argv[1]);
375     size_y = atoi(argv[2]);375     size_y = atoi(argv[2]);
376     376     
377     srand(time(NULL));377     srand(time(NULL));
378     init_map();378     init_map();
379     379     
380     dig_loop();380     dig_loop();
381     381     
382     print_map();382     print_map();
383     return 0;383     return 0;
384 }384 }
385  385  
386  386  

S.Rodriguez, May 2003