47 changes between the files.
old versionnew version   ( changed   added   deleted)  
digger.cppdigger2.cpp

0 //0 //
1 // Digging map generator (first)1 // Digging map generator (second)
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  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 void dig_tile(Vector v);54 void dig_tile(Vector v);
55 void door_tile(Vector v);55 void door_tile(Vector v);
56 void fill_tile(Vector v);56 void fill_tile(Vector v);
57 int rand_range(int Min, int Max);57 int rand_range(int Min, int Max);
58  58  
59  59  
60 enum { TILE_UNKNOWN, TILE_FLOOR, TILE_WALL, TILE_DOOR };60 enum { TILE_UNKNOWN, TILE_FLOOR, TILE_WALL, TILE_DOOR };
61 int **grid;61 int **grid;
62 int size_x, size_y;62 int size_x, size_y;
63 const int max_tries = 5;63 const int max_tries = 5;
64  64  
65  65  
66  66 class Doorway
67  67 {
68  68 public:
69  69     Doorway(Vector l, Vector h, bool door) { location=l; heading=h; has_door=door; }
70  70     Vector location, heading;
71  71     bool has_door;
72  72 };
73  73 std::vector<Doorway> doorways;
74  74  
75  75  
76  76 void dig_loop(void)
77  77 {
78  78     Vector entrance = Vector(size_x/2, size_y-1);
79  79     doorways.push_back(Doorway(entrance, Vector(0, -1), true));
80  80     
81  81     door_tile(entrance);
82  82     fill_tile(entrance+Vector(1, 0));
83  83     fill_tile(entrance-Vector(1, 0));
84  84     
85  85     while(doorways.size() > 0)
86  86     {
87  87         int which = rand_range(0, doorways.size()-1);
88  88         Doorway door = doorways[which];
89  89         doorways.erase(doorways.begin()+which);
90  90         
91  91         if(dig_random(door.location, door.heading))
92  92         {
93  93             if(door.has_door)
94  94                 door_tile(door.location);
95  95             else if(is_wall(door.location))
96  96                 dig_tile(door.location);
97  97         }
98  98     }
99  99 }
100  100  
101 // Dig either a room or a corridor. Retry until something fits, or max_tries101 // Dig either a room or a corridor. Retry until something fits, or max_tries
102 // times total.102 // times total.
103 int dig_random(Vector pos, Vector heading)103 int dig_random(Vector pos, Vector heading)
104 {104 {
105     int success = 0;105     int success = 0;
106     int tries;106     int tries;
107     107     
108     for(tries=0; tries<max_tries; tries++)108     for(tries=0; tries<max_tries; tries++)
109     {109     {
110         switch( rand_range(0, 1) ) {110         switch( rand_range(0, 1) ) {
111             default:111             default:
112             case 0: success = dig_room (pos, heading); break;112             case 0: success = dig_room (pos, heading); break;
113             case 1: success = dig_corridor (pos, heading); break;113             case 1: success = dig_corridor (pos, heading); break;
114         }114         }
115         if(success)115         if(success)
116             return 1;116             return 1;
117     }117     }
118     return 0;118     return 0;
119 }119 }
120  120  
121 // Dig a randomly sized room with an entrance at #entrance, facing in the121 // Dig a randomly sized room with an entrance at #entrance, facing in the
122 // direction given by #heading. If it doesn't fit, return 0 without changing122 // direction given by #heading. If it doesn't fit, return 0 without changing
123 // anything. If it does fit, try to place more connected to the room as well.123 // anything. If it does fit, try to place more connected to the room as well.
124 int dig_room(Vector entrance, Vector heading)124 int dig_room(Vector entrance, Vector heading)
125 {125 {
126     Vector size;126     Vector size;
127     Vector pos, corner;127     Vector pos, corner;
128     Vector door_pos;128     Vector door_pos;
129     int entrance_offset;129     int entrance_offset;
130     130     
131     // ########131     // ########
132     // #......# ^132     // #......# ^
133     // #......# |size.y133     // #......# |size.y
134     // #......# |134     // #......# |
135     // #......# v135     // #......# v
136     // C####.##136     // C####.##
137     // <---->137     // <---->
138     // size.x138     // size.x
139     // <---->139     // <---->
140     // entrance_offset140     // entrance_offset
141     141     
142     size.x = rand_range(3, 6);142     size.x = rand_range(3, 6);
143     size.y = rand_range(3, 6);143     size.y = rand_range(3, 6);
144     entrance_offset = rand_range(1, size.x);144     entrance_offset = rand_range(1, size.x);
145     145     
146     corner = entrance + (heading.left()*entrance_offset);146     corner = entrance + (heading.left()*entrance_offset);
147     147     
148     // Check the area to see if any of it has already been dug148     // Check the area to see if any of it has already been dug
149     pos=corner;149     pos=corner;
150     for(int yi=0; yi<size.y+2; yi++) {150     for(int yi=0; yi<size.y+2; yi++) {
151         for(int xi=0; xi<size.x+2; xi++) {151         for(int xi=0; xi<size.x+2; xi++) {
152             if(!is_in_bounds_or_border(pos))152             if(!is_in_bounds_or_border(pos))
153                 return 0;153                 return 0;
154             if(!is_wall(pos) && pos!=entrance)154             if(!is_wall(pos) && pos!=entrance)
155                 return 0;155                 return 0;
156             pos += heading.right();156             pos += heading.right();
157         }157         }
158         pos -= heading.right()*(size.x+2);158         pos -= heading.right()*(size.x+2);
159         pos += heading;159         pos += heading;
160     }160     }
161     161     
162     // Fill the whole area with rock162     // Fill the whole area with rock
163     pos=corner;163     pos=corner;
164     for(int yi=0; yi<size.y+2; yi++) {164     for(int yi=0; yi<size.y+2; yi++) {
165         for(int xi=0; xi<size.x+2; xi++) {165         for(int xi=0; xi<size.x+2; xi++) {
166             fill_tile(pos);166             fill_tile(pos);
167             167             
168             pos += heading.right();168             pos += heading.right();
169         }169         }
170         pos -= heading.right()*(size.x+2);170         pos -= heading.right()*(size.x+2);
171         pos += heading;171         pos += heading;
172     }172     }
173     173     
174     // Dig out the inside174     // Dig out the inside
175     pos=corner+heading+heading.right();175     pos=corner+heading+heading.right();
176     for(int yi=0; yi<size.y; yi++) {176     for(int yi=0; yi<size.y; yi++) {
177         for(int xi=0; xi<size.x; xi++) {177         for(int xi=0; xi<size.x; xi++) {
178             dig_tile(pos);178             dig_tile(pos);
179             pos += heading.right();179             pos += heading.right();
180         }180         }
181         pos -= heading.right()*size.x;181         pos -= heading.right()*size.x;
182         pos += heading;182         pos += heading;
183     }183     }
184     184     
185     // Make the entrance a door185     // Make the entrance a door
186     door_tile(entrance);186     door_tile(entrance);
187     187     
188     // Left wall connection188     // Left wall connection
189     door_pos = corner + heading*rand_range(1, size.y);189     door_pos = corner + heading*rand_range(1, size.y);
190     if(dig_random(door_pos, heading.left()))190     doorways.push_back(Doorway(door_pos, heading.left(), true));
191         door_tile(door_pos);191  
192     // Opposite wall connection192     // Opposite wall connection
193     door_pos = corner + heading*(size.y+1) + heading.right()*rand_range(1, size.x);193     door_pos = corner + heading*(size.y+1) + heading.right()*rand_range(1, size.x);
194     if(dig_random(door_pos, heading))194     doorways.push_back(Doorway(door_pos, heading, true));
195         door_tile(door_pos);195  
196     // Right wall connection196     // Right wall connection
197     door_pos = corner + heading.right()*(size.x+1) + heading*rand_range(1, size.y);197     door_pos = corner + heading.right()*(size.x+1) + heading*rand_range(1, size.y);
198     if(dig_random(door_pos, heading.right()))198     doorways.push_back(Doorway(door_pos, heading.right(), true));
199         door_tile(door_pos);199  
200     200     
201     return 1;201     return 1;
202 }202 }
203  203  
204 int dig_corridor(Vector entrance, Vector heading)204 int dig_corridor(Vector entrance, Vector heading)
205 {205 {
206     int length = rand_range(2, 6);206     int length = rand_range(2, 6);
207     int ii;207     int ii;
208     Vector pos;208     Vector pos;
209     Vector left_pos, right_pos;209     Vector left_pos, right_pos;
210     210     
211     pos = entrance;211     pos = entrance;
212     left_pos = entrance + heading.left();212     left_pos = entrance + heading.left();
213     right_pos = entrance + heading.right();213     right_pos = entrance + heading.right();
214     214     
215     // Check that there's space for the corridor215     // Check that there's space for the corridor
216     for(ii=0; ii<length; ii++)216     for(ii=0; ii<length; ii++)
217     {217     {
218         pos += heading;218         pos += heading;
219         left_pos += heading;219         left_pos += heading;
220         right_pos += heading;220         right_pos += heading;
221         221         
222         if(!is_in_bounds(pos) || !is_wall(pos) || !is_wall(left_pos) || !is_wall(right_pos))222         if(!is_in_bounds(pos) || !is_wall(pos) || !is_wall(left_pos) || !is_wall(right_pos))
223             return 0;223             return 0;
224     }224     }
225     225     
226     // Dig the corridor226     // Dig the corridor
227     pos = entrance;227     pos = entrance;
228     left_pos = entrance + heading.left();228     left_pos = entrance + heading.left();
229     right_pos = entrance + heading.right();229     right_pos = entrance + heading.right();
230     230     
231     for(ii=0; ii<length; ii++)231     for(ii=0; ii<length; ii++)
232     {232     {
233         pos += heading;233         pos += heading;
234         left_pos += heading;234         left_pos += heading;
235         right_pos += heading;235         right_pos += heading;
236         236         
237         dig_tile(pos);237         dig_tile(pos);
238         fill_tile(left_pos);238         fill_tile(left_pos);
239         fill_tile(right_pos);239         fill_tile(right_pos);
240     }240     }
241     241     
242     // Put something at the end, or, if that fails, seal off the dead end.242     fill_tile(pos); // Seal off the end (it'll turn into a door when connected)
243     if(!dig_random(pos, heading))243     doorways.push_back(Doorway(pos, heading, false));
244         fill_tile(pos);244  
245     245     
246     return 1;246     return 1;
247 }247 }
248  248  
249  249  
250 int is_in_bounds(Vector v)250 int is_in_bounds(Vector v)
251 {251 {
252     return v.x>=1 && v.y>=1 && v.x<size_x-1 && v.y<size_y-1;252     return v.x>=1 && v.y>=1 && v.x<size_x-1 && v.y<size_y-1;
253 }253 }
254 int is_in_bounds_or_border(Vector v)254 int is_in_bounds_or_border(Vector v)
255 {255 {
256     return v.x>=0 && v.y>=0 && v.x<size_x && v.y<size_y;256     return v.x>=0 && v.y>=0 && v.x<size_x && v.y<size_y;
257 }257 }
258  258  
259 int is_known(Vector v) {259 int is_known(Vector v) {
260     return grid[v.y][v.x] != TILE_UNKNOWN;260     return grid[v.y][v.x] != TILE_UNKNOWN;
261 }261 }
262 int is_floor(Vector v) {262 int is_floor(Vector v) {
263     return grid[v.y][v.x] == TILE_FLOOR;263     return grid[v.y][v.x] == TILE_FLOOR;
264 }264 }
265 int is_wall(Vector v) {265 int is_wall(Vector v) {
266     return grid[v.y][v.x] == TILE_WALL || grid[v.y][v.x] == TILE_UNKNOWN;266     return grid[v.y][v.x] == TILE_WALL || grid[v.y][v.x] == TILE_UNKNOWN;
267 }267 }
268 void dig_tile(Vector v) {268 void dig_tile(Vector v) {
269     grid[v.y][v.x] = TILE_FLOOR;269     grid[v.y][v.x] = TILE_FLOOR;
270 }270 }
271 void door_tile(Vector v) {271 void door_tile(Vector v) {
272     grid[v.y][v.x] = TILE_DOOR;272     grid[v.y][v.x] = TILE_DOOR;
273 }273 }
274 void fill_tile(Vector v) {274 void fill_tile(Vector v) {
275     grid[v.y][v.x] = TILE_WALL;275     grid[v.y][v.x] = TILE_WALL;
276 }276 }
277  277  
278  278  
279 // Return a random number between Min and Max.279 // Return a random number between Min and Max.
280 int rand_range(int Min, int Max)280 int rand_range(int Min, int Max)
281 {281 {
282     return rand() % (Max-Min+1) + Min;282     return rand() % (Max-Min+1) + Min;
283 }283 }
284  284  
285  285  
286 void init_map(void)286 void init_map(void)
287 {287 {
288     int xi, yi;288     int xi, yi;
289     289     
290     grid = new int*[size_y];290     grid = new int*[size_y];
291     291     
292     for(yi=0; yi<size_y; yi++)292     for(yi=0; yi<size_y; yi++)
293         grid[yi] = new int[size_x];293         grid[yi] = new int[size_x];
294     294     
295     for(yi=0; yi<size_y; yi++)295     for(yi=0; yi<size_y; yi++)
296     for(xi=0; xi<size_x; xi++)296     for(xi=0; xi<size_x; xi++)
297         grid[yi][xi] = TILE_UNKNOWN;297         grid[yi][xi] = TILE_UNKNOWN;
298 }298 }
299  299  
300  300  
301 void print_map(void)301 void print_map(void)
302 {302 {
303     for(int yi=0; yi<size_y; yi++)303     for(int yi=0; yi<size_y; yi++)
304     {304     {
305         for(int xi=0; xi<size_x; xi++)305         for(int xi=0; xi<size_x; xi++)
306         {306         {
307             switch(grid[yi][xi]) {307             switch(grid[yi][xi]) {
308                 case TILE_UNKNOWN: putchar(' '); break;308                 case TILE_UNKNOWN: putchar(' '); break;
309                 case TILE_FLOOR: putchar('.'); break;309                 case TILE_FLOOR: putchar('.'); break;
310                 case TILE_WALL: putchar('#'); break;310                 case TILE_WALL: putchar('#'); break;
311                 case TILE_DOOR: putchar('+'); break;311                 case TILE_DOOR: putchar('+'); break;
312             }312             }
313         }313         }
314         putchar('\n');314         putchar('\n');
315     }315     }
316 }316 }
317  317  
318 int main(int argc, char **argv)318 int main(int argc, char **argv)
319 {319 {
320     if(argc < 3) {320     if(argc < 3) {
321         printf("Usage: %s xsize ysize\n", argv[0]);321         printf("Usage: %s xsize ysize\n", argv[0]);
322         return 1;322         return 1;
323     }323     }
324     size_x = atoi(argv[1]);324     size_x = atoi(argv[1]);
325     size_y = atoi(argv[2]);325     size_y = atoi(argv[2]);
326     326     
327     srand(time(NULL));327     srand(time(NULL));
328     init_map();328     init_map();
329     329     
330     dig_room(Vector(size_x/2, size_y-1), Vector(0, -1));330     dig_loop();
331     331     
332     print_map();332     print_map();
333     return 0;333     return 0;
334 }334 }
335  335  
336  336  

S.Rodriguez, May 2003