连连看寻路算法

阅读： 评论：0

主题：[讨论]连连看寻路算法/全程求解算法

作者：华山论剑     平板显示 发表时间：2007-11-28 17:51:00 楼主  遇到一个算法问题，希望朋友们多给些意见。 最近SDK写了个连连看游戏，其中的两点间寻路的算法基本上是用网上的一段代码，全路径求解算法则是自己写的，遇到容易的矩阵可以秒杀，但遇到复杂的则速度就很慢了。希望大家给些意见，改善一下效率。 先说全程求解部分。 说明： 1、如果有解，出解法； 2、如果无解，给出相对最佳路径； 3、如果有多解，到一个就退出； 4、连连看的矩阵为10*12(10行，每行12张牌)，加上上下左右要各留一空行以便寻路，矩阵为12*14； 5、矩阵中某点值为0表示无牌，否则有牌； 6、矩阵不一定是初始状态，因为有时我们玩到一半可能用软件来求解。 例子数组： m[12][14] = { 0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,    0,   29,  3,   18,  26,  9,   2,   6,   33,  10,  9,   4,   15,  0,    0,   19,  18,  29,  7,   14,  9,   10,  23,  34,  16,  21,  15,  0,    0,   21,  27,  26,  2,   26,  11,  30,  17,  25,  14,  10,  5,   0,    0,   19,  12,  33,  33,  31,  34,  15,  11,  28,  7,   8,   23,  0,    0,   12,  16,  27,  4,   5,   21,  27,  8,   1,   6,   23,  4,   0,    0,   19,  34,  25,  1,   6,   26,  25,  15,  17,  12,  6,   31,  0,    0,   10,  4,   16,  17,  31,  8,   8,   7,   28,  28,  34,  30,  0,    0,   3,   21,  5,   14,  18,  2,   12,  20,  20,  2,   25,  1,   0,    0,   30,  20,  19,  31,  3,   9,   14,  16,  5,   29,  33,  3,   0,    0,   1,   20,  11,  27,  28,  17,  30,  18,  7,   29,  11,  23,  0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0   }   这个数组也许是无解的，如果无解，则给出相对最好的解法。 基本流程： 1、    复制矩阵和路径数组为m和way； 2、    先一个有牌点p1； 3、    然后其它几个配对的点same[N]； 4、    依次检查p1和same[N]中的元素是否相通； 5、    若相通则消去两张牌，若消完则返回； 6、    没消完再递归寻路。

作者：机床罩壳雨中飞燕      发表时间：2007-11-28 17:54:00 　第1楼手机受话器  那个叫回溯嘛。。。。

作者：华山论剑      发表时间：2007-11-28 17:56:00 　第2楼  下面是代码： typedef struct {     int真空度传感器 m[12][14];     point way[60][4]; }llk; int least_left;                    //最少剩牌数，用于无解时保存最好解法 point shortest_way[60][4];         //相对最好解法路径 int find_same(point p, point same[], const int m[][14]) {                                  //相同的点     int i, j;     int num = 0;     for (i=1; i<row-1; ++i)         for (j=1; j<col-1; ++j)         {             if ( m[i][j]==m[p.x][p.y] &&                  (i!=p.x||j!=p.y) )             {                 same[num].x     = i;                 same[num++].y = j;             }            }     return 川口成型机炮筒原理num; } BOOL find_way(llk       *v,        //llk结构               int       left,      //剩下牌张               const int in[][14],  //矩阵               point     wayin[][4]);//全程求解路径 {     int i, j, k;                   //循环变量     int m[12][14];                 //矩阵复制品     int num, idx;                  //对于一个点，有几个相同的     int old;                       //保存旧值     point way[60][4], same[10];    //路径，相同点的坐标数组     point p;                       //要配对的点     if (least_left==0)         return TRUE;     idx = (120 - left) / 2;        //路径中要更新的位置索引     memcpy(m, in, sizeof(m));      //矩阵复制品     memcpy(way, wayin, sizeof(way));//路径复制品     for (i=1; i<row-1 && least_left; ++i)         for (j=1; j<col-1 && least_left; ++j)     //缩进太多，将之提前------------num1     if (m[i][j] && least_left)     //到有牌点     {         p.x = i;         p.y = j;         num = find_same(p, same, m);         //缩进太多，将之提前------------num2     for (k=0; k<num && least_left; ++k)//路     {         way[idx][0].x = i;         way[idx][0].y = j;         way[idx][3].x = same[k].x;         way[idx][3].y = same[k].y;         if (check_way(way[idx], m))//check_way是两点间寻路函数         {             if (left==2)           //最后的牌清空了             {                 least_left = 0;                 save_sol(v, way);                 return TRUE;             }             else             {                 if (left-2<least_left)//保存最短路径                 {                     least_left = left - 2;                     memcpy(shortest_way, way, sizeof(way));                 }                             old = m[i][j];     //保存旧值                 m[i][j] = m[same[k].x][same[k].y] = 0;                                       //消去2张牌                 find_way(v, left - 2, m, way);                                    //递归寻路                 tek-081if (least_left==0) //只要到一个，从所有的递归中退出                     return TRUE;                 m[i][j] = m[same[k].x][same[k].y] = old;                                       //恢复2张牌                 ZeroMemory((void*)&way[idx], sizeof(way[0]));                                    //恢复路径最后一维(置0)             }         }     }//-----------------------------num2结束     }//-----------------------------num1结束     return FALSE; } 但是配合两点间的寻路函数，效率不高，像上面的例子数组，算一个晚上也没结果。希望朋友们参考参考，能不能优化优化，最好代码也能简化些，解决了外层的，再来解决两点寻路算法。

本文发布于:2023-05-18 16:23:03，感谢您对本站的认可！

本文链接：https://patent.en369.cn/patent/2/104242.html

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。

上一篇：unity自带寻路Navmesh入门教程，带鼠标点击。

下一篇：【Unity3D】自动寻路系统Navigation实现人物上楼梯、走斜坡、攀爬、跳跃

标签：路径   寻路   算法   矩阵   求解   数组   希望