一个类似连连看游戏
首页图片
f02fc924b899a90156819c501e950a7b0308f5c4.jpg
效果GIF##
2016-08-12 21_34_01.gif
2016-08-12 21_36_08.gif
连连看消除算法##
CCB5EC28-4F2E-41E5-A199-20EEF0FDD02A.png
总体算法的核心思想就如同上面图所示
找AB两点是否能消除，我们只用看A，B两点的纵轴/横轴上能到达的点是否能分别连通，灰色标示障碍，那么A，B两点沿轴向（蓝色箭头）能连通的区域标示为粉色，而红色箭头标示横轴能连通。所以上面符合规则的连通路径有3条（3个红色箭头标示）。上图是纵向搜索，横向搜索类同。
以纵轴搜索为例：
我们需要取A，B沿着纵轴能到点的纵坐标的交集G，再来判断分别以A,B为横坐标（纵坐标在G）的点是否连通，如上图中 A能到纵向点集[1,7] ,B能到纵向点集[3,7],则交集[3,7]，我们搜索点 (E,3)和(G,3) , (E,4)和(G,4) , (E,5)和(G,5) , (E,6)和(G,6) ，(E,7)和(G,7) 是否直线连通，(E,3)和(G,3)，(E,4)和(G,4)不连通，其余都连通，所以我们找到3条路径.
//元素
struct ele {
int x;
int y;
int q;
ele(int _x , int _y ,int _q){
x = _x;
y = _y;
q = _q;
}
};
typedef ele* ele_p;
bool isPath(ele_p s , ele_p d); //两元素是否直线连通
int pathToIndex(ele_p e , int type); //元素能沿着轴向能延伸的最大索引.
list<int> *startCheck(ele_p s , ele_p e); //.
D5EFB3AB-616C-45F3-9639-27DCE6DCCCD4.png
在练练看游戏中，我们只用找到一条合适的路径就可以了，然而我们应该优化算法找到一条折线尽量少，路径尽量短的路径，上图中，如果纵坐标集合[3,7]顺序搜索，找到的第一条路径应该是A,(E,5),(G,5),B,然而最优路径并不是这条，而是A,(G,6),B,这条路径只是折了一次。(如下图),所以我们重新设计搜索方式。
76BF13A7-1249-4495-9EDC-8B828E6EFDBA.png
上图很清晰的列出了所有的情况，蓝色标示交集G的范围。按照上图的搜索方式，我们会找到一个最优得路径。
下面给出一 伪代码
# s,e是两个节点 ， f,b代表G集合的上下限, paths是一个list指针的指针 ，后面会说明为啥用list保存 #
searchPathByY(ele_p s , ele_p e , int f , int b , list<int> **paths){
list<int> *elePath = new list<int>;
// 确定s和e的位置
ele_p front = s和e中纵坐标小的;
ele_p back = s和e中纵坐标大得;
int middle = 0;
//确定搜索中点；
if (front->y >= f) {
if (back->y <= b) {
//search from middle of frontAndBack
middle = (front->y+back->y)/2;
}else{
middle = front->y;
}
}else{
if (back->y >= b) {
// search from middle of frontAndBack
middle = (f+b)/2;
}else{
// search from middle of back
middle = back->y;
}
}
int middleOffset = 0;
while (点在集合G中) {
// 搜索偏离+-middleOffset的点
if(两点存在直线路径){
将和front横坐标相等的点push_front。
将和back横坐标相等的点push_back。
}
middleOffset++;
}
//没搜索到路径，返回false
if (elePath->empty()) {
delete elePath;
return false;
}
if (front和list.push_front不是一个点) {
将front点push_front到elePath;
}
if (back和list.push_back不是一个点) {
将back点push_back到elePath;
}
if (s和front不是一个点) {
对elePath做reverse；
}
*paths = elePath;
return true;
}
上面是纵轴搜索的情况，横轴搜索的情况和上面类似。paths里面就会存有有效路径了，如果为空则表示不存在路径。
简单框架##
E6CF42F7-235A-4773-8B33-1EFBC811F09A.png
@protocol LLKViewDataSource <NSObject>
-(int)getTypeOfRow:(int)row andCol:(int)col;
-(NSArray *)checkPathOne:(int)point1 andOther:(int)point2;
-(void)endGame;
-(NSArray *)generateNew;
@end
llkView是整个游戏的界面。接受点击事件，然后通过(NSArray *)checkPathOne:(int)point1 andOther:(int)point2 把点击的索引交给控制器，控制器转发给llk对象进行处理，看是否能消除，并且将数据返回给LLKVIew进行处理。
另外一方面，通过定时器每隔一段时间通过-(NSArray *)generateNew;方法产生新节点，然后LLKVIew更新。
让产生新节点的权值不同
D9D75D0F-ADFA-49A6-99F0-2775B6A69DA2.png
在初始化游戏的时候 希望平均的分配每一个权值的数量，并且让所有的权值都成对的出现，并且产生一定数量的空节点。
我的做法是，先把权值平均分配到所有的节点中 ，然后成对的产生空节点，并且将替换成空节点的权值存入vector<int> emptyEle容器中，
当产生消除时候，一定会有两个相同权值加入到emptyEle中，然而我们产生的时候并不希望产生相同权值，所以在我们放入权值的时候我们一头一尾的放入，拿得时候从头拿两个，这样就能避免拿出两个权值相等的了。
C++对象的释放##
由于ARC不能对C++对象进行管理，然而delloc方法也不能手动调用，所以采用runtime机制调换成自己的delloc方法手动的把c++对象释放了。
+ (void)load
{
static dispatch_once_t token;
dispatch_once(&token, ^{
const char *orignSelName = "dealloc";
SEL orignSelector = sel_registerName(orignSelName);
const char *newSelName = "deallocWithC";
SEL newSelector = sel_registerName(newSelName);
Method originM = class_getInstanceMethod([self class], orignSelector);
Method newM = class_getInstanceMethod([self class], newSelector);
if (class_addMethod([self class], orignSelector, method_getImplementation(newM), method_getTypeEncoding(newM)))
{
class_replaceMethod([self class], newSelector, method_getImplementation(originM), method_getTypeEncoding(originM));
}
else
{
method_exchangeImplementations(originM, newM);
}
});
}
-(void)deallocWithC{
delete myllk;
[self deallocWithC];
}
大概框架就是这样，还有一些细节没做怎么好,代码放在https://github.com/lvjiaqijiaqi/llk_byLjq
