civ_map_generator 0.1.5

use rand::{Rng, seq::IndexedRandom};

use crate::{
    grid::{
        Grid,
        direction::Direction,
        hex_grid::{HexGrid, HexOrientation},
    },
    tile::Tile,
    tile_component::{BaseTerrain, TerrainType},
    tile_map::{River, RiverEdge, TileMap},
};

impl TileMap {
    /// Adds rivers to the map.
    pub fn add_rivers(&mut self) {
        let grid = self.world_grid.grid;

        let river_source_range_default = 4;
        let sea_water_range_default = 3;
        // `TILES_PER_RIVER_EDGE` specifies the number of tiles required before a river edge can appear.
        // When `TILES_PER_RIVER_EDGE` is set to 12, it indicates that for every 12 tiles, there can be 1 river edge.
        const TILES_PER_RIVER_EDGE: u32 = 12;

        (0..4).for_each(|index| {
            let (river_source_range, sea_water_range) = if index <= 1 {
                (river_source_range_default, sea_water_range_default)
            } else {
                (
                    (river_source_range_default / 2),
                    (sea_water_range_default / 2),
                )
            };

            self.all_tiles().for_each(|tile| {
                let terrain_type = tile.terrain_type(self);
                let area_id = tile.area_id(self);
                // Check if the tile can be a river starting location.
                let pass_condition = match index {
                    0 => {
                        // Mountain and Hill are the 1st priority for river starting locations.
                        matches!(terrain_type, TerrainType::Mountain | TerrainType::Hill)
                    }
                    1 => {
                        // Land tiles that are not near the coast are the 2nd priority for river starting locations.
                        terrain_type != TerrainType::Water
                            && !tile.is_coastal_land(self)
                            && self.random_number_generator.random_range(0..8) == 0
                    }
                    2 => {
                        // If there are still not enough rivers generated, the algorithm should run again using Mountain and Hill as the river starting locations.
                        let num_tiles = self.area_list[area_id].size;
                        let num_river_edges = self.river_edge_count(area_id);
                        matches!(terrain_type, TerrainType::Mountain | TerrainType::Hill)
                            && (num_river_edges <= num_tiles / TILES_PER_RIVER_EDGE)
                    }
                    3 => {
                        // At last if there are still not enough rivers generated, the algorithm should run again using any Land tiles as the river starting locations.
                        let num_tiles = self.area_list[area_id].size;
                        let num_river_edges = self.river_edge_count(area_id);
                        terrain_type != TerrainType::Water
                            && (num_river_edges <= num_tiles / TILES_PER_RIVER_EDGE)
                    }
                    _ => unreachable!(),
                };

                // Tile should meet these conditions:
                // 1. It should meet the pass condition
                // 2. It should be not a natural wonder
                // 3. It should not be adjacent to a natural wonder
                // 4. all tiles around it in a given distance `river_source_range` (including self) should be not fresh water
                // 5. all tiles around it in a given distance `sea_water_range` (including self) should be not water
                if pass_condition
                    && tile.natural_wonder(self).is_none()
                    && !tile
                        .neighbor_tiles(grid)
                        .any(|neighbor_tile| neighbor_tile.natural_wonder(self).is_some())
                    && !tile
                        .tiles_in_distance(river_source_range, grid)
                        .any(|tile| tile.is_freshwater(self))
                    && !tile
                        .tiles_in_distance(sea_water_range, grid)
                        .any(|tile| tile.terrain_type(self) == TerrainType::Water)
                {
                    let start_tile = self.get_inland_corner(tile);
                    if let Some(start_tile) = start_tile {
                        self.do_river(start_tile, None);
                    }
                }
            });
        });
    }

    /// This function is called to create a river.
    ///
    /// # Arguments
    ///
    /// - `start_tile`: The tile where the river starts.
    /// - `original_flow_direction`: The original flow direction at the start of the river.
    ///   - `None`: Algorithm automatically determines initial flow direction (default)
    ///   - `Some(Direction)`: Forces specific starting flow direction (must be a valid direction
    ///     from [`Grid::corner_direction_array()`])
    fn do_river(&mut self, start_tile: Tile, original_flow_direction: Option<Direction>) {
        let grid = self.world_grid.grid;
        // This array contains the list of tuples.
        // In this tuple, the elemment means as follows:
        // 1. The first element indicates the next possible flow direction of the river.
        // 2. The second element represents the direction of a neighboring tile relative to the current tile.
        //    We evaluate the weight value of these neighboring tiles using a certain algorithm and select the minimum one to determine the next flow direction of the river.
        let flow_direction_and_neighbor_tile_direction = match grid.layout.orientation {
            HexOrientation::Pointy => [
                (Direction::North, Direction::NorthWest),
                (Direction::NorthEast, Direction::NorthEast),
                (Direction::SouthEast, Direction::East),
                (Direction::South, Direction::SouthWest),
                (Direction::SouthWest, Direction::West),
                (Direction::NorthWest, Direction::NorthWest),
            ],
            HexOrientation::Flat => [
                (Direction::East, Direction::NorthEast),
                (Direction::SouthEast, Direction::South),
                (Direction::SouthWest, Direction::SouthWest),
                (Direction::West, Direction::NorthWest),
                (Direction::NorthWest, Direction::NorthWest),
                (Direction::NorthEast, Direction::North),
            ],
        };

        /************ Do river start ************/

        // If the start tile have a river, exit the function
        // That will also prevent the river from forming a loop
        if self
            .river_list
            .iter()
            .flatten()
            .any(|river_edge| river_edge.tile == start_tile)
        {
            return;
        }

        // Create a new river
        let mut river = River::new();

        let mut start_tile = start_tile;
        let mut original_flow_direction = original_flow_direction;
        let mut this_flow_direction = original_flow_direction;

        loop {
            let mut river_tile;
            if let Some(this_flow_direction) = this_flow_direction {
                match (grid.layout.orientation, this_flow_direction) {
                    /********** Pointy Hex Orientation And Flow Direction **********/
                    (HexOrientation::Pointy, Direction::East | Direction::West) => unreachable!(),
                    (HexOrientation::Pointy, Direction::North) => {
                        river_tile = start_tile;
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::NorthEast, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || neighbor_tile.has_river_in_direction(Direction::SouthEast, self)
                                || neighbor_tile.has_river_in_direction(Direction::SouthWest, self)
                            {
                                break;
                            } else {
                                river_tile = neighbor_tile;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Pointy, Direction::NorthEast) => {
                        river_tile = start_tile;
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) = river_tile.neighbor_tile(Direction::East, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || river_tile.has_river_in_direction(Direction::East, self)
                                || neighbor_tile.has_river_in_direction(Direction::SouthWest, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Pointy, Direction::SouthEast) => {
                        if let Some(neighbor_tile) = start_tile.neighbor_tile(Direction::East, grid)
                        {
                            river_tile = neighbor_tile
                        } else {
                            break;
                        };
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::SouthEast, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || river_tile.has_river_in_direction(Direction::SouthEast, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                        if let Some(neighbor_tile2) =
                            river_tile.neighbor_tile(Direction::SouthWest, grid)
                        {
                            if neighbor_tile2.terrain_type(self) == TerrainType::Water
                                || neighbor_tile2.has_river_in_direction(Direction::East, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Pointy, Direction::South) => {
                        if let Some(neighbor_tile) =
                            start_tile.neighbor_tile(Direction::SouthWest, grid)
                        {
                            river_tile = neighbor_tile
                        } else {
                            break;
                        };
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::SouthEast, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || river_tile.has_river_in_direction(Direction::SouthEast, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                        if let Some(neighbor_tile2) =
                            river_tile.neighbor_tile(Direction::East, grid)
                        {
                            if neighbor_tile2.has_river_in_direction(Direction::SouthWest, self) {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Pointy, Direction::SouthWest) => {
                        river_tile = start_tile;
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::SouthWest, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || neighbor_tile.has_river_in_direction(Direction::East, self)
                                || river_tile.has_river_in_direction(Direction::SouthWest, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Pointy, Direction::NorthWest) => {
                        river_tile = start_tile;
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) = river_tile.neighbor_tile(Direction::West, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || neighbor_tile.has_river_in_direction(Direction::East, self)
                                || neighbor_tile.has_river_in_direction(Direction::SouthEast, self)
                            {
                                break;
                            } else {
                                river_tile = neighbor_tile;
                            }
                        } else {
                            break;
                        }
                    }
                    /********** End Pointy Hex Orientation And Flow Direction **********/
                    /********** Flat Hex Orientation And Flow Direction **********/
                    (HexOrientation::Flat, Direction::North | Direction::South) => unreachable!(),
                    (HexOrientation::Flat, Direction::NorthEast) => {
                        river_tile = start_tile;
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::NorthEast, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || river_tile.has_river_in_direction(Direction::NorthEast, self)
                                || neighbor_tile.has_river_in_direction(Direction::South, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Flat, Direction::East) => {
                        if let Some(neighbor_tile) =
                            start_tile.neighbor_tile(Direction::NorthEast, grid)
                        {
                            river_tile = neighbor_tile
                        } else {
                            break;
                        };
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::SouthEast, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || river_tile.has_river_in_direction(Direction::SouthEast, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                        if let Some(neighbor_tile2) =
                            river_tile.neighbor_tile(Direction::South, grid)
                        {
                            if neighbor_tile2.terrain_type(self) == TerrainType::Water
                                || neighbor_tile2.has_river_in_direction(Direction::NorthEast, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Flat, Direction::SouthEast) => {
                        if let Some(neighbor_tile) =
                            start_tile.neighbor_tile(Direction::South, grid)
                        {
                            river_tile = neighbor_tile
                        } else {
                            break;
                        };
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::SouthEast, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || river_tile.has_river_in_direction(Direction::SouthEast, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                        if let Some(neighbor_tile2) =
                            river_tile.neighbor_tile(Direction::NorthEast, grid)
                        {
                            if neighbor_tile2.terrain_type(self) == TerrainType::Water
                                || neighbor_tile2.has_river_in_direction(Direction::South, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Flat, Direction::SouthWest) => {
                        river_tile = start_tile;
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::South, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || river_tile.has_river_in_direction(Direction::South, self)
                                || neighbor_tile.has_river_in_direction(Direction::NorthEast, self)
                            {
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Flat, Direction::West) => {
                        river_tile = start_tile;
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::SouthWest, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || neighbor_tile.has_river_in_direction(Direction::NorthEast, self)
                                || neighbor_tile.has_river_in_direction(Direction::SouthEast, self)
                            {
                                break;
                            } else {
                                river_tile = neighbor_tile;
                            }
                        } else {
                            break;
                        }
                    }
                    (HexOrientation::Flat, Direction::NorthWest) => {
                        river_tile = start_tile;
                        river.push(RiverEdge::new(river_tile, this_flow_direction));
                        if let Some(neighbor_tile) =
                            river_tile.neighbor_tile(Direction::North, grid)
                        {
                            if neighbor_tile.terrain_type(self) == TerrainType::Water
                                || neighbor_tile.has_river_in_direction(Direction::South, self)
                                || neighbor_tile.has_river_in_direction(Direction::SouthEast, self)
                            {
                                break;
                            } else {
                                river_tile = neighbor_tile;
                            }
                        } else {
                            break;
                        }
                    } /********** End Flat Hex Orientation And Flow Direction **********/
                }
            } else {
                river_tile = start_tile;
            }

            if river_tile.terrain_type(self) == TerrainType::Water {
                break;
            }

            // Get all next possible flow directions of the river.
            let next_possible_flow_directions: Vec<Direction> =
                if let Some(this_flow_direction) = this_flow_direction {
                    // If `this_flow_direction` is Some, we can choose at most 2 directions as the next flow direction.
                    // The next flow direction should not be the opposite of the original flow direction.
                    next_flow_directions(this_flow_direction, grid)
                        .into_iter()
                        .filter(|&flow_direction| {
                            Some(flow_direction.opposite()) != original_flow_direction
                        })
                        .collect()
                } else {
                    // If `this_flow_direction` is None, we can choose 6 directions as the next flow direction.
                    grid.corner_direction_array().to_vec()
                };

            // Get next possible flow direction and relative neighbor tile iterator to calculate the best flow direction.
            // NOTICE: When the river flows to the edge of the map, relative neighbor tile may not exist.
            let next_possible_flow_direction_and_neighbor_tile_iter =
                flow_direction_and_neighbor_tile_direction
                    .into_iter()
                    .filter_map(|(flow_direction, direction)| {
                        if next_possible_flow_directions.contains(&flow_direction) {
                            river_tile
                                .neighbor_tile(direction, grid)
                                .map(|neighbor_tile| (flow_direction, neighbor_tile))
                        } else {
                            None
                        }
                    });

            /********** Get the best flow direction **********/
            // We always choose flow direction with the lowest value.
            let mut best_flow_direction = None;
            let mut best_value = i32::MAX;

            next_possible_flow_direction_and_neighbor_tile_iter.for_each(
                |(flow_direction, neighbor_tile)| {
                    let mut value = self.river_value_at_tile(neighbor_tile);
                    // That will make `flow_direction` equal to `original_flow_direction` is more likely to be preferred.
                    if Some(flow_direction) == original_flow_direction {
                        value = value * 3 / 4;
                    }
                    if value < best_value {
                        best_value = value;
                        best_flow_direction = Some(flow_direction);
                    }
                },
            );
            /********** End get the best flow direction **********/

            /********** Tackle with the situation when river flows to the edge of map **********/
            // When the river flows to the edge of the map,
            // in this case, `flow_direction_and_neighbor_tile` may be empty,
            // we can't choose any direction as `best_flow_direction` according to the algorithm above.
            // And then we should tackle with this situation.
            if best_flow_direction.is_none()
                && let Some(original_flow_direction) = original_flow_direction
            {
                if next_possible_flow_directions.contains(&original_flow_direction) {
                    // If `original_flow_direction` is in `next_possible_flow_directions`,
                    // we choose `original_flow_direction` as `best_flow_direction`.
                    best_flow_direction = Some(original_flow_direction);
                } else {
                    // If `original_flow_direction` is not in `next_possible_flow_directions`,,
                    // we randomly choose one direction from `next_possible_flow_directions` as `best_flow_direction`.
                    best_flow_direction = next_possible_flow_directions
                        .choose(&mut self.random_number_generator)
                        .copied();
                }
            }
            /********** End tackle with the situation when river flows to the edge of map **********/

            if best_flow_direction.is_some() {
                original_flow_direction = original_flow_direction.or(best_flow_direction);
                start_tile = river_tile;
                this_flow_direction = best_flow_direction;
            } else {
                break;
            }
        }
        /************ Do river End ************/
        // If the river has any river edge, add it to the river list of the map.
        if !river.is_empty() {
            self.river_list.push(river);
        }
    }

    /// Returns the value representing the suitability of flow direction for a river according to the tile.
    ///
    /// The lower the value, the more suitable the flow direction is.
    fn river_value_at_tile(&mut self, tile: Tile) -> i32 {
        fn tile_elevation(tile_map: &TileMap, tile: Tile) -> i32 {
            match tile.terrain_type(tile_map) {
                TerrainType::Mountain => 4,
                TerrainType::Hill => 3,
                TerrainType::Water => 2,
                TerrainType::Flatland => 1,
            }
        }

        let grid = self.world_grid.grid;

        // Check if the tile itself or any of its neighboring tiles are natural wonders.
        if tile.natural_wonder(self).is_some()
            || tile
                .neighbor_tiles(grid)
                .any(|neighbor_tile| neighbor_tile.natural_wonder(self).is_some())
        {
            return -1;
        }

        let mut sum = tile_elevation(self, tile) * 20;

        // Usually, the tile have 6 neighbors. If not, the sum increases by 40 for each missing neighbor of the tile.
        sum += 40 * (6 - tile.neighbor_tiles(grid).count() as i32);

        tile.neighbor_tiles(grid).for_each(|neighbor_tile| {
            sum += tile_elevation(self, neighbor_tile);
            if neighbor_tile.base_terrain(self) == BaseTerrain::Desert {
                sum += 4;
            }
        });

        sum += self.random_number_generator.random_range(0..10);
        sum
    }

    /// Retrieves an inland corner tile based on the provided tile.
    ///
    /// *An inland corner* is defined as a tile that has all its neighboring tiles in specific directions
    /// (0 to 3) existing and not being water.
    ///
    /// At first, the function will collect the current tile and its neighbors
    /// located in specified edge directions (3 to 5), then filter out those that do not qualify
    /// as inland corners. Finally, choose one of the qualified inland corners randomly.
    ///
    /// # Arguments
    ///
    /// - `tile`: The current tile.
    ///
    /// # Returns
    ///
    /// Returns `Some(Tile)` if an inland corner is found,
    /// or `None` if no such inland corner exists.
    fn get_inland_corner(&mut self, tile: Tile) -> Option<Tile> {
        let grid = self.world_grid.grid;
        // We choose current tile and its `grid.edge_direction_array()[3..6]` neighbors as the candidate inland corners

        // Initialize a list with the current tile
        let mut tile_list = vec![tile];

        // Collect valid neighbor tiles in edge directions [3..6]
        tile_list.extend(
            grid.edge_direction_array()[3..6]
                .iter()
                .filter_map(|&direction| tile.neighbor_tile(direction, grid)),
        );

        // Retain only those tiles that qualify as inland corners
        // An inland corner requires all neighbors in edge directions [0..3] to exist and not be water
        tile_list.retain(|&tile| {
            grid.edge_direction_array()[0..3].iter().all(|&direction| {
                tile.neighbor_tile(direction, grid)
                    .is_some_and(|neighbor_tile| {
                        neighbor_tile.terrain_type(self) != TerrainType::Water
                    })
            })
        });

        // Choose a random corner if any exist
        tile_list.choose(&mut self.random_number_generator).copied()
    }

    /// Returns the number of river edges in the current area according to `area_id`
    fn river_edge_count(&self, current_area_id: usize) -> u32 {
        self.river_list
            .iter()
            .flatten()
            .filter(|river_edge| river_edge.tile.area_id(self) == current_area_id)
            .count() as u32
    }
}

/// Returns the next possible flow directions of the river based on the current flow direction.
///
/// # Arguments
///
/// - `flow_direction`: The current direction of the river flow.
/// - `grid`: The grid containing the tile map.
///
/// # Returns
///
/// An array containing two `Direction` values:
/// - The first element represents the flow direction after a clockwise turn.
/// - The second element represents the flow direction after a counterclockwise turn.
fn next_flow_directions(flow_direction: Direction, grid: HexGrid) -> [Direction; 2] {
    let hex_orientation = grid.layout.orientation;
    [
        hex_orientation.corner_clockwise(flow_direction), // turn_right_flow_direction
        hex_orientation.corner_counter_clockwise(flow_direction), // turn_left_flow_direction
    ]
}