MeleePatternMatching

Haha, my isp went nuts yesterday so here is a belated plee:

MeleePatternMatching would seem to me to be the best kind of melee gun, as loads of melee bots move in regular patterns or have repeating corner movement. Having realised that, it is clear that you only need look at the change in actual position, rather than the change in heading/velocity when trying to match and project the pattern. I came up with the following code. The way its built up, and the way it searches the string was cribbed straight from FunkyChicken, also i have some functions taken from one of PEZ's bots (i cant remember which):

public class MeleePatternMatcher
{
    final int HISTORY_LENGTH = 10000;
    final int MAX_SEARCH_LENGTH = 128;
    
    ArrayList history;
    StringBuffer historyString;
    
    public MeleePatternMatcher()
    {
        history = new ArrayList();
        historyString = new StringBuffer();
    }
    
    public void add(Enemy target)
    {
        double bearing = absoluteBearing(target.lastPosition, target.position);
        double distancePerTick = target.lastPosition.distance(target.position)/target.timeSinceLastScan;

        for(int i=0; i<target.timeSinceLastScan; i++)
        {
            PMData temp = new PMData(bearing, distancePerTick);

            if(history.size() > HISTORY_LENGTH)
            {
                historyString.deleteCharAt(HISTORY_LENGTH);
                history.remove(HISTORY_LENGTH);  
            }

            history.add(0, temp);
            historyString.insert(0, temp.toChar());
        }
    }
    
    public Point2D predict(Point2D here, double bulletPower, Enemy target)
    {
        double bulletTime=0;
        double bulletSpeed = 20 - (3*bulletPower);
        int startIndex;
        Point2D position = target.position;

        if ((startIndex=findStartIndex()) == -1) return position;
            
        while((bulletTime+=bulletSpeed)<here.distance(position) && startIndex>=0)
        {
            PMData current = (PMData)history.get(startIndex);
            position = vectorToLocation(current.bearing, current.distance, position);
            startIndex--;
        }
        
        return position;
    }
    
    public int findStartIndex()
    {
        int startIndex = -1;
        int searchlength = MAX_SEARCH_LENGTH;
        
        if(historyString.length()<searchlength) return startIndex;
        while ((startIndex = historyString.toString().indexOf(historyString.substring(0, searchlength-=8), 1)) < 0);
        
        return startIndex;
    }
    
    public double absoluteBearing(Point2D source, Point2D target) 
    {
        return Math.atan2(target.getX() - source.getX(), target.getY() - source.getY());
    }
    
    public Point2D vectorToLocation(double angle, double length, Point2D sourceLocation) 
    {
        return new Point2D.Double(sourceLocation.getX() + Math.sin(angle) * length,
            sourceLocation.getY() + Math.cos(angle) * length);
    }
    
    public class PMData
    {
        double bearing;
        double distance;       

        public PMData(double bearing, double distance)
        {
            this.bearing = bearing;
            this.distance = distance;
        }

        public char toChar()
        {
            int val = 1;
            val *= Math.pow(2, Math.round(distance/5));
            val *= Math.pow(3, Math.round(Math.toDegrees(bearing)/2));
            
            return (char)(val);
        }
    }
}

With a system looking at the change in the actual position of the enemy, it should do great against bots that move disregarding the opponents, and so should do well in the Pattern Matcher challenge, but it only gets around 50%, and i really dont know whats wrong with it. anyone any ideas?? --Brainfade

It looks like you are storing the data in terms relative to your current position, so unless you are remaining absolutely still it will be inacurate, surely? -- Tango

Nope, don't think i am. The only data stored is movement between 2 scans -- Brainfade

PMData holds a bearing and a distance. Those values have to be relative to something, and I can't see where you convert them to something absolute. -- Tango

Sorry, thats my fault i should really have commented or explained my code. I have an Enemy object that stores all possible relevant information on an opponent including the current and previous position. i create a PMData instance for every tick, interpolating between the 2 recording positions, to record the absolute bearing of the move made and the distance moved in the last tick. I use this data in a symbolic pattern matcher. Once found, the vectors stored in the PMData instance for that tick are projected onto the current position until the enemy distance would be the same as the bullet travel distance. I then shoot at that point. To add a scan to teh pattern matcher you call the add() method with an Enemy object, and to project where the enemy will be before firing you call predict(). Maybe one day i'll actually listen to what i'm always being told and comment my code... --Brainfade

OK, so to summerise, the bearing and distance are relative to the last enemy position. That makes sense. :-) -- Tango

Can you explain what happens in the while() loops in the predict() and findStartIndex?() methods? --Starrynte

When you insert something at position 0 (in the Arraylist and StringBuffer?), it doesn't overwrite it, right? --Starrynte

Nope, thats the whole point of inserting it, ArrayList.add(int Index, Object <E>) will insert the object at position Index. To overwrite you would ahve to use the Set(int index, Object <E>), which will overwrite the Object at index with the new Object. --Chase-san

What does findStartIndex?() do? Btw, does this work yet? --Starrynte

It seems to work, kind of. Btw, should I do the PM for every bot or just the target? Also, if it doesn't seem to work, make sure you have an instance of the class for each robot. Otherwise, you're patternmatching all the robots at once for just one target! --Starrynte

Nvm about the "it seems to work", it can't hit Crazy on 1v1. Maybe you should start tweaking with 1v1 first --Starrynte

It always fire with HOT, even against Crazy. This is because findStartIndex?() always returns -1 for some reason--Starrynte

Aha! findStartIndex?() always returns -1 because historyString.length() is always less than searchlength! --Starrynte

If timeSinceLastScan? is 0 (which it probably will be in 1v1) it won't add anything. --Starrynte

---

Hello. I am just curious if anyone could actually teach me how to code some fast melee pattern matching code. I have been trying to figure out this for very long but have no solutions to it. And mind telling me what you think is the best radar to use for melee? thanks. -- Aryary

Take a look at Simonton's melee microbot, Sprout. IIRC it uses melee pattern matching, although I've never looked at it very closely. -- Skilgannon

Hmm ok. Thanks. Will see what I can do. -- Aryary