需要维护两个列表一个是开放列表还有一个封闭列表
Vector open = new Vector(); // 开放列表
Vector close = new Vector(); // 封闭列表
定义节点类
class Node {
int x;
int y;
int g; // G = 移动代价，沿着到父块而生成路径移动的代价。
int h; // H = 从格子中给定 的方块到最终目标 B点的评估移动代价。
int f; // 估价
Node father;
Node(Node node, int sx, int sy, int ex, int ey) {
if (node != null) { // 新建子节点
father = node; // 设置父节点
x = sx; // 当前x
y = sy; // 当前y
h = (getABS(sx - ex) + getABS(sy - ey))*10; // 实际代价 当前块移动到终点块的绝对距离。
g = node.g + 10; // 代价推算 当前块移动代价=父块移动代价+移动代价
f = g + h; // 估价
}
else { // 根节点
x = sx;
y = sy;
h = 0;
g = 0;
f = 9999;
}
}
}
private int getABS(int v) {
if (v < 0) {
return -v;
}
return v;
}
// 开始寻路
public void xunLu(int sx, int sy, int ex, int ey) {
boolean flag = true; // 是否存在于open list中
int minIndex = 0; // 具有最小F值对象的的open list下标
int newX = 0;
int newY = 0;
/**
* 1 添加开始方块到开放列表。
* 初始化根接点,把根节点放入开放列表.
*/
Node minNode = new Node(null, sx, sy, ex, ey);
open.add(minNode);
while (open.size() != 0) {
/**
* 2 查找开放列表中具有最小F值的方块。
*/
minNode = ((Node)open.get(0));
minIndex = 0;
for (int i = 1; i < open.size(); i++) {
if (minNode.f > ( (Node) open.get(i)).f) {
minNode = ( (Node) open.get(i));
minIndex = i;
}
}
/**
* 3 把最小F值的方块从开放列表中取出然后放入封闭列表。
*/
if (minNode != null) {
close.add(minNode);
open.remove(minIndex);
}
/**
* 4 如果目前找到的最小F值块是终点就返回。
*/
if (minNode.x == ex && minNode.y == ey) {
do {
minNode = minNode.father;
}
while (get != null);
return;
}
/**
* 5 对最小F值块(即上面刚刚放入封闭列表里面) 的8个相邻方块的进行判断.
* 将4或8个方向,可以走的放入开放列表内.
*/
for (int i = 0; i < 4; i++) {
flag = true;
newX = minNode.x + t[0];
newY = minNode.y + t[1];
/**
*5。1 地图是否越界 如果它不可行走，或者存在于封闭列表，忽略它。
*/
if(newY < 0 || newY > 4 || newX < 0 || newX > 9) {
continue;
}
if (map[newY][newX] == 0) { // 判断是否是可以移动
for (int k = 0; k < close.size(); k++) {
if ( (((Node) close.get(k)).x == newX) &&
(((Node) close.get(k)).y == newY) ) {
flag = false;
break;
}
}
if(flag) {
for(int ii = 0; ii < open.size(); ii++) {
if( ((Node)open.get(ii)).x == newX && ((Node)open.get(ii)).y == newY) {
open.remove(ii);
break;
}
}
open.add(new Node(minNode, newX,newY, ex, ey));
}
}
}
}
}作者: jiazurongyu 时间: 2011-6-8 14:15
以前的帖子顶上去作者: wytanmark09 时间: 2011-6-8 15:10
路过学习，留下脚印~~
。 好了下面我们还是来看看如何实现吧。