/**
 * 使用改進(jìn)的Dijkstra算法進(jìn)行路徑規(guī)劃，每次選出一個(gè)到初始節(jié)點(diǎn)距離最短的節(jié)點(diǎn)
 *
**/


package page;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;       //LinkedList

public class BDijkstra 
{
	public static int comparenumber=0;    //用于保存該算法所進(jìn)行的比較次數(shù)
	
	//無(wú)參構(gòu)造函數(shù)
	public  BDijkstra()
	{		
	}
	
	//有參構(gòu)造函數(shù)
	public  BDijkstra(JButton[][] b,int[][] environ,int MaxM,int MaxN,int startX,int startY,int goalX,int goalY)
	{	
		//如果目標(biāo)位置就是初始位置，則直接輸出說(shuō)明語(yǔ)句即可，無(wú)需進(jìn)行路徑規(guī)劃。
		if(startX==goalX&&startY==goalY)   
		{
			System.out.println("the goal cell is the start cell, so do not need to planning path!");
		}
		//如果目標(biāo)位置不是初始位置，則進(jìn)行如下的路徑規(guī)劃
		else    
		{
			//給出算法所用變量的說(shuō)明			
			LinkedList open=new LinkedList();    //保存擴(kuò)展到的節(jié)點(diǎn)
			LinkedList closed=new LinkedList();  //保存規(guī)劃過(guò)的節(jié)點(diǎn)

			int nowx=0,nowy=0;      //目前正在處理單元格的位置
			int nowdis=0;           //目前正在處理單元格到初始單元格的距離

			//處理初始單元格，創(chuàng)建其對(duì)應(yīng)的節(jié)點(diǎn)加入closed表中，該節(jié)點(diǎn)的父節(jié)點(diǎn)指向自身
			BNodes now=new BNodes(startX,startY,startX,startY,0);		
			closed.add(now);
			comparenumber++;

			nowx=startX;
			nowy=startY;
			nowdis=0;

			int x=nowx-1;   //目前正在處理的單元的鄰近單元位置
			int y=0; 
			int distance1=nowdis+10;  //目前正在處理單元的鄰近單元到初始節(jié)點(diǎn)的距離
			int distance2=nowdis+14;

			//求出算法開(kāi)始時(shí)間
			double h1=new java.util.Date().getTime();
			
			//規(guī)劃到目標(biāo)節(jié)點(diǎn)之前執(zhí)行如下循環(huán)
			while(nowx!=goalX||nowy!=goalY)
			{
				//處理上一行的三個(gè)鄰近單元	
				if(x>=0&&x<MaxM)  //如果上一行存在，則對(duì)其上一行的鄰近節(jié)點(diǎn)進(jìn)行判斷
				{
					y=nowy-1;	
					if(y>=0&&y<MaxN)  //如果該節(jié)點(diǎn)存在
					{
						comparenumber++;
						new BExtendDemo (environ,x,y,distance2,open,nowx,nowy);
					}
					y=nowy;
					comparenumber++;
					new BExtendDemo (environ,x,y,distance1,open,nowx,nowy);	
					y=nowy+1;	
					if(y>=0&&y<MaxN)  //如果該節(jié)點(diǎn)存在
					{
						comparenumber++;
						new BExtendDemo (environ,x,y,distance2,open,nowx,nowy);
					}
				}
				
				//處理同一行的兩個(gè)節(jié)點(diǎn)
				x=nowx;			
				y=nowy-1;
				if(y>=0&&y<MaxN)  //如果該節(jié)點(diǎn)存在
				{
					comparenumber++;
					new BExtendDemo (environ,x,y,distance1,open,nowx,nowy);
				}
				y=nowy+1;
				if(y>=0&&y<MaxN)  //如果該節(jié)點(diǎn)存在
				{
					comparenumber++;
					new BExtendDemo (environ,x,y,distance1,open,nowx,nowy);
				}
				
				//處理下一行的三個(gè)鄰近節(jié)點(diǎn)
				x=nowx+1;
				if(x>=0&&x<MaxM)  //如果下一行存在，則對(duì)其上一行的鄰近節(jié)點(diǎn)進(jìn)行判斷
				{
					y=nowy-1;	
					if(y>=0&&y<MaxN)  //如果該節(jié)點(diǎn)存在
					{
						comparenumber++;
						new BExtendDemo (environ,x,y,distance2,open,nowx,nowy);
					}
					y=nowy;
					comparenumber++;
					new BExtendDemo (environ,x,y,distance1,open,nowx,nowy);	
					y=nowy+1;	
					if(y>=0&&y<MaxN)  //如果該節(jié)點(diǎn)存在
					{
						comparenumber++;
						new BExtendDemo (environ,x,y,distance2,open,nowx,nowy);
					}
				}				
				
				//選出open表中路徑最短者
			    now=(BNodes)new BChooseOpen(open).getNode();
			    nowx=now.getX();     
				nowy=now.getY();
				nowdis=now.getDistance();				
				distance1=nowdis+10;  //目前正在處理單元的鄰近單元到初始節(jié)點(diǎn)的距離
				distance2=nowdis+14;
				x=nowx-1;
				y=nowy;
				
				b[nowx][nowy].setText(""+environ[nowx][nowy]);
								
				open.remove(now);
				closed.add(now);
			}

			double h2=new java.util.Date().getTime();
			System.out.println("該程序的運(yùn)行時(shí)間為： "+(h2-h1)+"  毫秒");

			/*for(int i=0;i<20;i++)
			{
				for(int j=0;j<20;j++)
					System.out.print("	"+b[i][j].getText());
				System.out.println();
			}	*/
						
		
			System.out.println("the number of the planned nodes  is: "+closed.size());
			System.out.println("the number of the extended nodes is: "+(open.size()+closed.size()));
			System.out.println("the number of the considered nodes is:   "+comparenumber);

		}//else==!(startX==goalX&&startY==goalY)
	}//構(gòu)造函數(shù)
}//類定義