2. 技术人生
    3. AStar

    AStar

    技术2022-05-11  80

        以前对A*算法的理解停留在人工智能书本上面，但是最近2天看了Stanford的一个游戏介绍网站http://theory.stanford.edu/~amitp/GameProgramming/之后，觉得对A*算法有了比较深刻的了解。那个网站对A*描述没有课本1条又1条的公式化，更多的是图形，结合游戏本身实际来描述，觉得帮助很大。

        现在用Java编写了一个算法演示，效果还不错，不过现在open列表是链表形式，效率o(n)比较差，下一步可以考虑用堆插入查找来实现o(lgn)(不过其实现在100×100看起来还可以吧，暂时没有什么动力做，看以后需要吧）

    附：算法源代码，不妥之处，还望各位指正。 

    AStar.java（算法核心）

     

    /** *  */ package  Arithmetic; import  java.util. * ; import  GUI. * ; /** * @author 冯家耀 * */ public   class  AStar  {    final int BARRIER = -3;    final int START = -1;    final int END = -2;    Node [][]grid;    List<Node> open = new LinkedList();    Set close = new HashSet();    Node startNode;    Node endNode;    int [][]result;//1:找过 2:找到 0：空    final int EVEN_FIND = 1;    final int SUC_FIND = 2;    final int NOT_FIND = 0;    int gridRows;    int gridCols;    int D = 1;    public AStar(GridValue [][]g){        if(g==null)return;        gridRows = g.length;        gridCols = g[0].length;        grid = new Node[gridRows][gridCols];        result = new int[gridRows][gridCols];        boolean hasfindfirst = false;        boolean hasfindend = false;        for(int i=0;i<gridRows;i++){            for(int j = 0; j < gridCols; j++){                grid[i][j] = new Node(i,j,g[i][j].toInt());                if(! hasfindfirst){                    if(grid[i][j].cost == START){                        hasfindfirst = true;                        startNode = grid[i][j];                    }                }                if(! hasfindend){                    if(grid[i][j].cost == END){                        hasfindend = true;                        endNode = grid[i][j];                    }                }            }        }    }    class Node{        Node parent;        int row;        int col;        int cost;        int f;        int g;        public Node(int row,int col, int cost){            this.row = row;            this.col = col;            this.cost = cost;        }        @Override        public boolean equals(Object obj) {            if(obj instanceof Node && ((Node)obj).row == row && ((Node)obj).col == col)return true;            else return false;        }        @Override        public int hashCode() {            return row*gridCols+col;        }    }    int estimateH(Node node){        //return D*( (Math.abs(node.row) - endNode.row) + Math.abs(node.col - endNode.col) );        //return D*( Math.max((Math.abs(node.row) - endNode.row) , Math.abs(node.col - endNode.col)) );        int deltay = node.row - endNode.row;        int deltax = node.col - endNode.col;        return (int)(D*Math.sqrt((deltay*deltay + deltax*deltax)));    }    public boolean findPath(){        insertIntoOpen(startNode);        while(!open.isEmpty()){            Node node = open.remove(0);            System.out.println("Scan open");            result[node.row][node.col] = EVEN_FIND;            if(node.equals(endNode)){                markEven(node);                createPath();                return true;            }            else{                List neighborNodeList = findNeighbor(node);                Iterator<Node> it = neighborNodeList.iterator();                while(it.hasNext()){                    Node neighborNode = it.next();                    if(close.contains(neighborNode)){                        continue;                    }                    else{//FIXME 效率超低                        if(! open.contains(neighborNode)){                            neighborNode.g = node.g + neighborNode.cost;                            neighborNode.f = neighborNode.g + estimateH(neighborNode);                            neighborNode.parent = node;                            insertIntoOpen(neighborNode);                        }                        else{                            if(node.g + neighborNode.cost +  estimateH(neighborNode) < neighborNode.f){                                neighborNode.g = node.g + neighborNode.cost;                                neighborNode.f = neighborNode.g + estimateH(neighborNode);                                open.remove(neighborNode);                                neighborNode.parent = node;                                insertIntoOpen(neighborNode);                            }                        }                    }                }                            }            close.add(node);        }                return false;    }    private void markEven(Node node){        result[node.row][node.col] = -1;    }    private void createPath(){        LinkedList pathlist = new LinkedList();        Node tmp = endNode;        while(tmp.parent != null){            result[tmp.row][tmp.col] = SUC_FIND;            tmp = tmp.parent;        }    }    private List findNeighbor(Node node){        List<Node> list = new ArrayList();        int left = node.col-1;        int up = node.row-1;        int down = node.row+1;        int right = node.col+1;        if(left > 0){            if(grid[node.row][left].cost != BARRIER)                list.add(grid[node.row][left]);            if(up>0){                if(grid[up][node.col].cost != BARRIER)                    list.add(grid[up][node.col]);                if(grid[up][left].cost != BARRIER)                    list.add(grid[up][left]);            }            if(down < gridRows - 1){                if(grid[down][node.col].cost != BARRIER)                    list.add(grid[down][node.col]);                if(grid[down][left].cost != BARRIER)                    list.add(grid[down][left]);            }        }        if(right < gridCols - 1){            if(grid[node.row][right].cost != BARRIER)                list.add(grid[node.row][right]);            if(up>0){                if(grid[up][right].cost != BARRIER)                    list.add(grid[up][right]);            }            if( down < gridRows - 1){                if(grid[down][right].cost != BARRIER)                    list.add(grid[down][right]);            }        }        return list;    }    public int[][] getResult(){        return result;    }    private void insertIntoOpen(Node node){        int size = open.size();        Iterator<Node>it = open.iterator();        int i = 0;        while(it.hasNext()){            if(it.next().f > node.f)break;            i++;        }        open.add(i, node);        System.out.println("OPEN ADD NODE:("+ node.row+","+node.col+")" );    }}

     GridValue.java

    package  GUI; public   enum  GridValue {    BARRIER(-3),    START(-1),    END(-2),    LEN1(1),    LEN10(10),    LEN50(50),    LEN100(100),    LEN150(150);        private int value;    private GridValue(int value){        this.value = value;    }    public int toInt(){        return this.value;    }}

     

    MainForm.java（界面展示）

    package  GUI; import  java.awt. * ; import  java.awt.event.ActionEvent; import  java.awt.event.ActionListener; import  java.awt.event.MouseAdapter; import  java.awt.event.MouseEvent; import  javax.swing.BoxLayout; import  javax.swing.JButton; import  javax.swing.JFrame; import  javax.swing.JLabel; import  javax.swing.JOptionPane; import  javax.swing.JPanel; import  javax.swing.JSplitPane; import  javax.swing.WindowConstants; import  sun.font.GlyphLayout.GVData; /*** This code was edited or generated using CloudGarden's Jigloo* SWT/Swing GUI Builder, which is free for non-commercial* use. If Jigloo is being used commercially (ie, by a corporation,* company or business for any purpose whatever) then you* should purchase a license for each developer using Jigloo.* Please visit www.cloudgarden.com for details.* Use of Jigloo implies acceptance of these licensing terms.* A COMMERCIAL LICENSE HAS NOT BEEN PURCHASED FOR* THIS MACHINE, SO JIGLOO OR THIS CODE CANNOT BE USED* LEGALLY FOR ANY CORPORATE OR COMMERCIAL PURPOSE.*/ public   class  MainForm  extends  javax.swing.JFrame  {    private JSplitPane jSplitPane1;    private JButton jButton3;    private JButton jButton2;    private JButton jButton1;    private JPanel jPanel17;    private JPanel jPanel1;    private JLabel jLabel3;    private JLabel jLabel4;    private JLabel jLabel5;    private JPanel jPanel1Start;    private JLabel jLabel7;    private JPanel jPanel1End;    private JPanel jPanel14;    private JPanel jPanel16;    private JLabel jLabel6;    private JPanel jPanel12;    private JPanel jPanel1Barrier;    private JPanel jPanel10;    private JPanel jPanelLength150;    private JPanel jPanel8;    private JPanel jPanelLength100;    private JPanel jPanel6;    private JLabel jLabel2;    private JPanel jPanelLength50;    private JPanel jPanel4;    private JLabel jLabel1;    private JPanel jPanelLength10;    private GridPanel gridPanel;    private JPanel jPanel2;    /**    * Auto-generated main method to display this JFrame    */    public static void main(String[] args) {        MainForm inst = new MainForm();        inst.setVisible(true);        inst.setTitle("A*算法演示");    }        public MainForm() {        super();        initGUI();    }                private void initGUI() {        try {            setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE);            {                jSplitPane1 = new JSplitPane();                getContentPane().add(jSplitPane1, BorderLayout.CENTER);                jSplitPane1.setDividerSize(1);                jSplitPane1.setDividerLocation(412);                jSplitPane1.setResizeWeight(1.0);                {                    gridPanel = new GridPanel();                    gridPanel.setBackground(Color.BLACK);                    gridPanel.setPreferredSize(new Dimension(411,411));                    jSplitPane1.setLeftComponent(gridPanel);//                    gridPanel.addMouseListener(new )                }                {                    jPanel2 = new JPanel();                    FlowLayout jPanel2Layout = new FlowLayout();                    jPanel2Layout.setAlignment(FlowLayout.LEFT);                    jSplitPane1.setRightComponent(jPanel2);                    jPanel2.setBackground(Color.GRAY);                    jPanel2.setPreferredSize(new Dimension(40,400));                    jPanel2.setLayout(jPanel2Layout);                    {                        jPanel1 = new JPanel();                        FlowLayout jPanel1Layout = new FlowLayout();                        jPanel1Layout.setAlignment(FlowLayout.LEFT);                        jPanel1.setLayout(jPanel1Layout);                        jPanel2.add(jPanel1);                        jPanel1.setPreferredSize(new java.awt.Dimension(165,26));                        jPanel1.setBackground(new java.awt.Color(128,128,128));                        {                            jPanelLength10 = new JPanel();                            jPanel1.add(jPanelLength10);                            GridLayout jPanel3Layout = new GridLayout(1, 1);                            jPanel3Layout.setHgap(5);                            jPanel3Layout.setVgap(5);                            jPanel3Layout.setColumns(1);                            jPanelLength10.setLayout(jPanel3Layout);                            jPanelLength10.setPreferredSize(new java.awt.Dimension(15, 13));                            jPanelLength10.setBackground(new java.awt.Color(33,233,0));                            jPanelLength10.addMouseListener(new MouseAdapter() {                                public void mousePressed(MouseEvent evt) {                                    gridPanel.setCurrentValue(GridValue.LEN10);                                }                            });                        }                        {                            jLabel1 = new JLabel();                            jPanel1.add(jLabel1);                            jLabel1.setText("10");                        }                    }                    {                        jPanel4 = new JPanel();                        FlowLayout jPanel4Layout = new FlowLayout();                        jPanel4Layout.setAlignment(FlowLayout.LEFT);                        jPanel4.setLayout(jPanel4Layout);                        jPanel2.add(jPanel4);                        jPanel4.setPreferredSize(new java.awt.Dimension(165,26));                        jPanel4.setBackground(new java.awt.Color(128,128,128));                        {                            jPanelLength50 = new JPanel();                            GridLayout jPanel5Layout = new GridLayout(1, 1);                            jPanel5Layout.setHgap(5);                            jPanel5Layout.setVgap(5);                            jPanel5Layout.setColumns(1);                            jPanel4.add(jPanelLength50);                            jPanelLength50.setBackground(new java.awt.Color(255,128,128));                            jPanelLength50.setPreferredSize(new java.awt.Dimension(15,13));                            jPanelLength50.setLayout(jPanel5Layout);                            jPanelLength50.addMouseListener(new MouseAdapter() {                                public void mousePressed(MouseEvent evt) {                                    gridPanel.setCurrentValue(GridValue.LEN50);                                }                            });                        }                        {                            jLabel2 = new JLabel();                            jPanel4.add(jLabel2);                            jLabel2.setText("50");                        }                    }                    {                        jPanel6 = new JPanel();                        jPanel2.add(jPanel6);                        FlowLayout jPanel6Layout = new FlowLayout();                        jPanel6Layout.setAlignment(FlowLayout.LEFT);                        jPanel6.setLayout(jPanel6Layout);                        jPanel6.setPreferredSize(new java.awt.Dimension(165,26));                        jPanel6.setBackground(new java.awt.Color(128,128,128));                        {                            jPanelLength100 = new JPanel();                            GridLayout jPanel7Layout = new GridLayout(1, 1);                            jPanel7Layout.setHgap(5);                            jPanel7Layout.setVgap(5);                            jPanel7Layout.setColumns(1);                            jPanel6.add(jPanelLength100);                            jPanelLength100.setBackground(new java.awt.Color(255,255,128));                            jPanelLength100.setPreferredSize(new java.awt.Dimension(15,13));                            jPanelLength100.setLayout(jPanel7Layout);                            jPanelLength100                                .addMouseListener(new MouseAdapter() {                                public void mousePressed(MouseEvent evt) {                                    gridPanel.setCurrentValue(GridValue.LEN100);                                }                                });                        }                        {                            jLabel3 = new JLabel();                            jPanel6.add(jLabel3);                            jLabel3.setText("100");                        }                    }                    {                        jPanel8 = new JPanel();                        FlowLayout jPanel8Layout = new FlowLayout();                        jPanel8Layout.setAlignment(FlowLayout.LEFT);                        jPanel8.setLayout(jPanel8Layout);                        jPanel2.add(jPanel8);                        jPanel8.setPreferredSize(new java.awt.Dimension(165,26));                        jPanel8.setBackground(new java.awt.Color(128,128,128));                        {                            jPanelLength150 = new JPanel();                            GridLayout jPanel9Layout = new GridLayout(1, 1);                            jPanel9Layout.setHgap(5);                            jPanel9Layout.setVgap(5);                            jPanel9Layout.setColumns(1);                            jPanel8.add(jPanelLength150);                            jPanelLength150.setBackground(new java.awt.Color(128,255,128));                            jPanelLength150.setPreferredSize(new java.awt.Dimension(15,13));                            jPanelLength150.setLayout(jPanel9Layout);                            jPanelLength150                                .addMouseListener(new MouseAdapter() {                                public void mousePressed(MouseEvent evt) {                                    gridPanel.setCurrentValue(GridValue.LEN150);                                }                                });                        }                        {                            jLabel4 = new JLabel();                            jPanel8.add(jLabel4);                            jLabel4.setText("150");                        }                    }                    {                        jPanel10 = new JPanel();                        FlowLayout jPanel10Layout = new FlowLayout();                        jPanel10Layout.setAlignment(FlowLayout.LEFT);                        jPanel10.setLayout(jPanel10Layout);                        jPanel2.add(jPanel10);                        jPanel10.setPreferredSize(new java.awt.Dimension(165,26));                        jPanel10.setBackground(new java.awt.Color(128,128,128));                        {                            jPanel1Barrier = new JPanel();                            GridLayout jPanel11Layout = new GridLayout(1, 1);                            jPanel11Layout.setHgap(5);                            jPanel11Layout.setVgap(5);                            jPanel11Layout.setColumns(1);                            jPanel10.add(jPanel1Barrier);                            jPanel1Barrier.setBackground(new java.awt.Color(128,255,255));                            jPanel1Barrier.setPreferredSize(new java.awt.Dimension(15,13));                            jPanel1Barrier.setLayout(jPanel11Layout);                            jPanel1Barrier.addMouseListener(new MouseAdapter() {                                public void mousePressed(MouseEvent evt) {                                    gridPanel.setCurrentValue(GridValue.BARRIER);                                }                            });                        }                        {                            jLabel5 = new JLabel();                            jPanel10.add(jLabel5);                            jLabel5.setText("固体");                        }                    }                    {                        jPanel12 = new JPanel();                        FlowLayout jPanel12Layout = new FlowLayout();                        jPanel12Layout.setAlignment(FlowLayout.LEFT);                        jPanel12.setLayout(jPanel12Layout);                        jPanel2.add(jPanel12);                        jPanel12.setPreferredSize(new java.awt.Dimension(165,26));                        jPanel12.setBackground(new java.awt.Color(128,128,128));                        {                            jPanel1Start = new JPanel();                            GridLayout jPanel13Layout = new GridLayout(1, 1);                            jPanel13Layout.setHgap(5);                            jPanel13Layout.setVgap(5);                            jPanel13Layout.setColumns(1);                            jPanel12.add(jPanel1Start);                            jPanel1Start.setBackground(new java.awt.Color(255,0,255));                            jPanel1Start.setPreferredSize(new java.awt.Dimension(15,13));                            jPanel1Start.setLayout(jPanel13Layout);                            jPanel1Start.addMouseListener(new MouseAdapter() {                                public void mouseClicked(MouseEvent evt) {                                    gridPanel.setCurrentValue(GridValue.START);                                }                            });                        }                        {                            jLabel6 = new JLabel();                            jPanel12.add(jLabel6);                            jLabel6.setText("起点");                        }                    }                    {                        jPanel16 = new JPanel();                        jPanel2.add(jPanel16);                        jPanel16.setBackground(new java.awt.Color(128,128,128));                        jPanel16.setPreferredSize(new java.awt.Dimension(165,26));                        {                            jPanel14 = new JPanel();                            FlowLayout jPanel14Layout = new FlowLayout();                            jPanel14Layout.setAlignment(FlowLayout.LEFT);                            jPanel14.setLayout(jPanel14Layout);                            jPanel16.add(jPanel14);                            jPanel14.setBackground(new java.awt.Color(                                128,                                128,                                128));                            jPanel14.setPreferredSize(new java.awt.Dimension(                                165,                                26));                            {                                jPanel1End = new JPanel();                                GridLayout jPanel15Layout = new GridLayout(1, 1);                                jPanel15Layout.setHgap(5);                                jPanel15Layout.setVgap(5);                                jPanel15Layout.setColumns(1);                                jPanel14.add(jPanel1End);                                jPanel1End.setBackground(new java.awt.Color(128,0,255));                                jPanel1End.setPreferredSize(new java.awt.Dimension(15,13));                                jPanel1End.setLayout(jPanel15Layout);                                jPanel1End.addMouseListener(new MouseAdapter() {                                    public void mouseClicked(MouseEvent evt) {                                        gridPanel.setCurrentValue(GridValue.END);                                    }                                });                            }                            {                                jLabel7 = new JLabel();                                jPanel14.add(jLabel7);                                jLabel7.setText("终点");                            }                        }                    }                    {                        jPanel17 = new JPanel();                        GridBagLayout jPanel17Layout = new GridBagLayout();                        jPanel17Layout.rowWeights = new double[] {0.1, 0.0, 0.0};                        jPanel17Layout.rowHeights = new int[] {7, 35, 35};                        jPanel17Layout.columnWeights = new double[] {0.1};                        jPanel17Layout.columnWidths = new int[] {7};                        jPanel17.setLayout(jPanel17Layout);                        jPanel2.add(jPanel17);                        jPanel17.setPreferredSize(new java.awt.Dimension(170, 197));                        jPanel17.setBackground(new java.awt.Color(128,128,128));                        {                            jButton1 = new JButton();                            jPanel17.add(jButton1, new GridBagConstraints(0, 1, 1, 1, 0.0, 0.0, GridBagConstraints.CENTER, GridBagConstraints.NONE, new Insets(0, 0, 0, 0), 0, 0));                            jButton1.setText("计算");                            jButton1.setPreferredSize(new java.awt.Dimension(130, 25));                            jButton1.addActionListener(new ActionListener() {                                public void actionPerformed(ActionEvent evt) {                                    Arithmetic.AStar astar = new Arithmetic.AStar(gridPanel.getGrid());                                    if(                                            astar.findPath()                                                                        ){                                        gridPanel.setResult(astar.getResult());                                        JOptionPane.showConfirmDialog(MainForm.this, "FOUND");                                    }                                    else JOptionPane.showConfirmDialog(MainForm.this, "NOT FOUND");                                    gridPanel.repaint();                                }                            });                        }                        {                            jButton2 = new JButton();                            jPanel17.add(jButton2, new GridBagConstraints(0, 2, 2, 1, 0.0, 0.0, GridBagConstraints.CENTER, GridBagConstraints.NONE, new Insets(0, 0, 0, 0), 0, 0));                            jButton2.setText("消除路径");                            jButton2.setPreferredSize(new java.awt.Dimension(130, 25));                            jButton2.addMouseListener(new MouseAdapter() {                                public void mouseClicked(MouseEvent evt) {                                    System.out                                        .println("jButton2.mouseClicked, event="                                            + evt);                                    //TODO add your code for jButton2.mouseClicked                                }                            });                        }                        {                            jButton3 = new JButton();                            jPanel17.add(jButton3, new GridBagConstraints(0, 0, 1, 1, 0.0, 0.0, GridBagConstraints.CENTER, GridBagConstraints.NONE, new Insets(0, 0, 0, 0), 0, 0));                            jButton3.setText("清空所有");                            jButton3.setPreferredSize(new java.awt.Dimension(130,25));                            jButton3.addMouseListener(new MouseAdapter() {                                public void mouseClicked(MouseEvent evt) {                                    gridPanel.clearAll();                                    gridPanel.setResult(null);                                    gridPanel.repaint();                                }                            });                        }                    }                }            }            pack();            this.setSize(600, 450);            //this.setExtendedState(JFrame.MAXIMIZED_BOTH);        } catch (Exception e) {            e.printStackTrace();        }    }    @Override    public void paint(Graphics g) {        // TODO 自动生成方法存根        super.paint(g);            }} class  GridPanel  extends  JPanel {        final int rows = 20;    final int cols = 20;    GridValue [][]grid = new GridValue[rows][cols];    final int gridPanelWidth = 411;    final int gridPanelHeight = 411;    int [][]result;    int rowspan = (gridPanelHeight - 10 - 1) / rows;    int colspan = (gridPanelWidth - 10 - 1) / cols;    int edge = 5;        private GridValue currentValue = GridValue.LEN1;    public GridPanel() {        for(int i = 0; i < rows; i++)            for(int j = 0; j < cols;j++){                grid[i][j] = GridValue.LEN1;            }        addMouseListener(new MouseAdapter(){            @Override            public void mousePressed(MouseEvent e) {                int xgrid = (e.getX() - edge) / colspan;                int ygrid = (e.getY() - edge) / rowspan;                grid[ygrid][xgrid] = currentValue;                repaint();            }        });    }    public GridValue[][] getGrid(){        return grid;    }    public void  setResult(int[][]result){        this.result = result;    }    public void clearAll(){        for(int i = 0; i < rows; i++){            for(int j = 0; j < cols;j++){                grid[i][j] = GridValue.LEN1;            }        }        repaint();    }    public void setCurrentValue(GridValue value){        currentValue = value;    }    public void drawGrid(Graphics g,int row,int col){        //grid[row][col] = value;        int startrow = edge + rowspan*row;        int startcol = edge + colspan*col;        boolean draw = true;        switch(grid[row][col]){        case BARRIER:            g.setColor(new java.awt.Color(128,255,255));            break;        case START:            g.setColor(new java.awt.Color(255,0,255));            break;        case END:            g.setColor(new java.awt.Color(128,0,255));            break;        case LEN1:                        draw = false;            break;        case LEN10:            g.setColor(new java.awt.Color(33,233,0));            break;        case LEN50:            g.setColor(new java.awt.Color(255,128,128));            break;        case LEN100:            g.setColor(new java.awt.Color(255,255,128));            break;        case LEN150:            g.setColor(new java.awt.Color(128,255,128));            break;        default:break;        }        if(draw)            g.fillRect(startcol + colspan/4, startrow+rowspan/4, rowspan/2, colspan/2);    }    public void drawResult(Graphics g,int row,int col){        if(result == null)return;        int startrow = edge + rowspan*row;        int startcol = edge + colspan*col;        int r = result[row][col];        boolean draw = true;        if(r == 0)return;        if(r == 1)g.setColor(Color.WHITE);        if(r == 2)g.setColor(Color.YELLOW);        g.drawOval(startcol + colspan/2, startrow+rowspan/2, colspan/4, rowspan/4);    }    @Override    public void paint(Graphics g) {        super.paint(g);        g.setColor(Color.WHITE);        for(int i = 0;i < rows+1;i++){            g.drawLine(edge, edge + rowspan*i, gridPanelWidth - edge - 1, edge + rowspan*i);        }        for(int i = 0;i < cols+1;i++){            g.drawLine( edge + colspan*i, edge, edge + colspan*i, gridPanelHeight - edge - 1);        }        for(int i = 0; i < rows; i++){            for(int j = 0; j < cols;j++){                drawGrid(g, i, j);                drawResult(g,i,j);            }        }    }}

     

     

    专利

    最新回复(0)