Talk:Wall Smoothing/Implementations/Non-Iterative

Credits - Wall Smoothing/Implementations/Non-Iterative Old wiki page: WallSmoothing/NonIterative Original author(s): David Alves

From old wiki

For what it's worth, my published WallSmoothing method does use iteration, but will only loop a maximum of two times in any situation, I think. I just put the 25-loop limit on the iteration as a form of personal infinite-loop paranoia. I'll take a closer look at yours when the alcohol wears off... ;) -- Voidious

I added a line to the end of your method which prints out the value of g right before the function returns. It was always 26. Perhaps I'm not passing your method the right parameters? I can send you the code to check if you like. --David Alves

Yikes! I will look into this. I might be just ganking your method soon if that's the case... -- Voidious

Ok - as implemented in Dookious, I just ran a couple matches and the value of g is never greater than 2. Maybe something got lost in translation when I posted it on the wiki; I'll take a look later when I get a chance. Thanks for the heads up on that. If you want me to check the code, feel free to e-mail to me, my e-mails on the ContactInfo page. -- Voidious

---

Here's a version that's a bit cleaner to look at, if anyone is interested. It is geared for driving at a given heading, not toward a given point.

    HALF_PI = Math.PI / 2;
    WALKING_STICK = 120;
    WALL_MARGIN = 18;
    S = WALL_MARGIN;
    W = WALL_MARGIN;
    N = 600 - WALL_MARGIN;
    E = 800 - WALL_MARGIN;

    // angle = the angle you'd like to go if there weren't any walls
    // oDir  =  1 if you are currently orbiting the enemy clockwise
    //         -1 if you are currently orbiting the enemy counter-clockwise
    // returns the angle you should travel to avoid walls
    double smooth(double angle, int oDir) {
        angle = smoothWest(N - getY(), angle - HALF_PI, oDir) + HALF_PI;
        angle = smoothWest(E - getX(), angle + Math.PI, oDir) - Math.PI;
        angle = smoothWest(getY() - S, angle + HALF_PI, oDir) - HALF_PI;
        angle = smoothWest(getX() - W, angle, oDir);
        
        // for bots that could calculate an angle that is pointing pretty far
        // into a corner, these three lines may be necessary when travelling
        // counter-clockwise (since the smoothing above may have moved the 
        // walking stick into another wall)
        angle = smoothWest(getY() - S, angle + HALF_PI, oDir) - HALF_PI;
        angle = smoothWest(E - getX(), angle + Math.PI, oDir) - Math.PI;
        angle = smoothWest(N - getY(), angle - HALF_PI, oDir) + HALF_PI;
        
        return angle;
    }

    // smooths agains the west wall
    double smoothWest(double dist, double angle, int oDir) {
        if (dist < -WALKING_STICK * Math.sin(angle)) {
            return Math.acos(oDir * dist / WALKING_STICK) - oDir * HALF_PI;
        }
        return angle;
    }

-- Simonton

Well done, much cleaner then my prototype version I have bee working on, and with half the code. I guess I have a ways to go, think you can build a better wall distance function too? --Chase-san

Small notes there Simonton, it doesn't seem to work counter clockwise, and it kinda sticks in the upper left corner on approach. --Chase-san

Oops! I should know better than to adapt my code to something more standard without testing it first. There, try that :). Oh ... and what's a "wall distance function"? Oh wait ... the distance forward to a wall? Um, hold on a minute ... -- Simonton

Not sure, but Chase-san might be referring to the "orbital" wall distance style that a lot of bots use: assuming the enemy tank continues in a standard orbit, at what GF would it be when it hits a wall? CassiusClay and Dookious do it with brute force, checking every .01 GFs until they find a projected enemy location off the map. -- Voidious

Works great, minor problems in Genesis, but those are my fault. This method will soon probably replace all the other methods just cause its so much faster then the smallest but still small itself.

Another note, the method seems to act oddly at some stick sizes, have you tested more then 120? --Chase-san

No, that sounds strange. How much larger? -- Simonton

Actually no, I ran a test, it just seems i'm used to other kinds of smoothing. Its just working too well, making me think its not working correctly. --Chase-san

I just tested this code, it works better than almost all other wall smoothing functions I have tried, except for the persistent sticking bug Chase-san noted. I have seen the bot get stuck when going counter-clockwise in the upper-left corner, and possibly when going clockwise in the lower-right corner. Do you have any idea what is causing this? --AaronR

Hmm. I use a variation of this in WeeksOnEnd, so I can't run it right now to see (not enough time to create a bot to use it). I thought I tested it before ... maybe I can be of more help later, but probably not right away. -- Simonton

Thanks anyway. If you do go hunting for the bug, here is what I have figured out:

• It always occurs when going counter-clockwise.
• The bot can get stuck in any corner, but most frequently in the upper-left corner.
• When it does get stuck, the bot can sometimes escape by reversing direction, this is why the bug is not visible in a typical bot.

The easiest way I have found to reproduce this bug is to create a bot that always moves counter-clockwise and keep running rounds until it starts a round very close to or inside the smoothing radius in the upper-left corner, at which point it will just vibrate back and forth. If you then make the bot reverse direction, it may shoot off on a diagonal instead of moving clockwise normally - a response very similar to what happens in other wall-smoothing algorithms if you try to head in one direction with the angle and the other with the orientation.

-- AaronR

You could just program the bot, so that when your bot is within radius r (the smoothing radius) of the wall to move outside it, then allow the smoother to work as normal (though, this could lead to a pattern matcher catching on, though it is a rather small window). Since I assume this happens near the corners, move along the wall a little ways, not out into the field (it can look rather innocent if you move that way, even to a patternmatcher).

An easier way, though I doupt that there is an easy way to fix the bug in the method, without something of that sort anyway. Perhaps a check, and if within, use the radius to the wall your heading towards (maybe 8 less, to make up for velocity), make sure only to check if say, 5 or more within the radius, to allow room for error.

--Chase-san

Oh, wow, sorry, I totally forgot about this. I also never saw you latest post, AaronR. Um, I may be able to check this out tonight. By the way, if you look at the opening .battle file you'll see a way to specify the starting position of a bot, which sounds like an easier way to re-produce the bug :). -- Simonton

Alrighty. I was unable to replicate the getting stuck behavior, but I did find a bug. I should like you to add the three new lines above & let me know if it fixes your problem. -- Simonton

Well, it seems this "bug" was my fault all along. The code I was using looked like this:

  public void onScannedRobot(ScannedRobotEvent e) {
	double angle = smooth(getHeadingRadians(), -1);
	setBackAsFront(angle);
  }

So one quarter or so of the time the bot was doing exactly what I said before: "trying to head in one direction with the angle and the other with the orientation". As long as you feed the method legal input, it seems to work correctly. However, I found another bug: the stick size is too small, and some bots will frequently hit the second or third wall they encounter. Changing the stick size to the other common value of 160 removes this problem.

-- AaronR

Ah. That would do it. And you're right, that stick size is a bit small. 123 is the minimum to guarantee missing the wall, IF you never approach the wall at greater than a 90 degree angle (actually 122.something). If you are retreating from the enemy at the same time as approaching the wall, there will be times that you need a longer stick. Also, again, those three new lines above may be necessary depending on the way you calculate your desired angle, as mentioned in the new comments. Happy smoothing! -- Simonton

Angle Based version of face code

//no object creation or method calling if we can help it, need this to stay fast and rather memory unintensive
//px = position x
//py = position y
//angle = angle we are trying to travel
//direction = orbit direction (> 0 = clockwise, anything else is counter-clockwise)
//fw = field width
//fh = field height
//c2pd = orbit center to position distance
public static final double fastSmooth(double px, double py, double angle, int direction,
        double fw, double fh, double c2pd) {
    final double margin = 18;

    double stick = 150;
    if(c2pd < stick) stick = c2pd;

    double stickSq = stick*stick;

    double nx = px + stick*Math.sin(angle);
    double ny = py + stick*Math.cos(angle);

    if(nx >= margin && nx <= fw - margin && ny >= margin && ny <= fh - margin)
        return angle;

    /* TOP */
    if(ny > fh - margin || py > fh - stick - margin) {
        //System.out.println("top");
        /* RIGHT */
        if(nx > fw - margin || px > fw - stick - margin) {
            //System.out.println("right");
            if(direction > 0) {
                //smooth right
                stick = fw - margin - px;
                nx = fw - margin;
                ny = py - direction * Math.sqrt(stickSq - stick*stick);
                return Math.atan2(nx-px, ny-py);
            } else {
                //smooth top
                stick = fh - margin - py;
                nx = px + direction * Math.sqrt(stickSq - stick*stick);
                ny = fh - margin;
                return Math.atan2(nx-px, ny-py);
            }
        } else /* LEFT */ if(nx < margin || px < stick + margin) {
            //System.out.println("left");
            if(direction > 0) {
                //smooth top
                stick = fh - margin - py;
                nx = px + direction * Math.sqrt(stickSq - stick*stick);
                ny = fh - margin;
                return Math.atan2(nx-px, ny-py);
            } else {
                //smooth left
                stick = px - margin;
                nx = margin;
                ny = py + direction * Math.sqrt(stickSq - stick*stick);
                return Math.atan2(nx-px, ny-py);
            }
        }
        //smooth top
        stick = fh - margin - py;
        nx = px + direction * Math.sqrt(stickSq - stick*stick);
        ny = fh - margin;
        return Math.atan2(nx-px, ny-py);
    } else /* BOTTOM */ if(ny < margin || py < stick + margin) {
        /* RIGHT */
        if(nx > fw - margin || px > fw - stick - margin) {
            if(direction > 0) {
                //smooth bottom
                stick = py - margin;
                nx = px - direction * Math.sqrt(stickSq - stick*stick);
                ny = margin;
                return Math.atan2(nx-px, ny-py);
            } else {
                //smooth right
                stick = fw - margin - px;
                nx = fw - margin;
                ny = py - direction * Math.sqrt(stickSq - stick*stick);
                return Math.atan2(nx-px, ny-py);
            }
        } else /* LEFT */ if(nx < margin || px < stick + margin) {
            if(direction > 0) {
                //smooth left
                stick = px - margin;
                nx = margin;
                ny = py + direction * Math.sqrt(stickSq - stick*stick);
                return Math.atan2(nx-px, ny-py);
            } else {
                //smooth bottom
                stick = py - margin;
                nx = px - direction * Math.sqrt(stickSq - stick*stick);
                ny = margin;
                return Math.atan2(nx-px, ny-py);
            }
        }
        //smooth bottom
        stick = py - margin;
        nx = px - direction * Math.sqrt(stickSq - stick*stick);
        ny = margin;
        return Math.atan2(nx-px, ny-py);
    }

    /* RIGHT */
    if(nx > fw - margin || px > fw - stick - margin) {
        stick = fw - margin - px;
        nx = fw-margin;
        ny = py - direction * Math.sqrt(stickSq - stick*stick);
        return Math.atan2(nx-px, ny-py);
    } else /* LEFT */ if(nx < margin || px < stick + margin) {
        stick = px - margin;
        nx = margin;
        ny = py+direction * Math.sqrt(stickSq - stick*stick);
        return Math.atan2(nx-px, ny-py);
    }
    System.err.println("Something is really messed up here... (check your wall smoothing code!)");
    return angle;
}

— Chase-san 18:06, 9 August 2011 (UTC)