Wall Smoothing/Implementations/Non-Iterative

Wall Smoothing Sub-pages:

Wall Smoothing - Implementations

Warning

This page assumes a good knowledge of Wall Smoothing. If you're not completely sure what it is, read that page first. =)

How it works

As far as I know, every method of Wall Smoothing published so far has used iteration. Due to the expensive operations involved (sin, cos, tan, atan, and sqrt), it would be best to avoid this. The code below started with me realizing that there's no reason to have to do Wall Smoothing using iteration, we can use the pythagorean theorem to find a wallsmoothed angle without using such costly operations.

Here's how it's done:

1. If the enemy is closer than the desired smoothing radius ("stick length"), then set the stick length to be equal to the distance to the enemy. More on why we do that later.
2. Project our destination point normally, either clockwise or counterclockwise. If it's on the drivable area of the field, just return that point.
3. Check which walls need to be smoothed, top or bottom and left or right. It gets a little tricky if two of them need to be smoothed.
4. If two walls need to be smoothed, check if we're going clockwise or counterclockwise. If we're going clockwise for example, and we're smoothing in the top right corner, we need to smooth against the right wall, since it's further clockwise than the top wall.
5. Make a triangle using our "stick" as the hypotenuse. One side will be a perpendicular dropped to the wall. The other side will be how far up or down the wall we need to go. Since we know the length of the hypotenuse and the perpendicular line segment that we dropped, we can calculate the third side.
6. Presto! Non-Iterative wall smoothing courtesy of our good friend Pythagoras.

You may wonder why step 1 is in there. As you can see in the image above, our bot (blue circle) is 100 units away from the enemy (red circle). Even though the stick length is set to 150, giving us the outer dim blue circle, our destinations are projected out only 100 units, because the enemy is closer than the stick length setting. The reason for this is shown in the right-hand image above. Since our wallsmoothed destinations are at the intersection of the gray lines and the dim blue circle (which has a radius equal to our stick length), there simply aren't any good wallsmoothed destinations that allow us to continue traveling clockwise. This algorithm would happily decide that a point must be found on the top wall, and would choose the intersection of the blue circle and the gray line. Although we asked for a clockwise destination, the algorithm would travel to far, and end up picking a point that makes us drive counter-clockwise around the enemy. By setting the stick length equal to the distance to the enemy when the stick is longer than the enemy distance, we ensure that we can always smooth clockwise or counterclockwise regardless of our position or the enemy's.

Cool stuff

• At best, this method will use 2 slow operations: 1 sin and 1 cos. (That's if no wallsmoothing is needed)
• At worst, it will use 3 slow operations: 1 sin, 1 cos, and 1 sqrt. That's all!
• This method returns a precise answer. Your wall smoothed destination will be exactly 18 units from the wall, and exactly 150 pixels from your position. Or whatever you change those values to be. =)

The code

// orbitCenter is the point we are orbiting, position is our current position, direction is our orbit direction (clockwise or counterclockwise), distance to orbit center is the distance to the orbit center.
public Point2D.Double fastWallSmooth(Point2D.Double orbitCenter, Point2D.Double position, double direction, double distanceToOrbitCenter){
	final double MARGIN = 18;
	final double STICK_LENGTH = 150;
	
	double fieldWidth = getBattleFieldWidth(), fieldHeight = getBattleFieldHeight();
	
	double stick = Math.min(STICK_LENGTH, distanceToOrbitCenter);
	double stickSquared = square(stick);
	
	int LEFT = -1, RIGHT = 1, TOP = 1, BOTTOM = -1;
	
	int topOrBottomWall = 0;
	int leftOrRightWall = 0;
	
	double desiredAngle = Utils.normalAbsoluteAngle(absoluteAngle(position, orbitCenter) - direction * Math.PI / 2.0);
	Point2D.Double projected = projectPoint(position, desiredAngle, stick);
	if(projected.x >= 18 && projected.x <= fieldWidth - 18 && projected.y >= 18 && projected.y <= fieldHeight - 18)
		return projected;
	
	if(projected.x  > fieldWidth - MARGIN || position.x  > fieldWidth - stick - MARGIN) leftOrRightWall = RIGHT;
	else if (projected.x < MARGIN || position.x < stick + MARGIN) leftOrRightWall = LEFT;
	
	if(projected.y > fieldHeight - MARGIN || position.y > fieldHeight - stick - MARGIN) topOrBottomWall = TOP;
	else if (projected.y < MARGIN || position.y < stick + MARGIN) topOrBottomWall = BOTTOM;
	
	if(topOrBottomWall == TOP){
		if(leftOrRightWall == LEFT){
			if(direction > 0)
				//smooth against top wall
				return new Point2D.Double(position.x + direction * Math.sqrt(stickSquared - square(fieldHeight - MARGIN - position.y)), fieldHeight - MARGIN);
			else
				//smooth against left wall
				return new Point2D.Double(MARGIN, position.y + direction * Math.sqrt(stickSquared - square(position.x - MARGIN)));
				
		} else if(leftOrRightWall == RIGHT){
			if(direction > 0)
				//smooth against right wall
				return new Point2D.Double(fieldWidth - MARGIN, position.y - direction * Math.sqrt(stickSquared - square(fieldWidth - MARGIN - position.x)));
			else 
				//smooth against top wall
				return new Point2D.Double(position.x + direction * Math.sqrt(stickSquared - square(fieldHeight - MARGIN - position.y)), fieldHeight - MARGIN);
			
		}
		//Smooth against top wall
		return new Point2D.Double(position.x + direction * Math.sqrt(stickSquared - square(fieldHeight - MARGIN - position.y)), fieldHeight - MARGIN); 
	} else if(topOrBottomWall == BOTTOM){
		if(leftOrRightWall == LEFT){
			if(direction > 0)
				//smooth against left wall
				return new Point2D.Double(MARGIN, position.y + direction * Math.sqrt(stickSquared - square(position.x - MARGIN)));
			else
				//smooth against bottom wall
				return new Point2D.Double(position.x - direction * Math.sqrt(stickSquared - square(position.y - MARGIN)), MARGIN);
		} else if(leftOrRightWall == RIGHT){
			if(direction > 0)
				//smooth against bottom wall
				return new Point2D.Double(position.x - direction * Math.sqrt(stickSquared - square(position.y - MARGIN)), MARGIN);
			else
				//smooth against right wall
				return new Point2D.Double(fieldWidth - MARGIN, position.y - direction * Math.sqrt(stickSquared - square(fieldWidth - MARGIN - position.x)));
				
		}
		//Smooth against bottom wall
		return new Point2D.Double(position.x - direction * Math.sqrt(stickSquared - square(position.y - MARGIN)), MARGIN);
	}
	
	if(leftOrRightWall == LEFT){
		//smooth against left wall
		return new Point2D.Double(MARGIN, position.y + direction * Math.sqrt(stickSquared - square(position.x - MARGIN)));
	} else if(leftOrRightWall == RIGHT){
		//smooth against right wall
		return new Point2D.Double(fieldWidth - MARGIN, position.y - direction * Math.sqrt(stickSquared - square(fieldWidth - MARGIN - position.x)));
	}
	
	throw new RuntimeException("This code should be unreachable. position = " + position.x + ", " + position.y + "  orbitCenter = " + orbitCenter.x + ", " + orbitCenter.y + " direction = " + direction);
}

public static Point2D.Double projectPoint(Point2D.Double origin, double angle, double distance){
	return new Point2D.Double(origin.x + distance * Math.sin(angle), origin.y + distance * Math.cos(angle));
}

public static double absoluteAngle(Point2D.Double origin, Point2D.Double target) {
    return Math.atan2(target.x - origin.x, target.y - origin.y);
}

public double square(double x){
	return x*x;
}