【Android论文栏目提醒】：网学会员--在 Android论文编辑为广大网友搜集整理了：基于Android平台的弹幕类游戏碰撞检测实现 - 大学课件绩等信息，祝愿广大网友取得需要的信息，参考学习。
南京邮电大学 毕 业 设 计（论 文）题 目 基于
Android 平台的弹幕类游戏碰撞检测实现专 业 测控技术与仪器学生姓名 周慧芹班级学号 B080501 B08050104指导教师 王保云指导单位 自动化学院 日期：2012 年 3 月 12 日至 2012 年 6 月 15 日 毕业设计（
论文）原创性声明 本人郑重声明：所提交的毕业设计（
论文），是本人在导师指导下，独立进行研究工作所取得的成果。
除文中已注明引用的内容外，本毕业设计（
论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。
对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。
论文作者签名： 日期： 年 月 日 摘 要 弹幕射击类游戏中，游戏玩家在躲避满屏幕的子弹时，游戏系统在每个周期都需要对 N 个碰撞对进行检测，这样非常耗时，效率很低，影响游戏的生动性与顺畅度。
因此，如何提高游戏中的碰撞检测效率是一个很重要的问题。
本文介绍了碰撞检测理论基础，包括数学与几何学知识以及常用的碰撞检测理论，研究了针对弹幕射击类游戏的碰撞检测算法，并利用 C编程实现了所设计的算法。
为了解决效率问题，本文对子弹采取子弹链的方式进行数据的存储，每个角色指向自身的子弹，避免对自身发出的子弹进行检测。
同时，在面对满屏幕的子弹时，采取空间划分的方式，剔除不可能发生碰撞的子弹，确定潜在碰撞集，减少不必要的碰撞对的检测，加快检测速度。
针对不同的碰撞情形，优先考虑检测效率或者检测精确度，分别选择圆形包围体和多边形包围体对人物进行物理模拟。
关键词：弹幕游戏；碰撞检测；空间划分；包围体；潜在碰撞集； ABSTRACT In the bullet hell game the game system needs to detect the collision of N pairs of roleand bullet when gamers escape out of the bullets full of the screen in each cycle. This willconsume a large amount of time and will be inefficient. Soit’s of much importance to improvethe efficiency of collision detection. This article describes the theoretical basis of the collision detection including mathematicsand geometry knowledge and collision detection theory and finally we explore the collisiondetection algorithm for the bullet hell and complete the commissioning and operation of the codein C environment.In order to improve the efficiency of collision detection and make the gamerun more smoothly and lively we reduce the unnecessary collision detection by storing thebullets as bullet chains and linking each role to its own bullet chains. Meanwhile we divide thespace to remove unnecessary bullets and identify the potential collision set when we do thecollision detection about the bullets full of screen .The speed of collision detection is apparentlyaccelerated in this way . For different collision situations we give priority to detectionefficiency or detection accuracy respectively and choose circular bounding volume or polygonbounding volume to simulate the characters physically .Key words：barrage game；collision detection；space division；bounding volume； potential collision set； 目 录第一章 绪论 ...............................................1 1.1
Android 系统 ................................................ 1 1.1.1
Android 系统简介 ...................................... 1 1.1.2
Android 系统的发展 .................................... 1 1.2 开发环境及语言介绍 ......................................... 2 1.2.1Linux 环境下 Bash shell 编程 ........................... 2 1.2.2Eclipse 环境下的 C编程 ............................... 2 1.3 弹幕射击游戏的发展现状介绍 ................................. 3 1.4 本章小结 ................................................... 4第二章 碰撞检测算法原理 .....................................5 2.1 碰撞检测的研究现状 ......................................... 5 2.1.1 研究碰撞检测的意义 ................................... 5 2.1.2 国内外研究现状 ....................................... 5 2.2 碰撞检测的基本概念 ......................................... 6 2.2.1 凸多边形 ............................................. 6 2.2.2 多边形凸性测试 ....................................... 7 2.2.3 包围体 ............................................... 7 2.2.4 优化操作 ............................................. 9 2.3 碰撞检测的基本算法 ........................................ 10 2.3.1 基于 GPU 的碰撞检测 .................................. 10 2.3.2 基于分离轴定理的多边形相交测试 ...................... 12 2.3.3 基于空间划分的网格测试算法 .......................... 14 2.4 本章小结 .................................................. 19第三章 算法设计与实现 ......................................20 3.1 本文术语定义 .............................................. 20 3.1.1Hero ................................................. 20 3.1.2Boss ................................................. 20 3.1.3Barrage .............................................. 20 3.2 算法主要功能 .............................................. 20 3.3 弹幕系统的分类与其包围体 .................................. 21 3.3.1 弹幕系统 ............................................ 21 3.3.2 包围体的选择 ........................................ 22 3.4 预处理 .................................................... 24 3.4.1 设置子弹链 .......................................... 24 3.4.2 两种坐标系统 ........................................ 25 3.5 基于空间划分的碰撞检测算法 ................................ 26 3.5.1 算法基本思想 ........................................ 26 3.5.2 潜在碰撞集的确定 .................................... 27 3.5.3 碰撞检测计算 ........................................ 28 3.6 基于 AABB 矩形包围盒的碰撞检测算法 ......................... 28 3.6.1 算法基本思想 ........................................ 28 3.6.2 基于 AABB 包围盒的碰撞检测 ........................... 29 3.6.3 基于分离轴定理的多边形碰撞检测 ...................... 31 3.7 基于几何图形的碰撞检测算法 ................................ 31 3.7.1 算法的基本思想 ...................................... 31 3.7.2 基于几何图形的碰撞检测 .............................. 32 3.8 本章小结 .................................................. 33第四章 算法测试与性能分析 ................................34 4.1 算法综述 .................................................. 34 4.2 测试结果 .................................................. 34 4.2.1 圆形与矩形 .......................................... 34 4.2.2 矩形与多边形 ........................................ 35 4.3 本章小结 .................................................. 36结束语 …………………………………………………………………37致 谢 …………………………………………………………………38参考文献..................................................39附录 A 游戏中碰撞检测实现代码 .............................40 南京邮电大学 2012 届本科生毕业设计（
论文） 第一章 绪论1.1
Android 系统1.1.1
Android 系统简介
Android 一词的本意是“机器人”，同时也是 Google 于 2007 年 11 月 5 日发行的开源手机操作系统。
Android 是一个以 Linux 为基础的开放源代码操作系统， 运行于 ARM9 构架的 CPU，该平台由操作系统、中间件、用户界面和应用软件组成，是一个真正意义上的开放性移动设备综合平台。
它包括操作系统、用户界面和移动电话工作所需的全部软件，而且不存在阻碍移动产业创新的专有权障碍。
类似于诺基亚的 Symbain 和微软的 WindowsMobile。
同其他操作系统一样，
Android 采用了分层的系统架构，从高层到低层分别是应用程序层、应用程序框架层、系统运行库层和 linux 核心层。
Android 系统同一系列核心应用程序包一起发布，这些应用程序都是使用 Java 语言编写，包括 email 客户端、日历、地图等程序；应用程序框架层是应用程序的核心，是所有的应用开发都必须遵循的框架原则；
Android系统架构会包含一些 C/C库来支持我们使用的各个组件，使其更好的服务，包括系统 C库、多媒体库、SGL、SQLite、Webkit 等；底层以 linux 内核工作为基础，由 C 语言开发，只提供系统基本功能，如安全性、内存管理、网络协议栈等，同时 linux 内核也作为硬件和软件栈之间的抽象层。
1.1.2
Android 系统的发展 2007 年 11 月 5 号，谷歌公司正式向外界展示了名为
Android 的操作系统，并且宣布成立一个全球性的联盟组织，该组织由 34 家手机制造商、软件开发商、电信运营商以及芯片制造商共同组成。
这一组织支持谷歌发布的手机操作系统以及应用软件，共同开发
Android 系统的开放源代码。
Android 第一版于 2008 年 9 月发布，目前最新版本为
Android4.0 ，（冰激凌三明治） 于 2011 年 10 月 19 日在香港发布。
在目前市面上几大系统中，
Android的市场占有率最高，上升速度最快。
1 南京邮电大学 2012 届本科生毕业设计（
论文）1.2 开发环境及语言介绍1.2.1Linux 环境下 Bash shell 编程 Shell 是一种具备特殊功能的程序，它是使用者和 UNIX/Linux 操作系统的核心程序kernel 间的一个接口。
为了对用户屏蔽内核的复杂性，也为了保护内核以免用户误操作造成损害，在内核的周围建了一个外壳——shell，用户向 shell 提出请求，shell 解释并将请求传给内核。
本质上，shell 脚本是命令行命令简单的组合到一个文件里面。
Shell 基本上是一个命令解释器，类似于 DOS 下的 command.com，它接收用户命令，然后调用相应的应用程序。
不同的是，在 DOS 下，command.com 只有一个，而在 Linux 下流行的 shell 有好几个，如 bash、ksh、csh、zsh、ash 等，一般 Linux 系统都将 bash 作为默认 shell。
通常情况下，我们从命令行输入命令每输入一次就能够得到系统的一次响应。
一旦需要我们一个接着一个的输入命令而最后才得到结果的时候，这样的做法显然就没有效率。
要达到这样的目的，通常我们利用 shell 程序或者 shell 脚本来实现。
从程序员的角度来看，Shell 本身是一种用 C 语言编写的程序，从用户的角度来看，Shell 是用户与 Linux 操作系统沟通的桥梁。
用户既可以输入命令执行，又可以利用 Shell 脚本编程，完成更加复杂的操作。
Shell 编程有很多类似 C 语言和其他程序语言的特征，但是又没有编程语言那样复杂。
Shell 程序就是放在一个文件中的一系列 Linux 命令和实用程序，在执行的时候，通过Linux 一个接着一个地解释和执行每个命令。
1.2.2Eclipse 环境下的 C编程 Eclipse 是著名的跨平台的自由集成开发环境（Integrated Development Environment，IDE），是一个开放源代码的、基于 Java 的可扩展开发平台。
就 Eclipse 本身而言，它只是一个框架和一组被称为平台核心的服务程序，用于通过插件组件构建开发环境。
虽然Eclipse 是使用 Java 语言开发，常用做 Java IDE，但是由于拥有很多插件支持，因此 Eclipse拥有较佳的灵活性，支持诸如 C/C、Python、PHP 等主流语言开发。
正因为此，本文的算法也选择 ubuntu11.10 下 Eclipse Indigo 环境下进行 C编程测试。
Eclipse 不直接支持 C，它使用外部插件 C/C开发工具箱（C/C DevelopmentToolkit）提供支持。
CDT 是完全用 Java 实现的开放源代码项目，作为 Eclipse SDK 平台的一组插件，它提供包括 C/C编辑器、C/C调试器、C/C Launcher、剖析器、内容提示以及 Makefile 生成器等功能。
由于其复杂性，CDT 被分成几个组件，都采用独立插件的形式。
每个组件都作为一个独立自主的项目进行运作，有它自己的一组提交者、错误类别和邮件列表，但是插件之间相互依赖，CDT 的正常工作需要所有插件的支持。
CDT 插件的完整列表如下所示： 2 南京邮电大学 2012 届本科生毕业设计（
论文） （1） 主 CDT 插件：“框架”CDT 插件； （2） CDT 功能 Eclipse：CDT 功能组件（Feature Component）； （3） CDT 核心：提供核心模型 、 （Core Model）CDOM 与核心组件 ； （Core Component） （4） CDT UI：核心 UI、视图、编辑器和向导； （5） CDT 启动：为如编辑器和调试器之类的外部工具提供启动机制； （6） CDT 调试核心：提供调试功能； （7） CDT 调试 UI：为 CDT 调试编辑器、视图和向导提供用户界面； （8） CDT 调试 MI：用于与 MI 兼容的调试器的应用程序连接器。
在安装 CDT 之前，首先必须确保 GNU C 编译器（GNU C compile，GCC）以及所有附带的工具如 make、binutil（在 linux 环境下，均可以通过终端命令安装获取）等都是可用的。
在 Eclipse 中安装 CDT 之后，选择相应的 C项目类型即可进行 C/C的编程。
1.3 弹幕射击游戏的发展现状介绍 弹幕射击游戏在亚洲范围内一般认为等同于 2D 平面射击游戏（包括卷轴射击游戏和自由移动的平面射击游戏），因其中敌我双方的子弹在屏幕上停留的时间较长且密度很高形成“幕状”而得名。
弹幕系射击游戏结合了“射击”和“闪躲”两大射击游戏要素，玩家要在敌人放出的大量子弹（弹幕）的细小空隙间闪避，能在玩家闪躲弹幕的时候给玩家带来快感。
此类游戏偏重于依靠精准微调和走位来躲避攻击，如著名同人游戏系列东方 project。
最先具有弹幕射击游戏特征的是在 1997 年发售的怒首领蜂，不过因为当时的电脑硬件及软件尚未先进，画面上能显示的弹幕和人物单位都被大大限制。
近年的计算机图形学（Computer Graphics，CG）处理技术已经发展成熟，在画面上显示百名角色和上千发弹幕已经不再是难题。
在 2000 年以后，类似怒首领蜂的射击游戏陆续出现，确立了弹幕射击游戏的形象。
弹幕射击游戏在日本比较发达，日式风格的弹幕射击游戏几乎都属于纵卷轴射击游戏，只有一部分的商业、同人弹幕射击游戏是属于横向卷轴射击游戏。
比较著名的弹幕射击类游戏有式神之城系列（Alfa System）、怒首领蜂系列CAVE、东方 project 系列（上海爱莉丝幻乐团）等。
目前，弹幕射击游戏如怒首领蜂、虫姬等在 ios 平台均有版本上线，同时获得很高的评价，但是在
Android 系统，目前只有一些破解的非正式的弹幕射击游戏，我们知道，
Android的市场占有率，相关公司也正在或者已经准备开发
Android 版本的弹幕射击游戏，以满足更多的弹幕游戏爱好者。
3 南京邮电大学 2012 届本科生毕业设计（
论文）1.4 本章小结 本章属于绪论部分，主要介绍了在游戏开发中所遇到的相关基础知识，虽然与算法没有直接关系，但是算法的提出与实现都依赖于这些知识与技术。
我们团队之所以会想到做这款弹幕射击游戏，主要是因为兴趣爱好，其次很重要的原因就是
Android 平台上的弹幕射击游戏非常少，一方面能够检验我们所学过的知识，另一方面也能多了解游戏市场动态，然后将自己的技术知识转化为实实在在的物品，真正做到理论与实践相结合。
通过本章的内容，读者能够了解本文的算法是为了弹幕射击游戏而设计，同时也了解到游戏的开发环境 Eclipse、开发语言 C以及运行平台
Android 操作系统。
基于本文的篇幅以及研究算法这一主题，这些必不可少的外部环境的介绍也很少，有兴趣的读者建议多看一些相关书籍与论坛包括博客园、
Android 开发网、
Android 优亿开发等。
关于弹幕射击类游戏，读者可以通过东方 project 了解更多。
在之后的第二章节中，本文将介绍碰撞检测理论的相关知识，在第三章节，本文将详细介绍针对本游戏图金志而设计的碰撞检测理论。
在第四章节，本文将对所设计的算法进行测试。
4 南京邮电大学 2012 届本科生毕业设计（
论文） 第二章 碰撞检测算法原理2.1 碰撞检测的研究现状2.1.1 研究碰撞检测的意义 碰撞检测（Collision Detection，CD）是计算机图形学和虚拟现实中最基本且非常重要的组成部分，广泛应用于虚拟制造、CAD/CAM、计算机动画、物理建模、游戏、机器人、路径和运动规划等领域。
随着计算机软硬件以及网络的日益成熟，特别是计算机图形学、计算机动画仿真和虚拟现实等技术的快速发展，我们需要一个成熟的控制机制来真实的模拟现实世界，以满足人们对交互实时性和场景真实性的要求。
因此，碰撞检测技术得到了广泛而深入的研究，成为模拟现实世界不可或缺的技术。
碰撞检测技术作为一种用于判断一对或者多对物体在给定时间区域内的同一时刻是否占有共同区域的方法，其基本任务是判断两个或者多个物体彼此之间是否发生穿透或者接触，也就是判断在某一时刻两个集合模型是否发生干涉，如果集合模型之间发生碰撞，则进行相应的反馈，几乎在所有游戏中均有所应用。
碰撞检测问题是基于现实生活中一个普遍存在的事实——两个不可穿透的对象不可能共享相同的空间区域。
游戏中，无论是物体与物体之间还是物体与场景之间，如果没有碰撞检测，那么物体之间的穿行就变成透明的，这无疑影响玩家对于真实性的体验。
弹幕射击类游戏是一种二维游戏，玩家在控制自身运动的同时，既要躲避敌人发射的子弹，又要向敌人发射子弹，游戏高手要在看似水泄不通的敌群之间找出一条安全路径，以毫厘之差躲过铺天盖地的子弹。
弹幕射击类游戏的特色就在于它的节奏，不同于寻常射击游戏那种争分夺秒的紧张感，也没有要迫切消灭敌人的疯狂射击，弹幕射击类游戏的精髓就在于玩家体验“擦弹”的感受，而这种“擦弹”的感受基于有效的碰撞检测技术。
弹幕游戏碰撞场面中，成千上万的子弹在纷飞，检测角色与子弹是否发生碰撞，需要进行巨量的数据计算，耗费大量的运行时间。
因此要求碰撞检测算法设计要简单实用、耗时少，使得整个游戏运行更流畅、更平滑、更生动。
2.1.2 国内外研究现状 近年来，国内外研究人员已经在碰撞检测领域中做了很多意义重大的工作，设计出一些比较成熟的算法，并开发了相应的软件包。
针对不同的研究对象，研究人员采用不同的研究方法，最终提出了种类繁多的碰撞检测方法，适应于不同的场合，推进了虚拟现实技术的发展。
5 南京邮电大学 2012 届本科生毕业设计（
论文） 静态干涉检测算法是最早被研究的领域，在这方面，Ganter 和 Agarwal 做出了重大的贡献。
该类算法主要用于检测静止状态中各物体之间是否发生干涉，如机械零件装配过程中的干涉检查等等。
这类算法对实时性要求不高，但对精度有较高的要求。
由于对准确性要求.
上一篇：
android_无线点餐
下一篇：
猪疥癣病的防治
2013-9-18
