游戏制作入门...从一个简单的连连看游戏开始(一)..连连看游戏 ，只要将相同花色的两张牌用三根以内的直线连在一起就可以消除， 规则简单容易上手 . 简单点说就是从一张牌到另一张牌之间的连线..最多只能拐两个弯...[attach]719961[/attach]OK..知道了规则..那我们现在当然就可以来实现它.. 首先我们不考虑界面啊..特效啊..什么什么的..我们就单纯的来看一下下面这个 matrix0 0 0 0 0 00 1 2 3 4 00 0 0 0 0 00 0 0 0 0 00 2 4 3 1 00 0 0 0 0 0我们可以把它看成一个简易的4*4 连连看地图..,为什么是4*4而不是6*6?因为最外面的一圈0是代表 外围空间..连连看的规则规定能从外围连线..我们对中间4*4的matrix编个号••比如第一行第一个就是(1,1)••一次类推••里 面 有 4 种 花 色 (1,2,3,4) 的 八 张 牌 ( 上 下 各 四 张 , 分 别 处 于 (1,1),(1,2),(1,3),(1,4),(4,1),(4,2),(4,3),(4,4)) 怎么样来确定任意两张牌之间是不是能消去呢?首先..他们的花色必须要相同... 比如说如果用户点击(1,1)和(4,1)这两个位置时..这是立即能判断出不能消去的..好..如果点击的是(1,1)和(4,4)呢?这两个位置的花色是相同..那怎么知道这两个位置之间的连线是否符合 游戏规则呢?大家好好想想...如果把这个问题抽象为一个图的模型••那么问题转化为在这个无向图G中••如果确定两点 之间是否连通..且组成路径的直线不超过三根..(也就是不转两个以上的弯..)我们分开来看这个问题••说到图的连通性••大家能想到什么算法？BFS..DFS. •这是最容易想到的.. 好吧•那我们就挑一个••从BFS入手吧••(事实上解决这题两种方法都行..BFS更简单一点••)不知道对BFS大家还记得多少..BFS除了可以用来求图的连通性..还能用来求等步长的图中两点的最短距 离..(其实稍作一下变化..就变成大家熟悉的 Dijkstra 算法,即单源最短路径).如果我们直接对这题用 BFS..会怎么样？我们可以得到这两张牌之间是否连通..即能不能连线..这是游戏很 必要的条件..如果两张牌之间不连通..那自然不能消去..第一个问题我们已经解决了..那怎么解决第二个问 题？很简单••在BFS里面加上限制条件就0K 了…在普通的BFS里••我们都会设一个布尔标志数组..sign..来 判断某一结点是否已扩展过了••现在我们动动手脚••把sign改为int型••将它初试化为-1,它的意思也要改 变下..它不再代表是否已经访问过..而代表在以前经过扩展到这个点时所需的最小拐弯数 大家想一想. 为什么要保存最小?至此问题已经迎刃而解..当整个 BFS 进行完后..我们检查目标点的 sign 数组值..如果发现其中的值为-1, 那么就代表这两个点不连通 ..如果发现值 >2.那么就代表这两个点之间不存在一条符合规则的路线 ()..如 果小于等于2..则返回 true..好了到此为止...连连看的后台程序就写好了 ..当然我上面说的这个算法..还有很大的优化余地..可以加一 些剪枝条件••那样在第一次找到目标点时就能判断好••而不用等到BFS结束..好了下面附上我的BFS代码..[code]#include #include using namespace std;const short dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};struct point{short x,y;char last,corner;};int sx,sy,gx,gy;int n,m;int map[1010][1010];char sign[1010][1010];bool bfs(){if (sx==gx&&sy==gy) return false;memset(sign,-1,sizeof(sign));queue l;point t={sx,sy,-1,0};l.push(t);int h=0,r=1,tmp=1;while(!l.empty()){point temp=l.front();l.pop();for (int i=0;i<4;++i){int cx=temp.x+dir[i][0],cy=temp.y+dir[i][1];if (cx<1||cx>n||cy<1||cy>m) continue;if (temp.last!=-1) tmp=dir[temp.last][0]*dir[i][0]+dir[temp.last][1]*dir[i][1];if (tmp==-1) continue;int cor=temp.corner;if (tmp==0) cor++;if (cor>2) continue;if (cx==gx&&cy==gy) return true;if (cor==2){if (cx!=gx&&cy!=gy) continue;if (cx==gx&&(i==0||i==1)) continue;if (cy==gy&&(i==2||i==3)) continue;}if (map[cx][cy]!=0) continue;if (sign[cx][cy]!=-1&&cor>sign[cx][cy]) continue; sign[cx][cy]=cor;point tt={cx,cy,i,cor};l.push(tt);}}return false;}int main(){while(scanf(\"%d%d\",&n,&m),n&&m){for (int i=0;i