package?com.yan.astar;

import?java.util.ArrayList;
import?java.util.List;
import?java.util.PriorityQueue;
import?java.util.Queue;

public?class?AStar
{
	public?final?static?int?BAR?=?1;?//?障礙值
	public?final?static?int?PATH?=?8;?//?路徑
	public?final?static?int?DIRECT_VALUE?=?1;?//?橫豎移動代價G
	
	Queue?openList?=?new?PriorityQueue（）;?//?open表，優先隊列（升序）
	List?closeList?=?new?ArrayList（）;	//?close表
	
	/**
	?*?開始算法
	?*/
	public?void?start（MapInfo?mapInfo）
	{
		if（mapInfo==null）?return;
		//?清表clear
		openList.clear（）;
		closeList.clear（）;
		//?開始搜索
		openList.add（mapInfo.start）;
		moveNodes（mapInfo）;
	}

	/**
	?*?移動當前結點
	?*/
	private?void?moveNodes（MapInfo?mapInfo）
	{
		while?（!openList.isEmpty（））
		{
			if?（isCoordInClose（mapInfo.end.coord））
			{
				drawPath（mapInfo.maps?mapInfo.end）;
				break;
			}
			Node?current?=?openList.poll（）;
			closeList.add（current）;
			addNeighborNodeInOpen（mapInfocurrent）;
		}
	}
	
	/**
	?*?在二維數組中繪制路徑（回溯法），并求得總代價，輸出逆向路徑
	?*/
	private?void?drawPath（int[][]?maps?Node?end）
	{
		if（end==null||maps==null）?return;
		System.out.println（“總代價：“?+?end.G）;
		System.out.print（“路徑逆序為:“）;
		while?（end?!=?null）
		{
			Coord?c?=?end.coord;
			maps[c.y][c.x]?=?PATH;
			end?=?end.parent;
			System.out.print（“（“+c.y+““+c.x+“）“+“<-“）;?
		}
		System.out.println（）;
	}

	/**
	?*?添加所有鄰結點到open表
	?*/
	private?void?addNeighborNodeInOpen（MapInfo?mapInfoNode?current）
	{
		int?x?=?current.coord.x;
		int?y?=?current.coord.y;
		//?左
		addNeighborNodeInOpen（mapInfocurrent?x?-?1?y?DIRECT_VALUE）;
		//?上
		addNeighborNodeInOpen（mapInfocurrent?x?y?-?1?DIRECT_VALUE）;
		//?右
		addNeighborNodeInOpen（mapInfocurrent?x?+?1?y?DIRECT_VALUE）;
		//?下
		addNeighborNodeInOpen（mapInfocurrent?x?y?+?1?DIRECT_VALUE）;
	}

	/**
	?*?添加一個鄰結點到open表
	?*/
	private?void?addNeighborNodeInOpen（MapInfo?mapInfoNode?current?int?x?int?y?int?value）
	{
		if?（canAddNodeToOpen（mapInfox?y））
		{
			Node?end=mapInfo.end;
			Coord?coord?=?new?Coord（x?y）;
			int?G?=?current.G?+?value;?//?計算鄰結點的G值
			Node?child?=?findNodeInOpen（coord）;
			if?（child?==?null）
			{
				int?H?=?calcH（end.coordcoord）;?//?計算H值
				if（isEndNode（end.coordcoord））
				{
					child=end;
					child.parent=current;
					child.G=G;
					child.H=H;
				}
				else
				{
					child?=?new?Node（coord?current?G?H）;
				}
				openList.add（child）;
			}
			else?if?（child.G?>?G）
			{
				child.G?=?G;
				child.parent?=?current;
				openList.add（child）;
			}
		}
	}

	/**
	?*?從Open列表中查找結點
	?*/
	private?Node?findNodeInOpen（Coord?coord）
	{
		if?（coord?==?null?||?openList.isEmpty（））?return?null;
		for?（Node?node?:?openList）
		{
			if?（node.coord.equals（coord））
			{
				return?node;
			}
		}
		return?null;
	}


	/**
	?*?計算H的估值：“曼哈頓”法，坐標分別取差值相加
	?*/
	private?int?calcH（Coord?endCoord?coord）
	{
		return?Math.abs（end.x?-?coord.x）
				+?Math.abs（end.y?-?c

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????303??2017-10-17?00:42??A-star\A-star\.classpath

?????文件????????382??2017-10-17?00:42??A-star\A-star\.project

?????文件????????598??2017-10-17?00:42??A-star\A-star\.settings\org.eclipse.jdt.core.prefs

?????文件???????4638??2017-10-18?13:17??A-star\A-star\bin\com\yan\astar\AStar.class

?????文件????????602??2017-10-17?15:49??A-star\A-star\bin\com\yan\astar\Coord.class

?????文件????????586??2017-10-17?15:49??A-star\A-star\bin\com\yan\astar\MapInfo.class

?????文件???????1088??2017-10-17?15:49??A-star\A-star\bin\com\yan\astar\Node.class

?????文件???????1655??2017-10-24?18:11??A-star\A-star\bin\com\yan\astar\Test.class

?????文件???????4114??2017-10-18?13:17??A-star\A-star\src\com\yan\astar\AStar.java

?????文件????????361??2017-10-17?15:49??A-star\A-star\src\com\yan\astar\Coord.java

?????文件????????418??2017-10-17?15:49??A-star\A-star\src\com\yan\astar\MapInfo.java

?????文件????????664??2017-10-17?15:49??A-star\A-star\src\com\yan\astar\Node.java

?????文件????????899??2017-10-24?18:11??A-star\A-star\src\com\yan\astar\Test.java

?????文件???????4114??2017-10-18?13:17??A-star\AStar.java

?????文件????????361??2017-10-17?15:49??A-star\Coord.java

?????文件????????418??2017-10-17?15:49??A-star\MapInfo.java

?????文件????????664??2017-10-17?15:49??A-star\Node.java

?????文件????????899??2017-10-24?18:11??A-star\Test.java

?????目錄??????????0??2017-12-22?11:44??A-star\A-star\bin\com\yan\astar

?????目錄??????????0??2017-12-22?11:44??A-star\A-star\src\com\yan\astar

?????目錄??????????0??2017-12-22?11:44??A-star\A-star\bin\com\yan

?????目錄??????????0??2017-12-22?11:44??A-star\A-star\src\com\yan

?????目錄??????????0??2017-12-22?11:44??A-star\A-star\bin\com

?????目錄??????????0??2017-12-22?11:44??A-star\A-star\src\com

?????目錄??????????0??2017-12-22?11:44??A-star\A-star\.settings

?????目錄??????????0??2017-12-22?11:44??A-star\A-star\bin

?????目錄??????????0??2017-12-22?11:44??A-star\A-star\src

?????目錄??????????0??2017-12-22?11:44??A-star\A-star

?????目錄??????????0??2017-12-22?11:44??A-star

-----------?---------??----------?-----??----

............此處省略2個文件信息