astar.java

java语言编写的最短路径

package test.star;
import java.awt.Point;
import java.util.LinkedList;
/** *//** */
/** *//**
 * <p>
 * Title: LoonFramework
 * </p>
 * <p>
 * Description:描述路径节点用类
 * </p>
 * <p>
 * Copyright: Copyright (c) 2008
 * </p>
 * <p>
 * Company: LoonFramework
 *From:网络大本营 Http://www.qqview.com
 * </p>
 * <p>
 * License: http://www.apache.org/licenses/LICENSE-2.0
 * </p>
 * 
 * @author chenpeng
 * @email：[e-mail]
 * @version 0.1
 */
public class Node implements Comparable {
  // 坐标
  public Point _pos;
  // 开始地点数值
  public int _costFromStart;
  // 目标地点数值
  public int _costToObject;
  // 父节点
  public Node _parentNode;
  private Node() {
  }
  /** *//** */
  /** *//**
   * 以注入坐标点方式初始化Node
   * 
   * @param _pos
   */
  public Node(Point _pos) {
    this._pos = _pos;
  }
  /** *//** */
  /** *//**
   * 返回路径成本
   * 
   * @param node
   * @return
   */
  public int getCost(Node node) {
    // 获得坐标点间差值 公式：(x1, y1)-(x2, y2)
    int m = node._pos.x - _pos.x;
    int n = node._pos.y - _pos.y;
    // 取两节点间欧几理德距离（直线距离）做为估价值，用以获得成本
    return (int) Math.sqrt(m * m + n * n);
  }
  /** *//** */
  /** *//**
   * 检查node对象是否和验证对象一致
   */
  public boolean equals(Object node) {
    // 验证坐标为判断依据
    if (_pos.x == ((Node) node)._pos.x && _pos.y == ((Node) node)._pos.y) {
      return true;
    }
    return false;
  }
  /** *//** */
  /** *//**
   * 比较两点以获得最小成本对象
   */
  public int compareTo(Object node) {
    int a1 = _costFromStart + _costToObject;
    int a2 = ((Node) node)._costFromStart + ((Node) node)._costToObject;
    if (a1 < a2) {
      return -1;
    } else if (a1 == a2) {
      return 0;
    } else {
      return 1;
    }
  }
  /** *//** */
  /** *//**
   * 获得上下左右各点间移动限制区域
   * 
   * @return
   */
  public LinkedList getLimit() {
    LinkedList limit = new LinkedList();
    int x = _pos.x;
    int y = _pos.y;
    // 上下左右各点间移动区域(对于斜视地图，可以开启注释的偏移部分，此时将评估8个方位)
    // 上
    limit.add(new Node(new Point(x, y - 1)));
    // 右上
    // limit.add(new Node(new Point(x+1, y-1)));
    // 右
    limit.add(new Node(new Point(x + 1, y)));
    // 右下
    // limit.add(new Node(new Point(x+1, y+1)));
    // 下
    limit.add(new Node(new Point(x, y + 1)));
    // 左下
    // limit.add(new Node(new Point(x-1, y+1)));
    // 左
    limit.add(new Node(new Point(x - 1, y)));
    // 左上
    // limit.add(new Node(new Point(x-1, y-1)));
    return limit;
  }
}
 


package test.star;
import java.awt.Point;
import java.util.LinkedList;
import java.util.List;
/** *//** */
/** *//**
 * <p>
 * Title: LoonFramework
 * </p>
 * <p>
 * Description:A*寻径处理用类(此类为演示用，并不意味着算法是最佳实现)
 * </p>
 * <p>
 * Copyright: Copyright (c) 2008
 * </p>
 * <p>
 * Company: LoonFramework
 * </p>
 * <p>
 * License: http://www.apache.org/licenses/LICENSE-2.0
 * </p>
 * 
 * @author chenpeng
 * @email：[e-mail]
 * @version 0.1
 */
public class PathFinder {
  // 路径优先等级list(此示例中为内部方法)
  private LevelList _levelList;
  // 已完成路径的list
  private LinkedList _closedList;
  // 地图描述
  private int[][] _map;
  // 行走区域限制
  private int[] _limit;
  /** *//** */
  /** *//**
   * 以注入地图的2维数组及限制点描述初始化此类
   * 
   * @param _map
   */
  public PathFinder(int[][] map, int[] limit) {
    _map = map;
    _limit = limit;
    _levelList = new LevelList();
    _closedList = new LinkedList();
  }
  /** *//** */
  /** *//**
   * A*方式寻径,注入开始坐标及目标坐标后运算,返回可行路径的List
   * 
   * @param startPos
   * @param objectPos
   * @return
   */
  public List searchPath(Point startPos, Point objectPos) {
    // 初始化起始节点与目标节点
    Node startNode = new Node(startPos);
    Node objectNode = new Node(objectPos);
    // 设定起始节点参数
    startNode._costFromStart = 0;
    startNode._costToObject = startNode.getCost(objectNode);
    startNode._parentNode = null;
    // 加入运算等级序列
    _levelList.add(startNode);
    // 当运算等级序列中存在数据时，循环处理寻径，直到levelList为空
    while (!_levelList.isEmpty()) {
      // 取出并删除最初的元素
      Node firstNode = (Node) _levelList.removeFirst();
      // 判定是否和目标node坐标相等
      if (firstNode.equals(objectNode)) {
        // 是的话即可构建出整个行走路线图，运算完毕
        return makePath(firstNode);
      } else {
        // 否则
        // 加入已验证List
        _closedList.add(firstNode);
        // 获得firstNode的移动区域
        LinkedList _limit = firstNode.getLimit();
        // 遍历
        for (int i = 0; i < _limit.size(); i++) {
          // 获得相邻节点
          Node neighborNode = (Node) _limit.get(i);
          // 获得是否满足等级条件
          boolean isOpen = _levelList.contains(neighborNode);
          // 获得是否已行走
          boolean isClosed = _closedList.contains(neighborNode);
          // 判断是否无法通行
          boolean isHit = isHit(neighborNode._pos.x, neighborNode._pos.y);
          // 当三则判定皆非时
          if (!isOpen && !isClosed && !isHit) {
            // 设定costFromStart
            neighborNode._costFromStart = firstNode._costFromStart + 1;
            // 设定costToObject
            neighborNode._costToObject = neighborNode.getCost(objectNode);
            // 改变neighborNode父节点
            neighborNode._parentNode = firstNode;
            // 加入level
            _levelList.add(neighborNode);
          }
        }
      }
    }
    // 清空数据
    _levelList.clear();
    _closedList.clear();
    // 当while无法运行时，将返回null
    return null;
  }
  /** *//** */
  /** *//**
   * 判定是否为可通行区域
   * 
   * @param x
   * @param y
   * @return
   */
  private boolean isHit(int x, int y) {
    for (int i = 0; i < _limit.length; i++) {
      if (_map[y][x] == _limit[i]) {
        return true;
      }
    }
    return false;
  }
  /** *//** */
  /** *//**
   * 通过Node制造行走路径
   * 
   * @param node
   * @return
   */
  private LinkedList makePath(Node node) {
    LinkedList path = new LinkedList();
    // 当上级节点存在时
    while (node._parentNode != null) {
      // 在第一个元素处添加
      path.addFirst(node);
      // 将node赋值为parent node
      node = node._parentNode;
    }
    // 在第一个元素处添加
    path.addFirst(node);
    return path;
  }
  private class LevelList extends LinkedList {
    /** *//** */
    /** *//**
     * 
     */
    private static final long serialVersionUID = 1L;
    /** *//** */
    /** *//**
     * 增加一个node
     * 
     * @param node
     */
    public void add(Node node) {
      for (int i = 0; i < size(); i++) {
        if (node.compareTo(get(i)) <= 0) {
          add(i, node);
          return;
        }
      }
      addLast(node);
    }
  }
}
 


package test.star;
import java.awt.Graphics;
import java.awt.Image;
import java.io.File;
import java.io.IOException;
/** *//** */
/** *//**
 * <p>
 * Title: LoonFramework
 * </p>
 * <p>
 * Description:一个简单的地图实现
 * </p>
 * <p>
 * Copyright: Copyright (c) 2008
 * </p>
 * <p>
 * Company: LoonFramework
 * </p>
 * <p>
 * License: http://www.apache.org/licenses/LICENSE-2.0
 * </p>
 * 
 * @author chenpeng
 * @email：[e-mail]
 * @version 0.1
 */
public class TestMap {
  final static private int CS = 32;
  // 地图描述
  final static public int[][] MAP = { { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
      { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
      { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
      { 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
      { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
      { 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
      { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
      { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
  // 无法移动区域
  final static public int[] HIT = { 1 };
  // 设定背景方格默认行数
  final static private int ROW = 15;
  // 设定背景方格默认列数
  final static private int COL = 15;
  private Image floorImage;
  private Image wallImage;
  public TestMap() {
    try {
      floorImage = javax.imageio.ImageIO.read(new File("floor.gif"));
      wallImage = javax.imageio.ImageIO.read(new File("wall.gif"));
    } catch (IOException e) {
      // TODO Auto-generated catch block
      e.printStackTrace();
    }
  }
  public void draw(Graphics g) {
    for (int i = 0; i < ROW; i++) {
      for (int j = 0; j < COL; j++) {
        switch (MAP[i][j]) {
        case 0:
          g.drawImage(floorImage, j * CS, i * CS, null);
          break;
        case 1:
          g.drawImage(wallImage, j * CS, i * CS, null);
          break;
        }
      }
    }
  }
}