sp.zip_Astar 寻路_Astar算法_routing_寻路_寻路算法

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 Gene