partitioner.java

2004年robotcup世界冠军源代码

// Added by Omid Aghazadeh
package MRL.Utilities.Partitioning;

import java.util.*;
import yab.agent.object.*;
import yab.agent.*;
import MRL.MRLConstants;
import yab.agent.Util;

public final class Partitioner { // Motionless Objects Are Never Changed So There's No Need To Update Them Later?
  protected final Collection allpartitions = new HashSet();
  protected final Collection quadpartitions = new HashSet();
//  private final static List edges; //
  private final DisasterSpace world;
  private final Set motionlessObjects = new HashSet();
  private final Set edgeObjects = new HashSet();
    private final Condition PARTITIONABLE_C = new Condition(){
     public boolean eval(Object obj){
         return obj instanceof Partitionable;
     }
  } ;
  // ---------------------------------------------------------------- OMID

  public Partitioner(DisasterSpace world,int width_div, int height_div, Collection motionlessObjects) {
    this.world = world;
    this.motionlessObjects.addAll(PARTITIONABLE_C.extract(motionlessObjects));
    QuadPartition(width_div, height_div);
    int objectsPartitioned =  FillPartitions(quadpartitions,motionlessObjects);
    System.out.println(world.self + " , OBJS : " + motionlessObjects.size() + " , OBJS Partitioned : " + objectsPartitioned + " , Edge Objects : " + edgeObjects.size());
    motionlessObjects.clear();
  }

  public int TotalCount() {
    return allpartitions.size();
  }

  public Partition getPartition(Partitionable p) {
    return getPartition(allpartitions, p);
  }

  public int getPartitionID(Partitionable p) {
    Partition partition = getPartition(p);
    return partition == null ? -1 : partition.getID();
  }

  private Partition getPartition(Collection partitions, Partitionable p) {
    Collection includingpartitions = getIncludingPartitions(p,partitions); // For OverLap Support.
    if(includingpartitions.size() == 0) return null;
    Partition result = (Partition)includingpartitions.iterator().next(), partition;
    if (includingpartitions.size() > 1) {
      int mindistance = result.getDistanceToCenter(p), dist;
      for (Iterator it = includingpartitions.iterator(); it.hasNext(); ) {
        partition = (Partition) it.next();
        dist = partition.getDistanceToCenter(p);
        if (dist < mindistance) {
          result = partition;
          mindistance = dist;
        }
      }
    }
    includingpartitions = null;
    return result;
  }

    private Partition getPartitionWNO(Collection partitions , Partitionable p){
        Partition part;
        for(Iterator it = partitions.iterator();it.hasNext();){
            part = (Partition) it.next();
            if(part.Includes(p)) return part;
        }
        return null;
    }
  /*
   public List FindEdges(){
     List roads = World.roads,result = new ArrayList(),connectingroads;
     Road startingroad = findTopMostRoad(),road = startingroad;
     roads.add(startingroad);
     PointObject head,tail,prevpoint=findUpperPointOfRoad(startingroad),nextpoint= startingroad.head() == prevpoint ? startingroad.tail() : startingroad.head();
     boolean more = true;
     while (more) {
       connectingroads = nextpoint.ConnectedRoads();
       nextpoint = prevpoint ==road.head()  ? road.tail() : road.head();


     }
   }
     private Road findTopMostRoad() {
    List roads = World.roads;
    Road road, result = (Road) roads.get(0);
    PointObject head, tail, prevtopposition = findUpperPointOfRoad(result);
    boolean isedge = true;
    for (Iterator it = roads.iterator(); it.hasNext(); ) {
      road = (Road) it.next();
      head = road.head();
      tail = road.tail();
      if (head.y() > prevtopposition.y() || tail.y() > prevtopposition.y()) {
        result = road;
        prevtopposition = findUpperPointOfRoad(result);
      }
    }
    return result;
     }

     private PointObject findUpperPointOfRoad(Road road) {
    return road.head().y() > road.tail().y() ? road.head() : road.tail();
     }

   */
  /*
      private List getQuadPartitionList() {
        List qpl = new ArrayList();
        Partition partition;
        for (Iterator it = allpartitions.iterator(); it.hasNext(); ) {
          partition = (Partition) it.next();
          if (partition instanceof QuadPartition) qpl.add(partition);
        }
        return qpl;
      }
   */

  private int FillPartitions(Collection partitions,Collection objects) { // Returns Number Of Objects Filled In Partitions
    int result = 0;
    boolean bFound;
    Partition partition/*,headPart,tailPart*/;
    Collection edgeParts= new HashSet();
    Object obj;
    Partitionable p;
    Path path;
    Road road;
    for (Iterator it = objects.iterator(); it.hasNext(); ) {
      obj =  it.next();
      if(obj instanceof Partitionable){
        p = (Partitionable) obj;
        bFound = false;
        for(Iterator it2 = partitions.iterator();it2.hasNext();){
            partition = (Partition) it2.next();
            if(partition.Includes(p)){
                bFound = true;
                if(partition.Add(p)){
                 result++;
                }
            }
        }
        if(!bFound){
          if(MRL.MRLConstants.PARTITION_DEBUG_MODE) System.out.println("Partitioning , Ignoring : " + p + " , Cant Find Matching Partition!" );
        }
        else{
            if(p instanceof Path){
                edgeParts.clear();
                path = (Path) p;
                for(Iterator it2 = path.iterator();it2.hasNext();){
                    road = (Road) it2.next();
                    partition = getPartition(partitions,road);
                    edgeParts.add(partition);
                }
                if(edgeParts.size() > 1 && ! edgeObjects.contains(path)){
                    edgeObjects.add(path);
                    for(Iterator it2 = edgeParts.iterator();it2.hasNext();){
                        partition = (Partition) it2.next();
                        partition.addEdgeObject(path);
                        partition.Add(path);
                        path.setEdgePath();
                    }
                    if(MRL.MRLConstants.PARTITION_DEBUG_DEEP_MODE) System.out.println(path + " , Is An Edge Object Of :  " + edgeParts.size() );
                }
//                headPart =getPartition(partitions,path.getFirstNode());
//                tailPart =getPartition(partitions,path.getLastNode());
//
//                if(headPart!=tailPart) {
//                    headPart.addEdgeObject(path);
//                    tailPart.addEdgeObject(path);
//                }
            }
          }
      }
        else{
         if(MRL.MRLConstants.PARTITION_DEBUG_MODE) System.out.println("Partitioning , Ignoring : " + obj );
      }
    }
    return result;
  }

  private Collection getContainingPartitions(Partitionable p, Collection Partitions) {
    List result = new ArrayList();
    Partition partition;
    for (Iterator it = Partitions.iterator(); it.hasNext(); ) {
      partition = (Partition) it.next();
      if (partition.IsContaining(p)) result.add(partition);
    }
    return result;
  }

  private Collection getIncludingPartitions(Partitionable p, Collection Partitions) {
  List result = new ArrayList();
  Partition partition;
  for (Iterator it = Partitions.iterator(); it.hasNext(); ) {
    partition = (Partition) it.next();
    if (partition.Includes(p)) result.add(partition);
  }
  return result;
}


  public int QuadPartitionFill() {
    return FillPartitions(quadpartitions, motionlessObjects);
  }

  public static final int LEN_TO_OVERLAP_EDGES = 10000;
  private int QuadPartition(int width_div, int height_div) {
    Partition partition;

//      int lenToOverLap = (world.self instanceof PoliceForce || world.self instanceof PoliceOffice) ? LEN_TO_OVERLAP_EDGES : 50;
    int lenToOverLap = Util.max(height_div,width_div);
    int top = getBoundary(0) , bottom = getBoundary(1) ,
        left = getBoundary(2) ,
        right = getBoundary(3) , width = right - left, height =  top - bottom,
        eachheight = (int) Math.ceil(height / height_div)  ,
        eachwidth = (int) Math.ceil(width / width_div);

    int partition_id;
    for (int i = 0; i < height_div; i++) {
      for (int j = 0; j < width_div; j++) {
        partition_id = i * width_div + j;
        partition = new QuadPartition(world,partition_id,
                                      left + j * eachwidth  - lenToOverLap,
                                      bottom + i * eachheight - lenToOverLap , eachwidth + 2* lenToOverLap ,
                                      eachheight + 2* lenToOverLap);
        quadpartitions.add(partition);
      }
    }
    allpartitions.addAll(quadpartitions);
    return quadpartitions.size();
  }

  /*
        private int CheckVerticalPosition(Road road1, Road road2) {

        }

        private int CheckHorizontalPosition(Road road1, Road road2) {

        }
   */

  private int getBoundary(int dir) { // 0 : Up , 1 : Down , 2 : Left , 3 : Right
    int result = -1;
    Partitionable max = (Partitionable) motionlessObjects.iterator().next(), res;
    switch (dir) {
      case 0:
        for (Iterator it = motionlessObjects.iterator(); it.hasNext(); ) {
          res = (Partitionable) it.next();
          if (res.y() > max.y()) max = res;
        }
        result = max.y();
        break;
      case 1:
        for (Iterator it = motionlessObjects.iterator(); it.hasNext(); ) {
          res = (Partitionable) it.next();
          if (res.y() < max.y()) max = res;
        }
        result = max.y();
        break;
      case 2:
        for (Iterator it = motionlessObjects.iterator(); it.hasNext(); ) {
          res = (Partitionable) it.next();
          if (res.x() < max.x()) max = res;
        }
        result = max.x();
        break;
      case 3:
        for (Iterator it = motionlessObjects.iterator(); it.hasNext(); ) {
          res = (Partitionable) it.next();
          if (res.x() > max.x()) max = res;
        }
        result = max.x();
        break;
      default:
        break;
    }
    return result;
  }

  public String toString() {
    String result = "TotalPartitions:" + TotalCount() + ",Details:\n";
    Partition partition;
    for (Iterator it = allpartitions.iterator(); it.hasNext(); ) {
      partition = (Partition) it.next();
      result += partition.toString() + ",Contents:" + partition.showContents() +
          "\n";
    }
    return result;
  }


  ///// TESTS
  /*
  public void testPartitions() {
    RealObject ro;
    for (Iterator it = World.getObjects().iterator(); it.hasNext(); ) {
      ro = (RealObject) it.next();
      if (ro instanceof Partitionable) {
        System.out.println("Object : " + ro + " , In Partition : " +
                           getPartition((Partitionable)ro).getID());
      }

    }
  }

  public void testAllObjectsIncluded() {
    System.out.println("testAllObjectsIncluded() Started.");
    RealObject ro;
    for (Iterator it = World.getObjects().iterator(); it.hasNext(); ) {
      ro = (RealObject) it.next();
      if (getPartitionID((Partitionable)ro) == -1) {
        System.out.println("Error,Object:" + ro + " Isn't In A Partition");
        System.exit( -1);
      }
    }
    System.out.println("testAllObjectsIncluded() Ended.");
  }
  */
  public void getUpdatedMovingObjectsInfo(RealObject self , Collection objects) {
    RealObject ro;
    MovingObject mo;
    int total = 0, updated = 0;
    for (Iterator it = objects.iterator(); it.hasNext(); ) {
      ro = (RealObject) it.next();
      if (ro instanceof MovingObject) {
        total++;
        mo = (MovingObject) ro;
        if (mo.position() != null) updated++;
      }
    }
    System.out.println("Self : " + self.id + " Of " +
                       yab.agent.Util.classBaseName(self) + " ,Total : " +
                       total + " , Total MO Position Set In This DP : " +
                       updated);
  }

  public Partition getPartition(int Partition_ID){
    Partition partition=null;
    if(Partition_ID >= 0){
      for (Iterator it = allpartitions.iterator(); it.hasNext(); ) {
        partition = (Partition) it.next();
        if (partition.getID() == Partition_ID)break;
      }
    }
    return partition;
  }

  /*
  public void testRoads(){
    long dur1,dur2;
    Partition partition=null;
    List parttest=null,worldtest=new ArrayList();
    int totalcount,sumpartscount=0;
    totalcount = World.roads.size();
    Calendar c1 = new GregorianCalendar();
    dur1=c1.getTimeInMillis();
    for(Iterator it = allpartitions.iterator();it.hasNext();){
      partition = (Partition) it.next();
      sumpartscount += partition.getRoads().size();
    }
    c1 = new GregorianCalendar();
    dur1 = c1.getTimeInMillis() - dur1;
    if(totalcount == sumpartscount) System.out.println("All Roads Are Covered In Partitions , Search Took : " + dur1 + " Milli Secs.");
    else System.out.println("Some Roads Are Probably Missing!");
    c1 = new GregorianCalendar();
    dur1 = c1.getTimeInMillis();
    Road road;
    for(Iterator it = World.roads.iterator();it.hasNext();){
      road = (Road) it.next();
      if(getPartition(road) == partition) worldtest.add(road);
    }
    c1 = new GregorianCalendar();
    dur1 = c1.getTimeInMillis() - dur1;
    totalcount = worldtest.size();
    c1 = new GregorianCalendar();
    dur2 = c1.getTimeInMillis();
    parttest = partition.getRoads();
    c1 = new GregorianCalendar();
    dur2 = c1.getTimeInMillis() - dur2;
    sumpartscount = parttest.size();
    System.out.println("Time For World Search Took : " + dur1 + " , " + totalcount + " Roads Found");
    System.out.println("Time For Partition Search Took : " + dur2 + " , " + sumpartscount + " Roads Found");
  }

  */
  public Collection getPartitions(){
    return allpartitions;
  }

  // ---------------------------------------------------------------- OMID

}