用cocos2d-x制作连连看
最近一段在看cocos2d-x。就做个连连看练手。
难度主要是是算法实现。
最开始想用bfs，后来发现最短路径的转弯个数不一定是最小的。
然后就用dfs了，设置两个变量turn_num，step_num标记转弯个数和步数进行剪枝，算法效率还是挺快的。
没有去用二维数组存取位置信息，为了方便只是用个CCArray存储，影响不大。
Cell类：
class Cell : public CCNode{public :Cell(int xx,int yy,int tt,Cell* turnPoint,CCSprite* cellImage,char str[]);~Cell();int x,y;//坐标int t;//拐点个数char str[20];//图片标识bool is_remove; Cell* preturn;//上一个拐点public :CCSprite* cell_image;};void GameLayer::link_dfs(bool** vis,Cell* start,Cell* end){static int step =0;if(start->t>turn_num) return;//如果大于2个弯直接退出if(step>step_num) return; //如果步数大于之前的步数说明不是最优解 直接跳出if(start->x==end->x && start->y==end->y){is_link=true;step_num=MIN(step,step_num);//获取最优解turn_num=MIN(start->t,turn_num);getPath(start);//debugPath(start);//路径信息//debugTurns(start);//拐点信息}else{for(int i=0;i<4;i++)//四个方向{int xx=start->x+dir[i][0];int yy=start->y+dir[i][1];//在范围内且没有被访问过或者未被阻挡if(xx>=0 && xx<=ROW+1 && yy>=0 && yy<=COL+1 &&!vis[xx][yy]){Cell* temp=new Cell(xx,yy,start->t,start->preturn,NULL,"");//起始点的转弯点为空if(start->preturn==NULL){temp->preturn=start;}//如果横坐标纵坐标都和上一个拐点的坐标不一致 该点是拐点 else if(start->preturn->x!=xx && start->preturn->y!=yy){temp->t+=1;//拐点个数+1temp->preturn=start;}vis[xx][yy]=true;//被访问step++;//步数+1link_dfs(vis,temp,end);vis[xx][yy]=false;//恢复step--;//恢复}}}}源码下载地址：连连看