连连看设计思路与源码[二]-寻路算法(as3.0)

private var roadPoint:Array = [-1,-1,-1,-1,-1,-1,-1,-1];//记录路径数组
private var minRoadPoint:uint = 10000;//当前最短路径格数
private var roadPointMap:BitmapData;
private var roadPointImage:Bitmap;
private var hintRoadArray:Array = [-1,-1,-1,-1];//提示的两个方块的路径
          //判断不在同一直线的两个点是否能够连接c是列,r是行,找出来的路线非最短路线
private function pointCheck(c1:uint,r1:uint,c2:uint,r2:uint):Boolean{
    if(mapArray[r1][c1]!= mapArray[r2][c2])return false;
    if(c1==c2 && r1==r2)return false;//同一点
    var i:uint=0;
    var result:Boolean=false;
    if(c1==c2){//两点在同一列               
        if(lineCheck(c1,r1,c2,r2))return true;
        for(i=0;i<mapArray[0].length;i++){
            if(mapArray[r1][i]==0 && mapArray[r2][i]==0){
                if(lineCheck(c1,r1,i,r1) && lineCheck(i,r1,i,r2) && lineCheck(i,r2,c2,r2)){
                    result = true;
                    break;
                }
            }
        }
    }
    else if(r1==r2){//两点在同一行               
        if(lineCheck(c1,r1,c2,r2))return true;
        for(i=0;i<mapArray.length;i++){
            if(mapArray[i][c1]==0 && mapArray[i][c2]==0){
                if(lineCheck(c1,r1,c1,i) && lineCheck(c1,i,c2,i) && lineCheck(c2,i,c2,r2)){
                    result = true;                       
                    break;
                }
            }
        }
    }
    else{//两点不在同一直线
        //先测试每一条垂直线 P------
        //                                         |||||||
        //                                       -------Q  
        for(i=0;i<mapArray[0].length;i++){
            if(i==c1 && mapArray[r2][i]==0){//只有一个拐角
                if(lineCheck(c1,r1,c1,r2) && lineCheck(c1,r2,c2,r2)){
                    result = true;
                    break;
                }
            }
            else if(i==c2 && mapArray[r1][i]==0){//只有一个拐角
                if(lineCheck(c2,r2,c2,r1) && lineCheck(c2,r1,c1,r1)){
                    result = true;
                    break;
                }
            }
            else if(mapArray[r1][i]==0 && mapArray[r2][i]==0){
                if(lineCheck(c1,r1,i,r1) && lineCheck(i,r1,i,r2) && lineCheck(i,r2,c2,r2)){
                    result = true;
                    break;
                }
            }
        }
        if(!result){
            //再测试每一条水平线 P  |__|
            //                                           |__|
            //                                           |__|Q
            //                                           |    |
             for(i=0;i<mapArray.length;i++){//只有一个拐角
                if(mapArray[i][c1]==0 && mapArray[i][c2]==0){
                    if(i==r1 && mapArray[r1][c2]==0){
                        if(lineCheck(c1,r1,c2,r1) && lineCheck(c2,r1,c2,r2)){
                            result = true;
                            break;
                        }
                    }
                    else if(i==r2 && mapArray[r2][c1]==0){//只有一个拐角
                        if(lineCheck(c1,r1,c1,r2) && lineCheck(c1,r2,c2,r2)){
                            result = true;
                            break;
                        }
                    }
                    else if(lineCheck(c1,r1,c1,i) && lineCheck(c1,i,c2,i) && lineCheck(c2,i,c2,r2)){
                        result = true;                       
                        break;
                    }
                }
             }
        }
    }           
   
    return result;
}
以下是算法的改进,能够找到最短的路径并记录下来.

//寻找最短路线,效率相对较低.
        private function findShortRoad(c1:uint,r1:uint,c2:uint,r2:uint):Boolean{
            if(mapArray[r1][c1]!= mapArray[r2][c2])return false;
            if(c1==c2 && r1==r2)return false;//同一点
            var i:uint=0;
            var result:Boolean=false;
            if(c1==c2){//两点在同一列               
                if(lineCheck(c1,r1,c2,r2)){//直连是最短的路径
                    addRoadPoint(c1,r1,c1,r1,c1,r1,c2,r2);
                    return true;
                }
                for(i=0;i<mapArray[0].length;i++){
                    if(mapArray[r1][i]==0 && mapArray[r2][i]==0){
                        if(lineCheck(c1,r1,i,r1) && lineCheck(i,r1,i,r2) && lineCheck(i,r2,c2,r2)){
                            result = true;
                            roadPointCount(c1,r1,i,r1,i,r2,c2,r2);                           
                        }
                    }
                }
            }
            else if(r1==r2){//两点在同一行               
                if(lineCheck(c1,r1,c2,r2)){
                    addRoadPoint(c1,r1,c1,r1,c2,r2,c2,r2);
                    return true;
                }
                for(i=0;i<mapArray.length;i++){
                    if(mapArray[i][c1]==0 && mapArray[i][c2]==0){
                        if(lineCheck(c1,r1,c1,i) && lineCheck(c1,i,c2,i) && lineCheck(c2,i,c2,r2)){
                            result = true;                       
                            roadPointCount(c1,r1,c1,i,c2,i,c2,r2);
                        }
                    }
                }
            }
            else{//两点不在同一直线
                //先测试每一条垂直线 P------
                //                |||||||
                //                -------Q  
                for(i=0;i<mapArray[0].length;i++){
                    if(i==c1 && mapArray[r2][i]==0){//只有一个拐角
                        if(lineCheck(c1,r1,c1,r2) && lineCheck(c1,r2,c2,r2)){
                            result = true;
                            roadPointCount(c1,r1,c1,r1,c1,r2,c2,r2);
                        }
                    }
                    else if(i==c2 && mapArray[r1][i]==0){//只有一个拐角
                        if(lineCheck(c2,r2,c2,r1) && lineCheck(c2,r1,c1,r1)){
                            result = true;
                            roadPointCount(c2,r2,c2,r2,c2,r1,c1,r1);
                        }
                    }
                    else if(mapArray[r1][i]==0 && mapArray[r2][i]==0){
                        if(lineCheck(c1,r1,i,r1) && lineCheck(i,r1,i,r2) && lineCheck(i,r2,c2,r2)){
                            result = true;
                            roadPointCount(c1,r1,i,r1,i,r2,c2,r2);
                        }
                    }
                }               
                //再测试每一条水平线 P  |__|
                //                   |__|
                //                   |__|Q
                //                   |  |
                 for(i=0;i<mapArray.length;i++){//只有一个拐角
                    if(mapArray[i][c1]==0 && mapArray[i][c2]==0){
                        if(i==r1 && mapArray[r1][c2]==0){
                            if(lineCheck(c1,r1,c2,r1) && lineCheck(c2,r1,c2,r2)){
                                result = true;
                                roadPointCount(c1,r1,c1,r1,c2,r1,c2,r2);
                            }
                        }
                        else if(i==r2 && mapArray[r2][c1]==0){//只有一个拐角
                            if(lineCheck(c1,r1,c1,r2) && lineCheck(c1,r2,c2,r2)){
                                result = true;
                                roadPointCount(c1,r1,c1,r1,c1,r2,c2,r2);
                            }
                        }
                        else if(lineCheck(c1,r1,c1,i) && lineCheck(c1,i,c2,i) && lineCheck(c2,i,c2,r2)){
                            result = true;                       
                            roadPointCount(c1,r1,c1,i,c2,i,c2,r2);
                        }
                    }
                 }               
            }           
            return result;
        }
       
        //记录路径点
        private function addRoadPoint(c1:uint,r1:uint,c2:uint,r2:uint,c3:uint,r3:uint,c4:uint,r4:uint):void{
            roadPoint[0] = c1;
            roadPoint[1] = r1;
            roadPoint[2] = c2;
            roadPoint[3] = r2;
            roadPoint[4] = c3;
            roadPoint[5] = r3;
            roadPoint[6] = c4;
            roadPoint[7] = r4;           
        }
       
        //始终记录最短的路线的路径点
        private function roadPointCount(c1:uint,r1:uint,c2:uint,r2:uint,c3:uint,r3:uint,c4:uint,r4:uint):void{
            var count:uint = 0;
            count = Math.abs(c2-c1) + Math.abs(c3-c2) + Math.abs(c4-c3) + Math.abs(r2-r1) + Math.abs(r3-r2) + Math.abs(r4-r3);
            if(count < minRoadPoint){
                addRoadPoint(c1,r1,c2,r2,c3,r3,c4,r4);
                minRoadPoint = count;
            }
        }