<>();// 每次寻路之前将栈清空this.steps = new YKDStack<>();// 将起点添加到栈中，并将其标记为已访问this.steps.push(new Tile(start, -1));this.map[start.getRow()][start.getColumn()] = '*';// 循环到栈中元素为空结束，则表示从起点开始未能找到结束点while (this.steps.peek() != null) {// 获取栈顶元素Tile tile = this.steps.peek();Point tilePoint = tile.getPoint();// 判断是不是结束节点if (this.isSame(tilePoint, end)) {break;}// 修改栈顶元素的方向，准备进行探索tile.setDirection(tile.getDirection() + 1);// 当方向为 4 的时候，表示所有方向都已经遍历过了，所以标记为死路@，并弹出栈顶元素if (tile.getDirection() == 4) {this.map[tilePoint.getRow()][tilePoint.getColumn()] = '@';this.steps.pop();} else {// 否则探索目标方向的方格int[] direction = directions[tile.getDirection()];// 根据方向向量获取新方格的位置信息Point newPoint = new Point(tilePoint.getRow() + direction[0],tilePoint.getColumn() + direction[1]);// 如果可以通行，则将新探索的方格添加到栈中，并标记为已访问if (this.canStep(newPoint)) {Tile newTile = new Tile(newPoint, -1);this.map[newPoint.getRow()][newPoint.getColumn()] = '*';this.steps.push(newTile);}// 如果不可以通行，则不处理，再次获取栈顶元素，改变方向 。}}return path;}
这部分非常重要，大家需要仔细阅读这部分代码和注释，彻底理解方向探索的核心 。
第四步：回溯整个路径
从上面代码可以看出，当while循环执行完成后，只有两种情况
第一种，栈为空，也就是遍历完起点所能走到的所有方格，里面都没有找到终点 第二种，找到终点，break跳出循环
我们需要特别关心第二种情况，大家试想一下这个时候栈中存储的方格是什么特征？
栈中元素全是*元素，因为@将全部pop出栈 。*元素表示的是探索的路径，并且从起点开始，终点结束的 。如果我们依次pop，这将是一条终点到起点的路径，我们需要倒排即可 。
我们来看看最后的代码：
// 寻找路径public ArrayList findPath(Point start, Point end) {ArrayList path = new ArrayList<>();......// 从栈中以此回退方格信息，也就是整个访问路径信息while (this.steps.peek() != null) {//将下一个路径插到前面，已完成路径回溯path.add(0, this.steps.pop().getPoint());}return path;}
测试一下：
public static void main(String[] args) {char[][] map = {{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},{'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},{'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},{'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},{'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},{'#', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}};Game game = new Game(map);Point start = new Point(1, 1);Point end = new Point(8, 8);ArrayList path = game.findPath(start, end);for (Point point : path) {System.out.println(point.getRow() + " - " + point.getColumn());}}