<>();// 存储4个方向private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};public Game(char[][] map) {this.map = map;}......}
接下来我们来看看整个实战过程 。
实战过程
第 1 步
我们站在起点，将起点位置{1, 1}加入到steps栈中，并将该元素的方向设置为-1，也就是表示还未探索过 。
第 2 步
获取栈顶元素，也就是{1, 1}方格，将方格的方向加 1 当做探索方向，也就是右侧(-1 + 1 = 0, 在右下左上中，索引为 0 的是右侧) 。探索方格右侧方格{1, 2}，并将其加入到steps栈中，方向设置为-1 。
第 3 步
获取栈顶元素，也就是{1, 2}方格，将方格的方向加 1 当做探索方向，同样也是右侧 。因为右侧遇到#，无法作为路径，则继续将方向加 1，改为下侧（0 + 1 = 1, 在右下左上中，索引为 1 的是下侧） 。探索方格下侧方格{2, 2}，并将其加入到steps栈中，方向设置为-1 。
以此类推，可以达到如下情况
这时候我们发现{1, 4}这个方格，上下左右都不能移动了，这是一条死路，因此我们将该方格设置为@，并将此方格从栈顶pop 。继续观察此时的栈顶元素{1, 5}，同样也是死路，我们将其也设置为@，并执行pop操作 。
直到如下场景：
获取栈顶元素{3, 2}，发现之前的方向是右侧0，首先加 1 探索下侧方向，无法通行 。将方向继续加 1，探索左侧方向，因此将{3, 1}加入栈顶 。
下面的步骤就不演示，以此内推，最终可以找到结束的节点，如下图所示：
路径回溯
这个时候，栈中存储的刚好是从起点到终点的方格路径，我们只需要依次pop栈顶元素，然后倒叙即可获取路径完整信息 。
代码实现
? 有了思路，接下来便开始完善方法 。
// 寻找路径public ArrayList findPath(Point start, Point end) {ArrayList path = new ArrayList<>();return path;}
第一步：将起点添加到栈中
// 寻找路径public ArrayList findPath(Point start, Point end) {ArrayList path = new ArrayList<>();// 每次寻路之前将栈清空this.steps = new YKDStack<>();// 将起点添加到栈中，并将其标记为已访问this.steps.push(new Tile(start, -1));this.map[start.getRow()][start.getColumn()] = '*';}
这一步比较简单，大家需要注意的是每次寻找路径之前，需要将栈清空 。
第二步：循环获取栈顶元素，修改方向准备进行探索
// 判断是否为同一个方格，用于判断是否找到结束方格private boolean isSame(Point point1, Point point2) {return point1.getRow() == point2.getRow() && point1.getColumn() == point2.getColumn();}// 寻找路径public ArrayList findPath(Point start, Point end) {ArrayList path = new ArrayList<>();// 每次寻路之前将栈清空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);}return path;}
? 如上面代码，当栈为空的时候表示没有任何一条路径可以从起点到终点 。我们抽离了方法判断两个方格是否相同 。
第三步：根据方向添加新探索节点到栈中，或者设置为死路并 pop 栈顶元素
// 判断是否为同一个方格private boolean isSame(Point point1, Point point2) {return point1.getRow() == point2.getRow() && point1.getColumn() == point2.getColumn();}// 判断探索是否可以进行，如果是空格才可以进行private boolean canStep(Point point) {return this.map[point.getRow()][point.getColumn()] == ' ';}// 寻找路径public ArrayList findPath(Point start, Point end) {ArrayList path = new ArrayList