package com.pesets.game.map;

import java.awt.Point;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.Queue;

import com.badlogic.gdx.math.Vector2;
import com.pesets.game.Map;

public class PassageMap {
	private int width, height;
	private BitSet passage;
	
	PassageMap(int width, int height)
	{
		this.width = width;
		this.height = height;
		passage = new BitSet(width * height);
	}
	
	public int getWidth() {
		return width;
	}
	public int getHeight() {
		return height;
	}
	
	public boolean isCanPass(int x, int y)
	{
		if (x < 0 || y < 0 || x >= width || y >= height)
			return false;
		return passage.get(x + y * width);
	}
	
	public void setPassage(int x, int y, boolean canPass)
	{
		int num = x + y * width;
		if (canPass)
			passage.set(num);
		else
			passage.clear(num);
	}
	
	public Vector2 getRealCoords(int x, int y)
	{
		return new Vector2((x + 0.5f) * Map.CellSize, (y + 0.5f) * Map.CellSize);
	}
	
	public LinkedList<Vector2> findPath(int x1, int y1, int x2, int y2)
	{
		LinkedList<Vector2> result = new LinkedList<Vector2>();
		
		Queue<Point> points = new LinkedList<Point>();
		int[] weights = new int[width * height];
		points.add(new Point(x1, y1));
		weights[x1 + y1 * width] = 1;
		int iterations = 0;

		MainCycle: while (points.isEmpty() == false)
		{
			iterations++;
			Point p = points.poll();
			int w = weights[p.x + p.y * width];
			
			for (int i = -1; i <= 1; i++)
				for (int j = -1; j <= 1; j++)
				{
					if ((i == 0) ^ (j == 0))
					{
						if (isCanPass(p.x + i, p.y + j) == false) continue;
						int windex = p.x + i + (p.y + j) * width;
						if (weights[windex] <= w + 1 && weights[windex] != 0) continue;
						weights[windex] = w + 1;
						if (p.x + i == x2 && p.y + j == y2) break MainCycle;
						points.add(new Point(p.x + i, p.y + j));
					}
				}
			if (iterations > 1000) break;
		}
		
		if (weights[x2 + y2 * width] == 0) return result;
		
		int x = x2;
		int y = y2;
		iterations = 0;
		while (x != x1 || y != y1)
		{
			iterations++;
			int nx = -1;
			int ny = -1;
			for (int i = -1; i <= 1; i++)
				for (int j = -1; j <= 1; j++)
				{
					if ((i == 0) ^ (j == 0))
					{
						if (isCanPass(x + i, y + j) == false) continue;
						if (weights[x + i + (y + j) * width] <= 0) continue;
						if (nx == -1 || weights[x + i + (y + j) * width] < weights[nx + ny * width])
						{
							nx = x + i;
							ny = y + j;
						}
					}
				}
			
			if (nx == -1)
			{
				break;
			}
			result.addFirst(getRealCoords(nx, ny));
			weights[x + y * width] = 0;
			x = nx;
			y = ny;
			if (iterations > 1000)
			{
				result.clear();
				return result;
			}
		}
		result.add(getRealCoords(x2, y2));

		
		return result;
	}
}
