开发者社区> eddie小英俊> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

原因好消息: 自己主动算法设计推箱子游戏(三)

简介:
+关注继续查看

在本节中,我们谈论的闭合曲线充满,为什么这件事情

当一个场景,当我们递归,我们推标箱,假设没有推箱子。然后跑到哪里都白跑。最好是反复出现歧视坐标都是一样的

这些坐标被反转包含(同样的排序结果)。工的位置(求解算法部分再具体说)


因为场景有多个箱子,每一个箱子能够有几个方向移动。重复的寻路效率不高。起初我想删除路径部分,仅仅检測是否能移动到目标

来提升运行效率,就是偷懒一下,然后想想既然是礼物,偷懒也不是分时候,也有脸献给别人于是废弃了A×算法


目的就非常明显了。标定全部能到达的位置。检測的时候就不用寻他妹的路了,直接检測是否被填充就可以


那么怎样填充一个闭合的曲线呢?最简单的逻辑是:

1.往周围4个或8个方向,记录全部不是边界。没被填充的点并填充

2.递归这些点,直到没有新的点被检測到


递归,又是递归。这是自交么?罪过啊!

万恶的递归,可怜的堆栈……


上面的方法实现非常easy,只是有非常多点会被重复检測若干次,效率并不太高

第二种方法就是我们要说的:扫描线种子填充算法

主要逻辑思想是:

1.把坐标换成线段,记录最左和最右断点。填充线段,增加队列(取代递归)

2.填充最先增加队列的线段,检查上一行和下一行,把相邻的线段都加进来,从队列中删除

3.反复1-2直到队列没有不论什么线段


演示样例源码,详情见资源

// 扫描线填充(用循环代替递归, 玩家必须在边界封闭的曲线内)
int fnStageScan(PQUEUE pQueue, PSTAGE pStage)
{
	UINT x0, xl, xr, y0, xid;
	UINT flag;	//, c
	PSTACK s;
	PSTAR p;
	//UINT sNum;

	union {
		UINT *pData;
		BYTE *pNum;
	};
	UINT X, Y;
	int i;

	// 首先清零非类型位
	Y = pStage->SizeX * pStage->SizeY;
	X = Y % 4;
	pNum = pStage->Matrix;
	while(X--)
	{
		*pNum++ &= SMT_FILTER;	// 清零非类型信息
	}
	Y /= 4;
	while(Y--)
	{
		*pData++ &= SMT_MATRIX;	// 清零非类型信息
	}
	// 清空堆栈, 种子入栈
	s = pQueue->Stacks;
	p = s->Stars;
	p->X = pStage->PosX;
	p->Y = pStage->PosY;
	s->Count = 1;
    while(s->Count)
	{
        X = p->X;
        Y = p->Y;
		p--;
		s->Count--;
		pNum = &pStage->Matrix[Y * pStage->SizeX + X];
		*pNum |= SMT_OPENED;	// Me.PSet (x0, Y), newvalue
        x0 = X + 1;
		pNum++;
        // 填充右边不是箱子也不是边界的单元
        while((*pNum & SMT_MASKED) == 0)	// Me.Point(x0, Y) <> boundaryvalue
		{
			//if(x0 >= pStage->SizeX) break;	// 到最右边(地图控制)
            *pNum |= SMT_OPENED;
			pNum++;
            x0++;
		}
        xr = x0 - 1;	// 最右坐标
        x0 = X - 1;
		pNum = &pStage->Matrix[Y * pStage->SizeX + x0];
        // 填充左边不是箱子也不是边界的单元
        while((*pNum & SMT_MASKED) == 0)	// Me.Point(x0, Y) <> boundaryvalue
		{
			//if(x0 < 0) break;	// 到最左边(地图控制)
            *pNum |= SMT_OPENED;
			pNum--;
            x0--;
		}
        xl = x0 + 1;	// 最左象素
        // 检查上一条扫描线和下一条扫描线。若存在非边界且未填充的象素。则选代替表各连续区间的种子象素入栈。
        y0 = Y;
        for(i = 1; i >= -1; i -= 2)
		{
            x0 = xr;
            Y = y0 + i;
            while(x0 >= xl)
			{
                flag = 0;	// 向左传递未填充的点直到边界, 记录最后一个点的X坐标
                pNum = &pStage->Matrix[Y * pStage->SizeX + x0];		// c = Me.Point(x0, Y)
                //while(((*pNum & SMT_MASKED) == 0) && ((*pNum & SMT_OPENED) == 0) && (x0 >= xl))
				while(((*pNum & SMT_OPNMSK) == 0) && (x0 >= xl))
				{
					// (c <> boundaryvalue) And (c <> newvalue) And (x0 >= xl)
                    if(flag == 0)
					{
                        flag = 1;
                        xid = x0;
					}
					pNum--;	// c = Me.Point(x0, Y)
                    x0--;
				}
                // 将最右側可填充象素压入栈中
                if(flag == 1)
				{
					p++;
					p->X = xid;
					p->Y = Y;
					s->Count++;	// s.push(Point(xid,y));
                    flag = 0;
				}
                // 检查当前填充行是否被中断。若被中断,寻找左方第一个可填充象素
                pNum = &pStage->Matrix[Y * pStage->SizeX + x0];		// c = Me.Point(x0, Y)
                while(*pNum & SMT_OPNMSK)
				{
					// (c = boundaryvalue) Or (c = newvalue) '推断当前点是否为边界或箱子 或 推断当前点是否为已填充点
					if(x0 == 0) break;	// 到最左边(...)
                    pNum--;
                    x0--;	// 若当前点为边界点或已填充点。依据前面的推断,当前点必定未超出左边界。则当前点向左移动
                }
			}	// loop while(x0 >= xl)
		}	// next for(i = 1; i >= -1; i -= 2)
	}	// loop while(!s.isempty())
	return 1;
}

为了存储空间,我仅仅填充特定标志位,队列固定大小,结构更加紧凑,測试运行效果:

左边画线的端点。一个充满完全随机的内右键点击一个封闭的曲线上的点。请参阅资源工具包。

版权声明:本文博客原创文章,博客,未经同意,不得转载。







本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/4748919.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
复刻经典童年游戏扫雷之运营大大们来捉迷藏了
复刻经典童年游戏扫雷之运营大大们来捉迷藏了
0 0
关于泡泡龙游戏的一点儿总结,以及分享一个好方法
不少人都问过这样的一个问题:你做一个游戏需要多长时间?通常我的回答都是:不好说,看情况。
0 0
如何做一个俄罗斯方块游戏(二)
整个系列教程计划按照这个流程图开展,这也是我制作整个游戏的过程,今天我们就来看一下“随机生成形状”这个模块。
0 0
整合到一起,做出小游戏(下)
终于到了真正动手做游戏的时刻,在这一节里,我会带你从头开始将我们的“太空保卫者”按照设计方案制作出来。这一节里的内容会非常的多,一遍消化不了,可以多读几遍。别着急,慢慢来。
0 0
整合到一起,做出小游戏(上)
终于到了真正动手做游戏的时刻,在这一节里,我会带你从头开始将我们的“太空保卫者”按照设计方案制作出来。这一节里的内容会非常的多,一遍消化不了,可以多读几遍。别着急,慢慢来。
0 0
C++游戏系列5:不止有一件武器
更多见:C++游戏系列目录 知识点:对象数组作为数据成员 改进:每个角色所持有的武器不只一件,故持有的武器,用了对象数组来表示,当然,也可以是空手。由此而带来的,还得记录一共有几件武器,当前手持哪种武器。 【项目-角色有多样武器】 1.game.h:类声明 #ifndef GAME_H_INCLUDED #define GAME_H_INCLUDED #inc
777 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
对话式交互从开端到成长
立即下载
对话交互:从开端到成长
立即下载
案例:打造超越用户期待的服务体验
立即下载