判断某点是否在封闭曲线之内——lineGirl碰撞算法讨论
作者 佚名技术
来源 服务器技术
浏览
发布时间 2012-07-13
|
lineGirl游戏是一类画线游戏,游戏方法是在一幅图上画线"圈地",如果画线未封闭之前被怪碰到则回到起点并失去生命一次.目标是在生命全部失去前圈够足够百分比的"地".闪客帝国上有朋友做过此游戏,点击进入游戏"天蚕变之希望篇" 这里仅就其中怪物碰撞到已划定的"地"反弹回来的算法简单讨论一下. 怪物碰到"地"被反弹,如果将"地"看作一封闭曲线,那么问题转变为判断怪是否进入封闭曲线,如果进入则被反弹(弹出曲线外).再进一步抽象,把怪看作一个质点(事实上应该把怪的四边看作四个质点,任一个进入封闭曲线后即被反弹,但这里不影响核心算法),那么问题转变为如何判断某点是否在封闭曲线内. 明确了核心算法后就可以开始用数学方法讨论了,不过别担心,我不会写公式的:) 首先看看一般情况,请看下图(见图一):  图一:一般情况判断某点是否在封闭曲线内. 如图所示,A点在曲线S内,那么可以证明,由A点作任一方向的射线,该射线与曲线边的交点有奇数个.而相反如果在曲线S外,如点B,则交点有偶数个.这个定理很好理解,这里不作多述. 好了,明确了这条定理后我们就有方向了,考虑一下lineGirl类型的游戏中所画的封闭曲线并不是任意的,而是只有直角的,线条只有水平和竖直两种,那么我们可以把射线方向确定一下,比如限定为水平方向,如下图所示(见图二):  图二:直角多边形(曲线)中判断某点是否在其内. 如上图,问题关键是:如何判断某点(比如A点,它在S内)是否在曲线S内呢?这里我们必段假定曲线是已知的,也就是曲线上各顶点坐标已知,且各点连接顺序已知,我们观察一下S的特点可以发现,如果A点纵坐标在某一段竖直线段两个端点坐标纵坐标之间,比如CD线段,那么与该线段必有一个交点(即交点1).否则则没有交点,比如线段AB.根据顶点顺序可以顺次查找符合条件的线段(两端点必为相邻顶点),如果总线段数为奇数,则该点在S内. 另外,对于点是否在线上可以单列出来首先判断,虽然可以把在线上作为一种在曲线内的特殊情况,但是单列出来也不会太麻烦,而且代码可能更清晰.这都不是问题. 有了以上两种一般情况的铺垫,下面我们可以很容易地解决lineGirl中的实际问题了.这是因为在实际制作游戏过程中我们可以使用二维数组. 稍微解释一下如何使用二维数组来构造游戏: 我们控制人物移动和怪物移动的最小单位为某一定值,这样就可以以该值为最单位将场景分为若干小块,每一小块都是二维数组中的一个元素."圈地"就抽象为在二维数组中作标记,标记越多"地"也图得越多.而且计算"圈地"的百分比也较容易. 在数组下讨论判断就更容易了,如下图(见图三):  图三:数组情况下对于封闭曲线的判断. 点A在曲线内,每一方格代表一个数组元素,人物移动的最小长度就是方格的边长.以A为端点作水平射线也就是取出A点所代表的数组元素中的同行脚码比A小的元素,如图所示,一共有三个交点.观察一下这三个交点可以发现这样的判断规律:交点左右一边是未圈中地(即在曲线外),另一边是圈中地(即在曲线内),由于不存在"曲线上",所以我们只要数清楚这样的前一元素是未圈中地/圈中地,后一元素是圈中地/未圈中地的个数就可以了,更进一步,圈中地和未圈中地把射线分为了若干段,比如A的射线分为了两段属于圈中地,两段属于未圈中地,如果未圈中地的段数为偶数段,则点A在曲线内(圈中地内),反之如果为奇数则在圈中地外. 以上判断算法可纯算作个人笔记,因为我还没有去做一个DEMO,有朋友正在做,所以只是一点儿意见而已.不对之处希听指正. 关键词： |
凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢! |
你可能对下面的文章感兴趣
上一篇: Flash实现水波效果的一个实例下一篇: as的画圆形的动画效果
关于判断某点是否在封闭曲线之内——lineGirl碰撞算法讨论的所有评论
