Robocode 高手的秘诀: 因数避墙法（factored wall avoidance）

要设计出一种算法，使您的机器人不会被困在角落里或者过多的偏离想要的移动方向，而且不会靠近墙，这是件很困难的事。 因数避墙法是一种简单的解决办法。在这篇小技巧中，David McCoy 将向您展示如何实现这项方便的技术。

我们只要对在 Tracking your opponents' movement中做的机器人加以补充，就能将因数避墙法添加到现有的或讨厌的移动算法中。这种方法将预想的方向和根据机器人和墙之间距离远近确定的安全方向作为因数试图找到最可能的方向。

我们先要给机器人添加常见数学算法使用的一些辅助方法。

calculateBearingToXYRadians() 方法使用 java.lang.Math 中的 atan2() 方法来计算从 sourceX,sourceY 到 targetX,targetY 的绝对方位，然后再把这个值转化为相对于 sourceHeading 的相对方位。

我们还需要 normalizeAbsoluteAngleRadians() 方法和 normalizeRelativeAngleRadians() 方法。

private static final double DOUBLE_PI = (Math.PI * 2);
private static final double HALF_PI = (Math.PI / 2);
public double calculateBearingToXYRadians(double sourceX, double sourceY,
    double sourceHeading, double targetX, double targetY) {
        return normalizeRelativeAngleRadians(
           Math.atan2((targetX - sourceX), (targetY - sourceY)) -
               sourceHeading);
    }
public double normalizeAbsoluteAngleRadians(double angle) {
   if (angle < 0) {
        return (DOUBLE_PI + (angle % DOUBLE_PI));
    } else {
        return (angle % DOUBLE_PI);
    }
}
public static double normalizeRelativeAngleRadians(double angle) {
    double trimmedAngle = (angle % DOUBLE_PI);
    if (trimmedAngle > Math.PI) {
        return -(Math.PI - (trimmedAngle % Math.PI));
    } else if (trimmedAngle < -Math.PI) {
        return (Math.PI + (trimmedAngle % Math.PI));
    } else {
        return trimmedAngle;
    }
}

回页首

接着，为了以相反方向导航，我们需要用一些辅助方法把 AdvancedRobot 类的功能扩展到允许倒行操作：

• getRelativeHeading() 方法将应付正确计算相对于机器人当前的方向的相对方向产生的额外开销。
  
• reverseDirection() 非常简单。它负责 direction 实例变量的开关和使机器人掉头。 请注意，由于减速需要时间，依据机器人的速度，在掉过头来之前最多会沿原来的方向再走 4 格。
  
• setAhead() 和 setBack() 方法将覆盖 AdvancedRobot 类中的同名方法。这两个方法会设置机器人对于目前方向的相对速度，必要的时候，还会调整 direction 实例变量。我们这么做的目的是要确保相对操作都与机器人当前的移动方向有关。
  
• setTurnLeftRadiansOptimal() 和 setTurnRightRadiansOptimal() 方法使机器人的方向转过的角度超过 (Math.PI / 2) 。您会希望这个方法和 adjustHeadingForWalls 方法（我们将在后面讨论）一起使用。
  

注：我没有使用 getter 和 setter 方法，而是直接存取 direction 实例变量。尽管通常这并非良好的编程习惯，但为了加快数据存取，在我的机器人代码中我一直都是直接存取的。

public double getRelativeHeadingRadians() {
    double relativeHeading = getHeadingRadians();
    if (direction < 1) {
        relativeHeading =
                normalizeAbsoluteAngleRadians(relativeHeading + Math.PI);
    }
    return relativeHeading;
}
public void reverseDirection() {
    double distance = (getDistanceRemaining() * direction);
    direction *= -1;
    setAhead(distance);
}
public void setAhead(double distance) {
    double relativeDistance = (distance * direction);
    super.setAhead(relativeDistance);
    if (distance < 0) {
        direction *= -1;
    }
}
public void setBack(double distance) {
    double relativeDistance = (distance * direction);
    super.setBack(relativeDistance);
    if (distance > 0) {
        direction *= -1;
    }
}
public void setTurnLeftRadiansOptimal(double angle) {
    double turn = normalizeRelativeAngleRadians(angle);
    if (Math.abs(turn) > HALF_PI) {
        reverseDirection();
        if (turn < 0) {
            turn = (HALF_PI + (turn % HALF_PI));
        } else if (turn > 0) {
            turn = -(HALF_PI - (turn % HALF_PI));
        }
    }
    setTurnLeftRadians(turn);
}
public void setTurnRightRadiansOptimal(double angle) {
    double turn = normalizeRelativeAngleRadians(angle);
    if (Math.abs(turn) > HALF_PI) {
        reverseDirection();
        if (turn < 0) {
            turn = (HALF_PI + (turn % HALF_PI));
        } else if (turn > 0) {
            turn = -(HALF_PI - (turn % HALF_PI));
        }
    }
        setTurnRightRadians(turn);
}

回页首

我们需要添加的最后一个方法是 adjustHeadingForWalls() 方法。

这个方法的前面一半根据机器人和墙的靠近程度选择 安全的 x 和 y 的位置（机器人当前的 x 或 y 位置，或者如果机器人靠近墙，则就是中心点）。方法的后面一半则计算距离“安全点”的方位，并把这个方位和依机器人离墙远近得到的预想方向都作为因数考虑在内。

可以使用 WALL_AVOID_INTERVAL 和 WALL_AVOID_FACTORS 常量来调整机器人对墙的担忧程度。

private static final double WALL_AVOID_INTERVAL = 10;
private static final double WALL_AVOID_FACTORS = 20;
private static final double WALL_AVOID_DISTANCE =
        (WALL_AVOID_INTERVAL * WALL_AVOID_FACTORS);
private double adjustHeadingForWalls(double heading) {
    double fieldHeight = getBattleFieldHeight();
    double fieldWidth = getBattleFieldWidth();
    double centerX = (fieldWidth / 2);
    double centerY = (fieldHeight / 2);
    double currentHeading = getRelativeHeadingRadians();
    double x = getX();
    double y = getY();
    boolean nearWall = false;
    double desiredX;
    double desiredY;
    // If we are too close to a wall, calculate a course toward 
    // the center of the battlefield.
    if ((y < WALL_AVOID_DISTANCE) ||
            ((fieldHeight - y) < WALL_AVOID_DISTANCE)) {
        desiredY = centerY;
        nearWall = true;
    } else {
        desiredY = y;
    }
    if ((x < WALL_AVOID_DISTANCE) ||
            ((fieldWidth - x) < WALL_AVOID_DISTANCE)) {
        desiredX = centerX;
        nearWall = true;
    } else {
        desiredX = x;
    }
    // Determine the safe heading and factor it in with the desired 
    // heading if the bot is near a wall
    if (nearWall) {
        double desiredBearing = 
           calculateBearingToXYRadians(x, 
                                       y, 
                                       currentHeading, 
                                       desiredX, 
                                       desiredY);
        double distanceToWall = Math.min(
                Math.min(x, (fieldWidth - x)),
                Math.min(y, (fieldHeight - y)));
        int wallFactor =
                (int)Math.min((distanceToWall / WALL_AVOID_INTERVAL),
                              WALL_AVOID_FACTORS);
        return ((((WALL_AVOID_FACTORS - wallFactor) * desiredBearing) +
                 (wallFactor * heading)) / WALL_AVOID_FACTORS);
    } else {
        return heading;
    }
}

回页首

其余的工作很容易。我们可以使用目前的导航算法，将得出的结果送入 adjustHeadingForWalls() 方法来避开墙。

为了保持简单，示例机器人（请参阅 参考资料下载添加这一技术所需的源代码）要求方向改变为零，从而试着沿直线移动。

public void run() {
    while(true) {
        setTurnRightRadiansOptimal(adjustHeadingForWalls(0));
        setAhead(100);
        execute();
    }
}

关于它就是这样了。简单，但有效。