use crate::outline_template_based::outline::OutlinePoints;

use crate::{LandGenerationParameters, LandGenerator};

use integral_geometry::{Point, Polygon, Rect, Size};

use land2d::Land2D;

pub struct MazeTemplate {

    width: usize,

    height: usize,

    cell_size: usize,

    inverted: bool,

    distortion_limiting_factor: u32,

    braidness: usize,

}

pub struct MazeLandGenerator {

    maze_template: MazeTemplate,

}

fn prev_odd(num: usize) -> usize {

    if num & 1 == 0 {

        num - 1

    } else {

        num

    }

}

impl MazeLandGenerator {

    pub fn new(maze_template: MazeTemplate) -> Self {

        Self { maze_template }

    }

    fn generate_outline<I: Iterator<Item = u32>>(

        &self,

        size: &Size,

        play_box: Rect,

        intersections_box: Rect,

        random_numbers: &mut I,

    ) -> OutlinePoints {

        let num_cells = Size::new(

            prev_odd(size.width / self.maze_template.cell_size),

            prev_odd(size.height / self.maze_template.cell_size),

        );

        let num_edges = Size::new(num_cells.width - 1, num_cells.height - 1);

        let seen_cells = Size::new(num_cells.width / 2, num_cells.height / 2);

        let num_steps = if self.maze_template.inverted { 3 } else { 1 };

        let mut step_done = vec![false; num_steps];

        let mut last_cell = vec![Point::diag(0); num_steps];

        let mut came_from_pos = vec![0; num_steps];

        let mut came_from = vec![vec![Point::diag(0); num_cells.area()]; num_steps];

        let mut done = false;

        let mut seen_list = vec![vec![None as Option<usize>; seen_cells.width]; seen_cells.height];

        let mut x_walls = vec![vec![true; seen_cells.width]; seen_cells.height - 1];

        let mut y_walls = vec![vec![true; seen_cells.width - 1]; seen_cells.height];

        let mut x_edge_list = vec![vec![false; num_edges.width]; num_cells.height];

        let mut y_edge_list = vec![vec![false; num_cells.width]; num_edges.height];

        let mut maze = vec![vec![false; num_cells.width]; num_cells.height];

        let off_y = 0;

        for current_step in 0..num_steps {

            let x = random_numbers.next().unwrap_or_default() as usize % (seen_cells.width - 1)

                / num_steps;

            last_cell[current_step] = Point::new(

                (x + current_step * seen_cells.width / num_steps) as i32,

                random_numbers.next().unwrap_or_default() as i32 / num_steps as i32,

            );

        }

        let see_cell = |current_step: usize, start_dir: Point, seen_list: &mut Vec<Vec<Option<usize>>>, x_walls: &mut Vec<Vec<bool>>, y_walls: &mut Vec<Vec<bool>>,

                        last_cell: &mut Vec<Point>, came_from: &mut Vec<Vec<Point>>, came_from_pos: &mut Vec<i32>| {

            loop {

                let p = last_cell[current_step];

                seen_list[p.y as usize][p.x as usize] = Some(current_step);

                let mut dir = start_dir;

                let next_dir_clockwise = true;//random_numbers.next().unwrap_or_default() % 2 == 0;

                for _ in 0..5 {

                    let sp = p + dir;

                    let when_seen =

                        if sp.x < 0

                            || sp.x >= seen_cells.width as i32

                            || sp.y < 0

                            || sp.y >= seen_cells.height as i32

                        {

                            None

                        } else {

                            Some(seen_list[sp.y as usize][sp.x as usize])

                        }

                    ;

                    match when_seen {

                        None => {

                            // try another direction

                            if dir.x == -1 && p.x > 0 {

                                y_walls[p.y as usize][p.x as usize - 1] = false;

                            }

                            if dir.x == 1 && p.x < seen_cells.width as i32 - 1 {

                                y_walls[p.y as usize][p.x as usize] = false;

                            }

                            if dir.y == -1 && p.y > 0 {

                                x_walls[p.y as usize][p.x as usize] = false;

                            }

                            if dir.y == 1 && p.y < seen_cells.height as i32 - 1 {

                                x_walls[p.y as usize][p.x as usize] = false;

                            }

                            if next_dir_clockwise {

                                dir = dir.rotate90();

                            } else {

                                dir = dir.rotate270();

                            }

                        }

                        Some(None) => {

                            // cell was not seen yet, go there

                            if dir.y == -1 {

                                x_walls[p.y as usize - 1][p.x as usize] = false;

                            }

                            if dir.y == 1 {

                                x_walls[p.y as usize][p.x as usize] = false;

                            }

                            if dir.x == -1 {

                                y_walls[p.y as usize][p.x as usize - 1] = false;

                            }

                            if dir.x == 1 {

                                y_walls[p.y as usize][p.x as usize] = false;

                            }

                            last_cell[current_step] = p + dir;

                            came_from_pos[current_step] += 1;

                            came_from[came_from_pos[current_step] as usize][current_step] = p;

                        }

                        _ => {

                            return true;

                        }

                    }

                }

                last_cell[current_step] = came_from[came_from_pos[current_step] as usize][current_step];

                came_from_pos[current_step] -= 1;

                return came_from_pos[current_step] < 0;

            }

        };

        let mut islands: Vec<Polygon> = vec![];

        let mut polygon: Vec<Point> = vec![];

        let add_vertex = |p: Point, polygon: &mut Vec<Point>| {

            let cell_size = self.maze_template.cell_size as i32;

            let [x, y] = [p.x, p.y].map(|i| {

                if self.maze_template.inverted || i & 1 == 0 {

                    cell_size

                } else {

                    cell_size * 2 / 3

                }

            });

            let new_point =

                Point::new((p.x - 1) * cell_size + x, (p.y - 1) * cell_size + y + off_y);

            let nv = polygon.len();

            if nv > 2 {

                if polygon[nv - 2].x == polygon[nv - 1].x && polygon[nv - 1].x == new_point.x

                    || polygon[nv - 2].y == polygon[nv - 1].y && polygon[nv - 1].y == new_point.y

                {

                    polygon.pop();

                }

            }

            polygon.push(new_point);

        };

        let add_edge = |p: Point, dir: Point, polygon: &mut Vec<Point>, x_edge_list: &mut Vec<Vec<bool>>, y_edge_list: &mut Vec<Vec<bool>>| {

            let mut dir = dir.rotate270();

            let mut next_p = Some(p);

            while let Some(p) = next_p {

                next_p = None;

                for _ in 0..4 {

                    dir = dir.rotate90();

                    let cdir = Point::new(

                        if dir.x < 0 { 0 } else { dir.x },

                        if dir.y < 0 { 0 } else { dir.y },

                    );

                    let np = p + cdir;

                    let edge_list = if dir.x == 0 {

                        &mut *x_edge_list

                    } else {

                        &mut *y_edge_list

                    };

                    if np.x >= 0

                        && np.y > 0

                        && np.x < num_cells.width as i32

                        && np.y < num_cells.height as i32

                        && edge_list[np.y as usize][np.x as usize]

                    {

                        (*edge_list)[np.y as usize][np.x as usize] = false;

                        add_vertex(p + dir + Point::new(1, 1), polygon);

                        next_p = Some(p + dir);

                        break;

                    }

                }

            }

        };

        while !done {

            done = true;

            for current_step in 0..num_steps {

                if !step_done[current_step] {

                    let dir = match random_numbers.next().unwrap_or_default() % 4 {

                        0 => Point::new(0, -1),

                        1 => Point::new(1, 0),

                        2 => Point::new(0, 1),

                        3 => Point::new(-1, 0),

                        _ => panic!(),

                    };

                    step_done[current_step] =

                        see_cell(current_step, dir, &mut seen_list, &mut x_walls, &mut y_walls, &mut last_cell, &mut came_from, &mut came_from_pos);

                    done = false;

                }

            }

        }

        for x in 0..seen_cells.width {

            for y in 0..seen_cells.height {

                if seen_list[y][x].is_some() {

                    maze[y * 2 + 1][x * 2 + 1] = true;

                }

            }

            for y in 0..seen_cells.height - 1 {

                if !x_walls[y][x] {

                    maze[y * 2 + 2][x * 2 + 1] = true;

                }

            }

        }

        for x in 0..seen_cells.width - 1 {

            for y in 0..seen_cells.height {

                if !y_walls[y][x] {

                    maze[y * 2 + 1][x * 2 + 2] = true;

                }

            }

        }

        for x in 0..num_edges.width {

            for y in 0..num_cells.height {

                x_edge_list[y][x] = maze[y][x] != maze[y][x + 1];

            }

        }

        for x in 0..num_cells.width {

            for y in 0..num_edges.height {

                y_edge_list[y][x] = maze[y][x] != maze[y + 1][x];

            }

        }

        for x in 0..num_edges.width {

            for y in 0..num_cells.height {

                if x_edge_list[y][x] {

                    x_edge_list[y][x] = false;

                    add_vertex(Point::new(x as i32 + 1, y as i32 + 1), &mut polygon);

                    add_vertex(Point::new(x as i32 + 1, y as i32), &mut polygon);

                    add_edge(Point::new(x as i32, y as i32 - 1), Point::new(0, -1), &mut polygon, &mut x_edge_list, &mut y_edge_list);

                    islands.push(Polygon::new(&polygon));

                    polygon.clear();

                }

            }

        }

        OutlinePoints {

            islands,

            fill_points: vec![],

            size: *size,

            play_box,

            intersections_box,

        }

    }

}

impl LandGenerator for MazeLandGenerator {

    fn generate_land<T: Copy + PartialEq + Default, I: Iterator<Item = u32>>(

        &self,

        parameters: &LandGenerationParameters<T>,

        random_numbers: &mut I,

    ) -> Land2D<T> {

        let do_invert = false;

        let (basic, zero) = if do_invert {

            (parameters.zero, parameters.basic)

        } else {

            (parameters.basic, parameters.zero)

        };

        let land_size = Size::new(self.maze_template.width, self.maze_template.height);

        let mut land = Land2D::new(&land_size, basic);

        let mut points = self.generate_outline(

            &land.size().size(),

            Rect::at_origin(land_size).with_margin(land_size.to_square().width as i32 * -2),

            land.play_box(),

            random_numbers,

        );

        if !parameters.skip_distort {

            points.distort(parameters.distance_divisor, random_numbers);

        }

        if !parameters.skip_bezier {

            points.bezierize(5);

        }

        points.draw(&mut land, zero);

        for p in &points.fill_points {

            land.fill(*p, zero, zero)

        }

        points.draw(&mut land, basic);

        land

    }

}