精华内容
下载资源
问答
  • 游戏开发常用算法

    热门讨论 2013-03-01 21:17:13
    游戏开发常用算法,讲解一些常见的游戏开发算法……
  • 游戏开发常用算法

    千次阅读 2017-08-11 17:16:42
    要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序的数据结构和变量用来描述问题的对象,...
    要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序的数据结构和变量用来描述问题的对象,程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。 
    算法是问题求解过程的精确描述,一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止,或终止于给出问题的解,或终止于指出问题对此输入数据无解。 
        通常求解一个问题可能会有多种算法可供选择,选择的主要标准是算法的正确性和可靠性,简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。 
        算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和藐视算法,在算法设计时又常常采用递归技术,用递归描述算法。

    一、迭代法 

    迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: 
    (1)   选一个方程的近似根,赋给变量x0; 
    (2)   将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; 
    (3)   当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。 
    若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:
    【算法】迭代法求方程的根 
    {   x0=初始近似根; 
    do { 
        x1=x0; 
        x0=g(x1);   /*按特定的方程计算新的近似根*/ 
        } while ( fabs(x0-x1)>Epsilon); 
    printf(“方程的近似根是%f\n”,x0); 

    迭代算法也常用于求方程组的根,令 
        X=(x0,x1,…,xn-1) 
    设方程组为: 
        xi=gi(X)     (I=0,1,…,n-1) 
    则求方程组根的迭代算法可描述如下: 
    【算法】迭代法求方程组的根 
    {   for (i=0;i      x=初始近似根; 
        do { 
          for (i=0;i        y=x; 
          for (i=0;i        x=gi(X); 
          for (delta=0.0,i=0;i        if (fabs(y-x)>delta)     delta=fabs(y-x); 
          } while (delta>Epsilon); 
        for (i=0;i      printf(“变量x[%d]的近似根是 %f”,I,x); 
        printf(“\n”); 

    具体使用迭代法求根时应注意以下两种可能发生的情况: 
    (1)   如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; 
    (2)   方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。

    二、穷举搜索法

    穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。
    【问题】 将A、B、C、D、E、F这六个变量排成如图所示的三角形,这六个变量分别取[1,6]上的整数,且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。
    程序引入变量a、b、c、d、e、f,并让它们分别顺序取1至6的证书,在它们互不相同的条件下,测试由它们排成的如图所示的三角形三条边上的变量之和是否相等,如相等即为一种满足要求的排列,把它们输出。当这些变量取尽所有的组合后,程序就可得到全部可能的解。细节见下面的程序。
    【程序1】
    # include 
    void main()
    { int a,b,c,d,e,f;
    for (a=1;a<=6;a++) 
    for (b=1;b<=6;b++) {
    if (b==a) continue;
    for (c=1;c<=6;c++) {
    if (c==a)||(c==b) continue;
    for (d=1;d<=6;d++) {
    if (d==a)||(d==b)||(d==c) continue;
    for (e=1;e<=6;e++) {
    if (e==a)||(e==b)||(e==c)||(e==d) continue;
    f=21-(a+b+c+d+e);
    if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {
    printf(“%6d,a);
    printf(“%4d%4d”,b,f);
    printf(“%2d%4d%4d”,c,d,e);
    scanf(“%*c”);
    }
    }
    }
    }
    }
    }
    按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形,每条边有4个变量的情况,程序的循环重数就要相应改变。
    对一组数穷尽所有排列,还有更直接的方法。将一个排列看作一个长整数,则所有排列对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数,从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每个整数,这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3,并令其对应的长整数为124653。要寻找比长整数124653更大的排列,可从该排列的最后一个数字顺序向前逐位考察,当发现排列中的某个数字比它前一个数字大时,如本例中的6比它的前一位数字4大,这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列,不能立即调整得太大,如本例中将数字6与数字4交换得到的排列126453就不是排列124653的下一个排列。为了得到排列124653的下一个排列,应从已经考察过的那部分数字中选出比数字大,但又是它们中最小的那一个数字,比如数字5,与数字4交换。该数字也是从后向前考察过程中第一个比4大的数字。5与4交换后,得到排列125643。在前面数字1,2,5固定的情况下,还应选择对应最小整数的那个排列,为此还需将后面那部分数字的排列顺序颠倒,如将数字6,4,3的排列顺序颠倒,得到排列1,2,5,3,4,6,这才是排列1,2,4,6,5,3的下一个排列。按以上想法编写的程序如下。
    【程序2】
    # include 
    # define SIDE_N 3
    # define LENGTH 3
    # define VARIABLES 6
    int A,B,C,D,E,F;
    int *pt[]={&A,&B,&C,&D,&E,&F};
    int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};
    int side_total[SIDE_N];
    main{}
    { int i,j,t,equal;
    for (j=0;j   *pt[j]=j+1;
    while(1)
    { for (i=0;i   { for (t=j=0;j   t+=*side[i][j];
    side_total[i]=t;
    }
    for (equal=1,i=0;equal&&i   if (side_total[i]!=side_total[i+1] equal=0;
    if (equal)
    { for (i=1;i   printf(“%4d”,*pt[i]);
    printf(“\n”);
    scanf(“%*c”);
    }
    for (j=VARIABLES-1;j>0;j--)
    if (*pt[j]>*pt[j-1]) break;
    if (j==0) break;
    for (i=VARIABLES-1;i>=j;i--)
    if (*pt[i]>*pt[i-1]) break;
    t=*pt[j-1];* pt[j-1] =* pt[i]; *pt[i]=t;
    for (i=VARIABLES-1;i>j;i--,j++)
    { t=*pt[j]; *pt[j] =* pt[i]; *pt[i]=t; }
    }
    }
    从上述问题解决的方法中,最重要的因素就是确定某种方法来确定所有的候选解。下面再用一个示例来加以说明。
    【问题】 背包问题
    问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
    设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中,限制重量为tw。考虑一个n元组(x0,x1,…,xn-1),其中xi=0 表示第i个物品没有选取,而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用枚举法解决背包问题,需要枚举所有的选取方案,而根据上述方法,我们只要枚举所有的n元组,就可以得到问题的解。
    显然,每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数,且这些二进制数的取值范围为0~2n-1。因此,如果把0~2n-1分别转化为相应的二进制数,则可以得到我们所需要的2n个n元组。
    【算法】
    maxv=0;
    for (i=0;i<2n;i++)
    { B[0..n-1]=0;
    把i转化为二进制数,存储于数组B中;
    temp_w=0;
    temp_v=0;
    for (j=0;j   { if (B[j]==1)
    { temp_w=temp_w+w[j];
    temp_v=temp_v+v[j];
    }
    if ((temp_w<=tw)&&(temp_v>maxv))
    { maxv=temp_v;
    保存该B数组;
    }
    }
    }

    三、递推法

    递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解,当N=1时,解或为已知,或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质,即当得到问题规模为i-1的解后,由问题的递推性质,能从已求得的规模为1,2,…,i-1的一系列解,构造出问题规模为I的解。这样,程序可从i=0或i=1出发,重复地,由已知至i-1规模的解,通过递推,获得规模为i的解,直至得到规模为N的解。
    【问题】 阶乘计算
    问题描述:编写程序,对给定的n(n≦100),计算并输出k的阶乘k!(k=1,2,…,n)的全部有效数字。
    由于要求的整数可能大大超出一般整数的位数,程序用一维数组存储长整数,存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a[ ]存储:
    N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100
    并用a[0]存储长整数N的位数m,即a[0]=m。按上述约定,数组的每个元素存储k的阶乘k!的一位数字,并从低位到高位依次存于数组的第二个元素、第三个元素……。例如,5!=120,在数组中的存储形式为:
    3 0 2 1 ……
    首元素3表示长整数是一个3位数,接着是低位到高位依次是0、2、1,表示成整数120。
    计算阶乘k!可采用对已求得的阶乘(k-1)!连续累加k-1次后求得。例如,已知4!=24,计算5!,可对原来的24累加4次24后得到120。细节见以下程序。
    # include 
    # include 
    # define MAXN 1000
    void pnext(int a[ ],int k)
    { int *b,m=a[0],i,j,r,carry;
    b=(int * ) malloc(sizeof(int)* (m+1));
    for ( i=1;i<=m;i++) b[i]=a[i];
    for ( j=1;j<=k;j++)
    { for ( carry=0,i=1;i<=m;i++)
    { r=(i   a[i]=r%10;
    carry=r/10;
    }
    if (carry) a[++m]=carry;
    }
    free(b);
    a[0]=m;
    }

    void write(int *a,int k)
    { int i;
    printf(“%4d!=”,k);
    for (i=a[0];i>0;i--)
    printf(“%d”,a[i]);
    printf(“\n\n”);
    }

    void main()
    { int a[MAXN],n,k;
    printf(“Enter the number n: “);
    scanf(“%d”,&n);
    a[0]=1;
    a[1]=1;
    write(a,1);
    for (k=2;k<=n;k++)
    { pnext(a,k);
    write(a,k);
    getchar();
    }
    }

    四、递归

    递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。
    能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。
    【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。
    斐波那契数列为:0、1、1、2、3、……,即:
    fib(0)=0;
    fib(1)=1;
    fib(n)=fib(n-1)+fib(n-2) (当n>1时)。
    写成递归函数有:
    int fib(int n)
    { if (n==0) return 0;
    if (n==1) return 1;
    if (n>1) return fib(n-1)+fib(n-2);
    }
    递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n-2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。
    在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。
    在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。
    由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。
    【问题】 组合问题
    问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1
    (4)5、3、2 (5)5、3、1 (6)5、2、1
    (7)4、3、2 (8)4、3、1 (9)4、2、1
    (10)3、2、1
    分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。
    【程序】
    # include 
    # define MAXN 100
    int a[MAXN];
    void comb(int m,int k)
    { int i,j;
    for (i=m;i>=k;i--)
    { a[k]=i;
    if (k>1)
    comb(i-1,k-1);
    else
    { for (j=a[0];j>0;j--)
    printf(“%4d”,a[j]);
    printf(“\n”);
    }
    }
    }

    void main()
    { a[0]=3;
    comb(5,3);
    }
    【问题】 背包问题
    问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
    设n件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。
    对于第i件物品的选择考虑有两种可能:
    (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。
    (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。
    按以上思想写出递归算法如下:
    try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv)
    { /*考虑物品i包含在当前方案中的可能性*/
    if(包含物品i是可以接受的)
    { 将物品i包含在当前方案中;
    if (i   try(i+1,tw+物品i的重量,tv);
    else
    /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/
    以当前方案作为临时最佳方案保存;
    恢复物品i不包含状态;
    }
    /*考虑物品i不包含在当前方案中的可能性*/
    if (不包含物品i仅是可男考虑的)
    if (i   try(i+1,tw,tv-物品i的价值);
    else
    /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/
    以当前方案作为临时最佳方案保存;
    }
    为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表:
    物品 0 1 2 3
    重量 5 3 2 1
    价值 4 4 3 1

    并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。

    按上述算法编写函数和程序如下:
    【程序】
    # include 
    # define N 100
    double limitW,totV,maxV;
    int option[N],cop[N];
    struct { double weight;
    double value;
    }a[N];
    int n;
    void find(int i,double tw,double tv)
    { int k;
    /*考虑物品i包含在当前方案中的可能性*/
    if (tw+a[i].weight<=limitW)
    { cop[i]=1;
    if (i   else
    { for (k=0;k   option[k]=cop[k];
    maxv=tv;
    }
    cop[i]=0;
    }
    /*考虑物品i不包含在当前方案中的可能性*/
    if (tv-a[i].value>maxV)
    if (i   else
    { for (k=0;k   option[k]=cop[k];
    maxv=tv-a[i].value;
    }
    }

    void main()
    { int k;
    double w,v;
    printf(“输入物品种数\n”);
    scanf((“%d”,&n);
    printf(“输入各物品的重量和价值\n”);
    for (totv=0.0,k=0;k   { scanf(“%1f%1f”,&w,&v);
    a[k].weight=w;
    a[k].value=v;
    totV+=V;
    }
    printf(“输入限制重量\n”);
    scanf(“%1f”,&limitV);
    maxv=0.0;
    for (k=0;k   find(0,0.0,totV);
    for (k=0;k   if (option[k]) printf(“%4d”,k+1);
    printf(“\n总价值为%.2f\n”,maxv);
    }
    作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。
    【程序】
    # include 
    # define N 100
    double limitW;
    int cop[N];
    struct ele { double weight;
    double value;
    } a[N];
    int k,n;
    struct { int ;
    double tw;
    double tv;
    }twv[N];
    void next(int i,double tw,double tv)
    { twv[i].=1;
    twv[i].tw=tw;
    twv[i].tv=tv;
    }
    double find(struct ele *a,int n)
    { int i,k,f;
    double maxv,tw,tv,totv;
    maxv=0;
    for (totv=0.0,k=0;k   totv+=a[k].value;
    next(0,0.0,totv);
    i=0;
    While (i>=0)
    { f=twv[i].;
    tw=twv[i].tw;
    tv=twv[i].tv;
    switch(f)
    { case 1: twv[i].++;
    if (tw+a[i].weight<=limitW)
    if (i   { next(i+1,tw+a[i].weight,tv);
    i++;
    }
    else
    { maxv=tv;
    for (k=0;k   cop[k]=twv[k].!=0;
    }
    break;
    case 0: i--;
    break;
    default: twv[i].=0;
    if (tv-a[i].value>maxv)
    if (i   { next(i+1,tw,tv-a[i].value);
    i++;
    }
    else
    { maxv=tv-a[i].value;
    for (k=0;k   cop[k]=twv[k].!=0;
    }
    break;
    }
    }
    return maxv;
    }

    void main()
    { double maxv;
    printf(“输入物品种数\n”);
    scanf((“%d”,&n);
    printf(“输入限制重量\n”);
    scanf(“%1f”,&limitW);
    printf(“输入各物品的重量和价值\n”);
    for (k=0;k   scanf(“%1f%1f”,&a[k].weight,&a[k].value);
    maxv=find(a,n);
    printf(“\n选中的物品为\n”);
    for (k=0;k   if (option[k]) printf(“%4d”,k+1);
    printf(“\n总价值为%.2f\n”,maxv);
    }

    五、回溯法

    回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。

    1、回溯法的一般描述

    可用回溯法求解的问题P,通常要能表达为:对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)∣xi∈Si ,i=1,2,…,n},给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域,且 |Si| 有限,i=1,2,…,n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

    解问题P的最朴素的方法就是枚举法,即对E中的所有n元组逐一地检测其是否满足D的全部约束,若满足,则为问题P的一个解。但显然,其计算量是相当大的。

    我们发现,对于许多问题,所给定的约束集D具有完备性,即i元组(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束意味着j(jj。因此,对于约束集D具有完备性的问题P,一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的一个约束,就可以肯定,以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解,因而就不必去搜索它们、检测它们。回溯法正是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法。

    回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树,它可以这样构造: 

    设Si中的元素可排成xi(1) ,xi(2) ,…,xi(mi-1) ,|Si| =mi,i=1,2,…,n。从根开始,让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边,按从左到右的次序,分别带权xi+1(1) ,xi+1(2) ,…,xi+1(mi) ,i=0,1,2,…,n-1。照这种构造方式,E中的一个n元组(x1,x2,…,xn)对应于T中的一个叶子结点,T的根到这个叶子结点的路径上依次的n条边的权分别为x1,x2,…,xn,反之亦然。另外,对于任意的0≤i≤n-1,E中n元组(x1,x2,…,xn)的一个前缀I元组(x1,x2,…,xi)对应于T中的一个非叶子结点,T的根到这个非叶子结点的路径上依次的I条边的权分别为x1,x2,…,xi,反之亦然。特别,E中的任意一个n元组的空前缀(),对应于T的根。

    因而,在E中寻找问题P的一个解等价于在T中搜索一个叶子结点,要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1,x2,…,xn满足约束集D的全部约束。在T中搜索所要求的叶子结点,很自然的一种方式是从根出发,按深度优先的策略逐步深入,即依次搜索满足约束条件的前缀1元组(x1i)、前缀2元组(x1,x2)、…,前缀I元组(x1,x2,…,xi),…,直到i=n为止。

    在回溯法中,上述引入的树被称为问题P的状态空间树;树T上任意一个结点被称为问题P的状态结点;树T上的任意一个叶子结点被称为问题P的一个解状态结点;树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点,它对应于问题P的一个解。

    【问题】 组合问题
    问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。
    例如n=5,r=3的所有组合为: 
    (1)1、2、3 (2)1、2、4 (3)1、2、5
    (4)1、3、4 (5)1、3、5 (6)1、4、5
    (7)2、3、4 (8)2、3、5 (9)2、4、5
    (10)3、4、5
    则该问题的状态空间为:
    E={(x1,x2,x3)∣xi∈S ,i=1,2,3 } 其中:S={1,2,3,4,5}
    约束集为: x1   显然该约束集具有完备性。
    问题的状态空间树T:

    2、回溯法的方法

    对于具有完备约束集D的一般问题P及其相应的状态空间树T,利用T的层次结构和D的完备性,在T中搜索问题P的所有解的回溯法可以形象地描述为:

    从T的根出发,按深度优先的策略,系统地搜索以其为根的子树中可能包含着回答结点的所有状态结点,而跳过对肯定不含回答结点的所有子树的搜索,以提高搜索效率。具体地说,当搜索按深度优先策略到达一个满足D中所有有关约束的状态结点时,即“激活”该状态结点,以便继续往深层搜索;否则跳过对以该状态结点为根的子树的搜索,而一边逐层地向该状态结点的祖先结点回溯,一边“杀死”其儿子结点已被搜索遍的祖先结点,直到遇到其儿子结点未被搜索遍的祖先结点,即转向其未被搜索的一个儿子结点继续搜索。

    在搜索过程中,只要所激活的状态结点又满足终结条件,那么它就是回答结点,应该把它输出或保存。由于在回溯法求解问题时,一般要求出问题的所有解,因此在得到回答结点后,同时也要进行回溯,以便得到问题的其他解,直至回溯到T的根且根的所有儿子结点均已被搜索过为止。

    例如在组合问题中,从T的根出发深度优先遍历该树。当遍历到结点(1,2)时,虽然它满足约束条件,但还不是回答结点,则应继续深度遍历;当遍历到叶子结点(1,2,5)时,由于它已是一个回答结点,则保存(或输出)该结点,并回溯到其双亲结点,继续深度遍历;当遍历到结点(1,5)时,由于它已是叶子结点,但不满足约束条件,故也需回溯。

    3、回溯法的一般流程和技术

    在用回溯法求解有关问题的过程中,一般是一边建树,一边遍历该树。在回溯法中我们一般采用非递归方法。下面,我们给出回溯法的非递归算法的一般流程:

    在用回溯法求解问题,也即在遍历状态空间树的过程中,如果采用非递归方法,则我们一般要用到栈的数据结构。这时,不仅可以用栈来表示正在遍历的树的结点,而且可以很方便地表示建立孩子结点和回溯过程。
    例如在组合问题中,我们用一个一维数组Stack[ ]表示栈。开始栈空,则表示了树的根结点。如果元素1进栈,则表示建立并遍历(1)结点;这时如果元素2进栈,则表示建立并遍历(1,2)结点;元素3再进栈,则表示建立并遍历(1,2,3)结点。这时可以判断它满足所有约束条件,是问题的一个解,输出(或保存)。这时只要栈顶元素(3)出栈,即表示从结点(1,2,3)回溯到结点(1,2)。

    【问题】 组合问题
    问题描述:找出从自然数1,2,…,n中任取r个数的所有组合。
    采用回溯法找问题的解,将找到的组合以从小到大顺序存于a[0],a[1],…,a[r-1]中,组合的元素满足以下性质:
    (1) a[i+1]>a[i],后一个数字比前一个大;
    (2) a[i]-i<=n-r+1。
    按回溯法的思想,找解过程可以叙述如下:

    首先放弃组合数个数为r的条件,候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件,扩大其规模,并使其满足上述条件(1),候选组合改为1,2。继续这一过程,得到候选组合1,2,3。该候选解满足包括问题规模在内的全部条件,因而是一个解。在该解的基础上,选下一个候选解,因a[2]上的3调整为4,以及以后调整为5都满足问题的全部要求,得到解1,2,4和1,2,5。由于对5不能再作调整,就要从a[2]回溯到a[1],这时,a[1]=2,可以调整为3,并向前试探,得到解1,3,4。重复上述向前试探和向后回溯,直至要从a[0]再回溯时,说明已经找完问题的全部解。按上述思想写成程序如下:
    【程序】
    # define MAXN 100
    int a[MAXN];
    void comb(int m,int r)
    { int i,j;
    i=0;
    a[i]=1;
    do {
    if (a[i]-i<=m-r+1
    { if (i==r-1)
    { for (j=0;j   printf(“%4d”,a[j]);
    printf(“\n”);
    }
    a[i]++;
    continue;
    }
    else
    { if (i==0)
    return;
    a[--i]++;
    }
    } while (1)
    }

    main()
    { comb(5,3);
    }
    【问题】 填字游戏
    问题描述:在3×3个方格的方阵中要填入数字1到N(N≥10)内的某9个数字,每个方格填一个整数,似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。

    可用试探发找到问题的解,即从第一个方格开始,为当前方格寻找一个合理的整数填入,并在当前位置正确填入后,为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书,就要回退到前一方格,调整前一方格的填入数。当第九个方格也填入合理的整数后,就找到了一个解,将该解输出,并调整第九个的填入的整数,寻找下一个解。

    为找到一个满足要求的9个数的填法,从还未填一个数开始,按某种顺序(如从小到大的顺序)每次在当前位置填入一个整数,然后检查当前填入的整数是否能满足要求。在满足要求的情况下,继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求,就改变填入的整数。如对当前方格试尽所有可能的整数,都不能满足要求,就得回退到前一方格,并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查,直到找到一个满足问题要求的解,将解输出。
    回溯法找一个解的算法:
    { int m=0,ok=1;
    int n=8;
    do{
    if (ok) 扩展;
    else 调整;
    ok=检查前m个整数填放的合理性;
    } while ((!ok||m!=n)&&(m!=0))
    if (m!=0) 输出解;
    else 输出无解报告;
    }
    如果程序要找全部解,则在将找到的解输出后,应继续调整最后位置上填放的整数,试图去找下一个解。相应的算法如下:
    回溯法找全部解的算法:
    { int m=0,ok=1;
    int n=8;
    do{
    if (ok) 
    { if (m==n) 
    { 输出解;
    调整;
    }
    else 扩展;
    }
    else 调整;
    ok=检查前m个整数填放的合理性;
    } while (m!=0);
    }
    为了确保程序能够终止,调整时必须保证曾被放弃过的填数序列不会再次实验,即要求按某种有许模型生成填数序列。给解的候选者设定一个被检验的顺序,按这个顺序逐一形成候选者并检验。从小到大或从大到小,都是可以采用的方法。如扩展时,先在新位置填入整数1,调整时,找当前候选解中下一个还未被使用过的整数。将上述扩展、调整、检验都编写成程序,细节见以下找全部解的程序。
    【程序】
    # include 
    # define N 12
    void write(int a[ ])
    { int i,j;
    for (i=0;i<3;i++)
    { for (j=0;j<3;j++)
    printf(“%3d”,a[3*i+j]);
    printf(“\n”);
    }
    scanf(“%*c”);
    }

    int b[N+1];
    int a[10];
    int isprime(int m)
    { int i;
    int primes[ ]={2,3,5,7,11,17,19,23,29,-1};
    if (m==1||m%2=0) return 0;
    for (i=0;primes[i]>0;i++)
    if (m==primes[i]) return 1;
    for (i=3;i*i<=m;)
    { if (m%i==0) return 0;
    i+=2;
    }
    return 1;
    }

    int checkmatrix[ ][3]={ {-1},{0,-1},{1,-1},{0,-1},{1,3,-1},
    {2,4,-1},{3,-1},{4,6,-1},{5,7,-1}};
    int selectnum(int start)
    { int j;
    for (j=start;j<=N;j++)
    if (b[j]) return j
    return 0;
    }

    int check(int pos)
    { int i,j;
    if (pos<0) return 0;
    for (i=0;(j=checkmatrix[pos][i])>=0;i++)
    if (!isprime(a[pos]+a[j])
    return 0;
    return 1;
    }

    int extend(int pos)
    { a[++pos]=selectnum(1);
    b[a][pos]]=0;
    return pos;
    }

    int change(int pos)
    { int j;
    while (pos>=0&&(j=selectnum(a[pos]+1))==0)
    b[a[pos--]]=1;
    if (pos<0) return –1
    b[a[pos]]=1;
    a[pos]=j;
    b[j]=0;
    return pos;
    }

    void find()
    { int ok=0,pos=0;
    a[pos]=1;
    b[a[pos]]=0;
    do {
    if (ok)
    if (pos==8)
    { write(a);
    pos=change(pos);
    }
    else pos=extend(pos);
    else pos=change(pos);
    ok=check(pos);
    } while (pos>=0)
    }

    void main()
    { int i;
    for (i=1;i<=N;i++)
    b[i]=1;
    find();
    }
    【问题】 n皇后问题
    问题描述:求出在一个n×n的棋盘上,放置n个不能互相捕捉的国际象棋“皇后”的所有布局。
    这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线4个方向相互捕捉。如图所示,一个皇后放在棋盘的第4行第3列位置上,则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉。

    1 2 3 4 5 6 7 8
    × × 
    × × × 
    × × × 
    × × Q × × × × ×
    × × × 
    × × × 
    × × 
    × × 
    从图中可以得到以下启示:一个合适的解应是在每列、每行上只有一个皇后,且一条斜线上也只有一个皇后。
    求解过程从空配置开始。在第1列至第m列为合理配置的基础上,再配置第m+1列,直至第n列配置也是合理时,就找到了一个解。接着改变第n列配置,希望获得下一个解。另外,在任一列上,可能有n种配置。开始时配置在第1行,以后改变时,顺次选择第2行、第3行、…、直到第n行。当第n行配置也找不到一个合理的配置时,就要回溯,去改变前一列的配置。得到求解皇后问题的算法如下:
    { 输入棋盘大小值n;
    m=0;
    good=1;
    do {
    if (good)
    if (m==n)
    { 输出解;
    改变之,形成下一个候选解;
    }
    else 扩展当前候选接至下一列;
    else 改变之,形成下一个候选解;
    good=检查当前候选解的合理性;
    } while (m!=0);
    }
    在编写程序之前,先确定边式棋盘的数据结构。比较直观的方法是采用一个二维数组,但仔细观察就会发现,这种表示方法给调整候选解及检查其合理性带来困难。更好的方法乃是尽可能直接表示那些常用的信息。对于本题来说,“常用信息”并不是皇后的具体位置,而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因在某一列上恰好放一个皇后,引入一个一维数组(col[ ]),值col[i]表示在棋盘第i列、col[i]行有一个皇后。例如:col[3]=4,就表示在棋盘的第3列、第4行上有一个皇后。另外,为了使程序在找完了全部解后回溯到最初位置,设定col[0]的初值为0当回溯到第0列时,说明程序已求得全部解,结束程序运行。

    为使程序在检查皇后配置的合理性方面简易方便,引入以下三个工作数组:
    (1) 数组a[ ],a[k]表示第k行上还没有皇后;
    (2) 数组b[ ],b[k]表示第k列右高左低斜线上没有皇后;
    (3) 数组 c[ ],c[k]表示第k列左高右低斜线上没有皇后;

    棋盘中同一右高左低斜线上的方格,他们的行号与列号之和相同;同一左高右低斜线上的方格,他们的行号与列号之差均相同。

    初始时,所有行和斜线上均没有皇后,从第1列的第1行配置第一个皇后开始,在第m列col[m]行放置了一个合理的皇后后,准备考察第m+1列时,在数组a[ ]、b[ ]和c[ ]中为第m列,col[m]行的位置设定有皇后标志;当从第m列回溯到第m-1列,并准备调整第m-1列的皇后配置时,清除在数组a[ ]、b[ ]和c[ ]中设置的关于第m-1列,col[m-1]行有皇后的标志。一个皇后在m列,col[m]行方格内配置是合理的,由数组a[ ]、b[ ]和c[ ]对应位置的值都为1来确定。细节见以下程序:
    【程序】
    # include 
    # include 
    # define MAXN 20
    int n,m,good;
    int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];

    void main()
    { int j;
    char awn;
    printf(“Enter n: “); scanf(“%d”,&n);
    for (j=0;j<=n;j++) a[j]=1;
    for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
    m=1; col[1]=1; good=1; col[0]=0;
    do {
    if (good)
    if (m==n)
    { printf(“列\t行”);
    for (j=1;j<=n;j++)
    printf(“%3d\t%d\n”,j,col[j]);
    printf(“Enter a character (Q/q for exit)!\n”);
    scanf(“%c”,&awn);
    if (awn==’Q’||awn==’q’) exit(0);
    while (col[m]==n)
    { m--;
    a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
    }
    col[m]++;
    }
    else
    { a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
    col[++m]=1;
    }
    else
    { while (col[m]==n)
    { m--;
    a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
    }
    col[m]++;
    }
    good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
    } while (m!=0);
    }
    试探法找解算法也常常被编写成递归函数,下面两程序中的函数queen_all()和函数queen_one()能分别用来解皇后问题的全部解和一个解。
    【程序】
    # include 
    # include 
    # define MAXN 20
    int n;
    int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
    void main()
    { int j;
    printf(“Enter n: “); scanf(“%d”,&n);
    for (j=0;j<=n;j++) a[j]=1;
    for (j=0;j<=2*n;j++) cb[j]=c[j]=1;
    queen_all(1,n);
    }

    void queen_all(int k,int n)
    { int i,j;
    char awn;
    for (i=1;i<=n;i++)
    if (a[i]&&b[k+i]&&c[n+k-i])
    { col[k]=i;
    a[i]=b[k+i]=c[n+k-i]=0;
    if (k==n)
    { printf(“列\t行”);
    for (j=1;j<=n;j++)
    printf(“%3d\t%d\n”,j,col[j]);
    printf(“Enter a character (Q/q for exit)!\n”);
    scanf(“%c”,&awn);
    if (awn==’Q’||awn==’q’) exit(0);
    }
    queen_all(k+1,n);
    a[i]=b[k+i]=c[n+k-i];
    }
    }
    采用递归方法找一个解与找全部解稍有不同,在找一个解的算法中,递归算法要对当前候选解最终是否能成为解要有回答。当它成为最终解时,递归函数就不再递归试探,立即返回;若不能成为解,就得继续试探。设函数queen_one()返回1表示找到解,返回0表示当前候选解不能成为解。细节见以下函数。
    【程序】
    # define MAXN 20
    int n;
    int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
    int queen_one(int k,int n)
    { int i,found;
    i=found=0;
    While (!found&&i   { i++;
    if (a[i]&&b[k+i]&&c[n+k-i])
    { col[k]=i;
    a[i]=b[k+i]=c[n+k-i]=0;
    if (k==n) return 1;
    else
    found=queen_one(k+1,n);
    a[i]=b[k+i]=c[n+k-i]=1;
    }
    }
    return found;
    }

     

    六、贪婪法

    贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。

    例如平时购物找钱时,为使找回的零钱的硬币数最少,不考虑找零钱的所有各种发表方案,而是从最大面值的币种开始,按递减的顺序考虑各币种,先尽量用大面值 的币种,当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优,是因为银行对其发行的硬币种类和硬币面值 的巧妙安排。如只有面值分别为1、5和11单位的硬币,而希望找回总额为15单位的硬币。按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬 币,共找回5个硬币。但最优的解应是3个5单位面值的硬币。

    【问题】 装箱问题

    问题描述:装箱问题可简述如下:设有编号为0、1、…、n-1的n种物品,体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱 子里。约定这n种物品的体积均不超过V,即对于0≤i<n,有0<vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱 子数要少。
    若考察将n种物品的集合分划成n个或小于n个物品的所有子集,最优解就可以找到。但所有可能划分的总数太大。对适当大的n,找出所有可能的划分要花费的时 间是无法承受的。为此,对装箱问题采用非常简单的近似算法,即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中,该算法虽不能保证找到最优解,但还 是能找到非常好的解。不失一般性,设n件物品的体积是按从大到小排好序的,即有v0≥v1≥…≥vn-1。如不满足上述要求,只要先对这n件物品按它们的 体积从大到小排序,然后按排序结果对物品重新编号即可。装箱算法简单描述如下:
    { 输入箱子的容积;
    输入物品种数n;
    按体积从大到小顺序,输入各物品的体积;
    预置已用箱子链为空;
    预置已用箱子计数器box_count为0;
    for (i=0;i   { 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j;
    if (已用箱子都不能再放物品i)
    { 另用一个箱子,并将物品i放入该箱子;
    box_count++;
    }
    else
    将物品i放入箱子j;
    }
    }
    上述算法能求出需要的箱子数box_count,并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解,设有6种物品,它们的体积分别为: 60、45、35、20、20和20单位体积,箱子的容积为100个单位体积。按上述算法计算,需三只箱子,各箱子所装物品分别为:第一只箱子装物品1、 3;第二只箱子装物品2、4、5;第三只箱子装物品6。而最优解为两只箱子,分别装物品1、4、5和2、3、6。

    若每只箱子所装物品用链表来表示,链表首结点指针存于一个结构中,结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按以上算法编写的程序。
    【程序】
    # include 
    # include 
    typedef struct ele
    { int vno;
    struct ele *link;
    } ELE;
    typedef struct hnode
    { int remainder;
    ELE *head;
    Struct hnode *next;
    } HNODE;

    void main()
    { int n, i, box_count, box_volume, *a;
    HNODE *box_h, *box_t, *j;
    ELE *p, *q;
    Printf(“输入箱子容积\n”);
    Scanf(“%d”,&box_volume);
    Printf(“输入物品种数\n”);
    Scanf(“%d”,&n);
    A=(int *)malloc(sizeof(int)*n);
    Printf(“请按体积从大到小顺序输入各物品的体积:”);
    For (i=0;i   Box_h=box_t=NULL;
    Box_count=0;
    For (i=0;i   { p=(ELE *)malloc(sizeof(ELE));
    p->vno=i;
    for (j=box_h;j!=NULL;j=j->next)
    if (j->remainder>=a[i]) break;
    if (j==NULL)
    { j=(HNODE *)malloc(sizeof(HNODE));
    j->remainder=box_volume-a[i];
    j->head=NULL;
    if (box_h==NULL) box_h=box_t=j;
    else box_t=boix_t->next=j;
    j->next=NULL;
    box_count++;
    }
    else j->remainder-=a[i];
    for (q=j->next;q!=NULL&&q->link!=NULL;q=q->link);
    if (q==NULL)
    { p->link=j->head;
    j->head=p;
    }
    else
    { p->link=NULL;
    q->link=p;
    }
    }
    printf(“共使用了%d只箱子”,box_count);
    printf(“各箱子装物品情况如下:”);
    for (j=box_h,i=1;j!=NULL;j=j->next,i++)
    { printf(“第%2d只箱子,还剩余容积%4d,所装物品有;\n”,I,j->remainder);
    for (p=j->head;p!=NULL;p=p->link)
    printf(“%4d”,p->vno+1);
    printf(“\n”);
    }
    }
    【问题】 马的遍历
    问题描述:在8×8方格的棋盘上,从任意指定的方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。

    马在某个方格,可以在一步内到达的不同位置最多有8个,如图所示。如用二维数组board[ ][ ]表示棋盘,其元素记录马经过该位置时的步骤号。另对马的8种可能走法(称为着法)设定一个顺序,如当前位置在棋盘的(i,j)方格,下一个可能的位置依 次为(i+2,j+1)、(i+1,j+2)、(i-1,j+2)、(i-2,j+1)、(i-2,j-1)、(i-1,j-2)、(i+1,j-2)、 (i+2,j-1),实际可以走的位置尽限于还未走过的和不越出边界的那些位置。为便于程序的同意处理,可以引入两个数组,分别存储各种可能走法对当前位 置的纵横增量。
    4 3 
    5 2
    马 
    6 1
    7 0 

    对于本题,一般可以采用回溯法,这里采用Warnsdoff策略求解,这也是一种贪婪法,其选择下一出口的贪婪标准是在那些允许走的位置中,选择出口最少 的那个位置。如马的当前位置(i,j)只有三个出口,他们是位置(i+2,j+1)、(i-2,j+1)和(i-1,j-2),如分别走到这些位置,这三 个位置又分别会有不同的出口,假定这三个位置的出口个数分别为4、2、3,则程序就选择让马走向(i-2,j+1)位置。

    由于程序采用的是一种贪婪法,整个找解过程是一直向前,没有回溯,所以能非常快地找到解。但是,对于某些开始位置,实际上有解,而该算法不能找到解。对于 找不到解的情况,程序只要改变8种可能出口的选择顺序,就能找到解。改变出口选择顺序,就是改变有相同出口时的选择标准。以下程序考虑到这种情况,引入变 量start,用于控制8种可能着法的选择顺序。开始时为0,当不能找到解时,就让start增1,重新找解。细节以下程序。
    【程序】
    # include 
    int delta_i[ ]={2,1,-1,-2,-2,-1,1,2};
    int delta_j[ ]={1,2,2,1,-1,-2,-2,-1};
    int board[8][8];
    int exitn(int i,int j,int s,int a[ ])
    { int i1,j1,k,count;
    for (count=k=0;k<8;k++)
    { i1=i+delta_i[(s+k)%8];
    j1=i+delta_j[(s+k)%8];
    if (i1>=0&&i1<8&&j1>=0&&j1<8&&board[I1][j1]==0)
    a[count++]=(s+k)%8;
    }
    return count;
    }

    int next(int i,int j,int s)
    { int m,k,mm,min,a[8],b[8],temp;
    m=exitn(i,j,s,a);
    if (m==0) return –1;
    for (min=9,k=0;k   { temp=exitn(I+delta_i[a[k]],j+delta_j[a[k]],s,b);
    if (temp   { min=temp;
    kk=a[k];
    }
    }
    return kk;
    }

    void main()
    { int sx,sy,i,j,step,no,start;
    for (sx=0;sx<8;sx++)
    for (sy=0;sy<8;sy++)
    { start=0;
    do {
    for (i=0;i<8;i++)
    for (j=0;j<8;j++)
    board[i][j]=0;
    board[sx][sy]=1;
    I=sx; j=sy;
    For (step=2;step<64;step++)
    { if ((no=next(i,j,start))==-1) break;
    I+=delta_i[no];
    j+=delta_j[no];
    board[i][j]=step;
    }
    if (step>64) break;
    start++;
    } while(step<=64)
    for (i=0;i<8;i++)
    { for (j=0;j<8;j++)
    printf(“%4d”,board[i][j]);
    printf(“\n\n”);
    }
    scanf(“%*c”);
    }
    }

    七、分治法

    1、分治法的基本思想

    任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的 排序问题,当n=1时,不需任何计算;n=2时,只要作一次比较即可排好序;n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要 想直接解决一个规模较大的问题,有时是相当困难的。

    分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

    如果原问题可分割成k个子问题

    2、分治法的适用条件

    分治法所能解决的问题一般具有以下几个特征:
    (1)该问题的规模缩小到一定的程度就可以容易地解决;
    (2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
    (3)利用该问题分解出的子问题的解可以合并为该问题的解;
    (4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。 

    上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提,它也是大多数问 题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具 备第三条特征,则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子 问题,此时虽然可用分治法,但一般用动态规划法较好。

    3、分治法的基本步骤

    分治法在每一层递归上都有三个步骤:
    (1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
    (2)解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
    (3)合并:将各个子问题的解合并为原问题的解。
    它的一般的算法设计模式如下:
    Divide_and_Conquer(P)
    if |P|≤n0 
    then return(ADHOC(P))
    将P分解为较小的子问题P1、P2、…、Pk
    for i←1 to k 
    do 
    yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
    T ← MERGE(y1,y2,…,yk) △ 合并子问题
    Return(T)
    其中 |P| 表示问题P的规模;n0为一阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。ADHOC(P)是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时,直接用算法ADHOC(P)求解。
    算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法,用于将P的子问题P1、P2、…、Pk的相应的解y1、y2、…、yk合并为P的解。
    根据分治法的分割原则,原问题应该分为多少个子问题才较适宜?各个子问题的规模应该怎样才为适当?这些问题很难予以肯定的回答。但人们从大量实践中发 现,在用分治法设计算法时,最好使子问题的规模大致相同。换句话说,将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。 这种使子问题规模大致相等的做法是出自一种平衡子问题的思想,它几乎总是比子问题规模不等的做法要好。

    分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显,有些问题合并方法比较复杂,或者是有多种合并方案;或者是合并方案不明显。究竟应该怎样合并,没有统一的模式,需要具体问题具体分析。
    【问题】 大整数乘法
    问题描述:
    通常,在分析一个算法的计算复杂性时,都将加法和乘法运算当作是基本运算来处理,即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。

    这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而,在某些情况下,我们要处理很大的整数,它无法在计算机硬件能直接表示的 范围内进行处理。若用浮点数来表示它,则只能近似地表示它的大小,计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所 有位数上的数字,就必须用软件的方法来实现大整数的算术运算。

    请设计一个有效的算法,可以进行两个n位大整数的乘法运算。

    设X和Y都是n位的二进制整数,现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法,但是这样做计算步骤太多,显得效 率较低。如果将每2个1位数的乘法或加法看作一步运算,那么这种方法要作O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘 积算法。

    图6-3 大整数X和Y的分段
    我们将n位的二进制整数X和Y各分为2段,每段的长为n/2位(为简单起见,假设n是2的幂),如图6-3所示。
    由此,X=A2n/2+B,Y=C2n/2+D。这样,X和Y的乘积为:
    XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)
    如果按式(1)计算XY,则我们必须进行4次n/2位整数的乘法(AC,AD,BC和BD),以及3次不超过n位的整数加法(分别对应于式(1)中的 加号),此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运 算总数,则由式(1),我们有:
    (2)由此可得T(n)=O(n2)。因此,用(1)式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性,必须减少乘法次数。为此我们把XY写成另一种形式:
    XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)
    虽然,式(3)看起来比式(1)复杂些,但它仅需做3次n/2位整数的乘法(AC,BD和(A-B)(D-C)),6次加、减法和2次移位。由此可得:
    (4)
    用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式(3),并考虑到X和Y的符号对结果的影响,我们给出大整数相乘的完整算法MULT如下:
    function MULT(X,Y,n); {X和Y为2个小于2n的整数,返回结果为X和Y的乘积XY}
    begin
    S=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}
    X=ABS(X);
    Y=ABS(Y); {X和Y分别取绝对值}
    if n=1 then
    if (X=1)and(Y=1) then return(S)
    else return(0)
    else begin
    A=X的左边n/2位;
    B=X的右边n/2位;
    C=Y的左边n/2位;
    D=Y的右边n/2位;
    ml=MULT(A,C,n/2);
    m2=MULT(A-B,D-C,n/2);
    m3=MULT(B,D,n/2); 
    S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
    return(S); 
    end;
    end;
    上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。
    【问题】 最接近点对问题
    问题描述:
    在应用中,常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中,常需要了解其邻域中其他几何对象的信息。例如,在空中 交通控制问题中,若将飞机作为空间中移动的一个点来看待,则具有最大碰撞危险的2架飞机,就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基 本问题之一。下面我们着重考虑平面上的最接近点对问题。

    最接近点对问题的提法是:给定平面上n个点,找其中的一对点,使得在n个点的所有点对中,该点对的距离最小。

    严格地说,最接近点对可能多于1对。为了简单起见,这里只限于找其中的一对。

    这个问题很容易理解,似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出,找出达到最小距离的两个点即可。然而,这样做效率太低,需要O(n2)的计算时间。我们能否找到问题的一个O (nlogn)算法。

    这个问题显然满足分治法的第一个和第二个适用条件,我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2,每个子集中约有n/2个点,然后在 每个子集中递归地求其最接近的点对。在这里,一个关键的问题是如何实现分治法中的合并步骤,即由S1和S2的最接近点对,如何求得原集合S中的最接近点 对,因为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中,则问题很容易解决。但是,如果这2个点 分别在S1和S2中,则对于S1中任一点p,S2中最多只有n/2个点与它构成最接近点对的候选者,仍需做n2/4次计算和比较才能确定S的最接近点对。 因此,依此思路,合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足:

    T(n)=2T(n/2)+O(n2)

    它的解为T(n)=O(n2),即与合并步骤的耗时同阶,显示不出比用穷举的方法好。从解递归方程的套用公式法,我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。

    为了使问题易于理解和分析,我们先来考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x1、x2、…、xn。最接近点对即为这n个实数中相差 最小的2个实数。我们显然可以先将x1、x2、…、xn排好序,然后,用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上,因此如在排 序算法中所证明的,耗时为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此,对这种一维的简单情形,我们还是尝试用分治法来求解,并希望能 推广到二维的情形。

    假设我们用x轴上某个点m将S划分为2个子集S1和S2,使得S1={x∈S | x≤m};S2={x∈S | x>m}。这样一来,对于所有p∈S1和q∈S2有p  递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2},并设δ=min {|p1-p2|,|q1-q2|},S中的最接近点对或者是{p1,p2},或者是{q1,q2},或者是某个{p3,q3},其中p3∈S1且 q3∈S2。如图1所示。

    图1 一维情形的分治法
    我们注意到,如果S的最接近点对是{p3,q3},即 | p3-q3 | < δ,则p3和q3两者与m的距离不超过δ,即 | p3-m | < δ,| q3-m | < δ,也就是说,p3∈(m-δ,m),q3∈(m,m+δ)。由于在S1中,每个长度为δ的半闭区间至多包含一个点(否则必有两点距离小于δ),并且m是 S1和S2的分割点,因此(m-δ,m)中至多包含S中的一个点。同理,(m,m+δ)中也至多包含S中的一个点。由图1可以看出,如果(m-δ,m)中 有S中的点,则此点就是S1中最大点。同理,如果(m,m+δ)中有S中的点,则此点就是S2中最小点。因此,我们用线性时间就能找到区间(m-δ,m) 和(m,m+δ)中所有点,即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。也就是说,按这种分治策略,合并步可在O(n) 时间内完成。这样是否就可以得到一个有效的算法了呢?

    还有一个问题需要认真考虑,即分割点m的选取,及S1和S2的划分。选取分割点m的一个基本要求是由此导出集合S的一个线性分割,即S=S1∪S2 ,S1∩S2=Φ,且S1 {x | x≤m};S2 {x | x>m}。容易看出,如果选取m=[max(S)+min(S)]/2,可以满足线性分割的要求。选取分割点后,再用O(n)时间即可将S划分成 S1={x∈S | x≤m}和S2={x∈S | x>m}。然而,这样选取分割点m,有可能造成划分出的子集S1和S2的不平衡。例如在最坏情况下,|S1|=1,|S2|=n-1,由此产生的分 治法在最坏情况下所需的计算时间T(n)应满足递归方程:
    T(n)=T(n-1)+O(n)

    它的解是T(n)=O(n2)。这种效率降低的现象可以通过分治法中“平衡子问题”的方法加以解决。也就是说,我们可以通过适当选择分割点m,使S1 和S2中有大致相等个数的点。自然地,我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O (n)时间内确定一个平衡的分割点m。

    至此,我们可以设计出一个求一维点集S中最接近点对的距离的算法pair如下。
    Float pair(S);
    { if | S | =2 δ= | x[2]-x[1] | /*x[1..n]存放的是S中n个点的坐标*/
    else 
    { if ( | S | =1) δ=∞
    else 
    { m=S中各点的坐标值的中位数;
    构造S1和S2,使S1={x∈S | x≤m},S2={x∈S | x>m};
    δ1=pair(S1);
    δ2=pair(S2);
    p=max(S1);
    q=min(S2);
    δ=min(δ1,δ2,q-p);
    }
    return(δ);
    }
    由以上的分析可知,该算法的分割步骤和合并步骤总共耗时O(n)。因此,算法耗费的计算时间T(n)满足递归方程:

    解此递归方程可得T(n)=O(nlogn)。

    【问题】循环赛日程表 
    问题描述:设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:
    (1)每个选手必须与其他n-1个选手各赛一次; 
    (2)每个选手一天只能参赛一次; 
    (3)循环赛在n-1天内结束。 
    请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行,第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n,1≤j≤n-1。

    按分治策略,我们可以将所有的选手分为两半,则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分,直到只剩下两个选手时,比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。

    1 2 3 4 5 6 7
    1 2 3 4 5 6 7 8
    2 1 4 3 6 7 8 5
    3 4 1 2 7 8 5 6
    1 2 3 4 3 2 1 8 5 6 7
    1 2 3 4 5 6 7 8 1 4 3 2
    1 2 1 4 3 6 5 8 7 2 1 4 3
    1 2 3 4 1 2 7 8 5 6 3 2 1 4
    2 1 4 3 2 1 8 7 6 5 4 3 2 1
    (1) (2) (3)
    图1 2个、4个和8个选手的比赛日程表
    图1所列出的正方形表(3)是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此,将左 上角小块中的所有数字按其相对位置抄到右下角,又将左下角小块中的所有数字按其相对位置抄到右上角,这样我们就分别安排好了选手1至选手4和选手5至选手 8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。

    八、动态规划法

    经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题。简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加。

    为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。以下先用实例说明动态规划方法的使用。

    【问题】 求两字符序列的最长公共字符子序列
    问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X= “x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列,使得对所有的j=0,1,…,k- 1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。

    给定两个序列A和B,称序列Z是A和B的公共子序列,是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。

    如采用列举A的所有子序列,并一一检查其是否又是B的子序列,并随时记录所发现的子序列,最终求出最长公共子序列。这种方法因耗时太多而不可取。

    考虑最长公共子序列问题如何分解成子问题,设A=“a0,a1,…,am-1”,B=“b0,b1,…,bm-1”,并Z=“z0,z1,…,zk-1”为它们的最长公共子序列。不难证明有以下性质:
    (1) 如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一个最长公共子序列;
    (2) 如果am-1!=bn-1,则若zk-1!=am-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列;
    (3) 如果am-1!=bn-1,则若zk-1!=bn-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列。
    这样,在找A和B的公共子序列时,如有am-1=bn-1,则进一步解决一个子问题,找“a0,a1,…,am-2”和“b0,b1,…,bm-2” 的一个最长公共子序列;如果am-1!=bn-1,则要解决两个子问题,找出“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共 子序列和找出“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列,再取两者中较长者作为A和B的最长公共子序列。
    定义c[i][j]为序列“a0,a1,…,ai-2”和“b0,b1,…,bj-1”的最长公共子序列的长度,计算c[i][j]可递归地表述如下:
    (1)c[i][j]=0 如果i=0或j=0;
    (2)c[i][j]= c[i-1][j-1]+1 如果I,j>0,且a[i-1]=b[j-1];
    (3)c[i][j]=max(c[i][j-1],c[i-1][j]) 如果I,j>0,且a[i-1]!=b[j-1]。
    按此算式可写出计算两个序列的最长公共子序列的长度函数。由于c[i][j]的产生仅依赖于c[i-1][j-1]、c[i-1][j]和c[i][j-1],故可以从c[m][n]开始,跟踪c[i][j]的产生过程,逆向构造出最长公共子序列。细节见程序。
    # include 
    # include 
    # define N 100
    char a[N],b[N],str[N];

    int lcs_len(char *a, char *b, int c[ ][ N])
    { int m=strlen(a), n=strlen(b), i,j;
    for (i=0;i<=m;i++) c[i][0]=0;
    for (i=0;i<=n;i++) c[0][i]=0;
    for (i=1;i<=m;i++) 
    for (j=1;j<=m;j++)
    if (a[i-1]==b[j-1])
    c[i][j]=c[i-1][j-1]+1;
    else if (c[i-1][j]>=c[i][j-1])
    c[i][j]=c[i-1][j];
    else
    c[i][j]=c[i][j-1];
    return c[m][n];
    }

    char *buile_lcs(char s[ ],char *a, char *b)
    { int k, i=strlen(a), j=strlen(b);
    k=lcs_len(a,b,c);
    s[k]=’\0’;
    while (k>0)
    if (c[i][j]==c[i-1][j]) i--;
    else if (c[i][j]==c[i][j-1]) j--;
    else { s[--k]=a[i-1];
    i--; j--;
    }
    return s;
    }

    void main()
    { printf (“Enter two string(<%d)!\n”,N); 
             scanf(“%s%s”,a,b); 
             printf(“LCS=%s\n”,build_lcs(str,a,b)); 
           } 

    1、动态规划的适用条件 
    任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。 
    (1)最优化原理(最优子结构性质) 
    最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。 

    图2 
    例如图2中,若路线I和J是A到C的最优路径,则根据最优化原理,路线J必是从B到C的最优路线。这可用反证法证明:假设有另一路径J’是B到C的最优路径,则A到C的路线取I和J’比I和J更优,矛盾。从而证明J’必是B到C的最优路径。 
    最优化原理是动态规划的基础,任何问题,如果失去了最优化原理的支持,就不可能用动态规划方法计算。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。 
    (2)无后向性 
    将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。 
    (3)子问题的重叠性 
    动态规划算法的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种 状态,所以它的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受,所以我们舍空间而取时 间。 
    所以,能够用动态规划解决的问题还有一个显著特征:子问题的重叠性。这个性质并不是动态规划适用的必要条件,但是如果该性质无法满足,动态规划算法同其他算法相比就不具备优势。 
    2、动态规划的基本思想 
    前文主要介绍了动态规划的一些理论依据,我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划,这种标准动态规划是在研究多阶段 决策问题时推导出来的,具有严格的数学形式,适合用于理论上的分析。在实际应用中,许多问题的阶段划分并不明显,这时如果刻意地划分阶段法反而麻烦。一般 来说,只要该问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决。 
    动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。 
    由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解。其中贪心法的当前选择 可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下,一步一步地作出贪心选择;而分治法中的各个子问题是独立的(即 不包含公共的子子问题),因此一旦递归地求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解。但不足的是,如果当前选择可能要依赖子问题的解 时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。 
    解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值 的解。若存在若干个取最优值的解的话,它只取其中的一个。在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是, 动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存 起来,避免每次碰到时都要重复计算。 
    因此,动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解。 
    3、动态规划算法的基本步骤 
    设计一个标准的动态规划算法,通常可按以下几个步骤进行: 
    (1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性),否则问题就无法用动态规划求解。 
    (2)选择状态:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。 
    (3)确定决策并写出状态转移方程:之所以把这两步放在一起,是因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的 状态。所以,如果我们确定了决策,状态转移方程也就写出来了。但事实上,我们常常是反过来做,根据相邻两段的各状态之间的关系来确定决策。 
    (4)写出规划方程(包括边界条件):动态规划的基本方程是规划方程的通用形式化表达式。 
    一般说来,只要阶段、状态、决策和状态转移确定了,这一步还是比较简单的。动态规划的主要难点在于理论上的设计,一旦设计完成,实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值,但是一般将其改为递推计算,实现的大体上的框架如下: 
    标准动态规划的基本框架 
    1. 对fn+1(xn+1)初始化;   {边界条件} 
    for k:=n downto 1 do 
    for 每一个xk∈Xk do 
    for 每一个uk∈Uk(xk) do 
    begin 
    5.         fk(xk):=一个极值;           {∞或-∞} 
    6.         xk+1:=Tk(xk,uk);             {状态转移方程} 
    7.         t:=φ(fk+1(xk+1),vk(xk,uk));     {基本方程(9)式} 
    if t比fk(xk)更优 then fk(xk):=t; {计算fk(xk)的最优值} 
    end; 
    9. t:=一个极值;                     {∞或-∞} 
    for 每一个x1∈X1 do 
    11.   if f1(x1)比t更优 then t:=f1(x1);     {按照10式求出最优指标} 
    12. 输出t; 
    但是,实际应用当中经常不显式地按照上面步骤设计动态规划,而是按以下几个步骤进行: 
    (1)分析最优解的性质,并刻划其结构特征。 
    (2)递归地定义最优值。 
    (3)以自底向上的方式或自顶向下的记忆化方法(备忘录法)计算出最优值。 
    (4)根据计算最优值时得到的信息,构造一个最优解。 
    步骤(1)~(3)是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤(4)可以省略,若需要求出问题的一个最优解,则必须执行步骤(4)。此 时,在步骤(3)中计算最优值时,通常需记录更多的信息,以便在步骤(4)中,根据所记录的信息,快速地构造出一个最优解。 

    【问题】   凸多边形的最优三角剖分问题 
    问题描述:多边形是平面上一条分段线性的闭曲线。也就是说,多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接 两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点,则称该多边形为简单多边形。一个简单多边形将平面分为3个部分:被包围 在多边形内的所有点构成了多边形的内部;多边形本身构成多边形的边界;而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时, 称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。 
    通常,用多边形顶点的逆时针序列来表示一个凸多边形,即P=表示具有n条边v0v1,v1v2,…,vn-1vn的一个凸多边形,其中,约定v0=vn 。 
    若vi与vj是多边形上不相邻的两个顶点,则线段vivj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形和。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。图1是一个凸多边形的两个不同的三角剖分。 

    (a)   (b) 
    图1 一个凸多边形的2个不同的三角剖分 
    在凸多边形P的一个三角剖分T中,各弦互不相交且弦数已达到最大,即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角刮分中,恰好有n-3条弦和n-2个三角形。 
    凸多边形最优三角剖分的问题是:给定一个凸多边形P=以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分,使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。 
    可以定义三角形上各种各样的权函数ω。例如:定义ω(△vivjvk)=| vivj |+| vivk |+| vkvj |,其中,| vivj |是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。 
    (1)最优子结构性质 
    凸多边形的最优三角剖分问题有最优子结构性质。事实上,若凸(n+1)边形P=的一个最优三角剖分T包含三角形v0vkvn,1≤k≤n-1,则T的权为 3个部分权的和,即三角形v0vkvn的权,子多边形的权和的权之和。可以断言由T所确定的这两个子多边形的三角剖分也是最优的,因为若有或的更小权的三 角剖分,将会导致T不是最优三角剖分的矛盾。 
    (2)最优三角剖分对应的权的递归结构 
    首先,定义t[i,j](1≤i的最优三角剖分所对应的权值,即最优值。为方便起见,设退化的多边形具有权值0。据此定义,要计算的凸(n+1)边多边形P对应的权的最优值为t[1,n]。 
    t[i,j]的值可以利用最优子结构性质递归地计算。由于退化的2顶点多边形的权值为0,所以t[i,i]=0,i=1,2,…,n 。当j一i≥1时,子多边形至少有3个顶点。由最优于结构性质,t[i,j]的值应为t[i,k]的值加上t[k+1,j]的值,再加上△vi- 1vkvj的权值,并在i≤k≤j-1的范围内取最小。由此,t[i,j]可递归地定义为: 

    (3)计算最优值 
    下面描述的计算凸(n+1)边形P=的三角剖分最优权值的动态规划算法MINIMUM_WEIGHT,输入是凸多边形P=的权函数ω,输出是最优值t [i,j]和使得t[i,k]+t[k+1,j]+ω(△vi-1vkvj)达到最优的位置(k=)s[i,j],1≤i≤j≤n 。 
    Procedure MINIMUM_WEIGHT(P,w); 
    Begin 
    n=length[p]-1; 
    for i=1 to n do t[i,i]:=0; 
    for ll=2 to n do 
    for i=1 to n-ll+1 do 
    begin 
    j=i+ll-1; 
    t[i,j]=∞; 
    for k=i to j-1 do 
    begin 
    q=t[i,k]+t[k+1,j]+ω(△vi-1vkvj); 
    if qbegin 
    t[i,j]=q; 
    s[i,j]=k; 
    end; 
            end; 
    end; 
    return(t,s); 
    end; 
    算法MINIMUM_WEIGHT_占用θ(n2)空间,耗时θ(n3)。 
    (4)构造最优三角剖分 
    如我们所看到的,对于任意的1≤i≤j≤n ,算法MINIMUM_WEIGHT在计算每一个子多边形的最优三角剖分所对应的权值t[i,j]的同时,还在s[i,j]中记录了此最优三角剖分中与边 (或弦)vi-1vj构成的三角形的第三个顶点的位置。因此,利用最优子结构性质并借助于s[i,j],1≤i≤j≤n ,凸(n+l)边形P=的最优三角剖分可容易地在Ο(n)时间内构造出来。

    展开全文
  • 拼图游戏常用算法

    千次阅读 2018-01-17 18:26:28
    拼图游戏常用算法 1、随机数组生成 //随机矩阵 /** * * @param {Object} arr 要混洗的范围 * @param {Object} count 得到数组的大小 */ function getRandomArrayElements(arr, count) { //拷贝所有数组...

    拼图游戏常用算法

    1、随机数组生成

    //随机矩阵
    /**
     * 
     * @param {Object} arr  要混洗的范围
     * @param {Object} count 得到数组的大小
     */
    function getRandomArrayElements(arr, count) {
        //拷贝所有数组元素到shuffled中
        var shuffled = arr.slice(0),
            i = arr.length,
            min = i - count,
            temp, index;
        //如果i小于长度
        while(i-- > min) {
            //产生一个随机数,下标为取值范围为索引加1之间的数
            index = Math.floor((i + 1) * Math.random());
            //进行数据交换
            temp = shuffled[index];
            shuffled[index] = shuffled[i];
            shuffled[i] = temp;
        }
        //返回交换后的数组
        return shuffled.slice(min);
    }
    //函数测试
    var puzzle = [1, 2, 3, 4, 5, 6, 7, 8, 0]; 
    //数组混洗
    var arr = getRandomArrayElements(puzzle,puzzle.length);
    console.log(arr)

    测试结果:
    image

    2、拼图可解计算

    有两种方式可以判断拼图是否可解:

    (1)判断整个序列是奇排列还是偶排列,再判断0的位置是奇位置还是偶位置,如果前两者的奇偶性相同则有解。

    (2)序列里面排除空白块0,判断序列是奇排列还是偶排列。如果是偶排列,则可以完成。

    (3)偶排列任意交换两个数形成奇排列,奇排列任意交换两个数形成偶排列。

    什么是逆序?
    当数列中较小的数字位置在较大数字的后方时,就是逆序。
    逆序数:
    例如:
    1 2 3 5 4,逆序数有1对,54
    5 4 3 2 1,逆序数有10对,54,53,52,51,43,42,41,32,31,21

    //拼图的奇偶性
    /**
     * 
     * @param {Object} arr 拼图数组
     * @param {Object} size 数组大小
     */
    function CalcParity(arr, size) {
        var count = 0;
        //计算排列的奇偶性
        for(var i = 0; i < size - 1; i++) {
            for(var j = i + 1; j < size; j++) {
                //找到0所在的位置
                if(arr[i] > arr[j]) {
                    count++;
                }
            }
        }
        //排列奇偶性
        console.log("逆序数为:" + count)
            //计算0的位置
        for(var i = 0; i < size; i++) {
            //找出0所在的位置
            if(arr[i] == 0) {
                break;
            }
        }
        console.log("0位置:" + i)
    
        if(count % 2 != i % 2) //奇偶性不同则无解
        {
            //无解
            console.log("无解")
            return false;   
        } else {
            console.log("可解")
            return true;
        }
    }
    
    //函数测试
    var puzzle = [1, 2, 3, 4, 5, 6, 7, 8, 0]; //可解
    //数组混淆
    var arr = getRandomArrayElements(puzzle,puzzle.length);
    CalcParity(arr, arr.length);

    测试结果:
    image
    注:有解无解函数只可判定3X3,4x4无法判定。

    展开全文
  • 游戏开发中常用算法

    万次阅读 多人点赞 2018-04-02 17:16:57
    堆排序:可用于做游戏排行榜前多少多少名,根据求最大的K个数还是最小的K个数来建最大堆和最小堆,再将最大/小堆的根节点和最后一个子叶节点交换,最后调整堆,重复刚才那两个步骤,直到得到K个数。当然,这种题也...

    内容会持续更新,有错误的地方欢迎指正,谢谢!

    1.与数组相关的算法:

    1. 快速排序(分治思想的应用):不是任何情况都适用,数据量小的话,还不如冒泡快,但快排的确很优秀。
    2. 堆排序:可用于做游戏排行榜前多少多少名,根据求最大的K个数还是最小的K个数来建最大堆和最小堆,再将最大/小堆的根节点和最后一个子叶节点交换,最后调整堆,重复刚才那两个步骤,直到得到K个数。当然,这种题也可以用红黑树实现的set来做。
    3. 二分查找:用于查找出分数为多少多少的玩家

    2.与树有关的算法

    四叉树、八叉树可用来检测大量物体之间的碰撞总次数。

    这里写图片描述

    3.与图有关的算法

    1.小型游戏可以用的简单的寻路算法:

    1. 随机寻路算法:当NPC不管是遇到障碍物还是遇到了边界(利用碰撞检测),都会随机选取一个前进的方向,继续行走
    2. 跟踪算法:当游戏中的主角进入到NPC 的“警戒区域”后,游戏的AI 可轻易获得目标的位置,然后控制NPC 对象移向被跟踪的对象
    3. 闪避算法:和跟踪算法完全相反,也就是当游戏中的主角进入到NPC 的“警戒区域”后,主角可以去追着NPC跑

    2.大型游戏一般使用A*寻路算法:使用最广泛的一种寻路算法,简单说一下A*寻路算法:

    这里写图片描述

    公式:f(n)=g(n)+h(n),g(n)表示从起点到任意点n的实际直线距离,h(n)表示任意顶点n到目标点的估算距离(常用曼哈顿距离公式用于估算h(n):|x1 - x2| + |y1 - y2|)

    把待处理的方格A存入一个”开启列表”,开启列表就是一个等待检查方格的列表;”关闭列表”中存放的都是不需要再次检查的方格。

    每次从OPEN列表中选择 f(n) 最小的节点将其加入CLOESE列表中,同时扩展相邻节点并将它们加入OPEN列表,可把OPEN列表看成一个优先队列,key值为 f(n),优先级最高的先出。

    最后直到把终点加入OPEN列表中,计算出指针指向就完事了。所以最后的路径就是,从终点开始沿着父指针不断往起点走,最后回到起始点,这样最短路径就找到了:

    这里写图片描述

    A*寻路的详细介绍请见:https://blog.csdn.net/billcyj/article/details/79462670

    3.DFS、BFS也常用于求最优方法这类问题

    展开全文
  • 游戏常用算法

    万次阅读 2013-09-11 12:50:51
    算法一:A*寻路初探 译者序:很久以前就知道了A*算法,但是从未认真读过相关的文章,也没有看过代码,只是脑子里有个模糊的概念。这次决定从头开始,研究一下这个被人推崇备至的简单方法,作为学习人工智能的开始。...

    算法一:A*寻路初探

    译者序:很久以前就知道了A*算法,但是从未认真读过相关的文章,也没有看过代码,只是脑子里有个模糊的概念。这次决定从头开始,研究一下这个被人推崇备至的简单方法,作为学习人工智能的开始。

    这篇文章非常知名,国内应该有不少人翻译过它,我没有查找,觉得翻译本身也是对自身英文水平的锻炼。经过努力,终于完成了文档,也明白的A*算法的原理。毫无疑问,作者用形象的描述,简洁诙谐的语言由浅入深的讲述了这一神奇的算法,相信每个读过的人都会对此有所认识。

    原文链接:http://www.gamedev.net/reference/articles/article2003.asp

    以下是翻译的正文。(由于本人使用ultraedit编辑,所以没有对原文中的各种链接加以处理(除了图表),也是为了避免未经许可链接的嫌疑,有兴趣的读者可以参考原文。

    会者不难,A*(念作A星)算法对初学者来说的确有些难度。

    这篇文章并不试图对这个话题作权威的陈述。取而代之的是,它只是描述算法的原理,使你可以在进一步的阅读中理解其他相关的资料。

    最后,这篇文章没有程序细节。你尽可以用任意的计算机程序语言实现它。如你所愿,我在文章的末尾包含了一个指向例子程序的链接。 压缩包包括C++和Blitz Basic两个语言的版本,如果你只是想看看它的运行效果,里面还包含了可执行文件。我们正在提高自己。让我们从头开始。。。

     

    序:搜索区域

    假设有人想从A点移动到一墙之隔的B点,如图,绿色的是起点A,红色是终点B,蓝色方块是中间的墙。

     [图1]

        你首先注意到,搜索区域被我们划分成了方形网格。像这样,简化搜索区域,是寻路的第一步。这一方法把搜索区域简化成了一个二维数组。数组的每一个元素是网格的一个方块,方块被标记为可通过的和不可通过的。路径被描述为从A到B我们经过的方块的集合。一旦路径被找到,我们的人就从一个方格的中心走向另一个,直到到达目的地。

    这些中点被称为“节点”。当你阅读其他的寻路资料时,你将经常会看到人们讨论节点。为什么不把他们描述为方格呢?因为有可能你的路径被分割成其他不是方格的结构。他们完全可以是矩形,六角形,或者其他任意形状。节点能够被放置在形状的任意位置-可以在中心,或者沿着边界,或 其他什么地方。我们使用这种系统,无论如何,因为它是最简单的。

     

    开始搜索

    正如我们处理上图网格的方法,一旦搜索区域被转化为容易处理的节点,下一步就是去引导一次找到最短路径的搜索。在A*寻路算法中,我们通过从点A开始,检查相邻方格的方式,向外扩展直到找到目标。

     

    我们做如下操作开始搜索:

       1,从点A开始,并且把它作为待处理点存入一个“开启列表”。开启列表就像一张购物清单。尽管现在列表里只有一个元素,但以后就会多起来。你的路径可能会通过它包含的方格,也可能不会。基本上,这是一个待检查方格的列表。

       2,寻找起点周围所有可到达或者可通过的方格,跳过有墙,水,或其他无法通过地形的方格。也把他们加入开启列表。为所有这些方格保存点A作为“父方格”。当我们想描述路径的时候,父方格的资料是十分重要的。后面会解释它的具体用途。

       3,从开启列表中删除点A,把它加入到一个“关闭列表”,列表中保存所有不需要再次检查的方格。

    在这一点,你应该形成如图的结构。在图中,暗绿色方格是你起始方格的中心。它被用浅蓝色描边,以表示它被加入到关闭列表中了。所有的相邻格现在都在开启列表中,它们被用浅绿色描边。每个方格都有一个灰色指针反指他们的父方格,也就是开始的方格。

     [图2]

    接着,我们选择开启列表中的临近方格,大致重复前面的过程,如下。但是,哪个方格是我们要选择的呢?是那个F值最低的。

     

    路径评分选择路径中经过哪个方格的关键是下面这个等式:

    F = G + H

    这里:

        * G = 从起点A,沿着产生的路径,移动到网格上指定方格的移动耗费。

        * H = 从网格上那个方格移动到终点B的预估移动耗费。这经常被称为启发式的,可能会让你有点迷惑。这样叫的原因是因为它只是个猜测。我们没办法事先知道路径的长 度,因为路上可能存在各种障碍(墙,水,等等)。虽然本文只提供了一种计算H的方法,但是你可以在网上找到很多其他的方法。

    我们的路径是通过反复遍历开启列表并且选择具有最低F值的方格来生成的。文章将对这个过程做更详细的描述。首先,我们更深入的看看如何计算这个方程。

     

    正如上面所说,G表示沿路径从起点到当前点的移动耗费。在这个例子里,我们令水平或者垂直移动的耗费为10,对角线方向耗费为14。我们取这些值是因为沿对角线的距离是沿水平或垂直移动耗费的的根号2(别怕),或者约1.414倍。为了简化,我们用10和14近似。比例基本正确,同时我们避免了求根运算和小数。这不是只因为我们怕麻烦或者不喜欢数学。使用这样的整数对计算机来说也更快捷。你不就就会发现,如果你不使用这些简化方法,寻路会变得很慢。

     

    既然我们在计算沿特定路径通往某个方格的G值,求值的方法就是取它父节点的G值,然后依照它相对父节点是对角线方向或者直角方向(非对角线),分别增加14和10。例子中这个方法的需求会变得更多,因为我们从起点方格以外获取了不止一个方格。

     

    H 值可以用不同的方法估算。我们这里使用的方法被称为曼哈顿方法,它计算从当前格到目的格之间水平和垂直的方格的数量总和,忽略对角线方向,然后把结果乘以 10。这被成为曼哈顿方法是因为它看起来像计算城市中从一个地方到另外一个地方的街区数,在那里你不能沿对角线方向穿过街区。很重要的一点,我们忽略了一切障碍物。这是对剩余距离的一个估算,而非实际值,这也是这一方法被称为启发式的原因。想知道更多?你可以在这里找到方程和额外的注解。

    F的值是G和H的和。第一步搜索的结果可以在下面的图表中看到。F,G和H的评分被写在每个方格里。正如在紧挨起始格右侧的方格所表示的,F被打印在左上角,G在左下角,H则在右下角。

     [图3]

    现在我们来看看这些方格。写字母的方格里,G = 10。这是因为它只在水平方向偏离起始格一个格距。紧邻起始格的上方,下方和左边的方格的G值都等于10。对角线方向的G值是14。

    H 值通过求解到红色目标格的曼哈顿距离得到,其中只在水平和垂直方向移动,并且忽略中间的墙。用这种方法,起点右侧紧邻的方格离红色方格有3格距离,H值就 是30。这块方格上方的方格有4格距离(记住,只能在水平和垂直方向移动),H值是40。你大致应该知道如何计算其他方格的H值了~。

    每个格子的F值,还是简单的由G和H相加得到

     

    继续搜索

     

    为了继续搜索,我们简单的从开启列表中选择F值最低的方格。然后,对选中的方格做如下处理:

     

       4,把它从开启列表中删除,然后添加到关闭列表中。

       5,检查所有相邻格子。跳过那些已经在关闭列表中的或者不可通过的(有墙,水的地形,或者其他无法通过的地形),把他们添加进开启列表,如果他们还不在里面的话。把选中的方格作为新的方格的父节点。

       6,如果某个相邻格已经在开启列表里了,检查现在的这条路径是否更好。换句话说,检查如果我们用新的路径到达它的话,G值是否会更低一些。如果不是,那就什么都不做。

        另一方面,如果新的G值更低,那就把相邻方格的父节点改为目前选中的方格(在上面的图表中,把箭头的方向改为指向这个方格)。最后,重新计算F和G的值。如果这看起来不够清晰,你可以看下面的图示。

    好了,让我们看看它是怎么运作的。我们最初的9格方格中,在起点被切换到关闭列表中后,还剩8格留在开启列表中。这里面,F值最低的那个是起始格右侧紧邻的格子,它的F值是40。因此我们选择这一格作为下一个要处理的方格。在紧随的图中,它被用蓝色突出显示。

     [图4]

    首先,我们把它从开启列表中取出,放入关闭列表(这就是他被蓝色突出显示的原因)。然后我们检查相邻的格子。哦,右侧的格子是墙,所以我们略过。左侧的格子是起始格。它在关闭列表里,所以我们也跳过它。

    其 他4格已经在开启列表里了,于是我们检查G值来判定,如果通过这一格到达那里,路径是否更好。我们来看选中格子下面的方格。它的G值是14。如果我们从当 前格移动到那里,G值就会等于20(到达当前格的G值是10,移动到上面的格子将使得G值增加10)。因为G值20大于14,所以这不是更好的路径。如果 你看图,就能理解。与其通过先水平移动一格,再垂直移动一格,还不如直接沿对角线方向移动一格来得简单。

    当我们对已经存在于开启列表中的4个临近格重复这一过程的时候,我们发现没有一条路径可以通过使用当前格子得到改善,所以我们不做任何改变。既然我们已经检查过了所有邻近格,那么就可以移动到下一格了。

    于是我们检索开启列表,现在里面只有7格了,我们仍然选择其中F值最低的。有趣的是,这次,有两个格子的数值都是54。我们如何选择?这并不麻烦。从速度上 考虑,选择最后添加进列表的格子会更快捷。这种导致了寻路过程中,在靠近目标的时候,优先使用新找到的格子的偏好。但这无关紧要。(对相同数值的不同对 待,导致不同版本的A*算法找到等长的不同路径。)

     

    那我们就选择起始格右下方的格子,如图。

     

     [图5]

     

    这次,当我们检查相邻格的时候,发现右侧是墙,于是略过。上面一格也被略过。我们也略过了墙下面的格子。为什么呢?因为你不能在不穿越墙角的情况下直接到达 那个格子。你的确需要先往下走然后到达那一格,按部就班的走过那个拐角。(注解:穿越拐角的规则是可选的。它取决于你的节点是如何放置的。)

    这样一来,就剩下了其他5格。当前格下面的另外两个格子目前不在开启列表中,于是我们添加他们,并且把当前格指定为他们的父节点。其余3格,两个已经在开启 列表中(起始格,和当前格上方的格子,在表格中蓝色高亮显示),于是我们略过它们。最后一格,在当前格的左侧,将被检查通过这条路径,G值是否更低。不必 担心,我们已经准备好检查开启列表中的下一格了。

     

    我们重复这个过程,知道目标格被添加进开启列表,就如在下面的图中所看到的。

     

     [图6]

     

    注 意,起始格下方格子的父节点已经和前面不同的。之前它的G值是28,并且指向右上方的格子。现在它的G值是20,指向它上方的格子。这在寻路过程中的某处 发生,当应用新路径时,G值经过检查变得低了-于是父节点被重新指定,G和F值被重新计算。尽管这一变化在这个例子中并不重要,在很多场合,这种变化会导 致寻路结果的巨大变化。

     

    那么,我们怎么确定这条路径呢?很简单,从红色的目标格开始,按箭头的方向朝父节点移动。这最终会引导你回到起始格,这就是你的路径!看起来应该像图中那样。从起始格A移动到目标格B只是简单的从每个格子(节点)的中点沿路径移动到下一个,直到你到达目标点。就这么简单。

     

     [图7]

     

     

     

     

    A*方法总结

    好,现在你已经看完了整个说明,让我们把每一步的操作写在一起:

     

       1,把起始格添加到开启列表。

       2,重复如下的工作:

          a) 寻找开启列表中F值最低的格子。我们称它为当前格。

          b) 把它切换到关闭列表。

          c) 对相邻的8格中的每一个?

              * 如果它不可通过或者已经在关闭列表中,略过它。反之如下。

              * 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。

              * 如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。

          d) 停止,当你

              * 把目标格添加进了开启列表,这时候路径被找到,或者

              * 没有找到目标格,开启列表已经空了。这时候,路径不存在。

       3.保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。

     

    题外话

     

    离题一下,见谅,值得一提的是,当你在网上或者相关论坛看到关于A*的不同的探讨,你有时会看到一些被当作A*算法的代码而实际上他们不是。要使用A*,你 必须包含上面讨论的所有元素--特定的开启和关闭列表,用F,G和H作路径评价。有很多其他的寻路算法,但他们并不是A*,A*被认为是他们当中最好的。 Bryan Stout在这篇文章后面的参考文档中论述了一部分,包括他们的一些优点和缺点。有时候特定的场合其他算法会更好,但你必须很明确你在作什么。好了,够多 的了。回到文章。

     

    实现的注解

     

    现在你已经明白了基本原理,写你的程序的时候还得考虑一些额外的东西。下面这些材料中的一些引用了我用C++和Blitz Basic写的程序,但对其他语言写的代码同样有效。

     

    1, 维护开启列表:这是A*寻路算法最重要的组成部分。每次你访问开启列表,你都需要寻找F值最低的方格。有几种不同的方法实现这一点。你可以把路径元素随意 保存,当需要寻找F值最低的元素的时候,遍历开启列表。这很简单,但是太慢了,尤其是对长路径来说。这可以通过维护一格排好序的列表来改善,每次寻找F值 最低的方格只需要选取列表的首元素。当我自己实现的时候,这种方法是我的首选。

     

    在小地图。这种方法工作的很好,但它并不是最快的解决方 案。更苛求速度的A*程序员使用叫做“binary heap”的方法,这也是我在代码中使用的方法。凭我的经验,这种方法在大多数场合会快2~3倍,并且在长路经上速度呈几何级数提升(10倍以上速度)。 如果你想了解更多关于binary heap的内容,查阅我的文章,Using Binary Heaps in A* Pathfinding。

     

    2, 其他单位:如果你恰好看了我的例子代码,你会发现它完全忽略了其他单位。我的寻路者事实上可以相互穿越。取决于具体的游戏,这也许可以,也许不行。如果你 打算考虑其他单位,希望他们能互相绕过,我建议在寻路算法中忽略其他单位,写一些新的代码作碰撞检测。当碰撞发生,你可以生成一条新路径或者使用一些标准 的移动规则(比如总是向右,等等)直到路上没有了障碍,然后再生成新路径。为什么在最初的路径计算中不考虑其他单位呢?那是因为其他单位会移动,当你到达 他们原来的位置的时候,他们可能已经离开了。这有可能会导致奇怪的结果,一个单位突然转向,躲避一个已经不在那里的单位,并且会撞到计算完路径后,冲进它 的路径中的单位。

     

    然而,在寻路算法中忽略其他对象,意味着你必须编写单独的碰撞检测代码。这因游戏而异,所以我把这个决定权留给你。参考文献列表中,Bryan Stout的文章值得研究,里面有一些可能的解决方案(像鲁棒追踪,等等)。

     

    3, 一些速度方面的提示:当你开发你自己的A*程序,或者改写我的,你会发现寻路占据了大量的CPU时间,尤其是在大地图上有大量对象在寻路的时候。如果你阅 读过网上的其他材料,你会明白,即使是开发了星际争霸或帝国时代的专家,这也无可奈何。如果你觉得寻路太过缓慢,这里有一些建议也许有效:

     

        * 使用更小的地图或者更少的寻路者。

        * 不要同时给多个对象寻路。取而代之的是把他们加入一个队列,把寻路过程分散在几个游戏周期中。如果你的游戏以40周期每秒的速度运行,没人能察觉。但是他们会发觉游戏速度突然变慢,当大量寻路者计算自己路径的时候。

        * 尽量使用更大的地图网格。这降低了寻路中搜索的总网格数。如果你有志气,你可以设计两个或者更多寻路系统以便使用在不同场合,取决于路径的长度。这也正是 专业人士的做法,用大的区域计算长的路径,然后在接近目标的时候切换到使用小格子/区域的精细寻路。如果你对这个观点感兴趣,查阅我的文章Two- Tiered A* Pathfinding(双层A*算法)

        * 使用路径点系统计算长路径,或者预先计算好路径并加入到游戏中。

        * 预处理你的地图,表明地图中哪些区域是不可到达的。我把这些区域称作“孤岛”。事实上,他们可以是岛屿或其他被墙壁包围等无法到达的任意区域。A*的下限是,当你告诉它要寻找通往那些区域的路径时,它会搜索整个地图,直到所有可到达的方格/节点都被通过开启列表和关闭列表的计算。这会浪费大量的CPU时 间。可以通过预先确定这些区域(比如通过flood-fill或类似的方法)来避免这种情况的发生,用某些种类的数组记录这些信息,在开始寻路前检查它。 在我Blitz版本的代码中,我建立了一个地图预处理器来作这个工作。它也标明了寻路算法可以忽略的死端,这进一步提高了寻路速度。

     

    4, 不同的地形损耗:在这个教程和我附带的程序中,地形只有两种-可通过的和不可通过的。但是你可能会需要一些可通过的地形,但是移动耗费更高-沼泽,小山, 地牢的楼梯,等等。这些都是可通过但是比平坦的开阔地移动耗费更高的地形。类似的,道路应该比自然地形移动耗费更低。

     

    这个问题很容易解 决,只要在计算任何地形的G值的时候增加地形损耗就可以了。简单的给它增加一些额外的损耗就可以了。由于A*算法已经按照寻找最低耗费的路径来设计,所以 很容易处理这种情况。在我提供的这个简单的例子里,地形只有可通过和不可通过两种,A*会找到最短,最直接的路径。但是在地形耗费不同的场合,耗费最低的 路径也许会包含很长的移动距离-就像沿着路绕过沼泽而不是直接穿过它。

     

    一种需额外考虑的情况是被专家称之为“influence mapping”的东西(暂译为影响映射图)。就像上面描述的不同地形耗费一样,你可以创建一格额外的分数系统,并把它应用到寻路的AI中。假设你有一张 有大批寻路者的地图,他们都要通过某个山区。每次电脑生成一条通过那个关口的路径,它就会变得更拥挤。如果你愿意,你可以创建一个影响映射图对有大量屠杀 事件的格子施以不利影响。这会让计算机更倾向安全些的路径,并且帮助它避免总是仅仅因为路径短(但可能更危险)而持续把队伍和寻路者送到某一特定路径。

     

    5,处理未知区域:你是否玩过这样的PC游戏,电脑总是知道哪条路是正确的,即使它还没有侦察过地图?对于游戏,寻路太好会显得不真实。幸运的是,这是一格可以轻易解决的问题。

     

    答 案就是为每个不同的玩家和电脑(每个玩家,而不是每个单位--那样的话会耗费大量的内存)创建一个独立的“knownWalkability”数组,每个 数组包含玩家已经探索过的区域,以及被当作可通过区域的其他区域,直到被证实。用这种方法,单位会在路的死端徘徊并且导致错误的选择直到他们在周围找到 路。一旦地图被探索了,寻路就像往常那样进行。

     

    6,平滑路径:尽管A*提供了最短,最低代价的路径,它无法自动提供看起来平滑的路径。看一下我们的例子最终形成的路径(在图7)。最初的一步是起始格的右下方,如果这一步是直接往下的话,路径不是会更平滑一些吗?

     

    有 几种方法来解决这个问题。当计算路径的时候可以对改变方向的格子施加不利影响,对G值增加额外的数值。也可以换种方法,你可以在路径计算完之后沿着它跑一遍,找那些用相邻格替换会让路径看起来更平滑的地方。想知道完整的结果,查看Toward More Realistic Pathfinding,一篇(免费,但是需要注册)Marco Pinter发表在Gamasutra.com的文章

     

    7,非方形搜索区域:在我们的例子里,我们使用简单的2D方形图。你可以不使用这种方式。你可以使用不规则形状的区域。想想冒险棋的游戏,和游戏中那些国家。你可以设计一个像那样的寻路关卡。为此,你可能需要建立一个国家相邻关系的表格,和从一个国家移动到另一个的G值。你也需要估算H值的方法。其他的事情就和例子中完全 一样了。当你需要向开启列表中添加新元素的时候,不需使用相邻的格子,取而代之的是从表格中寻找相邻的国家。

     

    类似的,你可以为一张确定的 地形图创建路径点系统,路径点一般是路上,或者地牢通道的转折点。作为游戏设计者,你可以预设这些路径点。两个路径点被认为是相邻的如果他们之间的直线上 没有障碍的话。在冒险棋的例子里,你可以保存这些相邻信息在某个表格里,当需要在开启列表中添加元素的时候使用它。然后你就可以记录关联的G值(可能使用 两点间的直线距离),H值(可以使用到目标点的直线距离),其他都按原先的做就可以了。

     

    另一个在非方形区域搜索RPG地图的例子,查看我的文章Two-Tiered A* Pathfinding。

     

    进一步的阅读

     

    好,现在你对一些进一步的观点有了初步认识。这时,我建议你研究我的源代码。包里面包含两个版本,一个是用C++写的,另一个用Blitz Basic。顺便说一句,两个版本都注释详尽,容易阅读,这里是链接。

     

        * 例子代码:A* Pathfinder (2D) Version 1.71

     

    如果你既不用C++也不用Blitz Basic,在C++版本里有两个小的可执行文件。Blitz Basic可以在从Blitz Basic网站免费下载的litz Basic 3D(不是Blitz Plus)演示版上运行。Ben O'Neill提供一个联机演示可以在这里找到。

     

    你也该看看以下的网页。读了这篇教程后,他们应该变得容易理解多了。

     

        *  Amit的 A* 页面:这是由Amit Patel制作,被广泛引用的页面,如果你没有事先读这篇文章,可能会有点难以理解。值得一看。尤其要看Amit关于这个问题的自己的看法。

        * Smart Moves:智能寻路:Bryan Stout发表在Gamasutra.com的这篇文章需要注册才能阅读。注册是免费的而且比起这篇文章和网站的其他资源,是非常物有所值的。Bryan 用Delphi写的程序帮助我学习A*,也是我的A*代码的灵感之源。它还描述了A*的几种变化。

        * 地形分析:这是一格高阶,但是有趣的话题,Dave Pottinge撰写,Ensemble Studios的专家。这家伙参与了帝国时代和君王时代的开发。别指望看懂这里所有的东西,但是这是篇有趣的文章也许会让你产生自己的想法。它包含一些对 mip-mapping,influence mapping以及其他一些高级AI/寻路观点。对"flood filling"的讨论使我有了我自己的“死端”和“孤岛”的代码的灵感,这些包含在我Blitz版本的代码中。

     

    其他一些值得一看的网站:

     

        * aiGuru: Pathfinding

        * Game AI Resource: Pathfinding

        * GameDev.net: Pathfinding

     

    算法二:碰撞

    1.   碰撞检测和响应

    碰撞在游戏中运用的是非常广泛的,运用理论实现的碰撞,再加上一些小技巧,可以让碰撞检测做得非常精确,效率也非常高。从而增加游戏的功能和可玩性。

     

    2D碰撞检测

     

    2D的碰撞检测已经非常稳定,可以在许多著作和论文中查询到。3D的碰撞还没有找到最好的方法,现在使用的大多数方法都是建立在2D基础上的。

     

    碰撞检测:

    碰撞的检测不仅仅是运用在游戏中,事实上,一开始的时候是运用在模拟和机器人技术上的。这些工业上的碰撞检测要求非常高,而碰撞以后的响应也是需要符合现实生活的,是需要符合人类常规认识的。游戏中的碰撞有些许的不一样,况且,更重要的,我们制作的东西充其量是商业级别,还不需要接触到纷繁复杂的数学公式。

    图1

     

    最理想的碰撞,我想莫过于上图,完全按照多边形的外形和运行路径规划一个范围,在这个范围当中寻找会产生阻挡的物体,不管是什么物体,产生阻挡以后,我们运、动的物体都必须在那个位置产生一个碰撞的事件。最美好的想法总是在实现上有一些困难,事实上我们可以这么做,但是效率却是非常非常低下的,游戏中,甚至于工业中无法忍受这种速度,所以我们改用其它的方法来实现。

    图2

    最简单的方法如上图,我们寻找物体的中心点,然后用这个中心点来画一个圆,如果是一个3D的物体,那么我们要画的就是一个球体。在检测物体碰撞的时候,我们只要检测两个物体的半径相加是否大于这两个物体圆心的实际距离。

    图3

    这个算法是最简单的一种,现在还在用,但是不是用来做精确的碰撞检测,而是用来提高效率的模糊碰撞检测查询,到了这个范围以后,再进行更加精密的碰撞检测。 一种比较精密的碰撞检测查询就是继续这种画圆的思路,然后把物体细分,对于物体的每个部件继续画圆,然后再继续进行碰撞检测,直到系统规定的,可以容忍的 误差范围以后才触发碰撞事件,进行碰撞的一些操作。

     

    有没有更加简单的方法呢?2D游戏中有许多图片都是方方正正的,所以我们不必把碰撞的范围画成一个圆的,而是画成一个方的。这个正方形,或者说是一个四边形和坐标轴是对齐的,所以运用数学上的一些方法,比如距离计算等还是比较方便的。这个检测方法就叫AABBs(Axis-aligned Bounding Boxes)碰撞检测,游戏中已经运用的非常广泛了,因为其速度快,效率高,计算起来非常方便,精确度也是可以忍受的。

     

    做到这一步,许多游戏的需求都已经满足了。但是,总是有人希望近一步优化,而且方法也是非常陈旧的:继续对物体的各个部分进行细分,对每个部件做AABB的矩形,那这个优化以后的系统就叫做OBB系统。虽然说这个优化以后的系统也不错,但是,许多它可以运用到的地方,别人却不爱使用它,这是后面会继续介绍的 地方。

     

    John Carmack不知道看的哪本书,他早在DOOM中已经使用了BSP系统(二分空间分割),再加上一些小技巧,他的碰撞做得就非常好了,再加上他发明的 castray算法,DOOM已经不存在碰撞的问题,解决了这样的关键技术,我想他不再需要在什么地方分心了,只要继续研究渲染引擎就可以了。 (Windows游戏编程大师技巧P392~P393介绍)(凸多边形,多边形退化,左手定律)SAT系统非常复杂,是SHT(separating hyperplane theorem,分离超平面理论)的一种特殊情况。这个理论阐述的就是两个不相关的曲面,是否能够被一个超平面所分割开来,所谓分割开来的意思就是一个曲 面贴在平面的一边,而另一个曲面贴在平面的另一边。我理解的就是有点像相切的意思。SAT是SHT的特殊情况,所指的就是两个曲面都是一些多边形,而那个 超平面也是一个多边形,这个超平面的多边形可以在场景中的多边形列表中找到,而超平面可能就是某个多边形的表面,很巧的就是,这个表面的法线和两个曲面的 切面是相对应的。接下来的证明,我想是非常复杂的事情,希望今后能够找到源代码直接运用上去。而我们现在讲究的快速开发,我想AABB就足以满足了。

     

    3D碰撞检测

     

    3D 的检测就没有什么很标准的理论了,都建立在2D的基础上,我们可以沿用AABB或者OBB,或者先用球体做粗略的检测,然后用AABB和OBB作精细的检测。BSP技术不流行,但是效率不错。微软提供了D3DIntersect函数让大家使用,方便了许多,但是和通常一样,当物体多了以后就不好用了,明显 的就是速度慢许多。

     

    碰撞反应:

    碰撞以后我们需要做一些反应,比如说产生反冲力让我们反弹出去,或者停下来,或者让阻挡我们的物体飞出去,或者穿墙,碰撞最讨厌的就是穿越,本来就不合逻辑,查阅了那么多资料以后,从来没有看到过需要穿越的碰撞,有摩擦力是另外一回事。首先看看弹性碰撞。弹性碰撞就是我们初中物理中说的动量守恒。物体在碰撞前后的动量守恒,没有任何能量损失。这样的碰撞运用于打砖块的游戏中。引入质量的话,有的物体会是有一定的质量,这些物体通常来说是需要在碰撞以后进行另外一个方向的运动的,另外一些物体是设定为质量无限大的,这些物体通常是碰撞墙壁。

     

    当物体碰到质量非常大的物体,默认为碰到了一个弹性物体,其速度会改变,但是能量不会受到损失。一般在代码上的做法就是在速度向量上加上一个负号。

     

    绝对的弹性碰撞是很少有的,大多数情况下我们运用的还是非弹性碰撞。我们现在玩的大多数游戏都用的是很接近现实的非弹性碰撞,例如Pain-Killer中的那把吸力枪,它弹出去的子弹吸附到NPC身上时的碰撞响应就是非弹性碰撞;那把残忍的分尸刀把墙打碎的初始算法就是一个非弹性碰撞,其后使用的刚体力学就是先建立在这个算法上的。那么,是的,如果需要非弹性碰撞,我们需要介入摩擦力这个因素,而我们也无法简单使用动量守恒这个公式。

    我们可以采取比较简单的方法,假设摩擦系数μ非常大,那么只要物体接触,并且拥有一个加速度,就可以产生一个无穷大的摩擦力,造成物体停止的状态。

    基于别人的引擎写出一个让自己满意的碰撞是不容易的,那么如果自己建立一个碰撞系统的话,以下内容是无法缺少的:

    ——一个能够容忍的碰撞系统;

    ——一个从概念上可以接受的物理系统;

    ——质量;

    ——速度;

    ——摩擦系数;

    ——地心引力。

    算法三:寻路算法新思维

    目前常用寻路算法是A*方式,原理是通过不断搜索逼近目的地的路点来获得。

     

    如果通过图像模拟搜索点,可以发现:非启发式的寻路算法实际上是一种穷举法,通过固定顺序依次搜索人物周围的路点,直到找到目的地,搜索点在图像上的表现为一个不断扩大的矩形。如下:

     

    很快人们发现如此穷举导致搜索速度过慢,而且不是很符合逻辑,试想:如果要从(0,0)点到达(100,0)点,如果每次向东搜索时能够走通,那么干吗还要 搜索其他方向呢?所以,出现了启发式的A*寻路算法,一般通过已经走过的路程 + 到达目的地的直线距离 代价值作为搜索时的启发条件,每个点建立一个代价值,每次搜索时就从代价低的最先搜索,如下:

     

    综上所述,以上的搜索是一种矩阵式的不断逼近终点的搜索做法。优点是比较直观,缺点在于距离越远、搜索时间越长。

    现在,我提出一种新的AI寻路方式——矢量寻路算法

    通过观察,我们可以发现,所有的最优路线,如果是一条折线,那么、其每一个拐弯点一定发生在障碍物的突出边角,而不会在还没有碰到障碍物就拐弯的情况:如下图所示:

     

    我们可以发现,所有的红色拐弯点都是在障碍物(可以认为是一个凸多边形)的顶点处,所以,我们搜索路径时,其实只需要搜索这些凸多边形顶点不就可以了吗?如果将各个顶点连接成一条通路就找到了最优路线,而不需要每个点都检索一次,这样就大大减少了搜索次数,不会因为距离的增大而增大搜索时间

     

    这种思路我尚未将其演变为算法,姑且提出一个伪程序给各位参考:

    1.建立各个凸多边形顶点的通路表TAB,表示顶点A到顶点B是否可达,将可达的顶点分组保存下来。如: ( (0,0) (100,0) ),这一步骤在程序刚开始时完成,不要放在搜索过程中空耗时间。

    2.开始搜索A点到B点的路线

    3.检测A点可以直达凸多边形顶点中的哪一些,挑选出最合适的顶点X1。

    4.检测与X1相连(能够接通)的有哪些顶点,挑出最合适的顶点X2。

    5.X2是否是终点B?是的话结束,否则转步骤4(X2代入X1)

     

    如此下来,搜索只发生在凸多边形的顶点,节省了大量的搜索时间,而且找到的路线无需再修剪锯齿,保证了路线的最优性。

    这种方法搜索理论上可以减少大量搜索点、缺点是需要实现用一段程序得出TAB表,从本质上来说是一种空间换时间的方法,而且搜索时A*能够用的启发条件,在矢量搜索时依然可以使用。

     

     

    算法四:战略游戏中的战争模型算法的初步探讨

      《三国志》系列游戏相信大家都有所了解,而其中的(宏观)战斗时关于双方兵力,士气,兵种克制,攻击力,增援以及随战争进行兵力减少等数值的算法是十分值得研究的。或许是由于简单的缘故,我在网上几乎没有找到相关算法的文章。 下面给出这个战争的数学模型算法可以保证游戏中战争的游戏性与真实性兼顾,希望可以给有需要这方面开发的人一些启迪。

    假设用x(t)和y(t)表示甲乙交战双方在t时刻的兵力,如果是开始时可视为双方士兵人数。

      假设每一方的战斗减员率取决于双方兵力和战斗力,用f(x,y)和g(x,y)表示,每一方的增援率是给定函数用u(t)和v(t)表示。

       如果双方用正规部队作战(可假设是相同兵种),先分析甲方的战斗减员率f(x,y)。可知甲方士兵公开活动,处于乙方没一个士兵的监视和杀伤范围之内, 一但甲方的某个士兵被杀伤,乙方的火力立即集中在其余士兵身上,所以甲方的战斗减员率只与乙方的兵力有关可射为f与y成正比,即f=ay,a表示乙方平均 每个士兵对甲方士兵的杀伤率(单位时间的杀伤数),成为乙方的战斗有效系数。类似g= -bx

    这个战争模型模型方程1为

    x’(t)= -a*y(t)+u(t) x’(t)是x(t)对于t 的导数

    y’(t)= -b*x(t)+v(t) y’(t)是y(t)对于t的导数

    利用给定的初始兵力,战争持续时间,和增援兵力可以求出双方兵力在战争中的变化函数。

    (本文中解法略)

    如果考虑由于士气和疾病等引起的非战斗减员率(一般与本放兵力成正比,设甲乙双方分别为h,w)

    可得到改进战争模型方程2:

    x’(t)= -a*y(t)-h*x(t)+u(t)

    y’(t)= -b*x(t)-w*y(t)+v(t)

    利用初始条件同样可以得到双方兵力在战争中的变化函数和战争结果。

    此外还有不同兵种作战(兵种克制)的数学模型:

    模 型1中的战斗有效系数a可以进一步分解为a=ry*py*(sry/sx),其中ry是乙方的攻击率(每个士兵单位的攻击次数),py是每次攻击的命中 率。(sry/sx)是乙方攻击的有效面积sry与甲方活动范围sx之比。类似甲方的战斗有效系数b=rx*px*(srx/sy),rx和px是甲方的 攻击率和命中率,(srx/sy)是甲方攻击的有效面积与乙方活动范围sy之比。由于增加了兵种克制的攻击范围,所以战斗减员率不光与对方兵力有关,而且 随着己放兵力增加而增加。因为在一定区域内,士兵越多被杀伤的就越多。

    方程

    x’(t)= -ry*py*(sry/sx)*x(t)*y(t)-h*x(t)+u(t)

    y’(t)= -rx*px*(srx/sy)*x(t)*y(t)-w*y(t)+u(t) 

    算法五:飞行射击游戏中的碰撞检测

      在游戏中物体的碰撞是经常发生的,怎样检测物体的碰撞是一个很关键的技术问题。在RPG游 戏中,一般都将场景分为许多矩形的单元,碰撞的问题被大大的简化了,只要判断精灵所在的单元是不是有其它的东西就可以了。而在飞行射击游戏(包括象荒野大 镖客这样的射击游戏)中,碰撞却是最关键的技术,如果不能很好的解决,会影响玩游戏者的兴趣。因为飞行射击游戏说白了就是碰撞的游戏——躲避敌人的子弹或 飞机,同时用自己的子弹去碰撞敌人。

      碰撞,这很简单嘛,只要两个物体的中心点距离小于它们的半径之和就可以了。确实,而且我也看到很 多人是这样做的,但是,这只适合圆形的物体——圆形的半径处处相等。如果我们要碰撞的物体是两艘威力巨大的太空飞船,它是三角形或矩形或其他的什么形状,就会出现让人尴尬的情景:两艘飞船眼看就要擦肩而过,却出人意料的发生了爆炸;或者敌人的子弹穿透了你的飞船的右弦,你却安然无恙,这不是我们希望发生的。于是,我们需要一种精确的检测方法。

      那么,怎样才能达到我们的要求呢?其实我们的前辈们已经总结了许多这方面的经验,如上所述的半径检测法,三维中的标准平台方程法,边界框法等等。大多数游戏程序员都喜欢用边界框法,这也是我采用的方法。边界框是在编程中加进去的不可见的边界。边界框法,顾名思义,就是用边界框来检测物体是否发生了碰撞,如果两个物体的边界框相互干扰,则发生了碰撞。用什么样的边界框要视不同情况而定,用最近似的几何形状。当然,你可以用物体的准确几何形状作边界框,但出于效率的考虑,我不赞成这样做,因为游戏中的物体一般都很复杂,用复杂的边界框将增加大量的计算,尤其是浮点计算,而这正是我们想尽量避免的。但边界框也不能与准确几何形状有太大的出入,否则就象用半径法一样出现奇怪的现象。

       在飞行射击游戏中,我们的飞机大多都是三角形的,我们可以用三角形作近似的边界框。现在我们假设飞机是一个正三角形(或等要三角形,我想如果谁把飞机设计 成左右不对称的怪物,那他的审美观一定有问题),我的飞机是正着的、向上飞的三角形,敌人的飞机是倒着的、向下飞的三角形,且飞机不会旋转(大部分游戏中 都是这样的)。我们可以这样定义飞机:

    中心点O(Xo,Yo),三个顶点P0(X0,Y0)、P1(X1,Y1)、P2(X2,Y2)。

    中心点为正三角形的中心点,即中心点到三个顶点的距离相等。接下来的问题是怎样确定两个三角形互相干扰了呢?嗯,现在我们接触到问题的实质了。如果你学过平面解析几何,我相信你可以想出许多方法解决这个问题。判断一个三角形的各个顶点是否在另一个三角形里面,看起来是个不错的方法,你可以这样做,但我却发现一个小问题:一个三角形的顶点没有在另一个三角形的里面,却可能发生了碰撞,因为另一个三角形的顶点在这个三角形的里面,所以要判断两次,这很麻烦。有没有一次判断就可以的方法?

    我们把三角形放到极坐标平面中,中心点为原点,水平线即X轴为零度角。我们发现三角形成了这个样子:在每个角度我们都可以找到一个距离,用以描述三角形的边。既然我们找到了边到中心点的距离,那就可以用这个距离来检测碰撞。如图一,两个三角形中心点坐标分别为(Xo,Yo)和(Xo1, Yo1),由这两个点的坐标求出两点的距离及两点连线和X轴的夹角θ,再由θ求出中心点连线与三角形边的交点到中心点的距离,用这个距离与两中心点距离比 较,从而判断两三角形是否碰撞。因为三角形左右对称,所以θ取-90~90度区间就可以了。哈,现在问题有趣多了,-90~90度区间正是正切函数的定义 域,求出θ之后再找对应的边到中心点的距离就容易多了,利用几何知识,如图二,将三角形的边分为三部分,即图2中红绿蓝三部分,根据θ在那一部分而分别对 待。用正弦定理求出边到中心点的距离,即图2中浅绿色线段的长度。但是,如果飞机每次移动都这样判断一次,效率仍然很低。我们可以结合半径法来解决,先用 半径法判断是否可能发生碰撞,如果可能发生碰撞,再用上面的方法精确判断是不是真的发生了碰撞,这样基本就可以了。如果飞机旋转了怎么办呢,例如,如图三 所示飞机旋转了一个角度α,仔细观察图三会发现,用(θ-α)就可以求出边到中心点的距离,这时你要注意边界情况,即(θ-α)可能大于90度或小于- 90度。啰罗嗦嗦说了这么多,不知道大家明白了没有。我编写了一个简单的例程,用于说明我的意图。在例子中假设所有飞机的大小都一样,并且没有旋转。

    /

    //example.cpp

    //碰撞检测演示

    //作者 李韬

    /

    //限于篇幅,这里只给出了碰撞检测的函数

    //define/

    #define NUM_VERTICES 3

    #define ang_30 -0.5236

    #define ang60  1.0472

    #define ang120 2.0944

    //deftype

     

    struct object

    {

        float xo, yo;

        float radio;

        float x_vel, y_vel;

        float vertices[NUM_VERTICES][2];

    }

     

    //faction/

    //根据角度求距离

    float AngToDis(struct object obj, float angle)

    {

        float dis, R;

        R = obj.radius;

        if (angle <= ang_30)

            dis = R / (2 * sin(-angle));

        else if (angle >= 0)

            dis = R / (2 * sin(angle + ang60));

        else dis = R / (2 * sin(ang120 - angle));

        return dis;

    }

     

    //碰撞检测

    int CheckHit(struct object obj1, struct object obj2)

    {

        float deltaX, deltaY, angle, distance, bumpdis;

        deltaX = abs(obj1.xo - obj2.xo);

        deltaY = obj1.yo - obj2.yo;

        distance = sqrt(deltaX * deltaX + deltaY * deltaY);

        if (distance <= obj.radio)

        {

             angle = atan2(deltaY, deltaX);

             bumpdis1 = AngToDis(obj1, angle);

             return (distance <= 2 * bumpdis);

        }

        ruturn 0;

    }

    //End//

     

      上面程序只是用于演示,并不适合放在游戏中,但你应该明白它的意思,以便写出适合你自己的碰撞检测。游戏中的情况是多种多样的,没有哪种方法能适应所有情况,你一定能根据自己的情况找到最适合自己的方法。

    高级碰撞检测技术 

     

    高级碰撞检测技术 第一部分

    Advanced Collision Detection Techniques

     

    这文章原载于Gamasutra,共有三部分。我想将它翻译,请大家指教。

     

    http://www.gamasutra.com/features/20000330/bobic_01.htm

    http://www.gamasutra.com/features/20000330/bobic_02.htm

    http://www.gamasutra.com/features/20000330/bobic_03.htm

     

     

    / 1 ………………………………………………………………………………………………….

    自 从电脑游戏降临以来,程序员们不断地设计各种方法去模拟现实的世界。例如Pong(著名的碰球游戏),展示了一个动人的场面(一个球及两根摆绳)。当玩家 将拽住摆绳移动到一定高度的,然后放开球,球就会离开玩家向对手冲去。以今天的标准,这样的基础操作也许就是原始碰撞检测的起源。现在的电脑游戏比以前的 Pong复杂多了,而且更多是基于3D的。这也使3D碰撞检测的困难要远远高于一个简单的2D Pong。一些较早的飞行模拟游戏说明了糟糕的碰撞检测技术是怎样破坏一个游戏。如:当你的飞机撞到一座山峰的时候,你居然还可以安全的幸存下来,这在现 实中是不可能发生的。甚至最近刚出的一些游戏也存在此类问题。许多玩家对他们喜爱的英雄或是女英雄部分身体居然可以穿过墙而感到失望。甚至更坏的是玩家被 一颗没有和他发生碰撞关系的火箭击中。因为今天的玩家要求增加唯实论的要求越来越高,我们游戏开发者们将尽可能在我们的游戏世界做一些改进以便接近真实的 世界。

      Since the advent of computer games, programmers have continually devised ways to simulate the world more precisely. Pong, for instance, featured a moving square (a ball) and two paddles. Players had to move the paddles to an appropriate position at an appropriate time, thus rebounding the ball toward the opponent and away from the player. The root of this basic operation is primitive(by today’s standards) collision detection. Today’s games are much more advanced than Pong, and most are based in 3D. Collision detection in 3D is many magnitudes more difficult to implement than a simple 2D Pong game. The experience of playing some of the early flight simulators illustrated how bad collision detection can ruin a game. Flying through a mountain peak and surviving isn’t very realistic. Even some recent games have exhibited collision problems. Many game players have been disappointed by the sight of their favorite heroes or heroines with parts of their bodies inside rigid walls. Even worse, many players have had the experience of being hit by a rocket or bullet that was “not even close” to them. Because today’s players demand increasing levels of realism, we developers will have to do some hard thinking in order to approximate the real world in our game worlds as closely as possible.

     

    / 2 …………………………………………………………………………………………………

    这 篇碰撞检测的论文会使用一些基础的几何学及数学知识。在文章的结束,我也会提供一些参考文献给你。我假定你已经读过Jeff Lander写的图形教程中的碰撞检测部分(“Crashing into the New Year,” ; “When Two Hearts Collide,”; and “Collision Response: Bouncy, Trouncy, Fun,” )。我将给你一些图片让你能快速的联系起核心例程。我们将要讨论的碰撞检测是基于portal-based 及BSP-based 两种类型的引擎。因为每个引擎都有自己组织结构,这使得虚拟世界物体的碰撞检测技术也不尽相同。面向对象的碰撞检测是使用得比较多的,但这取决于你的现实 可实性,就想将引擎分成两部分一样。稍后,我们会概述多边形碰撞检测,也会研究如何扩展我们的弯曲物体。

    This article will assume a basic understanding of the geometry and math involved in collision detection. At the end of the article, I’ll provide some references in case you feel a bit rusty in this area. I’ll also assume that you’ve read Jeff Lander’s Graphic Content columns on collision detection (“Crashing into the New Year,” ; “When Two Hearts Collide,”; and “Collision Response: Bouncy, Trouncy, Fun,” ). I’ll take a top-down approach to collision detection by first looking at the whole picture and then quickly inspecting the core routines. I’ll discuss collision detection for two types of graphics engines: portal-based and BSP-based engines. Because the geometry in each engine is organized very differently from the other, the techniques for world-object collision detection are very different. The object-object collision detection, for the most part, will be the same for both types of engines, depending upon your current implementation. After we cover polygonal collision detection, we’ll examine how to extend what we’ve learned to curved objects.

     

    / 3 …………………………………………………………………………………………………

    重要的图片

    编写一个最好的碰撞检测例程。我们开始设计并且编写它的基本程序框架,与此同时我们也正在开发着一款游戏的图形管线。要想在工程结束的时候才加入碰撞检测是比较不好的。因为,快速的编写一个碰撞检测会使得游戏开发周期延迟甚至会导致游戏难产。在一个完美的游戏引擎中,碰撞检测应该是精确、有效、而且速度要快。这些意味着碰撞检测必须通过场景几何学的管理途径。蛮力方法是不会工作的 — 因为今天,3D游戏每幀运行时处理的数据量是令人难以置信的。你能想象一个多边形物体的检测时间。

    在一个完美的比赛发动机,碰撞察觉应该是精确, 有效,并且很快的。这些要求意味着那碰撞察觉必须仔细到景色被系住几何学管理管道。禽兽力量方法嬴得’t 工作—今天’s 3D 比赛每框架处理的数据的数量能是介意犹豫。去是你能核对对在景色的每另外的多角形的一个物体的每多角形的时间。

    The Big Picture

    To create an optimal collision detection routine, we have to start planning and creating its basic framework at the same time that we’re developing a game’s graphics pipeline. Adding collision detection near the end of a project is very difficult. Building a quick collision detection hack near the end of a development cycle will probably ruin the whole game because it’ll be impossible to make it efficient. In a perfect game engine, collision detection should be precise, efficient, and very fast. These requirements mean that collision detection has to be tied closely to the scene geometry management pipeline. Brute force methods won’t work — the amount of data that today’s 3D games handle per frame can be mind-boggling. Gone are the times when you could check each polygon of an object against every other polygon in the scene.

     

    / 4 …………………………………………………………………………………………………

    让我们来看看一个游戏的基本循环引擎。(Listing 1)

    http://www.gamasutra.com/features/20000330/bobic_l1.htm

    这 段代码简要的阐明了我们碰撞检测的想法。我们假设碰撞没发生并且更新物体的位置,如果我们发现碰撞发生了,我们移动物体回来并且不允许它通过边界(或删除 它或采取一些另外预防措施)。然而,因为我们不知道物体的先前的位置是否仍然是可得到的,这个假设是太过分简单化的。你必须为这种情况设计一个解决方案 (否则,你将可能经历碰撞而你将被粘住)。如果你是一个细心的玩家,你可能在游戏中会注意到,当你走近一面墙并且试图通过它时,你会看见墙开始动摇。你正 在经历的,是感动运动返回来的效果。动摇是一个粗糙的时间坡度的结果(时间片)。

    Let’s begin by taking a look at a basic game engine loop (Listing 1). A quick scan of this code reveals our strategy for collision detection. We assume that collision has not occurred and update the object’s position. If we find that a collision has occurred, we move the object back and do not allow it to pass the boundary (or destroy it or take some other preventative measure). However, this assumption is too simplistic because we don’t know if the object’s previous position is still available. You’ll have to devise a scheme for what to do in this case (otherwise, you’ll probably experience a crash or you’ll be stuck). If you’re an avid game player, you’ve probably noticed that in some games, the view starts to shake when you approach a wall and try to go through it. What you’re experiencing is the effect of moving the player back. Shaking is the result of a coarse time gradient (time slice).

     

    / 5 …………………………………………………………………………………………………

    但 是我们的方法是有缺陷的。我们忘记在我们的方程中加入时间。图1显示了时间的重要性,因而它不能省去。就算一个物体不在时间 t1 或 t2 抵触,它可以在时间t1 < t < t2穿过t边界哪儿。这是非常正确的,我们已经有大而连续的框架可操作。我们会发现必须还要一个好方法来处理差异。

    But our method is flawed. We forgot to include the time in our equation. Figure 1 shows that time is just too important to leave out. Even if an object doesn’t collide at time t1 or t2, it may cross the boundary at time t where t1 < t < t2. This is especially true when we have large jumps between successive frames (such as when the user hit an afterburner or something like that). We'll have to find a good way to deal with discrepancy as well.

     

    / 6 …………………………………………………………………………………………………

    我们应该将时间作为第4维也加入到所有的计算中去。这些使得计算变得很复杂,然而,我们只能舍弃它们。我们也可从原来的物体在时间 t1 和 t2 之间的占据,然后靠着墙测试结果(图 2 )。

    We could treat time as a fourth dimension and do all of our calculations in 4D. These calculations can get very complex, however, so we’ll stay away from them. We could also create a solid out of the space that the original object occupies between time t1 and t2 and then test the resulting solid against the wall (Figure 2).

     

    / 7 …………………………………………………………………………………………………

    一条简单的途径就是在 2 不同的时间在一个物体的地点附近创造凸壳。这条途径的效率很低并且毫无疑问它会降低你游戏的执行速度。如果不建立凸壳,我们可以在物体附近建立一个范围框。在我们熟悉几种技术后,我们要再次回到这个问题上。

    An easy approach is to create a convex hull around an object’s location at two different times. This approach is very inefficient and will definitely slow down your game. Instead of constructing a convex hull, we could construct a bounding box around the solid. We’ll come back to this problem once we get accustomed to several other techniques.

     

    / 8 …………………………………………………………………………………………………

    另外的途径,它是更容易的实现但是少些精确,是在正中央为交叉的一半和测试细分给的时间间隔。

    另外的途径,其是更容易的实现但是少些精确,是细分在为在midpoint 的交叉的一半和测试的给的时间间隔。这计算能递归地为每个结果的一半返回。这途径将比先前的方法更快,但是它不能保证精确检测所有碰撞的。

    Another approach, which is easier to implement but less accurate, is to subdivide the given time interval in half and test for intersection at the midpoint. This calculation can be done recursively for each resulting half, too. This approach will be faster than the previous methods, but it’s not guaranteed to catch all of the collisions.

     

    / 9 …………………………………………………………………………………………………

    另外的隐藏的问题是 collide_with_other_objects ()例程,它检查一个对象是否在场景内与任何另外的对象交叉。如果我们的场景有很多物体时,这例程会变得更重要。如果我们需要在场景对所有的别的对象检查,我们将粗略地做

    Another hidden problem is the collide_with_other_objects() routine, which checks whether an object intersects any other object in the scene. If we have a lot of objects in the scene, this routine can get very costly. If we have to check each object against all other objects in the scene, we’ll have to make roughly

     

    图三

    (N choose 2 )的比较。因此,我们将要完成的工作就是比较数字的关系N2 (or O(N2))。但是我们能避免施行 O ( N2 )在若干方法之一的对明智的比较。例如,我们能把我们的世界划分成是静止的物体( collidees )并且移动的物体( colliders )的初速度 v=0 。例如,在一个房间里的一面僵硬的墙是一碰撞面和向墙被扔的一个网球球是一碰撞对象。我们能建立一个二叉树(为每个组的一个)给这些对象,并且然后检查哪 个对象确实有碰撞的机会。我们能甚至进一步限制我们的环境以便一些碰撞对象不会与我们没有在 2 颗子弹之间计算碰撞的对方发生抵触,例程。当我们继续前进,这个过程将变得更清楚,为现在,让我们就说它是可能的。(为了减少场景方面数量的另外的方法就 是建立一个八叉树,这已经超出这篇文章的范围,但是你可以在文末参看我给你列出的参考文献)现在让看看基于portal-based引擎的碰撞检测。

    (N choose 2) comparisons. Thus, the number of comparisons that we’ll need to perform is of order N2 (or O(N2)). But we can avoid performing O(N2) pair-wise comparisons in one of several ways. For instance, we can divide our world into objects that are stationary (collidees) and objects that move (colliders) even with a v=0. For example, a rigid wall in a room is a collidee and a tennis ball thrown at the wall is a collider. We can build two spatial trees (one for each group) out of these objects, and then check which objects really have a chance of colliding. We can even restrict our environment further so that some colliders won’t collide with each other — we don’t have to compute collisions between two bullets, for example. This procedure will become more clear as we move on, for now, let’s just say that it’s possible. (Another method for reducing the number of pair-wise comparisons in a scene is to build an octree. This is beyond the scope of this article, but you can read more about octrees in Spatial Data Structures: Quadtree, Octrees and Other Hierarchical Methods, mentioned in the “For Further Info” section at the end of this article.) Now lets take a look at portal-based engines and see why they can be a pain in the neck when it comes to collision detection.

     

    算法六:关于SLG中人物可到达范围计算的想法

    下面的没有经过实践,因此很可能是错误的,觉得有用的初学朋友读一读吧:)

    希望高人指点一二 :)

     

    简介:

    在标准的SLG游戏中,当在一个人物处按下鼠标时,会以人物为中心,向四周生成一个菱形的可移动区范围,如下:

     

      0

     000

    00s00

     000

      0

     

    这个图形在刚开始学习PASCAL时就应该写过一个画图的程序(是否有人怀念?)。那个图形和SLG的扩展路径一样。

     

    一、如何生成路径:

    从人物所在的位置开始,向四周的四个方向扩展,之后的点再进行扩展。即从人物所在的位置从近到远进行扩展(类似广宽优先)。

     

    二、扩展时会遇到的问题:

    1、当扩展到一个点时,人物的移动力没有了。

    2、当扩展的时候遇到了一个障碍点。

    3、当扩展的时候这个结点出了地图。

    4、扩展的时候遇到了一个人物正好站在这个点(与2同?)。

    5、扩展的点已经被扩展过了。当扩展节点的时候,每个节点都是向四周扩展,因此会产生重复的节点。

     

    当 遇到这些问题的时候,我们就不对这些节点处理了。在程序中使用ALLPATH[]数组记录下每一个等扩展的节点,不处理这些问题节点的意思就是不把它们加 入到ALLPATH[]数组中。我们如何去扩展一个结点周围的四个结点,使用这个结点的坐标加上一个偏移量就可以了,方向如下:

     

      3

      0 2

      1

     

    偏移量定义如下:

    int offx[4] = { -1, 0, 1, 0 };

    int offy[4] = { 0, 1, 0, -1 };

     

    扩展一个节点的相邻的四个节点的坐标为:

    for(int i=0; i<4; i )

        temp.x = temp1.x offx[i];

        temp.y = temp1.y offy[i];

    }

     

    三、关于地图的结构:

    1、地图的二维坐标,用于确定每个图块在地图中的位置。

    2、SLG中还要引入一个变量decrease表示人物经过这个图块后他的移动力的减少值。例如,一个人物现在的移动力为CurMP=5,与之相领的图块的decrease=2;这时,如果人物移动到这里,那它的移动力变成CurMP-decrease。

    3、Flag域:宽度优先中好像都有这个变量,有了它,每一个点保证只被扩展一次。防止一个点被扩展多次。(一个点只被扩展一次真的能得到正确的结果吗?)

    4、一个地图上的图块是否可以通过,我们使用了一个Block代表。1---不可以通过;0---可以通过。

     

    这样,我们可以定义一个简单的地图结构数组了:

     

    #define MAP_MAX_WIDTH 50

    #define MAP_MAX_HEIGHT 50

    typedef struct tagTILE{ 

        int x,y,decrease,flag,block;

    }TILE,*LPTILE;

    TILE pMap[MAP_MAX_WIDTH][MAP_MAX_HEIGHT];

     

    以上是顺序数组,是否使用动态的分配更好些?毕竟不能事先知道一个地图的宽、高。

     

    四、关于路径:

    SLG游戏中的扩展路径是一片区域(以人物为中心向四周扩展,当然,当人物移动时路径只有一个)。这些扩展的路径必须要存储起来,所有要有一个好的结构。我定义了一个结构,不是很好:

     

    typedef struct tagNODE{ 

        int x,y;   //扩展路径中的一个点在地图中的坐标。

        int curmp; //人物到了这个点以后的当前的移动力。

    }NODE,*LPNODE;

     

    上面的结构是定义扩展路径中的一个点的结构。扩展路径是点的集合,因此用如下的数组进行定义:

     

    NODE AllPath[PATH_MAX_LENGTH];

     

    其中的PATH_MAX_LENGTH代表扩展路径的点的个数,我们不知道这个扩展的路径中包含多少个点,因此定义一个大一点的数字使这个数组不会产生溢出:

     

    #define PATH_MAX_LENGTH 200

     

    上 面的这个数组很有用处,以后的扩展就靠它来实现,它应该带有两个变量nodecount 代表当前的数组中有多少个点。当然,数组中的点分成两大部分,一部分是已经扩展的结点,存放在数组的前面;另一部分是等扩展的节点,放在数组的后面为什么 会出现已扩展节点和待扩展节点?如下例子:

     

    当前的人物坐标为x,y;移动力为mp。将它存放到AllPath数组中,这时的起始节点为等 扩展的节点。这时我们扩展它的四个方向,对于合法的节点(如没有出地图,也没有障碍......),我们将它们存放入AllPath数组中,这时的新加入 的节点(起始节点的子节点)就是等扩展结点,而起始节点就成了已扩展节点了。下一次再扩展节点的时候,我们不能再扩展起始节点,因为它是已经扩展的节点 了。我们只扩展那几个新加入的节点(待扩展节点),之后的情况以此类推。那么我们如何知道哪些是已经扩展的结点,哪些是等扩展的节点?我们使用另一个变量 cutflag,在这个变量所代表的下标以前的结点是已扩展节点,在它及它之后是待扩展结点。

     

    五、下面是基本框架(只扩展一个人物的可达范围):

     

    int nodecount=0; //AllPath数组中的点的个数(包含待扩展节点和已经扩展的节点

    int cutflag=0; //用于划分已经扩展的节点和待扩展节点

    NODE temp; //路径中的一个点(临时)

    temp.x=pRole[cur]->x; //假设有一个关于人物的类,代表当前的人物

    temp.y=pRole[cur]->y;

    temp.curmp=pRole[cur]->MP; //人物的最大MP

    AllPath[nodecount ]=temp; //起始点入AllPath,此时的起始点为等扩展的节点

     

    while(curflag<nodecount) //数组中还有待扩展的节点

        int n=nodecount; //记录下当前的数组节点的个数。

        for(int i=cutflag;i<nodecount;i ) //遍历待扩展节点

        { 

            for(int j=0;j<4;j ) //向待扩展节点的四周各走一步

            { 

                //取得相邻点的数据

                temp.x=AllPath[i].x offx[j];

                temp.y=AllPath[i].y offy[j];

                temp.curmp=AllPath[i].curmp-pMap[AllPath[i].x][AllPath[i].y].decrease;

    //以下为检测是否为问题点的过程,如果是问题点,不加入AllPath数组,继续处理其它的点

                if(pMap[temp.x][temp.y].block)

                    continue; //有障碍,处理下一个节点

                if(temp.curmp<0)

                    continue; //没有移动力了

                if(temp.x<0||temp.x>=MAP_MAX_WIDTH|| temp.y<0||temp.y>=MAP_MAX_HEIGHT)

                    continue; //出了地图的范围

                if(pMap[temp.x][temp.y].flag)

                    continue; //已经扩展了的结点

                //经过了上面几层的检测,没有问题的节点过滤出来,可以加入AllPath

                AllPath[nodecount]=temp;

            }

            pMap[AllPath[i].x][AllPath[i].y].flag=1; //将已经扩展的节点标记为已扩展节点

        }

        cutflag=n; //将已扩展节点和待扩展节点的分界线下标值移动到新的分界线

    }

    for(int i=0;i<nodecount;i )

        pMap[AllPath[i].x][AllPath[i].y].bFlag=0; //标记为已扩展节点的标记设回为待扩展节点。

    算法七:无限大地图的实现

    这已经不是什么新鲜的东西了,不过现在实在想不到什么好写,而且版面上又异常冷清,我再不说几句就想要倒闭了一样。只好暂且拿这个东西来凑数吧。 

    无限大的地图,听上去非常吸引人。本来人生活的空间就是十分广阔的,人在这么广阔的空间里活动才有一种自由的感觉。游戏中的虚拟世界由于受到计算机存储空间 的限制,要真实地反映这个无限的空间是不可能的。而对这个限制最大的,就是内存的容量了。所以在游戏的空间里,我们一般只能在一个狭小的范围里活动,在一 般的RPG中,从一个场景走到另一个场景,即使两个地方是紧紧相连的,也要有一个场景的切换过程,一般的表现就是画面的淡入淡出。

    这样的场景切换给人一种不连续的感觉(我不知道可不可以把这种称作“蒙太奇”:o)),从城内走到城外还有情可缘,因为有道城墙嘛,但是两个地方明明没有界限, 却偏偏在这一边看不到另外一边,就有点不现实了。当然这并不是毛病,一直以来的RPG都是遵循这个原则,我们(至少是我)已经习惯了这种走路的方式。我在 这里说的仅仅是另外一种看起来更自然一点的走路方式,仅此而已。

    当然要把整个城市的地图一下子装进内存,现在的确是不现实的,每一次只能放一部分,那么应该怎么放才是我们要讨论的问题。

    我们在以前提到Tile方法构造地图时就谈到过Tile的好处之一就是节省内存,这里仍然可以借鉴Tile的思想。我们把整个大地图分成几块,把每一块称作一个区域,在同一时间里,内存中只保存相邻的四块区域。这里每个区域的划分都有一定的要求:

    每个区域大小应该相等这是一定的了,不然判断当前屏幕在哪个区 域中就成了一个非常令人挠头的事;另外每个区域的大小都要大于屏幕的大小,也只有这样才能保证屏幕(就是图中那块半透明的蓝色矩形)在地图上荡来荡去的时 候,最多同时只能覆盖四个区域(象左图中所表示的),内存里也只要保存四个区域就足够了;还有一点要注意的,就是地图上的建筑物(也包括树啦,大石头啦什 么的)必须在一个区域内,这样也是为了画起来方便,当然墙壁——就是那种连续的围墙可以除外,因为墙壁本来就是一段一段拼起来的。 

    我们在程序中可以设定4个指针来分别指向这4个区域,当每次主角移动时,就判断当前滚动的屏幕是否移出了这四个区域,如果移出了这四个区域,那么就废弃两个 (或三个)已经在目前的四个相邻区域中被滚出去的区域(说得很别扭,各位见谅),读入两个(或三个)新滚进来的区域,并重新组织指针。这里并不涉及内存区 域的拷贝。

     

    这样的区域划分方法刚好适合我们以前提到的Tile排列方法,只要每个区域横向Tile的个数是个偶数就行了,这样相邻的两个 区域拼接起来刚好严丝合缝,而且每个区域块的结构完全一致,没有那些需要重复保存的Tile(这个我想我不需要再画图说明了,大家自己随便画个草图就看得 出来了)。在文件中的保存方法就是按一个个区域分别保存,这样在读取区域数据时就可以直接作为一整块读入,也简化了程序。另外还有个细节就是,我们的整个 地图可能不是一个规则的矩形,可能有些地方是无法达到的,如右图所示,背景是黑色的部分代表人物不能达到的地方。那么在整个地图中,这一部分区域(在图中 蓝色的3号区域)就可以省略,表现在文件存储上就是实际上不存储这一部分区域,这样可以节省下不少存储空间。对于这种地图可以用一个稀疏矩阵来存储,大家 也可以发挥自己的才智用其他对于编程来说更方便的形式来存储地图。  

     

    这就是对无限大地图实现的一种方法,欢迎大家提出更好的方法。也希望整个版面能够活跃一点。

    Ogre中的碰撞检测

    Ogre采用树桩管理场景中的各种"元素"(摄像机、灯光、物体等),所有的东西都挂在"树"上,不在"树"上的东西不会被渲染。

    Ogre::SceneManager就是"树"的管理者,Ogre::SceneNode是从SceneManager中创建的(当然BSP和8*树的管理也和这两个类有关,这暂时不讨论)。

    AABB(轴对齐包围盒)

    这个东西是碰撞检测的基础(怎么总想起JJYY呢),和它类似的还有OBB(有向包围盒),由于OBB创建复杂,所以Ogre采用了AABB。

    最简单的碰撞检测:

    通过Ogre::SceneNode::_getWorldAABB()可以取得这个叶子节点的AABB(Ogre::AxisAlignedBox), Ogre::AxisAlignedBox封装了对AABB的支持,该类的成员函数Ogre::AxisAlignedBox::intersects ()可以判断一个AABB和"球体、点、面以及其他面"的相交情况(碰撞情况)。

        m_SphereNode树的叶子,挂了一个"球"

        m_CubeNode树的叶子,挂了一个"正方体"

        AxisAlignedBox spbox=m_SphereNode->_getWorldAABB();

    AxisAlignedBox cbbox=m_CubeNode->_getWorldAABB();

    if(spbox.intersects(cbbox))

    {

         //相交

    }

    区域查询:

    简单的讲就是,查询某一区域中有什么东西,分为AABB、球体、面查询。

       //创建一个球体查询,这里的100是m_SphereNode挂着的那个球体的半径

       SphereSceneQuery * pQuery=m_SceneMgr->createSphereQuery(Sphere(m_SphereNode->getPosition(),100));

       //执行这个查询

       SceneQueryResult QResult=pQuery->execute();

       //遍历查询列表找出范围内的物体

       for (std::list<MovableObject*>::iterator iter = QResult.movables.begin(); iter != QResult.movables.end();++iter)

       {

        MovableObject* pObject=static_cast<MovableObject*>(*iter);

        if(pObject)

        {

         if(pObject->getMovableType()=="Entity")

         {

          Entity* ent = static_cast<Entity*>(pObject);

          //这里简化了操作,由于只有一个"球体"和一个"正方体",

          //所以只判断了球体和正方体的相交

          if(ent->getName()=="cube")

          {

           //改变位置防止物体重叠

           vtl=-vtl;

           m_SphereNode->translate(vtl);

           break;

          }

         }

        }

       }

    相交查询

    遍历所有的对象,找到一对一对的相交物体(废话呀,相交当然至少两个物体)。

        //创建相交检测

        IntersectionSceneQuery* pISQuery=m_SceneMgr->createIntersectionQuery();

        //执行查询

        IntersectionSceneQueryResult QResult=pISQuery->execute();

        //遍历查询列表找出两个相交的物体

        for (SceneQueryMovableIntersectionList::iterator iter = QResult.movables2movables.begin();

         iter != QResult.movables2movables.end();++iter)

        {

         

         SceneQueryMovableObjectPair pObject=static_cast<SceneQueryMovableObjectPair>(*iter);

         //if(pObject)

         {

          String strFirst=pObject.first->getName();

          String strSecond=pObject.second->getName();

          //下面加入你自己的两个物体相交判断代码,或者简单的用AABB的判断方法,

         }

        }

     

    展开全文
  • 【H5/JS】游戏常用算法-追踪算法

    千次阅读 2018-06-09 20:48:10
    追踪算法在动作游戏中非常常见,从很早的游戏《吃豆人》到大型的街机机战类游戏,到处可见追踪效果的身影。一个好的追踪算法将会大大提高游戏的可玩性和玩家的兴趣。【简单算法】先来看一个简单的跟踪算法,如下图所...
  • 游戏开发常用算法概述

    千次阅读 2014-10-21 23:37:38
    游戏开发属于软件开发中的一种,但又是...下面是我收集的一些常用算法、设计模式及变成思想,欢迎拍砖和补充。 一 算法 1 随机数 常用于抽装备,暴击,闪避等 2 最短路径 用于地图中寻找到达指定位置的最短路径,dota
  • 游戏开发中会用到哪些常用AI算法

    千次阅读 2017-02-16 08:45:43
    游戏开发中会用到哪些常用AI算法 “人工智能”(Artificial Intelligence)简称AI,在游戏里是必不可缺的, 请教一般在哪些地方会使用什么样的AI算法,比如寻路、战斗等等。   游戏编程中的寻路算法 在...
  • 游戏常用算法1-视线追踪算法

    千次阅读 2014-07-09 22:21:18
    游戏常用算法1-视线追踪算法游戏中我们常常看到这样一种情况,敌人死死盯着目标不放。如在《三国无双》中,当角色进入敌人的领地之后,敌人就会想你奔袭而来,拦也拦不住。这是怎么做到的呢。有一种简答的算法是...
  • 游戏开发常用算法

    千次阅读 2014-04-27 00:23:17
    算法是程序设计的精髓,程序设计的实质就是构造解决问题的算法,将其解释为计算机语言。 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计算机解题的过程。在这个过程中,无论是形成...
  • 手机游戏开发常用排序算法

    千次阅读 2012-06-12 11:14:57
    If NoSwap Then Return//本趟排序中未发生交换,则终止算法// end End; //BubbleSort// 四、快速排序(Quick Sort) 1. 基本思想:  在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"...
  • 游戏中的常用算法

    千次阅读 2015-09-10 09:48:38
    一,递归 计算阶乘 int fun(int n) { ...二,A*自动寻路算法 劣势:有一定的局限性,可能不会是最优路线 先把一块区域分成小网格 f =g+h 寻路总消耗 g=从起点到当前位置(其中一个网格)的消耗 h=从当
  • 路径搜索算法游戏中非常常见,特别是在 RPG、SLG 中经常用到。在这些游戏中,通过鼠标指定行走目的地,人物或者NPC就会自动行走到目标地点,这就是通过路径搜索或者称为寻路算法来实现的。通俗地说,就是在...
  • 游戏常用的伪随机算法之PRD暴击算法 PRD伪随机算法常用于游戏中的暴击算法,因此本文的标题将其称为 PRD暴击算法。 诞生与应用 PRD算法诞生与《魔兽争霸3》,可以说其诞生就是为了解决游戏中暴击概率所存在的问题...
  • 游戏开发常用算法1

    千次阅读 2012-06-12 11:12:19
    要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序的数据结构和变量用来描述问题的对象,...
  • 游戏常用加密压缩算法 日本游戏常用加密压缩算法 程序破解员: 分析游戏的加密方式,能写基本的文件解包工具和打包工具,能对加了密的游戏文本进行抽取,还原并进行编辑。 懂得汇编和反汇编以及一门...
  • 所谓迷宫生成算法,就是用以生成随机的迷宫的算法 迷宫生成算法是处于这样一个场景: 一个row行,col列的网格地图,一开始默认所有网格四周的墙是封闭的 要求在网格地图边缘,也就是网格的边上打通2面墙 ...
  • 游戏开发常用算法2

    千次阅读 2012-06-12 11:13:37
    算法依次将物品放到它第一个能放进去的箱子中,该算法虽不能保证找到最优解,但还 是能找到非常好的解。不失一般性,设n件物品的体积是按从大到小排好序的,即有v0≥v1≥…≥vn-1。如不满足上述要求,只要先对这n...
  • 日本游戏常用加密压缩算法

    千次阅读 2009-09-01 17:32:00
    懂得一些常见的压缩算法(如:LZ777,ZLIB等)日本的游戏不管是PC还是掌机都会因为版权的问题将除去游戏框架以外的资源文件单独归档加密存储我们讨论 最常见的 最简单日本游戏常用的压缩和加密算法这里不是密码学/...
  • 除非是在极为特殊的情况下,要求使用非常精确的碰撞,否则,一般情况下在游戏中是不建议使用这种算法,特别是在运行效率不太高的HTML5游戏中。一般来说在使用像素碰撞检测之前会使用AABB矩形包围盒先检测两个精灵...
  • 这种算法经常用于RPG(早期的《最终幻想》、《DQ》、《仙剑奇侠传》)、SLG(《炎龙骑士团》、《超级机器人大战》)、PUZ(《俄罗斯方块》、《宝石谜阵》)类型的游戏。这类游戏中,通常情况下整个地图都是由一些...
  • RPGViewer - 游戏常用压缩算法的介绍和识别

    万次阅读 热门讨论 2008-02-25 11:26:00
    deflatehttp://www.zlib.net/这是ZIP默认采用的压缩...很多国外游戏的档案都采用这种压缩算法,或者直接使用ZIP文件格式存储资源。目前不少国内厂商也开始采用deflate。默认ZIP使用的deflate,传入的WindowBits是-0x
  • 常用CG算法

    千次阅读 2009-08-07 09:18:40
    追踪root对象算法: 深度追踪root对象,将heap中所有被引用到的root做标志,所有未被标志的对象视为非活动对象,所占用的空间视为非活动内存。 2)清理非活动对象 Copy算法: 方法:将内存分为两个区域(from ...
  • Java实现游戏抽奖算法

    万次阅读 多人点赞 2017-07-24 08:36:00
    常用抽奖算法对比基础的游戏抽奖算法通常要求实现在指定奖品的集合中,每个奖品根据对对应概率进行抽取。个人了解的主要有以下几中抽奖算法
  • ACM常用经典算法

    千次阅读 2016-07-29 20:03:12
    排序算法(平方排序算法的应用,Shell排序,快速排序,归并排序,时间复杂度下界,三种线性时间排 序,外部排序)   数论(整除,集合论,关系,素数,进位制,辗转相除,扩展的辗转相除,同余运算,解线性同...
  • 常用算法原理

    千次阅读 2016-06-01 13:23:25
    回溯法正是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法。 回溯法首先将问题 P 的 n 元组的状态空间 E 表示成一棵高为 n 的带权有序树 T ,把在 E 中求问题 P 的所有解转化为在 T ...
  • 常用算法 二分查找算法(非递归)分治问题 在工作和生活中, 我们经常会遇到很多算法. 但是不同于我们之前学习的数据结构与算法, 他们更具目的性, 更加贴合我们工作需要. 下面, 就让我们一起来学习吧! 二分查找算法...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,713
精华内容 21,885
关键字:

常用游戏算法