习作DB_在四边方格地图里寻找路径

给确定某点设定一个移动力值, 移动力值就是它在地图上最远可能达到的距离.
给每个地图方格设定一个障碍值, 经过这个方格时移动力将被加量消耗.
给定某两点后, 在确定移动力和地图配置的情况下, 找出地图上从开始点到结束点的可能路径.
如果可以找到, 则显示该路径, 如果找不到, 则不显示.

参考思路:
– 参考文章一. (你需要谷歌翻译…)
– 参考文章二. (你还是需要谷歌翻译…)

上面参考文章里个人需要回避掉的问题:
– 我不想处理基于二维数组排列的地图.
– 从给定终点出发同时向四个方向寻径必然使方向顺序问题不可回避(文章中选择保留经典迷宫右手法则即 上->右->下->左).
– 计算量随移动力扩大而指数增长.

为回避上述问题的简化思路:
– 限制地图形状为正方形, 地图单元格用一维数组排列.
– 不寻求最短路径, 只寻求能最快能算出的可能路径, 则寻径只需要从两点构成的方形两边的两个方向.
– 方向顺序由两点构成的方形纵横比决定, 先短后长.
– 限制路径转弯最多折角两次, 第一次直角路径如果无法到达结束点(即路径上的障碍之总和大于给定移动力), 则将长边往起始方向平移一格尝试, 循环到最后路径为对角直角路径为止. 如果最后路径仍无法到达结束点, 则视该点不可到达, 结束寻找.

简化后造成的问题:
– 因为实际可以通过多次折角达到的结束点因为折角限制仍会被视为不可到达, 使地图配置本身成斜角时寻径能力缩短.

鼠标位置:选择终点
[W|S|A|D]:移动起始点
[F]:改变移动力
[Q]:退出程序

在2.0内制作， 用3.0以上运行可能会报错:

//- --- --- ---
//- public
//- --- --- ---
//-
static final float C_MAP_OBSTACLE_PERCENTAGE=1.1f; //<<< we dont need random map yet
static final int C_MAP_OBSTACLE_MAX_VALUE=2;
static final int C_MAP_GRIDWIDTH_MAX=12;
//-
//-
int pbGridScale =16;
int pbGridFill  =16;
//--
int pbPathStartX =0;
int pbPathStartY =0;
int pbMAbility=4;
//--
int pbPathEndX =0;
int pbPathEndY =0;
//-
EcMap pbTheMap;

void setup() {size(320, 240);noStroke();frameRate(16);textAlign(LEFT, TOP);ellipseMode(CENTER);
  frame.setTitle("UnitMap");
  //--
  pbTheMap=new EcMap(C_MAP_GRIDWIDTH_MAX);
  //--** Walls  
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(2, 2)).ccSetObstacle(9);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(3, 2)).ccSetObstacle(9);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(2, 3)).ccSetObstacle(9);
  //--
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(5, 2)).ccSetObstacle(9);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(6, 2)).ccSetObstacle(9);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(6, 3)).ccSetObstacle(9);
  //--  
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(2, 5)).ccSetObstacle(9);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(2, 6)).ccSetObstacle(9);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(3, 6)).ccSetObstacle(9);
  //--  
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(5, 6)).ccSetObstacle(9);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(6, 6)).ccSetObstacle(9);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(6, 5)).ccSetObstacle(9);
  //--** Sands
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(4, 2)).ccSetObstacle(1);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(4, 3)).ccSetObstacle(1);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(3, 3)).ccSetObstacle(1);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(3, 4)).ccSetObstacle(1);
  pbTheMap.cmMaskList.get(pbTheMap.ccTellIndexByGrid(2, 4)).ccSetObstacle(1);
  //--
}//+++

void draw(){background(0);
  //--
  for(EcMask it:pbTheMap.cmMaskList){it.ccSetOnPath(false);}
  //--
  {
    ArrayList<EcMask> lpPath=pbTheMap.ccTellPosiblePath(pbPathStartX, pbPathStartY, pbPathEndX, pbPathEndY); 
    if(!lpPath.isEmpty()){
      for(EcMask it:lpPath){it.ccSetOnPath(true);}
    }
  }
  //--
  for(EcMask it:pbTheMap.cmMaskList){
    if(it.ccIsMouseOver()){
      pbPathEndX=it.cmGridX;
      pbPathEndY=it.cmGridY;
    }
    it.ccUpdate();
  }  
  //--
}//+++

void keyPressed(){switch(key){
  //--
  case 'w':fsShiftTarget( 0, -1);break;
  case 's':fsShiftTarget( 0,  1);break;
  case 'a':fsShiftTarget(-1,  0);break;
  case 'd':fsShiftTarget( 1,  0);break;
  //--
  case 'f':
    pbMAbility++;pbMAbility&=0x07;
    pbMAbility=pbMAbility==0?1:pbMAbility;
    break;
  case 'r': //<<< for map resetting but we dont have random map yet
    break;
  //--
  case 'e': //<<< reserved key
    break;
  //--
  case 'q':fsPover();
  default:break;
}}//+++

//* *** *** *** *** ***
//*
//* Operate
//*
//* *** *** *** *** ***
//- --- --- ---

void fsShiftTarget(int pxX, int pxY){
  pbPathStartX+=pxX;pbPathStartX=constrain(pbPathStartX,0,pbTheMap.cmGridDivide-1);
  pbPathStartY+=pxY;pbPathStartY=constrain(pbPathStartY,0,pbTheMap.cmGridDivide-1);
}//+++

void fsPover(){
  exit();
}//+++
//< <<< <<< <<< <<< <<< operate

//* *** *** *** *** ***
//*
//* Class
//*
//* *** *** *** *** ***

class EcMap{
  ArrayList<EcMask> cmMaskList;
  int cmGridDivide;
  //--
  EcMap(int pxDivide){
    cmMaskList=new ArrayList<EcMask>();
    int lpCapa=pxDivide*pxDivide;
    for(int i=0;i<lpCapa;i++){
      int lpX=i%pxDivide;
      int lpY=i/pxDivide;
      cmMaskList.add(
        new EcMask(lpX, lpY,
          random(1)>C_MAP_OBSTACLE_PERCENTAGE?((int)random(1,C_MAP_OBSTACLE_MAX_VALUE)):0
        )
      );
    }
    cmGridDivide=pxDivide;
  }
  //--** 
  ArrayList<EcMask> ccTellDirectPath(int pxStartX, int pxStartY, int pxEndX, int pxEndY){
    ArrayList<EcMask> lpRes=new ArrayList<EcMask>();
    //--
    int lpSampleX=pxStartX;
    int lpSampleY=pxStartY;
    //--
    int lpDiffX=pxEndX-pxStartX;
    int lpDiffY=pxEndY-pxStartY;
    int lpStage=abs(lpDiffX)<abs(lpDiffY)?2:1;
    int lpStagePusher=lpStage==2?-1:1;
    //--
    //--
    while((lpStage==1)||(lpStage==2)){
      switch(lpStage){
        case 1:
          for(int i=0,s=(int)abs(lpDiffX);i<=s;i++){
            if(lpSampleX==pxEndX){break;}
            lpSampleX+=(lpDiffX<0)?-1:1;
            lpRes.add(cmMaskList.get(ccTellIndexByGrid(lpSampleX, lpSampleY)));
            //[DEBUG]::print("got::X--"+nf(lpSampleX,2));print("::Y--"+nf(lpSampleY,2));println("::ID--"+nf(ccTellIndexByGrid(lpSampleX, lpSampleY),2));
          }lpStage+=lpStagePusher;
          break;
        case 2:
          for(int i=0,s=(int)abs(lpDiffY);i<=s;i++){
            if(lpSampleY==pxEndY){break;}
            lpSampleY+=(lpDiffY<0)?-1:1;
            lpRes.add(cmMaskList.get(ccTellIndexByGrid(lpSampleX, lpSampleY)));
            //[DEBUG]::print("got::X--"+nf(lpSampleX,2));print("::Y--"+nf(lpSampleY,2));println("::ID--"+nf(ccTellIndexByGrid(lpSampleX, lpSampleY),2));
          }lpStage+=lpStagePusher;
          break;
        default:break;
      }
    }
    //[DEBUG]::println(">>> end");
    return lpRes;
    //--
  }
  //--  
  ArrayList<EcMask> ccTellPosiblePath(int pxStartX, int pxStartY, int pxEndX, int pxEndY){
    ArrayList<EcMask> lpRes=new ArrayList<EcMask>();    
    int lpCost;
    //--
    int lpSampleX=pxStartX;
    int lpSampleY=pxStartY;
    //--
    int lpDiffX=pxEndX-pxStartX;
    int lpDiffY=pxEndY-pxStartY;
    boolean lpIsXFirst=abs(lpDiffY)>abs(lpDiffX);
    //--
    lpRes.clear();
    lpRes.addAll(ccTellDirectPath(lpSampleX, lpSampleY, pxEndX, pxEndY));
    //--    
    if(lpDiffX==0||lpDiffY==0){
      lpCost=ccTellCostValueByPath(lpRes);
      if(lpCost<=pbMAbility){
        return lpRes;
      }else{
        lpRes.clear();
        return lpRes;
      }
    }
    //--
    for(int i=0,s=lpIsXFirst?
                    (int)abs(lpDiffX):(int)abs(lpDiffY);
                    i<s;i++){
      lpCost=ccTellCostValueByPath(lpRes);
      if(lpCost<=pbMAbility){return lpRes;}else{
        lpRes.clear();
        int lpTryX=lpSampleX;
        int lpTryY=lpSampleY;
        for(int j=0;j<=i;j++){
          if(lpIsXFirst){lpTryX+=(lpDiffX<0)?-1:1;}
          else{          lpTryY+=(lpDiffY<0)?-1:1;}
          lpRes.add(cmMaskList.get(ccTellIndexByGrid(lpTryX, lpTryY)));
        }
        lpRes.addAll(ccTellDirectPath(lpTryX, lpTryY, pxEndX, pxEndY));
      }
    }
    lpCost=ccTellCostValueByPath(lpRes);
    if(lpCost<=pbMAbility){return lpRes;}
    lpRes.clear();
    return lpRes;
  }
  //--
  int ccTellCostValueByPath(ArrayList<EcMask> pxPath){
    int lpRes=0;
    if(pxPath==null){return 255;}
    if(pxPath.isEmpty()){return 255;}    
    for(EcMask it:pxPath){lpRes+=(it.cmObsatcleLevel+1);}
    return lpRes;
  }
  //--
  int ccTellIndexByGrid(int pxX, int pxY){return pxY*cmGridDivide+pxX;}
  //--
}//+++

class EcMask{
  //--
  int cmGridX, cmGridY;
  int cmAbsoX, cmAbsoY;
  int cmGridDist;
  int cmObsatcleLevel;
  boolean cmIsOnPath;
  EcMask(int pxGridX, int pxGridY, int pxObsatcleLevel){
    cmGridX=pxGridX;cmAbsoX=0;
    cmGridY=pxGridY;cmAbsoY=0;
    cmGridDist=0;
    cmObsatcleLevel=pxObsatcleLevel;
    cmIsOnPath=false;
  }
  //--**
  void ccUpdate(){
    cmAbsoX=cmGridX*pbGridFill;
    cmAbsoY=cmGridY*pbGridFill;
    cmGridDist=
      (int)abs(pbPathStartX-cmGridX)+
      (int)abs(pbPathStartY-cmGridY);
    //--
    int lpColor=ccTellColor();
    if(ccIsMouseOver()){lpColor+=0x00111111;lpColor|=0xFF000000;}
    //--
    fill(lpColor); rect(cmAbsoX, cmAbsoY, pbGridScale, pbGridScale);
    if(cmObsatcleLevel!=0){
      fill(color(0xCC,0xCC,0x33));
      text(nf(cmObsatcleLevel,1),cmAbsoX,cmAbsoY);
    }
    //--
  }
  //--**
  void ccSetOnPath(boolean pxStat){cmIsOnPath=pxStat;}
  void ccSetObstacle(int pxValue){cmObsatcleLevel=pxValue;}
  //--
  int ccTellColor(){
    //-- ** <<< earlier one gets higher priority
    if(ccIsPathStart()){return color(0xCC,0xCC,0x33);}
    if(ccIsPathEnd()){return color(0xCC,0x33,0x33);}
    if(cmIsOnPath){return color(0xCC,0x99,0x33);}
    if(ccTellAbility()){return color(0x99,0x99,0x99);}
    return color(0x66,0x66,0x66);
  }
  //--
  boolean ccTellAbility(){return cmGridDist<=(pbMAbility);}
  boolean ccIsMouseOver(){return ccIsContaining(mouseX, mouseY);}  
  boolean ccIsPathStart(){return (pbPathStartX==cmGridX)&&(pbPathStartY==cmGridY);}
  boolean ccIsPathEnd(){return (pbPathEndX==cmGridX)&&(pbPathEndY==cmGridY);}
  boolean ccIsContaining(int pxX, int pxY){
    return (pxX>cmAbsoX)&&(pxX<cmAbsoX+pbGridScale)&&
           (pxY>cmAbsoY)&&(pxY<cmAbsoY+pbGridScale);
    //--
  }
  //--
}//+++

//< <<< <<< <<< <<< <<< Class

//EOF

最后编辑：2018-10-31

作者：constrain

nullpointerexception

站内专栏 站点