论坛交流
首页办公自动化| 网页制作| 平面设计| 动画制作| 数据库开发| 程序设计| 全部视频教程
应用视频: Windows | Word2007 | Excel2007 | PowerPoint2007 | Dreamweaver 8 | Fireworks 8 | Flash 8 | Photoshop cs | CorelDraw 12
编程视频: C语言视频教程 | HTML | Div+Css布局 | Javascript | Access数据库 | Asp | Sql Server数据库Asp.net  | Flash AS
当前位置 > 文字教程 > Flash AS编程教程
Tag:2.0,3.0菜鸟,游戏,,cs,技巧,源码,,文本,文字,函数,音乐,随机,拖拽,asp,access,xml,mc,视频教程

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

文章类别:Flash AS编程 | 发表日期:2008-10-6 17:35:59


[DEMO]连连看试玩 
连连看设计思路与源码[一]-地图类   连连看设计思路与源码[二]-寻路算法   连连看设计思路与源码[三]-显示与操作


在第一节中,我们已经知道了如何生成一个初始地图,那么接下来就是必须对此地图中对被点击到的两个图案进行连接测试,当然,首先必须要求两个点击的图案必须一样,否则就无需做连接测试了

那么连接的情况就有:

  • 直线相连
  • 一个折点的相连
  • 二个折点的相连

那么我们先来实现直线相连测试的算法.直线相连,分为两种情总,一种是两个目标图案处于同一行,另一种就是处于同一列.

以下是判断的代码:

c为列,r为行,所以c1,r1为第一个图案的坐标,c2,r2为第二个图案的坐标.我们将他抽像为一个点吧.那么第一个图案设为点P,第二个图案设为点Q

//判断同一直线上的两个点是否通畅
        private function lineCheck(c1:uint,r1:uint,c2:uint,r2:uint):Boolean{           
            if(c1==c2 && r1==r2)return true;//同一点
            else if(c1==c2){//两点处于同一列               
                if(r1>r2){//确保r1<r2,因为两点位置互换不影响比较结果
                    var t:uint = r1;
                    r1=r2;
                    r2=t;
                }
                if(r1+1==r2)return true;//两点相邻
                for(var i:uint=r1+1;i<r2;i++){
                    if(mapArray[i][c1]>0)return false;
                }
                return true;
            }
            else if(r1==r2){//两点处于同一行               
                if(c1>c2){//确保c1<c2
                    var t:uint=c1;
                    c1=c2;
                    c2=t;
                }
                if(c1+1==c2)return true;//两点相邻
                for(var i:uint=c1+1;i<c2;i++){
                    if(mapArray[r1][i]>0)return false;
                }
                return true;
            }
            return false;//两点不在同一直线
        }

 

图案相对位置的情况只有两种,一种是在同一直线,另外一种则为不在同一直线

图案在同一直线上的相连有两种连法,一种是直连,如果无法直连,则必须得通过两个折点连起来.如图为处于同一直线的两点连接的所有方式

               
  Q         P  
  P P     Q    
    P     Q    
  Q P     Q    
  P         Q  
        P      
  P Q   Q      

那么假设P和Q处于同一行.则测试的方法为,经过P,Q分别处两条竖直线AG,HN,如图

    A     H    
    B     I    
    C     J    
    D     K    
    P     Q    
    E     L    
    F     M    
    G     N    

然后再经过各点作水平线,分别为AH,BI,CJ,DK,PQ,EL,FM,GN,则我们要测试的路线为PAHQ,PBIQ,PCJQ,PDKQ,PQ,PELQ,PFMQ,PGNQ,只要其中的一条路线能够通过,则代表该两点是可以消掉的.

同理,当PQ处于同一列时,则通过PQ作两条水平线,然后再对连结每一条垂直线,再测试各条通路是否可以通过. 

               
               
A B C P D E F G
               
H I J Q K L M N
               
               
               

而当P和Q处于不同一直线时,其实就是对P和Q的水平线的测试和竖直线的测试的综合,只要一测试路通,就停止测试.如果水平与竖直都找不到通路的话,则认为两点不可连. 

      O   W    
      R   X    
A B C P D E F G
      S   Y    
H I J K L Q M N
      T   Z    
      U   V    

以下是代码的实现:

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;
            }
        }

视频教程列表
文章教程搜索
 
Flash AS推荐教程
Flash AS热门教程
看全部视频教程
购买方式/价格
购买视频教程: 咨询客服
tel:15972130058