2D游戏地图地表生成技术

2D游戏地图地表生成技术 杨涛，秦可，吴飞，庄越挺 (浙江大学人工智能研究所，浙江，杭州310027，0571—87951853) Email：susanyang@zju．edu．cn，explorercn@sohu．tom， wufei@cS．zju．edu．cn，yzhuang@cS．zju．edu．cn 摘要：在做2D游戏地图编辑时，如何让不同地表间能自然过渡，如何使地图地表间的过渡拼接能自 动完成，一直是大型地图系统编辑时比较棘手的问题。通过对现存地表及其边缘生成算法进行。针 对它们面对的问题提出了一种新的2D地表智能生成算法。该算法采用先拼接后处理地砖间过渡的方 法，通过给不同类的地砖分配不同的优先级，并按优先级从低到高的顺序来统一处理过渡，很好地解决 了图片量大及多种地砖衔接时自然过渡的游戏地表拼接问题。 关键字：斜角视觉游戏，地表过渡，地砖 2DGamesTerrainGeneration YangTao，QinKe，WuFei，ZhuangYueting (ThebutituteofArtifwialIntelligence，乃巧缸馏University，Hangzhou310027。China) Abstract：Duringthegamemapeditingprocess，howtomaketheterraintransitionbetweenvariouster- raintilesnaturally，andhowtoautomaticseamlesslygenerateterrain’SedgeisalwaysatoughproblemtOgame designers．Accordingtotheanalysisofthecurrentgameterraintransitiontechnologies，anovelmetlxxlispro- posedtohandlingtheterraintransitionin2Dgames．Firstly，tileswereplacedonthegamemapwithoutter． raintransitionbetweendifferenttiles，thenafterthegamemapisfinishedalltheterraintransitionproblem werehandledtogether．Withassigningdifferentprioritytothevariousterraintiles，andhandlingterraintran— sitionfromlow研嘶tytiletohigh面洲tyones，itiseasytogeneratecomplexgameterrains诵t11hugetileset andmuhiterraintransitionbetweenvarioustiles． Keywords：isometricgame，terraintransitions，tde 如何使得游戏中的场景做得更加逼真，一 直是游戏者们努力追求的目标。在斜角视 觉的2D游戏中为了让游戏画面丰富和逼真， 美工必须要制作大量的场景图片；另一方面，为 了提高游戏程序的画面绘制效率、方便图片资 源的管理和压缩游戏资源包的数据量，一般都 会在游戏场景资源制作的时候充分地考虑到图 片资源的重用问题，尤其是需要制作大量的游 戏地图地表元素时，图片资源重用是必不可少 的，其中的难点就是在重用地表地图资源时如 一何能自动地处理地表元素图片拼接时不同材质 地表间的过渡问题，比如：如何处理草地、沙漠、 沙滩和海洋等材质地表问的自然衔接问题，使 自动拼接后的效果更加的逼真。 对于地图地表的生成技术，现存的算法主 要有两大类：一是进行地表拼接时同时处理地 表问过渡问题；二是先进行地表拼接，再统一处 理地表间过渡问题。其中第一类算法中具有代 297 八、计算机游戏 表性的如著名游戏《星际争霸》的地图编辑器中 的地表生成方法。该算法中，最基本地图图元 由12片小矩形组成，地表生成时，通过层层覆 盖来实现地表间的过渡。这种算法生成地表过 程比较直观，且对于地表类型不复杂的情况下， 能生成令人满意的地表效果，但是在处理多种 地表衔接时效果并不理想。第二类算法代表有 《帝国时代Ⅱ》。《帝国时代Ⅱ》使用的方法是专 门制作各种地表间衔接的Tile图片，在地图放 置某个坐标处的地表时对其周围的地表进行判 断，从而决定是否需要处理地表的衔接，如果 要，则选择合适的Tile图片，在必要时还需要 改变周围已经放置好的Tile图片。这种方法 很好地解决了多种地表衔接时的过渡处理，但 是由于要专门制作各种地表问衔接的Tile图 片，即每两类地砖有一组过渡tile，所以这种方 法需要的图片量是相当大的。针对图片量的问 题，DavidMichael【2】提出了另一种算法。给不 同的地表赋予不同的优先级，并为每一种地表 制作32种过渡tile，在处理过渡时，对于每一个 tile，覆盖它的过渡tile以优先级从低到高的顺 序来绘制。这种方法减少了图片量，并实现了 多种地表衔接处理，它的缺点是过渡处理时比 较繁锁。 针对现存地图地表生成算法中出现的如上 问题，本文提出了一种新的算法。该算法采用 先绘制基本地砖，再处理地砖间的过渡问题的 +基本思想。和现存的算法相比，在图片量方面 又有了更迸一步的减少，另一方面通过给不同 类地砖分配不同的优先级，并按优先级从低到 高的顺序来统一处理过渡的方法使得地表问过 渡处理简单化，同时多种地表衔接问题也得到 了令人满意的效果。 地图地表智能生成算法 本文中所采用的地图地表智能生成算法主 要思想如下：给不同类(材质)的地砖分配不同 的优先级，不同类地砖拼接时，总是较高优先级 地砖覆盖较低优先级地砖；为每类地砖设计过 渡地砖；采用先拼接，后统一处理过渡问题的方 298 法绘制地图(地表)。即，先不考虑不同材质地 表间过渡问题而只做简单的地表拼接，最后再 根据不同地砖的优先级设置来处理过渡问题。 1．1地图重叠拼接处理 在斜视角游戏中表示地表的tile为菱形， 考虑到计算机中处理的图片都是矩形，故采用 矩形图片存放菱形Tile，如图1所示。这样处 理，在进行地图地表拼接时，会出现重叠部分。 采用镂空图的方法解决这一问题：在贴图时，图 片的背景是透明的。镂空间的制作原理是利用 屏蔽，并使用绘图函数对图片与屏蔽中每一个 像素进行逻辑AND运算。 图1地块单元及重叠拼接 1．2优先级设置及过渡地砖设计 本文所述算法中，给不同材质的地表(地 砖)分配不同的优先级．当两种不同类型的地砖 拼接时，总是较高优先级的地砖覆盖较低优先 级的地砖。图2所示为本算法采用的优先级设 置，从左到右优先级依次从低到高。 图2地砖优先级设计 在设计过渡地砖时，我们采用的方法为：为 每类地砖制作一组过渡tile。考虑每一块地砖 与八个方向的地砖相连(地图边缘tile除外)， 即有可能向八个方向过渡：四个边方向及四个 角方向(如图3所示)。 将八个方向分成两组：边方向及角方向，两 组方向分别处理。 1)角方向过渡地砖：此情况较简单，针对四 个方向只需四个角过渡地砖。如图4所示。 2D游戏地图地表生成技术 图3与中心地砖相邻的八个方向地砖 Edge·nOrtjwest Edgc-nOrtjwest Edge_southeast Edgesoutheast ＼∥ <>《爹◇ ＼／／ 图4中心地砖及角过渡地砖 <≥≤≥<》≤》《》 ≤>《>≤≥《≥《》 《：>《》《>《》《》 <萝<》《萝《≥《》 图5四个边方向可能的过渡地砖 2)边方向过渡地砖：对于边方向过渡地砖， 除了中心地砖，同时还需考虑包围该相邻边方 向地砖的其它地砖。综合考虑，针对每一个边 方向， 给出可能出现的过渡地砖如图5所示。从 图5可以看出，四组边过渡地砖中存在重复块， 实际所需的边过渡地砖为13块。在之后的算 法描述过程中将解释重复的过渡地砖在实际地 图地表生成过程中如何被处理。 通过对角方向和边方向过渡情况分别讨论 得出，在实际算法中，每类地砖只需18个过渡 地砖，包括4个角过渡地砖、13个边过渡地砖 和一个基本地砖。如此，极大地减少了图片量。 其中，过渡地砖中地表只占图片中的某一部分， 无地表的部分透明(可采用楼空图的做法)。 1．3地图地表拼接及过渡问题处理 我们采用如下方法自动生成地图地表：先 绘制tile再统一处理tile的过渡问题。 在详细介绍具体算法之前先引入一个重要 的数据结构：地砖类链表。为每类地砖维护一 个链表，该链表记录地图地表中该类地砖的位 置，以便在处理过渡问题时对同类地表的过渡 统一处理。考虑到优先级设定的规则：较高优 先级地砖覆盖较低优先级地砖，不存在优先级 最低的地砖向其它类地砖的过渡问题，故勿需 为优先级最低的地砖类维护链表。 生成地图地表第一步：绘制地砖。在这一 阶段，不考虑不同材质地砖间的过渡问题。设 计师可根据需要在地图的任意位置绘制不同地 砖，以满足游戏场景需要。在绘制地砖时，同时 为每类地砖维护它们的地砖类链表：地图中每 绘制一块地砖，就将该地砖(实际上是该地砖在 地图中的索引)添加到其类地砖链表尾部。简 单绘制完所有地砖后，地图地表基本成型，但由 于没有对不同材质地砖问的过渡进行处理，所 以地表看上不自然。 生成地图地表第二步：处理不同材质地砖 间的过渡问题。我们采用的处理过渡问题算法 基本思想是：按优先级从低到高的顺序统一处 理过渡。由于优先级最低的地砖不存在向其它 优先级地砖过渡的问题，故从地图中优先级为 2(在此为黄色地砖)的地砖开始处理过渡。对 优先级为2的每块具体地砖，如果与该地砖相 邻的八个方向存在优先级比2低的地砖(如蓝 色地砖)，则将优先级为2的地砖类相对于该方 向的过渡地砖覆盖于优先级较它低的地砖上。 当地图中所有优先级为2的地块均处理完毕 299 八、计算机游戏 后，再处理优先级为3的地砖，以此类推，直至 地图中所有地砖全部处理完毕。 在本算法中，对每一个具体地砖，将与它相 邻的八个方向分为四个角方向和四个边方向分 别检查(本文中所指边方向和角方向均是针对 菱形地砖来说的)。在具体检查过程中，采用先 角方向后边方面的顺序进行。 1)角方向地砖检查：角方向可按西、北、东、 南的顺序进行检查。如果角方向相邻地砖(基) 类型的优先级低于中心地砖的优先级，则 将该中心地砖相对于此角方向的过渡地砖覆盖 相邻角地砖。考虑到，每一个角过渡地砖中的 地表是夹该角的两个边过渡地砖中地表的一部 分，故为避免重复绘制，在检查角方向时：同时 考察与中心地砖边相邻的，夹该角方向地砖的 优先级。如果相邻边方向地砖的优先级等于中 心地砖的优先级，即边方向地砖与中心地砖属 同类地砖，这样，当这些边地砖为被处理地砖时 会向原角地砖进行边过渡。所以，在此情况下， 角过渡地砖不绘制。 2)边方向地砖检查：边方向可以按西北、东 北、东南、西南的顺序进行检查。考虑如下情 况：被处理地砖记为mid—tile，与它边相邻的地 砖记为tile—j，考察方向为东南方向。图6列 出向东南方向检查可能的过渡地砖情况。从该 图可以看出，检查相邻边方向地砖时，不同只考 虑被探测地砖tile—j的优先级高低问题，而要 根据如下步骤进行检查： (a) (b) (c) (d) (e) 图6东南方向边过渡地砖 (左上角的黄色地砖为mid—title，中间蓝色地砖为tile—j) (a)检查tile—j的优先级是否小于mid— tile的优先级，如果不小于，转d)。 (b)检查与mid—tile角方向相邻且为tile —j边相邻地砖的优先级是否均等于mid—tile 的优先级。如均不等，将mid—tile类的地砖相 对于这个方向的过渡地砖A覆盖tile—j，并转 d)，见图6(a)情况。 (c)检查与tile—j边相邻的第四块tile。 综合考虑包围tile—j的四块边相邻地砖的类型 (优先级)，针对图6(b)、6(c)、6(d)、6(e)的情 况将mid—tile类地砖的相应的过渡地砖覆盖 tile—jo标记tile—j为已经综合处理过的地砖。 (d)结束检查。 由于被综合处理的地砖，即图6中(b)， (c)，(d)，(e)四种情况中的tile—j会被不只一 个mid—tile检查，为避免重复绘制，当某一地 砖第一次被综合处理时就将其标记为已综合处 理过的地砖。当下一个可能会对tile—j综合处 理的地砖为当前被处理地砖mid—tile时，如果 检查综合处理标记为真，则不对此tile—j处理。 300 综合以上各方面讨论，斜角视觉2D游戏 中地图地表生成技术的算法为： ， 1)为类地砖分配优先级，并为每类地砖制 作基地砖及17个过渡地砖，用镂空法对各个地 砖进行处理； ‘ 2)在地图上绘制基本地砖，同时为各类地 砖(除优先级为1的地砖类)维护其地砖类链 表，地砖类链表存放地图内此类地砖的所有地 砖； 3)按同类过渡地砖统一处理的方法，逐层 绘制过渡地砖。此过程通过如下规则实现：按 优先级从低到高的顺序依次遍历各类链表，对 每一个类链表中的地砖，采用上文提到的过渡 检查算法处理与它相邻的四个相邻角地砖及四 个相邻边地砖。 2实验结果及说明 图7、图8显示了两组地图地表智能生成 算法的实验结果。 2D游戏地图地表生成技术 (a)处理过渡前 (b)处理过渡后 图7实验结果1 (a)处理过渡前 (b)处理过渡后 图8实验结果1 从实验结果可以看出，采用地图地表智能 生成算法，使得不同材质地表间能够自然过渡。 图9中还展示了多种不同材质地表同时衔接时 过渡问题处理效果：处理前，第三排第三列的绿 色地砖周围存在四种与它不同材质的地砖，从 处理后的地表图可以看出，当多种地砖同时衔 接时，过渡效果仍是令人满意的。 3 结论与展望 。 本文所提出的2D游戏中地图地表生成技 术能自动处理不同材质地表间过渡问题，加快 了地图生成的速度，具有图片量小、过渡问题处 理简单、多种地表同时衔接时自然处理过渡问 题等优点。采用此算法，使得斜角视觉的2D 游戏场景更加逼真，实现在不同材质地表问的 无逢拼接。 地图地表智能生成算法虽然取得了令人满 意的处理效果，但由于生成地表时采用先拼接 后处理过渡的方法，故生成过程不直观，地图地 表的修改也不方便。以上的不足之处以待我们 的深入研究去逐步解决。 参考文献 [1】L．Gautier，C．Diot．DesignandevaluationofMi— Maze,aMultiplayerGameoiltheIntemet．IEEE MultimediaSysteanConference．Austin．June28- July1，1998． [2】DavidMichael，Tile／Map-BasedGameTechniques： HandlingTerrainTransitions，一http：／／www一． game——d——e—v—,net／reference／articles／article934,asp [3]D．Kalles，E．Ntoutsi．Interactiveverificationof gamedesignandplaylngstrategies．T(Ⅺ1SwithArti— tidalIntdligence，2002．Proceeding，14thIEEEIn· ternationalConferenceon，4—6Nov．2002：425．430． [4】S．Cass．Mindgames．Spectrum，IEEE，Volume 39，Issue12，Dee．2002．：40—44 [5]L．Bishop，D．Eberly，T．Whitted，etal．Edslgning aPCgameengine．ComputerGraphicsandApplica— tions，IEEE，Volume18，Issue1，Jan．．Feb．1998： 46．53 [6]荣钦科技。游戏设计概论，北京科海电子出版社， 2003 [7]荣钦科技，VisualC+十游戏设计(第二版)，北京科 海电子出版社，2003 [8]DonaldHeam，M．PaulineBaker，计算机图形学(第 二版)，电子工业出版社，2003 301 2D游戏地图地表生成技术 作者： 杨涛， 秦可， 吴飞， 庄越挺 作者单位： 浙江大学人工智能研究所,浙江,杭州,310027 本文链接：http://d.g.wanfangdata.com.cn/Conference_6203602.aspx 下载时间：2009年11月5日