var AStarPath = new Class({
	initialize: function(startZone,endZone){
		this.startZone = startZone;
		this.endZone = endZone;
		this.openedList = [];
		this.closedList = [];
	},
    computeAStarPath: function(){
        this.path=[];
        this.startNode = new AStarNode(this.startZone);
        this.endNode = new AStarNode(this.endZone);
        this.openedList.push(this.startNode);
        var adjacentNodes = this.startNode.getFreeNeighbourNodes();
        for(var i=0;i<adjacentNodes.length;i++){
            adjacentNodes[i].setParent(this.startNode);
            adjacentNodes[i].initScoreAndCosts(this.endNode);
            this.openedList.push(adjacentNodes[i]);
        }
        this.closedList.push(this.openedList.shift());
        this.cycleOpenedList();
        if($defined(this.endNode.parent)){
            //this.endNode.zone.colorZone();
            this.path.unshift(this.endNode);
            this.extractPath();
        }
        return this.path;
    },
    extractPath: function(){
        //this.path[0].parent.zone.colorZone();
        this.path.unshift(this.path[0].parent);
        if(!$defined(this.path[0].parent))
            return;
        else{
            if(!this.path[0].parent.hasSameZoneAsNode(this.startNode))
                this.extractPath();
        }
    },
    cycleOpenedList: function(){
        
        while(this.openedList.length>0){

            // find the node with the lowest F and name it currentNode
            var currentNode = null;
            var currentNodePosition = 0;
            for(var i=0;i<this.openedList.length;i++){
                if($defined(currentNode)){
                    if(this.openedList[i].F<=currentNode.F){
                        currentNode = this.openedList[i];
                        currentNodePosition = i;
                    }
                } else {
                    currentNode = this.openedList[i];
                    currentNodePosition = i;
                }
            }
            // found the currentNode by here
            this.closedList.push(currentNode);
            if(currentNode.hasSameZoneAsNode(this.endNode)){
                this.endNode=currentNode;
                break;
            }
            this.openedList.splice(currentNodePosition,1);
            var adjacentNodes = currentNode.getFreeNeighbourNodes();
            for(var i=0;i<adjacentNodes.length;i++){
                var nodeExistsInClosedList = false;
                for(var j=0;j<this.closedList.length;j++){
                    if(adjacentNodes[i].hasSameZoneAsNode(this.closedList[j])){
                        nodeExistsInClosedList=true;
                        break;
                    }
                }
                if(nodeExistsInClosedList)
                    continue;
                if(!adjacentNodes[i].zone.isWalkable())
                    continue;
                var nodeExistsInOpenedList = false;
                for(var j=0;j<this.openedList.length;j++){
                    if(adjacentNodes[i].hasSameZoneAsNode(this.openedList[j])){
                        nodeExistsInOpenedList=true;
                        adjacentNodes[i]=this.openedList[j];
                        break;
                    }
                }
                if(nodeExistsInOpenedList){
                    var newG = currentNode.G + game.standardCost;
                    if(newG>=adjacentNodes[i].G){

                    } else {
                        adjacentNodes[i].setParent(currentNode);
                        adjacentNodes[i].initScoreAndCosts(this.endNode);
                    }
                } else {
                    adjacentNodes[i].setParent(currentNode);
                    adjacentNodes[i].initScoreAndCosts(this.endNode);
                    this.openedList.push(adjacentNodes[i]);
                }
            }
        }
    }
});

var AStarNode = new Class({
	initialize: function(zone){
		this.zone = zone;
		this.parent = null;
        this.F = 0;
        this.G = 0;
        this.H = 0;
	},
    hasSameZoneAsNode: function(node){
       var result = false;
       if(this.zone.x == node.zone.x && this.zone.y == node.zone.y)
           result = true;
       return result;
    },
	setParent: function(node){
		this.parent = node;
	},
	getFreeNeighbourNodes: function(){
		var neighbourNodes = [];
        var nodeX = this.zone.x;
        var nodeY = this.zone.y;
		if(nodeX>=game.standardWidth){
            var zone = game.zones[(nodeX-game.standardWidth)/game.standardWidth][nodeY/game.standardHeight];
            if(zone.isWalkable())
                neighbourNodes.push(new AStarNode(zone));
		}
		if(nodeY>=game.standardHeight){
			var zone = game.zones[nodeX/game.standardWidth][(nodeY-game.standardHeight)/game.standardHeight];
            if(zone.isWalkable())
                neighbourNodes.push(new AStarNode(zone));
		}
		if(nodeX<game.worldWidth-game.standardWidth){
			var zone = game.zones[(nodeX+game.standardWidth)/game.standardWidth][nodeY/game.standardHeight];
            if(zone.isWalkable())
                neighbourNodes.push(new AStarNode(zone));
		}
		if(nodeY<game.worldHeight-game.standardHeight){
			var zone = game.zones[nodeX/game.standardWidth][(nodeY+game.standardHeight)/game.standardHeight];
            if(zone.isWalkable())
                neighbourNodes.push(new AStarNode(zone));
		}
		return neighbourNodes;
	},
	computeHCost: function(endNode){
        // maybe it will be good to diff the endzone against the real position of the hero in this.zone, than against the x and y of the this.zone
        this.H = parseInt(Math.sqrt(Math.pow(endNode.zone.x-this.zone.x,2)+Math.pow(endNode.zone.y-this.zone.y,2)));
	},
    computeGCost: function(){
        if($defined(this.parent))
            this.G = game.standardCost+this.parent.G;
        else {
            debugger;
        }
    },
    computeFScore: function(){
        this.F = this.G + this.H;
    },
    initScoreAndCosts: function(endNode){
        this.computeHCost(endNode);
        this.computeGCost();
        this.computeFScore();
    }
});




/*
 * the main problem to solve with Astar is to find the zones that make up the fastest route between a start zone and
 * a destination zone, avoiding obstacles along the way.
 * the algorithm is like this:
 * given data: startNode, endNode
 * every node has a cost of walking through it. here in bomberman all free nodes have the same cost
 * we could make walls and fake walls and bombActiveZones to have much higher costs just to avoid them, or not adding them in the openList
 * by default - save some computation
 * given methods: computeHcost and computeGcost
 * computeHcost of a node to the endNode: returns the distance from the center of the currentNode to the center of the endNode
 * and we know them both sqrt(dx*dx+dy*dy)
 * computeGcost of a node to the startNode: returns the walking cost of the currentNode to the startingNode by traversing the parentNodes
 * of the currentNode recursively.
 * computeFcost : the sum of H and G [F = G + H]
 *
 * we create two arrays of data: openList and closedList
 * we add the startNode to the openList array.
 * then we search for the adjacent nodes of this startingNode
 * after we find them, we set their parent to be the startingNode
 * remove startingNode from the openList and add it to the closedList
 * computeH,G,Fcost for every Node in the open list
 * iterate through them and pick the one with lowest Gcost. this will be out currentNode
 * if there are more nodes with the same lowest Fcost, choose the last one added to the openlist.
 * add the currentNode to the closedList
 * check the adjacent of this currentNode [which is now in the closedList] and add them to the openList
 * compute H,G,F cost for every new Node added in the open list
 * if a newly found adjacent Node is already in the openedList, check the Gcost of that node . if it is lower than what has been computed
 * at this level , then we do nothing. if not, i.e. the Gcost of the node is higher than the newly computed cost, then update the F and the G cost of that node
 * and set its parent to the currentNode.
 * and so on.
 * [NO: in bomberman however the F = H because G is the same for all free nodes. :NO]
 * the G has 2 values in bomberman: one for a free zone and a bigger one for a bombActiveZone.
 *
 * so the algorithm is like this:
 * 1. add startNode to the openedList, find the adjacentNodes, set their parent to be the startNode, compute F,H,G costs for them,
 * add them to openedList, put startNode to the closedList
 * repeat the following:
 * ---------------------------------------------------------------
 * look for the node with the lowest F score. name it currentNode.
 * move it to the closedList.
 * find the adjacentNodes of this currentNode.
 * for each of them do {
 *      if it is not walkable, if it is in the closedList, ignore it.
 *      else {
 *              if it is not in the openedList add it there. set its parent to be the currentNode. compute F,H,G for it.
 *              if it is in the openedList already, check its already computed G cost with the one you compute by taking into account
 *              walking through the currentNode. if the  newly G cost is higher do nothing for the checkedNode. it it is lower, then set its parent to
 *              the currentNode amd recompute F and G for it.
 *      }
 *      stop when:
 *      you add the target square to the closedList or openedList is empty and you haven't reached the targetNode.
 *      it means there is no path.
 * }
 * ---------------------------------------------------------------
 * 3. compute the path by going from the endNode recursively thorugh its parents untill
 * you get to the startNode. that is the path to follow.
 * 
 */