DFdou's Blog Life is short,Be yourself.

Android-AS3的AStar复刻版

因为需要，所以直接把AS3版本的AStar复刻成了Java版，基本上什么都没改。
唉，让人比较无语的是Java里的ArrayList和Array咩有shift和unshift之类的常用函数的？
问了班里几个似乎在做Java的人，得到的答案=没有答案。
下边是复刻之后的代码：
AStar.java:

/**
 *
 */
package util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import android.util.Log;

/**
 * @author DFdou
 *
 */

public class AStar {
    // 待考察表
    private ArrayList<node> _open = new ArrayList</node><node>();
    // 已考察表
    private ArrayList</node><node> _closed = new ArrayList</node><node>();
    // 网格
    private Grid _grid;
    // 开始节点
    private Node _startNode;
    // 结束节点
    private Node _endNode;
    // 终点节点的数组
    private ArrayList</node><node> _path = new ArrayList</node><node>();
    // 曼哈顿估价函数,算横竖距离和
    //private Function _heuristic = manhattan;
    // 几何估价法,算直线距离
    // private var _heuristic:Function = euclidian;
    // 对角线估价法
    // private var _heuristic:Function=diagonal;
    // 直线前进代价
    private float _straightCost = 1.0f;
    // 对角线前进代价
    private float _diagCost = 1.414f;

    public AStar() {
    }

    // 8方向
    public boolean findPath(Grid grid) {
	_grid = grid;
	// 创建待考察列表
	_open.clear();
	// 创建已考察列表
	_closed.clear();
	// 起点
	_startNode = _grid.getStartNode();
	// 终点
	_endNode = _grid.getEndNode();
	_startNode.g = 0;
	// 选一个估价函数,传入起点
	_startNode.h = manhattan(_startNode);
	_startNode.f = _startNode.g + _startNode.h;
	// 返回寻路结果
	return search();
    }

    public boolean search() {
	// 将起点节点设为当前节点
	Node node = _startNode;
	// 如果木有到达目标节点
	while (node != _endNode) {
	    // 循环的节点范围,不需要检测grid范围以外的节点
	    int startX = Math.max(0, node.x - 1);
	    int endX = Math.min(_grid.getNumCols() - 1, node.x + 1);
	    int startY = Math.max(0, node.y - 1);
	    int endY = Math.min(_grid.getNumRows() - 1, node.y + 1);
	    for (int i = startX; i < = endX; i++) {
		for (int j = startY; j <= endY; j++) {
		    // 尝试节点
		    Node test = _grid.getNode(i, j);
		    // 尝试节点为当前节点,或者为不可通过的节点,或者临接节点都不能通过那么就跳过该节点
		    if (test == node || !test.walkable
			    || !_grid.getNode(node.x, test.y).walkable
			    || !_grid.getNode(test.x, node.y).walkable) {
			continue;
		    }
		    float cost = _straightCost;
		    // 如果不在同直线距离上,就是对角线了～
		    if (!((node.x == test.x) || (node.y == test.y))) {
			cost = _diagCost;
		    }
		    // 计算g值
		    double g = node.g + cost * test.costMultiplier;
		    // 计算h值
		    double h = manhattan(test);
		    // 相加得到f
		    double f = g + h;
		    // 如果测试点已经在待考察列表或者已考察列表里,就比较已考察的结果是否比当前结果大,是的话就重新赋值,也就是说找到了更优的点
		    if (isOpen(test) || isClosed(test)) {
			if (test.f > f) {
			    test.f = f;
			    test.g = g;
			    test.h = h;
			    test.parent = node;
			}
			// 测试点不再待考察列表中,赋值,设置父节点,加入待考察列表
		    } else {
			test.f = f;
			test.g = g;
			test.h = h;
			test.parent = node;
			_open.add(test);
		    }
		}
	    }
	    // 根据f进行排序,最后一个是f值最小的
	    // _open.sortOn("f", Array.NUMERIC);
	    Comparator comp = new NodeFComparator();
	    Collections.sort(_open, comp);
	    // 作为当前节点
	    // node = _open.shift();
	    node = _open.get(0);
	    _open.remove(0);
	    _open.trimToSize();
	}
	buildPath();
	return true;
    }

    // 4方向
    public boolean findPath4(Grid grid) {
	_grid = grid;
	// 创建待考察列表
	_open.clear();
	// 创建已考察列表
	_closed.clear();
	// 起点
	_startNode = _grid.getStartNode();
	// 终点
	_endNode = _grid.getEndNode();
	_startNode.g = 0;
	// 选一个估价函数,传入起点
	_startNode.h = manhattan(_startNode);
	_startNode.f = _startNode.g + _startNode.h;
	// 返回寻路结果
	return search4();
    }

    public boolean search4() {
	// 将起点节点设为当前节点
	Node node = _startNode;
	// 如果木有到达目标节点
	while (node != _endNode) {
	    // 循环的节点范围,不需要检测grid范围以外的节点
	    int startX = Math.max(0, node.x - 1);
	    int endX = Math.min(_grid.getNumCols() - 1, node.x + 1);
	    int startY = Math.max(0, node.y - 1);
	    int endY = Math.min(_grid.getNumRows() - 1, node.y + 1);
	    for (int i = startX; i < = endX; i++) {
		for (int j = startY; j <= endY; j++) {
		    // 尝试节点
		    Node test = _grid.getNode(i, j);
		    // 尝试节点为当前节点,或者为不可通过的节点,或者临接节点都不能通过那么就跳过该节点
		    // PS:在四方向寻路情况下跳过对角线点
		    if (test == node || !test.walkable
			    || !_grid.getNode(node.x, test.y).walkable
			    || !_grid.getNode(test.x, node.y).walkable
			    || Math.abs(i - node.x) + Math.abs(j - node.y) > 1) {
			continue;
		    }
		    float cost = _straightCost;
		    // 如果不在同直线距离上,就是对角线了～
		    if (!((node.x == test.x) || (node.y == test.y))) {
			cost = _diagCost;
		    }
		    // 计算g值
		    double g = node.g + cost * test.costMultiplier;
		    // 计算h值
		    double h = manhattan(test);
		    // 相加得到f
		    double f = g + h;
		    // 如果测试点已经在待考察列表或者已考察列表里,就比较已考察的结果是否比当前结果大,是的话就重新赋值,也就是说找到了更优的点
		    if (isOpen(test) || isClosed(test)) {
			if (test.f > f) {
			    test.f = f;
			    test.g = g;
			    test.h = h;
			    test.parent = node;
			}
			// 测试点不再待考察列表中,赋值,设置父节点,加入待考察列表
		    } else {
			test.f = f;
			test.g = g;
			test.h = h;
			test.parent = node;
			_open.add(test);
		    }
		}
	    }

	    // 当前节点已经考察过了,所以就加入已考察列表
	    _closed.add(node);
	    // 检查待考察表里面有没有节点,没有就意味着没有可行的路径
	    if (_open.size() == 0) {
		return false;
	    }
	    // 根据f进行排序,最后一个是f值最小的
	    // _open.sortOn("f", Array.NUMERIC);
	    Comparator comp = new NodeFComparator();
	    Collections.sort(_open, comp);
	    // 作为当前节点
	    // node = _open.shift();
	    node = _open.get(0);
	    _open.remove(0);
	    _open.trimToSize();
	}
	buildPath();
	return true;
    }

    // 建立路径
    private void buildPath() {
	_path.clear();
	Node node = _endNode;
	_path.add(node);
	while (node != _startNode) {
	    node = node.parent;
	    // _path.unshift(node);
	    _path.add(0, node);
	}
    }

    public ArrayList</node><node> getPath() {
	return _path;
    }

    private boolean isOpen(Node node) {
	int len = _open.size();
	for (int i = 0; i < len; i++) {
	    if (_open.get(i) == node) {
		return true;
	    }
	}
	return false;
    }

    private boolean isClosed(Node node) {
	int len = _closed.size();
	for (int i = 0; i < len; i++) {
	    if (_closed.get(i) == node) {
		return true;
	    }
	}
	return false;
    }

    private double manhattan(Node node) {
	return Math.abs(node.x - _endNode.x) * _straightCost
		+ Math.abs(node.y + _endNode.y) * _straightCost;
    }

    private double euclidian(Node node) {
	float dx = node.x - _endNode.x;
	float dy = node.y - _endNode.y;
	return Math.sqrt(dx * dx + dy * dy) * _straightCost;
    }

    private double diagonal(Node node) {
	float dx = Math.abs(node.x - _endNode.x);
	float dy = Math.abs(node.y - _endNode.y);
	float diag = Math.min(dx, dy);
	float straight = dx + dy;
	return _diagCost * diag + _straightCost * (straight - 2 * diag);
    }

    // public float getVisited() {
    // return ArrayUtils.addAll(_closed, _open);
    // }
}