linesight.java

A-star 问题找到最短路径 结合了遇到障碍物问题。

/*
 * LineSight.java
 *
 * Created on 2007年3月29日, 下午1:08
 */

package astar;
import com.sun.swing.internal.plaf.metal.resources.metal;
import java.util.*;
/**
 *
 * @author  Administrator
 */
public class LineSight extends javax.swing.JPanel{
    private class ToPoint{
        public ToPoint(int x, int y){
            this.x = x;
            this.y = y;
            this.S = 0;
        }
        public boolean compare(int x, int y){
            if(this.x==x && this.y == y){
                return true;
            }
            return false;
        }
        public boolean compare(ToPoint t){
            if(this.x==t.x && this.y == t.y){
                return true;
            }
            return false;
        }
        public int C(){
            return S+this.H();
        }
        public int H(){
            return Math.abs(y-goal.y)+( Math.abs(x-goal.x)-Math.abs(y-goal.y) );
        }
        public ToPoint parent = null;
        public int S;
        public int x;
        public int y;
    }
    /** Creates new form LineSight */
    public final static int WH = 20;
    public final static int SPEED = 1;
    public static boolean PAINT = false;
    public static boolean WEIGHT = false;
    
    private ToPoint goal;
    private ArrayList closed;//closed
    private ToPoint nowTo;//now point's position
    private ArrayList obstacle;//obstacle
    private ArrayList opened;//opened
    private ArrayList bestpath;
    private ToPoint to;
    private java.awt.Color lineColor = new java.awt.Color(0,128,0);
    
    public LineSight() {
        obstacle = new ArrayList();
        closed = new ArrayList();
        opened = new ArrayList();
        bestpath = new ArrayList();
        repaint();
    }
    public void clear(int x, int y){
        bestpath.clear();
        bestpath.add(new ToPoint(x, y));
    }
    public void addBestpath(int x, int y){
        nowTo = new ToPoint(x, y);
        bestpath.add(nowTo);
        repaint();
    }
    public void addBestpath(int x, ToPoint tp){
        bestpath.add(x,nowTo);
        repaint();
    }
    public void addBestpath(ToPoint to){
        bestpath.add(to);
        repaint();
    }
    public void removeBestpath(int x, int y){
        bestpath.remove(new ToPoint(x,y));
        repaint();
    }
    public void addGoal(int x, int y){
        goal = new ToPoint(x,y);
    }
    public void addClosed(ToPoint to){
        closed.add(to);
    }
    public void removeClosed(ToPoint to){
        closed.remove(to);
    }
    public void addOpened(int x, int y){
        opened.add(new ToPoint(x,y));
    }
    public void addOpened(ToPoint to){
        opened.add(to);
    }
    public void removeOpened(ToPoint tp){
        for(int i=0; i<opened.size(); i++){
            if(((ToPoint)opened.get(i)).compare(tp)==true){
                opened.remove(i);
                return;
            }
        }
    }
    public void addObstacle(int x, int y){
        obstacle.add(new ToPoint(x,y));
    }
    public void removeObstacle(int x, int y){
        obstacle.remove(new ToPoint(x,y));
    }
    public void paint(java.awt.Graphics g){
        g.setColor(java.awt.Color.WHITE);
        g.fillRect(0,0,this.getWidth(),this.getHeight());
        g.setColor(lineColor);
        int i;
        for(i=0; i<this.getHeight(); i++){
            g.drawLine(0, i*WH, this.getWidth(), i*WH);
            g.drawString((i)+"", 0, i*WH);
        }
        for(i=0; i<this.getWidth(); i++){
            g.drawLine(i*WH, 0, i*WH, this.getHeight());
            g.drawString((i+1)+"", i*WH, 10);
        }
        
        for(i=0; i<obstacle.size(); i++ ){
            g.setColor(java.awt.Color.BLACK);
            to = (ToPoint)obstacle.get(i);
            g.fillRect((to.x-1)*WH, (to.y-1)*WH, WH, WH);
        }
        /////////////////////////////////////////////////////////////////////////////////
        for(i=0; i<bestpath.size(); i++){
            g.setColor(java.awt.Color.MAGENTA);
            to = (ToPoint)bestpath.get(i);
            g.fillOval(((to.x-1)*WH), ((to.y-1)*WH), WH, WH);
        }
        ///////////////////////////////////////////////////////////////////////////////////
        for(i=0; i<1; i++){
            g.setColor(java.awt.Color.RED);
            g.fillOval(((goal.x-1)*WH), ((goal.y-1)*WH), WH, WH);
        }
        
    }
   
    public ToPoint checkAnDirection(int x, int y, int flag){
        //1 2 3
        //4   5
        //6 7 8
        ToPoint to = null;
        switch(flag){
            case 0:
                to = new ToPoint(x,y);
                break;
            case 1:
                to = new ToPoint(x-1, y-1);
                break;
            case 2:
                to = new ToPoint(x, y-1);
                break;
            case 3:
                to = new ToPoint(x+1, y-1);
                break;
            case 4:
                to = new ToPoint(x-1, y);
                break;
            case 5:
                to = new ToPoint(x+1, y);
                break;
            case 6:
                to = new ToPoint(x-1, y+1);
                break;
            case 7:
                to = new ToPoint(x, y+1);
                break;
            case 8:
                to = new ToPoint(x+1, y+1);
                break;
        }
        for(int i=0; i<obstacle.size(); i++){
            if(((ToPoint)(obstacle.get(i))).compare(to)==true){
                return null;
            }
        }
        return to;
    }
    public ToPoint checkClosed(ToPoint to){
        if(to==null){
            return null;
        }
        for(int i=0; i<closed.size(); i++){
            if(((ToPoint)closed.get(i)).compare(to)==true){
                return null;
            }
        }
        return to;
    }
    
    private void addOpenedPoints(ToPoint parent){
        ToPoint tp;
        for(int i=1; i<=8; i++){
            tp = this.checkClosed(this.checkAnDirection(parent.x,parent.y,i));
            if( tp !=null ){
                int j = 0;
                for(; j<opened.size(); j++){
                    if(((ToPoint)opened.get(j)).compare(tp)==true){
                        break;
                    }
                }
                if(j == opened.size()){
                     tp.parent = parent;
                     tp.S = parent.S + 1;
                     opened.add(tp);
               }
            }
            
        }
    }
    private ToPoint getMinOpenedPoints(){
        ToPoint tp = null;
        if(opened.size()==0){
            return null;
        }
        tp = (ToPoint)opened.get(0);
        for(int i=1; i<opened.size(); i++){
            if(tp.C() > ((ToPoint)opened.get(i)).C() ){
                tp = (ToPoint)opened.get(i);
            }
        }
        return tp;
    }
    public void run(){
        ToPoint tp = null;
        this.addOpenedPoints(nowTo);
        this.addClosed(nowTo);
        while(true){
            tp = this.getMinOpenedPoints();
            if(tp == null){
                return;
            }
            this.addClosed(tp);
            this.removeOpened(tp);
            if(tp.x == goal.x &&
               tp.y == goal.y){
                
                System.out.println("I find the best way.");
                do{
                    try{
                        Thread.sleep(1000);
                    }catch(Exception e){};
                    this.addBestpath(tp);
                    repaint();
                    tp = tp.parent;
                }while(tp.parent !=null );
                return ;
            }
            this.addOpenedPoints(tp);
        }
    }
    
}