Talk:Wall Avoidance

From old wiki

I need serious help with this wall avoidance issue. This is the weakest spot of Marshmallow at the moment. Is there some simple strategies I can use that doesn't end in the robot oscillation, quite predictably, against the walls? -- PEZ

The easiest way I've found to avoid walls is to use a movement method that picks an (x,y) coordinate to move to. As long as the coordinate you pick is within the rectangle (18.0, 18.0)-(battlefieldwidth - 18.0, battlefieldheight - 18.0) you won't hit any walls. You can make the wall margin greater than 18.0 to account for the fact that bots make wide turns at high speed. Code for moving to an (x,y) coordinate is readily available. There is an extremely small piece of code to do this in DuelistMicro's source, (It has to fit into a microbot, remember? :-P) though it occaisionally drives the bot in the wrong direction (about once per round at 800x600). As far as I know this is the smallest possible code. -- David Alves

---

Has anyone tried David David McCoy's WallAvoidance method at developerWorks? It works by seeing if it is necessary to adjust for walls, and if it is necessary it factors in a bearing to the middle of the BattleField. It seems to work quite well, but sometimes seems to go totally the wrong way... -- Jomel

---

Somewhat depending on your movement system the following piece of code (which I found the first time in Cigaret I think) could make for a huge improvement in wall avoidance:

setMaxVelocity(Math.abs(getTurnRemaining()) < 40 ? preferredVelocity : 0.1);

You need to do this almost every turn. The idea here is to push the brake pedal hard if you find yourself having to make a really sharp turn. I'm working with a new movement system for Marshmallow, somewhat on the basis of an AngleGenerator. This allows me to make movement descisions very often and makes for a very fluid movement. With this code plugged in I hit the wall less than 2% of the rounds. Without it I hit the wall about 5 times every round. -- PEZ

---

Any idea why this doesn't work:

if (getX()<20 || getY()<20 || getX()>getBattleFieldWidth()-20 || getY()>getBattleFieldHeight()-20) {
    if (nearwall=false) {
        direction*=-1;
        nearwall=true; out.println("Near wall");
    }
    else {
        out.println("Still near wall");
    }
}
else {
    nearwall=false;
}

nearwall is set to false originally, and this is the first thing in the run method. afterwards it goes ahead(100*direction). The onscannedrobot keeps it perpedicular. When i run it it hits walls, it notices when it is "still near wall", but it never says "near wall", so never changes direction until it crashes (onHitWall changes direction too) -- Tango

if your distance is less then 18 to the wall you just hit it, because 2*18 is the length of your robot. so if you have for example a distance of 25 to a wall and you are moving with velocity 8 against the wall you will have a distance of 25-8=17 the next tick (this means you just hit the wall). as a result the chance that you are once in the range of 18-20 to a wall is really small compared to all possible situations you will hit the wall in the next tick (especially if you are moving with full speed). have a look at how Kawigi's bots do this (at least some of them) they calculate their position for the next tick and then check if this is a "dangerous" position. -- rozu

I'm working on a whole new movement system, but i just wanted to try this. The new one will use Rectange2D.contains. So the best way to improve this system is to increase the 20. I'll give 30 a try, 18+8=26, so 30 seems a good buffer. -- Tango

No, it seems that wasn't the problem. I even tried it with 50 and it didn't work. It's not that it's discovering it's near the wall too late, it's the fact that it is only running the "still near wall" code, and not the "near wall" code. (i made the distinction so it wouldn't just go backwards and fowards near the wall, and would instead wait until it was away from the wall before starting again) -- Tango

What I generally do is project my movement forward (i.e. getX() + Math.sin(getHeadingRadians())*currentDirection*30 or something) and see if that point is inside the field rectangle (it doesn't matter if you're close to the wall if you're not going toward it) -- Kawigi

Yeah, i plan to do something like that when i get around to a new movement system, i'm just trying to work out why this one doesn't work, to try and improve my java knowledge. -- Tango

If you're using ahead() and not setAhead() then your method isn't interrupting until you hit the wall, and that's the only time the remainder has a chance to look and actually see if you're near a wall. -- Kuuran

That still doesn't explain why the nested if never comes up true (ie. why it always prints "still near wall" and never "near wall". -- Tango

You used an assignment instead of a conditional. -- Kuuran

So i did, thankyou. All this for want of an equals sign... -- Tango

It's a common pitfall for all C based languages (and other languages too where you can use an assignment as an expression). In your case the compiler would have cought it if it wasn't that the variable involved is a boolean. One way to avoid this is to use the unary not operator, !, when testing booleans. Like so:

if (!nearwall) { ...

This can be read as "if not nearwall" which better expresses what you intend and thus is better code. -- PEZ

I actually knew that... not sure why i didn't use it... :-/ -- Tango

whats this WallSmoothing

Watch Shadow and SandboxDT. See how they move as the approach the wall? Thats wall smoothing. -- jim

---

I'm trying WallAvoidance with a CustomEvent. Anyone done this already? -- Qetu

Yeah, i worked on this for quite a while but never quite managed to get it to work for me. The problem i found was that although you could get it to work successfully in not hitting the walls, it tended to degrade my performance against any wall segmenters (or pattern matchers to a lesser extent). I rightly or wrongly concluded that this was because of the instantanious nature with which the wall avoidance was initiated, and that it involved an almost complete change of movement pattern. I suppose you could write more complex event handlers to implement an approximation to WallSmoothing, but i concluded it was easier to actually check the projected destination of my robot and adjust accordingly to avoid the problem, rather than trying to deal with it once the problem had arisen. Prevention is better than cure, or so they say anyway. Good luck to you... --Brainfade

Righto! Prevention is better than cure. -- PEZ

the two good methods seem to be: create a rectangle slightly smaller than the battlefield 1. bounce if your predicted posistion is outside of rectangle a 2. wall smooth if your predicted posistion is outside of recangle a

Just to add to the section, the following code does wall avoidance with custom events. As an example, i just made the robot to look at the center of the field and move ahead a bit whenever it is very near the wall. The code can be suitably modified to do WallSmoothing as well.

class NearWallEvent extends Condition
{
    private AdvancedRobot bot;
    private double minDistance;
    private double battleFieldWidth;
    private double battleFieldHeight;
    
    public NearWallEvent(AdvancedRobot aRobot)
    {
        this.bot = aRobot;
        this.minDistance = this.bot.getHeight();
        this.battleFieldWidth = this.bot.getBattleFieldWidth();
        this.battleFieldHeight = this.bot.getBattleFieldHeight();
    }
    
    public boolean test()
    {
        if(Math.min(this.bot.getX(), this.battleFieldWidth - this.bot.getX())<this.minDistance)
            return true;
        else if(Math.min(this.bot.getY(), this.battleFieldHeight - this.bot.getY())<this.minDistance)
            return true;
        return false;
    }
}

public void onCustomEvent(CustomEvent ce)
{
    Condition condition = ce.getCondition();
    if(condition instanceof NearWallEvent)
    {
        this.stop();
        AXFUtil.MovementMethods.lookAt(this, this.battleFieldWidth/2, this.battleFieldHeight/2);
        this.ahead(this.botHeight);
        this.resume();
    }        
}

-- AxialXForm

---

Yet another "any idea why this code doesn't work"?:

if(!field.contains(getX() + getVelocity()*Math.sin(getHeadingRadians()),getY() + getVelocity()*Math.cos(getHeadingRadians()))) { ahead= -ahead ; } setAhead(ahead*md);

where ahead is either 1 or -1, and md is a constant. My bot seems to vibrate and get stuck(won't ever come off) on the wall. -- Nantuko_Primus

• • Now that I have read your whole question: It takes you 5 ticks to slow down, during which you travel 8 + 6 + 4 + 2 + 0 pixels. At some point I would guess you get more than one pixel inside your boundary (I assume field is smaller than the whole field) and you oscillate. You oscilate because when your velocity is zero you are using getX() and getY() to see if you are out of bounds. It is possible to do this with velocities larger that zero if you are in the corners too. -- jim

Why not do:

		if(!field.contains(getX() + ahead*md*Math.sin(getHeadingRadians()),getY() + ahead*md*Math.cos(getHeadingRadians()))) {
			ahead= -ahead ;
		}
		setAhead(ahead*md);

or something like that? (I don't know what md is, maybe you'd want to use a smaller number). The problem is that when you change ahead, the sign of the velocity doesn't change for several more turns, what's important is what direction you're trying to go. -- Kawigi

Thanks! I realized the problem in Spanish class today. Thanks for the help though. -- Nantuko_Primus

---

Why don't use AntiGravityMovement - that's very simple (you don't need to think about other algorithms - this not only avoids walls, but also other robots, and can be useful in targeting)? A good AntiGravity snippet is here: Hanji/AGravEngine Hanji/GravPoint -- Ph

My nearWall() function isn't working. Could someone tell me why? Here it is:

public boolean nearWall() {
		if(dir==-1){
		    if(getX() + 100 >= getBattleFieldWidth() && getHeading() > 270 - 45 && getHeading() < 270 + 45)
		    return true;
		    if(getX() - 100 <= 0 && getHeading() > 45 && getHeading() < 135)
		    return true;
		    if(getY() + 100 >= getBattleFieldHeight() && getHeading() > 180 - 45 && getHeading() < 180 + 45)
		    return true;
		    if(getY() - 100 <= 0 && getHeading() > 360 - 45 && getHeading() < 45)
		    return true;
	    }
	else{
		if(getX() + 100 >= getBattleFieldWidth() && getHeading() > 45 && getHeading() < 135)
		return true;
		if(getX() - 100 <= 0 && getHeading() > 270 - 45 && getHeading() < 270 + 45)
		return true;
		if(getY() + 100 >= getBattleFieldHeight() && getHeading() > 360 - 45 && getHeading() < 45)
		return true;
		if(getY() - 100 <= 0 && getHeading() > 180 - 45 && getHeading() < 180 + 45)
		return true;
	}
		return false;
	}

dir

is set to either 1 or -1 and I use it to determine whether I am going forward or backward. nearWall() tells me if I am about to crash. When it returns true, I do

dir=-dir;

. WHy does it mess up? --Bayen (edit: it's fixed now)

I'm going to take a guess here that it seems to freeze instead of going backwards. You need to adjust the if block so that it doesn't check for the first set of conditions if you are in reverse. As it is, I expect it will get near the wall while going foward, hit reverse, still be near the wall, hit reverse again, and keep reversing direction until the transmission drops out. -- Martin

Thanks Martin, that fixed it up completely! I went back and changed the code to the correct version --Bayen

private static final double northeast =  45.0;
private static final double southeast = 135.0;
private static final double southwest = 225.0;
private static final double northwest = 315.0;

public static boolean isInRange( double min, double value, double max )
{
	return ( ( min <= value ) && ( value <= max ) );
}

public static boolean isNearWall( double x, double y, double heading, double velocity, double proximity, double maxX, double maxY )
{
	boolean isNearWall;
	double minX = proximity;
	double minY = proximity;
	maxX -= proximity;
	maxY -= proximity;


	if( isInRange( minX, x, maxX ) && isInRange( minY, y, maxY ) ) isNearWall = false;
	else if( velocity == 0.0 ) isNearWall = false;
	else if( velocity > 0.0 )
	{
		if( x > maxX && isInRange( northeast, heading, southeast ) ) isNearWall = true;
		else if( y < minY && isInRange( southeast, heading, southwest ) ) isNearWall = true;
		else if( x < minX && isInRange( southwest, heading, northwest ) ) isNearWall = true;
		else if( y > maxY && !isInRange( northeast, heading, northwest ) ) isNearWall = true; // not in alternate range
		else isNearWall = false;
	}
	else
	{
		if( x < minX && isInRange( northeast, heading, southeast ) ) isNearWall = true;
		else if( y > maxY && isInRange( southeast, heading, southwest ) ) isNearWall = true;
		else if( x > maxX && isInRange( southwest, heading, northwest ) ) isNearWall = true;
		else if( y < minY && !isInRange( northeast, heading, northwest ) ) isNearWall = true; // not in alternate range
		else isNearWall = false;
	}


	return isNearWall;
}

There is some food for thought. I doubt it is code size friendly, but maybe so, and it's more readable to me. I did not test it. -- Martin

One more comment (now that I am back from the dentist): 200 seems a really high number. On an 800x600 field you will be bouncing around in a 400x200 space, 1/6th the size of the arena. Slamming the brakes (or reverse) from max velocity gives you 12 units of travel. You don't need much more than that (if any). -- Martin

Besides the 12 units, you need one extra tick (=8 units) spare. Lets assume that you are at 12.1 units from the wall, you just continue until the next tick and only then hitting the brakes (at 4.1 units from the wall) which is to late. Instead of evaluating your current position, I rather evaluate your future position. In that case the problem with 'close to the wall, but already reversing' is solved automatically. I use(d) something like this:

playField = new Rectangle2D.Double( 18, 18, getBattleFieldWidth() - 36, getBattleFieldHeight() - 36);
// currDirection is 1 if going forwards, -1 if going backwards
myHeading = getHeadingRadians();
myCheckDistance = WALLCHECK * currDirection;   // WALLCHECK = 20
// calculate future position (very short BlindMansStick)
newposx = myPos.getX() + Math.sin( myHeading) * myCheckDistance;
newposy = myPos.getY() + Math.cos( myHeading) * myCheckDistance;
// if future position not in field, bounce
if (!playField.contains( newposx, newposy)) {
    switchDir = true;
}

You have to put it in a function yourself, and change some variables to your own. I just quickly copied it from an older source. -- GrubbmGait

I originally said 20 units but 'corrected' myself with 12. You are right. -- Martin

Some Ideas

-- Iterative technique --

I pull these from my memory of some of the offerings on Old-RoboWiki. Use a wall-stick to project point in front of you some distance. If it falls outside the bounds of the current arena, adjust the direction of your wall-stick either clockwise (+1 latDir) or counterclockwise (-1 latDir)

//May be attributed to PEZ
static double wallSmooth(Point center, int velDir, double heading, int latDir) {
    //Adjust the heading if going backwards
    heading += (velDir-1)/2*Helpers.PI;
    int counter = 0;
    while(!arena.contains(project(center, WALL_STICK, heading))) {
        heading += 0.01 * latDir;
    }
    return Utils.normalAbsoluteAngle(heading);
}

A refinement of my post on the prior wiki
-- Single-Shot Smoothing --

    //Given some point in the arena, and some heading, how long is the ray cast to the wall in front of you
    //This returns a measurement of mega-pixels given a 600 X 800 arena. :)

	static double calcWallSpace(final Point eCenter, double eGoing) {
		eGoing = Utils.normalAbsoluteAngle(eGoing);
		final double wallDistLat = eGoing < Helpers.PI ? (PLAY_WIDTH+18d-eCenter.getX()) / (Helpers.cos((Helpers.PI/2d - eGoing)))
			: eCenter.getX() / (Helpers.cos((3d*Helpers.PI/2d - eGoing)));
		eGoing = Utils.normalRelativeAngle(eGoing);
		final double wallDistVirt = Math.abs(Utils.normalRelativeAngle(eGoing)) < Helpers.PI / 2d  ?
				(PLAY_HEIGHT+18d-eCenter.getY()) / (Helpers.cos(eGoing)) : eCenter.getY() / (Helpers.cos(Helpers.PI - eGoing));
		 return(float)(Math.min(wallDistLat, wallDistVirt) / MAX_DIST);
	}
    //Given same data as iterative example
    //As written, will have no effect on desired absolute heading if distance to forward wall is greater than 200 pixels (0.2 MP) in a standard arena

    //This inverts wallSpace measurement and cubes it in order to maintain a tight enough turning curve
	
	static double wallSmooth(final Point center, final int velDir, double heading, final int latDir) {
		final double wallSpace; 		
		final Point future = project(center, velDir * 165d, heading);
   
    // Note:: PlayHeight = getBattleFieldHeight() - 36
		boolean top = future.getY() > PLAY_HEIGHT + 18d,
			bottom = future.getY() < 18,
			left = future.getX() < 18,
			right = future.getX() >= PLAY_WIDTH + 18d;
		//NOTE: I invert the heading for negative velocities in the next line
		final double wallSpaceFact =
			(1d - (wallSpace=Math.min(0.2d, calcWallSpace(center, Utils.normalAbsoluteAngle((heading = (heading + (velDir-1)/2 * Helpers.PI))))) * 5.2d)*wallSpace*wallSpace);
		double desiredAngle = heading;
		
		switch(latDir) {
			case 1:
				if(top && right) top = false;
				if(left && top) left = false;
				if(bottom && left) bottom = false;
				if(right && bottom) right = false;
				
			
				if(top) desiredAngle += Utils.normalRelativeAngle(Helpers.HALF_PI - heading) * wallSpaceFact;
				else if(right) desiredAngle += Utils.normalRelativeAngle(Helpers.PI - heading) * wallSpaceFact;
				else if(bottom) desiredAngle += Utils.normalRelativeAngle(Helpers.THREE_OVER_TWO_PI - heading) * wallSpaceFact;
				else if(left) desiredAngle += Utils.normalRelativeAngle(Helpers.TWO_PI - heading) * wallSpaceFact;
				
				break;
			case -1:
				if(top && right) right = false;
				if(left && top) top = false;
				if(bottom && left) left = false;
				if(right && bottom) bottom = false;
				
				if(top) desiredAngle += Utils.normalRelativeAngle(Helpers.THREE_OVER_TWO_PI - heading) * wallSpaceFact;
				else if(right) desiredAngle += Utils.normalRelativeAngle(0d - heading) * wallSpaceFact;
				else if(bottom) desiredAngle += Utils.normalRelativeAngle(Helpers.HALF_PI - heading) * wallSpaceFact;
				else if(left) desiredAngle += Utils.normalRelativeAngle(Helpers.PI - heading) * wallSpaceFact;
				
				break;
			default: System.out.println("quit it please");
				break;
		}
		
		return Utils.normalAbsoluteAngle(desiredAngle);
	}

Both of these methods take the same parameters and result in an absolute desired angle of travel so as to avoid the wall with the desired lateral direction relative to the enemy.