HOG2
MapGenerators.cpp
Go to the documentation of this file.
1 //
2 // MapGenerator.cpp
3 // hog2 glut
4 //
5 // Created by Nathan Sturtevant on 2/5/14.
6 // Copyright (c) 2014 University of Denver. All rights reserved.
7 //
8 
9 #include "MapGenerators.h"
10 #include <vector>
11 #include <algorithm>
12 #include <random>
13 
20 void MakePseudoMaze(Map *map, int pathSize)
21 {
22  int width = map->GetMapWidth();
23  int height = map->GetMapHeight();
24  map->SetRectHeight(0, 0, width-1, height-1, 0, kGround);
25  int pathWidth = 1;
26  for (int t = 0; (pathSize>>t); t++)
27  pathWidth = t+1;
28  for (int i = 0; i < 6*width*height; i++)
29  {
30  long x = (random()%width)&(~pathSize); // only path on even tiles
31  long y = (random()%height)&(~pathSize);
32 
33  if (map->GetHeight(x, y) <= 1)
34  {
35  switch(random()%4)
36  {
37  case 0: // NORTH
38  if ((x >= 2*pathWidth) && (map->GetHeight(x-2*pathWidth, y)+map->GetHeight(x, y) < 2))
39  {
40  for (int t = 0; t < pathWidth; t++)
41  {
42  map->SetHeight(x-2, y+t, map->GetHeight(x-2, y)+1);
43  map->SetHeight(x-1, y+t, map->GetHeight(x-1, y)+1);
44  map->SetHeight(x, y+t, map->GetHeight(x, y)+1);
45  }
46  }
47  break;
48  case 1: // SOUTH
49  if ((x < width-2*pathWidth) && (map->GetHeight(x+2*pathWidth, y)+map->GetHeight(x, y) < 2))
50  {
51  for (int t = 0; t < pathWidth; t++)
52  {
53  map->SetHeight(x+2, y+t, map->GetHeight(x+2, y)+1);
54  map->SetHeight(x+1, y+t, map->GetHeight(x+1, y)+1);
55  map->SetHeight(x, y+t, map->GetHeight(x, y)+1);
56  }
57  }
58  break;
59  case 2: // WEST
60  if ((y >= 2*pathWidth) && (map->GetHeight(x, y-2*pathWidth)+map->GetHeight(x, y) < 2))
61  {
62  for (int t = 0; t < pathWidth; t++)
63  {
64  map->SetHeight(x+t, y-2, map->GetHeight(x, y-2)+1);
65  map->SetHeight(x+t, y-1, map->GetHeight(x, y-1)+1);
66  map->SetHeight(x+t, y, map->GetHeight(x, y)+1);
67  }
68  }
69  break;
70  case 3: // EAST
71  if ((y < height-2*pathWidth) && (map->GetHeight(x, y+2*pathWidth)+map->GetHeight(x, y) < 2))
72  {
73  for (int t = 0; t < pathWidth; t++)
74  {
75  map->SetHeight(x+t, y+2, map->GetHeight(x, y+2)+1);
76  map->SetHeight(x+t, y+1, map->GetHeight(x, y+1)+1);
77  map->SetHeight(x+t, y, map->GetHeight(x, y)+1);
78  }
79  }
80  break;
81  }
82  }
83  }
84  for (int x = 0; x < width; x++)
85  for (int y = 0; y < height; y++)
86  if (map->GetHeight(x, y) > 0)
87  {
88  map->SetHeight(x, y, 0);
89  map->SetTerrainType(x, y, kOutOfBounds);
90  }
91 }
92 
96 void MakeMaze(Map *map, int corridorWidth, int startx, int starty)
97 {
98  int width = map->GetMapWidth();
99  int height = map->GetMapHeight();
100  int boxSize = corridorWidth+1;
101  if (startx == -1)
102  startx = width/(2*boxSize);
103  else
104  startx = startx-startx%boxSize;
105  if (starty == -1)
106  starty = height/(2*boxSize);
107  else
108  starty = starty-starty%boxSize;
109  // fill the whole map empty
110  map->SetRectHeight(0, 0, width-1, height-1, 0, kGround);
111  // block all the walls
112  for (int x = 0; x < width; x+=boxSize)
113  map->SetRectHeight(x, 0, x, height-1, 0, kOutOfBounds);
114  for (int y = 0; y < height; y+=boxSize)
115  map->SetRectHeight(0, y, width-1, y, 0, kOutOfBounds);
116  // mark univisited states
117  for (int x = 0; x < width; x+=boxSize)
118  for (int y = 0; y < height; y += boxSize)
119  map->SetTerrainType(x+1, y+1, kOutOfBounds);
120  std::vector<int> x;
121  std::vector<int> y;
122 
123  x.push_back(startx);
124  y.push_back(starty);
125  // x.push_back(0);
126  // y.push_back(0);
127  // map->SetHeight(0, 0, 1);
128  map->SetTerrainType(x.back()*boxSize+1, y.back()*boxSize+1, kGround);
129 
130  while (x.size() > 0)
131  {
132  bool lastRandom = false;
133  // map->Print();
134  int val;
135 
136  if (lastRandom || (1 != random()%10))
137  {
138  val = x.size()-1;
139 // if (1 == random()%30)
140 // lastRandom = false;
141  }
142  else {
143  // bias towards end of array
144  val = ((random()%(3*x.size()/2))+x.size()/2)%x.size();
145 // lastRandom = true;
146  }
147 
148  //printf("Trying to extend (%d, %d)\n", x[val], y[val]);
149  // raise up a corridor and open paths
150  switch (random()%4)
151  {
152  case 0: // NORTH
153  {
154  if ((y[val] > 0) && (map->GetTerrainType(x[val]*boxSize+1, (y[val]-1)*boxSize+1) == kOutOfBounds))
155  {
156  for (int t = 0; t < boxSize-1; t++)
157  {
158  map->SetTerrainType(x[val]*boxSize+1+t, y[val]*boxSize, kGround);
159  }
160  x.push_back(x[val]);
161  y.push_back(y[val]-1);
162  // mark cell as unblocked
163  map->SetTerrainType(x.back()*boxSize+1, y.back()*boxSize+1, kGround);
164  //printf("Extended NORTH to (%d, %d) [size %d]\n", x.back(), y.back(), x.size());
165  break;
166  }
167  }
168  case 1: // SOUTH
169  {
170  if ((y[val] < (height+boxSize-1)/boxSize) && (map->GetTerrainType(x[val]*boxSize+1, (y[val]+1)*boxSize+1) == kOutOfBounds))
171  {
172  for (int t = 0; t < boxSize-1; t++)
173  {
174  map->SetTerrainType(x[val]*boxSize+1+t, (y[val]+1)*boxSize, kGround);
175  }
176  x.push_back(x[val]);
177  y.push_back(y[val]+1);
178  // mark cell as unblocked
179  map->SetTerrainType(x.back()*boxSize+1, y.back()*boxSize+1, kGround);
180  //printf("Extended SOUTH to (%d, %d) [size %d]\n", x.back(), y.back(), x.size());
181  break;
182  }
183  }
184  case 2: // EAST
185  {
186  if (((x[val]+1)*boxSize+1 < width) && (map->GetTerrainType((x[val]+1)*boxSize+1, y[val]*boxSize+1) == kOutOfBounds))
187  {
188  for (int t = 0; t < boxSize-1; t++)
189  {
190  map->SetTerrainType((x[val]+1)*boxSize, y[val]*boxSize+1+t, kGround);
191  }
192  x.push_back(x[val]+1);
193  y.push_back(y[val]);
194  // mark cell as unblocked
195  map->SetTerrainType(x.back()*boxSize+1, y.back()*boxSize+1, kGround);
196  //printf("Extended EAST to (%d, %d) [size %d]\n", x.back(), y.back(), x.size());
197  break;
198  }
199  }
200  case 3: // WEST
201  {
202  if ((x[val] > 0) && (map->GetTerrainType((x[val]-1)*boxSize+1, y[val]*boxSize+1) == kOutOfBounds))
203  {
204  for (int t = 0; t < boxSize-1; t++)
205  {
206  map->SetTerrainType(x[val]*boxSize, y[val]*boxSize+1+t, kGround);
207  }
208  x.push_back(x[val]-1);
209  y.push_back(y[val]);
210  // mark cell as unblocked
211  map->SetTerrainType(x.back()*boxSize+1, y.back()*boxSize+1, kGround);
212  //printf("Extended WEST to (%d, %d) [size %d]\n", x.back(), y.back(), x.size());
213  }
214  break;
215  }
216  }
217 
218  // check to see if node is blocked on all sides
219  if (((x[val] == 0) || map->GetTerrainType((x[val]-1)*boxSize+1, y[val]*boxSize+1) == kGround) && // blocked left
220  (((x[val]+1)*boxSize+1 >= width) || map->GetTerrainType((x[val]+1)*boxSize+1, y[val]*boxSize+1) == kGround) && // blocked right
221  ((y[val] == 0) || map->GetTerrainType(x[val]*boxSize+1, (y[val]-1)*boxSize+1) == kGround) && // blocked up
222  (((y[val]+1)*boxSize+1 >= height) || map->GetTerrainType(x[val]*boxSize+1, (y[val]+1)*boxSize+1) == kGround)) // blocked down
223  {
224  // printf("(%d, %d) now blocked: %d left\n", x[val], y[val], x.size()-1);
225  x[val] = x.back();
226  y[val] = y.back();
227  x.pop_back();
228  y.pop_back();
229  }
230  }
231 }
232 
233 void BuildRandomRoomMap(Map *map, int roomSize, int openingProbability)
234 {
235  int width = map->GetMapWidth();
236  int height = map->GetMapHeight();
237 
238  map->SetTerrainType(0, 0, width-1, height-1, kGround);
239  for (int x = 0; x < height; x += roomSize)
240  {
241  // draw a horizontal line
242  map->SetTerrainType(0, x, width-1, x, kOutOfBounds);
243  // then punch a bunch of holes in it
244  for (int y = 0; y < width; y += roomSize)
245  {
246  if ((random()%100) < openingProbability) // chance of creating hole
247  {
248  int val = roomSize/8;
249  if (val == 0)
250  val = 1;
251  for (int z = 0; z < val; z++)
252  {
253  map->SetTerrainType(y+1+random()%(roomSize-1), x, kGround);
254  }
255  }
256  }
257  }
258  for (int x = 0; x < width; x += roomSize)
259  {
260  // draw a vertical line
261  map->SetTerrainType(x, 0, x, height-1, kOutOfBounds);
262  // then punch a bunch of holes in it
263  for (int y = 0; y < height; y += roomSize)
264  {
265  if ((random()%100) < openingProbability) // chance of creating hole
266  {
267  int val = roomSize/8;
268  if (val == 0)
269  val = 1;
270  for (int z = 0; z < val; z++)
271  {
272  map->SetTerrainType(x, y+1+random()%(roomSize-1), kGround);
273  }
274  }
275  }
276  }
277 }
278 
279 void MakeRandomMap(Map *map, int obstacles)
280 {
281  int total = map->GetMapWidth()*map->GetMapHeight()*obstacles/100;
282  for (int x = 0; x < total; x++)
283  {
284  int xloc, yloc;
285  while (1)
286  {
287  xloc = random()%map->GetMapWidth();
288  yloc = random()%map->GetMapHeight();
289  if (map->GetTerrainType(xloc, yloc) == kGround)
290  break;
291  }
292  map->SetTerrainType(xloc, yloc, kOutOfBounds);
293  }
294 }
295 
296 struct loc { int x; int y; };
297 
298 void StraightDir(Map *m, loc l, std::vector<loc> &dirs)
299 {
300  dirs.resize(0);
301  if ((m->GetTerrainType(l.x+1, l.y) == kGround) && (m->GetTerrainType(l.x-2, l.y) == kTrees))
302  dirs.push_back({l.x-2, l.y});
303  if ((m->GetTerrainType(l.x-1, l.y) == kGround) && (m->GetTerrainType(l.x+2, l.y) == kTrees))
304  dirs.push_back({l.x+2, l.y});
305  if ((m->GetTerrainType(l.x, l.y+1) == kGround) && (m->GetTerrainType(l.x, l.y-2) == kTrees))
306  dirs.push_back({l.x, l.y-2});
307  if ((m->GetTerrainType(l.x, l.y-1) == kGround) && (m->GetTerrainType(l.x, l.y+2) == kTrees))
308  dirs.push_back({l.x, l.y+2});
309 
310  if (dirs.size() != 1)
311  dirs.resize(0);
312 }
313 
314 void PossibileDirs(Map *m, loc l, std::vector<loc> &dirs)
315 {
316  dirs.resize(0);
317  if ((m->GetTerrainType(l.x+1, l.y) == kTrees) && (m->GetTerrainType(l.x+2, l.y) == kTrees))
318  dirs.push_back({l.x+2, l.y});
319  if ((m->GetTerrainType(l.x-1, l.y) == kTrees) && (m->GetTerrainType(l.x-2, l.y) == kTrees))
320  dirs.push_back({l.x-2, l.y});
321  if ((m->GetTerrainType(l.x, l.y+1) == kTrees) && (m->GetTerrainType(l.x, l.y+2) == kTrees))
322  dirs.push_back({l.x, l.y+2});
323  if ((m->GetTerrainType(l.x, l.y-1) == kTrees) && (m->GetTerrainType(l.x, l.y-2) == kTrees))
324  dirs.push_back({l.x, l.y-2});
325 }
326 
327 void Burrow(Map *m, loc l1, loc l2)
328 {
329  m->SetTerrainType(l1.x, l1.y, kGround);
330  m->SetTerrainType(l2.x, l2.y, kGround);
331  m->SetTerrainType((l1.x+l2.x)/2, (l1.y+l2.y)/2, kGround);
332 }
333 void MakeMaze(Map *m, float straightPercent, float branchPercent)
334 {
335  assert(branchPercent >= 0 && branchPercent <= 1 && straightPercent >= 0 && straightPercent <= 1);
336  for (int y = 0; y < m->GetMapHeight(); y++)
337  for (int x = 0; x < m->GetMapWidth(); x++)
338  m->SetTerrainType(x, y, kTrees);
339  std::vector<loc> places;
340  int startx = ((int)random()%m->GetMapWidth())|1;
341  int starty = ((int)random()%m->GetMapHeight())|1;
342  places.push_back({startx, starty});
343 
344  std::vector<loc> straight;
345  std::vector<loc> all;
346  while (places.size() > 0)
347  {
348  // Get random location from eligible locations
349  int which = (int)random()%places.size();
350  //if (74 > random()%100)
351  which = places.size()-1; // continue last direction
352 
353  loc currLoc = places[which];
354  places.erase(places.begin()+which);
355 
356  StraightDir(m, currLoc, straight);
357  PossibileDirs(m, currLoc, all);
358  // with straightPercent, continue straight when possible
359  if (straight.size() > 0 && (random()%10000) < 10000*straightPercent)
360  {
361  Burrow(m, currLoc, straight[0]);
362  places.push_back(straight[0]);
363  }
364  else {
365  // with probabiliy branchPercent, go in 2 directions
366  if ((random()%10000) < 10000*branchPercent)
367  {
368  while (all.size() > 2)
369  all.erase(all.begin()+random()%all.size());
370  }
371  else {
372  while (all.size() > 1)
373  all.erase(all.begin()+random()%all.size());
374  }
375  for (loc next : all)
376  {
377  Burrow(m, currLoc, next);
378  places.push_back(next);
379  }
380  std::random_device rd;
381  std::mt19937 g(rd());
382  // std::random_shuffle ( places.begin(), places.end() );
383  std::shuffle(places.begin(), places.end(), g);
384  }
385  }
386 }
387 
388 Map *MakeWarehouseMap(int columns, int rows, int corridor, int shelfWidth, int shelfHeight, int leftMargin, int rightMargin)
389 {
390  int mapWidth = leftMargin+rightMargin+columns*shelfWidth+(columns-1)*corridor+2;
391  int mapHeight = rows*shelfHeight+(rows+1)*corridor+2;
392  Map *map = new Map(mapWidth, mapHeight);
393  // put a 1-width border on the whole map
394  map->SetTerrainType(0, 0, 0, mapHeight-1, kTrees);
395  map->SetTerrainType(mapWidth-1, 0, mapWidth-1, mapHeight-1, kTrees);
396  map->SetTerrainType(0, mapHeight-1, mapWidth-1, mapHeight-1, kTrees);
397  map->SetTerrainType(0, 0, mapWidth-1, 0, kTrees);
398 
399  for (int x = 1+leftMargin; x+shelfWidth+rightMargin < mapWidth; x += shelfWidth+corridor)
400  {
401  for (int y = 1+corridor; y+shelfHeight+corridor < mapHeight; y += shelfHeight+corridor)
402  {
403  map->SetRectHeight(x, y, x+shelfWidth-1, y+shelfHeight-1, 0, kTrees);
404  }
405  }
406  return map;
407 }
loc::x
int x
Definition: MapGenerators.cpp:296
PossibileDirs
void PossibileDirs(Map *m, loc l, std::vector< loc > &dirs)
Definition: MapGenerators.cpp:314
MakeWarehouseMap
Map * MakeWarehouseMap(int columns, int rows, int corridor, int shelfWidth, int shelfHeight, int leftMargin, int rightMargin)
Definition: MapGenerators.cpp:388
loc::y
int y
Definition: MapGenerators.cpp:296
kTrees
@ kTrees
Definition: Map.h:59
kOutOfBounds
@ kOutOfBounds
Definition: Map.h:52
Map::SetRectHeight
void SetRectHeight(long x1, long y1, long x2, long y2, long h, tTerrain type=kGround)
Set the height and terrain of a set of tiles.
Definition: Map.cpp:1578
width
int width
Definition: SFML_HOG.cpp:54
StraightDir
void StraightDir(Map *m, loc l, std::vector< loc > &dirs)
Definition: MapGenerators.cpp:298
kGround
@ kGround
Definition: Map.h:55
loc
Definition: MapGenerators.cpp:296
Map::GetMapWidth
long GetMapWidth() const
return the width of the map
Definition: Map.h:163
BuildRandomRoomMap
void BuildRandomRoomMap(Map *map, int roomSize, int openingProbability)
Definition: MapGenerators.cpp:233
Map::GetTerrainType
long GetTerrainType(long x, long y, tSplitSide split=kWholeTile) const
Get the terrain type of the (split) tile at x, y.
Definition: Map.cpp:1028
height
int height
Definition: SFML_HOG.cpp:54
Map::SetHeight
void SetHeight(long x, long y, long height, tSplitSide split=kWholeTile)
Set the (flat) height of the tile at x, y.
Definition: Map.cpp:1173
Burrow
void Burrow(Map *m, loc l1, loc l2)
Definition: MapGenerators.cpp:327
Map::GetHeight
long GetHeight(long x, long y, tSplitSide split=kWholeTile)
Get the (flat) height of the tile at x, y.
Definition: Map.cpp:1144
MapGenerators.h
MakeMaze
void MakeMaze(Map *map, int corridorWidth, int startx, int starty)
MakeMaze(map)
Definition: MapGenerators.cpp:96
Map::GetMapHeight
long GetMapHeight() const
return the height of the map
Definition: Map.h:165
Map::SetTerrainType
void SetTerrainType(int32_t x1, int32_t y1, int32_t x2, int32_t y2, tTerrain t)
Map::SetTerrainType()
Definition: Map.cpp:1049
MakePseudoMaze
void MakePseudoMaze(Map *map, int pathSize)
MakeMaze(map, pathsize)
Definition: MapGenerators.cpp:20
MakeRandomMap
void MakeRandomMap(Map *map, int obstacles)
Definition: MapGenerators.cpp:279
Map
A tile-based representation of the world.
Definition: Map.h:142
Generated by   doxygen 1.8.17