Skilgannon/PreciseIntersect

Like all my code, this is designed to run as fast as possible. At first I was working on a distance-based method (similar to the check at the beginning), but I realized there would be a bucketload of special cases, so I ditched that and went with standard square/circle intersection. All my own work, although after writing I did go over Krabb's and Rednaxela's implementations to check for bugs. It seems great minds think alike =) although I have a strange love of arrays ;-)

       import java.awt.geom.*;
   import java.util.*;
    public class PreciseUtils{
   
   //high speed test to determine if the full method should be run this tick
       public static boolean intersects(Point2D.Double botLocation, Wave wave){
         double[] distSq = new double[]{
               wave.fireLocation.distanceSq(botLocation.x - 18, botLocation.y + 18),
               wave.fireLocation.distanceSq(botLocation.x + 18, botLocation.y + 18),
               wave.fireLocation.distanceSq(botLocation.x + 18, botLocation.y - 18),
               wave.fireLocation.distanceSq(botLocation.x - 18, botLocation.y - 18)};
         
         //faster? I'm not sure
      	// Arrays.sort(distSq);
         // return (sqr(wave.distanceTraveled + bulletVelocity) > distSq[0]
            // && sqr(wave.distanceTraveled) < distSq[3]);
            
         return (sqr(wave.distanceTraveled) >
            Math.min(Math.min(distSq[0], distSq[1]), Math.min(distSq[2],distSq[3]))
            && sqr(wave.distanceTraveled - wave.bulletVelocity) < Math.max(Math.max(distSq[0], distSq[1]), Math.max(distSq[2],distSq[3])));
      
      }
       public static double[] getIntersectionRange(Point2D.Double botLocation, Wave wave){
         double[] yBounds = new double[]{botLocation.y - 18, botLocation.y + 18};
         double[] xBounds = new double[]{botLocation.x - 18, botLocation.x + 18};
         
         double[] radii = new double[]{wave.distanceTraveled, wave.distanceTraveled - wave.bulletVelocity};
      	
         ArrayList<Point2D.Double> intersects = new ArrayList<Point2D.Double>();
         for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++){
               Point2D.Double[] testPoints = vertIntersect(wave.fireLocation.x, wave.fireLocation.y, radii[i], xBounds[j]);
               for(int k = 0; k < testPoints.length; k++)
                  if(inBounds(testPoints[k].y, yBounds))
                     intersects.add(testPoints[k]);
            }
            
         for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++){
               Point2D.Double[] testPoints = horizIntersect(wave.fireLocation.x, wave.fireLocation.y, radii[i], yBounds[j]);
               for(int k = 0; k < testPoints.length; k++)
                  if(inBounds(testPoints[k].x, xBounds))
                     intersects.add(testPoints[k]);
            }
         for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++){
               Point2D.Double testCorner = new Point2D.Double(xBounds[i], yBounds[j]);
               double distSq = testCorner.distanceSq(wave.fireLocation);
               if(distSq < sqr(radii[0]) && distSq > sqr(radii[1]))
                  intersects.add(testCorner);
            }
         double antiClockAngle = Double.POSITIVE_INFINITY;
         double clockAngle = Double.NEGATIVE_INFINITY;
         double absBearing = angle(wave.fireLocation, botLocation);
         for(Point2D.Double p: intersects){
            double angDiff = fastRelativeAngle(angle(wave.fireLocation,p) - absBearing);
            if(angDiff > clockAngle)
               clockAngle = angDiff;
            if(angDiff < antiClockAngle)
               antiClockAngle = angDiff;
         }
         return new double[]{fastAbsoluteAngle(antiClockAngle + absBearing), fastAbsoluteAngle(clockAngle + absBearing)};
      }
       static boolean inBounds(double q,double[] xBounds){
         return q >= bounds[0] && q <= bounds[1] ;
      }

      
   	//assumes between -PI*2 and PI*2
       public static double fastRelativeAngle(double angle) {
         return angle<-Math.PI?angle+Math.PI*2:angle>Math.PI?angle-Math.PI*2:angle;
      }
      
   	//assumes between -PI*2 and PI*4
       public static double fastAbsoluteAngle(double angle){
         return angle > Math.PI*2 ? angle - Math.PI*2 : angle < 0? angle + Math.PI*2 : angle;
      }
   
       static Point2D.Double[] vertIntersect(double centerX, double centerY, double r, double intersectX){
         double deltaX = centerX - intersectX;
         double sqrtVal = r*r - deltaX*deltaX;
         if(sqrtVal < 0)
            return new Point2D.Double[]{};
            

// commented out because having this decision would 
// take more execution time than the rare occurence 
// that a perfect 0 discriminant would save, and
// the code downstream can deal with it anyways 
        // if(sqrtVal == 0)
          //  return new Point2D.Double[]{
            //      new Point2D.Double(intersectX, centerY)};
      		
         sqrtVal = Math.sqrt(sqrtVal);
         return new Point2D.Double[]{
               new Point2D.Double(intersectX, centerY + sqrtVal),
               new Point2D.Double(intersectX, centerY - sqrtVal)};
      } 
       static Point2D.Double[] horizIntersect(double centerX, double centerY, double r, double intersectY){
         double deltaY = centerY - intersectY;
         double sqrtVal = r*r - deltaY*deltaY;
         if(sqrtVal < 0)
            return new Point2D.Double[]{};
            
         if(sqrtVal == 0)
            return new Point2D.Double[]{
                  new Point2D.Double(centerX, intersectY)};
      		
         sqrtVal = Math.sqrt(sqrtVal);
         return new Point2D.Double[]{
               new Point2D.Double(centerX + sqrtVal, intersectY),
               new Point2D.Double(centerX - sqrtVal, intersectY),};
      } 
   
       public static double sqr(double d){
         return d*d;}
         
       public static double angle(Point2D.Double source, Point2D.Double target) {
         return Math.atan2(target.x - source.x, target.y - source.y);
      }
      
       public class Wave{
         double distanceTraveled;
         double bulletVelocity;
         Point2D.Double fireLocation;
      }
   }

---

Hmm, nice. This looks like a pretty solid implementation to me, and at a glance looks like it would probably notably quicker than mine. I'm quiet curious to see what affect this will have on Druss's targeting ability :-) -- Rednaxela

I've actually made a couple small changes, which would mostly affect the execution speed. I'm curious how you layered all the ranges on top of each other to find a firing angle. Is the methodology anything similar to this?

            GFRange[] ranges = new GFRange[cluster.size()];
            double[] indices = new double[ranges.length*2];
            for(int i = 0; i < ranges.length; i++){
               ranges[i] = iterator.next();
               indices[i*2] = ranges[i].min;
               indices[i*2 + 1] = ranges[i].max;
            }

            Arrays.sort(indices);
            int[] indicesScores = new int[indices.length - 1];
            for(int i = 0; i < ranges.length; i++){
               int minIndex = Arrays.binarySearch(indices,ranges[i].min);
               int maxIndex = Arrays.binarySearch(indices,ranges[i].max);
               while(minIndex<maxIndex)
                  indicesScores[minIndex++]++;
            }
            int maxIndex = indicesScores.length/2;
            for(int i = 0; i < indicesScores.length; i++){
               if(indicesScores[i] > indicesScores[maxIndex])
                  maxIndex = i;
            }
            double fireGF = (indices[maxIndex] + indices[maxIndex + 1])/2;

            return fireGF*MEA*lateralDirection;

-- Skilgannon

Well, the way I did it should be in effect similar to that. I use a class I call "MovementProfile" that stores overlayed ranges and has a variety of functions for adding/retrieving data from it. See the MovementProfile file in RougeDC's code or [here]. It's a bit messy and not all of the utility functions are actually used currently/anymore but I have them around in case I still need them. The utility functions besides getting the best GF that I am using are mostly there for the purpose of getting data about the profile for my CrowdTargeting weighting system to use (because I don't like VirtualBullets). Basically, it stores a sorted array where each element contains 1) an amount of increase/decrease and 2) The precise GF that increase/decrease occurs at. The reason I store amounts of increases/decreases instead of storing the overall value of an index, is that it makes incrementally adding to the profile far simpler and it's not as if searching for the highest point is much slower. -- Rednaxela