package sokobanevo.pathfinding;

import java.util.ArrayList;

/**
 * A* class
 * 
 * Class contains A* solution and pathfinding related functions
 * 
 * @author Payne
 */
public class Astar {
    
    /**
    * Computes shortest path between two tiles in map using A*.
    *    
    * Is using Minimum Heap for closed and open list for faster performance.
    *    
    * @param ignoreBoxes flag which decides, whether boxes in map will be ignored during A* processing or not.
    * @return -1 if cannot be reached else returns length of shortest path
    */
    public static int lengthOfPathBetweenTilesInMap(ArrayList<char[]> map, int fromX, int fromY, int toX, int toY, boolean ignoreBoxes){
        
        if(fromX == toX && fromY == toY){ //means we are at endpoint
            return 0; 
        }
        
        int pathLength = 0;
        MinHeap openList = new MinHeap();
        MinHeap closedList = new MinHeap();
        
        openList.add(new AstarNode(fromX, fromY, true, 0, Astar.manhattanDistanceFromTo(fromX, fromY, toX, toY)));
        
        boolean finished = false;
        AstarNode current;
        
        while(!finished){
            current = (AstarNode) openList.remove();
            closedList.add(current);
            
            if((current.getX() == toX) && (current.getY() == toY)){ 
                return current.getGCost();
            }

            // for all adjacent nodes:
            ArrayList<AstarNode> adjacentNodes;
            if(ignoreBoxes){
                 adjacentNodes = Astar.getAdjacentPassableNodesFromMapIgnoreBoxes(map, current, closedList);
            }else{
                 adjacentNodes = Astar.getAdjacentPassableNodesFromMap(map, current, closedList);
            }
            for(int i = 0; i < adjacentNodes.size(); i++){
                AstarNode currentAdj = adjacentNodes.get(i);
                int currentPosInOpenList = openList.containsAt(currentAdj);
                if(currentPosInOpenList == -1){  //node IS NOT in the open list
                    currentAdj.setHCost(Astar.manhattanDistanceFromTo(currentAdj.getX(), currentAdj.getY(), toX, toY));
                    openList.add(currentAdj);
                }else{ // node IS in the open list
                    if(((AstarNode)openList.getNodeAt(currentPosInOpenList)).getGCost() > current.getGCost() + 1){
                        ((AstarNode)openList.getNodeAt(currentPosInOpenList)).setGCost(current.getGCost() + 1);
                        openList.fixHeap();
                    }
                }
            }

            if(openList.size() == 0){
                return -1;
            }
        }
        
        return pathLength;
    }
    
    /**
    * Function, gets all (max 4) adjacent passable nodes for given node.
    *    
    * @return List of adjacent nodes.
    */
    public static ArrayList<AstarNode> getAdjacentPassableNodesFromMap(ArrayList<char[]> map, AstarNode node, MinHeap closedList){
        ArrayList<AstarNode> adjacents = new ArrayList<AstarNode>();
        
        if(node.getX() > 0 && (map.get(node.getY())[node.getX() - 1] == '.') || (map.get(node.getY())[node.getX() - 1] == ' ')){
            AstarNode newNode = new AstarNode(node.getX() - 1, node.getY(), true, node.getGCost() + 1, 0);
            if(closedList.containsAt(newNode) == -1){       
                adjacents.add(newNode);
            }
        }
        
        if(node.getX() < map.get(node.getY()).length - 1 && (map.get(node.getY())[node.getX() + 1] == '.') || (map.get(node.getY())[node.getX() + 1] == ' ')){
            AstarNode newNode = new AstarNode(node.getX() + 1, node.getY(), true, node.getGCost() + 1, 0);
            if(closedList.containsAt(newNode) == -1){       
                adjacents.add(newNode);
            }
        }
        
        if(node.getY() > 0 && (map.get(node.getY() - 1)[node.getX()] == '.') || (map.get(node.getY() - 1)[node.getX()] == ' ')){
            AstarNode newNode = new AstarNode(node.getX(), node.getY() - 1, true, node.getGCost() + 1, 0);
            if(closedList.containsAt(newNode) == -1){       
                adjacents.add(newNode);
            }
        }
        
        if(node.getY() < map.size() - 1 && (map.get(node.getY() + 1)[node.getX()] == '.') || (map.get(node.getY() + 1)[node.getX()] == ' ')){
            AstarNode newNode = new AstarNode(node.getX(), node.getY() + 1, true, node.getGCost() + 1, 0);
            if(closedList.containsAt(newNode) == -1){       
                adjacents.add(newNode);
            }
        }
        
        return adjacents;
    }
    
    
    /**
    * Function, gets all (max 4) adjacent passable nodes for given node, ignores boxes.
    *    
    * @return List of adjacent nodes, even if box is in them.
    */
    public static ArrayList<AstarNode> getAdjacentPassableNodesFromMapIgnoreBoxes(ArrayList<char[]> map, AstarNode node, MinHeap closedList){
        ArrayList<AstarNode> adjacents = new ArrayList<AstarNode>();
        
        if(node.getX() > 0 && map.get(node.getY())[node.getX() - 1] != '#'){
            AstarNode newNode = new AstarNode(node.getX() - 1, node.getY(), true, node.getGCost() + 1, 0);
            if(closedList.containsAt(newNode) == -1){       
                adjacents.add(newNode);
            }
        }
        
        if(node.getX() < map.get(node.getY()).length - 1 && map.get(node.getY())[node.getX() + 1] != '#'){
            AstarNode newNode = new AstarNode(node.getX() + 1, node.getY(), true, node.getGCost() + 1, 0);
            if(closedList.containsAt(newNode) == -1){       
                adjacents.add(newNode);
            }
        }
        
        if(node.getY() > 0 && map.get(node.getY() - 1)[node.getX()] != '#'){
            AstarNode newNode = new AstarNode(node.getX(), node.getY() - 1, true, node.getGCost() + 1, 0);
            if(closedList.containsAt(newNode) == -1){       
                adjacents.add(newNode);
            }
        }
        
        if(node.getY() < map.size() - 1 && map.get(node.getY() + 1)[node.getX()] != '#'){
            AstarNode newNode = new AstarNode(node.getX(), node.getY() + 1, true, node.getGCost() + 1, 0);
            if(closedList.containsAt(newNode) == -1){       
                adjacents.add(newNode);
            }
        }
        
        return adjacents;
    }
    
    
    /**
    * Function, calculates Manhattan distance from one tile of map to another.
    *    
    * @return computed Manhattan distance
    */
    public static int manhattanDistanceFromTo(int fromX, int fromY, int toX, int toY){
        return Math.abs(fromY - toY) + Math.abs(fromX - toX);
    }
    
}