ProvinceRationalizer7.pde

//Run this program in Processing (http://processing.org).

//This program has three objectives:
//1. Make provinces round and compact rather than skinny and snake-like;
//2. Don't make any province more fragmented than it already is; and
//3. Preserve all existing adjacencies between provinces.
//When you feed it a map (data/input.png), it spits out a progressively-better version
//of that map (output/*.png) every thirty seconds until you tell it to stop.

boolean mapIsCylinder=false;//Make this "true" if the map is a cylinder (wraps around at the east and west edges).
//color colorWater=color(68,107,163);//EU4
//color colorWasteland=color(94,94,94);//EU4

PImage image;//Input and output
Map map;

int timeMark;
boolean aMatchWasFound;
int successfulFlips=0;

void setup(){
  frameRate(999999);
  timeMark=millis();
  print("Loading image...");
  colorMode(RGB,255);//Default
  image=loadImage("input.png");//Actually "data/input.png"
  image.loadPixels();
  print(" Done in "+(millis()-timeMark)/1000+" seconds.\nDoing preliminary stuff...");
  map=new Map();
  map.analyze();
  print(" Done in "+(millis()-timeMark)/1000+" seconds.\nDoing flips...");
  timeMark=millis();
}
void draw(){
  map.attemptFlip();
  if(millis()-timeMark>30000){
    map.export();
    timeMark=millis();
  }
  //exit();
}

class Map{
  Pxl[] pxls;
  Province[] provinces;
  float[] xOriginal;
  float[] yOriginal;
  Map(){
    //Pxls
    pxls=new Pxl[image.pixels.length];
    for(int pxl=0;pxl<pxls.length;pxl++){
      pxls[pxl]=new Pxl(pxl);
    }
    println("Count of pixels: "+pxls.length);
  }
  void analyze(){
    for(Pxl pxl:pxls){
      pxl.province=-1;
    }
    //Provinces
    provinces=new Province[0];
    int provinceCount=0;
    for(Pxl pxl:pxls){
      if(pxl.province==-1){
        if(provinceCount==provinces.length){
          provinces=(Province[])expand(provinces);
        }
        provinces[provinceCount]=new Province(provinceCount,pxl);
        provinceCount++;
      }
    }
    provinces=(Province[])subset(provinces,0,provinceCount);
    //Section count, neighbors, pxl radii
    xOriginal=new float[provinces.length];
    yOriginal=new float[provinces.length];
    for(Province province:provinces){
      province.analyze();
      xOriginal[province.num]=province.x;
      yOriginal[province.num]=province.y;
    }
    println("Count of provinces: "+provinces.length);

  }
  void attemptFlip(){
    boolean thisAttemptHasFailed=false;
    //Choose two random pxls in different provinces
    int pxl0,pxl1,province0,province1;
    /*do{
      pxl0=int(random(pxls.length));
      pxl1=int(random(pxls[pxl0].neighbors.length));
      pxl1=pxls[pxl0].neighbors[pxl1];
      province0=pxls[pxl0].province;
      province1=pxls[pxl1].province;
    }while(province0==province1);*/
    do{
      province0=int(random(provinces.length));
      province1=int(random(provinces[province0].neighbors.length));
      province1=provinces[province0].neighbors[province1];
    }while(1==0/*provinces[province0].clr==colorWater||provinces[province0].clr==colorWasteland*/);
    do{
      pxl0=int(random(provinces[province0].pxls.length));
      pxl0=provinces[province0].pxls[pxl0];
      pxl1=int(random(provinces[province1].pxls.length));
      pxl1=provinces[province1].pxls[pxl1];
      aMatchWasFound=false;
      for(int neighbor:pxls[pxl0].neighbors){
        if(pxls[neighbor].province==province1){
          aMatchWasFound=true;
          break;
        }
      }
      if(aMatchWasFound){
        aMatchWasFound=false;
        for(int neighbor:pxls[pxl1].neighbors){
          if(pxls[neighbor].province==province0){
            aMatchWasFound=true;
            break;
          }
        }
      }
    }while(!aMatchWasFound);//Both pixels must be on the border between the chosen provinces
    //Would executing this flip increase the sum of radii?
    //if(pxls[pxl0].r<dist(pxls[pxl0].x,pxls[pxl0].y,provinces[province1].x,provinces[province1].y)||pxls[pxl1].r<dist(pxls[pxl1].x,pxls[pxl1].y,provinces[province0].x,provinces[province0].y)){
    if(pxls[pxl0].r+pxls[pxl1].r<dist(pxls[pxl0].x,pxls[pxl0].y,provinces[province1].x,provinces[province1].y)+dist(pxls[pxl1].x,pxls[pxl1].y,provinces[province0].x,provinces[province0].y)){
      thisAttemptHasFailed=true;
    }
    //Would executing this flip increase the number of sections in either province, or create a new adjacency?
    /*if(!thisAttemptHasFailed){
      int neighborProvince;
      boolean flipWillMakeNewSection=true;
      boolean flipWillMakeNewAdjacency=false;
      //Flipping pxl0 to pxl1's position
      for(int neighborPxl:pxls[pxl1].neighbors){
        neighborProvince=pxls[neighborPxl].province;
        if(neighborProvince==province0){
          flipWillMakeNewSection=false;
        }else{
          aMatchWasFound=false;
          for(int neighbor:provinces[province0].neighbors){
            if(neighborProvince==neighbor){
              aMatchWasFound=true;
              break;
            }
          }
          if(!aMatchWasFound){
            flipWillMakeNewAdjacency=true;
            break;
          }
        }
      }
      if(flipWillMakeNewSection||flipWillMakeNewAdjacency){
        thisAttemptHasFailed=true;
      }else{
        flipWillMakeNewSection=true;flipWillMakeNewAdjacency=false;
        //Flipping pxl1 to pxl0's position
        for(int neighborPxl:pxls[pxl0].neighbors){
          neighborProvince=pxls[neighborPxl].province;
          if(neighborProvince==province1){
            flipWillMakeNewSection=false;
          }else{
            aMatchWasFound=false;
            for(int neighbor:provinces[province1].neighbors){
              if(neighborProvince==neighbor){
                aMatchWasFound=true;
                break;
              }
            }
            if(!aMatchWasFound){
              flipWillMakeNewAdjacency=true;
              break;
            }
          }
        }
        if(flipWillMakeNewSection||flipWillMakeNewAdjacency){
          thisAttemptHasFailed=true;
        }
      }
    }*/
    //Conclusion
    if(!thisAttemptHasFailed){
      color tempColor=pxls[pxl0].clr;
      pxls[pxl0].clr=pxls[pxl1].clr;
      pxls[pxl1].clr=tempColor;
      //analyze();
      int sectionCount0Old=provinces[province0].sectionCount;
      int sectionCount1Old=provinces[province1].sectionCount;
      int[] neighbors0Old=provinces[province0].neighbors;
      int[] neighbors1Old=provinces[province1].neighbors;
      provinces[province0]=new Province(province0,pxls[pxl1]);
      provinces[province1]=new Province(province1,pxls[pxl0]);
      provinces[province0].analyze();
      provinces[province1].analyze();
      //Ensure that adjacencies haven't changed
      //Ensure that section count has remained stable or has fallen
      if(!thisAttemptHasFailed&&(provinces[province0].sectionCount>sectionCount0Old||provinces[province1].sectionCount>sectionCount1Old)){
        thisAttemptHasFailed=true;
      }
      if(!thisAttemptHasFailed){
        if(neighbors0Old.length!=provinces[province0].neighbors.length||neighbors1Old.length!=provinces[province1].neighbors.length){
          thisAttemptHasFailed=true;
        }else{
          for(int neighbor=0;neighbor<neighbors0Old.length;neighbor++){
            if(neighbors0Old[neighbor]!=provinces[province0].neighbors[neighbor]){
              thisAttemptHasFailed=true;
              break;
            }
          }
          if(!thisAttemptHasFailed){
            for(int neighbor=0;neighbor<neighbors1Old.length;neighbor++){
              if(neighbors1Old[neighbor]!=provinces[province1].neighbors[neighbor]){
                thisAttemptHasFailed=true;
                break;
              }
            }
          }
        }
      }
      if(!thisAttemptHasFailed){
        successfulFlips++;
      }else{
        tempColor=pxls[pxl0].clr;
        pxls[pxl0].clr=pxls[pxl1].clr;
        pxls[pxl1].clr=tempColor;
        provinces[province0]=new Province(province0,pxls[pxl0]);
        provinces[province1]=new Province(province1,pxls[pxl1]);
        provinces[province0].analyze();
        provinces[province1].analyze();
      }
    }
  }
  void export(){
    image.loadPixels();
    for(Pxl pxl:pxls){
      image.pixels[pxl.num]=pxl.clr;
    }
    image.updatePixels();
    image.save("output/"+millis()/1000+" seconds, "+frameCount+" attempts, "+successfulFlips+" successes.png");
  }
}
class Pxl{
  int num;//Unique
  color clr;
  int x,y;//Location (from NW toward SE)
  int[] neighbors;
  int province;
  float r;
  boolean hasBeenSectioned;
  Pxl(int input){
    num=input;
    clr=image.pixels[num];
    x=num%image.width;
    y=num/image.width;
    neighbors=new int[4];
    int neighborCount=0;
    if(x<image.width-1){
      neighbors[neighborCount]=num+1;
      neighborCount++;
    }else if(mapIsCylinder){
      neighbors[neighborCount]=num+1-image.width;
      neighborCount++;
    }
    if(y>0){
      neighbors[neighborCount]=num-image.width;
      neighborCount++;
    }
    if(x>0){
      neighbors[neighborCount]=num-1;
      neighborCount++;
    }else if(mapIsCylinder){
      neighbors[neighborCount]=num-1+image.width;
      neighborCount++;
    }
    if(y<image.height-1){
      neighbors[neighborCount]=num+image.width;
      neighborCount++;
    }
    neighbors=subset(neighbors,0,neighborCount);
    province=-1;
  }
}
class Province{
  int num;
  color clr;
  int[] pxls;
  float x,y;
  int[] neighbors;
  int sectionCount;
  Province(int input0,Pxl input1){
    num=input0;
    clr=input1.clr;
    pxls=new int[0];
    int pxlCount=0;
    if(frameCount==0){
      x=0;
      y=0;
    }else{
      x=map.xOriginal[num];
      y=map.yOriginal[num];
    }
    for(Pxl pxl:map.pxls){
      if(pxl.clr==clr){
        if(pxlCount==pxls.length){
          pxls=expand(pxls);
        }
        pxls[pxlCount]=pxl.num;
        if(frameCount==0){
          x+=float(pxl.x);
          y+=float(pxl.y);
        }
        pxlCount++;
        pxl.province=num;
      }
    }
    pxls=subset(pxls,0,pxlCount);
    if(frameCount==0){
      x/=float(pxls.length);
      y/=float(pxls.length);
    }
    //println("Province "+num+" has "+pxls.length+" pxls.");
  }
  void analyze(){
    //Section count, neighbors, pxl radii
    neighbors=new int[0];
    int neighborCount=0;
    for(int pxl:pxls){
      map.pxls[pxl].r=dist(x,y,float(map.pxls[pxl].x),float(map.pxls[pxl].y));
      map.pxls[pxl].hasBeenSectioned=false;
      for(int neighborPxl:map.pxls[pxl].neighbors){
        if(map.pxls[neighborPxl].province!=num){
          aMatchWasFound=false;
          for(int neighborProvince:neighbors){
            if(map.pxls[neighborPxl].province==neighborProvince){
              aMatchWasFound=true;
              break;
            }
          }
          if(!aMatchWasFound){
            if(neighborCount==neighbors.length){
              neighbors=expand(neighbors);
            }
            neighbors[neighborCount]=map.pxls[neighborPxl].province;
            neighborCount++;
          }
        }
      }
    }
    neighbors=sort(subset(neighbors,0,neighborCount));
    //println("Count of provinces neighboring province "+num+": "+neighbors.length);
    sectionCount=0;
    for(int pxl:pxls){
      if(!map.pxls[pxl].hasBeenSectioned){
        map.pxls[pxl].hasBeenSectioned=true;
        sectionCount++;
        do{
          aMatchWasFound=false;
          for(int pxl2:pxls){
            if(!map.pxls[pxl2].hasBeenSectioned){
              for(int neighbor:map.pxls[pxl2].neighbors){
                if(map.pxls[neighbor].province==num&&map.pxls[neighbor].hasBeenSectioned){
                  aMatchWasFound=true;
                  map.pxls[pxl2].hasBeenSectioned=true;
                  break;
                }
              }
            }
          }
        }while(aMatchWasFound);
      }
    }
    //println("Count of sections in province "+num+": "+sectionCount);
  }
}