package projectzombie.util.math.astar;
import java.util.ArrayList;
import java.util.List;

import gl_engine.vec.Vec2i;

class Node
{
	int x, y;
	int g, h, s;
	Node parent;
	
	public Node(Node parent, int x, int y, int g, int h, int s) {
		this.parent = parent;
		this.x = x;
		this.y = y;
		this.g = g;
		this.h = h;
		this.s = s;
	}
}

public class AStar
{
	AStarSearch search;
	
	Vec2i start;
	Vec2i goal;
	int radius;
	
	List<Node> open;
	List<Node> closed;
	
	Node now;
	Node found;
	
	public AStar(Vec2i start, int radius, AStarSearch search)
	{
		this.search = search;
		this.start = start;
		this.radius = radius;
	}
	
	public Vec2i[] getPath(Vec2i goal)
	{
		// Goal out of range
		if(this.posOutOfRange(goal.x, goal.y)) {
			return null;
		}
		
		// Start is a wall
		if(search.getWeight(start.x, start.y) == 100) {
			return null;
		}
		
		this.goal = goal;
		this.open = new ArrayList<Node>(radius*4);
		this.closed = new ArrayList<Node>(radius*4);
		
		now = new Node(null, start.x, start.y, 0, 0, 1);
		closed.add(now);
		
		addNeighboursToList();
		
		while(open.size() > 0)
		{
			// Found the goal
			if(found != null)
			{
				Node n = found;
				Vec2i[] path = new Vec2i[n.s];
				
				for(int i=0;n!=null;i++) {
					path[i] = new Vec2i(n.x, n.y);
					n = n.parent;
				}
				
				return path;
			}
			
			int nid = getEasiestNode();
			Node n = open.get(nid);
			
			open.remove(nid);
			closed.add(n);
			now = n;
			
			addNeighboursToList();
		}
		
		return null;
	}
	
	private boolean neighbourInList(List<Node> nodes, int x, int y) {
		for(Node n : nodes) {
			if(n.x == x && n.y == y) {
				return true;
			}
		}
		return false;
	}
	
	private boolean posOutOfRange(int x, int y) {
		return (
				x > start.x + radius ||
				x < start.x - radius ||
				y > start.y + radius || 
				y < start.y - radius);
	}
	
	private void addNeighboursToList()
	{
		int neighbours[] = {
				 1,  0,
				-1,  0,
				 0,  1,
				 0, -1
		};
		
		for(int i=0;i<neighbours.length;i+=2)
		{
			int x = now.x + neighbours[i + 0];
			int y = now.y + neighbours[i + 1];
			
			// Ignore out of range coords
			if(posOutOfRange(x, y)) {
				continue;
			}
			
			int weight = search.getWeight(x, y);
			
			// Ignore all solid walls
			if(weight == 100) {
				continue;
			}
			
			// Ignore already open/closed points
			if(neighbourInList(open, x, y) || neighbourInList(closed, x, y)) {
				continue;
			}
			
			// Create a new node
			Node node = new Node(now, x, y, g(weight, x, y), h(x, y), now.s + 1);
			
			if(x == goal.x && y == goal.y) {
				found = node;
			}
			
			open.add(node);
		}
	}
	
	private int g(int w, int x, int y) {
		return now.g + (100 / (100 - w));
	}
	
	private int h(int x, int y) {
		return Math.abs(x - goal.x) + Math.abs(y - goal.y);
	}
	
	private int getEasiestNode()
	{
		Node check = null;
		int id = -1;
		
		for(int i=0;i<open.size();i++)
		{
			Node n = open.get(i);
			
			if(check == null || n.g + n.h < check.g + check.h) {
				check = n;
				id = i;
			}
		}
		
		return id;
	}
}
