civ_map_generator 0.1.8

//! This module provides functionality for generating and manipulating fractal maps which can be used in games like Civilization.

use std::{
    cmp::{max, min},
    path::Path,
};

use bitflags::bitflags;

use image::{
    DynamicImage, GrayImage, ImageBuffer,
    imageops::{FilterType, resize},
};
use rand::{RngExt, rngs::StdRng, seq::IndexedRandom};

use crate::grid::{
    Cell, Grid, Size, WrapFlags, direction::Direction, offset_coordinate::OffsetCoordinate,
};

const DEFAULT_WIDTH_EXP: u32 = 7;
const DEFAULT_HEIGHT_EXP: u32 = 6;

/// A fractal generator for generating terrain maps using diamond-square algorithm and voronoi Algorithm.
pub struct CvFractal<G: Grid> {
    /// The map/world size, equal to the grid size which is used in the game.
    ///
    /// **Different** from [`CvFractal::fractal_grid`], The map size can be any valid size.
    map_size: Size,
    /// The fractal grid.
    ///
    /// It is the same as the grid used in the game **except** the grid's size.
    /// The size is determined by [`Self::fractal_exp`]:
    /// - Width resolution: `1 << width_exp` (power of 2)
    /// - Height resolution: `1 << height_exp` (power of 2)
    fractal_grid: G,
    /// The fractal's flags. It is used to control the fractal's generation process.
    ///
    /// # Notes
    ///
    /// In original CIV 5, [`FractalFlags`] also contains the fields `WarpX` and `WarpY` flags.
    /// In this implementation, the field [`CvFractal::fractal_grid`] controls the wrap behavior directly.
    /// we don't need to support warp flags in [`FractalFlags`].
    flags: FractalFlags,
    /// Fractal source grid resolution exponent configuration.
    ///
    /// Actual width/height resolution is automatically calculated as 2^exponent,
    /// ensuring [`Self::fractal_grid`]'s dimensions are always powers of two.
    fractal_exp: FractalExp,
    /// Stores the 2D fractal array with dimensions `[2^m + 1][2^n + 1]` for the Diamond-Square algorithm.
    ///
    /// # Notes
    ///
    /// The array includes an extra row (last row) and column (last column) beyond the final [`Self::fractal_grid`] — these are not part of the output fractal surface,
    /// but are necessary for the algorithm to work correctly.
    ///
    /// In Diamond-Square algorithm, this fractal array is divided into smaller sub-grids for calculating fractal values.
    fractal_array: Vec<Vec<u32>>,
}

impl<G: Grid> CvFractal<G> {
    /// Creates a new empty fractal with the given parameters.
    ///
    /// # Arguments
    ///
    /// - `grid`: The base map/world grid (distinct from [`CvFractal::fractal_grid`])
    /// - `flags`: Bit flags controlling fractal generation behavior
    /// - `width_exp`: The exponent for calculating fractal width (width = 2^width_exp)
    ///   - To replicate original behavior with negative values, use [`DEFAULT_WIDTH_EXP`] directly
    /// - `height_exp`: The exponent for calculating fractal height (height = 2^height_exp)
    ///   - To replicate original behavior with negative values, use [`DEFAULT_HEIGHT_EXP`] directly
    ///
    /// # Notes
    ///
    /// In original CIV5, `width_exp` and `height_exp` parameter was allowed to be negative,
    /// and when they are negative, the function will use [`DEFAULT_WIDTH_EXP`] and [`DEFAULT_HEIGHT_EXP`] respectively.
    /// In this implementation, negative values are not allowed, you should use [`DEFAULT_WIDTH_EXP`] and [`DEFAULT_HEIGHT_EXP`] directly.
    fn empty(grid: G, flags: FractalFlags, fractal_exp: FractalExp) -> Self {
        let map_size = grid.size();

        let fractal_width = fractal_exp.fractal_width();
        let fractal_height = fractal_exp.fractal_height();

        let fractal_grid = grid.with_dimensions(fractal_width, fractal_height);

        let fractal_array =
            vec![vec![0; (fractal_height + 1) as usize]; (fractal_width + 1) as usize];

        Self {
            map_size,
            fractal_grid,
            fractal_array,
            flags,
            fractal_exp,
        }
    }

    /// Generate a fractal with the given parameters.
    /// # Arguments
    ///
    /// - `random`: Random number generator.
    /// - `grain`: Controls the level of detail or smoothness of the fractal.\
    ///     - Valid range (If the provided value exceeds the maximum allowed value, it will be clamped to the maximum allowed value):
    ///         - `[0, 7.min(width_exp).min(height_exp)]`
    ///     - Effect on algorithm (The value determines how many iterations the diamond-square algorithm will execute):
    ///         - Higher grain → Fewer iterations → More random noise\
    ///           When `grain` equals the maximum allowed value, the fractal is completely random.
    ///         - Lower grain → More iterations → Smoother gradients\
    ///           When `grain = 0`, the fractal is the smoothest.
    /// - `hint_image`: Optional image to use as an initial source for the fractal.\
    ///   The fractal array is first divided into smaller sub-grids according to the argument `grain`.
    ///   The four corner points of each sub-grid serve as initial control points for the diamond-square algorithm.\
    ///     - When `hint_image` is `None`, each sub-grid-corner is initialized with a random value.
    ///     - When `hint_image` is `Some`, each sub-grid-corner is sampled from `hint_image`.
    /// - `rifts`: Optional fractal to use as a source for the fractal to add rifts. When `rifts` is `None`, no rifts are added.\
    ///     - `rifts`'s width and height must be equal to the width and height of `self`.
    ///
    /// # Algorithm Steps
    ///
    /// 1. Divide the fractal array into smaller sub-grids according to `grain`.
    /// 2. Initialize the four corner points of each sub-grid as control points:
    ///    - If `hint_image` is `None`, assign random values.
    ///    - If `hint_image` is `Some`, sample values from `hint_image`.
    /// 3. Run the diamond-square algorithm iteratively within each sub-grid to compute
    ///    the height values of all remaining (non-sub-grid-corner) points.
    /// 4. Tackle other fractal effects, such as add rifts...
    ///
    /// # Panics
    ///
    /// Panics if `grain` is invalid.
    ///
    /// # Notes
    ///
    /// Original CIV5 only supports to create vertical rifts when the fractal is WrapX.
    /// This function support to create both vertical and horizontal rifts.
    /// But we suggest to create only one of them at a time.
    fn generate_fractal(
        &mut self,
        random: &mut StdRng,
        grain: u32,
        hint_image: Option<&DynamicImage>,
        rifts: Option<&CvFractal<G>>,
    ) {
        let fractal_exp = self.fractal_exp;
        let fractal_width = fractal_exp.fractal_width();
        let fractal_height = fractal_exp.fractal_height();

        // Maximum allowed value of `grain`, which also serves as the maximum iteration count for the Diamond-Square algorithm.
        let max_allowed = 7.min(fractal_exp.width_exp).min(fractal_exp.height_exp);

        let grain = if grain > max_allowed {
            eprintln!(
                "Warning: grain value {} exceeds maximum allowed value {}. Clamping to {}.",
                grain, max_allowed, max_allowed
            );
            max_allowed
        } else {
            grain
        };

        // Convert to usize for the following calculations.
        // `smooth` is the iteration count for the Diamond-Square algorithm.
        let smooth = (max_allowed - grain) as usize;

        // At first, divide the fractal array into smaller sub-grids ((2^smooth) * (2^smooth) squares),
        // The four corner points of each sub-grid serve as initial control points for the diamond-square algorithm.
        // `hint_width` is the num of `sub-grid-corner` in every row after dividing.
        // Notes: when the fractal is WrapX, we don't consider the last row,
        //      because the last row of the fractal is the same as the first row,
        //      We preprocess this case at the beginning of every iter stage in Diamond-Square algorithm.
        let hint_width = (fractal_width >> smooth)
            + if self.fractal_grid.wrap_flags().contains(WrapFlags::WrapX) {
                0
            } else {
                1
            };
        // `hint_height` is the num of `sub-grid-corner` in every column after dividing.
        // Notes: when the fractal is WrapY, we don't consider the last column,
        //      because the last column of the fractal is the same as the first column,
        //      We preprocess this case at the beginning of every iter in Diamond-Square algorithm.
        let hint_height = (fractal_height >> smooth)
            + if self.fractal_grid.wrap_flags().contains(WrapFlags::WrapY) {
                0
            } else {
                1
            };

        // Initialize the four corner points of each sub-grid as control points by sampling values from `hint_image` or assign random values.
        if let Some(img) = hint_image {
            // Resize the image to the hint size if necessary, and convert it to grayscale.
            let gray_hint_img = if hint_width != img.width() || hint_height != img.height() {
                eprintln!(
                    "Image size {}x{} doesn't match hint size {}x{}.
                    We will resize the image to the hint size.
                    Please check if it is the correct behavior.
                    Resizing...",
                    img.width(),
                    img.height(),
                    hint_width,
                    hint_height
                );
                img.resize_exact(hint_width, hint_height, FilterType::Triangle)
                    .to_luma8()
            } else {
                eprintln!(
                    "Image size matches hint size: {}x{}",
                    img.width(),
                    img.height()
                );
                img.to_luma8()
            };

            // Assign an initial value to each vertex by `gray_hint_img` for later use in the diamond-square algorithm.
            for x in 0..hint_width as usize {
                for y in 0..hint_height as usize {
                    self.fractal_array[x << smooth][y << smooth] =
                        gray_hint_img.get_pixel(x as u32, y as u32)[0] as u32;
                }
            }
        } else {
            // Assign an initial value to each vertex by random number generator for later use in the diamond-square algorithm.
            for x in 0..hint_width as usize {
                for y in 0..hint_height as usize {
                    self.fractal_array[x << smooth][y << smooth] = random.random_range(0..256);
                    // Fractal Gen 1
                }
            }
        }

        for pass in (0..smooth).rev() {
            /*********** start to preprocess fractal_array[][] at the beginning of every iter stage in Diamond-Square algorithm ***********/

            // If wrapping in the Y direction is needed, copy the bottom row to the top
            if self.fractal_grid.wrap_flags().contains(WrapFlags::WrapY) {
                for x in 0..=fractal_width as usize {
                    self.fractal_array[x][fractal_height as usize] = self.fractal_array[x][0];
                }
            } else if self.flags.contains(FractalFlags::Polar) {
                // Polar coordinate transformation, the top and bottom row will be set to 0
                for x in 0..=fractal_width as usize {
                    self.fractal_array[x][0] = 0;
                    self.fractal_array[x][fractal_height as usize] = 0;
                }
            }

            // If wrapping in the X direction is needed, copy the leftmost column to the rightmost
            if self.fractal_grid.wrap_flags().contains(WrapFlags::WrapX) {
                for y in 0..=fractal_height as usize {
                    self.fractal_array[fractal_width as usize][y] = self.fractal_array[0][y];
                }
            } else if self.flags.contains(FractalFlags::Polar) {
                // Polar coordinate transformation, the rightmost and the leftmost column will be set to 0
                for y in 0..=fractal_height as usize {
                    self.fractal_array[0][y] = 0;
                    self.fractal_array[fractal_width as usize][y] = 0;
                }
            }

            // If crust construction is needed, perform the processing
            if self.flags.contains(FractalFlags::CenterRift) {
                if self.fractal_grid.wrap_flags().contains(WrapFlags::WrapY) {
                    for x in 0..=fractal_width as usize {
                        for y in 0..=(fractal_height / 6) as usize {
                            let factor =
                                ((fractal_height / 12) as i32 - y as i32).unsigned_abs() + 1;
                            self.fractal_array[x][y] /= factor;
                            self.fractal_array[x][(fractal_height / 2) as usize + y] /= factor;
                        }
                    }
                }

                if self.fractal_grid.wrap_flags().contains(WrapFlags::WrapX) {
                    for y in 0..=fractal_height as usize {
                        for x in 0..=(fractal_width / 6) as usize {
                            let factor =
                                ((fractal_width / 12) as i32 - x as i32).unsigned_abs() + 1;
                            self.fractal_array[x][y] /= factor;
                            self.fractal_array[(fractal_width / 2) as usize + x][y] /= factor;
                        }
                    }
                }
            }

            /********** the end of preprocess fractal_array[][] **********/

            // Use this value to exclude the vertices which have already get spots in the previous iter.
            // Generate a value with the lowest `pass + 1` bits set to 1 and the rest set to 0.
            let screen = (1 << (pass + 1)) - 1;
            // Use Diamond-Square algorithm to get spots
            // At first, We divide the fractal array into smaller sub-grids ((2^smooth) * (2^smooth) squares),
            // Notice! it's different with original Diamond-Square algorithm:
            //      1. Diamond Step and Square Step are in the independent iter of each other in the original,
            //         in this code them are in the same iter.
            //      2. In the original Square Step will use the calculation result of the Diamond Step,
            //         in this code Square Step doesn't use the calculation result of the Diamond Step.
            for x in 0..((fractal_width >> pass) as usize
                + if self.fractal_grid.wrap_flags().contains(WrapFlags::WrapX) {
                    0
                } else {
                    1
                })
            {
                for y in 0..((fractal_height >> pass) as usize
                    + if self.fractal_grid.wrap_flags().contains(WrapFlags::WrapY) {
                        0
                    } else {
                        1
                    })
                {
                    // Interpolate
                    let mut sum = 0;
                    let randness = 1 << (7 - smooth + pass) as i32;
                    // `(x << pass) & screen != 0` is equivalent to `(x << pass) % (1 << (pass + 1)) != 0`
                    // `(y << pass) & screen != 0` is equivalent to `(y << pass) % (1 << (pass +1)) != 0`
                    match ((x << pass) & screen != 0, (y << pass) & screen != 0) {
                        (true, true) => {
                            // (center)
                            sum += self.fractal_array[(x - 1) << pass][(y - 1) << pass] as i32;
                            sum += self.fractal_array[(x + 1) << pass][(y - 1) << pass] as i32;
                            sum += self.fractal_array[(x - 1) << pass][(y + 1) << pass] as i32;
                            sum += self.fractal_array[(x + 1) << pass][(y + 1) << pass] as i32;
                            sum >>= 2;
                            sum += random.random_range(-randness..randness);
                            sum = sum.clamp(0, 255);
                            self.fractal_array[x << pass][y << pass] = sum as u32;
                        }
                        (true, false) => {
                            // (horizontal)
                            sum += self.fractal_array[(x - 1) << pass][y << pass] as i32;
                            sum += self.fractal_array[(x + 1) << pass][y << pass] as i32;
                            sum >>= 1;
                            sum += random.random_range(-randness..randness);
                            sum = sum.clamp(0, 255);
                            self.fractal_array[x << pass][y << pass] = sum as u32;
                        }
                        (false, true) => {
                            // (vertical)
                            sum += self.fractal_array[x << pass][(y - 1) << pass] as i32;
                            sum += self.fractal_array[x << pass][(y + 1) << pass] as i32;
                            sum >>= 1;
                            sum += random.random_range(-randness..randness);
                            sum = sum.clamp(0, 255);
                            self.fractal_array[x << pass][y << pass] = sum as u32;
                        }
                        _ => {
                            // (corner) This was already set in the previous iter.
                        }
                    }
                }
            }
        }

        if let Some(rifts) = rifts {
            debug_assert!(
                rifts.fractal_exp == self.fractal_exp,
                "Rifts's dimension must be equal to the main fractal's dimension"
            );

            self.tectonic_action(rifts);
        }

        if self.flags.contains(FractalFlags::InvertHeights) {
            self.fractal_array
                .iter_mut()
                .flatten()
                .for_each(|val| *val = 255 - *val);
        }
    }

    pub fn get_height(&self, x: i32, y: i32) -> u32 {
        debug_assert!(
            0 <= x && x < self.map_size.width as i32,
            "'x' is out of the range of the grid width"
        );
        debug_assert!(
            0 <= y && y < self.map_size.height as i32,
            "'y' is out of the range of the grid height"
        );

        let fractal_exp = self.fractal_exp;
        let fractal_width = fractal_exp.fractal_width();
        let fractal_height = fractal_exp.fractal_height();

        let width_ratio = fractal_width as f64 / self.map_size.width as f64;
        let height_ratio = fractal_height as f64 / self.map_size.height as f64;

        // Use bilinear interpolation to calculate the pixel value
        let src_x = (x as f64 + 0.5) * width_ratio - 0.5;
        let src_y = (y as f64 + 0.5) * height_ratio - 0.5;

        let x_diff = src_x - src_x.floor();
        let y_diff = src_y - src_y.floor();

        let src_x = min(src_x as usize, fractal_width as usize - 1);
        let src_y = min(src_y as usize, fractal_height as usize - 1);

        let value = (1.0 - x_diff) * (1.0 - y_diff) * self.fractal_array[src_x][src_y] as f64
            + x_diff * (1.0 - y_diff) * self.fractal_array[src_x + 1][src_y] as f64
            + (1.0 - x_diff) * y_diff * self.fractal_array[src_x][src_y + 1] as f64
            + x_diff * y_diff * self.fractal_array[src_x + 1][src_y + 1] as f64;

        let height = value.clamp(0.0, 255.0) as u32;

        if self.flags.contains(FractalFlags::Percent) {
            (height * 100) >> 8
        } else {
            height
        }
    }

    /// Calculate height thresholds from percentiles of a fractal array.
    ///
    /// It takes an array of percentages. Each percentage value is clamped between 0 and 100.
    /// Extracts all values from the fractal array except the last row and column,
    /// flattens and sorts them, then maps each percentile to its corresponding height.
    ///
    /// The final output is an array containing the calculated height thresholds corresponding to the input percentages.
    ///
    /// # Arguments
    ///
    /// * `percents`: An array of N percentage values (0-100).
    ///
    /// # Returns
    ///
    /// An array of N corresponding height thresholds.
    ///
    /// For example, when the input is `[72]`, the output might be `[120]`,
    /// meaning that 72% of all values will be below the height threshold of 120, and 28% will be above it.
    pub fn heights_from_percents<const N: usize>(&self, percents: [u32; N]) -> [u32; N] {
        let percents = percents.map(|p| p.clamp(0, 100));

        // Get all value from the fractal array except its last row and last column
        let mut flatten: Vec<&u32> = self
            .fractal_array
            .iter()
            .take(self.fractal_array.len() - 1)
            .flat_map(|row| row.iter().take(row.len() - 1))
            .collect();
        flatten.sort_unstable();

        let len = flatten.len();
        percents.map(|percent| {
            let target_index = ((len - 1) * percent as usize) / 100;
            let target_value = flatten[target_index];
            *target_value
        })
    }

    fn tectonic_action(&mut self, rifts: &CvFractal<G>) {
        let fractal_exp = self.fractal_exp;
        let fractal_width = fractal_exp.fractal_width();
        let fractal_height = fractal_exp.fractal_height();

        // `deep` is the maximum depth of the rift, which is in [0..=255].
        // The deepest point is typically in the middle of the rift.
        const DEEP: u32 = 0;

        // These values when fractal is WrapX
        let rift_x = (fractal_width / 4) * 3;
        // `width` is the distance from the leftmost/rightmost to the middle of the rift.
        // The width of the rift equals [2 * width].
        const WIDTH: u32 = 16;

        // These values when fractal is WrapY
        let rift_y = (fractal_height / 4) * 3;
        // `height` is the distance from the topmost/bottommost to the middle of the rift.
        // The height of the rift equals [2 * height].
        const HEIGHT: u32 = 16;

        if self.fractal_grid.wrap_x() {
            for y in 0..=fractal_height as usize {
                // `rift_value` is the horizontal center x-coordinate of the rift.
                // It's in [-fractal_width / 8, fractal_width / 8 - fractal_width / 1024] range.
                let rift_value = (rifts.fractal_array[rift_x as usize][y] as i32 - 128)
                    * fractal_width as i32
                    / 128
                    / 8;
                for x in 0..WIDTH {
                    // Rift along edge of map.

                    // Notes: Don't use `Grid::normalize_offset` here,
                    // because when `y = fractal_height`, the offset is not on the grid,
                    // and `normalize_offset` will return an `Err`.

                    let right_x = (rift_value + x as i32).rem_euclid(fractal_width as i32) as usize;
                    let left_x = (rift_value - x as i32).rem_euclid(fractal_width as i32) as usize;

                    self.fractal_array[right_x][y] =
                        (self.fractal_array[right_x][y] * x + DEEP * (WIDTH - x)) / WIDTH;
                    self.fractal_array[left_x][y] =
                        (self.fractal_array[left_x][y] * x + DEEP * (WIDTH - x)) / WIDTH;
                }
            }

            for y in 0..=fractal_height as usize {
                self.fractal_array[fractal_width as usize][y] = self.fractal_array[0][y];
            }
        }

        if self.fractal_grid.wrap_y() {
            for x in 0..=fractal_width as usize {
                // `rift_value` is the height of the rift at the given y coordinate
                // It's in [-fractal_height / 8, fractal_height / 8 - fractal_height / 1024] range.
                let rift_value = (rifts.fractal_array[x][rift_y as usize] as i32 - 128)
                    * fractal_height as i32
                    / 128
                    / 8;
                for y in 0..HEIGHT {
                    // Rift along edge of map.

                    // Notes: Don't use `Grid::normalize_offset` here,
                    // because when `x = fractal_width`, the offset is not on the grid,
                    // and `normalize_offset` will return an `Err`.
                    let top_y = (rift_value + y as i32).rem_euclid(fractal_height as i32) as usize;
                    let bottom_y =
                        (rift_value - y as i32).rem_euclid(fractal_height as i32) as usize;

                    self.fractal_array[x][top_y] =
                        (self.fractal_array[x][top_y] * y + DEEP * (HEIGHT - y)) / HEIGHT;
                    self.fractal_array[x][bottom_y] =
                        (self.fractal_array[x][bottom_y] * y + DEEP * (HEIGHT - y)) / HEIGHT;
                }
            }

            for x in 0..=fractal_width as usize {
                self.fractal_array[x][fractal_height as usize] = self.fractal_array[x][0];
            }
        }
    }

    pub fn ridge_builder(
        &mut self,
        random: &mut StdRng,
        num_voronoi_seeds: u32,
        ridge_flags: FractalFlags,
        blend_ridge: u32,
        blend_fract: u32,
    ) {
        let fractal_exp = self.fractal_exp;
        let fractal_width = fractal_exp.fractal_width();
        let fractal_height = fractal_exp.fractal_height();
        // this will use a modified Voronoi system to give the appearance of mountain ranges

        let num_voronoi_seeds = max(num_voronoi_seeds, 3); // make sure that we have at least 3

        let mut voronoi_seeds: Vec<VoronoiSeed> = Vec::with_capacity(num_voronoi_seeds as usize);

        for _ in 0..num_voronoi_seeds {
            let mut voronoi_seed;

            loop {
                voronoi_seed = VoronoiSeed::random_seed(random, &self.fractal_grid);

                // Check if the new random seed is too close to an existing seed
                let is_too_close = voronoi_seeds.iter().any(|existing_seed| {
                    let distance_between_voronoi_seeds = self
                        .fractal_grid
                        .distance_to(voronoi_seed.cell, existing_seed.cell);
                    distance_between_voronoi_seeds < 7
                });

                // If it's not too close, break the loop
                if !is_too_close {
                    break;
                }
            }

            voronoi_seeds.push(voronoi_seed);
        }

        for x in 0..fractal_width as usize {
            for y in 0..fractal_height as usize {
                // get the hex coordinate for this position
                let current_offset_coordinate = OffsetCoordinate::new(x as i32, y as i32);
                let current_cell = self
                    .fractal_grid
                    .offset_to_cell(current_offset_coordinate)
                    .unwrap();

                // find the distance to each of the seeds (with modifiers for strength of the seed, directional bias, and random factors)
                // closest seed distance is the distance to the seed with the lowest distance
                let mut closest_seed_distance = i32::MAX;
                // next closest seed distance is the distance to the seed with the second lowest distance
                let mut next_closest_seed_distance = i32::MAX;
                for current_voronoi_seed in &voronoi_seeds {
                    let mut modified_distance = self
                        .fractal_grid
                        .distance_to(current_cell, current_voronoi_seed.cell);
                    // Checking if ridge_flags is not empty
                    // If it is empty, we don't need to modify the distance
                    // If it is not empty, we need to modify the distance
                    // The distance is modified by the weakness of the seed, the bias direction, and the directional bias strength
                    // The weakness of the seed is used to make the influence of the seed on its surrounding area more random
                    // The bias direction is used to make the influence of the seed more directional
                    // The directional bias strength is used to make the influence of the seed more directional
                    if !ridge_flags.is_empty() {
                        // make the influence of the seed on its surrounding area more random
                        modified_distance += current_voronoi_seed.weakness as i32;

                        let relative_direction = self
                            .fractal_grid
                            .estimate_direction(current_cell, current_voronoi_seed.cell);

                        // make the influence of the seed more directional
                        if relative_direction == Some(current_voronoi_seed.bias_direction) {
                            modified_distance -=
                                current_voronoi_seed.directional_bias_strength as i32;
                        } else if relative_direction
                            == Some(current_voronoi_seed.bias_direction.opposite())
                        {
                            modified_distance +=
                                current_voronoi_seed.directional_bias_strength as i32;
                        }

                        modified_distance = max(1, modified_distance);
                    }

                    if modified_distance < closest_seed_distance {
                        next_closest_seed_distance = closest_seed_distance;
                        closest_seed_distance = modified_distance;
                    } else if modified_distance < next_closest_seed_distance {
                        next_closest_seed_distance = modified_distance;
                    }
                }

                // use the modified distance between the two closest seeds to determine the ridge height
                let ridge_height =
                    (255 * closest_seed_distance as u32) / next_closest_seed_distance as u32;

                // blend the new ridge height with the previous fractal height
                self.fractal_array[x][y] = (ridge_height * blend_ridge
                    + self.fractal_array[x][y] * blend_fract)
                    / max(blend_ridge + blend_fract, 1);
            }
        }
    }

    /// Get the noise map of the 2d Array which is used in the civ map. The map is saved as a gray image.
    pub fn write_to_file(&self, path: &Path) {
        let width = self.map_size.width;
        let height = self.map_size.height;
        let pixels: Vec<u8> = (0..height)
            .flat_map(|y| (0..width).map(move |x| self.get_height(x as i32, y as i32) as u8))
            .collect();

        let _ = image::save_buffer(
            Path::new(&path),
            &pixels,
            width,
            height,
            image::ColorType::L8,
        );
    }

    /// Get the noise map of the 2d Array which is used in the civ map. The map is saved as a gray image.
    ///
    /// The function is same as [`CvFractal::write_to_file`], but it uses the image crate to resize the image.
    pub fn write_to_file_by_image(&self, path: &Path) {
        let map_width = self.map_size.width;
        let map_height = self.map_size.height;
        // get gray_image from `self.fractal_array`
        let fractal_exp = self.fractal_exp;
        let fractal_width = fractal_exp.fractal_width();
        let fractal_height = fractal_exp.fractal_height();

        // NOTICE: `pixels` doesn't contain the last row and column of the `fractal_array`
        let pixels: Vec<u8> = (0..fractal_height as usize)
            .flat_map(|y| (0..fractal_width as usize).map(move |x| self.fractal_array[x][y] as u8))
            .collect();

        let image: GrayImage =
            ImageBuffer::from_raw(fractal_width, fractal_height, pixels).unwrap();

        // get resized_image
        let resized_image = resize(&image, map_width, map_height, FilterType::Triangle);
        resized_image.save(path).unwrap();
    }
}

/// A builder for constructing [`CvFractal`].
///
/// This builder allows for flexible configuration of fractal generation parameters.
/// It separates the construction process from the final object representation,
/// allowing for more granular control over the fractal settings.
///
/// # Examples
///
/// ## Basic Usage with Smart Defaults
///
/// ```rust
/// use civ_map_generator::fractal::CvFractalBuilder;
/// use civ_map_generator::grid::{*, hex_grid::*};
/// use rand::{SeedableRng, rngs::StdRng};
///
/// let grid = HexGrid::new(
///     Size { width: 80, height: 40 }, // Custom grid size
///     HexLayout {
///         orientation: HexOrientation::Flat,
///         size: [8., 8.],
///         origin: [0., 0.],
///     },
///     Offset::Odd,
///     WrapFlags::WrapX,
/// );
/// let mut rng = StdRng::seed_from_u64(42);
///
/// // Create a fractal with automatic grain calculation
/// let fractal = CvFractalBuilder::new(grid).build(&mut rng);
/// ```
///
/// ## Custom Configuration
///
/// ```rust
/// use civ_map_generator::fractal::{CvFractalBuilder, FractalFlags};
/// use civ_map_generator::grid::{*, hex_grid::*};
/// use rand::{SeedableRng, rngs::StdRng};
///
/// let grid = HexGrid::new(
///     Size { width: 80, height: 40 },
///     HexLayout {
///         orientation: HexOrientation::Flat,
///         size: [8., 8.],
///         origin: [0., 0.],
///     },
///     Offset::Odd,
///     WrapFlags::WrapX,
/// );
/// let mut rng = StdRng::seed_from_u64(42);
///
/// // Create a fractal with custom grain
/// let fractal = CvFractalBuilder::new(grid)
///     .grain(3)
///     .build(&mut rng);
/// ```
///
/// ## Fractal with Rifts
///
/// ```rust
/// use civ_map_generator::fractal::CvFractalBuilder;
/// use civ_map_generator::grid::{*, hex_grid::*};
/// use rand::{SeedableRng, rngs::StdRng};
///
/// let grid = HexGrid::new(
///     Size { width: 80, height: 40 }, // Custom grid size
///     HexLayout {
///         orientation: HexOrientation::Flat,
///         size: [8., 8.],
///         origin: [0., 0.],
///     }, // Hex layout
///     Offset::Odd, // Odd offset for hexagonal grid
///     WrapFlags::WrapX, // Wrap horizontally
/// );
/// let mut rng = StdRng::seed_from_u64(42);
///
/// // First create a rift fractal
/// let rift_fractal = CvFractalBuilder::new(grid)
///     .grain(1)
///     .build(&mut rng);
///
/// // Then use it to create the main fractal with rifts
/// let main_fractal = CvFractalBuilder::new(grid)
///     .grain(2)
///     .rift_fractal(&rift_fractal)
///     .build(&mut rng);
/// ```
pub struct CvFractalBuilder<'a, G: Grid> {
    grid: G,
    grain: u32,
    flags: FractalFlags,
    hint_image: Option<&'a DynamicImage>,
    rift_fractal: Option<&'a CvFractal<G>>,
    fractal_exp: FractalExp,
}

impl<'a, G: Grid> CvFractalBuilder<'a, G> {
    /// Creates a new `CvFractalBuilder` with the required grid parameter.
    ///
    /// # Arguments
    ///
    /// - `grid`: The base map/world grid (distinct from the fractal's internal grid)
    ///
    /// # Default Values
    ///
    /// - `grain`: 3
    ///   - This provides a good default that creates moderately detailed fractals
    ///   - Can be overridden using [`CvFractalBuilder::grain`]
    /// - `flags`: Empty flags (`FractalFlags::empty()`)
    ///   - Can be overridden using [`CvFractalBuilder::flags`]
    /// - `rift_fractal`: None (no rifts)
    ///   - Can be overridden using [`CvFractalBuilder::rift_fractal`]`
    /// - `hint_image`: None (no hint image)
    ///   - Can be overridden using [`CvFractalBuilder::hint_image`]
    /// - `fractal_exp`: [`DEFAULT_WIDTH_EXP`] (7) and [`DEFAULT_HEIGHT_EXP`] (6)
    ///   - Can be overridden using [`CvFractalBuilder::fractal_exp`]
    pub fn new(grid: G) -> Self {
        Self {
            grid,
            grain: 2,
            flags: FractalFlags::empty(),
            hint_image: None,
            rift_fractal: None,
            fractal_exp: FractalExp::new(DEFAULT_WIDTH_EXP, DEFAULT_HEIGHT_EXP),
        }
    }

    /// Sets the grain value for the fractal generation.
    ///
    /// # Arguments
    ///
    /// - `grain`: Controls the level of detail or smoothness of the fractal.\
    ///     - Valid range (If the provided value exceeds the maximum allowed value, it will be clamped to the maximum allowed value):
    ///         - `[0, 7.min(width_exp).min(height_exp)]`
    ///     - Effect on algorithm (The value determines how many iterations the diamond-square algorithm will execute):
    ///         - Higher grain → Fewer iterations → More random noise\
    ///           When `grain` equals the maximum allowed value, the fractal is completely random.
    ///         - Lower grain → More iterations → Smoother gradients\
    ///           When `grain = 0`, the fractal is the smoothest.
    ///
    /// # Notes
    ///
    /// Its default valid range is `[0, 6]` if you don't specify the values of `fractal_exp` by [`Self::fractal_exp`].
    pub fn grain(mut self, grain: u32) -> Self {
        self.grain = grain;
        self
    }

    /// Sets the flags for fractal generation behavior.
    ///
    /// # Arguments
    ///
    /// - `flags`: Bit flags controlling fractal generation behavior
    pub fn flags(mut self, flags: FractalFlags) -> Self {
        self.flags = flags;
        self
    }

    /// Sets the hint image for fractal generation.
    ///
    /// # Arguments
    ///
    /// - `hint_image`: A hint image for fractal generation.
    ///   The fractal array is first divided into smaller sub-grids according to the argument `grain`.
    ///   The four corner points of each sub-grid serve as initial control points for the diamond-square algorithm.\
    ///   The sub-grid-corner is sampled from `hint_image` for the initial control points.
    pub fn hint_image(mut self, hint_image: &'a DynamicImage) -> Self {
        self.hint_image = Some(hint_image);
        self
    }

    /// Sets the rift fractal for generating rifts in the main fractal.
    ///
    /// # Arguments
    ///
    /// - `rift_fractal`: A fractal to control the rifts generation.
    ///   Its dimensions must be equal to the fractal's dimensions.
    ///
    /// # Panics
    ///
    /// Panics if rift fractal dimensions don't match the main fractal dimensions
    ///
    /// # Notes
    ///
    /// - Rifts are only applied when the main fractal's grid is Wrapped (i.e., WrapX or WrapY).
    ///   If the grid is non-Wrap, rifts will have no effect.
    /// - Original CIV5 only supports vertical rifts when the fractal is WrapX.
    ///   This implementation supports both vertical and horizontal rifts.
    ///   It's recommended to create only one type of rift at a time.
    pub fn rift_fractal(mut self, rift_fractal: &'a CvFractal<G>) -> Self {
        self.rift_fractal = Some(rift_fractal);
        self
    }

    /// Sets the fractal exponent for the fractal generation.
    ///
    /// # Arguments
    ///
    /// - `fractal_exp`: The fractal exponent for the fractal generation.
    ///   
    /// # Notes
    ///
    /// It will effect the valid range of `grain` if you specify it.\
    /// `grain`'s valid range is `[0, 7.min(width_exp).min(height_exp)]`.
    pub fn fractal_exp(mut self, fractal_exp: FractalExp) -> Self {
        self.fractal_exp = fractal_exp;
        self
    }

    /// Finalizes the construction and returns the `CvFractal` instance.
    ///
    /// # Arguments
    ///
    /// - `random`: A mutable reference to a random number generator
    ///
    /// # Panics
    ///
    /// Panics if rift fractal dimensions don't match the main fractal dimensions
    ///
    /// # Examples
    ///
    /// ```rust
    /// use civ_map_generator::fractal::CvFractalBuilder;
    /// use civ_map_generator::grid::{*, hex_grid::*};
    /// use rand::{SeedableRng, rngs::StdRng};
    ///
    /// let grid = HexGrid::new(
    ///     Size { width: 80, height: 40 }, // Custom grid size
    ///     HexLayout {
    ///         orientation: HexOrientation::Flat,
    ///         size: [8., 8.],
    ///         origin: [0., 0.],
    ///     }, // Hex layout
    ///     Offset::Odd, // Odd offset for hexagonal grid
    ///     WrapFlags::WrapX, // Wrap horizontally
    /// );
    /// let mut rng = StdRng::seed_from_u64(42);
    ///
    /// // Use default grain (automatically calculated)
    /// let fractal = CvFractalBuilder::new(grid).build(&mut rng);
    ///
    /// // Or set custom grain
    /// let fractal = CvFractalBuilder::new(grid)
    ///     .grain(3)
    ///     .build(&mut rng);
    /// ```
    pub fn build(self, random: &mut StdRng) -> CvFractal<G> {
        let mut fractal = CvFractal::empty(self.grid, self.flags, self.fractal_exp);

        let rifts = self.rift_fractal;

        fractal.generate_fractal(random, self.grain, None, rifts);

        fractal
    }
}

bitflags! {
    /// Flags for the CvFractal. It is used to control the behavior of the fractal generation.
    ///
    /// # Notes
    ///
    /// In original CIV 5, [`FractalFlags`] also contains the fields `WarpX` and `WarpY` flags.
    /// In this implementation, [`CvFractal`] has a field [`CvFractal::fractal_grid`] which controls the wrap behavior.
    /// we don't need to support warp flags in [`FractalFlags`].
    #[derive(Clone, Copy, Debug, PartialEq, Eq)]
    pub struct FractalFlags: u8 {
        /// When flag is set, The closer to the edge of the grid, the closer the value of the height to 0.
        ///
        /// # Notes
        ///
        /// When grid is wrapped in the X direction, ignored in the X direction.
        /// When grid is wrapped in the Y direction, ignored in the Y direction.
        const Polar = 0b00000001;
        /// When flag is set, the value of the height is in `0..=99`, otherwise the value is in `0..=255`
        const Percent = 0b00000010;
        /// When flag is set, draws rift in center of world
        const CenterRift = 0b00000100;
        /// When flag is set, inverts the fractal height values, e.g. the original value is `fractal_value`, the new value is `255 - fractal_value`
        const InvertHeights = 0b00001000;
    }
}

/// A seed for the Voronoi diagram in the fractal grid.
struct VoronoiSeed {
    /// The cell of the seed in the fractal grid.
    pub cell: Cell,
    /// Implies the influence of the seed on its surrounding area.
    pub weakness: u32,
    /// Indicates the preferred direction or bias when assigning points within its influence region during the generation of the diagram.
    pub bias_direction: Direction,
    /// The strength of the bias direction.
    pub directional_bias_strength: u32,
}

impl VoronoiSeed {
    /// Generates a random seed for the fractal.
    pub fn random_seed(random: &mut StdRng, fractal_grid: &impl Grid) -> Self {
        let offset_coordinate = OffsetCoordinate::from([
            random.random_range(0..fractal_grid.width()),
            random.random_range(0..fractal_grid.height()),
        ]);

        let cell = fractal_grid.offset_to_cell(offset_coordinate).unwrap();

        let weakness = random.random_range(0..6);

        let bias_direction = *fractal_grid
            .edge_direction_array()
            .as_ref()
            .choose(random)
            .unwrap();

        let directional_bias_strength = random.random_range(0..4);

        VoronoiSeed {
            cell,
            weakness,
            bias_direction,
            directional_bias_strength,
        }
    }
}

/// Fractal source grid resolution exponent configuration
///
/// Actual width/height resolution is automatically calculated as 2^exponent,
/// ensuring dimensions are always powers of two
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct FractalExp {
    /// Width exponent, final width = 1 << width_exp
    width_exp: u32,
    /// Height exponent, final height = 1 << height_exp
    height_exp: u32,
}

impl FractalExp {
    pub const fn new(width_exp: u32, height_exp: u32) -> Self {
        Self {
            width_exp,
            height_exp,
        }
    }

    /// Get width exponent
    #[inline]
    pub const fn width_exp(&self) -> u32 {
        self.width_exp
    }

    /// Get height exponent
    #[inline]
    pub const fn height_exp(&self) -> u32 {
        self.height_exp
    }

    /// Get actual computed fractal width (1 << width_exp)
    #[inline]
    pub const fn fractal_width(&self) -> u32 {
        1 << self.width_exp
    }

    /// Get actual computed fractal height (1 << height_exp)
    #[inline]
    pub const fn fractal_height(&self) -> u32 {
        1 << self.height_exp
    }
}