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

S = 0;

/**
* 剩余的时间
*/
private int time;

/**
* 迷宫地图
*/
private MazeMap map;

/**
* 正待尝试的位置集合(开启列表)
*/
private List attemptPositions;

/**
* 已经经过的位置集合(关闭列表)
*/
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());

// 子节点越界或者是墙壁或者已经在尝试过的列表中时，不做任何处理
if (getMap().isOverEdge(subPosition)
|| getMap().isWall(subPosition)
|| isInPassedTable(subPositionWeight))
{
continue;
}

subPositionWeights.add(subPositionWeight);
}
return subPositionWeights;
}

/**
* 添加一个点
*
*/
private void addPositionWeight(PositionWeight father,
PositionWeight positionWeight)
{
// 在待尝试列表中已经包含了当前点，则按照一定条件更新其父节点及其权值，否则直接添加
if (getAttemptPositions().contains(positionWeight))
{
updateCostByFather(fat

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