package jp.ac.nii.icpc2010.players;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Random;

import jp.ac.nii.icpc2010.players.BasePlayer;
import jp.ac.nii.icpc2010.playfield.FieldDirection;
import jp.ac.nii.icpc2010.playfield.IPlayField;

/**
 * APlayer has two basic behaviours:
 *  1) Try to chase the enemy player and to get slightly ahead of him (cutting him off)
 *  2) Hug walls or other non-free spaces (if the enemy player is unreachable)
 * 
 * @author Adrian
 *
 */
public class APlayer extends BasePlayer {
	// configurable lookahead amount
	private final static int GET_AHEAD_TURNS = 3;

	// for BFS
	Double[][] matrix;

	// information from last turn
	FieldDirection lastDirection;
	private Point lastEnemyPosition = new Point();

	public APlayer(int id, IPlayField playField) {
		super(id, playField);
	}

	public FieldDirection getInput() {
		// is there any possible move?
		Point ownPos = new Point(getX(), getY());
		if (!isFree(ownPos.x-1, ownPos.y) && !isFree(ownPos.x+1, ownPos.y)
				&& !isFree(ownPos.x, ownPos.y-1) && !isFree(ownPos.x, ownPos.y + 1)) {
			return lastDirection;
		}
		
		// default direction that is save
		FieldDirection decision = getSafeDirs(ownPos.x, ownPos.y).get(0);

		// pick enemy position
		Point enemyPos = getPosition(getEnemyIds().get(0));

		// predict next enemy position in a number of turns
		int targetX = enemyPos.x + (enemyPos.x - lastEnemyPosition.x) * GET_AHEAD_TURNS;
		int targetY = enemyPos.y + (enemyPos.y - lastEnemyPosition.y) * GET_AHEAD_TURNS;

		// try to get to that position
		breadthFirstSearch(targetX, targetY);

		// try to chase player
		boolean found = false;
		double bestDist = matrix[ownPos.x][ownPos.y];
		for (FieldDirection possibleDirection : getSafeDirs(ownPos.x, ownPos.y)) {
			int[] pred = getPlayField().stepOne(ownPos.x, ownPos.y, possibleDirection);
			double dist = matrix[pred[0]][pred[1]];
			if (dist < bestDist) {
				found = true;
				bestDist = dist;
				decision = possibleDirection;
			} else if (dist == bestDist && possibleDirection == lastDirection && new Random().nextDouble() <= 0.25) {
				decision = possibleDirection;
			} else if (dist == bestDist && possibleDirection != lastDirection && new Random().nextDouble() <= 0.25) {
				decision = possibleDirection;
			}
		}
		/*
		if (om.isLoggingOn()) {
			System.out.println("dist: " + bestDist);
		}
		*/
		
		// hug wall (or other non-free spaces)
		if (!found) {
			for (FieldDirection possibleDirection : getRandomDirs()) {
				int[] pred = getPlayField().stepOne(ownPos.x, ownPos.y, possibleDirection);
				if (!isFree(pred[0], pred[1])) {
					continue;
				}
				boolean foundNonFreeSpace = false;
				for (int[] adj : getAdjacentPos(pred[0], pred[1])) {
					if (isWall(adj[0], adj[1])) {
						foundNonFreeSpace = true;
						break;
					}
				}
				for (int[] adj : getAdjacentPos(pred[0], pred[1])) {
					if (!isFree(adj[0], adj[1])) {
						foundNonFreeSpace = true;
						break;
					}
				}
				if (foundNonFreeSpace) {
					decision = possibleDirection;
					break;
				}
			}
		}

		lastEnemyPosition = enemyPos;
		lastDirection = decision;

		return decision;
	}
	
	private void breadthFirstSearch(int x, int y) {
		initBreadthFirstSearch();
		breadthFirstSearch(x, y, 0);		
	}

	private void initBreadthFirstSearch() {
		matrix = new Double[getPlayField().getWidth()][];
		for (int i = 0; i < getPlayField().getWidth(); i++) {

			matrix[i] = new Double[getPlayField().getHeight()];
			for (int j = 0; j < matrix[i].length; j++) {
				if (!isFree(i, j))
					matrix[i][j] = Double.POSITIVE_INFINITY;
				else
					matrix[i][j] = -1.0;
			}
		}
	}

	private void breadthFirstSearch(int x, int y, double depth) {
		if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length) {
			if (depth > 0 && matrix[x][y] == Double.POSITIVE_INFINITY) {
				// not reachable
				return;
			}
			if (matrix[x][y] >= 0 && matrix[x][y] <= depth) {
				// already searched before
				return;
			}
			matrix[x][y] = depth;
		} else if (depth >= GET_AHEAD_TURNS) {
			return;
		}
		depth++;
		breadthFirstSearch(x, y-1, depth);
		breadthFirstSearch(x, y+1, depth);
		breadthFirstSearch(x-1, y, depth);
		breadthFirstSearch(x+1, y, depth);
	}
}
