营救公主(Java实现A*算法解决迷宫问题) - JAVA

/**
* 已经经过的位置集合(关闭列表)
*/
private List passedPositions;

/**
* 公主位置
*/
private PositionWeight princessPosition;

/**
* 王子位置
*/
private PositionWeight princePosition;

/**
* 王子移动一步的所有偏移量
*/
private List offsets = Arrays.asList(new Position[] {
new Position(1, 0), new Position(0, 1), new Position(-1, 0),
new Position(0, -1) });

public Prince(int time)
{
this.time = time;
this.attemptPositions = new ArrayList();
this.passedPositions = new ArrayList();
}

/**
* 开始寻找公主
*/
public int startToSearch()
{
reset();

if (getPrincePosition().getPosition() == null
|| getPrincessPosition().getPosition() == null || time < 0)
{
return FAIL;
}

// 1、添加王子自己的起始位置
getAttemptPositions().add(getPrincePosition());

// 2、通过移动维护待尝试列表和已经尝试的列表
attemptMove();

// 3、已经营救成功或者时间耗尽或者无法营救时，统计结果返回
return getSpendTime();
}

/**
* 设置迷宫地图
*/
public void setMap(MazeMap map)
{
this.map = map;
}

/**
* 重置
*
*/
private void reset()
{
// 清空待尝试的列表
getAttemptPositions().clear();

// 清空已经尝试的列表
getPassedPositions().clear();

// 初始化王子的位置
Position princePosition = getMap().getPrincePosition();
setPrincePosition(new PositionWeight(princePosition));

// 初始化公主的位置
Position princessPosition = getMap().getPrincessPosition();
PositionWeight princessPositionWeight = new PositionWeight(
princessPosition);
setPrincessPosition(princessPositionWeight);
}

/**
* 可预知式移动
*
*/
private void attemptMove()
{
// 1、在如下2种情况下均结束：1)只要在待尝试列表中发现了公主，表明已经找到； 2)迷宫中所有可达的点都遍历完成，仍然无法找到
if (getAttemptPositions().contains(getPrincessPosition())
|| getAttemptPositions().isEmpty())
{
return;
}

// 2、获取最新加入的开销最小的节点
PositionWeight minPositionWeight = getMinPositionWeight();

// 3、从待尝试列表中移除开销最小节点
getAttemptPositions().remove(minPositionWeight);

// 4、把找到的开销最小节点加至已经尝试的列表
getPassedPositions().add(minPositionWeight);

// 5、对当前的开销最小节点进行尝试，找出其所有子节点
List subPositionWeights = getReachableSubPositions(minPositionWeight);

// 6、把所有子节点按照一定条件添加至待尝试列表
for (PositionWeight subPositionWeight : subPositionWeights)
{
addPositionWeight(minPositionWeight, subPositionWeight);
}

// 7、重复以上操作
attemptMove();
}

/**
* 王子从当前移动一步，可达的位置(忽略墙)
*
*/
private List getReachableSubPositions(PositionWeight father)
{
List subPositionWeights = new ArrayList();

Position fatherPosition = father.getPosition();
PositionWeight subPositionWeight = null;
Position subPosition = null;
for (Position offset : offsets)
{
subPosition = fatherPosition.offset(offset);
subPositionWeight = new PositionWeight(subPosition, father,
getPrincessPosition());

// 子节点越界或者是墙壁或

营救公主(Java实现A*算法解决迷宫问题) (八)