aasterisk.java

手机游戏《紫色精灵》源代码

import java.util.Vector;

/**
 * <p>Title:A*寻路算法 </p>
 *
 * <p>Description: A*寻路算法</p>
 *
 * <p>Copyright: Copyright (c) 2005 wodead</p>
 *
 * <p>Company: wodead</p>
 *
 * @author wodead
 * @version 1.0
 */
public class AAsterisk {
	
	/**
	 * 开表
	 */
    private Vector openList = new Vector();
    
    /**
     * 闭表
     */
    private BlockNode[][] closeList = new BlockNode[12][10];
    
    /**
     * 当前节点
     */
    private BlockNode currentNode;
    
    /**
     * 构造一个算法
     *
     */
    public AAsterisk() {
    }

    /**
     * 返回路径
     * @param startRow
     * @param startColumn
     * @param targetRow
     * @param targetColumn
     * @param path, 假如无法找到路径，以及起点终点一样则将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;
        
        //添加起始节点到开启列表
        BlockNode startNode = new BlockNode(startRow, startColumn, null);
        addToOpenList(startNode);
        
        while(!openList.isEmpty()) {
            //选取F值最小的节点为当前节点
            currentNode = (BlockNode)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) ||
                        !Main.canCross(i, j))
                        continue;
                    
                    //创建一个节点，指定其父结点
                    BlockNode node = new BlockNode(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;

                    BlockNode 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值进行排序，从小到大
     * @param node
     */
    private void addToOpenList(BlockNode node) {
        int count = openList.size();
        for (int i = 0; i < count; i++) {
            BlockNode openNode = (BlockNode)openList.elementAt(i);
            if (node.getF() <= openNode.getF()) {
                openList.insertElementAt(node, i);
                return;
            }
        }

        openList.addElement(node);
    }

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