/**
* A星尋路
 * @author BrightLi
 * @since 2020/4/18
 */
import Grid from "./Grid"
import Node from "./Node"
import BinaryHeap from "./BinaryHeap"

export default class AStar
{
	private _path:Array<Node>;
	private _clear:Array<Node>;

	constructor(){
	}

// 開始導路
	public findPath(grid:Grid):Array<Node>{
		let endNode=grid.endNode;
		if(!grid.isWallableAt(endNode.x,endNode.y)){
			return [];
		}
		var startNode=grid.startNode;
		startNode.g=0;
		startNode.f=0;
		var endX=grid.endNode.x;
		var endY=grid.endNode.y;
		var openList=new BinaryHeap(function(node){
			return node.f;
		});
		openList.push(startNode);
		var closeList:Array<Node>=[];
		while(!openList.isEmpty){
			var node=openList.pop();
			closeList.push(node);
			if(node.x == endNode.x && node.y == endNode.y){
				var result=this.backtrace(node);
// 清理節點
				for(node of closeList){
					node.clear();
				}
				return result;
			}
			var neighbors=grid.getNeighbors(node,1);
			for(var neighbor of neighbors){
				var closed=(closeList.indexOf(neighbor) != -1);
				if(closed){
					continue;
				}
				var x=neighbor.x;
				var y=neighbor.y;
				var ng=node.g+((x-node.x==0 || y-node.y==0) ?1:1.414);
				var opened=openList.contain(neighbor);
				if(!opened || ng<neighbor.g){
					neighbor.g=ng;
					neighbor.h=neighbor.h || Math.abs(x-endX)+Math.abs(y-endY);
					neighbor.f=neighbor.g+neighbor.h;
					neighbor.parent=node
					if(!opened){
						openList.push(neighbor);
					}else{
						openList.update(neighbor);
					}
				}
			}
		}
		return [];
	}
// 生成導航路徑
	private backtrace(node:Node):Array<Node>{
		var path=[node];
		while(node.parent){
			node=node.parent;
			path.push(node);
		}
		return path.reverse();
	}
}