Talk:Escape Envelope

From Robowiki
Revision as of 08:41, 22 May 2009 by Robobot (talk | contribs) (Robobot 0.1 : correcting user page links)
Jump to navigation Jump to search

From old wiki's Escape Envelope page

There was an intresting discussion in robocoderepository. This is what I want to improve and dicusss. I hope you also find it usefull. -- SSO


Paul wrote: If the opponents bot is distance "d" away when it fires a bullet at speed "Vb" ...

If you are running towards it you will be hit at a distance of: d*Vb/(Vb+8) - we can call this minD

If you are running away from the enemy you will be hit at a distance of: d*Vb/(Vb-8) - we can call this maxD


this should be minD = d*Vr/(Vb + Vr), and maxD = d*Vr/(Vb - Vr) ? -Russ


The radius of the envelope is: (maxD - minD)/2

The position of the center from the enemy is: (maxD + MinD)/2


these two formulas are backwards . . . -Russ


for a 3.0 power bullet (Vb = 11): Radius = d*1.544, center = d*2.122

for a 1.0 power bullet (Vb = 17) Radius = d*0.6044, center = d*1.388


Little bit of implementation

public class MEnvelope extends Ellipse2D.Double{
  private double enemyDistance = 0.0;
  private double bulletSpeed = 0.0;
  private MBotV3 bot = null;
  public MEnvelope(AdvancedBot bot, double bulletSpeed) {
    this.bot = bot;

    this.enemyDistance = bot.getEnemy().getDistance();
    this.bulletSpeed = bulletSpeed;
    x = bot.getEnemy().x/2;
    y = bot.getEnemy().y/2;
    width = getDistanceMax(bot.getEnemy().getSpeed());
    height = getDistanceMin(bot.getEnemy().getSpeed());
  }
  double getDistanceMin(double speed){
   double dist = enemyDistance*bulletSpeed/(bulletSpeed +speed);
   return dist;
  }
  double getDistanceMax(double speed){
   double dist = enemyDistance*bulletSpeed/(bulletSpeed -speed);
   return dist;
  }

  public String toString(){
    return "Ellipse[" +(int)x +", "+(int)y+", "+(int)width+", "+(int)height+"]";
  }
}

Comments & improvements & example use?

Very, very interesting! Some of my bots use something similar, though I call it EscapeArea there. I use it both for dodging and for aiming in Marshmallow and my contribution to Princess is what I call EscapeAreaMovement. The difference between EscapeArea and EscapeEnvelope is mainly that I use a Polygon instead of an Ellipse and that I use a brute force way of constructing it (because I don't manage the trig needed to think something like the above up). Also I intersect the EscapeArea with the battle field boundaries so that I get rid of the part that's outside the field (if any). -- PEZ

This is a discussion we had some time ago in the RobocodeRepostory. Note that you can make it simpler, since the EscapeArea is not an ellipse, but a circumference (even if the starting point for the movement is not in the center of it). -- Albert

Can we have the link to the original discussion thread pasted here please? -- PEZ

The title is the "shape of the escape envelope" and the link is http://robocoderepository.com/jive/thread.jsp?forum=18&thread=1052&hilite=true&q=envelope&start=0#8321 --SSO

Thanks. And thanks for the little bit of implementation. It looks like I could use it instead of my brute EscapeArea thingy. =) Should be reasonably easy to crop it with the battle field I guess. -- PEZ


It seems like a targeting algorithm related to this may be interesting to be implemented for melee. A few things might be a little 'imperfect', but I think it would be effective in melee all the same. The approach I was thinking of is a sort of 2-D statistical sort of thing. I was thinking of modeling the escape area as a rotated square (for simplicity in storing data) instead of the circle described above. Basically fire waves like I would with any statistical gun, and when they hit, keep not the bearing in mind, but their location relative to where they were when I fired the wave and also relative to the direction they were facing when I fired. Keep a set of 'squares' in a sort of stat buffer (probably segmented on distance, raw velocity or absolute velocity, and acceleration) and when it comes time to fire, make a non-rotating square at the center of each 'bucket' for the current state of the robot, each with a 'value' equal to either the percentage of times they have been in that sector (rolling average) or the total number of times they ended up there (sum stats, like FloodMini). Then try a set of bearings to fire at in the square, and pick the bearing that intersects the highest sum of values of squares. This seems like a good way to model a guess-factor-like targeting when the opponent may or may not be moving relative to you. Does this sound like a plausible system? -- Kawigi

Definately. If you can squeeze it into a minibot the guns shouldn't be all that bad in 1v1 either. -- PEZ

It would sort of be related to guess-factor targeting in the way that absolute pattern-matching is related to relative patternmatching. -- Kawigi


I am currently working on something to this effect. I call it GuessFactor2D targeting, and what it basically does is draw the escape envelope around the target, which varies based on velocity and the time until impact, and then calculates the guess factor it takes both parallel to its heading and perpendicular to it. These statistics can then be extrapolated into a prediction based on both guess factors and it's current heading. This is far more exact than guess factoring, and works very well in basic pattern matching (with tweaking it may get even better, but so far it gets nearly 100% hits on spinbot and walls). The big difference is that GF targeting makes a few fatal assumptions that the bot:

  1. is always perpendicular to you
  2. is moving in a curve with a radius equal to the distance from you
  3. can move with an instant velocity of 8 backwards or forwards

By extrapolating data into two dimensions and checking it with regards to heading, we get a much better profile of movement all movements, whether perpendicular or otherwise. -- Jokester

I disagree that GuessFactorTargeting makes those assumptions (some nano-pattern-matchers do, however), but I think this is a good idea, particularly if you can effectively find the best shot bearing that intersects the most hits. I was working on something like this for Fhqwhgads at some point in time, and I used the Java AffineTransform class to help me translate things. At some point, however, I found some fundamental problem with what I was doing and ditched it (I don't remember what it was, but it sounds like you have it basically worked out). -- Kawigi

From old wiki's Escape Area page

A variant of EscapeEnvelope. Marshmallow uses it for both dodging and aiming. Feel free to use this code. I only ask you to give me credit if you do since I worked quite a while with getting it to work. -- PEZ

The first function returns the Area in which the target probably will move during the time the bullet travels, cropped so that it doesn't include any area outside the battle field. The second functions returns an array with the relative angles to the edges of the area from the gunners point of view.

    static Area escapeArea(Point2D gunLocation, Point2D targetLocation, double forwardAngle,
        double backwardAngle, Rectangle2D battleField, double bulletPower, double targetVelocity) {
        double distance = gunLocation.distance(targetLocation);
        double maxDistance = targetVelocity * travelTime(distance, bulletVelocity(bulletPower));
        double bearingToGun = pointsToAngle(targetLocation, gunLocation);
        Area escapeArea;
        Point2D point = new Point2D.Double();
        Polygon escapePolygon = new Polygon();
        toLocation(bearingToGun, 5.0, targetLocation, point);
        escapePolygon.addPoint((int)point.getX(), (int)point.getY());
        toLocation(bearingToGun - forwardAngle, maxDistance, targetLocation, point);
        escapePolygon.addPoint((int)point.getX(), (int)point.getY());
        toLocation(bearingToGun - 90.0, maxDistance, targetLocation, point);
        escapePolygon.addPoint((int)point.getX(), (int)point.getY());
        toLocation(bearingToGun - (180.0 - backwardAngle), maxDistance, targetLocation, point);
        escapePolygon.addPoint((int)point.getX(), (int)point.getY());
        toLocation(bearingToGun - 180.0, 5.0, targetLocation, point);
        escapePolygon.addPoint((int)point.getX(), (int)point.getY());
        toLocation(bearingToGun + (180.0 - backwardAngle), maxDistance, targetLocation, point);
        escapePolygon.addPoint((int)point.getX(), (int)point.getY());
        toLocation(bearingToGun + 90.0, maxDistance, targetLocation, point);
        escapePolygon.addPoint((int)point.getX(), (int)point.getY());
        toLocation(bearingToGun + forwardAngle, maxDistance, targetLocation, point);
        escapePolygon.addPoint((int)point.getX(), (int)point.getY());
        escapeArea = new Area(escapePolygon);
        escapeArea.intersect(new Area(battleField));
        return escapeArea;
    }

    static double[] escapeMinMaxAngles(Point2D gunLocation, Point2D targetLocation, Area escapeArea) {
        double[] angles = new double[2];
        double min = java.lang.Double.POSITIVE_INFINITY;
        double max = java.lang.Double.NEGATIVE_INFINITY;
        double bearingToTarget = pointsToAngle(gunLocation, targetLocation);
        PathIterator pathIterator = escapeArea.getPathIterator(null);
        double[] points = new double[6];
        Point2D point = new Point2D.Double();
        while (!pathIterator.isDone()) {
            int type = pathIterator.currentSegment(points);
            if (type != java.awt.geom.PathIterator.SEG_CLOSE) {
                point.setLocation(points[0], points[1]);
                double angle = pointsToAngle(gunLocation, point);
                angle = normalRelativeAngle(angle - bearingToTarget);
                if (angle < min) {
                    min = angle;
                }
                if (angle > max) {
                    max = angle;
                }
            }
            pathIterator.next();
        }
        angles[0] = min;
        angles[1] = max;
        return angles;
    }

In order to use right off this page you'll need to also implement some of the functions from Marshmallow/RobotUtilsCode.