tfloodfill.java

Thalmann算法的java实现。有详细注释。

/**
 *使用FloodFill算法进行路径规划
 *
 **/

package page;

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

public class TFloodFill 
{
	public  TFloodFill()
	{
	}
	
	//构造函数
	public  TFloodFill(JButton[][] b,int[][] environ,int MaxM,int MaxN,int startX,int startY,int goalX,int goalY)
	{	
		//如果目标位置就是初始位置，则直接输出说明语句即可，无需进行路径规划。
		if(startX==goalX&&startY==goalY)   
		{
			System.out.println("the goal cell is the start cell, so do not need to planning path!");
		}
		//如果目标位置不是初始位置，则进行如下的路径规划
		else    
		{
			LinkedList open=new LinkedList();
			LinkedList closed=new LinkedList();

			//处理初始节点：创建初始位置对应的节点，并将该节点加入open表中	
			TNodes now=new TNodes(startX,startY,1);		
			open.add(now);
			environ[startX][startY]=1;

			int layer=0,nowx=0,nowy=0;
			int x=0,y=0;
			now=(TNodes)open.get(0);
			layer=now.getLayer();
			nowx=now.getX();
			nowy=now.getY();
			layer++;

			//从初始单元格开始标号，到目标单元格标示后停止
			while(environ[goalX][goalY]==0)
			{
				open.remove(now);
				closed.add(now);

				//处理该节点的八个邻近节点
				
				//处理该节点上一行的邻近节点
				x=nowx-1;   
				if(x>=0&&x<MaxM)  //如果上一行存在，则对其上一行的邻近节点进行判断
				{
					y=nowy-1;
					if(y>=0&&y<MaxN) //如果上左节点存在，则对其进行判断
					{
						if(environ[x][y]==0)
						{
							environ[x][y]=layer;
							open.add(new TNodes(x,y,layer));
						}
					}
					y=nowy;
					if(environ[x][y]==0)
					{
						environ[x][y]=layer;
						open.add(new TNodes(x,y,layer));
					}
					y=nowy+1;
					if(y>=0&&y<MaxN)  
					{
						if(environ[x][y]==0)
						{
							environ[x][y]=layer;
							open.add(new TNodes(x,y,layer));
						}
					}
				}//该节点上一行的邻近节点处理完毕

				//处理该节点同一行的两个单元格
				x=nowx;  
				y=nowy-1;
				if(y>=0&&y<MaxN)  
				{
					if(environ[x][y]==0)
					{
						environ[x][y]=layer;
						open.add(new TNodes(x,y,layer));
					}
				}
				y=nowy+1;
				if(y>=0&&y<MaxN)  
				{
					if(environ[x][y]==0)
					{
						environ[x][y]=layer;
						open.add(new TNodes(x,y,layer));
					}
				}//该节点同一行的两个单元格处理完毕

				 //处理该节点下一行的邻近节点
				x=nowx+1;  
				if(x>=0&&x<MaxM)  //如果下一行存在，则对其上一行的邻近节点进行判断
				{
					y=nowy-1;
					if(y>=0&&y<MaxN)  //如果下左节点存在，则对其进行判断
					{
						if(environ[x][y]==0)
						{
							environ[x][y]=layer;
							open.add(new TNodes(x,y,layer));
						}
					}
					y=nowy;
					if(environ[x][y]==0)
					{
						environ[x][y]=layer;
						open.add(new TNodes(x,y,layer));
					}
					y=nowy+1;
					if(y>=0&&y<MaxN)  
					{
						if(environ[x][y]==0)
						{
							environ[x][y]=layer;
							open.add(new TNodes(x,y,layer));
						}
					}
				}//该节点下一行的邻近节点处理完毕

				now=(TNodes)open.get(0);
				layer=now.getLayer();
				nowx=now.getX();
				nowy=now.getY();
				layer++;

			}//while(environ[goalX][goalY]==0)
			

			//将open表中的所有节点（节点已标示，但是其子节点还没有标示）转移到closed表中
			while(open.size()>0)
			{
				now=(TNodes)open.get(0);
				closed.add(now);
				open.remove(now);
			}			
			System.out.println("the number of extended nodes is:   "+closed.size());			

			//回溯，规划路径
			nowx=goalX;
			nowy=goalY;
			now=(TNodes)(new TChooseClosed( closed, nowx,nowy).getNode());  //找出目标节点，now为其引用			
			b[nowx][nowy].setForeground(Color.green);
			int pathnumber=1;
			
			while(nowx!=startX||nowy!=startY)
			{
				//将节点的八个邻近单元格对应的节点加入open表中
				new TChange(nowx,nowy,MaxM,MaxN,environ,open,closed); 
					
				//对open表中，该节点的邻近单元进行比较，找出路径规划选定的节点
				now=(TNodes)(new TOpenChoose(open,now).getNode());				
				nowx=now.getX();
				nowy=now.getY();
				b[nowx][nowy].setForeground(Color.green);
				pathnumber++;
				open.clear();
			}		

			//在环境图中显示路径长度
			for(int i=0;i<MaxM;i++)
			{
				for(int j=0;j<MaxN;j++)
				{
					b[i][j].setText(""+environ[i][j]);
				}
			}
			System.out.println("the length of the planned path is:   "+pathnumber);

		}//else=!if(startX==goalX&&startY==goalY) 
	}//构造函数结束
}//NFloodFill类定义结束