using System;
using System.Collections;
using System.Collections.Generic;

public class AStarHelper
{

	public static AStarPoint getGoalFromGoal(AStarPoint start, AStarPoint end, AStarNode[,] nodes, Craft craft)
	{
		List<AStarNode> nodesList = getNodesLine(end, start, nodes);
		while(nodesList.Count > 0)
		{
			AStarNode node = nodesList[0];
			nodesList.RemoveAt(0);

			if(node.IsWalkable(craft))
			{
				return new AStarPoint(node.X, node.Y);
			}
		}
		return start;
	}
	
	public static AStarPoint getGoalFromStart(AStarPoint start, AStarPoint end, AStarNode[,] nodes, Craft craft)
	{
		List<AStarNode> nodesList = getNodesLine(start, end, nodes);

		AStarNode oldNode = nodes[start.x, start.y];

		while(nodesList.Count > 0)
		{
			AStarNode node = nodesList[0];
			nodesList.RemoveAt(0);

			if(!node.IsWalkable(craft))
			{
				break;
			}
			oldNode = node;
		}
		return new AStarPoint(oldNode.X, oldNode.Y);
	}
	
	private static List<AStarNode> getNodesLine(AStarPoint start, AStarPoint end, AStarNode[,] nodes)
	{
		int stepCount = 0;
		int fraction;
		int nextX = start.x;
		int nextY = start.y;
		int deltaX = end.x - nextX;
		int deltaY = end.y - nextY;
		int stepX;
		int stepY;
		AStarNode node;
		List<AStarNode> nodeList = new List<AStarNode>();

		if(deltaX < 0) stepX = -1; else stepX = 1;
		if(deltaY < 0) stepY = -1; else stepY = 1;
		
		deltaX = Math.Abs(deltaX*2);
		deltaY = Math.Abs(deltaY*2);
		
		if(deltaX > deltaY)
		{
			fraction = deltaY*2-deltaX;
			while(nextX != end.x)
			{
				if(fraction >= 0)
				{
					nextY = nextY+stepY;
					fraction = fraction-deltaX;
				}
				nextX = nextX+stepX;
				
				node = nodes[nextX, nextY];
				if(node != null)
				{
					nodeList.Add(node);
				}
				
				fraction = fraction+deltaY;
				stepCount++;
			}
		}
		else
		{
			fraction = deltaX*2-deltaY;
			while(nextY != end.y)
			{
				if(fraction >= 0)
				{
					nextX = nextX+stepX;
					fraction = fraction-deltaY;
				}
				nextY = nextY + stepY;
				
				node = nodes[nextX, nextY];
				if(node != null)
				{
					nodeList.Add(node);
				}
				
				fraction = fraction+deltaX;
				stepCount++;
			}
		}
		return nodeList;
	}
}