# `mapgen_rivers_c`
This aims to be a C++ implementation of the pre-generation part of [`mapgen_rivers`](https://github.com/Gael-de-Sailly/mapgen_rivers).

In its current state, it only includes the river routing algorithm, based on Cordonnier et al., 2019 [1]. The algorithm finds local depressions inside the elevation model, and links them using the Planar Borůvka's (or Mareš's) algorithm [2]. Flow accumulation is then performed using another new algorithm [3].

It has been ported to C++ for performance reasons, because the original Python implementation was slow (on my computer 85s for a 1000x1000 map) and had log-linear complexity. This implementation is about 200 times faster for a 1000x1000 map (0.4s) and its linear average complexity has been verified [1].

# Usage
## Required Python libraries
Currently the C++ part is not able to generate the input map, or view it. For this you need Python 3 with the following libraries:
- `numpy`
- `noise`

Example with `pip`:
```
python3 -m pip install numpy noise
```
(or remove the `3` if your default Python installation is Python 3)

## C++ Compliation
Compile `main.cpp`, `random.cpp` and `rivermapper.cpp`. Example using GCC:
```
g++ main.cpp random.cpp rivermapper.cpp -o rivermapper.out
```

## Quick test
Run `genmap.py` to generate the input map:
```
./genmap.py
```

You can view it:
```
./viewmap.py
```

Run the bin file you have generated:
```
./rivermapper.out
```

It creates files `dem_new`, `dirs`, `rivers` and `lakes`, and prints calculation times on the terminal.

View them:
```
./viewmap.py dirs
./viewmap.py rivers log
./viewmap.py lakes
```

## Parameters
### `genmap.py`
Syntax: `./genmap.py [size [filename]]`
1. `size`: size of the map (by default `400`)
2. `filename`: name of the file to write into (by default `dem`)

Example:
```
./genmap.py 1000 dem_large
```
### `viewmap.py`
Syntax: `./viewmap.py [filename [data_type] [log]]`
1. `filename`: name of the file to read from (by default `dem`)
2. `data_type`: numerical type of the data, in NumPy format, use `u1` for a flow direction map and `f8` for others. If omitted, automatically determined from file name if standard, or set to `f8`.
3. `log`: whether or not to plot in logarithmic color scale (good for river maps).

Example:
```
./viewmap.py rivers_large f8 log
```

### `rivermapper.out` (or the bin file generated by compilation)
Syntax: `./rivermapper.out [dem_file [dem_new =_file [dirs_file [rivers_file [lakes_file]]]]]`
1. `dem_file`: input file to read from (by default `dem`)
2. `dem_new_file`: output file for new elevation (by default `dem_new`)
2. `dirs_file`: output file for flow directions (by default `dirs`)
3. `rivers_file`: output file for rivers flux (by default `rivers`)
4. `lakes_file`: output file for lakes elevation (by default `lakes`)

Example:
```
./rivermapper.out dem_large dem_new_large dirs_large rivers_large lakes_large
```

# References

[1] Cordonnier, G., Bovy, B., and Braun, J. (2019). A versatile, linear complexity algorithm for flow routing in topographies with depressions, *Earth Surf. Dynam., 7*, 549–562. https://doi.org/10.5194/esurf-7-549-2019

[2] Mareš, M. (2002). Two linear time algorithms for MST on minor closed graph classes. *ETHZ, Institute for Mathematical Research*. https://doi.org/10.3929/ethz-a-004354035

[3] Zhou, G., Wei, H., and Fu, S. (2019). A fast and simple algorithm for calculating flow accumulation matrices from raster digital elevation. Front. *Earth Sci. 13*, 317–326. https://doi.org/10.1007/s11707-018-0725-9