1# Overmap Generation
2
3## Overview
4
5The **overmap** is what you see in the game when you use the _view map (m)_ command.
6
7It looks something like this:
8
9```
10...>│<......................│..............P.FFFF├─FF...
11..┌─┼─┐.....................│..............FFFFF┌┘FFFF..
12..│>│^│.....................│..............FF┌─┬┘FFFFF.F
13──┘...└──┐..............>│<.│..............F┌┘F│FFFFFFF─
14.........└──┐........vvO>│v.│............FF┌┘FF│FFFFFFFF
15............└┐.......─┬──┼─>│<........┌─T──┘FFF└┐FFFFFFF
16.............│.......>│<$│S.│<.......┌┘..FFFFFFF│FFF┌─┐F
17..O.........┌┴──┐....v│gF│O.│<v......│...FFFFFF┌┘F.F│F└─
18.OOOOO.....─┘...└─────┼──┼──┼────────┤....FFFFF│FF..│FFF
19.O.O.....dddd.......^p│^>│OO│<^......└─┐FFFFFFF├────┴─FF
20.........dddd........>│tt│<>│..........│FFF..FF│FFFFF.FF
21.........dddd......┌──┘tT├──...........│FFF..F┌┘FFFFFFFF
22.........dddd......│....>│^^..H........└┐...FF│FFFFFFFFF
23..................┌┘.....│<.............└─┐FF┌┘FFFFFFFFF
24..................│......│................│FF│FFFFFFFFFF
25.................┌┘......│................│F┌┘FFFFFFFFFF
26...FFF...........│......┌┘...............┌┘.│FFFFFFFFFFF
27FFFFFF...........│.....┌┘................│FF│FFFFFFFFFFF
28FFFFFF..FFFF.....│.....B..........─┐.....│┌─┘F..FFFFFFFF
29```
30
31In the context of **overmap generation**, the **overmap** is the collection of data and features
32that define the locations in the game world at a more abstract level than the local map that the
33player directly interacts with, providing the necessary context for local map generation to occur.
34
35By example, the overmap tells the game:
36
37* where the cities are
38* where the roads are
39* where the buildings are
40* what types the buildings are
41
42but it does not tell the game:
43
44* what the actual road terrain looks like
45* what the actual building layout looks like
46* what items are in the building
47
48It can sometimes be useful to think of the overmap as the outline for the game world which will then
49be filled in as the player explores. The rest of this document is a discussion of how we can create
50that outline.
51
52### Overmap generation
53
54Generating an overmap happens in the following sequence of functions ( see generate::overmap in overmap.cpp ):
55
56	populate_connections_out_from_neighbors( north, east, south, west );
57    place_rivers( north, east, south, west );
58    place_lakes();
59    place_forests();
60    place_swamps();
61    place_ravines();
62    place_cities();
63    place_forest_trails();
64    place_roads( north, east, south, west );
65    place_specials( enabled_specials );
66    place_forest_trailheads();
67    polish_river();
68    place_mongroups();
69    place_radios();
70
71This has some consequences on overmap special spawning, as discussed in the relevant section.
72
73## Terminology and Types
74
75First we need to briefly discuss some of the data types used by the
76overmap.
77
78### overmap_terrain
79
80The fundamental unit of the overmap is the **overmap_terrain**, which defines the id, name, symbol, color
81(and more, but we'll get to that) used to represent a single location on the overmap. The overmap is 180
82overmap terrains wide, 180 overmap terrains tall, and 21 overmap terrains deep (these are the z-levels).
83
84In this example snippet of an overmap, each character corresponds one entry in the overmap which
85references a given overmap terrain:
86
87```
88.v>│......FFF│FF
89──>│<....FFFF│FF
90<.>│<...FFFFF│FF
91O.v│vv.vvv┌──┘FF
92───┼──────┘.FFFF
93F^^|^^^.^..F.FFF
94```
95
96So for example, the `F` is a forest which has a definition like this:
97
98```json
99{
100    "type": "overmap_terrain",
101    "id": "forest",
102    "name": "forest",
103    "sym": "F",
104    "color": "green"
105}
106```
107
108and the `^` is a house which has a definition like this:
109
110```json
111{
112    "type": "overmap_terrain",
113    "id": "house",
114    "name": "house",
115    "sym": "^",
116    "color": "light_green"
117}
118```
119
120It's important to note that a single overmap terrain definition is referenced for every usage of that
121overmap terrain in the overmap--if we were to change the color of our forest from `green` to `red`, every
122forest in the overmap would be red.
123
124### overmap_special / city_building
125
126The next important concept for the overmap is that of the **overmap_special** and
127**city_building**. These types, which are similar in structure, are the mechanism by which multiple
128overmap terrains can be collected together into one conceptual entity for placement on the overmap.
129If you wanted to have a sprawling mansion, a two story house, a large pond, or a secret lair placed
130under an unassuming bookstore, you would need to use an **overmap_special** or a **city_building**.
131
132These types are effectively a list of the overmap terrains that compose them, the placement of
133those overmap terrains relative to each other, and some data used to drive the placement of the
134overmap special / city building (e.g. how far from a city, should be it connected to a road, can it
135be placed in a forest/field/river, etc).
136
137### overmap_connection
138
139Speaking of roads, the concept of linear features like roads, sewers, subways, railroads, and
140forest trails are managed through a combination of overmap terrain attributes and another type
141called an **overmap_connection**.
142
143An overmap connection effectively defines the types of overmap terrain on which a given connection
144can be made, the "cost" to make that connection, and the type of terrain to be placed when making
145the connection. This, for example, is what allows us to say that:
146
147* a road may be placed on fields, forests, swamps and rivers
148* fields are preferred over forests, which are preferred over swamps, which are preferred over rivers
149* a road crossing a river will be a bridge
150
151The **overmap_connection** data will then be used to create a linear road feature connecting two points,
152applying the previously defined rules.
153
154### overmap_location
155
156We've previously mentioned defining valid overmap terrain types for the placement of overmap specials,
157city buildings, and overmap connections, but one thing to clarify is these actually leverage another
158type called an **overmap_location** rather than referencing **overmap_terrain** values directly.
159
160Simply put, an **overmap_location** is just a named collection of **overmap_terrain** values.
161
162For example, here are two simple definitions.
163
164```json
165{
166    "type": "overmap_location",
167    "id": "forest",
168    "terrains": ["forest"]
169},
170{
171    "type": "overmap_location",
172    "id": "wilderness",
173    "terrains": ["forest", "field"]
174}
175```
176
177The value of these is that they allow for a given overmap terrain to belong to several different
178locations and provide a level of indirection so that when new overmap terrains are added (or
179existing ones removed), only the relevant **overmap_location** entries need to be changed rather
180than every **overmap_connection**, **overmap_special**, and **city_building** that needs those
181groups.
182
183For example, with the addition of a new forest overmap terrain `forest_thick`, we only have to
184update these definitions as follows:
185
186```json
187{
188    "type": "overmap_location",
189    "id": "forest",
190    "terrains": ["forest", "forest_thick"]
191},
192{
193    "type": "overmap_location",
194    "id": "wilderness",
195    "terrains": ["forest", "forest_thick", "field"]
196}
197```
198
199## Overmap Terrain
200
201### Rotation
202
203If an overmap terrain can be rotated (i.e. it does not have the `NO_ROTATE` flag), then when
204the game loads the definition from JSON, it will create the rotated definitions automatically,
205suffixing the `id` defined here with `_north`, `_east`, `_south` or `_west`. This will be
206particularly relevant if the overmap terrains are used in **overmap_special** or **city_building**
207definitions, because if those are allowed to rotate, it's desirable to specify a particular
208rotation for the referenced overmap terrains (e.g. the `_north` version for all).
209
210### Fields
211
212|    Identifier     |                                           Description                                            |
213| ----------------- | ------------------------------------------------------------------------------------------------ |
214| `type`            | Must be "overmap_terrain".                                                                       |
215| `id`              | Unique id.                                                                                       |
216| `name`            | Name for the location shown in game.                                                             |
217| `sym`             | Symbol used when drawing the location, like `"F"` (or you may use an ASCII value like `70`).     |
218| `color`           | Color to draw the symbol in. See [COLOR.md](COLOR.md).                                           |
219| `see_cost`        | Affects player vision on overmap. Higher values obstruct vision more.                            |
220| `travel_cost`     | Affects pathfinding cost. Higher values are harder to travel through (reference: Forest = 10 )   |
221| `extras`          | Reference to a named `map_extras` in region_settings, defines which map extras can be applied.   |
222| `mondensity`      | Summed with values for adjacent overmap terrains to influence density of monsters spawned here.  |
223| `spawns`          | Spawns added once at mapgen. Monster group, % chance, population range (min/max).                |
224| `flags`           | See `Overmap terrains` in [JSON_FLAGS.md](JSON_FLAGS.md).                                        |
225| `mapgen`          | Specify a C++ mapgen function. Don't do this--use JSON.                                          |
226| `mapgen_straight` | Specify a C++ mapgen function for a LINEAR feature variation.                                    |
227| `mapgen_curved`   | Specify a C++ mapgen function for a LINEAR feature variation.                                    |
228| `mapgen_end`      | Specify a C++ mapgen function for a LINEAR feature variation.                                    |
229| `mapgen_tee`      | Specify a C++ mapgen function for a LINEAR feature variation.                                    |
230| `mapgen_four_way` | Specify a C++ mapgen function for a LINEAR feature variation.                                    |
231
232### Example
233
234A real `overmap_terrain` wouldn't have all these defined at the same time, but in the interest of
235an exhaustive example...
236
237```json
238{
239    "type": "overmap_terrain",
240    "id": "field",
241    "name": "field",
242    "sym": ".",
243    "color": "brown",
244    "see_cost": 2,
245    "extras": "field",
246    "mondensity": 2,
247    "spawns": { "group": "GROUP_FOREST", "population": [ 0, 1 ], "chance": 13 },
248    "flags": [ "NO_ROTATE" ],
249    "mapgen": [ { "method": "builtin", "name": "bridge" } ],
250    "mapgen_straight": [ { "method": "builtin", "name": "road_straight" } ],
251    "mapgen_curved": [ { "method": "builtin", "name": "road_curved" } ],
252    "mapgen_end": [ { "method": "builtin", "name": "road_end" } ],
253    "mapgen_tee": [ { "method": "builtin", "name": "road_tee" } ],
254    "mapgen_four_way": [ { "method": "builtin", "name": "road_four_way" } ]
255}
256```
257
258## Overmap Special
259
260An overmap special is an entity that is placed in the overmap after the city generation process has
261completed--they are the "non-city" counterpart to the **city_building** type. They commonly are
262made up of multiple overmap terrains (though not always), may have overmap connections (e.g. roads,
263sewers, subways), and have JSON-defined rules guiding their placement.
264
265### Special placement
266
267There are a finite number of sectors in which overmap specials can be placed during overmap
268generation, each being a square with side length equal to `OMSPEC_FREQ` (defined in omdata.h; at
269the time of writing `OMSPEC_FREQ`= 15 meaning each overmap has 144 sectors for placing specials).
270At the beginning of overmap generation, a list of eligable map specials is built
271(`overmap_special_batch`).  Next, a free sector is chosen where a special will be placed.  A random
272point in that sector is checked against a random rotation of a random special from the special batch
273to see if it can be placed there. If not, a new random point in the sector is checked against a new
274special, and so on until a valid spawn is rolled.
275
276### Rotation
277
278In general, it is desirable to define your overmap special as allowing rotation--this will provide
279variety in the game world and allow for more possible valid locations when attempting to place the
280overmap special. A consequence of the relationship between rotating an overmap special and rotating
281the underlying overmap terrains that make up the special is that the overmap special should reference
282a specific rotated version of the associated overmap terrain--generally, this is the `_north` rotation
283as it corresponds to the way in which the JSON for mapgen is defined.
284
285### Connections
286
287The overmap special can be connected to the road, subway or sewer networks. Specifying a connection
288point causes the appropriate connection to be automatically generated from the nearest matching terrain
289, unless `existing` is set to true.
290
291Connections with `existing` set to true are used to test the validity of an overmap special's
292placement. Unlike normal connection points these do not have to reference road/tunnel terrain types.
293They will not generate new terrain, and may even be overwritten by the overmap special's terrain.
294However, since the overmap special algorithm considers a limited number of random locations per overmap,
295the use of `existing` connections that target a rare terrain lowers the chances of the special
296spawning considerably.
297
298### Occurrences (default)
299
300Occurrences is the way to set the baseline rarity of a special. The field can behave in two ways:
301by default, it sets the minimum and maximum occurrences of the special per overmap. Currently all
302overmap specials have a minimum occurrence of 0, to keep the overmaps from being too similar to each
303other. In addition, there are no specials with a maximum occurrence of 1. This is important because
304each normal special has a very high chance of being placed at least once per overmap, owing to some
305quirks of the code (most notably, the number of specials is only slightly more than the number of slots per
306overmap, specials that failed placement don't get disqualified and can be rolled for again, and placement iterates
307until all sectors are occupied). For specials that are not common enough to warrant appearing more
308than once per overmap please use the "UNIQUE" flag.
309
310### Occurrences ( UNIQUE )
311
312When the special has the "UNIQUE" flag, instead of defining the minimum and maximum number placed
313the occurrences field defines the chance of the special to be included in any one given overmap.
314Before any placement rolls, all specials with this flag have to succeed in an x_in_y (first value, second
315value) roll to be included in the `overmap_special_batch` for the currently generated overmap;
316any special that failed this roll will never be considered for placement.  Currently all UNIQUE specials
317use [x, 100] occurrences - percentages - for ease of understanding, but this is not required.
318
319
320### Locations
321
322The overmap special has two mechanisms for specifying the valid locations (`overmap_location`) that
323it may be placed on. Each individual entry in `overmaps` may have the valid locations specified,
324which is useful if different parts of a special are allowed on different types of terrain (e.g. a
325dock that should have one part on the shore and one part in the water). If all values are the same,
326locations may instead be specified for the entire special using the top level `locations` key, The
327value for an individual entry takes precedence over the top level value, so you may define the top
328level value and then only specify it for individual entries that differ.
329
330### City distance and size
331
332During generation of a new overmap, cities and their connecting roads will be generated before
333specials are placed. Each city gets assigned a size at generation and will begin its life as a single
334intersection. The city distance field specifies the minimum and maximum distance the special can be
335placed from _this_ intersection, *not* from the edge of the city, meaning a special with a low minimum
336distance and a high or unbounded maximum city size may be placed on the outer border of a larger city.
337Both city size and city distance requirements are only checked for the "nearest" city, measured from the
338original intersection.
339
340
341### Fields
342
343|   Identifier    |                                              Description                                              |
344| --------------- | ----------------------------------------------------------------------------------------------------- |
345| `type`          | Must be "overmap_special".                                                                            |
346| `id`            | Unique id.                                                                                            |
347| `overmaps`      | List of overmap terrains and their relative `[ x, y, z ]` location within the special.                |
348| `connections`   | List of overmap connections and their relative `[ x, y, z ]` location within the special.             |
349| `locations`     | List of `overmap_location` ids that the special may be placed on.                                     |
350| `city_distance` | Min/max distance from a city that the special may be placed. Use -1 for unbounded.                    |
351| `city_sizes`    | Min/max city size for a city that the special may be placed near. Use -1 for unbounded.               |
352| `occurrences`   | Min/max number of occurrences when placing the special. If UNIQUE flag is set, becomes X of Y chance. |
353| `flags`         | See `Overmap specials` in [JSON_FLAGS.md](JSON_FLAGS.md).                                             |
354| `rotate`        | Whether the special can rotate. True if not specified.                                                |
355
356### Example
357
358```json
359[
360  {
361    "type": "overmap_special",
362    "id": "campground",
363    "overmaps": [
364      { "point": [ 0, 0, 0 ], "overmap": "campground_1a_north", "locations": [ "forest_edge" ] },
365      { "point": [ 1, 0, 0 ], "overmap": "campground_1b_north" },
366      { "point": [ 0, 1, 0 ], "overmap": "campground_2a_north" },
367      { "point": [ 1, 1, 0 ], "overmap": "campground_2b_north" }
368    ],
369    "connections": [ { "point": [ 1, -1, 0 ], "terrain": "road", "connection": "local_road", "from": [ 1, 0, 0 ] } ],
370    "locations": [ "forest" ],
371    "city_distance": [ 10, -1 ],
372    "city_sizes": [ 3, 12 ],
373    "occurrences": [ 0, 5 ],
374    "flags": [ "CLASSIC" ],
375    "rotate" : true
376  }
377]
378```
379
380### Overmaps
381
382| Identifier  |                                Description                                 |
383| ----------- | -------------------------------------------------------------------------- |
384| `point`     | `[ x, y, z]` of the overmap terrain within the special.                    |
385| `overmap`   | Id of the `overmap_terrain` to place at the location.                      |
386| `locations` | List of `overmap_location` ids that this overmap terrain may be placed on. |
387
388### Connections
389
390|  Identifier  |                                           Description                                              |
391| ------------ | -------------------------------------------------------------------------------------------------- |
392| `point`      | `[ x, y, z]` of the connection end point. Cannot overlap an overmap terrain entry for the special. |
393| `terrain`    | Will go away in favor of `connection` eventually. Use `road`, `subway`, `sewer`, etc.              |
394| `connection` | Id of the `overmap_connection` to build. Optional for now, but you should specify it explicitly.   |
395| `from`       | Optional point `[ x, y, z]` within the special to treat as the origin of the connection.           |
396| `existing`   | Boolean, default false. If the special requires a preexisting terrain to spawn.						|
397
398## City Building
399
400A city building is an entity that is placed in the overmap during the city generation process--they
401are the "city" counterpart to the **overmap_special** type. The definition for a city building is a subset
402of that for an overmap special, and consequently will not be repeated in detail here.
403
404### Mandatory Overmap Specials / Region Settings
405
406City buildings are not subject to the same quantity limitations as overmap specials, and in fact
407the occurrences attribute does not apply at all. Instead, the placement of city buildings is driven
408by the frequency assigned to the city building within the `region_settings`. Consult
409[REGION_SETTINGS.md](REGION_SETTINGS.md) for more details.
410
411### Fields
412
413| Identifier  |                                   Description                                    |
414| ----------- | -------------------------------------------------------------------------------- |
415| `type`      | Must be "city_building".                                                         |
416| `id`        | Unique id.                                                                       |
417| `overmaps`  | As in `overmap_special`, with one caveat: all point x and y values must be >= 0. |
418| `locations` | As in `overmap_special`.                                                         |
419| `flags`     | As in `overmap_special`.                                                         |
420| `rotate`    | As in `overmap_special`.                                                         |
421
422### Example
423
424```json
425[
426  {
427    "type": "city_building",
428    "id": "zoo",
429    "locations": [ "land" ],
430    "overmaps": [
431      { "point": [ 0, 0, 0 ], "overmap": "zoo_0_0_north" },
432      { "point": [ 1, 0, 0 ], "overmap": "zoo_1_0_north" },
433      { "point": [ 2, 0, 0 ], "overmap": "zoo_2_0_north" },
434      { "point": [ 0, 1, 0 ], "overmap": "zoo_0_1_north" },
435      { "point": [ 1, 1, 0 ], "overmap": "zoo_1_1_north" },
436      { "point": [ 2, 1, 0 ], "overmap": "zoo_2_1_north" },
437      { "point": [ 0, 2, 0 ], "overmap": "zoo_0_2_north" },
438      { "point": [ 1, 2, 0 ], "overmap": "zoo_1_2_north" },
439      { "point": [ 2, 2, 0 ], "overmap": "zoo_2_2_north" }
440    ],
441    "flags": [ "CLASSIC" ],
442    "rotate" : true
443  }
444]
445```
446
447## Overmap Connection
448
449### Fields
450
451| Identifier |                                           Description                                           |
452| ---------- | ----------------------------------------------------------------------------------------------- |
453| `type`     | Must be "overmap_connection".                                                                   |
454| `id`       | Unique id.                                                                                      |
455| `subtypes` | List of entries used to determine valid locations, terrain cost, and resulting overmap terrain. |
456
457
458### Example
459
460```json
461[
462  {
463    "type": "overmap_connection",
464    "id": "local_road",
465    "subtypes": [
466      { "terrain": "road", "locations": [ "field", "road" ] },
467      { "terrain": "road", "locations": [ "forest_without_trail" ], "basic_cost": 20 },
468      { "terrain": "road", "locations": [ "forest_trail" ], "basic_cost": 25 },
469      { "terrain": "road", "locations": [ "swamp" ], "basic_cost": 40 },
470      { "terrain": "road_nesw_manhole", "locations": [  ] },
471      { "terrain": "bridge", "locations": [ "water" ], "basic_cost": 120 }
472    ]
473  },
474  {
475    "type": "overmap_connection",
476    "id": "subway_tunnel",
477    "subtypes": [ { "terrain": "subway", "locations": [ "subterranean_subway" ], "flags": [ "ORTHOGONAL" ] } ]
478  }
479]
480```
481
482### Subtypes
483
484|  Identifier  |                                                Description                                                 |
485| ------------ | ---------------------------------------------------------------------------------------------------------- |
486| `terrain`    | `overmap_terrain` to be placed when the placement location matches `locations`.                            |
487| `locations`  | List of `overmap_location` that this subtype applies to. Can be empty; signifies `terrain` is valid as is. |
488| `basic_cost` | Cost of this subtype when pathfinding a route. Default 0.                                                  |
489| `flags`      | See `Overmap connections` in [JSON_FLAGS.md](JSON_FLAGS.md).                                               |
490
491## Overmap Location
492
493### Fields
494
495| Identifier |                               Description                               |
496| ---------- | ----------------------------------------------------------------------- |
497| `type`     | Must be "overmap_location".                                             |
498| `id`       | Unique id.                                                              |
499| `terrains` | List of `overmap_terrain` that can be considered part of this location. |
500
501
502### Example
503
504```json
505[
506  {
507    "type": "overmap_location",
508    "id": "wilderness",
509    "terrains": [ "forest", "forest_thick", "field", "forest_trail" ]
510  }
511]
512
513```
514