1 // Copyright (C) 2002 Vibhu Rishi
2 // Copyright (C) 2002, 2003, 2004, 2005 Ulf Lorenz
3 // Copyright (C) 2003 Michael Bartl
4 // Copyright (C) 2004 David Barnsdale
5 // Copyright (C) 2004 Andrea Paternesi
6 // Copyright (C) 2006, 2007, 2008 Ben Asselstine
7 // Copyright (C) 2008 Janek Kozicki
9 // This program is free software; you can redistribute it and/or modify
10 // it under the terms of the GNU General Public License as published by
11 // the Free Software Foundation; either version 3 of the License, or
12 // (at your option) any later version.
14 // This program is distributed in the hope that it will be useful,
15 // but WITHOUT ANY WARRANTY; without even the implied warranty of
16 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 // GNU Library General Public License for more details.
19 // You should have received a copy of the GNU General Public License
20 // along with this program; if not, write to the Free Software
21 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
24 #ifndef MAPGENERATOR_H
25 #define MAPGENERATOR_H
31 #include <sigc++/signal.h>
33 // we need the enums from these classes
37 /** This class creates a map including the buildings (cities, ruins, temples).
38 * It does NOT care about player setup and such. This is done in a second step
39 * by the CreateScenario class. The parameters for map creation are set by
40 * GamePreferencesDialog::fillData().
41 * GamePreferencesDialog does use the MapConfDialog but this is
42 * just a skeleton - GamePreferencesDialog does all the work.
44 * The data is stored in two variables:
45 * - the terrain map stores the terrain information
46 * - the building map stores the information about building placement
48 * For historical reasons *cough*, the maps are long character arrays. The
49 * definition of the single characters can be found further down; missing
50 * buildings are denoted by a space. As a normal user, you will propably never
51 * need to worry about the format anyway. It is read and "translated" by the
52 * CreateScenario class which kind of supervises the scenario creation.
54 * Map generators with different styles (e.g. islands), derived from
55 * this class are possible and will hpefully be done in the
58 * When designating sites for cities, it takes care to ensure that
59 * the first cities on any land mass will be ports on those seas
60 * that connect with other land masses and islands. In doing so, it
61 * creates two data structures that may be useful elsewhere.
73 //! Set the cityset that will be used to generate the map.
75 * the cityset tells us how many tiles a city takes up.
77 void setCityset(Cityset *cs) {cityset = cs;};
79 //! Set the number of cities
80 int setNoCities(int nocities);
82 //! Set the number of ruins
83 int setNoRuins(int noruins);
85 //! Set the number of ruins
86 int setNoSignposts(int nosignposts);
88 //! Set the number of temples
89 int setNoTemples(int notemples);
91 /** Set terrain distribution. If the sum of the percentages is less than
92 * 100, the rest is filled with grass.
94 void setPercentages(int pwater, int pforest, int pswamp,
95 int phills, int pmountains);
98 //! Get number of cities
99 int getNoCities() const {return d_nocities;}
101 //! Get number of ruins
102 int getNoRuins() const {return d_noruins;}
104 //! Get number of signposts
105 int getNoSignposts() const {return d_nosignposts;}
107 //! Get number of temples
108 int getNoTemples() const {return d_notemples;}
113 * Use this function to start off the map generation. This
114 * implementation will first distribute the terrain in random patches,
115 * normalize it and then distribute the buildings.
117 * @param width the width of the map to be generated
118 * @param height the height of the map to be generated
120 void makeMap(int width, int height, bool roads);
122 /** A debug function, prints map to std::cout, using convention mentioned
123 * at MapGenerator::makeMap
125 void printMap(int j, int i);
128 /** Get the array for the terrain map (shallow copy)
130 * @param width is set to the width of the generated map
131 * @param height is set to the height of the generated map
132 * @return char array which represents the terrain map
134 const Tile::Type* getMap(int& width, int& height) const;
136 /** Get the buildings map (shallow copy)
138 * @param width is set to the width of the generated map
139 * @param height is set to the height of the generated map
140 * @return char array which represents the building map
142 const Maptile::Building* getBuildings(int& width, int& height) const;
145 * @param fraction How far along the progress bar should be.
146 * @param status A description of what's being generated.
148 //! Emitted when the generator generates something
149 sigc::signal<void, double, std::string> progress;
152 //! Fills the terrain map with grass
155 /** Spreads terrain over the map
157 * This function randomly places a given terrain type over the map.
158 * It only "overwrites" grass tiles, so terrain is not repeatedly
161 * @param t terrain to be placed
162 * @param percent amount of tiles to be modified (percentage of the
164 * @param contin if set to true (used for water tiles), the algorithm
165 * tries to create continuous areas instead of leaving
166 * patches when it hits a dead end.
168 void makeTerrain(Tile::Type t, int percent, bool contin);
169 void makeStreamer(Tile::Type type, int percent, int width);
172 * Water is special - in real world we usually have one big ocean, and
173 * everything flowing into it with rivers. To avoid generating lots of
174 * unconnected bodies of water (those should be swamps in general,
175 * maybe a pond) we need to find biggest body of water and connect
176 * others with it, using rivers. Ponds are allowed, but not too much of them.
180 * This helper function searches whole map for enclosed ares of
181 * THIS_TILE. Each such area gets a subsequent number which is
182 * assigned to corresponding cell in box. Maximum number of areas
183 * found is how_many and equals to highest number found in box.
185 void findAreasOf(Tile::Type THIS_TILE,std::vector<std::vector<int> >& box,int& how_many);
187 * Too much randomness and rivers can create too many small islands
188 * which normally would be eroded by water along the centuries of
189 * passing time. This function eliminates those islands keeping only
190 * few of them. The randomly generated map looks more realistic in this way.
192 void verifyIslands();
195 bool findBridgePurpose(Vector<int> pos, int type, Vector<int> &src, Vector<int> &dest);
196 bool canPlaceBridge(Vector<int> pos, int type, Vector<int> &src, Vector<int> &dest);
197 void placeBridge(Vector<int> pos, int type);
200 * Once makeRivers() finds a connection path between two bodies of water
201 * it calls this function to put water on that path.
203 void connectWithWater(Vector<int> from, Vector<int> to);
205 /** Mountains are specific - they must always be surrounded by hills,
206 * othwerwise the map graphically looks bad. Besides who has ever seen
207 * a mountain without even a tiny amount of hills around?
209 * This means that a lone montains becomes surrounded by hills and
210 * is not lone anymore. See GameMap::are_those_tiles_similar().
212 void surroundMountains(int minx, int maxx, int miny, int maxy);
214 /** Paving roads and putting cities can create lone mountains.
215 * Making rivers can also create lone tiles.
216 * We need to rescue them!
218 void rescueLoneTiles(Tile::Type FIND_THIS, Tile::Type REPLACE, bool grow);
220 /** Tries to find the nearest grass tile from a given location.
222 * This function becomes e.g. neccessary if you want to create
223 * connected water areas, but the algorithm in makeTerrain() gets
226 * @param x the x position where we are to look
227 * @param y the y position where we are to look
229 * @note if the function finds a free place, it modifies x and y.
230 * @return true if search succeeded.
232 bool seekPlain(int& x,int& y);
234 /** Designates the places where the cities will be by setting characters
235 * on the building map. Creates an island if it
236 * finds only water or occupied places.
238 * @param cities the number of cities to distribute
240 void makeCities(int cities);
242 //! Returns true if position (x,y) is free for a city
243 bool canPutCity(int x, int y);
245 //! Places a city at a certain location
246 void putCity(int x, int y, int& city_count);
248 /** Designates the location of buildings across the map. Creates an island
249 * if there is only water or occupied places.
251 * @param b the type of the building
252 * @param building the number of buildings to distribute
254 void makeBuildings(Maptile::Building b, int building);
256 //! Returns true if position (x,y) is free for buildings
257 bool canPutBuilding(int x, int y);
259 /** Tries to place a city around a certain position.
261 * This function is used internally for placing ports, that
262 * is why some of the parameters may be a bit strange.
264 * @param px x coordinate of position
265 * @param py y coordinate
266 * @param city_count increased if the city is placed
268 bool tryToPlaceCity(int px, int py, int& city_count);
271 /** Normalizes the terrain
273 * With normalization, we mean that if a tile is surrounded mainly
274 * by tiles different from it's own type, then there is a chance
275 * that the tile in question is modified itself. This leads to
276 * "better" terrain distribution.
278 * @note At the moment, only water is normalized
282 bool makeRoad(int src_x, int src_y, int dest_x, int dest_y);
283 bool makeRoad(Vector<int> src, Vector<int>dest);
284 int tryRoad(int src_x, int src_y, int dest_x, int dest_y);
285 int tryRoad(Vector<int> src, Vector<int>dest);
286 bool isAccessible(int src_x, int src_y, int dest_x, int dest_y);
287 bool isAccessible(Vector<int> src, Vector<int> dest);
288 bool makeAccessible(Vector<int> src, Vector<int> dest);
289 bool makeAccessible(int src_x, int src_y, int dest_x, int dest_y);
292 /** Find all places where it's possible to place a bridge:
294 * Bridge length is 2 tiles. So we can find two options:
299 * |0|.|.| |0|=|=|.| x-----> width - i
300 * +-+-+-+ +-+-+-+-+ |
301 * |=|=|=| |.|=|=|.| |
302 * +-+-+-+ or +-+-+-+-+ \|/
303 * |=|=|=| |.|=|=|.| '
304 * +-+-+-+ +-+-+-+-+ height - j
308 * this functions returns a randommly sorted vector of all possible
309 * places for bridges in
311 * std::vector<std::pair<int , Vector<int> > >
313 * .second is (j,i) coordinates of '0' point in there.
315 * The vector is randomly sorted, so just pick the first few - as much
316 * as you need, and they will be in random (probably in not close to
317 * each other locations).
319 * The output is checked and "duplicate" brigdes (which are close to
320 * each other - because the river is straight) are removed.
322 std::vector<std::pair < int , Vector<int> > > findBridgePlaces();
323 bool placePort(int x, int y);
324 void calculateBlockedAvenue(int x, int y);
325 bool inhospitableTerrain(int x, int y, unsigned int width);
331 Tile::Type* d_terrain; // the map of the terrain
332 Maptile::Building* d_building;
335 int d_pswamp, d_pwater, d_pforest, d_phills, d_pmountains;
336 unsigned int d_nocities, d_notemples, d_noruins, d_nosignposts;