前面的小节我们完成了坦克大战地图的绘制和导出，并在开始游戏时能导入使用它。本小节我们首先要解决的就是坦克与地形的碰撞检测，实现坦克在行驶时碰到地形障碍能被阻挡。然后我们将绘制一个简单版的迷宫地形，计算出坦克可到达目的地的最短路径。然后采用之前学的命令模式，让敌方坦克具有“思考”并执行通过最短路径到达目的地的指令。这一小节要实现的功能听起来非常的有趣，那我们就迫不及待的开始实操吧。
地形障碍物检测
首先，我们得对坦克当前位置所面对的那一侧的地形（四个地图数组元素）进行获取，看下示意图：
代码实现：
package com.pf.java.tankbattle.util;
import ...
public class MapUtil {
/**
* 获取坦克前进方向面对的4块8×8小格子的Ornament数组
* @param map
* @param x
* @param y
* @param offset
* @param d
* @return
*/
public static Ornament[] face(String[][] map, int x, int y, int offset, Direction d) {
Ornament[] o = null;
// startX, startY
int sx, sy;
switch (d) {
case UP:
if (y == offset) return null;
sy = y - 1 - offset;
sx = x - 2;
o = new Ornament[]{
new Ornament(map[sy][sx], sx, sy),
new Ornament(map[sy][sx + 1], sx + 1, sy),
new Ornament(map[sy][sx + 2], sx + 2, sy),
new Ornament(map[sy][sx + 3], sx + 3, sy)
};
break;
case RIGHT:
if (x == COLS * 4 - offset) return null;
sy = y - 2;
sx = x + offset;
o = new Ornament[]{
new Ornament(map[sy][sx], sx, sy),
new Ornament(map[sy + 1][sx], sx, sy + 1),
new Ornament(map[sy + 2][sx], sx, sy + 2),
new Ornament(map[sy + 3][sx], sx, sy + 3)
};
break;
case DOWN:
if (y == ROWS * 4 - offset) return null;
sy = y + offset;
sx = x - 2;
o = new Ornament[]{
new Ornament(map[sy][sx], sx, sy),
new Ornament(map[sy][sx + 1], sx + 1, sy),
new Ornament(map[sy][sx + 2], sx + 2, sy),
new Ornament(map[sy][sx + 3], sx + 3, sy)
};
break;
case LEFT:
if (x == offset) return null;
sy = y - 2;
sx = x - 1 - offset;
o = new Ornament[]{
new Ornament(map[sy][sx], sx, sy),
new Ornament(map[sy + 1][sx], sx, sy + 1),
new Ornament(map[sy + 2][sx], sx, sy + 2),
new Ornament(map[sy + 3][sx], sx, sy + 3)
};
break;
}
return o;
}
}
代码说明
这里方法接收的参数，第一个为二维数组地图，
x和y代表坦克中心点的地图元素索引。offset为坦克中心点到四个边的地图元素索引差值。最后一个为坦克当前的方向。基于这些信息我们可以获取到坦克朝向所面对的四个地形元素，这里我们用Ornament对象来记录地形元素的类型和它在二维数组代表的地图中的索引。注意，这里要先判断是否到达地图边界的情况。最后返回一个长度为4的Ornament[]数组类型。
然后，我们在Tank的move()方法中增加对地形的碰撞检测判断逻辑：
public boolean move() {
// 省略触及边界的判断逻辑
...
// -------- 执行坦克和地形碰撞检测逻辑 --------
int u = PIXEL_UNIT;
boolean isV = Direction.isVertical(direction);
// 注意当坦克坐标位于8×8格子边上时才进行碰撞检测
if (isV && y % u == 0 || !isV && x % u == 0) {
Ornament[] obstacles = MapUtil.face(frame.getMap(), x / u + 2, y / u + 2, 2, direction);
for (int i = 0; i < 4; i++) {
String type = obstacles[i].getType();
// 判断前面有河流、石头或者砖块就被阻挡
if (type.startsWith("R") || type.startsWith("S") || type.startsWith("B")) {
return false;
}
}
}
// 省略坦克与其他物体的碰撞检测逻辑
...
// 省略坦克移动逻辑
...
}
运行效果如下：
A*算法实现最短路径
关于A*算法的思想解剖，可以参考笔者的一篇文章——图解A*算法。这里我们将直接给出代码的具体实现。
首先一起来看下我们要实现的功能，如下图所示，我们要为敌方坦克赋予智能，让它可以从绿框位置用最短的路径到达红框的位置。
中间会通过一个迷宫一样的砖块地形。这里我们将采用A星算法来实现最短路径。黄色的虚线框框出了地图中要作为A星算法进行判断的区域，这个区域就是坦克在整个地图中中心点所在位置索引的取值范围。
核心类
首先是结点类定义：
package com.pf.java.tankbattle.algorithm.astar;
import ...
/**
* 与二维数组代表的地图中的每个元素相对应的一个结点类
* 它实现了Comparable接口，在其被添加到一个优先级队列时会基于比较方法，确定在队列中的位置
*/
public class Node implements Comparable {
private int x;
private int y;
/** 父结点引用，用于确定路径的连接关系 */
private Node parent;
/** 代表从起点到当前结点已走的步数（代价值） */
private int g;
/** 代表从当前结点到目标结点要走的步数（估算的代价值），
这里不考虑障碍物阻隔的情况，而实际评估使用后可能不可达 */
private int h;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public Node(int x, int y, Node parent, int g, int h) {
this(x, y);
this.parent = parent;
this.g = g;
this.h = h;
}
/**
* 计算总代价F
* @return
*/
public int f() {
return g + h;
}
/**
* 根据总代价来评估优先级
* 总代价越小优先级越高，会优先添加到优先级队列的队首
* @param other
* @return
*/
@Override
public int compareTo(Node other) {
if (other == null) return -1;
int f = f();
int of = other.f();
return Integer.compare(f, of);
}
// 省略按属性x和y重写的equals和hashcode方法
// 省略getter和setter
}
代码说明
A星算法每次向当前结点四个方向辐射时要获取或者生成新的结点对象。当然一开始的结点对象为路径的起点。这里的
x和y代表了结点位于划定的地图区域的索引值，注意这里的索引是相对整个地图而言的，而不是我们前面图示中黄色虚线划定的区域。
接下来我们用一个实体类Input来封装迷宫的输入信息：
package com.pf.java.tankbattle.algorithm.astar;
/**
* 输入信息
*/
public class Input {
/** 整个游戏地图 */
private String[][] map;
private int rows;
private int cols;
/** 迷宫入口结点 */
private Node start;
/** 迷宫出口结点 */
private Node end;
public Input(String[][] map, int x1, int y1, int x2, int y2) {
this.map = map;
// 从二维数组计算横向和纵向的深度
this.rows = map.length;
this.cols = map[0].length;
this.start = new Node(x1, y1);
this.end = new Node(x2, y2);
}
// 省略getter和setter
}
然后就是我们最核心的A星算法引擎类AStar：
package com.pf.java.tankbattle.algorithm.astar;
import ...
/**
A星算法核心引擎类
*/
public class AStar {
/** 存放被辐射到的结点到Open优先级队列 */
private Queue openQueue = new PriorityQueue();
/** 存放被选中的结点到一个普通的列表中 */
private List closeList = new ArrayList();
/** 这里临时加一个画笔对象，为了演示A星算法的动态执行过程，让大家看的更直观 */
private Graphics graphics;
/**
A星算法引擎启动入口方法
*/
public Node startRadiating(Input input, Graphics graphics) {
// 先清除集合中原来占用的数据
openQueue.clear();
closeList.clear();
this.graphics = graphics;
// 先将起点加入open队列
openQueue.add(input.getStart());
// 绘制起点和重点（下面4行代码仅作演示目的）
this.graphics.setColor(Color.green);
this.graphics.fillRect(input.getStart().getX() * 8, input.getStart().getY() * 8, 8, 8);
this.graphics.setColor(Color.RED);
this.graphics.fillRect(input.getEnd().getX() * 8, input.getEnd().getY() * 8, 8, 8);
// 只要open队列不为空，一直循环
while (!openQueue.isEmpty()) {
// 获取代价值最小的结点
Node currNode = openQueue.poll();
// 将其加入Close列表
closeList.add(currNode);
// 高亮标记已关闭的结点（下面4行代码仅作演示目的）
this.graphics.setColor(new Color(150, 208, 118));
this.graphics.fillRect(currNode.getX() * 8, currNode.getY() * 8, 8, 8);
this.graphics.setColor(Color.BLACK);
this.graphics.drawRect(currNode.getX() * 8, currNode.getY() * 8, 8, 8);
// 执行辐射
doRadiating(currNode, input);
// 判断end结点被辐射到
if (openQueue.contains(input.getEnd())) {
// 程序执行结束
break;
}
// 延缓执行中间过程，可以看清动态改变的结点
try {
Thread.sleep(50);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
// 程序执行结束，要么无通路（end结点的parent为null）；要么找到最短路径
return input.getEnd();
}
/**
对当前结点执行四个方向的辐射
*/
private void doRadiating(Node currNode, Input input) {
// 获取当前结点的索引
int x = currNode.getX();
int y = currNode.getY();
// 分别辐射左、上、右、下四个方向
doRadiating(currNode, input, x - 1, y, Direction.LEFT);
doRadiating(currNode, input, x, y - 1, Direction.UP);
doRadiating(currNode, input, x + 1, y, Direction.RIGHT);
doRadiating(currNode, input, x, y + 1, Direction.DOWN);
}
/**
实际的辐射方法
*/
private void doRadiating(Node currNode, Input input, int x, int y, Direction direction) {
// 判断是否能够辐射到结点(x, y)，如果不能就跳过
if (!canRadiating(currNode, input, x, y, direction)) return;
// 先尝试从Open队列中获取存在的node
Node node = findNodeInOpenQueue(x, y);
// 计算g值
int g = currNode.getG() + 1;
Node end = input.getEnd();
// 表示这是个新辐射的结点
if (node == null) {
// 计算h代价值
int h = (Math.abs(end.getX() - x) + Math.abs(end.getY() - y));
// 收尾的判断
if (isEndNode(x, y, end)) {
// 关联终点和其parent
node = end;
node.setParent(currNode);
node.setG(g);
node.setH(h);
} else {
// 创建被辐射的中间结点对象
node = new Node(x, y, currNode, g, h);
}
// 将新节点加到open队列
openQueue.add(node);
// 高亮展示
this.graphics.setColor(new Color(153, 255, 253));
this.graphics.fillRect(x * 8, y * 8, 8, 8);
this.graphics.setColor(Color.BLACK);
this.graphics.drawRect(x * 8, y * 8, 8, 8);
} else if (node.getG() > g) { // 辐射一个已存在于Open队列中的结点，重新评估其g代价值
// 当出现交叉辐射，辐射到原有的open结点时，若发现代价值g更小，
// 则更新g值，重新绑定父结点，这样总代价也会变小，再次加到open队列
node.setG(g);
node.setParent(currNode);
openQueue.add(node);
}
// 延缓执行，方便看清中间过程的动态效果
try {
Thread.sleep(50);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
/**
用当前结点坐标判断是否为终点
*/
private boolean isEndNode(int x, int y, Node end) {
return end.getX() == x && end.getY() == y;
}
/**
判断当前结点的指定邻结点能够被辐射
*/
private boolean canRadiating(Node currNode, Input input, int x, int y, Direction direction) {
// 先判断没有越界
if (x input.getCols() - 2 || y input.getRows() - 2) return false;
// 判断结点存在于Close列表中
// 注意该判断要在下面判断障碍物的逻辑之前执行，以优化性能
for (Node node : closeList) {
if (node.getX() == x && node.getY() == y) {
return false;
}
}
// 判断有障碍物的情况
// 注意，这里入参传入的是当前结点的坐标，而非邻结点！！
Ornament[] obstacles = MapUtil.face(input.getMap(), currNode.getX(), currNode.getY(), 2, direction);
if (obstacles == null) return false;
for (int i = 0; i < 4; i++) {
String type = obstacles[i].getType();
// 判断前面有河流、石头或者砖块就被阻挡
if (type.startsWith("R") || type.startsWith("S") || type.startsWith("B")) {
return false;
}
}
return true;
}
/**
从open队列中查找指定x和y坐标的已存在的结点
*/
private Node findNodeInOpenQueue(int x, int y) {
for (Node node : openQueue) {
if (node.getX() == x && node.getY() == y) {
return node;
}
}
return null;
}
}
动画演示
下面我们将采用动画的形式来演示下A星算法是如何进行结点辐射和选举的，以至于最终”蔓延“到目标结点。首先我们要停掉MyFrame中对游戏窗口的重绘线程，也就是注释掉startGame()方法调用的地方。这样以确保MyPanel中的paintComponent()方法只会在窗口被重绘时执行一次，以方便我们不断的在面板上不断绘制新的内容。看下MyPanel类中为此做的调整：
package com.pf.java.tankbattle;
import ...
public class MyPanel extends JPanel {
...
// 临时定义一个敌方智能坦克的成员变量引用
private EnemyTank smartEnemyTank;
public MyPanel(MyFrame frame, String[][] map) {
...
// 这里我们暂时只实例化一个敌方坦克，它是一个智能坦克
this.smartEnemyTank = EnemyTankFactory.getInstance().build(new EnemyTankConfig(EnemyType.PAWN, 32, 0, frame));
...
}
@Override
protected void paintComponent(Graphics g) {
super.paintComponent(g);
// 绘制网格
paintGrids(g);
// 绘制地图和坦克
doPaint(g);
// 这里我们采用了命令模式来封装最短路径规划到移动执行的整个流程
// 在当前的paint线程中，我们再新启一个线程来演示这种动画效果
Thread t = new Thread(() -> {
// 传入要执行以最短路径行驶到目的地的坦克，实例化一个迷宫输入对象，传入整个二维数组代表的地图、迷宫的起点和终点坐标位置，以及用于绘制动画效果的画笔对象
new MoveCommand(this.smartEnemyTank, new Input(this.map, 34, 2, 14, 26), this.getGraphics()).execute();
});
t.start();
}
...
}
我们一起来看下执行后的效果：
再看下MoveCommand命令的简单实现：
package com.pf.java.tankbattle.pattern.command.move;
import ...
public class MoveCommand implements Command {
private EnemyTank tank;
private Input input;
private Graphics graphics;
public MoveCommand(EnemyTank tank, Input input, Graphics graphics) {
this.tank = tank;
this.input = input;
this.graphics = graphics;
}
@Override
public void execute() {
new AStar().startRadiating(this.input, this.graphics);
}
}
完善MoveCommand
下面我们进一步完善MoveCommand，目标是能在游戏界面看到敌方坦克能智能的从迷宫的入口以最短路径行驶到出口这样一个效果。看下完善后的代码：
package com.pf.java.tankbattle.pattern.command.move;
import ...
public class MoveCommand implements Command {
private EnemyTank tank;
private Input input;
private Graphics graphics;
public MoveCommand(EnemyTank tank, Input input, Graphics graphics) {
this.tank = tank;
this.input = input;
this.graphics = graphics;
}
@Override
public void execute() {
Node end = new AStar().startRadiating(this.input, this.graphics);
// 说明没有通路，不执行
if (end.getParent() == null) {
// 释放该命令
tank.setMoveCommand(null);
return;
}
List path = new ArrayList();
path.add(end);
Node node = end.getParent();
// 从终点开始查找父结点，并添加到一个列表中
while (node != null) {
path.add(node);
node = node.getParent();
}
// 反向遍历path，并生成每个方向改变的step，用于后续执行
List steps = new ArrayList();
int size = path.size();
Direction currDirection = calcDirection(path.get(size - 1), path.get(size - 2));
int distance = 8;
for (int i = path.size() - 2; i > 0; i--) {
Direction nextDirection = calcDirection(path.get(i), path.get(i - 1));
if (nextDirection == currDirection) {
distance += 8;
} else {
steps.add(new Step(currDirection, distance));
distance = 8;
currDirection = nextDirection;
}
}
steps.add(new Step(currDirection, distance));
// 在TankThread中再新启一个线程来执行从起点到终点的行驶指令
Thread t = new Thread(() -> {
// 遍历每个步骤，执行坦克转向和移动
for (Step step : steps) {
tank.setDirection(step.getDirection());
for (int i = 0; i y1 ? Direction.DOWN : Direction.UP;
} else {
return x2 > x1 ? Direction.RIGHT : Direction.LEFT;
}
}
/**
* 用于执行最短路径上的每一个转向和行驶距离的步骤类
*/
class Step {
/** 当前方向 */
private Direction direction;
/** 要行驶的距离 */
private int distance;
public Step(Direction direction, int distance) {
this.direction = direction;
this.distance = distance;
}
public Direction getDirection() {
return direction;
}
public int getDistance() {
return distance;
}
}
}
相应的，我们在EnemyTank类中再加一个MoveCommand命令的成员变量，在外部给其设置一个命令对象后，可以在TankThread中执行它，而在MoveCommand内部，在执行完该命令后，就释放EnemyTank对它的引用：
package com.pf.java.tankbattle.entity.tank;
import ...
public class EnemyTank extends Tank {
...
private MoveCommand moveCommand;
// 省略构造器
...
public void init() {
tankThread = new Thread(() -> {
while (true) {
if (moveCommand != null) {
moveCommand.execute();
continue;
}
// 其他逻辑省略
...
}
});
}
...
public void setMoveCommand(MoveCommand moveCommand) {
this.moveCommand = moveCommand;
}
}
然后，我们恢复之前MyFrame中的startGame()方法调用的敌方，并在MyPanel中恢复前面为了演示A星算法的中间执行动画而做的代码调整。并在其构造器中创建完敌方智能坦克实例后，就为其设置一个new出来的MoveCommand命令对象：
this.smartEnemyTank = EnemyTankFactory.getInstance().build(new EnemyTankConfig(EnemyType.PAWN, 32, 0, frame));
this.smartEnemyTank.setMoveCommand(new MoveCommand(this.smartEnemyTank, new Input(this.map, 34, 2, 14, 26)));
同时，将之前为了演示A星中间动画而额外传入的Graphics画笔对象移除掉，涉及到该引用定义和使用地方都移除相应的代码，不要忘了，也一并移除Thread.sleep(millisecond)延迟执行的代码。
最后我们看下最终的游戏效果吧！
总结
通过本小节的实践，我们发现所谓的一些智能算法也并不是想象的那么复杂，只要我们勤于动手实践，做出一些有趣的例子。我们就能体会到算法设计者的别具匠心。也通过增加敌方坦克的智能，咱们写的坦克大战游戏也将更加有趣。还是那句话，学习的动力源于玩的心态，大家加油！
