[Home]Rednaxela/SuperBotwidth

Robo Home | Rednaxela | Changes | Preferences | AllPages

Showing revision 15
Well, while working on my new 1v1 bot, the thought came to me, that one aspect of existing top bots that may be sub-optimal, may be how botwidth is handled.

So, let's say you have a bullet wave passing a bot, like shown above. In every case I've heard of, people would just take the angular width of the bot and leave it at that. And that's perfectly accurate and fine when the enemy bot isn't moving. The thing is though, that method "forgets" that bots have depth and can move.

So for a more accurate (though significantly more complicated) method, I'm instead going to evaluate the range of points the bullet could hit the bot at, for every tick where the bullet wave is passing the bot. To do this on a given tick, I find
1) intrsections between the square and the bullet wave
2) intersections between the square and where the bullet wave was last tick
3) any corners of the square that lie between these two circles
I then evaluate the angles of all of these points, and find the range they are within (in the diagram above the red region). This gives the full range of angles that could have hit the bot at that particular tick in time.

So in the next tick, the bot has moved and the wave has advanced. So I calculate this range of angles the same way again, and create an augmented range.

This is repeated for every tick until the wave has left the bot, and the final augmented range, is the full range of angles (and thus GuessFactors) that could have hit the bot, in a more accurate way than plain botwidth, and correctly accounts for considerations such as that a moving bot can be hit by a greater range of angles than a still bot, because it may be hit on it's side by a bullet that started to pass by it that the bot then ran into.

I've implemented the bulk of this in my 1v1 bot in progress. The tricky part was doing the square-circle intersections which were bothersome, but is not that complex besides that. I'm not sure how much benefit this will have in the actual battlefield, however you can never be too accurate when it comes to WaveSurfing, GuessFactors and such things. I suppose. And questions/comments? Has this already been done before and I just didn't know about it?


Very nice write up and diagrams there! Well, I've experimented with angular bot width quite a bit. I never went this pixel perfect and treated my bot as a 36x36 square, but I did try adjusting the bot width to the max width at the situation's angle (e.g., the full diagonal length for a 45 degree shot), and I've also tried an approximation of the average width for that angle. I thought it was helping and left it in for a while, but upon going back to just using something static (like 40) and doing extensive testing, it made no difference at all for me, in challenge scores nor RoboRumble rating.

Frankly, like you said, every bit of precision helps, so pulled off right this could only be a good thing. My experience was that the difference was negligible and I removed it. I just use something like 36 or 40 for bot width now. I'd be interested to know how often the spot your surfer decides to move to would be any different using the two different bot width calculations - I suspect it would be extremely rarely, but it would be interesting to know for sure. I'd even bet you could remove all bot width calculations from most surfers and not impact their rating much at all. Please share your findings =)

-- Voidious

Thanks! Well, one note that comes to mind that may have an impact, is that when doing botwidth calculations of the style you're talking about, it never changes the center of the region. The method I'm using here though does more than just change the width though, which is where I suspect it may provide some significant strength. For one thing, it may change the center of the region compared to what other bots would see the center to be, particularly if the bot changes velocities partway though the time in which the wave passes it. In some ways, I suspect this alteration of the center may be more helpful than the adjustment of width itself. I'm also thinking that may have a larger impact on WaveSurfing than firing, due to how this particular method would give the bot the ability to account for it's own "curvature" (yes, the curvature of a square :)) as it moves through the wave (possibly giving greater weighting to parts of the bot that would pass the wave first), as opposed to pretending it's a "flat board" facing the wave. Anyways, yes I'll certainly share my findings on how this works out :)

--Rednaxela

Well, because I was bored and like my excessive diagrams, I made a little animation to help elaborate on how I think this could work with WaveSurfing.

Precise prediction would be done over the whole course of the bullet passing over the robot, and for each tick, the the danger is evaluated on sections of the robot that could be hit on that particular tick. Similar to how many bots handle surfing multiple waves at once, it would apply a weighting to parts that would be hit first. When the wave is *actually* passing over the bot, GuessFactors that are already known to be safe will be given no danger weighting (see parts in the animation becoming black again). One note is that this animation is for an unmoving bot, and that it could look a bit more interesting in cases of a moving bot. In some ways, I think this method to enhance WaveSurfing kinda reminds me of aerodynamics and hydrodynamics, in that it more fully follows the "flow" of danger around the bot and accounts for parts of the bot "shadowing" other parts of the bot and such :)

-- Rednaxela

Nice graphics! Yes I do it exactly like you (without your weightning) :) But my code isn't tuned for speed (Its quite slow) and i don't know if it is bugfree. I could publish my code here and we could compare our implementations (If you don't mind). The precise botwidth calculation was beneficial to my movement, but a drawback to the gun (I dunno i that is still the case). --Krabb

Incorporating this into my surfing was the main new feature of my 'magic' version of DrussGT that was for a while beating Dookious. Although using a different method, my surfing effectively takes into account the increased botwidth from going to an option that requires movement as the wave passes over. DrussGT only moves as a wave passes over him if the increased number of bins it would cover have less danger than the bins it avoids by keeping moving. And what's more, no special cases! Oh yes, and in other news my botwidth calculation is pretty much 100% accurate now. widthPixels = 50*Math.max(Math.abs(Math.sin(angle + Math.PI/4)),Math.abs(Math.cos(angle + Math.PI/4))) -- Skilgannon

I'm quite open to being proved wrong, but I'm still skeptical that it's such a huge advantage. =) I will certainly concede that it could only be advantageous, not disadvantageous. I'd love to see a bot doing this style of bot width and in parallel calculate how it would move if it just considered a static bot width (36 or 40), then output how often the surfing decisions would actually be different. Maybe I'll have to do it myself to find out. =) I just think that against simple targeters, having that extra bin or two added into your danger calculation is almost never going to change which position among the ones you're considering is the least dangerous. And against non-simple targeters, you aren't projecting their shots nearly accurately enough for it to show any real improvement - I think you could remove bot width altogether against them and not change your movement.

DrussGT is a unique case in how it uses bot width. Consider this: the new method you used would either keep the width / number of bins the same or increase it in every case, so this change would have effectively altered your distancing formula - if you add a couple bins to the number of bins in every situation, the % difference for closer bins decreases. It's entirely possible to me that the distancing side effect of what you did caused the performance gain - I've absolutely had such hidden things happen! While I find your distancing / bot width implementation intriguing and unique, I must confess I've always thought it was a little illogical. =) It seems analogous to but less accurate than just using average bin score and then multiplying dividing by distance, doesn't it? And separating them out gives you more direct access to tweaking your distance formula. But I digress...

-- Voidious

Ha, yes I am now using the average bin score and multiplying by botwidth (in radians). I've noticed the biggest improvement against bots that fight close up, especially those that shoot HOT, because my danger formula now sees that it is safer to keep moving than to stop as the wave passes over. But remember that the variable botwidth only affects options where I would still be moving when the wave hits. This is the vast minority of my options, so I doubt it affects my distancing much at all. Before 1.0.3 DrussGT didn't have the option to still be moving as the wave went overhead, and thus having a variable botwidth was useless. So when I added the option in I wanted to make sure I did it correctly, without giving these new options a non-existent advantage (or rather lack of disadvantage). So the jump in points I got was partly due to my variable botwidth, but probably more to do with adding the 'stay moving' option. -- Skilgannon

Ah, so you had already controlled for that possible side effect I mentioned. Your last explanation really has me thinking about this a different way. I had previously been looking at this as just more accurately pulling the danger for that spot from your stats, but the fact you cover more bot width when moving than when stationary is definitely relevant. I'll have to think about this - my Robocode skills sure are rusty. =) -- Voidious

@Krabb - Mine isn't turned for speed either, it's tuned for "however I could get my head around the stupid square-circle intersections" :) Sure, I'd like to compare some time, just need to get more of this finished in implementation :)
@Skilgannon - Hmm, interesting. By the sounds of it you're kind of adapting the plain angular botwidth to account for factors (such as that you'll cover more botwidth while moving) that I'm hoping to deal with.
@Voidious - Hmm yes, making a version with static botwidth to compare to would be interesting once I get this bot into the field.
Hmm, it is interesting hearing about other people's botwidth approaches and such, I suppose I'll some time soon see how this approach I'm thinking of will stack up, once I get this bot working enough.

-- Rednaxela

---

Well here's the main basis of the code I use for it, to compare to Garm/BotwidthCalculation. I think functionally they're indeed the same, though Krabb and I have very different code styles it seems :)
One note, is that this code is inside of my Wave class, and depends on: getRadius(), getSpeed(), intersects(AbsolutePoint p) and getGuessFactor(AbsolutePoint p) of my Wave class, and it also depends on the AbsolutePoint and Range utility classes I have. All of those things are fairly self-explaining by name and simple though but if you want the code for those, feel free to ask.

    // Get the intersecting guessfactor range of a bot centered at a given point
    public Range getGuessRange(AbsolutePoint p) {
        // Prepare radius ranges
        double radius = getRadius();
        double lastradius = radius-getSpeed();
        
        // Check if it's too far away for any intersection
        if (Math.abs(origin.distance(p) - radius) > Math.sqrt(2*18*18))
            return null;
                
        // Store a list of possible extreme points 
        List<AbsolutePoint> possiblepoints = new ArrayList<AbsolutePoint>();
        
        // Get the sides of the bot
        double bottom = p.y - 18;
        double top = p.y + 18;
        double left = p.x - 18;
        double right = p.x + 18;
        
        // Check if there is actually intersections with any sides
        possiblepoints.addAll(XCircleIntersect(origin, lastradius, left,   bottom, top));
        possiblepoints.addAll(XCircleIntersect(origin, radius,     left,   bottom, top));
        possiblepoints.addAll(XCircleIntersect(origin, lastradius, right,  bottom, top));
        possiblepoints.addAll(XCircleIntersect(origin, radius,     right,  bottom, top));
        
        possiblepoints.addAll(YCircleIntersect(origin, lastradius, bottom, left,   right));
        possiblepoints.addAll(YCircleIntersect(origin, radius,     bottom, left,   right));
        possiblepoints.addAll(YCircleIntersect(origin, lastradius, top,    left,   right));
        possiblepoints.addAll(YCircleIntersect(origin, radius,     top,    left,   right));
        
        // Get the corners of the bot
        AbsolutePoint c1 = AbsolutePoint.fromXY(left,  bottom);
        AbsolutePoint c2 = AbsolutePoint.fromXY(left,  top);
        AbsolutePoint c3 = AbsolutePoint.fromXY(right, top);
        AbsolutePoint c4 = AbsolutePoint.fromXY(right, bottom);
        
        // Add corners too if they're within what we want
        if (intersects(c1)) possiblepoints.add(c1);
        if (intersects(c2)) possiblepoints.add(c2);
        if (intersects(c3)) possiblepoints.add(c3);
        if (intersects(c4)) possiblepoints.add(c4);
        
        // Find the lowest and highest guessfactors
        Range r = null;
        for (AbsolutePoint point : possiblepoints) {
            double gf = getGuessFactor(point);
            if (r != null)
                r.grow(gf);
            else
                r = new Range(gf);
        }
        
        return r;
    }
    
    private static List<AbsolutePoint> XCircleIntersect(AbsolutePoint origin, double r, double x, double miny, double maxy) {
        List<AbsolutePoint> intersects = new ArrayList<AbsolutePoint>();
        double dx = x - origin.x;
        double D = r*r-dx*dx;
        
        // Negative discriminant, no intersection
        if (D < 0)
            return intersects;
        
        // Get an intersect
        double d = Math.sqrt(D);
        double y1 = origin.y + d;
        if (y1 >= miny && y1 <= maxy)
            intersects.add(AbsolutePoint.fromXY(x, y1));
        
        // Zero discriminant, no need for more
        if (D == 0)
            return intersects;
        
        // Get another intersect
        double y2 = origin.y - d;
        if (y2 >= miny && y2 <= maxy)
            intersects.add(AbsolutePoint.fromXY(x, y2));
        
        return intersects;
    }

    private static List<AbsolutePoint> YCircleIntersect(AbsolutePoint origin, double r, double y, double minx, double maxx) {
        List<AbsolutePoint> intersects = new ArrayList<AbsolutePoint>();
        double dy = y - origin.y;
        double D = r*r-dy*dy;
        
        // Negative discriminant, no intersection
        if (D < 0)
            return intersects;
        
        // Get an intersect
        double d = Math.sqrt(D);
        double x1 = origin.x + d;
        if (x1 >= minx && x1 <= maxx)
            intersects.add(AbsolutePoint.fromXY(x1, y));
        
        // Zero discriminant, no need for more
        if (D == 0)
            return intersects;
        
        // Get another intersect
        double x2 = origin.x - d;
        if (x2 >= minx && x2 <= maxx)
            intersects.add(AbsolutePoint.fromXY(x2, y));
        
        return intersects;
    }

-- Rednaxela

Okay, seems my above code is actually working, and is working quite well according to some debugging graphics I just hacked up after finishing my tracking of enemy waves. Now I just need to 1) Decide on some sorts of segmentations and how to weight them, 2) Throw stats from the waves into my KD Tree implementation, 3) Hack up some multiple linear regression code, 4) Copy my precise prediction from my old Gwynfor (It's precise prediction code was working very precisely and won't need much adaptation), and finally 5) Code the "core" of the wavesurfing, around the elements listed before. Then, I should at least in theory have a rather nice WaveSurfing movement. After which I'll probably slap on a standard gun and try out some movement challenges and such. Hopefully reality works as well as I hope :)

-- Rednaxela


Robo Home | Rednaxela | Changes | Preferences | AllPages
Edit revision 15 of this page | View other revisions | View current revision
Edited April 4, 2008 7:29 EST by Rednaxela (diff)
Search: