sketcher.java

最短寻路算法

import javax.swing.JApplet;
import java.awt.Component;

import java.awt.Color;

import java.awt.Container;
import java.awt.Graphics;
import java.awt.Point;
import java.util.Stack; 
                      
import java.awt.Rectangle;
                
import java.awt.event.MouseEvent;    

import javax.swing.event.MouseInputAdapter;    
import java.lang.Math; 
import	java.lang.Thread;

public class Sketcher extends JApplet {
	int tileX,tileY;
	int COLS=100;
	int ROWS=55;
	int [][] map=new int[COLS][ROWS];
	
	int count=0;
	int serchNum=0;
	int [][] trade=new int[COLS][ROWS];
	Math math;
	TilePane tilePane;
	public void init() {
		tilePane = new TilePane();
		Container content = getContentPane(); 
		content.add(tilePane);            
	}
		
	class TilePane extends Component {
			int a,b;
			int count=0;
			Point st=null;   
			SearchPath spath=new SearchPath();
			Stack<NODE> deleteNode=new Stack<NODE>();
		 public TilePane() {
   			 MouseHandler handler = new MouseHandler();       
   			 addMouseListener(handler);                       
    			 addMouseMotionListener(handler);              
  			}
		public void paint(Graphics g) {
			g.setColor(Color.BLACK); 
			g.fill3DRect(10,10,(COLS*10-20),(ROWS*10-20),true); 
			g.setColor(Color.orange); 
			g.drawString("A*", 60, 250); // Draw some text
			g.setColor(Color.red); 
			int i,j;
				for (i=1;i<COLS-1;i++)
					for (j=1;j<ROWS-1;j++)
						if (map[i][j]==1);
						//g.fill3DRect(i*10,j*10,9,9,true);
		}


		class MouseHandler extends MouseInputAdapter { 
			
   			public void mousePressed(MouseEvent e) {
   				 start = e.getPoint();   
      
   				 if(button1Down = (e.getButton() == MouseEvent.BUTTON1)) {
    					  g = getGraphics();              
    				  	  g.setColor(Color.black);    
    				 }
				 if (e.getButton() == MouseEvent.BUTTON3){
					int sx=0,sy=0;
					g = getGraphics();
					a=start.x;
					b=start.y;
					tileX=(int)a/10;
					tileY=(int)b/10;
					a=(a-a%10)+1;
					b=(b-b%10)+1;
					if (a>10&&a<(COLS*10-10)&&b>10&&b<(ROWS*10-10)&&map[tileX][tileY]==0){
					if (count==0){
						count++;
						st=start; 
						     
    				  	  	g.setColor(Color.orange); 
						g.fill3DRect((start.x/10)*10+1,(start.y/10)*10+1,9,9,true);
						
					}
					else{	
						count=0;
						last = e.getPoint();
						g.setColor(Color.blue);  
						g.fill3DRect((last.x/10)*10+1,(last.y/10)*10+1,9,9,true);
						//g.drawLine((last.x/10)*10+5,(last.y/10)*10+5,(st.x/10)*10+5,(st.y/10)*10+5);
						
						deleteNode.push(spath.FindPath(st.x/10,st.y/10,last.x/10,last.y/10));
						spath.freeNode();
						}
					}
					}
				if (e.getButton() == MouseEvent.BUTTON2){
					while (!deleteNode.empty())
						spath.deleteLine(deleteNode.pop()); 	
					}
				
  			
				}
  		 	 public void mouseDragged(MouseEvent e) {
   		 		  last = e.getPoint();                            
				  g.setColor(Color.RED);
    				  if(button1Down) {
					a=last.x;
					b=last.y;
					tileX=(int)a/10;
					tileY=(int)b/10;
					a=(a-a%10)+1;
					b=(b-b%10)+1;
					if (a>10&&a<(COLS*10-10)&&b>10&&b<(ROWS*10-10)&&map[tileX][tileY]==0){
						g.fill3DRect(a,b,9,9,true);
						map[tileX][tileY]=1;
					}
    		 		 }
			
   		 	}

   			 public void mouseReleased(MouseEvent e) {
      				if(button1Down = (e.getButton()==MouseEvent.BUTTON1)) {
      		 		 button1Down = false;                   
        				

					if(g!= null) {                       // If there's a graphics context
        				 // g2D.dispose();                        // ...release the resource
        				  g = null;                           // Set field to null
       					}
      		 			 start = last = null;                    // Remove the points
      					}
    			}

    
   			 private Point start;                     // Stores cursor position on press
   			 private Point last;                      // Stores cursor position on drag
	
   			 private boolean button1Down = false;          // Flag for button 1 state

		}
		public class NODE {
   				 double f,h;
   				 double g,tmpg;
    				int x,y;
   				 NODE Parent;
   				 NODE [] Child=new NODE[8];      
    				NODE NextNode;      
			}
		public class SearchPath{

			public SearchPath(){
				int i;
				for (i=0;i<ROWS;i++){
					map[0][i]=1;
					map[COLS-1][i]=1;
				}
				for (i=0;i<COLS;i++){
					map[i][0]=1;
					map[i][ROWS-1]=1;
				}
			}
			
			NODE OPEN,CLOSED;
			Stack<NODE> stackNode=new Stack<NODE>();
			public void freeNode(){
				/*NODE Node,node1;
 				Node=OPEN.NextNode;
 				 while (Node != null)
  				{node1=Node.NextNode;
  				  (Node);
  				  Node=node1;
  				}
  				Node=CLOSED.NextNode;
 				 while (Node !=null)
 				 {
				  node1=Node.NextNode;
  	  			free(Node);
  	 			 Node=node1;
  				}*/
			}
			public boolean checkNum(int x,int y,int x1,int y1){
			if(x==x1&&y==y1){
				return true;
			}
			else
				return false;
			}
			public boolean FreeTile(int x, int y){
				if(map[x][y]==0)
					trade[x][y]=1;
				serchNum++;
				return (!(map[x][y]==1));
			}
			public boolean FreeTile1(int x, int y){
				if(map[x][y]==0)
					trade[x][y]=1;
				serchNum++;
				return (!(map[x][y]==1||map[x+1][y]==1||map[x][y+1]==1));
			}
			public boolean FreeTile2(int x, int y){
				if(map[x][y]==0)
					trade[x][y]=1;
				serchNum++;
				return (!(map[x][y]==1||map[x-1][y]==1||map[x][y+1]==1));
			}
			public boolean FreeTile3(int x, int y){
				if(map[x][y]==0)
					trade[x][y]=1;
				serchNum++;
				return (!(map[x][y]==1||map[x+1][y]==1||map[x][y-1]==1));
			}
			public boolean FreeTile4(int x, int y){
				if(map[x][y]==0)
					trade[x][y]=1;
				serchNum++;
				return (!(map[x][y]==1||map[x-1][y]==1||map[x][y-1]==1));
			}
			public NODE FindPath(int sx,int sy,int dx,int dy)
			{
   				 NODE Node,BestNode;
    
   				 OPEN=new NODE();
   				 CLOSED=new NODE();

   				 Node=new NODE();
    
   				 Node.g=0;
   				 Node.h=0;
   				 Node.h=math.hypot((double)(dx-sx),(double)(dy-sy));
   				 //Node.h=0;
  				 Node.f=Node.g+Node.h;
   				 Node.x=sx;
   				 Node.y=sy;

    			 OPEN.NextNode=Node;       
  				  for (;;)
  				  {
	
 					BestNode=ReturnBestNode(); 
                                      
					if (checkNum(dx,dy,BestNode.x,BestNode.y)) 
						break;
					GenerateSuccessors(BestNode,dx,dy);
   				 }
				
				PrimeRun pr=new PrimeRun(BestNode,sx,sy);
				pr.start();
				return BestNode;
			}
			public NODE  ReturnBestNode()
			{
  			  NODE tmp;

    				if (OPEN.NextNode == null)
				{
	 			   System.out.print("ERROR: he is in prison\n");
					System.exit(-1);
				}

    			tmp=OPEN.NextNode;             
  			  OPEN.NextNode=tmp.NextNode;   
  			  tmp.NextNode=CLOSED.NextNode;
 			   CLOSED.NextNode=tmp;
			  return (tmp);
			}

			public void GenerateSuccessors(NODE BestNode,int dx,int dy)
			{
			    int x,y;
			    double t=math.sqrt(2);
		   
			    if (FreeTile1(x=BestNode.x-1,y=BestNode.y-1))
			      GenerateSucc(BestNode,x,y,dx,dy,t,0);
		
			    if (FreeTile(x=BestNode.x,y=BestNode.y-1))
			      GenerateSucc(BestNode,x,y,dx,dy,1,1);
		   
			    if (FreeTile2(x=BestNode.x+1,y=BestNode.y-1))
			      GenerateSucc(BestNode,x,y,dx,dy,t,2);
		  
			    if (FreeTile(x=BestNode.x+1,y=BestNode.y))
			      GenerateSucc(BestNode,x,y,dx,dy,1,3);
		
			    if (FreeTile4(x=BestNode.x+1,y=BestNode.y+1))
			      GenerateSucc(BestNode,x,y,dx,dy,t,4);
		 
			    if (FreeTile(x=BestNode.x,y=BestNode.y+1))
			      GenerateSucc(BestNode,x,y,dx,dy,1,5);
		  
			    if (FreeTile3(x=BestNode.x-1,y=BestNode.y+1))
			      GenerateSucc(BestNode,x,y,dx,dy,t,6);
		 
			    if (FreeTile(x=BestNode.x-1,y=BestNode.y))
			      GenerateSucc(BestNode,x,y,dx,dy,1,7);
			}

			public void GenerateSucc(NODE BestNode,int x, int y, int dx, int dy,double t,int c)
			{
  			  double g;
			    NODE Old,Successor;
			    g=BestNode.g+t;	    
	
  
 			  if ((Old=CheckOPEN(x,y))!= null)
			   {
				BestNode.Child[c]=Old;

				if (g < Old.g)
				{
				    Old.Parent=BestNode;
				    Old.g=g;
				    Old.f=g+Old.h;
				}
			    }
			    else if ((Old=CheckCLOSED(x,y)) != null) 
			    {
				BestNode.Child[c]=Old;

				if (g < Old.g)                    
				{
				    Old.Parent=BestNode;
				    Old.g=g;
				    Old.f=g+Old.h;
				    PropagateDown(Old);
				}
			    }
			    else
			    {
				Successor=new NODE();
				Successor.Parent=BestNode;
				Successor.g=g;
				Successor.h=math.hypot((double)(dx-x),(double)(dy-y));
				//Successor.h=0;
				Successor.f=g+Successor.h;    
				Successor.x=x;                 
				Successor.y=y;

				Insert(Successor);    

				BestNode.Child[c]=Successor;
  			  }
			}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			public  NODE CheckOPEN(int tx,int ty)
			{
 			   NODE tmp;

			    tmp=OPEN.NextNode;
			    while (tmp != null)
			    {
				if (checkNum(tmp.x,tmp.y,tx,ty))
				  return (tmp);
				else
			  tmp=tmp.NextNode;
  			  }
  			return (null);
			}
			public  NODE CheckCLOSED(int tx,int ty)
			{
			   NODE tmp;

			    tmp=CLOSED.NextNode;

			    while (tmp != null)
 			   {
				if (checkNum(tmp.x,tmp.y,tx,ty))
				  return (tmp);
				else
				  tmp=tmp.NextNode;
			    }
			 return (null);
			}

			public void Insert(NODE Successor)
			{
			    NODE tmp1,tmp2;
			    double f=0;

			    if (OPEN.NextNode == null)
 			     {
				OPEN.NextNode=Successor;
				return;
			      }


			    f=Successor.f;
			    tmp1=OPEN;
			    tmp2=OPEN.NextNode;

			    while ((tmp2 != null) && (tmp2.f < f))
			    {
			      tmp1=tmp2;
			      tmp2=tmp2.NextNode;
			    }
				Successor.NextNode=tmp2;
				tmp1.NextNode=Successor;
			}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			public void PropagateDown(NODE Old)
			{
 			   double g;
 			   int c;
 			   NODE Child,Father;
			   g=Old.g;            
			    for(c=0;c<8;c++)
			    {
			    if ((Child=Old.Child[c])==null) 
			      break;
				if ((c%2)==0){
				if ((g+math.sqrt(2))<Child.g)
				{
				  Child.g=g+math.sqrt(2);
				  Child.f=Child.g+Child.h;
				  Child.Parent=Old;         
				  stackNode.push(Child);               
				}    
				}else{
				if (g+1<Child.g)
				{
				  Child.g=g+1;
				  Child.f=Child.g+Child.h;
				  Child.Parent=Old;          
				  stackNode.push(Child);             
				}                             
				}
			    }

			    while (!stackNode.empty())
			    {
				Father=stackNode.pop();
				for(c=0;c<8;c++)
				{
				 if ((Child=Father.Child[c])==null)      
				  break;
				  if ((c%2)==0){
				  if ((Father.g+math.sqrt(2))<Child.g)
				  {                                
				    Child.g=Father.g+math.sqrt(2);
				    Child.f=Child.g+Child.h;
				    Child.Parent=Father;
				    stackNode.push(Child);
				  }
				}else{
				  if (Father.g+1 <Child.g)  
				  {                            
				    Child.g=Father.g+1;
				    Child.f=Child.g+Child.h;
				    Child.Parent=Father;
				    stackNode.push(Child);
					}
				}
				}
			    }
			}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
			 class PrimeRun extends Thread  {
				NODE path;
				int tempX,tempY,dx,dy;
        			PrimeRun(NODE path,int dx,int dy) {
				this.path=path.Parent;
				this.dx=dx;
				this.dy=dy;
				g1 = getGraphics();        
       				  }
 
        			 public void run() {
           			  	tempX=path.x;
					tempY=path.y;
 					while (path.Parent!= null)
 					 {
					if (map[path.x][path.y]==0){
					try{
					sleep(100);
					}catch(Exception e){}
    					
					g1.setColor(Color.black);
					g1.fill3DRect(tempX*10+1,tempY*10+1,9,9,true); 
					g1.setColor(Color.white);
					g1.drawLine(tempX*10+5,tempY*10+5,path.x*10+5,path.y*10+5);
					g1.fill3DRect(path.x*10+1,path.y*10+1,9,9,true);
					}
					else {
						deleteNode.push(spath.FindPath(dx,dy,tempX,tempY));
						break;
					}
					tempX=path.x;
					tempY=path.y;
					path=path.Parent;
  					}
					
        			}
				private Graphics g1= null; 
    			 }
			public void deleteLine(NODE p){
				Graphics g = getGraphics(); 
				g.setColor(Color.black);
				g.fillRect(p.x*10,p.y*10,11,11);
				while (p.Parent!= null){
					p=p.Parent;
					g.fillRect(p.x*10,p.y*10,11,11);
						
				}
			}
			
		}
	 private Graphics g= null; 
	}
	

}