Folded Pattern Matcher

This article may require cleanup to meet RoboWiki's quality standards. Please improve this article if you can.

I like the idea of pattern matching but was afraid of performance issues. Symbolic pattern matchers get around some of these issues by using optimized Java string libraries. Still, there's only so much a Boyers-Moore algorithm or regular expression parser can do. If you're interested in checking patterns of many sizes, Robocode will slow down. Even if it works, the resulting pattern matcher might not work in a Virtual Gun array.

An optimized algorithm came to me while I was showering before work:

Imagine a symbolic pattern matcher with a six character alphabet. A typical implementation might store its history in a string like so:

Character
Index->0000000000111111111122222222223333
       0123456789012345678901234567890123
       ||||||||||||||||||||||||||||||||||
       BFFADEDCEFBEDADCFCCFEEADDEBFACCEEA <-New characters appended here.

These strings are best searched using Java string libraries.

Now imagine a "folded" string that is folded at each changed symbol. Besides characters linked in a string, identical symbols could be linked one to the next using a linked list or similar data structure like so:

Character
Index->0000000000111111111122222222223333
       0123456789012345678901234567890123
       ||||||||||||||||||||||||||||||||||
          A<--------A<-------A<----A<---A<-A index
       B<--------B<--------------B<--------B index
              C<------C<CC<---------CC<----C index
           D<D<----D<D<-------DD<----------D index
            E<-E<-E<-------EE<--E<----EE<--E index
        FF<-----F<-----F<-F<------F<-------F index
                                         ^
                                         |
                                         New characters appended here.

To append the next character (I'll say 'A'):

• Add it to the string (or other data structure) just like you would in flat pattern matching.
• Create a reference from your new 'A' to the latest 'A' in the A index list.
• Point the A index list reference at your new 'A'.

Now you're ready to match a pattern:

• Take the first character in your recent pattern. In this case, the 'A' at index 33.
• Follow its index reference directly to the next 'A' in your string. In this case, the 'A' at index 28. (Interesting note: If there were no matches, you'd know immediately because the A index reference would be null.)
• Make sure you have a reference to A33 and A28
• Use these references to look one character deeper in the pattern and history. The character before A33 is E32 and the character before A28 is F27 so there's no match. Our first attempt yields a match only one character deep.
• Now repeat the process.
• Your pattern starts at A33.
• Follow your 'A' index reference to the 'A' at 22.
• Look a character deeper in pattern and history. The character before A33 is E32 and the character before A22 is E21 so we have a two-character match.
• Look a character deeper. E31 precedes E32 and E20 precedes E21 so we have a three-character match.
• One deeper. C30 precedes E31 and F19 precedes E20 for no match.
• Repeat with the next 'A' index ...

There are two nice outcomes from this approach. First, it's fast. Most pattern matching algorithms aren't aware of their inputs before they receive them so they can't take advantage of indexing until they've already passed through the pattern and history at least once. We get around this by indexing as the string is built. Second, you don't have to guess at the length of your maximum match. The algorithm explores the absolute depth of every existing one-character match.

I've included a prototype implementation below. It comes with no guarantees. There are more than a few things to iron out. Namely:

1. It currently uses my own strongly-typed collections. Java linked lists, array lists, etc, might work just as well and be easier to manage.
2. It doesn't sense when a projected destination is outside the battlefield.
3. It contains round breaks but doesn't do anything with them. A pattern match might project into the next round.
4. There's no memory management. The longer it runs, the more it steals.
5. Since its fast, it makes sense to crunch some stats like TronsGun when a deep match isn't found. (Which happens a lot.)

Feel free to use and improve the code but please return the results to the wiki. Cheers. --Corbos

import java.awt.geom.Point2D;

public class FoldedPatternMatcher {
	
	private PatternNode[] _nodeIndexes;
	private PatternNode _head;
	private int _scanCount = 0;
	final double TEN_DEGREES = 10 * Math.PI / 180;
	final double TWENTY_DEGREES = TEN_DEGREES * 2;
	final char BREAK_SCAN = '\uffff';
	
	public FoldedPatternMatcher(){
		_nodeIndexes = new PatternNode[512];
	}
	
	public void record(double velocity, double headingDelta){
		int index = (((int)((velocity + 8) * 15 / 16) << 5) | ((int)((headingDelta + TEN_DEGREES) * 31 / TWENTY_DEGREES)));
		PatternNode node = new PatternNode((char)index, _scanCount++);
		insert(node);
		node.IndexRef = _nodeIndexes[index];
		_nodeIndexes[index] = node;
	}
	
	public void insertBreak(){
		insert(new PatternNode(BREAK_SCAN, _scanCount++));
	}
	
	private void insert(PatternNode node){
		node.SequenceRef = _head;
		_head = node;
		if(node.SequenceRef != null){
			node.SequenceRef.ReverseSequenceRef = node;
		}
	}
	
	public Point2D.Double project(Point2D.Double enemyLocation, double currentHeading, double bulletVelocity, Point2D.Double robotLocation){
		
		Point2D.Double nextPosition = null;
		PatternNode indexSymbol, cursor;
		PatternNode lastSymbol = _head;
		PatternNode bestSymbol = null;
		indexSymbol = _head.IndexRef;
		int depth;
		int bestDepth = 0;
		
		while(indexSymbol != null && lastSymbol.Index - indexSymbol.Index < 55000){
			
			if(lastSymbol.Index - indexSymbol.Index > 20){
				
				cursor = indexSymbol;
				depth = 0;
				
				while(lastSymbol != null && cursor != null && lastSymbol.Symbol == cursor.Symbol && depth < 125){
					lastSymbol = lastSymbol.SequenceRef;
					cursor = cursor.SequenceRef;
					depth++;
				}
				
				if(depth >= bestDepth){
					bestSymbol = indexSymbol;
					bestDepth = depth;
				}
			}
			
			lastSymbol = _head;
			indexSymbol = indexSymbol.IndexRef;
		}
		
		if(bestSymbol != null){
			double projectedTime = 0;
			double enemyX = enemyLocation.x;
			double enemyY = enemyLocation.y;
			bestSymbol = bestSymbol.ReverseSequenceRef;
			while(Point2D.distance(robotLocation.x, robotLocation.y, enemyX, enemyY) > projectedTime * bulletVelocity && bestSymbol != null){
				currentHeading += bestSymbol.getHeading();
				enemyX += Math.sin(currentHeading) * bestSymbol.getVelocity();
				enemyY += Math.cos(currentHeading) * bestSymbol.getVelocity();
				bestSymbol = bestSymbol.ReverseSequenceRef;
				projectedTime++;
			}
			nextPosition = new Point2D.Double(enemyX, enemyY);
		}
		return nextPosition;
	}
	
	class PatternNode{
		
		public PatternNode IndexRef;
		public PatternNode SequenceRef;
		public PatternNode ReverseSequenceRef;
		public char Symbol;
		public int Index;
		
		public PatternNode(char s, int index){
			Symbol = s;
			Index = index;
		}
		
		public double getVelocity(){
			int i = (int)Symbol;
			i = i >> 5;
			return (((double)i) * 16 / 15) - 8;
		}
		
		public double getHeading(){
			int i = (int)Symbol;
			i = i & 31;
			return (((double)i) * TWENTY_DEGREES / 31) - TEN_DEGREES;
		}
	}

}