pathing.rs

use std::cmp::Ordering;
use std::collections::{BTreeSet, HashSet};
use std::hash::{Hash, Hasher};

use bevy::math::{uvec2, UVec2};
use pathfinding::prelude::{astar, astar_bag};

use crate::world::level_map::{LevelMap, MapLayer, MapTile};

#[derive(Copy, Clone, Debug, Default, Eq, PartialEq)]
pub struct PathingReqs {
	pub can_see: Option<bool>,
	pub can_walk: Option<bool>,
	pub can_fly: Option<bool>,
}

#[derive(Copy, Clone, Debug, Default)]
pub struct DistancePoint {
	distance: usize,
	point: UVec2,
}

impl DistancePoint {
	pub fn new(distance: usize, point: UVec2) -> Self {
		DistancePoint { distance, point }
	}
}

impl PartialEq for DistancePoint {
	fn eq(&self, other: &Self) -> bool {
		self.point.eq(&other.point)
	}
}

impl Eq for DistancePoint {}

impl PartialOrd for DistancePoint {
	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
		self.distance.partial_cmp(&other.distance)
	}
}

impl Ord for DistancePoint {
	fn cmp(&self, other: &Self) -> Ordering {
		self.distance.cmp(&other.distance)
	}
}

impl Hash for DistancePoint {
	fn hash<H: Hasher>(&self, state: &mut H) {
		self.point.hash(state);
	}
}

#[inline(always)]
fn tile_matches(tile: &MapTile, req: &PathingReqs) -> bool {
	req.can_walk
		.map(|should_walk| tile.can_walk == should_walk)
		.unwrap_or(true)
		&& req
			.can_see
			.map(|should_see| tile.can_see == should_see)
			.unwrap_or(true)
		&& req
			.can_fly
			.map(|should_fly| tile.can_fly == should_fly)
			.unwrap_or(true)
}

fn reduce_tiles(previous: Option<MapTile>, current: Option<MapTile>) -> Option<MapTile> {
	match previous {
		Some(tile) => match current {
			Some(current) => Some(MapTile {
				can_fly: tile.can_fly && current.can_fly,
				can_walk: tile.can_fly && current.can_walk,
				can_see: tile.can_fly && current.can_see,
				tile_group: 0,
			}),
			None => previous,
		},
		None => current,
	}
}

fn distance_between(a: &UVec2, b: &UVec2) -> usize {
	(a.x.abs_diff(b.x) + a.y.abs_diff(b.y)) as usize
}

impl LevelMap {
	pub fn get_adjacent(&self, initial: UVec2, reqs: PathingReqs) -> Vec<(UVec2, usize)> {
		let mut tiles = Vec::with_capacity(4);

		let right = self
			.layers
			.iter()
			.map(|layer| layer.get_tile_uvec2(uvec2(initial.x.saturating_add(1), initial.y)))
			.collect::<Vec<Option<MapTile>>>();
		let left = self
			.layers
			.iter()
			.map(|layer| layer.get_tile_uvec2(uvec2(initial.x.saturating_sub(1), initial.y)))
			.collect::<Vec<Option<MapTile>>>();
		let top = self
			.layers
			.iter()
			.map(|layer| layer.get_tile_uvec2(uvec2(initial.x, initial.y.saturating_add(1))))
			.collect::<Vec<Option<MapTile>>>();
		let bottom = self
			.layers
			.iter()
			.map(|layer| layer.get_tile_uvec2(uvec2(initial.x, initial.y.saturating_sub(1))))
			.collect::<Vec<Option<MapTile>>>();

		if let Some(tile) = left.into_iter().reduce(reduce_tiles).and_then(|f| f) {
			if tile_matches(&tile, &reqs) {
				tiles.push((uvec2(initial.x.saturating_sub(1), initial.y), 1));
			}
		}
		if let Some(tile) = right.into_iter().reduce(reduce_tiles).and_then(|f| f) {
			if tile_matches(&tile, &reqs) {
				tiles.push((uvec2(initial.x.saturating_add(1), initial.y), 1));
			}
		}
		if let Some(tile) = top.into_iter().reduce(reduce_tiles).and_then(|f| f) {
			if tile_matches(&tile, &reqs) {
				tiles.push((uvec2(initial.x, initial.y.saturating_add(1)), 1));
			}
		}
		if let Some(tile) = bottom.into_iter().reduce(reduce_tiles).and_then(|f| f) {
			if tile_matches(&tile, &reqs) {
				tiles.push((uvec2(initial.x, initial.y.saturating_sub(1)), 1));
			}
		}

		tiles
	}

	/// Find all tiles within a certain range that can be accessed based on
	/// the given requirements. Will not include the starting point in the
	/// returned list
	pub fn flood_fill(&self, start: UVec2, distance: usize, reqs: PathingReqs) -> Vec<UVec2> {
		let mut pending: BTreeSet<DistancePoint> =
			BTreeSet::from_iter(vec![DistancePoint::new(0, start)]);
		let mut found: HashSet<DistancePoint> = HashSet::new();

		while let Some(next) = pending.pop_first() {
			let adjacent = self.get_adjacent(next.point, reqs);
			for (point, adjacent_distance) in adjacent {
				let dp = DistancePoint::new(next.distance + adjacent_distance, point);
				if let Some(existing) = found.get(&dp) {
					if dp.distance < existing.distance {
						found.remove(&dp);
						found.insert(dp);
						pending.insert(dp);
					}
				} else if dp.distance < distance {
					found.insert(dp);
					pending.insert(dp);
				}
			}
		}

		found.into_iter().map(|dp| dp.point).collect()
	}

	/// Find the shortest path between two points that meets the requirements.
	/// Does not account for entity bottlenecks; to do so, use `custom_path_between`
	/// instead to provide costings that account for entities
	pub fn path_between(&self, start: UVec2, end: UVec2, reqs: PathingReqs) -> Vec<UVec2> {
		astar(
			&start,
			|&point| self.get_adjacent(point, reqs),
			|point| distance_between(point, &end),
			|&point| point == end,
		)
		.map(|(list, _)| list)
		.unwrap_or(Vec::new())
	}

	/// Find all paths that have the same shortest length between two points. Will take longer
	/// to find a result than simply fetching the first shortest path, but allows for more control
	/// over selection of the final path
	pub fn all_paths_between(
		&self,
		start: UVec2,
		end: UVec2,
		reqs: PathingReqs,
	) -> Vec<Vec<UVec2>> {
		astar_bag(
			&start,
			|&point| self.get_adjacent(point, reqs),
			|point| distance_between(point, &end),
			|&point| point == end,
		)
		.map(|(list, _)| list.collect())
		.unwrap_or(Vec::new())
	}
}