rustpather/

lib.rs

use std::collections::HashSet;
use std::collections::HashMap;

#[derive(Clone, Debug)]
struct Edge<T> {
	cost : i64,
	end : T
}

pub type Graph<T> = HashMap<T, Vec<Edge<T>>>;

pub type Node = (i64, i64);

pub fn to_fourway(grid : &Vec<Vec<u32>>) -> Graph<Node> {
	let mut graph : HashMap<(i64, i64), i64> = HashMap::new();

	for (y, row) in grid.iter().enumerate() {
		for (x, point) in row.iter().enumerate() {
			if *point > 0 {
				graph.insert((x as i64, y as i64), *point as i64);
			}
		}
	}

	let mut fullgraph : Graph<Node> = HashMap::new();
	for (point, _) in graph.iter() {
		let mut peers : Vec<Edge<Node>> = Vec::new();

		if graph.contains_key(&(point.0 - 1, point.1)) {
			peers.push(Edge{
				cost : graph[&(point.0 - 1, point.1)],
				end : (point.0 - 1, point.1)
			});
		}
		if graph.contains_key(&(point.0 + 1, point.1)) {
			peers.push(Edge{
				cost : graph[&(point.0 + 1, point.1)],
				end : (point.0 + 1, point.1)
			});
		}
		if graph.contains_key(&(point.0, point.1-1)) {
			peers.push(Edge{
				cost : graph[&(point.0, point.1 - 1)],
				end : (point.0, point.1 - 1)
			});
		}
		if graph.contains_key(&(point.0, point.1+1)) {
			peers.push(Edge{
				cost : graph[&(point.0, point.1 + 1)],
				end : (point.0, point.1 + 1)
			});
		}
		fullgraph.insert(*point, peers);
	}

	fullgraph
}

pub fn to_eightway(grid : &Vec<Vec<u32>>) -> Graph<Node> {
	let mut graph : HashMap<(i64, i64), i64> = HashMap::new();

	for (y, row) in grid.iter().enumerate() {
		for (x, point) in row.iter().enumerate() {
			if *point > 0 {
				graph.insert((x as i64, y as i64), *point as i64);
			}
		}
	}

	let mut fullgraph : Graph<Node> = HashMap::new();
	for (point, _) in graph.iter() {
		let mut peers : Vec<Edge<Node>> = Vec::new();

		if graph.contains_key(&(point.0 - 1, point.1)) {
			peers.push(Edge{
				cost : graph[&(point.0 - 1, point.1)],
				end : (point.0 - 1, point.1)
			});
		}
		if graph.contains_key(&(point.0 - 1, point.1 - 1)) {
			peers.push(Edge{
				cost : graph[&(point.0 - 1, point.1 - 1)],
				end : (point.0 - 1, point.1 - 1)
			});
		}

		if graph.contains_key(&(point.0 + 1, point.1)) {
			peers.push(Edge{
				cost : graph[&(point.0 + 1, point.1)],
				end : (point.0 + 1, point.1)
			});
		}
		if graph.contains_key(&(point.0 + 1, point.1 + 1)) {
			peers.push(Edge{
				cost : graph[&(point.0 + 1, point.1 + 1)],
				end : (point.0 + 1, point.1 + 1)
			});
		}

		if graph.contains_key(&(point.0, point.1-1)) {
			peers.push(Edge{
				cost : graph[&(point.0, point.1 - 1)],
				end : (point.0, point.1 - 1)
			});
		}
		if graph.contains_key(&(point.0+1, point.1-1)) {
			peers.push(Edge{
				cost : graph[&(point.0 + 1, point.1 - 1)],
				end : (point.0 + 1, point.1 - 1)
			});
		}

		if graph.contains_key(&(point.0, point.1+1)) {
			peers.push(Edge{
				cost : graph[&(point.0, point.1 + 1)],
				end : (point.0, point.1 + 1)
			});
		}
		if graph.contains_key(&(point.0-1, point.1+1)) {
			peers.push(Edge{
				cost : graph[&(point.0 - 1, point.1 + 1)],
				end : (point.0 - 1, point.1 + 1)
			});
		}
		fullgraph.insert(*point, peers);
	}

	fullgraph
}

pub fn heuristic(first : &Node, second : &Node) -> i64 {
	(first.0 - second.0).abs() + (first.1 - second.1).abs()
}

pub fn astar<T: Eq + std::hash::Hash + Clone + Copy, F: FnOnce(&T, &T) -> i64 + Copy>
(graph : &Graph<T>, start : T, end : T, heuristic: &F) -> Option<Vec<T>> {

	let mut openset : HashSet<T> = HashSet::new();
	let mut closedset : HashSet<T> = HashSet::new();
	let mut gscore : HashMap<T, i64> = HashMap::new();
	let mut fscore : HashMap<T, i64> = HashMap::new();
	let mut previous : HashMap<T, T> = HashMap::new();

	openset.insert(start);
	gscore.insert(start, 0);
	fscore.insert(start, heuristic(&start, &end));

	while openset.len() > 0 {
		let mut current = openset.iter().nth(0).unwrap().clone();

		for node in openset.iter() {
			let cost1 = gscore[&current] + heuristic(&current, &end);
			let cost2 = gscore[node] + heuristic(&node, &end);
			if cost2 < cost1 {
				current = node.clone();
			}
		}

		if current == end {
			let mut path : Vec<T> = vec![current];
			while previous.contains_key(&current) {
				current = previous[&current];
				path.push(current);
			}
			path.reverse();
			return Some(path);
		}

		openset.remove(&current);
		closedset.insert(current);

		let edges = graph[&current].clone();

		for edge in edges {
			if closedset.contains(&edge.end) {
				continue;
			}

			let potentialcost = gscore[&current] + edge.cost;

			if !openset.contains(&edge.end) {
				openset.insert(edge.end);
			}
			else if potentialcost >= gscore[&edge.end] {
				continue;
			}

			previous.insert(edge.end, current);
			gscore.insert(edge.end, potentialcost);
			fscore.insert(edge.end, potentialcost + heuristic(&edge.end, &end));
		}
	}
	None
}