package server.model.npcs.pathfinding;
import java.util.ArrayList;
import java.util.PriorityQueue;

import server.world.Tile;
import server.world.map.VirtualWorld;

/**
 * Simple Path Finder.
 * This one uses the most basic tree/network searching algorithm.
 * I also implemented a heuristic, so it is almost like a Greedy Best-First Search pathfinder.
 * Will have to evaluate the performance in the coming days.
 * @author Freddy
 *
 */

/**
 * TO-DO
 * Comment the rest of the code
 * CLIPPING AROUND FENCES (EG. FENCE NEAR VARROCK WILD)
 * Evaluate performance
 * Make optimizations
 *
 *
 */
public class SimplePath {

    //How many ms the path finder is allowed to find a path
    public static final int MS_ALLOWED = 1;

    public static Path findPath(Tile start, Tile finish) {
        //List of potential paths
        PriorityQueue<Path> paths = new PriorityQueue<Path>();
        //The starting path
        Path startingPath = new Path();
        startingPath.setTarget(finish);
        //Add the start node to the beginning of the starting path
        startingPath.getPath().addFirst(start);
        //Add the starting path to the paths list
        paths.add(startingPath);
        //Continue until there are no remaining open paths
        long startTime = System.currentTimeMillis(); //Make sure the pathfinder isn't taking too long.
        while(!paths.isEmpty() && System.currentTimeMillis() - startTime <= MS_ALLOWED) {
            //Poll for the path in the front of the list
            Path currentPathToExamine = paths.poll();
            //Check if this path has reached the target.
            if(currentPathToExamine.getPath().getLast().equals(finish)) {
                //If so, we have found our path.
                currentPathToExamine.getPath().removeFirst();
                return currentPathToExamine;
            }
            //Loop through all valid neighbors, extend path with each one, creating new valid paths.
            for(Tile adjacentValidTiles : getValidNeighbors(currentPathToExamine.getPath().getLast())) {
                //Check if the current path contains the adjacent tile
                if(!currentPathToExamine.getPath().contains(adjacentValidTiles)) {
                    //Extend the new path, add it to a new linked list object.
                    Path newPath = new Path();
                    newPath.setTarget(finish);
                    newPath.getPath().addAll(currentPathToExamine.getPath());
                    newPath.getPath().add(adjacentValidTiles);
                    //Add the new path to the main path list.
                    paths.add(newPath);
                }
            }
        }
        return startingPath;
    }

    public static ArrayList<Tile> getValidNeighbors(Tile home) {
        ArrayList<Tile> neighbors = new ArrayList<Tile>();
        //North
        neighbors.add(new Tile(home.x, home.y + 1, home.height));
        //West
        neighbors.add(new Tile(home.x - 1, home.y, home.height));
        //South
        neighbors.add(new Tile(home.x, home.y - 1, home.height));
        //East
        neighbors.add(new Tile(home.x + 1, home.y, home.height));
        //North West
        neighbors.add(new Tile(home.x - 1, home.y + 1, home.height));
        //South West
        neighbors.add(new Tile(home.x - 1, home.y - 1, home.height));
        //North East
        neighbors.add(new Tile(home.x + 1, home.y + 1, home.height));
        //South East
        neighbors.add(new Tile(home.x + 1, home.y - 1, home.height));

        //Create a list for the valid, clear tiles.
        ArrayList<Tile> validList = new ArrayList<Tile>();
        //Loop through all adjacent neighbors, only add the valid tiles to the list.
        for(Tile t : neighbors) {
            if(VirtualWorld.I(home.height, home.x, home.y, t.x, t.y, 0)) {
                validList.add(t);
            }
        }
        return validList;
    }
}