waysearch.java

Java ME手机应用开发大全一书的配套光盘上的源码

import java.util.Vector;

public class WaySearch
{
    /* 开表 */
    private Vector openList = new Vector();
    /* 闭表 */
    private Node[][] closeList = new Node[12][10];
    /* 当前节点 */
    private Node currentNode;
    /* 构造一个算法 */
    public WaySearch() {}
    /* 返回路径
     * 假如无法找到路径，以及起点终点一样则将path置空，否则将路线填入该列表中，第一个节点为起点，最后一个节点为终点
     */
    public void find(int startRow, int startColumn, int targetRow, int targetColumn, Vector path)
    {
        path.removeAllElements();
    	//起点终点一样返回
        if (startRow == targetRow && startColumn == targetColumn)
            return;        
        //清空开和闭表
        openList.removeAllElements();
        for (int i = 0; i < 12; i++)
            for (int j = 0; j < 10; j++)
                closeList[i][j] = null;        
        //添加起始节点到开启列表
        Node startNode = new Node(startRow, startColumn, null);
        addToOpenList(startNode);        
        while(!openList.isEmpty())
        {
            //选取F值最小的节点为当前节点
            currentNode = (Node)openList.firstElement();
            int curRow = currentNode.row;
            int curColumn = currentNode.column;
            //切换当前节点到关闭列表中
            openList.removeElement(currentNode);
            closeList[curRow][curColumn] = currentNode;
            //处理当前节点的相邻节点
            int sRow = (curRow > 1) ? curRow - 1 : 0;
            int sColumn = (curColumn > 1) ? curColumn - 1 : 0;
            int eRow = (curRow < 10) ? curRow + 1 : 11;
            int eColumn = (curColumn < 8) ? curColumn + 1 : 9;
            for (int i = sRow; i <= eRow; i++) 
            {
                for (int j = sColumn; j <= eColumn; j++) 
                {
                    //是自己或者该节点不可达，循环继续
                    if ((i == curRow && j == curColumn) || !MainCanvas.canCross(i, j))
                        continue;                    
                    //创建一个节点，指定其父结点
                    Node node = new Node(i ,j, currentNode);
                    //设置G值，水平和垂直方向为10，对角线为14
                    node.g = currentNode.g + ((i == curRow || j == curColumn) ? 10 : 14);                    
                    //目标节点被添加到开启列表中，搜索可以结束了，路径找到了
                    if (targetRow == i && targetColumn == j)
                    {
                        while (node.parent != null)
                        {
                            path.insertElementAt(node, 0);
                            node = node.parent;
                        }
                        path.insertElementAt(node, 0);
                        return;
                    }
                    //该节点在关闭列表中，不做处理
                    if (closeList[i][j] != null)
                        continue;
                    Node openBlock = listContains(node, openList);
                    if(openBlock == null)
                    {
                    	//节点不在开列表中，设置H值并添加到开表中
                        //设置H值，G值已经在建立node时应该已经被设置好了,并且父结点已经为currentNode
                        node.h = 10*(Math.abs(targetRow - i) + Math.abs(targetColumn - j));
                        addToOpenList(node);
                    } 
                    else if (openBlock.g > node.g) 
                    {
                        //节点在开列表中,假如g更小则改变其父结点为当前节点
                        openList.removeElement(openBlock);
                        addToOpenList(node);
                    }
                }
            }
        }
    }

    /*
     * 添加节点到开表中，并按F值进行排序，从小到大
     */
    private void addToOpenList(Node node) {
        int count = openList.size();
        for (int i = 0; i < count; i++) {
            Node openNode = (Node)openList.elementAt(i);
            if (node.getF() <= openNode.getF()) {
                openList.insertElementAt(node, i);
                return;
            }
        }

        openList.addElement(node);
    }
    /*
     * 表中是否已经包含新添的节点
     * return 表中的节点
     */
    private Node listContains(Node node, Vector list) 
    {
        int count = list.size();
        for (int i = 0; i < count; i++)
        {
            Node listNode = (Node) list.elementAt(i);
            if (node.row == listNode.row && node.column == listNode.column)
                return listNode;
        }
        return null;
    }
}